Improving memory hierarchy performance for irregular applications

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Improving memory hierarchy performance for irregular applications

Full text

Pdf (1.30 MB)

Source

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

Rhodes, Greece

Pages: 425 - 433

Year of Publication: 1999

ISBN:1-58113-164-X

Authors

John Mellor-Crummey	Department of Computer Science, MS 132, Rice University, 6100 Main, Houston, TX
David Whalley	Computer Science Department, Florida State University, Tallahassee, FL
Ken Kennedy	Department of Computer Science, MS 132, Rice University, 6100 Main, Houston, TX

Sponsor

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 33, Citation Count: 21

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/305138.305228 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.

	AKL79	Walid Abdul-Karim Abu-Sufah, Improving the performance of virtual memory computers., 1979
	AlR98	Memory Hierarchy Management for Iterative Graph Structures, Proceedings of the 12th. International Parallel Processing Symposium on International Parallel Processing Symposium, p.298, March 30-April 03, 1998
	AlK84	John R. Allen , Ken Kennedy, Automatic loop interchange, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.233-246, June 17-22, 1984, Montreal, Canada
	BBO83	B.R. Brooks, R.E. Bruccoleri, B.D. Olafson, D.J. States, S. Swaminathan, and M. Karplus, "CHARMM: A Program for Macromolecular Energy, Minimization and Dynamics Calculations," Journal of Computational Chemistry 187(4)(t 983).
	CCK90	David Callahan , Steve Carr , Ken Kennedy, Improving register allocation for subscripted variables, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.53-65, June 1990, White Plains, New York, United States
	DiK99	Chen Ding , Ken Kennedy, Improving cache performance in dynamic applications through data and computation reorganization at run time, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.229-241, May 01-04, 1999, Atlanta, Georgia, United States
	FST91	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
	GJG88	Dennis Gannon , William Jalby , Kyle Gallivan, Strategies for cache and local memory management by global program transformation, Journal of Parallel and Distributed Computing, v.5 n.5, p.587-616, October 1988 [doi>10.1016/0743-7315(88)90014-7]
	Knu73	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	KAP97	Induprakas Kodukula , Nawaaz Ahmed , Keshav Pingali, Data-centric multi-level blocking, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.346-357, June 16-18, 1997, Las Vegas, Nevada, United States
	LRW91	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
	McC69	A. C. McKellar , E. G. Coffman, Jr., Organizing matrices and matrix operations for paged memory systems, Communications of the ACM, v.12 n.3, p.153-165, March 1969 [doi>10.1145/362875.362879]
	MCT96	Kathryn S. McKinley , Steve Carr , Chau-Wen Tseng, Improving data locality with loop transformations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.4, p.424-453, July 1996 [doi>10.1145/233561.233564]
	MLG92	Todd C. Mowry , Monica S. Lam , Anoop Gupta, Design and evaluation of a compiler algorithm for prefetching, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.62-73, October 12-15, 1992, Boston, Massachusetts, United States
	NGH96	J.J. Navarro, E. Garcia, and J. R. Herrero, Proceedings of the lOth ACM International Conference on Supercomputing (ICS), (1996).
	OGR95	Chao-Wei Ou , Manoj Gunwani , Sanjay Ranka, Architecture-independent locality-improving transformations of computational graphs embedded in k-dimensions, Proceedings of the 9th international conference on Supercomputing, p.289-298, July 03-07, 1995, Barcelona, Spain [doi>10.1145/224538.224573]
	PaB96	Manish Parashar , James C. Browne, On Partitioning Dynamic Adaptive Grid Hierarchies, Proceedings of the 29th Hawaii International Conference on System Sciences (HICSS'96) Volume 1: Software Technology and Architecture, p.604, January 03-06, 1996
	Por89	Allan Kennedy Porterfield , K. W. Kennedy, Software methods for improvement of cache performance on supercomputer applications, 1989
	Sag94	H. Sagan, Space-Filling Curves, Springer-Verlag, New York, NY (I 994).
	Sam89	Hanan Samet, Applications of spatial data structures: Computer graphics, image processing, and GIS, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	SHT95	Jaswinder Pal Singh , Chris Holt , Takashi Totsuka , Anoop Gupta , John Hennessy, Load balancing and data locality in adaptive hierarchical N-body methods: Barnes-Hut, fast multipole, and radiosity, Journal of Parallel and Distributed Computing, v.27 n.2, p.118-141, June 1995 [doi>10.1006/jpdc.1995.1077]
	TCL98	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
	TuE95	Dean M. Tullsen , Susan J. Eggers, Effective cache prefetching on bus-based multiprocessors, ACM Transactions on Computer Systems (TOCS), v.13 n.1, p.57-88, Feb. 1995 [doi>10.1145/200912.201006]
	WaS93	M. S. Warren , J. K. Salmon, A parallel hashed Oct-Tree N-body algorithm, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.12-21, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169640]
	WoL91	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

CITED BY 21

	John Mellor-Crummey , David Whalley , Ken Kennedy, Improving Memory Hierarchy Performance for Irregular Applications Using Data and Computation Reorderings, International Journal of Parallel Programming, v.29 n.3, p.217-247, June 2001
	Y. Charlie Hu , Alan Cox , Willy Zwaenepoel, Improving fine-grained irregular shared-memory benchmarks by data reordering, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.33-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
	Mahmut Kendemir , J. Ramanujam, Data Relation Vectors: A New Abstraction for Data Optimizations, IEEE Transactions on Computers, v.50 n.8, p.798-810, August 2001
	Mohamed F. Mokbel , Walid G. Aref, Irregularity in multi-dimensional space-filling curves with applications in multimedia databases, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA
	Dimitrios S. Nikolopoulos , Constantine D. Polychronopoulos , Eduard Ayguadé, Scaling irregular parallel codes with minimal programming effort, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.16-16, November 10-16, 2001, Denver, Colorado
	Vijay S. Pai , Sarita Adve, Code transformations to improve memory parallelism, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.147-155, November 16-18, 1999, Haifa, Israel
	Mohamed F. Mokbel , Walid G. Aref , Ibrahim Kamel, Analysis of Multi-Dimensional Space-Filling Curves, Geoinformatica, v.7 n.3, p.179-209, September 2003
	Michelle Mills Strout , Larry Carter , Jeanne Ferrante, Compile-time composition of run-time data and iteration reorderings, ACM SIGPLAN Notices, v.38 n.5, May 2003
	Michelle Mills Strout , Paul D. Hovland, Metrics and models for reordering transformations, Proceedings of the 2004 workshop on Memory system performance, June 08-08, 2004, Washington, D.C.
	Jack Dongarra , Ian Foster , Geoffrey Fox , William Gropp , Ken Kennedy , Linda Torczon , Andy White, References, Sourcebook of parallel computing, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
	Qing Yi , Vikram Adve , Ken Kennedy, Transforming loops to recursion for multi-level memory hierarchies, ACM SIGPLAN Notices, v.35 n.5, p.169-181, May 2000
	Eladio Gutiérrez , Sergio Romero , Luis F. Romero , Oscar Plata , Emilio L. Zapata, Parallel techniques in irregular codes: cloth simulation as case of study, Journal of Parallel and Distributed Computing, v.65 n.4, p.424-436, April 2005
	Victor De La Luz , Mahmut Kandemir, Array Regrouping and Its Use in Compiling Data-Intensive Embedded Applications, IEEE Transactions on Computers, v.53 n.1, p.1-19, January 2004
	Ismail Kadayif , Mahmut Kandemir, Quasidynamic Layout Optimizations for Improving Data Locality, IEEE Transactions on Parallel and Distributed Systems, v.15 n.11, p.996-1011, November 2004
	Antonio Lain , Dhruva R. Chakrabarti , Prithviraj Banerjee, Compiler and Run-Time Support for Exploiting Regularity within Irregular Applications, IEEE Transactions on Parallel and Distributed Systems, v.11 n.2, p.119-135, February 2000
	Guohua Jin , John Mellor-Crummey, SFCGen: A framework for efficient generation of multi-dimensional space-filling curves by recursion, ACM Transactions on Mathematical Software (TOMS), v.31 n.1, p.120-148, March 2005
	M. Kandemir , J. Ramanujam , U. Sezer, Improving the energy behavior of block buffering using compiler optimizations, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.11 n.1, p.228-250, January 2006
	Jacques M. Bahi , Abdallah Makhoul , Ahmed Mostefaoui, Localization and coverage for high density sensor networks, Computer Communications, v.31 n.4, p.770-781, March, 2008
	Eladio Gutiérrez , Oscar Plata , Emilio L. Zapata, An analytical model of locality-based parallel irregular reductions, Parallel Computing, v.34 n.3, p.133-157, March, 2008
	David E. Singh , Maria J. Martin , Francisco F. Rivera, Runtime characterisation of irregular accesses applied to parallelisation of irregular reductions, International Journal of Computational Science and Engineering, v.1 n.1, p.1-14, February 2005