7
$\begingroup$

Basically, and as a simple method, we can access cache with Physical Address which is from the TLB.

But, as another method, we can access cache with Virtual Address. But, in this case, if the cache is not fully flushed between context switch(other process's datas can be exist in cache), there is an aliasing problem. Same memory can be directed from the different virtual address.

But in my text book, including these problem, many can be solved by virtually indexed physically tagged. I think this still can make an aliasing problem.

Am I wrong?

$\endgroup$
  • $\begingroup$ Shubham has given right answer. For more details/insights, you may see my survey paper on TLB which reviews 85+ papers. Figure 3a of the paper discusses address subdivision and 3b shows the special case where aliasing does not occur for certain cache size since cache index is computed entirely from page offset. $\endgroup$ – user984260 Feb 4 '18 at 10:53
6
$\begingroup$

The Aliasing problem can be solved if we select the cache size small enough. If cache size is such that the bits for indexing the cache all come from the page offset bits , multiple virtual address will point to the same index position in the cache and aliasing will be solved.

For example consider 32-bit virtual address 0xFFFF FFFF , this system uses a page size of 64kB suppose which make the page offset bits 16 bits. Now if we select The index bits to be 10 (number of sets 1024) and block size as 64 Bytes. Then the index bits and the block offset bits both are accommodated in the page offset bits of the virtual address. Consider another address 0xEEEE FFFF this address looks like it will cause aliasing but despite of having different virtual address the lower order bits force it to map to the same location in the cache and there is no aliasing. Only drawback of this approach is cache size is limited by the page size.

$\endgroup$
  • $\begingroup$ In layman words. Whole virtual memory notion relies around different virtual and physical page numbers. So in VI-PT, physical number is THE physical Tag. So no aliasing issue(as physical address are unique). The virtual address is used to narrow down to an entry in cache using indexing from the offset part(which is anyways same for physica/virtual address). So this limit indexing to use the non-page-number bits. Hence smaller cache size. $\endgroup$ – Anup Buchke Jul 23 at 2:02
1
$\begingroup$

There are two aspects related to VIPT caches and aliasing. And the issues can be a bit different between instruction set architectures.

1)

There are several ways to map the virtual addresses of each process to the external physical addresses.

Some use "process identifiers" or "address space identifiers" (iirc ARM, SPARC, MIPS) where each running process is given a different value used to select different page tables.

Some use "logical/physical" addresses where the addresses for each process (=logical) are translated o a larger address space (for example from 32 to 52 bits) (=virtual) shared between all processes, and TLBs transform these extended virtual addresses to physical addresses. PowerPCs are like that.

To avoid needing to flush all the TLBs and all the cache during each context switch, the cache tags (and TLBs) can store the corresponding address space identifiers or extended virtual addresses : Each adress of each process is different, and no aliasing is possible (well, sometimes aliasing is expected, for example where running privilegied kernel code mapped in the same virtual address range of all processes)

2)

A more subtle issue is when several processes share the same physical memory area. This range of physical memory may be mapped in different virtual addresses by each process. Modification by one process may not be visible by the other. Particularly with write-back caches where writes are not immediately forwarded to RAM. One solution, with the OS assistance, is to guarantee some alignment between processes depending on cache size, even if the virtual addresses are different between the different processes, they will be aliased in the same cache line, and will automatically eject one another.

Virtually Indexed caches are used principally on simple (old) CPUs, because of these aliasing issues. Nowadays, a very common technique is to limit each way of the L1 cache to the MMU page size (4kB or 8kB usually) so that the cache index is shared between physical and virtual addresses, cache fetch occurs at the same times as MMU address resolution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.