Why is that the page size equals the size of one cache way?

My book states "A direct-mapped cache cannot be bigger than a page".

  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$
    – Raphael
    Aug 20 '17 at 18:23
  • $\begingroup$ It would help to give a direct quotation from the book, and provide a citation for the book (title & authors). I suspect that the statement here has led to some confusion about what the book is saying -- total size of the cache, vs size of a single cache entry. $\endgroup$
    – D.W.
    Aug 22 '17 at 1:22

Assume you have different processes sharing memory. That means you can have different pointers pointing to the same physical memory. If you have two different pointers, pointing to the same physical memory, but pointing to different entries in the cache, then you will be in trouble.

In practice, memory mapping is done page by page. So both pointers will have the same offset into a page, but the page numbers can be different. One pointer can have an even page number, one an odd page number. If your cache is bigger than a page, for example two pages, then two pointers with an even and an odd page numbers would point to different cache entries, exactly what we want to avoid.

Of course an operating system could just not do any memory mapping that creates two pointers to the same memory location pointing an odd number of pages apart, and then the cache could be two pages in size.


First, your book is wrong.

It is possible to have a direct-mapped cache larger than a page. For example, a while ago, when caches were made of fast SRAM chips, it was quite common to have simple direct mapped 64kB to 1MB L2 caches (for example Pentium 2 & 3). In modern chips, the caches are not simply direct mapped anymore, but their ways are often larger than a page.

The reason is about virtual and physical addresses, and aliasing.

Cache addresses and tags can be either virtual or physical, taken "before" or "after" the MMU. There is an issue with virtual cache indexes larger than a MMU page, because different processes could map the same physical address range into different virtual addresses, that don't coincide in the cache. There are several mitigation techniques, such as cache colouring (constraining the way the OS does memory allocation, grouping MMU pages to match the cache size), using write-thru caches and automatic invalidation of aliased lines after context switches...

The benefit of virtual addresses is that they are available earlier, as they don't need to cross the MMU. Except with very complex deeply pipelined out-of-order CPUs, this reduced latency can make a large difference.

The simplest solution is to constraint cache ways to the MMU page size, in that case, the low addresses needed for addressing the cache memory is identical for physical and virtual addresses. Then, after the cache has been read, the tags can more easily use physical addresses (reading cache memory and tags occurs at the same time as MMU address resolution)


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.