Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

The Design and Evaluation of In-Cache Address Translation

David A. Wood

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-90-565
February 1990

http://www.eecs.berkeley.edu/Pubs/TechRpts/1990/CSD-90-565.pdf

In this dissertation we study in-cache address translation, a new approach to implementing virtual memory. In-cache translation combines the functions of the traditional translation lookaside buffer with a virtual address cache. Rather than dedicating hardware resources specifically to hold pagetable entries, in-cache translation lets the pagetable share the regular cache with instructions and data. By combining the two mechanisms we simplify the memory system design, and potentially reduce the cycle time. In addition, by eliminating the translation lookaside buffer, we simplify the translation consistency problem in multiprocessors: the operating system can use the regular data cache coherency protocol to maintain a consistent view of the pagetable.

Trace-driven simulation shows that in-cache translation has better performance than many translation lookaside buffer designs. As cache memories grow larger, the advantage of in-cache translation will also increase. Other simulation results indicate that in-cache translation will also increase. Other simulation results indicate that in-cache translation performs well over a wide range of cache configurations.

To further understand in-cache translation, we implemented it as a central feature of SPUR, a multiprocessor workstation developed at the University of California at Berkeley. A five-processor prototype convincingly demonstrates the feasibility of this new mechanism. In addition, a set of event counters, imbedded in the custom VLSI cache controller chip, provides a means to measure cache performance. We use these counters to evaluate the performance of in-cache translation for 23 workloads. These measurements validate some of the key simulation results.

The measurements and simulations also show that the performance of in-cache translation is sensitive to pagetable placement. We propose a variation of the algorithm, called inverted in-cache translation, which reduces this sensitivity. We also examine alternative ways to support reference and dirty bits in a virtual address cache. An analytic model and measurements from the prototype show that the SPUR mechanism has the best performance, but that emulating dirty bits with protection is not much worse and does not require additional hardware. Finally, we show that the miss bit approximation to reference bits, where the bit is only checked on cache misses, performs better than true reference bits, which require a partial cache flush.

Advisor: Randy H. Katz


BibTeX citation:

@phdthesis{Wood:CSD-90-565,
    Author = {Wood, David A.},
    Title = {The Design and Evaluation of In-Cache Address Translation},
    School = {EECS Department, University of California, Berkeley},
    Year = {1990},
    Month = {Feb},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1990/5356.html},
    Number = {UCB/CSD-90-565},
    Abstract = {In this dissertation we study in-cache address translation, a new approach to implementing virtual memory. In-cache translation combines the functions of the traditional translation lookaside buffer with a virtual address cache. Rather than dedicating hardware resources specifically to hold pagetable entries, in-cache translation lets the pagetable share the regular cache with instructions and data. By combining the two mechanisms we simplify the memory system design, and potentially reduce the cycle time. In addition, by eliminating the translation lookaside buffer, we simplify the translation consistency problem in multiprocessors: the operating system can use the regular data cache coherency protocol to maintain a consistent view of the pagetable. <p>Trace-driven simulation shows that in-cache translation has better performance than many translation lookaside buffer designs. As cache memories grow larger, the advantage of in-cache translation will also increase. Other simulation results indicate that in-cache translation will also increase. Other simulation results indicate that in-cache translation performs well over a wide range of cache configurations. <p>To further understand in-cache translation, we implemented it as a central feature of SPUR, a multiprocessor workstation developed at the University of California at Berkeley. A five-processor prototype convincingly demonstrates the feasibility of this new mechanism. In addition, a set of event counters, imbedded in the custom VLSI cache controller chip, provides a means to measure cache performance. We use these counters to evaluate the performance of in-cache translation for 23 workloads. These measurements validate some of the key simulation results. <p>The measurements and simulations also show that the performance of in-cache translation is sensitive to pagetable placement. We propose a variation of the algorithm, called inverted in-cache translation, which reduces this sensitivity. We also examine alternative ways to support reference and dirty bits in a virtual address cache. An analytic model and measurements from the prototype show that the SPUR mechanism has the best performance, but that emulating dirty bits with protection is not much worse and does not require additional hardware. Finally, we show that the miss bit approximation to reference bits, where the bit is only checked on cache misses, performs better than true reference bits, which require a partial cache flush.}
}

EndNote citation:

%0 Thesis
%A Wood, David A.
%T The Design and Evaluation of In-Cache Address Translation
%I EECS Department, University of California, Berkeley
%D 1990
%@ UCB/CSD-90-565
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/1990/5356.html
%F Wood:CSD-90-565