Nonlinear array layouts for hierarchical memory systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Nonlinear array layouts for hierarchical memory systems

Full text

Pdf (2.20 MB)

Source

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

Rhodes, Greece

Pages: 444 - 453

Year of Publication: 1999

ISBN:1-58113-164-X

Authors

Siddhartha Chatterjee	Department of Computer Science, The University of North Carolina, Chapel Hill, NC
Vibhor V. Jain	Department of Computer Science, The University of North Carolina, Chapel Hill, NC
Alvin R. Lebeck	Department of Computer Science, Duke University, Durham, NC
Shyam Mundhra	Department of Computer Science, The University of North Carolina, Chapel Hill, NC
Mithuna Thottethodi	Department of Computer Science, Duke University, Durham, NC

Sponsor

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 27, Citation Count: 31

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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.305231 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	E. Anderson , Z. Bai , C. Bischof , L. S. Blackford , J. Demmel , Jack J. Dongarra , J. Du Croz , S. Hammarling , A. Greenbaum , A. McKenney , D. Sorensen, LAPACK Users' guide (third ed.), Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
	2	Jennifer M. Anderson , Saman P. Amarasinghe , Monica S. Lam, Data and computation transformations for multiprocessors, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.166-178, July 19-21, 1995, Santa Barbara, California, United States
	3	Remzi H. Arpaci , David E. Culler , Arvind Krishnamurthy , Steve G. Steinberg , Katherine Yelick, Empirical evaluation of the CRAY-T3D: a compiler perspective, Proceedings of the 22nd annual international symposium on Computer architecture, p.320-331, June 22-24, 1995, S. Margherita Ligure, Italy
	4	Utpal K. Banerjee, Loop Transformations for Restructuring Compilers: The Foundations, Kluwer Academic Publishers, Norwell, MA, 1993
	5	Ioana Banicescu , Susan Flynn Hummel, Balancing processor loads and exploiting data locality in N-body simulations, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.43-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224306]
	6	T. Bially. Space-filling curves: Their generation and their application to bandwidth reduction. IEEE Transactions on Information Theory, II'-15(6):658-664, Nov. 1969.
	7	Jeff Bilmes , Krste Asanovic , Chee-Whye Chin , Jim Demmel, Optimizing matrix multiply using PHiPAC: a portable, high-performance, ANSI C coding methodology, Proceedings of the 11th international conference on Supercomputing, p.340-347, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263662]
	8	Brad Calder , Chandra Krintz , Simmi John , Todd Austin, Cache-conscious data placement, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.139-149, October 02-07, 1998, San Jose, California, United States
	9	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
	10	Larry Carter , Jeanne Ferrante , Susan Flynn Hummel, Hierarchical tiling for improved superscalar performance, Proceedings of the 9th International Symposium on Parallel Processing, p.239-245, April 25-28, 1995
	11	Siddhartha Chatterjee , John R. Gilbert , Robert Schreiber , Shang-Hua Teng, Optimal evaluation of array expressions on massively parallel machines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.1, p.123-156, Jan. 1995 [doi>10.1145/200994.201004]
	12	Siddhartha Chatterjee , Alvin R. Lebeck , Praveen K. Patnala , Mithuna Thottethodi, Recursive array layouts and fast parallel matrix multiplication, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.222-231, June 27-30, 1999, Saint Malo, France [doi>10.1145/305619.305645]
	13	T. M. Chilimbi, J. R. Lares, and M. D. Hill. Improving pointer-based codes through cache-conscious data placement. Technical Report CS-TR-98-1365, University of Wisconsin--Madison, Mar. 1998.
	14	Michał Cierniak , Wei Li, Unifying data and control transformations for distributed shared-memory machines, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.205-217, June 18-21, 1995, La Jolla, California, United States
	15	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
	16	J. J. Dongarra , Jeremy Du Croz , Sven Hammarling , I. S. Duff, A set of level 3 basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.16 n.1, p.1-17, March 1990 [doi>10.1145/77626.79170]
	17	K. Esseghir. lmprovingdata locality foreaches. Master's thesis, Department of Computer Science, Rice University, Houston, TX, Sept. 1993.
	18	Jeremy D. Frens , David S. Wise, Auto-blocking matrix-multiplication or tracking BLAS3 performance from source code, Proceedings of the sixth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.206-216, June 18-21, 1997, Las Vegas, Nevada, United States
	19	Christine Fricker , Olivier Temam , William Jalby, Influence of cross-interferences on blocked loops: a case study with matrix-vector multiply, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.4, p.561-575, July 1995 [doi>10.1145/210184.210185]
	20	Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
	21	Somnath Ghosh , Margaret Martonosi , Sharad Malik, Cache miss equations: an analytical representation of cache misses, Proceedings of the 11th international conference on Supercomputing, p.317-324, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263657]
	22	Somnath Ghosh , Margaret Martonosi , Sharad Malik, Precise miss analysis for program transformations with caches of arbitrary associativity, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.228-239, October 02-07, 1998, San Jose, California, United States
	23	G. Gibson, t. S. Vitter, and i. Wilkes. Report of the working group on storage UO for large-scale computing. ACM Comput. Sum., Dec. 1996.
	24	M. F. Goodchild and A. W. Grandfield. Optimizing raster storage: an examination of four alternatives. In Proceedings of Auto-Carte 6, volume 1, pages 400-407~Ottawa, Oct. 1983.
	25	Manish Gupta, Automatic data partitioning on distributed memory multicomputers, University of Illinois at Urbana-Champaign, Champaign, IL, 1992
	26	F. G. Gustavson, Recursion leads to automatic variable blocking for dense linear-algebra algorithms, IBM Journal of Research and Development, v.41 n.6, p.737-756, Nov. 1997
	27	D. Hilbert. 'Uber stetige Abbildung einer Linie auf ein Fl/iehenstiick. Mathematische AnnaIen, 38:459-460,1891.
	28	Y. Charlie Hu , S. Lennart Johnsson , Shang-Hua Teng, High performance Fortran for highly irregular problems, Proceedings of the sixth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.13-24, June 18-21, 1997, Las Vegas, Nevada, United States
	29	S. F. Hummel, I. Banieeseu, C.-T. Wang, and J. Wein. Load balancing and data locality via fractiling: An experimental study. In Language, Compilers andRun- ?qme Systems.for Scalable Computers. Kluwer Academic Publishers, 1995.
	30	H. V. Jagadish, Linear clustering of objects with multiple attributes, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.332-342, May 23-26, 1990, Atlantic City, New Jersey, United States
	31	Ken Kennedy , Ulrich Kremer, Automatic data layout for distributed-memory machines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.4, p.869-916, July 1998 [doi>10.1145/291891.291901]
	32	Kathleen Knobe , Joan D. Lukas , Guy L. Stelle, Jr., Data optimization: allocation of arrays to reduce communication on SIMD machines, Journal of Parallel and Distributed Computing, v.8 n.2, p.102-118, February 1990 [doi>10.1016/0743-7315(90)90086-5]
	33	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
	34	Charles H. Koelbel , David B. Loveman , Robert S. Schreiber , Guy L. Steele, Jr. , Mary E. Zosel, The high performance Fortran handbook, MIT Press, Cambridge, MA, 1994
	35	Richard E. Ladner , James D. Fix , Anthony LaMarca, Cache performance analysis of traversals and random accesses, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.613-622, January 17-19, 1999, Baltimore, Maryland, United States
	36	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
	37	Anthony LaMarca , Richard Ladner, The influence of caches on the performance of heaps, Journal of Experimental Algorithmics (JEA), 1, p.4-es, 1996 [doi>10.1145/235141.235145]
	38	Anthony George Lamarca , Richard E. Ladner, Caches and algorithms, 1996
	39	R. Laurini. Graphical data bases built on Pea.no space-filling curves. In C. E. Vandoni, editor, Proceedings of the EUROGRAPHICS '85 Conference, pages 327-338, Amsterdam, 1985. North-Holland.
	40	Alvin R. Lebeck , David A. Wood, Active memory: a new abstraction for memory system simulation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.7 n.1, p.42-77, Jan. 1997 [doi>10.1145/244804.244806]
	41	Mary E. Mace, Memory storage patterns in parallel processing, Kluwer Academic Publishers, Norwell, MA, 1987
	42	Bongki Moon , H. V. Jagadish , Christos Faloutsos , Joel H. Saltz, Analysis of the clustering properties of Hilbert space-filling curve, University of Maryland at College Park, College Park, MD, 1996
	43	Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
	44	G. Peano. Sur une eourbe qui remplit toute une aire plaine. Mathematisehe Annalen, 36:157-160, 1890.
	45	John R. Pilkington , Scott B. Baden, Dynamic Partitioning of Non-Uniform Structured Workloads with Spacefilling Curves, IEEE Transactions on Parallel and Distributed Systems, v.7 n.3, p.288-300, March 1996 [doi>10.1109/71.491582]
	46	Allan Kennedy Porterfield , K. W. Kennedy, Software methods for improvement of cache performance on supercomputer applications, 1989
	47	Gabriel Rivera , Chau-Wen Tseng, Data transformations for eliminating conflict misses, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.38-49, June 17-19, 1998, Montreal, Quebec, Canada
	48	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 [doi>10.1145/277830.277917]
	49	H. Sagan. Space-FillingCurves. Springer-Verlag, 1994. ISBN 0-387-94265-3.
	50	S. Sen, S. Chatterjee, and A. R. Lebeek. Towards a theory of cache-efficient algorithms. In preparation, Apr. 1999.
	51	J. P. Singh , T. Joe , J. L. Hennessy , A. Gupta, An empirical comparison of the Kendall Square Research KSR-1 and Stanford DASH multiprocessors, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.214-225, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169699]
	52	Amitabh Srivastava , Alan Eustace, ATOM: a system for building customized program analysis tools, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.196-205, June 20-24, 1994, Orlando, Florida, United States
	53	L. Stals and U. Pride. Techniques for improving the data locality of iterative methods. Technical Report MRR97-038, Institut ffir Mathematik, Universitfit Augsburg, Augsburg, Germany, Oct. 1997.
	54	Eric J. Stollnitz , Tony D. Derose , David H. Salesin, Wavelets for computer graphics: theory and applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
	55	V. Stmssen. Gaussian elimination is not optimal. Numer. Math., 13:354-356, 1969.
	56	Mark Swanson , Leigh Stoller , John Carter, Increasing TLB reach using superpages backed by shadow memory, Proceedings of the 25th annual international symposium on Computer architecture, p.204-213, June 27-July 02, 1998, Barcelona, Spain
	57	Madhusudhan Talluri , Mark D. Hill, Surpassing the TLB performance of superpages with less operating system support, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.171-182, October 05-07, 1994, San Jose, California, United States
	58	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]
	59	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
	60	Uzi Vishkin, Can parallel algorithms enhance serial implementation?, Communications of the ACM, v.39 n.9, p.88-91, Sept. 1996 [doi>10.1145/234215.234475]
	61	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]
	62	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
	63	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 32

	Siddhartha Chatterjee , Alvin R. Lebeck , Praveen K. Patnala , Mithuna Thottethodi, Recursive Array Layouts and Fast Matrix Multiplication, IEEE Transactions on Parallel and Distributed Systems, v.13 n.11, p.1105-1123, November 2002
	Sambuddhi Hettiaratchi , Peter Y. K. Cheung, A Novel Implementation of Tile-Based Address Mapping, Proceedings of the conference on Design, automation and test in Europe, p.10306, February 16-20, 2004
	Sambuddhi Hettiaratchi , Peter Y. K. Cheung, Mesh Partitioning Approach to Energy Efficient Data Layout, Proceedings of the conference on Design, Automation and Test in Europe, p.11076, March 03-07, 2003
	José E. Moreira , Samuel P. Midkiff , Manish Gupta , Pedro V. Artigas , Peng Wu , George Almasi, The NINJA project, Communications of the ACM, v.44 n.10, p.102-109, Oct. 2001
	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
	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
	Evangelia Athanasaki , Nectarios Koziris, Fast indexing for blocked array layouts to reduce cache misses, International Journal of High Performance Computing and Networking, v.3 n.5/6, p.417-433, March 2005
	Neungsoo Park , Bo Hong , Viktor K. Prasanna, Tiling, Block Data Layout, and Memory Hierarchy Performance, IEEE Transactions on Parallel and Distributed Systems, v.14 n.7, p.640-654, July 2003
	Sriram Sellappa , Siddhartha Chatterjee, Cache-Efficient Multigrid Algorithms, International Journal of High Performance Computing Applications, v.18 n.1, p.115-133, February 2004
	Xavier Vera , Björn Lisper , Jingling Xue, Data cache locking for higher program predictability, ACM SIGMETRICS Performance Evaluation Review, v.31 n.1, June 2003
	Vincent Loechner , Benoît Meister , Philippe Clauss, Precise Data Locality Optimization of Nested Loops, The Journal of Supercomputing, v.21 n.1, p.37-76, January 2002
	Steven T. Gabriel , David S. Wise, The Opie compiler from row-major source to Morton-ordered matrices, Proceedings of the 3rd workshop on Memory performance issues: in conjunction with the 31st international symposium on computer architecture, p.136-144, June 20-20, 2004, Munich, Germany
	José E. Moreira , Samuel P. Midkiff , Manish Gupta , Peng Wu , George Almasi , Pedro Artigas, NINJA: Java for high performance numerical computing, Scientific Programming, v.10 n.1, p.19-33, January 2002
	Chun-Yuan Lin , Jen-Shiuh Liu , Yeh-Ching Chung, Efficient Representation Scheme for Multidimensional Array Operations, IEEE Transactions on Computers, v.51 n.3, p.327-345, March 2002
	Alexander Heinecke , Michael Bader, Towards many-core implementation of LU decomposition using Peano Curves, Proceedings of the combined workshops on UnConventional high performance computing workshop plus memory access workshop, May 18-20, 2009, Ischia, Italy
	Xavier Vera , Jaume Abella , Josep Llosa , Antonio González, An accurate cost model for guiding data locality transformations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.5, p.946-987, September 2005
	Chengliang Zhang , Chen Ding , Mitsunori Ogihara , Yutao Zhong , Youfeng Wu, A hierarchical model of data locality, ACM SIGPLAN Notices, v.41 n.1, p.16-29, January 2006
	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
	David S. Wise , Jeremy D. Frens , Yuhong Gu , Gregory A. Alexander, Language support for Morton-order matrices, ACM SIGPLAN Notices, v.36 n.7, p.24-33, July 2001
	Gerth Stølting Brodal , Rolf Fagerberg , Riko Jacob, Cache oblivious search trees via binary trees of small height, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.39-48, January 06-08, 2002, San Francisco, California
	Bjarne S. Andersen , John A. Gunnels , Fred G. Gustavson , John K. Reid , Jerzy Waśniewski, A fully portable high performance minimal storage hybrid format Cholesky algorithm, ACM Transactions on Mathematical Software (TOMS), v.31 n.2, p.201-227, June 2005
	Sandeep Sen , Siddhartha Chatterjee, Towards a theory of cache-efficient algorithms, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.829-838, January 09-11, 2000, San Francisco, California, United States
	Chun-Yuan Lin , Yeh-Ching Chung , Jen-Shiuh Liu, Efficient Data Parallel Algorithms for Multidimensional Array Operations Based on the EKMR Scheme for Distributed Memory Multicomputers, IEEE Transactions on Parallel and Distributed Systems, v.14 n.7, p.625-639, July 2003
	G. Almasi , F. G. Gustavson , J. E. Moreira, Design and evaluation of a linear algebra package for Java, Proceedings of the ACM 2000 conference on Java Grande, p.150-159, June 03-04, 2000, San Francisco, California, United States
	Sandeep Sen , Siddhartha Chatterjee , Neeraj Dumir, Towards a theory of cache-efficient algorithms, Journal of the ACM (JACM), v.49 n.6, p.828-858, November 2002
	Xavier Vera , Nerina Bermudo , Josep Llosa , Antonio González, A fast and accurate framework to analyze and optimize cache memory behavior, ACM Transactions on Programming Languages and Systems (TOPLAS), v.26 n.2, p.263-300, March 2004
	Kristof Beyls , Erik H. D'Hollander, Generating cache hints for improved program efficiency, Journal of Systems Architecture: the EUROMICRO Journal, v.51 n.4, p.223-250, April 2005
	Mahmut Kandemir , Alok Choudhary , J. Ramanujam , Prith Banerjee, Reducing False Sharing and Improving Spatial Locality in a Unified Compilation Framework, IEEE Transactions on Parallel and Distributed Systems, v.14 n.4, p.337-354, April 2003
	Zhiyuan Li , Yonghong Song, Automatic tiling of iterative stencil loops, ACM Transactions on Programming Languages and Systems (TOPLAS), v.26 n.6, p.975-1028, November 2004
	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
	Jingling Xue , Xavier Vera, Efficient and Accurate Analytical Modeling of Whole-Program Data Cache Behavior, IEEE Transactions on Computers, v.53 n.5, p.547-566, May 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