Article

Advanced copy propagation for arrays

Authors:

Peter Vanbroekhoven,

Gerda Janssens,

Maurice Bruynooghe,

Henk Corporaal,

Francky CatthoorAuthors Info & Claims

LCTES '03: Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems

Pages 24 - 33

https://doi.org/10.1145/780732.780736

Published: 11 June 2003 Publication History

Abstract

The focus of this paper is on a data flow-transformation called advanced copy propagation. After an array is assigned, we can, under certain conditions, replace a read from this array by the righthand side of the assignment. If so, the intermediate assignment can be skipped. In case it becomes dead code, it can be eliminated. Where necessary we distinguish between the different elements of arrays as well as the different runtime instances of statements, allowing us to do propagation over global loop and condition scopes. We have formalized two basic operations: non-recursive propagation that operates on two statements and recursive propagation that operates on one statement. A global algorithm uses these two operations to do propagation on code involving any number of statements. Running our prototype implementation on some multimedia kernels shows that we can get a decrease in memory acesses between 22% and 43%.

References

[1]

A. V. Aho, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques and Tools. Addison-Wesley, Inc., 1986.

Digital Library

[2]

U. Banerjee. Dependence testing in ordinary programs. Master's thesis, Dept. of Comp. Sci., Univ. of Illinois, Nov. 1976.

[3]

F. Catthoor, S. Wuytack, E. De Greef, F. Balasa, L. Nachtergaele, and A. Vandecappelle. Custom Memory Management Methodology: Exploration of Memory Organisation for Embedded Multimedia System Design. Kluwer Academic Publishers, 1998.

Digital Library

[4]

K. Danckaert. Loop transformations for data transfer and storage reduction on multiprocessor systems. PhD thesis, K.U.Leuven, 2001.

[5]

E. De Greef, F. Catthoor, and H. De Man. Memory size reduction through storage order optimization for embedded parallel multimedia applications. In Proceedings of the Workshop on Parallel Processing and Multimedia of the International Parallel Processing Symposium, pages 84--98, 1997.

Digital Library

[6]

P. Feautrier. Dataflow analysis of array and scalar references. International Journal of Parallel Programming, 20(1):23--53, 1991.

Digital Library

[7]

M. W. Hall, J. M. Anderson, S. P. Amarasinghe, B. R. Murphy, S.-W. Liao, E. Bugnion, and M. S. Lam. Maximizing multiprocessor performance with the suif compiler. In IEEE Computer, December 1996.

Digital Library

[8]

J. Hennessy and D. Patterson. Computer Architecture: A Quantitative Approach. Morgan Kaufmann Publishers, San Francisco, CA, 1996.

Digital Library

[9]

B. Kienhuis. Matparser: An array dataflow analysis compiler. Technical report, University of California, Berkeley, February 2000.

[10]

J. Knoop, O. Ruthing, and B. Steffen. Partial dead code elimination. In SIGPLAN Conference on Programming Language Design and Implementation, pages 147--158, 1994.

Digital Library

[11]

H. Kung and C. Leiserson. Systolic arrays for VLSI. In Sparse Matrix Proceedings, pages 245--282, Philadelphia:SIAM, 1978.

[12]

S. Muchnick. Advanced compiler design & implementation. Morgan Kaufmann Publishers, San Francisco, CA, 1997.

Digital Library

[13]

W. Pugh. The Omega test: A fast and practical integer programming algorithm for dependence analysis. In Proceedings of Supercomputing '91, Albuquerque, NM, 1991.

Digital Library

[14]

F. Quiller'e and S. Rajopadhye. Optimizing memory usage in the polyhedral model. ACM Transactions on Programming Languages, 22(5):773--815, September 2000.

Digital Library

[15]

P. Quinton, S. Rajopadhye, and T. Risset. On manipulating Z-polyhedra. Technical report, Institut de Recherche en Informatique et Systemes Aleatoires, 1996.

[16]

L. Thiele and U. Artz. On the synthesis of massively parallel architectures. International journal of high speed electronics and systems, 4(2):99--131, 1993.

[17]

R. Tronccon, M. Bruynooghe, G. Janssens, and F. Catthoor. Storage size reduction by in-place mapping of arrays. In A. Cortesi, editor, Verification, Model Checking and Abstract Interpretation, Third Int.A Java Virtual Machine Architecture for Very Small Devices Workshop, VMCAI 2002, Revised Papers, volume 2294 of LNCS, pages 167--181. Springer-Verlag, 2002.

Digital Library

[18]

M. Wegman and K. Zadeck. Constant propagation with conditional branches. ACM Transactions on Programming Languages and Systems, 13(2):181--210, April 1991.

Digital Library

Cited By

Doerfert JSharma SHack SDubach CXue J(2018)Polyhedral expression propagationProceedings of the 27th International Conference on Compiler Construction10.1145/3178372.3179529(25-36)Online publication date: 24-Feb-2018
https://dl.acm.org/doi/10.1145/3178372.3179529
Palkovic MCorporaal HCatthoor F(2009)Dealing with data dependent conditions to enable general global source code transformationsInternational Journal of Embedded Systems10.1504/IJES.2009.0272384:1(27)Online publication date: 2009
https://doi.org/10.1504/IJES.2009.027238
Palkovic MCatthoor FCorporaal H(2009)Trade-offs in loop transformationsACM Transactions on Design Automation of Electronic Systems10.1145/1497561.149756514:2(1-30)Online publication date: 7-Apr-2009
https://dl.acm.org/doi/10.1145/1497561.1497565
Show More Cited By

Index Terms

Advanced copy propagation for arrays
1. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

Advanced copy propagation for arrays
Special Issue: Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool support for embedded systems (San Diego, CA).

The focus of this paper is on a data flow-transformation called advanced copy propagation. After an array is assigned, we can, under certain conditions, replace a read from this array by the righthand side of the assignment. If so, the intermediate ...
Defunctionalizing push arrays
FHPC '14: Proceedings of the 3rd ACM SIGPLAN workshop on Functional high-performance computing

Recent work on embedded domain specific languages (EDSLs) for high performance array programming has given rise to a number of array representations. In Feldspar and Obsidian there are two different kinds of arrays, called Pull and Push arrays. Both ...
On the geometry of isotropic arrays

We consider array geometries whose direction-of-arrival (DOA) estimation performance is isotropic. An isotropic array is one whose Cramer-Rao bound (CRB) on the DOA of a single source is uniform for all angles. For both planar arrays and volume arrays ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

LCTES '03: Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems

June 2003

304 pages

ISBN:1581136471

DOI:10.1145/780732

General Chair:
Frank Mueller
North Carolina State University
,
Publications Chair:
Uli Kremer
Rutgers University

ACM SIGPLAN Notices Volume 38, Issue 7
Special Issue: Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool support for embedded systems (San Diego, CA).
July 2003
293 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/780731
Issue’s Table of Contents

Copyright © 2003 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

LCTES03

Sponsor:

LCTES03: ACM SIGPLAN Symposium on Languages, Compilers, and Tools for Embedded Systems

June 11 - 13, 2003

California, San Diego, USA

Acceptance Rates

LCTES '03 Paper Acceptance Rate 29 of 128 submissions, 23%;

Overall Acceptance Rate 116 of 438 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
561
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)1

Reflects downloads up to 28 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Doerfert JSharma SHack SDubach CXue J(2018)Polyhedral expression propagationProceedings of the 27th International Conference on Compiler Construction10.1145/3178372.3179529(25-36)Online publication date: 24-Feb-2018
https://dl.acm.org/doi/10.1145/3178372.3179529
Palkovic MCorporaal HCatthoor F(2009)Dealing with data dependent conditions to enable general global source code transformationsInternational Journal of Embedded Systems10.1504/IJES.2009.0272384:1(27)Online publication date: 2009
https://doi.org/10.1504/IJES.2009.027238
Palkovic MCatthoor FCorporaal H(2009)Trade-offs in loop transformationsACM Transactions on Design Automation of Electronic Systems10.1145/1497561.149756514:2(1-30)Online publication date: 7-Apr-2009
https://dl.acm.org/doi/10.1145/1497561.1497565
Balasa FKjeldsberg PVandecappelle APalkovic MHu QZhu HCatthoor F(2008)Storage Estimation and Design Space Exploration Methodologies for the Memory Management of Signal Processing ApplicationsJournal of Signal Processing Systems10.1007/s11265-008-0244-053:1-2(51-71)Online publication date: 1-Nov-2008
https://dl.acm.org/doi/10.1007/s11265-008-0244-0
Vanbroekhoven PJanssens GBruynooghe MCatthoor F(2007)A practical dynamic single assignment transformationACM Transactions on Design Automation of Electronic Systems10.1145/1278349.127835312:4(40-es)Online publication date: 1-Sep-2007
https://dl.acm.org/doi/10.1145/1278349.1278353
Poucet CMamagkakis SAtienza DCatthoor F(2007)Systematic intermediate sequence removal for reduced memory accessesProceedingsof the 10th international workshop on Software & compilers for embedded systems10.1145/1269843.1269851(51-60)Online publication date: 20-Apr-2007
https://dl.acm.org/doi/10.1145/1269843.1269851
Rus SHe GAlias CRauchwerger LAltman ESkadron KZorn B(2006)Region array SSAProceedings of the 15th international conference on Parallel architectures and compilation techniques10.1145/1152154.1152165(43-52)Online publication date: 16-Sep-2006
https://dl.acm.org/doi/10.1145/1152154.1152165
Balasa FKjeldsberg PPalkovic MVandecappelle ACatthoor F(2006)Loop Transformation Methodologies for Array-Oriented Memory ManagementProceedings of the IEEE 17th International Conference on Application-specific Systems, Architectures and Processors10.1109/ASAP.2006.42(205-212)Online publication date: 11-Sep-2006
https://dl.acm.org/doi/10.1109/ASAP.2006.42
Palkovic MCorporaal HCatthoor FKavi KCytron R(2005)Global memory optimisation for embedded systems allowed by code duplicationProceedings of the 2005 workshop on Software and compilers for embedded systems10.1145/1140389.1140397(72-79)Online publication date: 29-Sep-2005
https://dl.acm.org/doi/10.1145/1140389.1140397
Rus SHe GRauchwerger L(2005)Scalable array SSA and array data flow analysisProceedings of the 18th international conference on Languages and Compilers for Parallel Computing10.1007/978-3-540-69330-7_27(397-412)Online publication date: 20-Oct-2005
https://dl.acm.org/doi/10.1007/978-3-540-69330-7_27
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents