Analytical cache models with applications to cache partitioning

ABSTRACT

An accurate, tractable, analytic cache model for time-shared systems is presented, which estimates the overall cache miss-rate of a multiprocessing system with any cache size and time quanta. The input to the model consists of the isolated miss-rate curves for each process, the time quanta for each of the executing processes, and the total cache size. The output is the overall miss-rate. Trace-driven simulations demonstrate that the estimated miss-rate is very accurate. Since the model provides a fast and accurate way to estimate the effect of context switching, it is useful for both understanding the effect of context switching on caches and optimizing cache performance for time-shared systems. A cache partitioning mechanism is also presented and is shown to improve the cache miss-rate up to 25% over the normal LRU replacement policy.

REFERENCES

• 1: A. Agarwal , J. Hennessy , M. Horowitz, An analytical cache model, ACM Transactions on Computer Systems (TOCS), v.7 n.2, p.184-215, May 1989 [doi>10.1145/63404.63407]
• 2: Cumpaq. Cumpaq A1phaStatiun family.
• 3: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 4: Susan J. Eggers , Joel S. Emer , Henry M. Levy , Jack L. Lo , Rebecca L. Stamm , Dean M. Tullsen, Simultaneous Multithreading: A Platform for Next-Generation Processors, IEEE Micro, v.17 n.5, p.12-19, September 1997 [doi>10.1109/40.621209]
• 5: C. Freeburit. The hewlett packard PA-RISC 8500 processor. TechiticM report, Itewlett Packard Laboratories, Oct. 1998.
• 6: Antonio González , Mateo Valero , Nigel Topham , Joan M. Parcerisa, Eliminating cache conflict misses through XOR-based placement functions, Proceedings of the 11th international conference on Supercomputing, p.76-83, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263599]
• 7: J. L. Heititiitg. SPEC CPU2000: Measuriitg CPU performaitce iit the Itew Itfilleititium. IEEE Computer, July 2000.
• 8: Norman P. Jouppi, Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers, Proceedings of the 17th annual international symposium on Computer Architecture, p.364-373, May 28-31, 1990, Seattle, Washington, United States
• 9: D. B. Kirk. Process depeitdeitt static cache partitioitiitg for reM-time systems. IIt Real-Time Systems Symposium, 1988.
• 10: Hantak Kwak , Ben Lee , Ali R. Hurson , Suk-Han Yoon , Woo-Jong Hahn, Effects of Multithreading on Cache Performance, IEEE Transactions on Computers, v.48 n.2, p.176-184, February 1999 [doi>10.1109/12.752659]
• 11: Jack L. Lo , Joel S. Emer , Henry M. Levy , Rebecca L. Stamm , Dean M. Tullsen , S. J. Eggers, Converting thread-level parallelism to instruction-level parallelism via simultaneous multithreading, ACM Transactions on Computer Systems (TOCS), v.15 n.3, p.322-354, Aug. 1997 [doi>10.1145/263326.263382]
• 12: P. Magitussoit aitd B. Weriter. Efficieitt memory simulatioit iit SimICS. lit 28th Annual Simulation Symposium, 1995.
• 13: MIPS Techitologies, IItc. MIPS RIO000 Microprocessor" User's Manual, 1996.
• 14: Jeffrey C. Mogul , Anita Borg, The effect of context switches on cache performance, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.75-84, April 08-11, 1991, Santa Clara, California, United States
• 15: J. Muoz. Data-Intensive Systems Benchmark Suite Analysis and Specification. http://www.aec.com/projectweb/dis, Juite 1999.
• 16: Mendel Rosenblum , Stephen A. Herrod , Emmett Witchel , Anoop Gupta, Complete Computer System Simulation: The SimOS Approach, IEEE Parallel & Distributed Technology: Systems & Technology, v.3 n.4, p.34-43, December 1995 [doi>10.1109/88.473612]
• 17: M. S. Squiillante , E. D. Lazowska, Using Processor-Cache Affinity Information in Shared-Memory Multiprocessor Scheduling, IEEE Transactions on Parallel and Distributed Systems, v.4 n.2, p.131-143, February 1993 [doi>10.1109/71.207589]
• 18: Harold S. Stone , John Turek , Joel L. Wolf, Optimal Partitioning of Cache Memory, IEEE Transactions on Computers, v.41 n.9, p.1054-1068, September 1992 [doi>10.1109/12.165388]
• 19: G. E. Suh aitd L. Rudolph. Set-associative cache models for time-shared systems. Techitical Report CSG Memo 433, Massachusetts IItstitute of Techitology, 2001.
• 20: Dominique Thiebaut , Harold S. Stone, Footprints in the cache, ACM Transactions on Computer Systems (TOCS), v.5 n.4, p.305-329, Nov. 1987 [doi>10.1145/29868.32979]
• 21: Dominique Thiébaut , Harold S. Stone , Joel L. Wolf, Improving Disk Cache Hit-Ratios Through Cache Partitioning, IEEE Transactions on Computers, v.41 n.6, p.665-676, June 1992 [doi>10.1109/12.144619]
• 22: Nigel Topham , Antonio González, Randomized Cache Placement for Eliminating Conflicts, IEEE Transactions on Computers, v.48 n.2, p.185-192, February 1999 [doi>10.1109/12.752660]
• 23: Josep Torrellas , Andrew Tucker , Anoop Gupta, Benefits of cache-affinity scheduling in shared-memory multiprocessors: a summary, Proceedings of the 1993 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.272-274, May 10-14, 1993, Santa Clara, California, United States
• 24: Dean M. Tullsen , Susan J. Eggers , Henry M. Levy, Simultaneous multithreading: maximizing on-chip parallelism, Proceedings of the 22nd annual international symposium on Computer architecture, p.392-403, June 22-24, 1995, S. Margherita Ligure, Italy
• 25: Richard A. Uhlig , Trevor N. Mudge, Trace-driven memory simulation: a survey, ACM Computing Surveys (CSUR), v.29 n.2, p.128-170, June 1997 [doi>10.1145/254180.254184]
• 26: Marco Zagha , Brond Larson , Steve Turner , Marty Itzkowitz, Performance analysis using the MIPS R10000 performance counters, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.16-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States [doi>10.1145/369028.369059]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

General Terms:
Design, Reliability