More iteration space tiling

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

More iteration space tiling

Full text

Pdf (1.01 MB)

Source

Conference on High Performance Networking and Computing archive
Proceedings of the 1989 ACM/IEEE conference on Supercomputing table of contents

Reno, Nevada, United States

Pages: 655 - 664

Year of Publication: 1989

ISBN:0-89791-341-8

Author

M. Wolfe

Oregon Graduate Center

Sponsors

Argonne Natl Lab : Argonne National Lab
IEEE-CS : Computer Society
NASA : National Aeronatics and Space Administration
SIGARCH: ACM Special Interest Group on Computer Architecture
Los Alamos National Labs : Los Alamos National Labs

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 16, Downloads (12 Months): 108, Citation Count: 84

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	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/76263.76337 What is a DOI?

ABSTRACT

Subdividing the iteration space of a loop into blocks or tiles with a fixed maximum size has several advantages. Tiles become a natural candidate as the unit of work for parallel task scheduling. Synchronization between processors can be done between tiles, reducing synchronization frequency (at some loss of potential parallelism). The shape and size of a tile can be optimized to take advantage of memory locality for memory hierarchy utilization. Vectorization and register locality naturally fits into the optimization within a tile, while parallelization and cache locality fits into optimization between tiles.

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.

	AbuS78	Walid AbduI-Karim Abu-Sufah, Improving the Performance of Virtual Memory Computers, Ph.D. Thesis, Dept. of Comp. Sci. Rpt. No. 78-945, Univ. of Illinois, Urbanu, IL, Nov., 1978; available as document 79-15307 from University Microfilms, Ann Arbor, MI.
	AbKL81	W. A. Abu-Sufah, D. j. Kuck and D. H. Lzwrie, "On the Performance Enhancement of Paging Systems Through Program Analysis ~nd Transformations," IEEE Trans. on Computer~, Vol. C-30, No. 5, pp. 341-356, May 1981.
	AlKe84	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
	AlKe87	Randy Allen , Ken Kennedy, Automatic translation of FORTRAN programs to vector form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.491-542, Oct. 1987 [doi>10.1145/29873.29875]
	Bane88	Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
	IrTr88	F. Irigoin , R. Triolet, Supernode partitioning, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.319-329, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73588]
	Lamp74	Leslie Lamport, The parallel execution of DO loops, Communications of the ACM, v.17 n.2, p.83-93, Feb. 1974 [doi>10.1145/360827.360844]
	Love77	David B. Loveman, Program Improvement by Source-to-Source Transformation, Journal of the ACM (JACM), v.24 n.1, p.121-145, Jan. 1977 [doi>10.1145/321992.322000]
	Mura71	Yoichi Muraoka, Parallelism exposure and exploitation in programs, 1971
	Wolf86	Michael Wolfe, Loop skewing: the wavefront method revisited, International Journal of Parallel Programming, v.15 n.4, p.279-293, Oct. 1986 [doi>10.1007/BF01407876]
	WoBa87	Michael Wolfe , Utpal Banerjee, Data dependence and its application to parallel processing, International Journal of Parallel Programming, v.16 n.2, p.137-178, April 1987 [doi>10.1007/BF01379099]
	Wolf87	Michael Wolfe, Iteration Space Tiling for Memory Hierarchies, Proceedings of the Third SIAM Conference on Parallel Processing for Scientific Computing, p.357-361, December 01-04, 1987
	Wolf89	Michael Joseph Wolfe, Optimizing Supercompilers for Supercomputers, MIT Press, Cambridge, MA, 1990

CITED BY 84

	K. Kennedy , K. S. McKinley , C. W. Tseng, Interactive Parallel Programming using the ParaScope Editor, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.329-341, July 1991
	Tzung-Shi Chen , Chih-Yung Chang, Skewed Data Partition and Alignment Techniques for Compiling Programs on Distributed Memory Multicomputers, The Journal of Supercomputing, v.21 n.2, p.191-211, February 2002
	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
	Ken Kennedy , Kathryn S. McKinley, Optimizing for parallelism and data locality, Proceedings of the 6th international conference on Supercomputing, p.323-334, July 19-24, 1992, Washington, D. C., United States
	David Callahan , Steve Carr , Ken Kennedy, Improving register allocation for subscripted variables, ACM SIGPLAN Notices, v.25 n.6, p.53-65, Jun. 1990
	O. Temam , E. D. Granston , W. Jalby, To copy or not to copy: a compile-time technique for assessing when data copying should be used to eliminate cache conflicts, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.410-419, December 1993, Portland, Oregon, United States
	Manish Gupta , Prithviraj Banerjee, A methodology for high-level synthesis of communication on multicomputers, Proceedings of the 6th international conference on Supercomputing, p.357-367, July 19-24, 1992, Washington, D. C., United States
	Hiroshi Ohta , Yasuhiko Saito , Masahiro Kainaga , Hiroyuki Ono, Optimal tile size adjustment in compiling general DOACROSS loop nests, Proceedings of the 9th international conference on Supercomputing, p.270-279, July 03-07, 1995, Barcelona, Spain
	M. E. Wolf , M. S. Lam, A Loop Transformation Theory and an Algorithm to Maximize Parallelism, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.452-471, October 1991
	Corinne Ancourt , François Irigoin, Scanning polyhedra with DO loops, ACM SIGPLAN Notices, v.26 n.7, p.39-50, July 1991
	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
	Suvas Vajracharya , Dirk Grunwald, Loop re-ordering and pre-fetching at run-time, Proceedings of the 1997 ACM/IEEE conference on Supercomputing (CDROM), p.1-13, November 15-21, 1997, San Jose, CA
	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
	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
	J. Ramanujam, Non-unimodular transformations of nested loops, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.214-223, November 16-20, 1992, Minneapolis, Minnesota, United States
	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
	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
	Greg Snider, Performance-constrained pipelining of software loops onto reconfigurable hardware, Proceedings of the 2002 ACM/SIGDA tenth international symposium on Field-programmable gate arrays, February 24-26, 2002, Monterey, California, USA
	Steven Lucco, A dynamic scheduling method for irregular parallel programs, ACM SIGPLAN Notices, v.27 n.7, p.200-211, July 1992
	D. Kulkarni , K. G. Kumar , A. Basu , A. Paulraj, Loop partitioning for distributed memory multiprocessors as unimodular transformations, Proceedings of the 5th international conference on Supercomputing, p.206-215, June 17-21, 1991, Cologne, West Germany
	Anthony LaMarca , Richard E. Ladner, The influence of caches on the performance of sorting, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.370-379, January 05-07, 1997, New Orleans, Louisiana, United States
	Mark Bromley , Steven Heller , Tim McNerney , Guy L. Steele, Jr., Fortran at ten gigaflops: the connection machine convolution compiler, ACM SIGPLAN Notices, v.26 n.6, p.145-156, June 1991
	Karin Högstedt , Larry Carter , Jeanne Ferrante, Selecting tile shape for minimal execution time, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.201-211, June 27-30, 1999, Saint Malo, France
	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
	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
	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
	Fabrice Rastello , Amit Rao , Santosh Pande, Optimal task scheduling at run time to exploit intra-tile parallelism, Parallel Computing, v.29 n.2, p.209-239, February 2003
	Somnath Ghosh , Margaret Martonosi , Sharad Malik, Cache miss equations: a compiler framework for analyzing and tuning memory behavior, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.4, p.703-746, July 1999
	Ken Kennedy , Kathryn S. McKinley , Chau-Wen Tseng, Analysis and transformation in the ParaScope editor, Proceedings of the 5th international conference on Supercomputing, p.433-447, June 17-21, 1991, Cologne, West Germany
	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
	Yeong-Sheng Chen , Sheng-De Wang , Chien-Min Wang, Compiler techniques for maximizing fine-grain and coarse-grain parallelism in loops with uniform dependences, Proceedings of the 8th international conference on Supercomputing, p.204-213, July 11-15, 1994, Manchester, England
	Peter Petrov , Alex Orailğlu, Towards effective embedded processors in codesigns: customizable partitioned caches, Proceedings of the ninth international symposium on Hardware/software codesign, p.79-84, April 2001, Copenhagen, Denmark
	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
	David F. Bacon , Susan L. Graham , Oliver J. Sharp, Compiler transformations for high-performance computing, ACM Computing Surveys (CSUR), v.26 n.4, p.345-420, Dec. 1994
	Lee-Chung Lu, A unified framework for systematic loop transformations, ACM SIGPLAN Notices, v.26 n.7, p.28-38, July 1991
	M. Jiménez , J. M. Llabería , A. Fernández , E. Morancho, A general algorithm for tiling the register level, Proceedings of the 12th international conference on Supercomputing, p.133-140, July 1998, Melbourne, Australia
	Stephanie Coleman , Kathryn S. McKinley, Tile size selection using cache organization and data layout, ACM SIGPLAN Notices, v.30 n.6, p.279-290, June 1995
	J. Ramanujam , P. Sadayappan, Tiling multidimensional iteration spaces for nonshared memory machines, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.111-120, November 18-22, 1991, Albuquerque, New Mexico, United States
	Keith D. Cooper , Timothy J. Harvey, Compiler-controlled memory, ACM SIGOPS Operating Systems Review, v.32 n.5, p.2-11, Dec. 1998
	Marta Jiménez , José M. Llabería , Agustín Fernández, Register tiling in nonrectangular iteration spaces, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.4, p.409-453, July 2002
	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
	Xian Chen , Graham M. Megson, A General Methodology of Partitioning and Mapping for Given Regular Arrays, IEEE Transactions on Parallel and Distributed Systems, v.6 n.10, p.1100-1107, October 1995
	Jingling Xue , Wentong Cai, Time-minimal tiling when rise is larger than zero, Parallel Computing, v.28 n.6, p.915-939, June 2002
	G. N. Srinivasa Prasanna , A. Agrawal , B. R. Musicus, Hierarchical Compilation of Macro Dataflow Graphs for Multiprocessors with Local Memory, IEEE Transactions on Parallel and Distributed Systems, v.5 n.7, p.720-736, July 1994
	Calin CaΒcaval , David A. Padua, Estimating cache misses and locality using stack distances, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA
	Nicholas Mitchell , Larry Carter , Jeanne Ferrante , Dean Tullsen, ILP versus TLP on SMT, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.37-es, November 14-19, 1999, Portland, Oregon, United States
	Mary Hall , Peter Kogge , Jeff Koller , Pedro Diniz , Jacqueline Chame , Jeff Draper , Jeff LaCoss , John Granacki , Jay Brockman , Apoorv Srivastava , William Athas , Vincent Freeh , Jaewook Shin , Joonseok Park, Mapping irregular applications to DIVA, a PIM-based data-intensive architecture, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.57-es, November 14-19, 1999, Portland, Oregon, United States
	S. G. Abraham , D. E. Hudak, Compile-Time Partitioning of Iterative Parallel Loops to Reduce Cache Coherency Traffic, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.318-328, July 1991
	T. S. Chen , J. P. Sheu, Communication-Free Data Allocation Techniques for Parallelizing Compilers on Multicomputers, IEEE Transactions on Parallel and Distributed Systems, v.5 n.9, p.924-938, September 1994
	W. Blume , R. Eigenmann, Performance Analysis of Parallelizing Compilers on the Perfect Benchmarks Programs, IEEE Transactions on Parallel and Distributed Systems, v.3 n.6, p.643-656, November 1992
	Karin Högstedt , Larry Carter , Jeanne Ferrante, Determining the idle time of a tiling, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.160-173, January 15-17, 1997, Paris, France
	Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, ACM SIGPLAN Notices, v.26 n.6, p.30-44, June 1991
	M. Kandemir , J. Ramanujam , A. Choudhary , P. Banerjee, A Layout-Conscious Iteration Space Transformation Technique, IEEE Transactions on Computers, v.50 n.12, p.1321-1336, December 2001
	Qing Yi , Ken Kennedy , Vikram Adve, Transforming Complex Loop Nests for Locality, The Journal of Supercomputing, v.27 n.3, p.219-264, March 2004
	Preeti Ranjan Panda , Hiroshi Nakamura , Nikil D. Dutt , Alexandru Nicolau, Augmenting Loop Tiling with Data Alignment for Improved Cache Performance, IEEE Transactions on Computers, v.48 n.2, p.142-149, February 1999
	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
	David Callahan , Steve Carr , Ken Kennedy, Improving register allocation for subscripted variables, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Chih-Yung Chang , Tzung-Shi Chen , Jang-Ping Sheu, Improving Memory Traffic by Assembly-Level Exploitation of Reuses for Vector Registers, The Journal of Supercomputing, v.17 n.2, p.187-204, Sept. 2000
	Guohua Jin , Zhiyuan Li , Fujie Chen, An Efficient Solution to the Cache Thrashing Problem Caused by True Data Sharing, IEEE Transactions on Computers, v.47 n.5, p.527-543, May 1998
	David C. Wong , Edward W. Davis , Jeffrey O. Young, A Software Approach to Avoiding Spatial Cache Collisions in Parallel Processor Systems, IEEE Transactions on Parallel and Distributed Systems, v.9 n.6, p.601-608, June 1998
	Edin Hodzic , Weijia Shang, On Supernode Transformation with Minimized Total Running Time, IEEE Transactions on Parallel and Distributed Systems, v.9 n.5, p.417-428, May 1998
	Sriram Sellappa , Siddhartha Chatterjee, Cache-Efficient Multigrid Algorithms, International Journal of High Performance Computing Applications, v.18 n.1, p.115-133, February 2004
	Edin Hodzic , Weijia Shang, On Time Optimal Supernode Shape, IEEE Transactions on Parallel and Distributed Systems, v.13 n.12, p.1220-1233, December 2002
	Yavor Angelov , Umakishore Ramachandran , Kenneth Mackenzie , James Matthew Rehg , Irfan Essa, Experiences with optimizing two stream-based applications for cluster execution, Journal of Parallel and Distributed Computing, v.65 n.6, p.678-691, June 2005
	Qing Yi , Ken Kennedy, Improving Memory Hierarchy Performance through Combined Loop Interchange and Multi-Level Fusion, International Journal of High Performance Computing Applications, v.18 n.2, p.237-253, May 2004
	Michelle Mills Strout , Larry Carter , Jeanne Ferrante , Barbara Kreaseck, Sparse Tiling for Stationary Iterative Methods, International Journal of High Performance Computing Applications, v.18 n.1, p.95-113, February 2004
	Monica S. Lam , Michael E. Wolf, A data locality optimizing algorithm, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Karin Högstedt , Larry Carter , Jeanne Ferrante, On the Parallel Execution Time of Tiled Loops, IEEE Transactions on Parallel and Distributed Systems, v.14 n.3, p.307-321, March 2003
	Mahmut Kandemir , Prithviraj Banerjee , Alok Choudhary , J. Ramanujam , Eduard Ayguadé, Static and Dynamic Locality Optimizations Using Integer Linear Programming, IEEE Transactions on Parallel and Distributed Systems, v.12 n.9, p.922-941, September 2001
	Yoon-Ju Lee , Pedro C. Diniz , Mary W. Hall , Robert Lucas, Empirical optimization for a sparse linear solver: a case study, International Journal of Parallel Programming, v.33 n.2, p.165-181, June 2005
	K. Patrick Lorton , David S. Wise, Analyzing block locality in Morton-order and Morton-hybrid matrices, Proceedings of the 2006 workshop on MEmory performance: DEaling with Applications, systems and architectures, p.5-12, September 16-20, 2006, Seattle, Washington
	Timothy J. Knight , Ji Young Park , Manman Ren , Mike Houston , Mattan Erez , Kayvon Fatahalian , Alex Aiken , William J. Dally , Pat Hanrahan, Compilation for explicitly managed memory hierarchies, Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, March 14-17, 2007, San Jose, California, USA
	Sriram Krishnamoorthy , Muthu Baskaran , Uday Bondhugula , J. Ramanujam , Atanas Rountev , P Sadayappan, Effective automatic parallelization of stencil computations, ACM SIGPLAN Notices, v.42 n.6, June 2007
	Abhishek Das , William J. Dally , Peter Mattson, Compiling for stream processing, Proceedings of the 15th international conference on Parallel architectures and compilation techniques, September 16-20, 2006, Seattle, Washington, USA
	Kazuaki Ishizaki , Hideaki Komatsu , Toshio Nakatani, A Loop Transformation Algorithm for Communication Overlapping, International Journal of Parallel Programming, v.28 n.2, p.135-154, April 2000
	J. Ramanujam , Satish Krishnamurthy , Jinpyo Hong , Mahmut Kandemir, Address Code and Arithmetic Optimizations for Embedded Systems, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.619, January 07-11, 2002
	C. Brandolese , W. Fornaciari , F. Salice , D. Sciuto, Analysis and Modeling of Energy Reducing Source Code Transformations, Proceedings of the conference on Design, automation and test in Europe, p.30306, February 16-20, 2004
	Nicholas Mitchell , Karin Högstedt , Larry Carter , Jeanne Ferrante, Quantifying the Multi-Level Nature of Tiling Interactions, International Journal of Parallel Programming, v.26 n.6, p.641-670, December 1998
	Jingling Xue , Chua-Huang Huang, Reuse-Driven Tiling for Improving Data Locality, International Journal of Parallel Programming, v.26 n.6, p.671-696, December 1998
	Yunquan Zhang , Ying Chen , Yuan Tang, Block size selection of parallel LU and QR on PVP-based and RISC-based supercomputers, Proceedings of the 2007 Asian technology information program's (ATIP's) 3rd workshop on High performance computing in China: solution approaches to impediments for high performance computing, November 11-11, 2007, Reno, Nevada
	Jia Guo , Ganesh Bikshandi , Basilio B. Fraguela , Maria J. Garzaran , David Padua, Programming with tiles, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA
	K. Patrick Lorton , David S. Wise, Analyzing block locality in Morton-order and Morton-hybrid matrices, ACM SIGARCH Computer Architecture News, v.35 n.4, September 2007
	Arun Kejariwal , Calin Casçaval, Parallelization spectroscopy: analysis of thread-level parallelism in hpc programs, Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, February 14-18, 2009, Raleigh, NC, USA
	Jingling Xue , Minyi Guo , Daming Wei, Improving the parallelism of iterative methods by aggressive loop fusion, The Journal of Supercomputing, v.43 n.2, p.147-164, February 2008