Cache miss equations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Cache miss equations: an analytical representation of cache misses

Full text

Pdf (1.98 MB)

Source

International Conference on Supercomputing archive
Proceedings of the 11th international conference on Supercomputing table of contents

Vienna, Austria

Pages: 317 - 324

Year of Publication: 1997

ISBN:0-89791-902-5

Authors

Somnath Ghosh	Department of Electrical Engineering, Princeton University
Margaret Martonosi	Department of Electrical Engineering, Princeton University
Sharad Malik	Department of Electrical Engineering, Princeton University

Sponsor

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 68, Citation Count: 51

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/263580.263657 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	David F. Bacon , Jyh-Herng Chow , Dz-ching R. Ju , Kalyan Muthukumar , Vivek Sarkar, A compiler framework for restructuring data declarations to enhance cache and TLB effectiveness, Proceedings of the 1994 conference of the Centre for Advanced Studies on Collaborative research, p.3, October 31-November 03, 1994, Toronto, Ontario, Canada
	2	Utpal K. Banerjee, Loop Transformations for Restructuring Compilers: The Foundations, Kluwer Academic Publishers, Norwell, MA, 1993
	3	S. Carr , K. Kennedy, Compiler blockability of numerical algorithms, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.114-124, November 16-20, 1992, Minneapolis, Minnesota, United States
	4	Steve Carr , Kathryn S. McKinley , Chau-Wen Tseng, Compiler optimizations for improving data locality, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.252-262, October 05-07, 1994, San Jose, California, United States
	5	Philippe Clauss, Counting solutions to linear and nonlinear constraints through Ehrhart polynomials: applications to analyze and transform scientific programs, Proceedings of the 10th international conference on Supercomputing, p.278-285, May 25-28, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237578.237617]
	6	Stephanie Coleman , Kathryn S. McKinley, Tile size selection using cache organization and data layout, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.279-290, June 18-21, 1995, La Jolla, California, United States
	7	Jeanne Ferrante , Vivek Sarkar , W. Thrash, On Estimating and Enhancing Cache Effectiveness, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.328-343, August 07-09, 1991
	8	M. D. Hill , A. J. Smith, Evaluating Associativity in CPU Caches, IEEE Transactions on Computers, v.38 n.12, p.1612-1630, December 1989 [doi>10.1109/12.40842]
	9	Monica D. Lam , Edward E. Rothberg , Michael E. Wolf, The cache performance and optimizations of blocked algorithms, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.63-74, April 08-11, 1991, Santa Clara, California, United States
	10	Alvin R. Lebeck , David A. Wood, Cache Profiling and the SPEC Benchmarks: A Case Study, Computer, v.27 n.10, p.15-26, October 1994 [doi>10.1109/2.318580]
	11	Margaret Martonosi , Anoop Gupta , Thomas Anderson, MemSpy: analyzing memory system bottlenecks in programs, Proceedings of the 1992 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.1-12, June 01-05, 1992, Newport, Rhode Island, United States
	12	Kathryn S. McKinley , Olivier Temam, A quantitative analysis of loop nest locality, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.94-104, October 01-04, 1996, Cambridge, Massachusetts, United States
	13	William Pugh, A practical algorithm for exact array dependence analysis, Communications of the ACM, v.35 n.8, p.102-114, Aug. 1992 [doi>10.1145/135226.135233]
	14	O. Temam , C. Fricker , W. Jalby, Cache interference phenomena, Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.261-271, May 16-20, 1994, Nashville, Tennessee, United States
	15	Robert P. Wilson , Robert S. French , Christopher S. Wilson , Saman P. Amarasinghe , Jennifer M. Anderson , Steve W. K. Tjiang , Shih-Wei Liao , Chau-Wen Tseng , Mary W. Hall , Monica S. Lam , John L. Hennessy, SUIF: an infrastructure for research on parallelizing and optimizing compilers, ACM SIGPLAN Notices, v.29 n.12, p.31-37, Dec. 1994 [doi>10.1145/193209.193217]
	16	Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.30-44, June 24-28, 1991, Toronto, Ontario, Canada
	17	M. Wolfe, More iteration space tiling, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.655-664, November 12-17, 1989, Reno, Nevada, United States [doi>10.1145/76263.76337]

CITED BY 51

	Gabriel Rivera , Chau-Wen Tseng, Locality optimizations for multi-level caches, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.2-es, November 14-19, 1999, Portland, Oregon, United States
	Siddhartha Chatterjee , Erin Parker , Philip J. Hanlon , Alvin R. Lebeck, Exact analysis of the cache behavior of nested loops, ACM SIGPLAN Notices, v.36 n.5, p.286-297, May 2001
	Nawaaz Ahmed , Nikolay Mateev , Keshav Pingali, Tiling imperfectly-nested loop nests, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.31-es, November 04-10, 2000, Dallas, Texas, United States
	Abdel-Hameed A. Badawy , Aneesh Aggarwal , Donald Yeung , Chau-Wen Tseng, Evaluating the impact of memory system performance on software prefetching and locality optimizations, Proceedings of the 15th international conference on Supercomputing, p.486-500, June 2001, Sorrento, Italy
	Gabriel Rivera , Chau-Wen Tseng, Tiling optimizations for 3D scientific computations, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.32-es, November 04-10, 2000, Dallas, Texas, United States
	Basilio B. Fraguela , Ramón Doallo , Emilio L. Zapata, Modeling set associative caches behavior for irregular computations, ACM SIGMETRICS Performance Evaluation Review, v.26 n.1, p.192-201, June 1998
	Gabriel Rivera , Chau-Wen Tseng, Eliminating conflict misses for high performance architectures, Proceedings of the 12th international conference on Supercomputing, p.353-360, July 1998, Melbourne, Australia
	Gabriel Rivera , Chau-Wen Tseng, Data transformations for eliminating conflict misses, ACM SIGPLAN Notices, v.33 n.5, p.38-49, May 1998
	Siddhartha Chatterjee , Vibhor V. Jain , Alvin R. Lebeck , Shyam Mundhra , Mithuna Thottethodi, Nonlinear array layouts for hierarchical memory systems, Proceedings of the 13th international conference on Supercomputing, p.444-453, June 20-25, 1999, Rhodes, Greece
	Jacqueline Chame , Sungdo Moon, A tile selection algorithm for data locality and cache interference, Proceedings of the 13th international conference on Supercomputing, p.492-499, June 20-25, 1999, Rhodes, Greece
	A. Hergenhan , W. Rosenstiel, Static timing analysis of embedded software on advanced processor architectures, Proceedings of the conference on Design, automation and test in Europe, p.552-559, March 27-30, 2000, Paris, France
	Mithuna Thottethodi , Siddhartha Chatterjee , Alvin R. Lebeck, Tuning Strassen's matrix multiplication for memory efficiency, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-14, November 07-13, 1998, San Jose, CA
	Sharad Malik , Margaret Martonosi , Yau-Tsun Steven Li, Static timing analysis of embedded software, Proceedings of the 34th annual conference on Design automation, p.147-152, June 09-13, 1997, Anaheim, California, United States
	Jesús Sánchez , Antonio González, Modulo scheduling for a fully-distributed clustered VLIW architecture, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.124-133, December 2000, Monterey, California, United States
	Somnath Ghosh , Margaret Martonosi , Sharad Malik, Precise miss analysis for program transformations with caches of arbitrary associativity, ACM SIGOPS Operating Systems Review, v.32 n.5, p.228-239, Dec. 1998
	Jesús Sánchez , Antonio González, Analyzing Data Locality in Numeric Applications, IEEE Micro, v.20 n.4, p.58-66, July 2000
	Richard A. Hankins , Jignesh M. Patel, Effect of node size on the performance of cache-conscious B⁺-trees, ACM SIGMETRICS Performance Evaluation Review, v.31 n.1, June 2003
	Somnath Ghosh , Margaret Martonosi , Sharad Malik, Automated cache optimizations using CME driven diagnosis, Proceedings of the 14th international conference on Supercomputing, p.316-326, May 08-11, 2000, Santa Fe, New Mexico, United States
	Chung-hsing Hsu , Ulrich Kremer, A Quantitative Analysis of Tile Size Selection Algorithms, The Journal of Supercomputing, v.27 n.3, p.279-294, March 2004
	Nawaaz Ahmed , Nikolay Mateev , Keshav Pingali, Synthesizing Transformations for Locality Enhancement of Imperfectly-Nested Loop Nests, International Journal of Parallel Programming, v.29 n.5, p.493-544, October 2001
	Ilya Gluhovsky , Brian O'Krafka, Comprehensive multiprocessor cache miss rate generation using multivariate models, ACM Transactions on Computer Systems (TOCS), v.23 n.2, p.111-145, May 2005
	John S. Harper , Darren J. Kerbyson , Graham R. Nudd, Analytical Modeling of Set-Associative Cache Behavior, IEEE Transactions on Computers, v.48 n.10, p.1009-1024, October 1999
	Nigel Topham , Antonio González, Randomized Cache Placement for Eliminating Conflicts, IEEE Transactions on Computers, v.48 n.2, p.185-192, February 1999
	J. Hu , M. Kandemir , N. Vijaykrishnan , M. J. Irwin, Analyzing data reuse for cache reconfiguration, ACM Transactions on Embedded Computing Systems (TECS), v.4 n.4, p.851-876, November 2005
	Thomas Rauber , Gudula Rünger, A Transformation Approach to Derive Efficient Parallel Implementations, IEEE Transactions on Software Engineering, v.26 n.4, p.315-339, April 2000
	J. S. Hu , M. Kandemir , N. Vijaykrishnan , M. J. Irwin , H. Saputra , W. Zhang, Compiler-directed cache polymorphism, ACM SIGPLAN Notices, v.37 n.7, July 2002
	Marcel P. van Lohuizen, Memory-efficient and thread-safe quasi-destructive graph unification, Proceedings of the 38th Annual Meeting on Association for Computational Linguistics, p.352-359, October 03-06, 2000, Hong Kong
	Richard Murphy , Arun Rodrigues , Peter Kogge , Keith Underwood, The implications of working set analysis on supercomputing memory hierarchy design, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts
	Wei Zhang , Mahmut Kandemir , Mustafa Karakoy , Guangyu Chen, Reducing data cache leakage energy using a compiler-based approach, ACM Transactions on Embedded Computing Systems (TECS), v.4 n.3, p.652-678, August 2005
	Frédéric Gruau , Yves Lhuillier , Philippe Reitz , Olivier Temam, BLOB computing, Proceedings of the 1st conference on Computing frontiers, April 14-16, 2004, Ischia, Italy
	Vibhu Saujanya Sharma , Kishor S. Trivedi, Architecture based analysis of performance, reliability and security of software systems, Proceedings of the 5th international workshop on Software and performance, p.217-227, July 12-14, 2005, Palma, Illes Balears, Spain
	Steve Carr , Soner Önder, A case for a working-set-based memory hierarchy, Proceedings of the 2nd conference on Computing frontiers, May 04-06, 2005, Ischia, Italy
	Michael A. Frumkin , Rob F. Van der Wijngaart, Tight bounds on cache use for stencil operations on rectangular grids, Journal of the ACM (JACM), v.49 n.3, p.434-453, May 2002
	Zhong Wang , Xiaobo Sharon Hu , Edwin H.-M. Sha, Register aware scheduling for distributed cache clustered architecture, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan
	D. Andrade , B. B. Fraguela , R. Doallo, Analytical modeling of codes with arbitrary data-dependent conditional structures, Journal of Systems Architecture: the EUROMICRO Journal, v.52 n.7, p.394-410, July 2006
	Vlad-Mihai Panait , Amit Sasturkar , Weng-Fai Wong, Static Identification of Delinquent Loads, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.303, March 20-24, 2004, Palo Alto, California
	Michael Dupré , Nathalie Drach , Olivier Temam, VHC: Quickly Building an Optimizer for Complex Embedded Architectures, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.53, March 20-24, 2004, Palo Alto, California
	A. Ya. Kalinov , A. L. Lastovetsky , I. N. Ledovskikh , M. A. Posypkin, Compilation of Vector Statements of C[] Language for Architectures with Multilevel Memory Hierarchy, Programming and Computing Software, v.27 n.3, p.111-122, May-June 2001
	Fei Guo , Yan Solihin, An analytical model for cache replacement policy performance, ACM SIGMETRICS Performance Evaluation Review, v.34 n.1, June 2006
	Ilya Gluhovsky , David Vengerov , Brian O'Krafka, Comprehensive multivariate extrapolation modeling of multiprocessor cache miss rates, ACM Transactions on Computer Systems (TOCS), v.25 n.1, p.2-es, February 2007
	Vibhu Saujanya Sharma , Kishor S. Trivedi, Quantifying software performance, reliability and security: An architecture-based approach, Journal of Systems and Software, v.80 n.4, p.493-509, April, 2007
	Andhi Janapsatya , Aleksandar Ignjatovic , Sri Parameswaran , Joerg Henkel, Instruction trace compression for rapid instruction cache simulation, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
	Johann Blieberger , Thomas Fahringer , Bernhard Scholz, Symbolic Cache Analysis for Real-Time Systems, Real-Time Systems, v.18 n.2-3, p.181-215, May 2000
	N. E. Crosbie , M. Kandemir , I. Kolcu , J. Ramanujam , A. Choudhary, Strategies for Improving Data Locality in Embedded Applications, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.631, January 07-11, 2002
	I. Kadayif , M. Kandemir , I. Kolcu, Exploiting Processor Workload Heterogeneity for Reducing Energy Consumption in Chip Multiprocessors, Proceedings of the conference on Design, automation and test in Europe, p.21158, February 16-20, 2004
	Arun Kejariwal , Alexandru Nicolau , Utpal Banerjee , Alexander V. Veidenbaum , Constantine D. Polychronopoulos, Cache-aware iteration space partitioning, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA
	A. M. Molnos , M. J. M. Heijligers , S. D. Cotofana , J. T. J. van Eijndhoven, Compositional Memory Systems for Data Intensive Applications, Proceedings of the conference on Design, automation and test in Europe, p.10728, February 16-20, 2004
	Rathijit Sen , Y. N. Srikant, WCET estimation for executables in the presence of data caches, Proceedings of the 7th ACM & IEEE international conference on Embedded software, September 30-October 03, 2007, Salzburg, Austria
	Carsten Scholtes, A method to derive the cache performance of irregular applications on machines with direct mapped caches, International Journal of Computational Science and Engineering, v.1 n.2-4, p.157-174, May 2005
	Richard C. Murphy , Peter M. Kogge, On the Memory Access Patterns of Supercomputer Applications: Benchmark Selection and Its Implications, IEEE Transactions on Computers, v.56 n.7, p.937-945, July 2007
	Arun Kejariwal , Alexandru Nicolau , Utpal Banerjee , Alexander V. Veidenbaum , Constantine D. Polychronopoulos, Cache-aware partitioning of multi-dimensional iteration spaces, Proceedings of SYSTOR 2009: The Israeli Experimental Systems Conference, May 04-April 06, 2009, Haifa, Israel