Symbolic analysis for parallelizing compilers

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Symbolic analysis for parallelizing compilers

Full text

Ps (420 KB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 18 , Issue 4 (July 1996) table of contents

Pages: 477 - 518

Year of Publication: 1996

ISSN:0164-0925

Authors

Mohammad R. Haghighat
Constantine D. Polychronopoulos

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 91, Citation Count: 28

Additional Information:

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

ABSTRACT

The notion of dependence captures that most important properties of a program for efficient execution on parallel computers. The dependence structure of a program defines that necessary constraints of the order of execution of the program components and provides sufficient information for the exploitation of the available parallelism. Static discovery and management of the dependence structure of programs save a tremendous amount of execution time, and dynamic utilization of dependence information results in a significant performance gain on parallel computers. However, experiments with parallel computers indicate that existing multiprocessing environments are unable to deliver the desired performance over a wide range of real applicatins, mainly due to lack of precision of their dependence information. This calls for an effective compilation scheme capable of understanding the dependence structure of complicated application programs. This article describes a methodology for capturing analyzing program properties that are essential in the effective detection and efficient exploitation of parallelism on parallel computers. Based on this methodology, a symbolic analysis framework is developed for the Parafrase-2 parallelizing compiler. This framework extends the scope of a variety of important program analysis problems and solves them in a unified way. The attained solution space of these problems is much larger than that handled by existing compiler technology. Such a powerful approach is required for the effective compilation of a large class of application programs. programs.

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	Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
	2	Allen, F. E., Cocke, J., and Kennedy, K. 1981. Reduction of operator strength. In Program Flow Analysis, S. S. Muchnick and N. D. Jones, Eds. Prentice-Hall, Englewood Cli s, N.J., 79{101.
	3	John Randal Allen, Dependence analysis for subscripted variables and its application to program transformations, 1983
	4	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]
	5	Zahira Ammarguellat , W. L. Harrison, III, Automatic recognition of induction variables and recurrence relations by abstract interpretation, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.283-295, June 1990, White Plains, New York, United States
	6	R. Apt Krzysztof , Ernst-Rüdiger Olderog, Verification of sequential and concurrent programs, Springer-Verlag New York, Inc., New York, NY, 1991
	7	Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
	8	Utpal K. Banerjee, Loop Parallelization, Kluwer Academic Publishers, Norwell, MA, 1994
	9	Z Furedi , I Barany, Computing the volume is difficult, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.442-447, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12176]
	10	Berry, M., Chen, D., Koss, P., Kuck, D. J., Pointer, L., Lo, S., Pang, Y., Roloff, R., Sameh, A., Clementi, E., Chin, S., Schneider, D., Fox, G., Messina, P., Walker, D., Hsiung, C., Schwarzmeier, J., Lue, K., Orszag, S., Seidl, F., Johnson, O., Swanson, G., Goodrum, R., and Martin, J. 1989. The Perfect Club Benchmarks: E ective performance evaluation of supercomputers. Int. J. Supercomput. Appl. 3, 3 (Fall), 5{40.
	11	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 [doi>10.1109/71.180621]
	12	D. Callahan , J. Dongarra , D. Levine, Vectorizing compilers: a test suite and results, Proceedings of the 1988 ACM/IEEE conference on Supercomputing, p.98-105, November 12-17, 1988, Orlando, Florida, United States
	13	B. F. Caviness, On Canonical Forms and Simplification, Journal of the ACM (JACM), v.17 n.2, p.385-396, April 1970 [doi>10.1145/321574.321591]
	14	Chin-Liang Chang , Richard C. Lee , Richard Char-Tung Lee, Symbolic Logic and Mechanical Theorem Proving, Academic Press, Inc., Orlando, FL, 1997
	15	Cheatham, T. E., Jr., Holloway, G. H., and Townley, J. A. 1979. Symbolic evaluation and the analysis of programs. IEEE Trans. Softw. Eng. 5, 4 (July), 402{417.
	16	Clarke, L. A. and Richardson, D. J. 1981. Symbolic evaluation methods for program analysis. In Program Flow Analysis, S. S. Muchnick and N. D. Jones, Eds. Prentice-Hall, Englewood Cli s, N.J., 264{300.
	17	John Cocke , Ken Kennedy, An algorithm for reduction of operator strength, Communications of the ACM, v.20 n.11, p.850-856, Nov. 1977 [doi>10.1145/359863.359888]
	18	Jacques Cohen , Joel Katcoff, Symbolic Solution of Finite-Difference Equations, ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.261-271, Sept. 1977 [doi>10.1145/355744.355751]
	19	Cooper, K. D., Hall, M. W., and Kennedy, K. 1992. Procedure cloning. In Proceedings of the 4th IEEE International Conference on Computer Languages. IEEE Computer Society, Washington, D.C., 96{105.
	20	Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
	21	Cousot, P. and Cousot, R. 1992. Abstract interpretation frameworks. J. Logic Comput. 2, 4, 511{547.
	22	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]
	23	Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
	24	Ron Cytron , J. Ferrante , V. Sarkar, Experiences using control dependence in PTRAN, Selected papers of the second workshop on Languages and compilers for parallel computing, p.186-212, May 1990, Urbana, Illinois, United States
	25	J. H. Davenport , Y. Siret , E. Tournier, Computer algebra: systems and algorithms for algebraic computation, Academic Press Ltd., London, UK, 1988
	26	Saumya K. Debray , Nai-Wei Lin, Cost analysis of logic programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.5, p.826-875, Nov. 1993 [doi>10.1145/161468.161472]
	27	Martin Dyer , Alan Frieze , Ravi Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies, Journal of the ACM (JACM), v.38 n.1, p.1-17, Jan. 1991 [doi>10.1145/102782.102783]
	28	Eigenmann, R., Hoeflinger, J., Jaxon, G., Li, Z., and Padua, D. 1991. Restructuring Fortran programs for cedar. In Proceedings of the 1991 ICPP. Vol. I. The Pennsylvania State University Press, University Park, Pa., 57{66.
	29	Eisenberg, M. 1971. Axiomatic Theory of Sets and Classes. Holt, Rinehart and Winston, Inc., New York.
	30	John R. Ellis, Bulldog: a compiler for VLSI architectures, MIT Press, Cambridge, MA, 1986
	31	Feautrier, P. 1988. Parametric integer programming. RAIRO Recherche Op erationelle 22, 243{268.
	32	Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
	33	Jeanne Ferrante , Vivek Sarkar , W. Thrash, On Estimating and Enhancing Cache Effectiveness, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.328-343, August 07-09, 1991
	34	Susan Flynn Hummel , Edith Schonberg , Lawrence E. Flynn, Factoring: a method for scheduling parallel loops, Communications of the ACM, v.35 n.8, p.90-101, Aug. 1992 [doi>10.1145/135226.135232]
	35	Amelia C. Fong , Jeffrey D. Ullman, Induction variables in very high level languages, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.104-112, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811544]
	36	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	37	Keith O. Geddes , Stephen R. Czapor , George Labahn, Algorithms for computer algebra, Kluwer Academic Publishers, Norwell, MA, 1992
	38	Milind Baburao Girkar, Functional parallelism: theoretical foundations and implementation, University of Illinois at Urbana-Champaign, Champaign, IL, 1992
	39	M. Gikar , C. Polychronopoulos, Compiling issues for supercomputers, Proceedings of the 1988 ACM/IEEE conference on Supercomputing, p.164-173, November 12-17, 1988, Orlando, Florida, United States
	40	M. Girkar , C. D. Polychronopoulos, Automatic Extraction of Functional Parallelism from Ordinary Programs, IEEE Transactions on Parallel and Distributed Systems, v.3 n.2, p.166-178, March 1992 [doi>10.1109/71.127258]
	41	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
	42	Gosper, R. W., Jr. 1978. Decision procedure for inde nite hypergeometric summation. Proc. Nat. Acad. Sci. 75, 1 (Jan.), 40{42.
	43	Mohammad Reza Haghighat, Symbolic analysis for parallelizing compilers, University of Illinois at Urbana-Champaign, Champaign, IL, 1995
	44	Haghighat, M. R. and Polychronopoulos, C. D. 1991. Symbolic dependence analysis for high-performance parallelizing compilers. In Advances in Languages and Compilers for Parallel Processing, A. Nicolau, D. Gelernter, T. Gross, and D. Padua, Eds. The MIT Press, Cambridge, Mass., 310{330.
	45	Mohammad R. Haghighat , Constantine D. Polychronopoulos, Symbolic Program Analysis and Optimization for Parallelizing Compilers, Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, p.538-562, August 03-05, 1992
	46	Mary W. Hall , John M. Mellor-Crummey , Alan Carle , René G. Rodríguez, FIAT: A Framework for Interprocedural Analysis and Transfomation, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.522-545, August 12-14, 1993
	47	Hansen, E. R. 1992. Global Optimization Using Interval Analysis. Marcel Dekker, New York.
	48	Paul Howard Havlak , Ken Kennedy, Interprocedural symbolic analysis, 1995
	49	P. Havlak , K. Kennedy, An Implementation of Interprocedural Bounded Regular Section Analysis, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.350-360, July 1991 [doi>10.1109/71.86110]
	50	Timothy Hickey , Jacques Cohen, Automating program analysis, Journal of the ACM (JACM), v.35 n.1, p.185-220, Jan. 1988 [doi>10.1145/42267.42275]
	51	F. Irigoin, Interprocedural analyses for programming environments, Environments and tools for parallel scientific computing, Elsevier Science Publishers B. V., Amsterdam, The Netherlands, 1993
	52	John Ivie, Some MACSYMA Programs for Solving Recurrence Relations, ACM Transactions on Mathematical Software (TOMS), v.4 n.1, p.24-33, March 1978 [doi>10.1145/355769.355772]
	53	James P. Jones , Yuri V. Matijasevič, Proof or recursive unsolvability of Hilbert's tenth problem, American Mathematical Monthly, v.98 n.10, p.689-709, Oct. 1991 [doi>10.2307/2324421]
	54	Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
	55	Jordan, C. 1965. Calculus of Finite Di erences, 3rd ed. Chelsea, New York.
	56	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]
	57	Michael Karr, Summation in Finite Terms, Journal of the ACM (JACM), v.28 n.2, p.305-350, April 1981 [doi>10.1145/322248.322255]
	58	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	59	Donald E. Knuth, Two notes on notation, American Mathematical Monthly, v.99 n.5, p.403-422, May 1992 [doi>10.2307/2325085]
	60	Kozen, D. 1981. Semantics of probabilistic programs. J. Comput. Syst. Sci. 22, 3 (June), 328{350.
	61	Clyde P. Kruskal , Alan Weiss, Allocating independent subtasks on parallel processors, IEEE Transactions on Software Engineering, v.11 n.10, p.1001-1016, Oct. 1985 [doi>10.1109/TSE.1985.231547]
	62	Kuck and Associates 1988. KAP User's Guide. Kuck and Associates, Champaign, Ill.
	63	Kuck, D. J., Kuhn, R. H., Leasure, B., and Wolfe, M. J. 1980. The structure of an advanced vectorizer for pipelined processors. In Proceedings of the 4th International Computer Software and Applications Conference. IEEE Computer Society, Washington, D.C., 709{715.
	64	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]
	65	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
	66	Moore, R. E. 1966. Interval Analysis. Prentice-Hall, Englewood Cli s, N.J.
	67	Jose Eduardo Moreira, On the implementation and effectiveness of autoscheduling for shared-memory multiprocessors, University of Illinois at Urbana-Champaign, Champaign, IL, 1996
	68	Joel Moses, Algebraic simplification: a guide for the perplexed, Communications of the ACM, v.14 n.8, p.527-537, Aug. 1971 [doi>10.1145/362637.362648]
	69	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]
	70	Marko Petkovsek, Finding closed-form solutions of difference equations by symbolic methods, Carnegie Mellon University, Pittsburgh, PA, 1991
	71	Constantine D. Polychronopoulos, Parallel Programming and Compilers, Kluwer Academic Publishers, Norwell, MA, 1988
	72	C. D. Polychronopoulos , D. J. Kuck, Guided self-scheduling: A practical scheduling scheme for parallel supercomputers, IEEE Transactions on Computers, v.36 n.12, p.1425-1439, Dec. 1987 [doi>10.1109/TC.1987.5009495]
	73	Polychronopoulos, C. D., Girkar, M. B., Haghighat, M. R., Lee, C. L., Leung, B. P., and Schouten, D. A. 1989. Parafrase-2: An environment for parallelizing, partitioning, synchronizing and scheduling programs on multiprocessors. In Proceedings of the 1989 ICPP. Vol. II. The Pennsylvania State University Press, University Park, Pa., 39{48.
	74	William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical recipes in FORTRAN (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992
	75	William Pugh, A practical algorithm for exact array dependence analysis, Communications of the ACM, v.35 n.8, p.102-114, Aug. 1992 [doi>10.1145/135226.135233]
	76	William Pugh, Counting solutions to Presburger formulas: how and why, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.121-134, June 20-24, 1994, Orlando, Florida, United States
	77	Reif, J. H. and Tarjan, R. E. 81. Symbolic program analysis in almost linear time. SIAM J. Comput. 11, 1 (Feb.), 81{93.
	78	Richardson, D. 1968. Some unsolvable problems involving elementary functions of a real variable. J. Symb. Logic 33, 511{520.
	79	Vivek Sarkar, Partitioning and Scheduling Parallel Programs for Multiprocessors, MIT Press, Cambridge, MA, 1989
	80	Schouten, D. A. 1990. An overview of interprocedural analysis techniques for high performance parallelizing compilers. M.S. thesis, Dept. of Computer Science, Univ. of Illinois at Urbana-Champaign, Urbana, Ill.
	81	Singh, J. P. and Hennessy, J. L. 1992. An empirical investigation of the e ectiveness and limitations of automatic parallelization. In Shared Memory Multiprocessing, N. Suzuki, Ed. The MIT Press, Cambridge, Mass., 213{240.
	82	Tang, P. and Yew, P.-C. 1986. Processor self-scheduling for multiple-nested parallel loops. In Proceedings of the 1986 ICPP. The Pennsylvania State University Press, University Park, Pa., 528{535.
	83	Nadia Tawbi , Paul Feautrier, Processor allocation and loop scheduling on multiprocessor computers, Proceedings of the 6th international conference on Supercomputing, p.63-71, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143387]
	84	Rémi Triolet , Francois Irigoin , Paul Feautrier, Direct parallelization of call statements, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.176-185, June 25-27, 1986, Palo Alto, California, United States
	85	Tzen, T. H. and Ni, L. M. 1991. Dynamic loop scheduling for shared memory multiprocessors. In Proceedings of the 1991 ICPP. Vol. II. The Pennsylvania State University Press, University Park, Pa., 247{250.
	86	Ben Wegbreit, Mechanical program analysis, Communications of the ACM, v.18 n.9, p.528-539, Sept. 1975 [doi>10.1145/361002.361016]
	87	Wegbreit, B. 1975b. Property extraction in well-founded property sets. IEEE Trans. Softw. Eng. 1, 3 (Sept.), 270{285.
	88	Wegbreit, B. 1976a. Goal-directed program transformation. IEEE Trans. Softw. Eng. 2, 2 (June), 69{80.
	89	Ben Wegbreit, Verifying Program Performance, Journal of the ACM (JACM), v.23 n.4, p.691-699, Oct. 1976 [doi>10.1145/321978.321987]
	90	Mark N. Wegman , F. Kenneth Zadeck, Constant propagation with conditional branches, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.181-210, April 1991 [doi>10.1145/103135.103136]
	91	Michael Joseph Wolfe, Optimizing Supercompilers for Supercomputers, MIT Press, Cambridge, MA, 1990
	92	Wolfe, M. J. 1990. Flow graph anomalies: What's in a loop? Tech. Rep., Oregon Graduate Inst., Beaverton, Oreg.
	93	Michael Wolfe, Beyond induction variables, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.162-174, June 15-19, 1992, San Francisco, California, United States
	94	Wolfe, M. J. 1993. Engineering a data dependence test. Concurrency Pract. Exper. 5, 7 (Oct.), 603{622.

CITED BY 28

	Sato Hiroyuki, Array form representation of idiom recognition system for numerical programs, ACM SIGAPL APL Quote Quad, v.31 n.2, p.87-98, December 2000
	Nikolay Mateev , Vijay Menon , Keshav Pingali, Fractal symbolic analysis, Proceedings of the 15th international conference on Supercomputing, p.38-49, June 2001, Sorrento, Italy
	Vijay Menon , Keshav Pingali, High-level semantic optimization of numerical codes, Proceedings of the 13th international conference on Supercomputing, p.434-443, June 20-25, 1999, Rhodes, Greece
	Brendon Cahoon , Kathryn S. McKinley, Simple and effective array prefetching in Java, Proceedings of the 2002 joint ACM-ISCOPE conference on Java Grande, p.86-95, November 03-05, 2002, Seattle, Washington, USA
	Rizos Sakellariou , John R. Gurd, Compile-time minimisation of load imbalance in loop nests, Proceedings of the 11th international conference on Supercomputing, p.277-284, July 07-11, 1997, Vienna, Austria
	Peng Wu , Albert Cohen , Jay Hoeflinger , David Padua, Monotonic evolution: an alternative to induction variable substitution for dependence analysis, Proceedings of the 15th international conference on Supercomputing, p.78-91, June 2001, Sorrento, Italy
	Robert A. van Engelen , J. Birch , Y. Shou , B. Walsh , Kyle A. Gallivan, A unified framework for nonlinear dependence testing and symbolic analysis, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France
	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
	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
	Arun Kejariwal , Alexandru Nicolau , Utpal Banerjee , Constantine D. Polychronopoulos, A novel approach for partitioning iteration spaces with variable densities, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, 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
	Mary W. Hall , Jennifer M. Anderson , Saman P. Amarasinghe , Brian R. Murphy , Shih-Wei Liao , Edouard Bugnion , Monica S. Lam, Maximizing Multiprocessor Performance with the SUIF Compiler, Computer, v.29 n.12, p.84-89, December 1996
	Vijay Menon , Keshav Pingali, Look left, look right, look left again: an application of fractal symbolic analysis to linear algebra code restructuring, International Journal of Parallel Programming, v.32 n.6, p.501-523, December 2004
	Douglas Gregor , Sibylle Schupp, STLlint: lifting static checking from languages to libraries, Software—Practice & Experience, v.36 n.3, p.225-254, March 2006
	Pramod Chandraiah , Rainer Doemer, Designer-controlled generation of parallel and flexible heterogeneous MPSoC specification, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California
	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
	Yixin Shou , Robert A. van Engelen , Johnnie Birch , Kyle A. Gallivan, Toward efficient flow-sensitive induction variable analysis and dependence testing for loop optimization, Proceedings of the 44th annual southeast regional conference, March 10-12, 2006, Melbourne, Florida
	Silvius Rus , Maikel Pennings , Lawrence Rauchwerger, Sensitivity analysis for automatic parallelization on multi-cores, Proceedings of the 21st annual international conference on Supercomputing, June 17-21, 2007, Seattle, Washington
	J. Birch , R.A. van Engelen , K.A. Gallivan , Y. Shou, An empirical evaluation of chains of recurrences for array dependence testing, Proceedings of the 15th international conference on Parallel architectures and compilation techniques, September 16-20, 2006, Seattle, Washington, USA
	Silvius Rus , Guobin He , Christophe Alias , Lawrence Rauchwerger, Region array SSA, Proceedings of the 15th international conference on Parallel architectures and compilation techniques, September 16-20, 2006, Seattle, Washington, USA
	Lawrence Snyder, The design and development of ZPL, Proceedings of the third ACM SIGPLAN conference on History of programming languages, p.8-1-8-37, June 09-10, 2007, San Diego, California
	Johann Blieberger , Thomas Fahringer , Bernhard Scholz, Symbolic Cache Analysis for Real-Time Systems, Real-Time Systems, v.18 n.2-3, p.181-215, May 2000
	Thomas Fahringer, Efficient Symbolic Analysis for Parallelizing Compilers and Performance Estimators, The Journal of Supercomputing, v.12 n.3, p.227-252, May 1, 1998
	Arun Kejariwal , Alexandru Nicolau , Utpal Banerjee , Alexander V. Veidenbaum , Constantine D. Polychronopoulos, Cache-aware iteration space partitioning, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA
	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
	Manuel Arenaz , Juan Touriño , Ramon Doallo, XARK: An extensible framework for automatic recognition of computational kernels, ACM Transactions on Programming Languages and Systems (TOPLAS), v.30 n.6, p.1-56, October 2008
	Arun Kejariwal , Alexandru Nicolau , Utpal Banerjee , Alexander V. Veidenbaum , Constantine D. Polychronopoulos, Cache-aware partitioning of multi-dimensional iteration spaces, Proceedings of SYSTOR 2009: The Israeli Experimental Systems Conference, May 04-April 06, 2009, Haifa, Israel
	Alexandru Nicolau , Guangqiang Li , Alexander V. Veidenbaum , Arun Kejariwal, Synchronization optimizations for efficient execution on multi-cores, Proceedings of the 23rd international conference on Supercomputing, June 08-12, 2009, Yorktown Heights, NY, USA

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Languages, Performance

Keywords:
dependence analysis, parallelization, symbolic analysis

REVIEW

"Max Hailperin : Reviewer"

In this paper, Haghighat and Polychronopoulos perfectly exemplify two of my maxims as a computer science educator: theory is an integral part of practice, not a contrast to it, and a concrete example is often the best way to convey an abstract more...

Collaborative Colleagues:

Mohammad R. Haghighat: colleagues

Constantine D. Polychronopoulos: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player