A practical algorithm for exact array dependence analysis

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A practical algorithm for exact array dependence analysis

Full text

Pdf (4.04 MB)

Source

Communications of the ACM archive
Volume 35 , Issue 8 (August 1992) table of contents

Pages: 102 - 114

Year of Publication: 1992

ISSN:0001-0782

Author

William Pugh

Univ. of Maryland, College Park

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 78, Citation Count: 155

Additional Information:

references cited by index terms review 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/135226.135233 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	John Randal Allen, Dependence analysis for subscripted variables and its application to program transformations, 1983
	2	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]
	3	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
	4	V. Balasundaram , K. Kennedy, A technique for summarizing data access and its use in parallelism enhancing transformations, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.41-53, June 19-23, 1989, Portland, Oregon, United States
	5	Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
	6	Michael Burke , Ron Cytron, Interprocedural dependence analysis and parallelization, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.162-175, June 25-27, 1986, Palo Alto, California, United States
	7	Dantzig, G.B. and Eaves, B,C. Fourier-Motzkin elimination and its dual. J. Combin. Theo. A, 14 (1973), 288-297.
	8	Gina Goff , Ken Kennedy , Chau-Wen Tseng, Practical dependence testing, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.15-29, June 24-28, 1991, Toronto, Ontario, Canada
	9	Haghighat, M. and Poiychronopoutos, C. Symbolic dependence analysis for high Performance parallelizing compilers. In Proceed.. ings of the Third Workshop on Languages and Compilers for Parallel Com.. puting, Aug. 1990.
	10	Paul Havlak , Ken Kennedy, Experience with interprocedural analysis of array side effects, Proceedings of the 1990 conference on Supercomputing, p.952-961, October 1990, New York, New York, United States
	11	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 [doi>10.1145/109025.109086]
	12	Klappholz, D. and Kong, X, Extending the Bane{jee-Wolfe test to handle execution conditions. Tech. Rep. 9101, Dept. of EE/CS, Stevens Institute of' Technology, 199i.
	13	Kuck, D., Muraoka, Y. and Chen, S. On the number of operations simultaneousiy executable in Fortrandike programs and their resulting speedup. IEEE Trans. Comput., 1972.
	14	Zhiyuan Li , Pen-Chung Yew, Some results on exact data dependence analysis, Selected papers of the second workshop on Languages and compilers for parallel computing, p.374-401, May 1990, Urbana, Illinois, United States
	15	Zhiyuan Li , Pen-Chung Yew , Chuag-Qi Zhu, Data dependence analysis on multi-dimensional array references, Proceedings of the 3rd international conference on Supercomputing, p.215-224, June 05-09, 1989, Crete, Greece [doi>10.1145/318789.318813]
	16	A. Lichnewsky , F. Thomasset, Introducing symbolic problem solving techniques in the dependence testing phases of a vectorizer, Proceedings of the 2nd international conference on Supercomputing, p.396-406, June 1988, St. Malo, France [doi>10.1145/55364.55403]
	17	Lee-Chung Lu , Marina C. Chen, Subdomain dependence test for massive parallelism, Proceedings of the 1990 conference on Supercomputing, p.962-972, October 1990, New York, New York, United States
	18	Dror E. Maydan , John L. Hennessy , Monica S. Lam, Efficient and exact data dependence analysis, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.1-14, June 24-28, 1991, Toronto, Ontario, Canada
	19	Yoichi Muraoka, Parallelism exposure and exploitation in programs, 1971
	20	William Pugh, Uniform techniques for loop optimization, Proceedings of the 5th international conference on Supercomputing, p.341-352, June 17-21, 1991, Cologne, West Germany [doi>10.1145/109025.109108]
	21	Robert Shostak, Deciding Linear Inequalities by Computing Loop Residues, Journal of the ACM (JACM), v.28 n.4, p.769-779, Oct. 1981 [doi>10.1145/322276.322288]
	22	Triolet, R. Interprocedural analysis for program restructuring with Parafrase. CSRD R.ep, 538, Dept. of Computer Science, University of Illinois at Urbana-Champaign, Dec. 1985.
	23	D. R. Wallace, Dependence of multi-dimensional array references, Proceedings of the 2nd international conference on Supercomputing, p.418-428, June 1988, St. Malo, France [doi>10.1145/55364.55405]
	24	Wotft:, Md. Optimizing supercompilers f'or supercomputers. PhD thesis, Dept, of Computer Science, University of Illinois at Urbanao Champaign, Oct, 1982,
	25	WolIie, M. Optimizing Supercompiters for Supercomputers. Pitman Publishing, London, 1989.
	26	Wolfe, M. The tiny loop restructur ing resea:rch tool. In Proceedings o{' 1991 lnternationat Conference on Para allel Processing, 1991.
	27	Wolfe, M. and Tseng, C, The power test for data dependence. Tech. Rep CS/E 90-015, Oregon Graduate Institme, Aug. 1990.

CITED BY 155

	N. Sreraman , R. Govindarajan, A Vectorizing Compiler for Multimedia Extensions, International Journal of Parallel Programming, v.28 n.4, p.363-400, August 2000
	Yunheung Paek , Jay Hoeflinger , David Padua, Efficient and precise array access analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.1, p.65-109, January 2002
	William Pugh , Evan Rosser, Iteration space slicing and its application to communication optimization, Proceedings of the 11th international conference on Supercomputing, p.221-228, July 07-11, 1997, Vienna, Austria
	Srivaths Ravi , Ganesh Lakshminarayana , Niraj K. Jha, Removal of memory access bottlenecks for scheduling control-flow intensive behavioral descriptions, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.577-584, November 08-12, 1998, San Jose, California, United States
	Nikolay Mateev , Vijay Menon , Keshav Pingali, Fractal symbolic analysis, Proceedings of the 15th international conference on Supercomputing, p.38-49, June 2001, Sorrento, Italy
	John Hughes , Lars Pareto, Recursion and dynamic data-structures in bounded space: towards embedded ML programming, ACM SIGPLAN Notices, v.34 n.9, p.70-81, Sept. 1999
	M. Kandemir , P. Banerjee , A. Choudhary , J. Ramanujam , N. Shenoy, A global communication optimization technique based on data-flow analysis and linear algebra, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.6, p.1251-1297, Nov. 1999
	Vadim Maslov, Enhancing array dataflow dependence analysis with on-demand global value propagation, Proceedings of the 9th international conference on Supercomputing, p.265-269, July 03-07, 1995, Barcelona, Spain
	Tevfik Bultan , Richard Gerber , Christopher League, Composite model-checking: verification with type-specific symbolic representations, ACM Transactions on Software Engineering and Methodology (TOSEM), v.9 n.1, p.3-50, Jan. 2000
	Nawaaz Ahmed , Nikolay Mateev , Keshav Pingali, Tiling imperfectly-nested loop nests, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.31-es, November 04-10, 2000, Dallas, Texas, United States
	John Hughes , Lars Pareto , Amr Sabry, Proving the correctness of reactive systems using sized types, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.410-423, January 21-24, 1996, St. Petersburg Beach, Florida, United States
	Thomas Ball , Sriram K. Rajamani, Automatically validating temporal safety properties of interfaces, Proceedings of the 8th international SPIN workshop on Model checking of software, p.103-122, May 2001, Toronto, Ontario, Canada
	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
	Wei-Ngan Chin , Siau-Cheng Khoo, Calculating sized types, ACM SIGPLAN Notices, v.34 n.11, p.62-72, Nov. 1999
	Rocco Aversa , Beniamino Di Martino , Nicola Mazzocca , Umberto Villano, Reducing Parallel Program Simulation Complexity by Static Analysis, The Journal of Supercomputing, v.17 n.3, p.299-310, Nov. 2000
	Denis Barthou , Albert Cohen , Jean-François Collard, Maximal static expansion, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.98-106, January 19-21, 1998, San Diego, California, United States
	A. Zaafrani , M. R. Ito, Expressing cross-loop dependencies through hyperplane data dependence analysis, Proceedings of the 1994 conference on Supercomputing, p.508-517, December 1994, Washington, D.C., United States
	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
	Zhe Dang , Richard A. Kemmerer, Three approximation techniques for ASTRAL symbolic model checking of infinite state real-time systems, Proceedings of the 22nd international conference on Software engineering, p.345-354, June 04-11, 2000, Limerick, Ireland
	István Forgács, An exact array reference analysis for data flow testing, Proceedings of the 18th international conference on Software engineering, p.565-574, March 25-29, 1996, Berlin, Germany
	Vikram Adve , John Mellor-Crummey, Using integer sets for data-parallel program analysis and optimization, ACM SIGPLAN Notices, v.33 n.5, p.186-198, May 1998
	Tod Amon , Gaetano Borriello , Jiwen Liu, Making complex timing relationships readable: Presburger formula simplicication using don't cares, Proceedings of the 35th annual conference on Design automation, p.586-590, June 15-19, 1998, San Francisco, California, United States
	Mahmut Kandemir , Alok Choudhary , Prithviraj Banerjee , J. Ramanujam , Nagaraj Shenoy, Minimizing Data and Synchronization Costs in One-Way Communication, IEEE Transactions on Parallel and Distributed Systems, v.11 n.12, p.1232-1251, December 2000
	A. S. Huang , G. Slavenburg , J. P. Shen, Speculative disambiguation: a compilation technique for dynamic memory disambiguation, ACM SIGARCH Computer Architecture News, v.22 n.2, p.200-210, April 1994
	William Blume , Rudolf Eigenmann , Jay Hoeflinger , David Padua , Paul Petersen , Lawrence Rauchwerger , Peng Tu, Automatic Detection of Parallelism: A Grand Challenge for High-Performance Computing, IEEE Parallel & Distributed Technology: Systems & Technology, v.2 n.3, p.37-47, September 1994
	Thomas Fahringer , Bernhard Scholz, Symbolic evaluation for parallelizing compilers, Proceedings of the 11th international conference on Supercomputing, p.261-268, July 07-11, 1997, Vienna, Austria
	Yonghong Song , Zhiyuan Li, New tiling techniques to improve cache temporal locality, ACM SIGPLAN Notices, v.34 n.5, p.215-228, May 1999
	Allen Goldberg , T. C. Wang , David Zimmerman, Applications of feasible path analysis to program testing, Proceedings of the 1994 ACM SIGSOFT international symposium on Software testing and analysis, p.80-94, August 17-19, 1994, Seattle, Washington, United States
	Yunheung Paek , Jay Hoeflinger , David Padua, Simplification of array access patterns for compiler optimizations, ACM SIGPLAN Notices, v.33 n.5, p.60-71, May 1998
	Yunheung Paek , Jay Hoeflinger , David Padua, Simplification of array access patterns for compiler optimizations, ACM SIGPLAN Notices, v.33 n.5, p.60-71, May 1998
	Wei-Ngan Chin , Masami Hagiya, A bounds inference method for vector-based memoization, ACM SIGPLAN Notices, v.32 n.8, p.176-187, Aug. 1997
	Siau-Cheng Khoo , Kun Shi, Output-constraint specialization, Proceedings of the ASIAN symposium on Partial evaluation and semantics-based program manipulation, p.106-116, September 12-14, 2002, Aizu, Japan
	Peiyi Tang, Exact side effects for interprocedural dependence analysis, Proceedings of the 7th international conference on Supercomputing, p.137-146, July 19-23, 1993, Tokyo, Japan
	Mary Fernández , Norman Ramsey, Automatic checking of instruction specifications, Proceedings of the 19th international conference on Software engineering, p.326-336, May 17-23, 1997, Boston, Massachusetts, United States
	Ugo Buy , Alessandro Orso , Mauro Pezze, Automated Testing of Classes, ACM SIGSOFT Software Engineering Notes, v.25 n.5, p.39-48, Sept. 2000
	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
	Y. Paek , A. Navarro , E. Zapata , J. Hoeflinger , D. Padua, An Advanced Compiler Framework for Non-Cache-Coherent Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.13 n.3, p.241-259, March 2002
	Yoji Yamada , John Gyllenhall , Grant Haab , Wen-mei Hwu, Data relocation and prefetching for programs with large data sets, Proceedings of the 27th annual international symposium on Microarchitecture, p.118-127, November 30-December 02, 1994, San Jose, California, United States
	Induprakas Kodukula , Nawaaz Ahmed , Keshav Pingali, Data-centric multi-level blocking, ACM SIGPLAN Notices, v.32 n.5, p.346-357, May 1997
	Yanhong A. Liu , Scott D. Stoller, Program optimization using indexed and recursive data structures, ACM SIGPLAN Notices, v.37 n.3, p.108-118, March 2002
	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
	William Blume , Rudolf Eigenmann, The range test: a dependence test for symbolic, non-linear expressions, Proceedings of the 1994 ACM/IEEE conference on Supercomputing, November 14-18, 1994, Washington, D.C.
	Yanhong A. Liu , Scott D. Stoller, From recursion to iteration: what are the optimizations?, ACM SIGPLAN Notices, v.34 n.11, p.73-82, Nov. 1999
	Mohammad R. Haghighat , Constantine D. Polychronopoulos, Symbolic analysis for parallelizing compilers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.4, p.477-518, July 1996
	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
	Ingrid M. Verbauwhede , Chris J. Scheers , Jan M. Rabaey, Memory estimation for high level synthesis, Proceedings of the 31st annual conference on Design automation, p.143-148, June 06-10, 1994, San Diego, California, United States
	Tod Amon , Gaetano Borriello , Taokuan Hu , Jiwen Liu, Symbolic timing verification of timing diagrams using Presburger formulas, Proceedings of the 34th annual conference on Design automation, p.226-231, June 09-13, 1997, Anaheim, California, United States
	William Pugh, Counting solutions to Presburger formulas: how and why, ACM SIGPLAN Notices, v.29 n.6, p.121-134, June 1994
	Apostolos A. Kountouris , Christophe Wolinski, False path analysis based on hierarchical control representation, Proceedings of the 11th international symposium on System synthesis, p.55-59, December 02-04, 1998, Hsinchu, Taiwan, China
	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
	Yang Bo , Zheng Fengzhou , Wang Dingxing , Zheng Weimin, Interactive and symbolic data dependence analysis based on ranges of expressions, Journal of Computer Science and Technology, v.17 n.2, p.160-171, March 2002
	Yanhong A. Liu , Scott D. Stoller, Dynamic Programming via Static Incrementalization, Higher-Order and Symbolic Computation, v.16 n.1-2, p.37-62, March-June 2003
	Wei-Ngan Chin , Siau-Cheng Khoo , Dana N. Xu, Extending sized type with collection analysis, ACM SIGPLAN Notices, v.38 n.10, p.75-84, October 2003
	Zhendong Su , David Wagner, A class of polynomially solvable range constraints for interval analysis without widenings, Theoretical Computer Science, v.345 n.1, p.122-138, 21 November 2005
	Rudolf Eigenmann , Jay Hoeflinger , David Padua, On the Automatic Parallelization of the Perfect Benchmarks®, IEEE Transactions on Parallel and Distributed Systems, v.9 n.1, p.5-23, January 1998
	Bernard Boigelot, On iterating linear transformations over recognizable sets of integers, Theoretical Computer Science, v.309 n.1, p.413-468, 2 December 2003
	Daniel M. Lavery , Wen-Mei W. Hwu, Unrolling-based optimizations for modulo scheduling, Proceedings of the 28th annual international symposium on Microarchitecture, p.327-337, November 29-December 01, 1995, Ann Arbor, Michigan, United States
	William Pugh , David Wonnacott, Constraint-based array dependence analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.3, p.635-678, May 1998
	Weng-Long Chang , Chih-Ping Chu, The infinity Lambda test, Proceedings of the 12th international conference on Supercomputing, p.196-203, July 1998, Melbourne, Australia
	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
	Zhe Dang , Oscar H. Ibarra , Richard A. Kemmerer, Generalized discrete timed automata: decidable approximations for safety verification, Theoretical Computer Science, v.296 n.1, p.59-74, 4 March 2003
	Tevfik Bultan , Richard Gerber , Christopher League, Verifying systems with integer constraints and Boolean predicates: a composite approach, ACM SIGSOFT Software Engineering Notes, v.23 n.2, p.113-123, March 1998
	William Blume , Rudolf Eigenmann, The range test: a dependence test for symbolic, non-linear expressions, Proceedings of the 1994 conference on Supercomputing, p.528-537, December 1994, Washington, D.C., United States
	Jay P. Hoeflinger , Yunheung Paek , Kwang Yi, Unified Interprocedural Parallelism Detection, International Journal of Parallel Programming, v.29 n.2, p.185-215, April 2001
	Angeles Navarro , Emilio Zapata , David Padua, Compiler Techniques for the Distribution of Data and Computation, IEEE Transactions on Parallel and Distributed Systems, v.14 n.6, p.545-562, June 2003
	Bernard Boigelot , Louis Latour, Counting the solutions of Presburger equations without enumerating them, Theoretical Computer Science, v.313 n.1, p.17-29, 16 February 2004
	Siau-Cheng Khoo , Kun Shi, Program Adaptation via Output-Constraint Specialization, Higher-Order and Symbolic Computation, v.17 n.1-2, p.93-128, March-June 2004
	Alexandru Turjan , Bart Kienhuis , Ed Deprettere, Translating affine nested-loop programs to process networks, Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems, September 22-25, 2004, Washington DC, USA
	A. Zaafrani , M. R. Ito, Expressing cross-loop dependencies through hyperplane data dependence analysis, Proceedings of the 1994 ACM/IEEE conference on Supercomputing, November 14-18, 1994, Washington, D.C.
	Induprakas Kodukula , Keshav Pingali, Transformations for imperfectly nested loops, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.12-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States
	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
	Yanhong A. Liu, Efficiency by Incrementalization: An Introduction, Higher-Order and Symbolic Computation, v.13 n.4, p.289-313, Dec. 1, 2000
	M. Cosnard , M. Loi, A simple algorithm for the generation of efficient loop structures, Proceedings of the IFIP WG10.3 working conference on Parallel architectures and compilation techniques, p.159-167, June 27-29, 1995, Limassol, Cyprus
	Wei-Ngan Chin , Siau-Cheng Khoo, Calculating Sized Types, Higher-Order and Symbolic Computation, v.14 n.2-3, p.261-300, September 2001
	Corneliu Popeea , Wei-Ngan Chin, A type system for resource protocol verification and its correctness proof, Proceedings of the 2004 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.135-146, August 24-25, 2004, Verona, Italy
	Michel Cosnard , Emmanuel Jeannot , Tao Yang, Compact DAG representation and its symbolic scheduling, Journal of Parallel and Distributed Computing, v.64 n.8, p.921-935, August 2004
	William Pugh , David Wonnacott, Going Beyond Integer Programming with the Omega Test to Eliminate False Data Dependences, IEEE Transactions on Parallel and Distributed Systems, v.6 n.2, p.204-211, February 1995
	William Blume , Rudolf Eigenmann, Nonlinear and Symbolic Data Dependence Testing, IEEE Transactions on Parallel and Distributed Systems, v.9 n.12, p.1180-1194, December 1998
	Paul M. Petersen , David A. Padua, Static and Dynamic Evaluation of Data Dependence Analysis Techniques, IEEE Transactions on Parallel and Distributed Systems, v.7 n.11, p.1121-1132, November 1996
	Thomas Fahringer , Bernhard Scholz, A Unified Symbolic Evaluation Framework for Parallelizing Compilers, IEEE Transactions on Parallel and Distributed Systems, v.11 n.11, p.1105-1125, November 2000
	Silvano Dal Zilio , Denis Lugiez , Charles Meyssonnier, A logic you can count on, ACM SIGPLAN Notices, v.39 n.1, p.135-146, January 2004
	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
	Hyuk Jae Lee , José A. B. Fortes, Generation of Injective and Reversible Modular Mappings, IEEE Transactions on Parallel and Distributed Systems, v.14 n.1, p.1-12, January 2003
	Changpeng Fang , Steve Carr , Soner Önder , Zhenlin Wang, Reuse-distance-based miss-rate prediction on a per instruction basis, Proceedings of the 2004 workshop on Memory system performance, June 08-08, 2004, Washington, D.C.
	Willem Visser , Corina S. Pǎsǎreanu , Sarfraz Khurshid, Test input generation with java PathFinder, ACM SIGSOFT Software Engineering Notes, v.29 n.4, July 2004
	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
	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
	S. W. Son , G. Chen , M. Kandemir , A. Choudhary, Exposing disk layout to compiler for reducing energy consumption of parallel disk based systems, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA
	Noah Snavely , Saumya Debray , Gregory R. Andrews, Unpredication, Unscheduling, Unspeculation: Reverse Engineering Itanium Executables, IEEE Transactions on Software Engineering, v.31 n.2, p.99-115, February 2005
	Chen Ding , Ken Kennedy, Improving effective bandwidth through compiler enhancement of global cache reuse, Journal of Parallel and Distributed Computing, v.64 n.1, p.108-134, January 2004
	Dinakar Dhurjati , Sumant Kowshik , Vikram Adve , Chris Lattner, Memory safety without garbage collection for embedded applications, ACM Transactions on Embedded Computing Systems (TECS), v.4 n.1, p.73-111, February 2005
	Patricio Bulić , Veselko Guštin, An efficient way to filter out data dependences with a sufficiently large distance between memory references, ACM SIGPLAN Notices, v.40 n.4, April 2005
	K. Subramani , L. Kovalchick, A greedy strategy for detecting negative cost cycles in networks, Future Generation Computer Systems, v.21 n.4, p.607-623, April 2005
	Konstantinos Kyriakopoulos , Kleanthis Psarris, Data dependence analysis techniques for increased accuracy and extracted parallelism, International Journal of Parallel Programming, v.32 n.4, p.317-359, August 2004
	Thi Viet Nga Nguyen , François Irigoin, Efficient and effective array bound checking, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.3, p.527-570, May 2005
	Kleanthis Psarris , Konstantinos Kyriakopoulos, The impact of data dependence analysis on compilation and program parallelization, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA
	Dezhuang Zhang , Rance Cleaveland, Efficient temporal-logic query checking for presburger systems, Proceedings of the 20th IEEE/ACM international Conference on Automated software engineering, November 07-11, 2005, Long Beach, CA, USA
	Sarfraz Khurshid , Yuk Lai Suen, Generalizing symbolic execution to library classes, ACM SIGSOFT Software Engineering Notes, v.31 n.1, January 2006
	Roberto Bagnara , Patricia M. Hill , Elisa Ricci , Enea Zaffanella, Precise widening operators for convex polyhedra, Science of Computer Programming, v.58 n.1-2, p.28-56, October 2005
	Gautam , S. Rajopadhye, Simplifying reductions, ACM SIGPLAN Notices, v.41 n.1, p.30-41, January 2006
	Wei-Ngan Chin , Siau-Cheng Khoo , Shengchao Qin , Corneliu Popeea , Huu Hai Nguyen, Verifying safety policies with size properties and alias controls, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA
	Vijay Menon , Keshav Pingali , Nikolay Mateev, Fractal symbolic analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.25 n.6, p.776-813, November 2003
	Weng-Long Chang , Chih-Ping Chu , Jia-Hwa Wu, A Polynomial-Time Dependence Test for Determining Integer-Valued Solutions in Multi-Dimensional Arrays Under Variable Bounds, The Journal of Supercomputing, v.31 n.2, p.111-135, December 2004
	Paolo D'Alberto , Alexandru Nicolau , Alexander Veidenbaum , Rajesh Gupta, Line Size Adaptivity Analysis of Parameterized Loop Nests for Direct Mapped Data Cache, IEEE Transactions on Computers, v.54 n.2, p.185-197, February 2005
	Yanhong A. Liu , Scott D. Stoller , Ning Li , Tom Rothamel, Optimizing aggregate array computations in loops, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.1, p.91-125, January 2005
	Cyrille Artho , Howard Barringer , Allen Goldberg , Klaus Havelund , Sarfraz Khurshid , Mike Lowry , Corina Pasareanu , Grigore Rosu , Koushik Sen , Willem Visser , Rich Washington, Combining test case generation and runtime verification, Theoretical Computer Science, v.336 n.2-3, p.209-234, 26 May 2005
	Sumant Kowshik , Dinakar Dhurjati , Vikram Adve, Ensuring code safety without runtime checks for real-time control systems, Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems, October 08-11, 2002, Grenoble, France
	Naraig Manjikian , Tarek S. Abdelrahman, Fusion of Loops for Parallelism and Locality, IEEE Transactions on Parallel and Distributed Systems, v.8 n.2, p.193-209, February 1997
	Hongwei Zhu , Ilie I. Luican , Florin Balasa, Memory size computation for multimedia processing applications, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan
	Renato Ferreira , Gagan Agrawal , Joel Saltz, Compiler supported high-level abstractions for sparse disk-resident datasets, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA
	Uday Bondhugula , Albert Hartono , J. Ramanujam , P. Sadayappan, A practical automatic polyhedral parallelizer and locality optimizer, ACM SIGPLAN Notices, v.43 n.6, June 2008
	John Mellor-Crummey , Vikram Adve, Simplifying Control Flow in Compiler-Generated Parallel Code, International Journal of Parallel Programming, v.26 n.5, p.613-638, October 1998
	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
	Arun Kejariwal , Alexandru Nicolau , Hideki Saito , Xinmin Tian , Milind Girkar , Utpal Banerjee , Constantine D. Polychronopoulos, A general approach for partitioning N-dimensional parallel nested loops with conditionals, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Martin Palkovic , Henk Corporaal , Francky Catthoor, Global memory optimisation for embedded systems allowed by code duplication, Proceedings of the 2005 workshop on Software and compilers for embedded systems, p.72-79, September 29-October 01, 2005, Dallas, Texas
	Seung Woo Son , Mahmut Kandemir, Energy-aware data prefetching for multi-speed disks, Proceedings of the 3rd conference on Computing frontiers, May 03-05, 2006, Ischia, Italy
	Willem Visser , Corina S. Pǎsǎreanu , Radek Pelánek, Test input generation for java containers using state matching, Proceedings of the 2006 international symposium on Software testing and analysis, July 17-20, 2006, Portland, Maine, USA
	Hongwei Zhu , Ilie I. Luican , Florin Balasa, Mapping multi-dimensional signals into hierarchical memory organizations, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
	Lakshminarayanan Renganarayanan , DaeGon Kim , Sanjay Rajopadhye , Michelle Mills Strout, Parameterized tiled loops for free, ACM SIGPLAN Notices, v.42 n.6, June 2007
	Jean-Christophe Filliâtre, Formal proof of a program: Find, Science of Computer Programming, v.64 n.3, p.332-340, February, 2007
	Wei-Ngan Chin , Cristina David , Huu Hai Nguyen , Shengchao Qin, Enhancing modular OO verification with separation logic, ACM SIGPLAN Notices, v.43 n.1, January 2008
	Christophe Alias , Fabrice Baray , Alain Darte, Bee+Cl@k: an implementation of lattice-based array contraction in the source-to-source translator rose, ACM SIGPLAN Notices, v.42 n.7, July 2007
	Sanjay Rajopadhye , Gautam Gupta , Lakshminarayanan Renganarayana, A domain specific interconnect for reconfigurable computing, ACM SIGPLAN Notices, v.43 n.7, July 2008
	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
	Alexandru Turjan , Bart Kienhuis , Ed Deprettere, Classifying interprocess communication in process network representation of nested-loop programs, ACM Transactions on Embedded Computing Systems (TECS), v.6 n.2, p.13-es, May 2007
	Rona Machlin, Index-based multidimensional array queries: safety and equivalence, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China
	Florin Balasa , Hongwei Zhu , Ilie I. Luican, Computation of storage requirements for multi-dimensional signal processing applications, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.15 n.4, p.447-460, April 2007
	Corneliu Popeea , Dana N. Xu , Wei-Ngan Chin, A practical and precise inference and specializer for array bound checks elimination, Proceedings of the 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, January 07-08, 2008, San Francisco, California, USA
	Seung Woo Son , Guangyu Chen , Mahmut Kandemir, A Compiler-Guided Approach for Reducing Disk Power Consumption by Exploiting Disk Access Locality, Proceedings of the International Symposium on Code Generation and Optimization, p.256-268, March 26-29, 2006
	R. Drechsler, Using Word-Level Information in Formal Hardware Verification, Automation and Remote Control, v.65 n.6, p.963-977, June 2004
	Tao Zhang , Xiaotong Zhuang , Santosh Pande, Compiler Optimizations to Reduce Security Overhead, Proceedings of the International Symposium on Code Generation and Optimization, p.346-357, March 26-29, 2006
	Wee Kheng Leow , Siau Cheng Khoo , Yi Sun, Automated Generation of Test Programs from Closed Specifications of Classes and Test Cases, Proceedings of the 26th International Conference on Software Engineering, p.96-105, May 23-28, 2004
	Denis Barthou , Albert Cohen , Jean-François Collard, Maximal Static Expansion, International Journal of Parallel Programming, v.28 n.3, p.213-243, June 2000
	Kun Zhang , Tao Zhang , Santosh Pande, Memory Protection through Dynamic Access Control, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.123-134, December 09-13, 2006
	Robert Schreiber , Shail Aditya , Scott Mahlke , Vinod Kathail , B. Ramakrishna Rau , Darren Cronquist , Mukund Sivaraman, PICO-NPA: High-Level Synthesis of Nonprogrammable Hardware Accelerators, Journal of VLSI Signal Processing Systems, v.31 n.2, p.127-142, June 2002
	Wei-Ngan Chin , Huu Hai Nguyen , Corneliu Popeea , Shengchao Qin, Analysing memory resource bounds for low-level programs, Proceedings of the 7th international symposium on Memory management, June 07-08, 2008, Tucson, AZ, USA
	F. Balasa , P. G. Kjeldsberg , A. Vandecappelle , M. Palkovic , Q. Hu , H. Zhu , F. Catthoor, Storage Estimation and Design Space Exploration Methodologies for the Memory Management of Signal Processing Applications, Journal of Signal Processing Systems, v.53 n.1-2, p.51-71, November 2008
	Muthu Manikandan Baskaran , Nagavijayalakshmi Vydyanathan , Uday Kumar Reddy Bondhugula , J. Ramanujam , Atanas Rountev , P. Sadayappan, Compiler-assisted dynamic scheduling for effective parallelization of loop nests on multicore processors, Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, February 14-18, 2009, Raleigh, NC, USA
	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
	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
	DaeGon Kim , Lakshminarayanan Renganarayanan , Dave Rostron , Sanjay Rajopadhye , Michelle Mills Strout, Multi-level tiling: M for the price of one, Proceedings of the 2007 ACM/IEEE conference on Supercomputing, November 10-16, 2007, Reno, Nevada
	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
	Jia-Hwa Wu , Chih-Ping Chu, An exact data dependence testing method for quadratic expressions, Information Sciences: an International Journal, v.177 n.23, p.5316-5328, December, 2007
	Tien-hsiung Weng , Barbara Chapman, Towards optimisation of openMP codes for synchronisation and data reuse, International Journal of High Performance Computing and Networking, v.1 n.1-3, p.43-54, August 2004
	Jia-Hwa Wu , Chih-Ping Chu, A multi-dimensional Interval Reduction test, International Journal of High Performance Computing and Networking, v.4 n.5/6, p.331-337, May 2006
	Minyi Guo , Weng-Long Chang , Jian Lu , Minglu Li, One-dimensional I test and direction vector I test with array references by induction variable, International Journal of High Performance Computing and Networking, v.3 n.4, p.219-226, December 2005
	Alberto Pettorossi , Maurizio Proietti, Totally correct logic program transformations via well-founded annotations, Higher-Order and Symbolic Computation, v.21 n.1-2, p.193-234, June 2008
	Ilie I. Luican , Hongwei Zhu , Florin Balasa, Computation of the minimum data storage and applications in memory management for multimedia signal processing, Integrated Computer-Aided Engineering, v.15 n.2, p.181-196, April 2008
	Michael Hind , Michael Burke , Paul Carini , Sam Midkiff, An empirical study of precise interprocedural array analysis, Scientific Programming, v.3 n.3, p.255-271, Fall 1994
	Jing Zhou , Guosun Zeng, A general data dependence analysis for parallelizing compilers, The Journal of Supercomputing, v.45 n.2, p.236-252, August 2008
	Jing Zhou , Guosun Zeng, A general data dependence analysis for parallelizing compilers, The Journal of Supercomputing, v.45 n.2, p.236-252, August 2008
	Seung Woo Son , Guangyu Chen , Ozcan Ozturk , Mahmut Kandemir , Alok Choudhary, Compiler-Directed Energy Optimization for Parallel Disk Based Systems, IEEE Transactions on Parallel and Distributed Systems, v.18 n.9, p.1241-1257, September 2007
	Albert Hartono , Muthu Manikandan Baskaran , Cédric Bastoul , Albert Cohen , Sriram Krishnamoorthy , Boyana Norris , J. Ramanujam , P. Sadayappan, Parametric multi-level tiling of imperfectly nested loops, Proceedings of the 23rd international conference on Supercomputing, June 08-12, 2009, Yorktown Heights, NY, 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
	A. I. Avetisyan , S. S. Gaisaryan , V. V. Babkova, Iterative development of parallel programs in the ParJava environment, Programming and Computing Software, v.35 n.4, p.223-234, July 2009

INDEX TERMS

Primary Classification:
D. Software
D.3 PROGRAMMING LANGUAGES
D.3.4 Processors
Subjects: Compilers

General Terms:
Algorithms, Experimentation, Languages, Measurement, Performance

Keywords:
Omega test, dependence analysis, integer programming, linear Diophantine equations

REVIEW

"Pierre Jouvelot : Reviewer"

Parallelizing compilers use dependence analysis to detect instructions that do not conflict in memory; these instructions are amenable to parallel scheduling. Most of the interesting parallelism occurs between array-manipulating instructions more...

Collaborative Colleagues:

William Pugh: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player