Maximizing parallelism and minimizing synchronization with affine transforms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Maximizing parallelism and minimizing synchronization with affine transforms

Full text

Pdf (1.19 MB)

Source

Annual Symposium on Principles of Programming Languages archive
Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages table of contents

Paris, France

Pages: 201 - 214

Year of Publication: 1997

ISBN:0-89791-853-3

Authors

Amy W. Lim	Computer Systems Laboratory, Stanford University, Stanford, CA
Monica S. Lam	Computer Systems Laboratory, Stanford University, Stanford, CA

Sponsors

L'Ecole des Mines de Paris : L'Ecole des Mines de Paris
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
Ctr Natl de la Recherche Sci :
SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 51, Citation Count: 26

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/263699.263719 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	r. Allen , D. Callahan , K. Kennedy, Automatic decomposition of scientific programs for parallel execution, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.63-76, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41631]
	2	Corinne Ancourt , François Irigoin, Scanning polyhedra with DO loops, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.39-50, April 21-24, 1991, Williamsburg, Virginia, United States
	3	Jennifer M. Anderson , Monica S. Lam, Global optimizations for parallelism and locality on scalable parallel machines, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.112-125, June 21-25, 1993, Albuquerque, New Mexico, United States
	4	Eduard Ayguadé , Jordi Torres, Partitioning the statement per iteration space using non-singular matrices, Proceedings of the 7th international conference on Supercomputing, p.407-415, July 19-23, 1993, Tokyo, Japan [doi>10.1145/165939.166021]
	5	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 [doi>10.1145/197405.197406]
	6	U. Banerjee. Unimodular transformations of double loops. In Proceedings of the Third Workshop on Programming Languages and Compilers for Parallel Computing, pages 192-219, August 1990.
	7	Utpal K. Banerjee, Loop Transformations for Restructuring Compilers: The Foundations, Kluwer Academic Publishers, Norwell, MA, 1993
	8	David Bau , Induprakas Kodukula , Vladimir Kotlyar , Keshav Pingali , Paul Stodghill, Solving Alignment Using Elementary Linear Algebra, Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing, p.46-60, August 08-10, 1994
	9	Paul Feautrier, Some efficient solutions to the affine scheduling problem: I. One-dimensional time, International Journal of Parallel Programming, v.21 n.5, p.313-348, Oct. 1992 [doi>10.1007/BF01407835]
	10	Paul Feautrier, Some efficient solutions to the affine scheduling problem: I. One-dimensional time, International Journal of Parallel Programming, v.21 n.5, p.313-348, Oct. 1992 [doi>10.1007/BF01407835]
	11	P. Feautrier. Towards automatic distribution. Technical Report 92.95, Institut Blaise Pascal/Laboratoire MASI, December 1992.
	12	C.-H. Huang , P. Sadayappan, Communication-free hyperplane partitioning of nested loops, Journal of Parallel and Distributed Computing, v.19 n.2, p.90-102, Oct. 1993 [doi>10.1006/jpdc.1993.1094]
	13	Wayne Kelly , William Pugh, Determining schedules based on performance estimation, University of Maryland at College Park, College Park, MD, 1993
	14	Wayne Kelly , William Pugh, A framework for unifying reordering transformations, University of Maryland at College Park, College Park, MD, 1993
	15	Wayne Kelly , William Plugh, Minimizing communication while preserving parallelism, Proceedings of the 10th international conference on Supercomputing, p.52-60, May 25-28, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237578.237585]
	16	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 [doi>10.1145/143369.143427]
	17	Ken Kennedy , Kathryn S. McKinley, Maximizing Loop Parallelism and Improving Data Locality via Loop Fusion and Distribution, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.301-320, August 12-14, 1993
	18	Amy Lim , Monica S. Lam, Communication-Free Parallelization via Affine Transformations, Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing, p.92-106, August 08-10, 1994
	19	Vivek Sarkar , Radhika Thekkath, A general framework for iteration-reordering loop transformations, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.175-187, June 15-19, 1992, San Francisco, California, United States
	20	Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
	21	Michael Edward Wolf, Improving locality and parallelism in nested loops, Stanford University, Stanford, CA, 1992
	22	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 [doi>10.1109/71.97902]
	23	Michael Joseph Wolfe, Optimizing Supercompilers for Supercomputers, MIT Press, Cambridge, MA, 1990

CITED BY 26

	Vincent Loechner , Catherine Mongenet, Communication Optimization for Affine Recurrence Equations Using Broadcast and Locality, International Journal of Parallel Programming, v.28 n.1, p.47-102, February 2000
	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
	Amy W. Lim , Gerald I. Cheong , Monica S. Lam, An affine partitioning algorithm to maximize parallelism and minimize communication, Proceedings of the 13th international conference on Supercomputing, p.228-237, June 20-25, 1999, Rhodes, Greece
	Amy W. Lim , Shih-Wei Liao , Monica S. Lam, Blocking and array contraction across arbitrarily nested loops using affine partitioning, ACM SIGPLAN Notices, v.36 n.7, p.103-112, July 2001
	Minyi Guo , Yi Pan , Zhen Liu, Symbolic Communication Set Generation for Irregular Parallel Applications, The Journal of Supercomputing, v.25 n.3, p.199-214, July 2003
	William Thies , Frédéric Vivien , Jeffrey Sheldon , Saman Amarasinghe, A unified framework for schedule and storage optimization, ACM SIGPLAN Notices, v.36 n.5, p.232-242, May 2001
	Patrick Carribault , Albert Cohen, Applications of storage mapping optimization to register promotion, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France
	Albert Cohen , Marc Sigler , Sylvain Girbal , Olivier Temam , David Parello , Nicolas Vasilache, Facilitating the search for compositions of program transformations, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts
	Monica S. Lam , Michael E. Wolf, A data locality optimizing algorithm, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Wlodzimierz Bielecki , Robert Drazkowski, Finding free schedules for parameterized loops with affine dependences represented with a single dependence relation, Proceedings of the 5th WSEAS International Conference on Applied Informatics and Communications, p.369-376, September 15-17, 2005, Malta
	W. Bielecki , K. Siedlecki, Extracting synchronization-free threads in perfectly nested loops using the omega project software, Proceedings of the 4th WSEAS International Conference on Software Engineering, Parallel & Distributed Systems, p.1-7, February 13-15, 2005, Salzburg, Austria
	Liping Xue , Ozcan Ozturk , Mahmut Kandemir, A memory-conscious code parallelization scheme, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California
	Sylvain Girbal , Nicolas Vasilache , Cédric Bastoul , Albert Cohen , David Parello , Marc Sigler , Olivier Temam, Semi-automatic composition of loop transformations for deep parallelism and memory hierarchies, International Journal of Parallel Programming, v.34 n.3, p.261-317, June 2006
	Mattan Erez , Jung Ho Ahn , Jayanth Gummaraju , Mendel Rosenblum , William J. Dally, Executing irregular scientific applications on stream architectures, Proceedings of the 21st annual international conference on Supercomputing, June 17-21, 2007, Seattle, Washington
	Muthu Manikandan Baskaran , Uday Bondhugula , Sriram Krishnamoorthy , J. Ramanujam , Atanas Rountev , P. Sadayappan, A compiler framework for optimization of affine loop nests for gpgpus, Proceedings of the 22nd annual international conference on Supercomputing, June 07-12, 2008, Island of Kos, Greece
	Sean Rul , Hans Vandierendonck , Koen De Bosschere, Function level parallelism driven by data dependencies, ACM SIGARCH Computer Architecture News, v.35 n.1, March 2007
	Jayanth Gummaraju , Mendel Rosenblum, Stream Programming on General-Purpose Processors, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.343-354, November 12-16, 2005, Barcelona, Spain
	Chun Xue , Zili Shao , Edwin H.-M. Sha, Maximize Parallelism Minimize Overhead for Nested Loops via Loop Striping, Journal of VLSI Signal Processing Systems, v.47 n.2, p.153-167, May 2007
	Shih-wei Liao , Zhaohui Du , Gansha Wu , Guei-Yuan Lueh, Data and Computation Transformations for Brook Streaming Applications on Multiprocessors, Proceedings of the International Symposium on Code Generation and Optimization, p.196-207, March 26-29, 2006
	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
	A. E. Doroshenko , D. V. Ragozin, Using Graph Models in Retargetable Optimizing Compilers for Microprocessors with VLIW Architectures, Cybernetics and Systems Analysis, v.39 n.2, p.192-211, March-April 2003
	Louis-Noel Pouchet , Cedric Bastoul , Albert Cohen , Nicolas Vasilache, Iterative Optimization in the Polyhedral Model: Part I, One-Dimensional Time, Proceedings of the International Symposium on Code Generation and Optimization, p.144-156, March 11-14, 2007
	Louis-Noël Pouchet , Cédric Bastoul , Albert Cohen , John Cavazos, Iterative optimization in the polyhedral model: part ii, multidimensional time, ACM SIGPLAN Notices, v.43 n.6, June 2008
	Fawzy A. Torkey , Afaf A. Salah , Nahed M. El Desouky , Sahar A. Gomaa, Transformations techniques for extracting parallelism in non-uniform nested loops, WSEAS Transactions on Computers, v.7 n.9, p.1395-1404, September 2008
	Muthu Manikandan Baskaran , Uday Bondhugula , Sriram Krishnamoorthy , J. Ramanujam , Atanas Rountev , P. Sadayappan, Automatic data movement and computation mapping for multi-level parallel architectures with explicitly managed memories, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA
	Fawzy A. Torkey , Afaf A. Salah , Nahed M. El Desouky , Sahar A. Gomaa, Affine and unimodular transformations for non-uniform nested loops, Proceedings of the 12th WSEAS international conference on Computers, p.414-419, July 23-25, 2008, Heraklion, Greece