缓存寻址方法混乱 [英] Cache Addressing Methods Confusion
问题描述
我一直在阅读缓存的四种解决方法：
- 物理索引物理标记（PIPT）
- 物理索引虚拟标记（PIVT）
- 虚拟索引物理标记（VIPT）
- 虚拟索引虚拟标记（VIVT）
以下哪些缓存会受到同义词和同义字的困扰？
我知道VIVT会遭受这些问题的困扰，而PIPT不会。但是PIVT和VIPT呢？为避免错误遗漏），在VIPT高速缓存中，同义词可能（实际上）被索引到不同的高速缓存集（在这种情况下，数据不一致是可能的，例如，在一组中写入同义词，然后读取同义词[物理上相同地址，另一组中的不同虚拟地址）），而在PIVT高速缓存中，同义词总是映射到同一组，但是虚拟地址的标记部分中的差异可能会导致未命中。
（直接映射的PIVT高速缓存在未提供服务之前对受害块进行写回操作将避免同义词问题，因为实际访问的[物理地址]必将强制驱逐任何同义词，因为物理地址索引会相同，并且该索引处只有一个块。通过直写直接映射的PIV出于相同的原因，T缓存的行为类似。最新的数据值将位于后备存储[L2或内存]中。假定任何写缓冲区或L2高速缓存都经过物理标记。如果在未命中服务后未更新后备存储，则错误的未命中[虚拟地址与标签不匹配但具有相同的物理地址]可以从后备存储读取陈旧数据。）
（请注意，PIVT通常仅在虚拟索引与物理索引相同时才有意义，即，使用页面偏移量内的虚拟位时。如果已经足够早地知道完整的物理地址以对缓存进行索引，则存在没有理由不使用标签的物理地址。）
使用直写不会消除同义词问题，只要同义词可以映射到缓存中的不同块即可。如果任何索引位可能不同（使用虚拟索引）或提供的方式不止一种，那么过时的值可能会保留在该替代位置，并且当使用其他虚拟地址探查缓存时找不到该值。当第二读取A为缓存命中时，读取A，写入B，读取A（其中A和B是同义词）的序列可能使第二读取A看不到写入B的结果。 （即使具有直接映射的直写式高速缓存，也需要对任何写缓冲区进行物理标记（由于写缓冲区相对较小，因此物理索引不是问题）。）
在L1高速缓存中同时存在两个同义词并先写入一个变量，然后又读取另一个变量的可能性可能极低，但仍然期望此类情况将得到正确处理。
由于当同一个虚拟地址映射到不同的物理地址（人希望避免错误命中）时发生同音异义词，所以在VIPT缓存中，同义词将映射到相同的缓存集，但标签却不同（因此不会有错误命中） ），而在PIVT缓存中，同音词可能会映射到同一集合（如果索引物理位碰巧匹配）并且在虚拟标记中会错误地匹配。
总之，不太可能的PIVT设计受同义词和同音异义问题的约束，而VIPT设计仅受同义词问题的约束。 VIVT设计具有不切实际的PIVT的所有问题，甚至更多（甚至特殊的直接映射情况也不起作用，因为当用于索引的虚拟地址位不同时，同义词可能会映射到不同的块）。
（对于多个内核/处理器，一致性通常由物理地址处理。尽管有可能提供将物理地址转换为虚拟地址的TLB模拟（至少一个PA-RISC处理器可能会这样做） ，从该翻译缓存中逐出会迫使被该虚拟地址标记的所有缓存块都被逐出，类似于因ASID用尽而导致的逐出。）
同义词和同义字的出现
可写同义词通常可能并不常见，但是一种出现的方式是文件是由多个进程映射的。显然，如果一个进程已经映射（例如，用于堆内存）另一进程用来映射文件的地址范围，则该进程无法将文件映射到另一进程正在使用的相同虚拟地址范围。
只读同义词可能更常见。一些操作系统使用整个系统上的单个零填充页面，并将许多虚拟页面映射到同一物理零页面（当程序尝试写入该页面时，使用写时复制）。如果对每个进程应用地址空间布局随机化（一种安全性功能），则不同的进程可能对相同的代码/文本物理页面使用不同的虚拟地址。
同形异义词最常见的形式与具有多个地址空间相关联。在常见的OS中，每个进程都被赋予了自己的地址空间（尽管OS通常为其自身保留该地址空间的一部分，并在不同进程中对该部分使用相同的映射）。通过将地址空间IDentifier附加到虚拟地址，可以使这种类型的同名异议问题变得更少。通过这种方式，仅当将ASID重新用于特定的虚拟标记缓存时，才需要对此类同名词进行特殊处理。 （ASID降低了特殊高速缓存管理的频率，以避免同音异义的问题，但是它们通常不能消除该问题。但是，即使降低频率，也可以通过降低性能要求来降低软件的复杂度；高度优化的代码通常都更困难
同形异义词的另一种形式是当页面被换出然后又换回到另一个地址的内存中时。如果I / O是从内存中完成的（不是某些处理器中的高速缓存），则OS必须至少回写所有高速缓存内容，因此刷新适当的内容将不再是问题。尽管页面将某些内容包含在缓存中的可能性（尤其是L1缓存，其中使用虚拟地址是最吸引人的原因，因为它具有延迟优势），但当OS认为页面是将其驱逐到磁盘的良好候选者时，这种可能性很低，并且任何此类内容的可能性都较低将一直保留在缓存中，直到页面被交换回内存的空间不足为止，即使这些不可能性的乘积也不为零。
无论如何，最好不要要求对
在Single Address Space OS中，由于所有进程都使用相同的虚拟地址映射到相同的地址，因此使用同一个地址空间OS不可能实现同义。物理地址，如果允许使用同义词，则用于只读存储器。在这种情况下，可以使用VIVT缓存而不会出现同音和同义词问题。 （SASOS可以简化进程间的通信。但是，类似UNIX的OS和其他一些OS是为多个地址空间设计的。）
只读存储器的数量不会带来正确性问题（仅可能由于错误的未命中而浪费带宽，而由于相同物理内存的重复缓存而浪费缓存容量）。这使得VIVT对指令高速缓存的吸引力降低。 （x86在要求指令高速缓存保持高速缓存一致的情况下有点不寻常，尽管提供一致的指令高速缓存可以简化某些软件。）
此外，可以通过使用VIPT高速缓存来处理同义词问题。初始虚拟索引作为一种方式预测的方式（探测未命中的备用集合-这是由AMD Athlon的64 KiB，具有4 KiB页的2向缓存实现的-或将包含物理索引的包含标签的L2缓存与用于索引L1的多余虚拟地址位，使先前缓存的L1虚拟索引处的块无效）或通过要求任何同义词对同一组缓存块进行索引（最简单的方法是通过页面着色，其中相应的物理地址位人为地相同作为用于索引的虚拟地址位。
I have been reading about the four ways a cache can be addressed:
- Physically Indexed Physically Tagged (PIPT)
- Physically Indexed Virtually Tagged (PIVT)
- Virtually Indexed Physically Tagged (VIPT)
- Virtually Indexed Virtually Tagged (VIVT)
Which of the following caches would suffer from the synonym and homonym issues? I know that the VIVT would suffer from these issues and PIPT won't. But what about PIVT and VIPT?
Since synonyms occur when different virtual addresses map to the same physical address (where one wants to avoid false misses), in a VIPT cache synonyms might be (virtually) indexed to different cache sets (in which case data inconsistency is possible, e.g., by a write to a synonym in one set followed by a read of a synonym [same physical address, different virtual address] in another set) while in a PIVT cache synonyms always map to the same set but a difference in the tag portion of the virtual address could result in a miss being indicated.
(A direct-mapped PIVT cache that does the writeback of the victimized block before the miss is services would avoid the synonym issue since the actual memory accessed [physical address] would necessarily force an eviction of any synonym since the physical address index would be the same and there is only one block at that index. A write-through direct-mapped PIVT cache would behave similarly for the same reasons; the most current data values would be in the backing store [L2 or memory]. This assumes that any write buffer or L2 cache is physically tagged. If the backing store is not updated before the miss is serviced, then a false miss [virtual address not matching the tag but having the same physical address] can read stale data from the backing store.)
(Note PIVT typically only makes sense when the virtual index is the same as the physical index, i.e., when virtual bits within the page offset are used. If one already knows the full physical address early enough to index the cache, there is little reason not to use the physical address for tags.)
Using write-through would not remove the synonym issue as long as synonyms could map to different blocks in the cache. If any index bits could differ (with virtual indexing) or more than one way was provided, then a stale value could remain in that alternate place and not be found when the cache is probed with a different virtual address. A sequence of read A, write B, read A (where A and B are synonyms) could have the second read A not see the write B result when that second read A is a cache hit. (Even with a direct-mapped write-through cache, any write buffer would need to be physically tagged [physical indexing is not an issue since write buffers are relatively small].)
While the probability of two synonyms being simultaneously present in L1 cache with a write to one followed by a read of the other might be extremely low, there is still an expectation that such cases will be handled correctly.
Since homonyms occur when the same virtual address maps to the different physical addresses (where one wants to avoid false hits), in a VIPT cache homonyms would map to the same cache set but the tags would be different (so there is no false hits) while in a PIVT cache homonyms could map to the same set (if the indexing physical bits happened to match) and would falsely match in the virtual tags.
In summary, the unlikely PIVT design is subject to synonym and homonym issues and the VIPT design is only subject to synonym issues. A VIVT design has all the issues of the unrealistic PIVT and more (even the special direct-mapped case would not work since synonyms could map to different blocks when the virtual address bits used for indexing are different).
(With multiple cores/processors, coherence is typically handled by physical addresses. While it would be possible to provide a TLB-analogue that translates physical addresses to virtual addresses [at least one PA-RISC processor might have done this], an eviction from that cache of translations would force any cache blocks tagged with that virtual address to be evicted somewhat similar to evictions caused by running out of ASIDs.)
Occurrences of synonyms and homonyms
Writable synonyms are probably not common in general, but one way they can occur is if a file is memory mapped by multiple processes. Obviously if one process has already mapped (e.g., for heap memory) the address range used by another process to map a file, then that one process cannot map the file to the same virtual address range that the other process is using.
Read-only synonyms might be more common. Some OSes use a single zero-filled page across the system and map many virtual pages to this same physical zero page (using copy on write when a program attempts to write to that page). If address space layout randomization (a security feature) is applied per process, different processes might use different virtual addresses for the same physical pages of code/text.
Perhaps the most common form of homonyms is associated with having multiple address spaces. In common OSes, each process is given its own address space (though the OS typically reserves part of that address space for itself and uses the same map for that section in different processes). This type of homonym can be made less problematic by appending an Address Space IDentifier to the virtual address. By this means, special handling of such homonyms is only necessary when an ASID is reused for a particular virtually tagged cache. (ASIDs reduce the frequency of special cache management to avoid homonym issues, but they do not eliminate the problem in general. However, even a reduction in frequency can made the software less complex by reducing performance requirements; highly optimized code is often both more difficult to produce and more difficult to maintain.)
Another form of homonym is when a page is swapped out and then swapped back into memory at a different address. If I/O is done from memory (not cache as in some processors), then the OS must at least writeback any cache contents so flushing the appropriate contents is less of an issue. While the probability that a page will have some contents in cache (especially L1 cache where using virtual addresses is most attractive because of the latency advantage) when the OS considers it a good candidate for eviction to disk is low and the probability that any such content will remain in cache until the page is swapped back into memory is low, even the product of these improbabilities is not zero.
In any case, it can be desirable not to require special handling of such cases even if the hardware designer cannot think of any worthwhile use for synonyms and homonyms.
With a Single Address Space OS, homonyms are impossible since all processes use the same mapping of virtual addresses to physical addresses and if synonyms are allowed they are for read-only memory. Under these conditions, VIVT caches can be used without the homonym and synonym issues. (SASOSes can simplify interprocess communication. However, UNIX-like OSes and some other OSes are designed for multiple address spaces.)
As a side note, synonyms of read-only memory do not introduce a correctness issue (merely potentially wasting bandwidth from false misses and cache capacity from duplicate caching of the same physical memory). This makes VIVT less unattractive for instruction caches. (x86 is somewhat unusual in requiring instruction caches to be cache coherent, though providing coherent instruction caches can simplify some software.)
In addition, synonym issues in VIPT caches can be handled by using the initial virtual index as a form of way prediction (probing alternate sets on a miss--this was done by the AMD Athlon's 64 KiB, 2-way cache with 4 KiB pages--or using a physically indexed tag-inclusive L2 cache with the excess virtual address bits used for indexing L1 included, invalidating the block at the previously cached L1 virtual index) or by requiring any synonyms to index the same set of cache blocks (most simply by page coloring where the corresponding physical address bits are artificially the same as the virtual address bits used for indexing).
这篇关于缓存寻址方法混乱的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
