Array expansion

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Array expansion

Full text

Pdf (873 KB)

Source

International Conference on Supercomputing archive
Proceedings of the 2nd international conference on Supercomputing table of contents

St. Malo, France

Pages: 429 - 441

Year of Publication: 1988

ISBN:0-89791-272-1

Author

P. Feautrier

Univ. Paris VI, FR

Sponsor

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 18, Downloads (12 Months): 45, Citation Count: 26

Additional Information:

abstract 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/55364.55406 What is a DOI?

ABSTRACT

A common problem in restructuring programs for vector or parallel execution is the suppression of false dependencies which originate in the reuse of the same memory cell for unrelated values. The method is simple and well understood in the case of scalars. This paper gives the general solution for the case of arrays. The expansion is done in two steps: first, modify all definitions of the offending array in order to obtain the single assignment property. Then, reconstruct the original data flow by adapting all uses of the array. This is done with the help of a new algorithm for solving parametric integer programs. The technique is quite general and may be used for other purposes, including program checking, collecting array predicates, etc…

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.

	Aho85	Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
	Alle84	John R. Allen , Ken Kennedy, Automatic loop interchange, ACM SIGPLAN Notices, v.19 n.6, p.233-246, June 1984
	Bake77	Brenda S. Baker, An Algorithm for Structuring Flowgraphs, Journal of the ACM (JACM), v.24 n.1, p.98-120, Jan. 1977 [doi>10.1145/321992.321999]
	Cous81	Patrick Cousot , Nicolas Halbwachs, Automatic discovery of linear restraints among variables of a program, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.84-96, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512770]
	Feau88	Feautrier P. Parametric Integer Programming to appear in RAIRO Recherche Operationelle, September 1988
	Jouv87	P. Jouvelot, Semantic parallelization: a practical exercise in abstract interpretation, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.39-48, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41629]
	Kuck78	David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
	Padu86	David A. Padua , Michael J. Wolfe, Advanced compiler optimizations for supercomputers, Communications of the ACM, v.29 n.12, p.1184-1201, Dec. 1986 [doi>10.1145/7902.7904]
	Wolf78	Wolfe M. J Techniques for improving the inherent parallelism in programs. M.S. thesis, Univ of Illinois at Urbane-Champlain, 1978.

CITED BY 26

	François Irigoin , Pierre Jouvelot , Rémi Triolet, Semantical interprocedural parallelization: an overview of the PIPS project, Proceedings of the 5th international conference on Supercomputing, p.244-251, June 17-21, 1991, Cologne, West Germany
	Zhiyuan Li, Array privatization for parallel execution of loops, Proceedings of the 6th international conference on Supercomputing, p.313-322, July 19-24, 1992, Washington, D. C., United States
	Yuan Lin , David Padua, Compiler analysis of irregular memory accesses, ACM SIGPLAN Notices, v.35 n.5, p.157-168, May 2000
	Dror E. Maydan , Saman P. Amarasinghe , Monica S. Lam, Array-data flow analysis and its use in array privatization, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.2-15, March 1993, Charleston, South Carolina, United States
	Peiyi Tang , John N. Zigman, Reducing data communication overhead for DOACROSS loop nests, Proceedings of the 8th international conference on Supercomputing, p.44-53, July 11-15, 1994, Manchester, England
	William Pugh , David Wonnacott, Static analysis of upper and lower bounds on dependences and parallelism, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.4, p.1248-1278, July 1994
	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
	Saman P. Amarasinghe , Monica S. Lam, Communication optimization and code generation for distributed memory machines, ACM SIGPLAN Notices, v.28 n.6, p.126-138, June 1993
	Vadim Maslov, Lazy array data-flow dependence analysis, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.311-325, January 16-19, 1994, Portland, Oregon, United States
	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
	Sungdo Moon , Mary W. Hall, Evaluation of predicated array data-flow analysis for automatic parallelization, ACM SIGPLAN Notices, v.34 n.8, p.84-95, Aug. 1999
	Michelle Mills Strout , Larry Carter , Jeanne Ferrante , Beth Simon, Schedule-independent storage mapping for loops, ACM SIGPLAN Notices, v.33 n.11, p.24-33, Nov. 1998
	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
	Wolfram Amme , Peter Braun , François Thomasset , Eberhard Zehendner, Data Dependence Analysis of Assembly Code, International Journal of Parallel Programming, v.28 n.5, p.431-467, Oct. 2000
	Mary W. Hall , Saman P. Amarasinghe , Brian R. Murphy , Shih-Wei Liao , Monica S. Lam, Interprocedural parallelization analysis in SUIF, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.4, p.662-731, July 2005
	Christian Lengauer , Sergei Gorlatch , Christoph Herrmann, The Static Parallelization of Loops and Recursions, The Journal of Supercomputing, v.11 n.4, p.333-353, Dec. 1997
	Albert Cohen , Sébastien Donadio , Maria-Jesus Garzaran , Christoph Herrmann , Oleg Kiselyov , David Padua, In search of a program generator to implement generic transformations for high-performance computing, Science of Computer Programming, v.62 n.1, p.25-46, September 2006
	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
	Nicolas Vasilache , Cedric Bastoul , Albert Cohen , Sylvain Girbal, Violated dependence analysis, Proceedings of the 20th annual international conference on Supercomputing, June 28-July 01, 2006, Cairns, Queensland, Australia
	Peter Vanbroekhoven , Gerda Janssens , Maurice Bruynooghe , Francky Catthoor, A practical dynamic single assignment transformation, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.12 n.4, p.40-es, September 2007
	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
	Peng Tu , David Padua, Array privatization for shared and distributed memory machines (extended abstract), ACM SIGPLAN Notices, v.28 n.1, p.64-67, Jan. 1993
	K. C. Shashidhar , Maurice Bruynooghe , Francky Catthoor , Gerda Janssens, Functional Equivalence Checking for Verification of Algebraic Transformations on Array-Intensive Source Code, Proceedings of the conference on Design, Automation and Test in Europe, p.1310-1315, March 07-11, 2005
	Mohammed Fellahi , Albert Cohen , Sid Touati, Code-size conscious pipelining of imperfectly nested loops, Proceedings of the 2007 workshop on MEmory performance: DEaling with Applications, systems and architecture, p.49-55, September 16-16, 2007, Brasov, Romania
	William Thies , Frédéric Vivien , Saman Amarasinghe, A step towards unifying schedule and storage optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.6, p.34-es, October 2007
	Anthony Danalis , Lori Pollock , Martin Swany , John Cavazos, MPI-aware compiler optimizations for improving communication-computation overlap, Proceedings of the 23rd international conference on Supercomputing, June 08-12, 2009, Yorktown Heights, NY, USA