William Pugh
- 1 Allen,.J.R. Dependence analysis for subscripted wtriables and its applL cation to program transformations. PhD thesis, Rice University, Apr. 1983. Google Scholar
Digital Library
- 2 AlLen, J.R. and Kennedy, K. Automatic translation of Fortran pro.-- grams to vector form. ACM 'Tran,~'. Prog. Lang. Syst. 9, 4 (Oct. i987), 491-542. Google ScholarDigital Library
- 3 Ancourt, C. and I rigoin, P. Scanning polyhedra with do loops. In PPOPP '.91, 199 !. Google ScholarDigital Library
- 4 Balasundaram, V. and Kennedy, K. A technique for summarizing data access and its use in parallelism enhancing transformations. In S!GPI.N Conference on. Program-. ming Language Desist and implemen.- tatioa, '89, June, 1989. Google ScholarDigital Library
- 5 Banerjee, U. Dependence analysis for supercomputing. Kiuwer Academic Publishers, Boston, Mass., 1988. Google ScholarDigital Library
- 6 Burke, M. and Cytron, R. Interprocedural dependence analysis and parallelization. In ProceMmgs q' the SIGPLAN "86 Symposium on Compiler Comtru. ction, Palo Alto, Calif., July, 11986. Google ScholarDigital Library
- 7 Dantzig, G.B. and Eaves, B,C. Fourier-Motzkin elimination and its dual. J. Combin. Theo. A, 14 (1973), 288-297.Google ScholarCross Ref
- 8 Goff, G., Kennedy, K. and Tseng, C. Practical dependence testing. I:, ACM SIGPLAN'91 Conference on Programming Language Design. and Implementation, 199:1. Google ScholarDigital Library
- 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.Google Scholar
- 10 Havlak, P. and Kennedy', K. Experience with interprocedural analysis of array side effeccts. In Superc. om. puting '90, 1990. Google ScholarDigital Library
- 11 Irigoin, P., Jouvelot, P. and Triolet, R, Semantical interprocedural parallelization: An overview of the pips prqject. In ICS '91, i99i. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google ScholarDigital Library
- 14 Li, Z. and Yew, P. Some results on exact: data dependence analysis. In D. Gelernter, A. Nicolau, and D. Padua, Eds., Langmages and Compil~ e rs .for Parallel Computing. 'The M IT Press, 1990. Google ScholarDigital Library
- 15 Li, Z., Yew, P. and Zh.u, C. Data dependence analysis on multidimensional array references. In Proceedings q' th.e 1989 ACM Internationa! ConJerence on Supercomputing, Google ScholarDigital Library
- 16 Lichnewsky, A. and Thomasset, F. Introducing symbolic problem sotw ing techniques in the' d:ependence testing phases of a vectorizer. In Proceedings of the Second International Con'/b~ence on Supercomputing St, Malo, France, July i988. Google ScholarDigital Library
- 17 Lu, L. and Chen, M. Subdomam dependence test for massive parallelism. I n Proceedings Supercomput ing ,90, New York, Nov. 1990. Google ScholarDigital Library
- 18 Maydan, D.E Hennessy, J.L. and Lam, M.S. Efficient and exact data dependence analysis. In ACM SIGPLAN'9i Con.Je'rence on Programruing Language Design and Implemew. tation, 1991. Google ScholarDigital Library
- 19 Muraoka, Y. Parallelism exposure and exploitation in programs. PhD thesis, Dept. of Computer Science, University of Ilhnois at Urbana- Champaign, Feb. 1971. Google ScholarDigital Library
- 20 Pugh, W. Uniform methods for loop optnnization. In 1991 Interna tional Cor~'krence on Supercompting, Cologne, Germany, June 1991. Google ScholarDigital Library
- 21 Shostak, R. Deciding linear inequat~ ities by computing loop residues. J. ACM 28, 4 (Oct- 1981), 769.779. Google ScholarDigital Library
- 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.Google Scholar
- 23 Wallace, D. Dependence of multidimensional array references In Proceedi,gs of the Second International Conference on Supercomputing, St. Malo, France, July 1988. Google ScholarDigital Library
- 24 Wotft:, Md. Optimizing supercompilers f'or supercomputers. PhD thesis, Dept, of Computer Science, University of Illinois at Urbanao Champaign, Oct, 1982,Google Scholar
- 25 WolIie, M. Optimizing Supercompiters for Supercomputers. Pitman Publishing, London, 1989.Google Scholar
- 26 Wolfe, M. The tiny loop restructur ing resea:rch tool. In Proceedings o{' 1991 lnternationat Conference on Para allel Processing, 1991.Google Scholar
- 27 Wolfe, M. and Tseng, C, The power test for data dependence. Tech. Rep CS/E 90-015, Oregon Graduate Institme, Aug. 1990.Google Scholar
Index Terms
- A practical algorithm for exact array dependence analysis
Recommendations
Exact procedures for solving the discrete ordered median problem
The discrete ordered median problem (DOMP) integrates classical discrete location problems, such as the N- median, N-center and Uncapacitated Facility Location problems. It was introduced by Nickel (In: Fleischmann B, Lasch R, Derigs U, Domschke W, ...
Exact solution approach for a class of nonlinear bilevel knapsack problems
We study a class of nonlinear bilevel knapsack problems. The upper-level objective is a nonlinear integer function of both the leader's and the follower's decision variables. At the lower level the follower solves a linear binary knapsack problem, where ...
A Value-Function-Based Exact Approach for the Bilevel Mixed-Integer Programming Problem
We examine bilevel mixed-integer programs whose constraints and objective functions depend on both upper-and lower-level variables. The class of problems we consider allows for nonlinear terms to appear in both the constraints and the objective ...
Reviews
Pierre Jouvelot
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 within loops. In a given loop context, precisely deciding when and under which conditions two array indices are equal amounts to solving an integer programming problem. Pugh debunks the common idea that using a general integer programming solver is too time-consuming. His research paper introduces the new constraint-solving algorithm Omega, which adapts the classical Fourier-Motzkin technique to integer constraints and extends it with new methods for dealing with equalities; discusses its use for performing integer projections in the computation of data dependence direction and distance vectors, which describe the dependence conditions between loop iterations; and shows the practicality of this approach on some NASA NAS benchmarks. The Omega test has been implemented in Michael Wolfe's TINY system and is freely available. The presented results are impressive, although I regret that neither the precise algorithm nor a correctness proof is given. (Admittedly, formally specifying the complete algorithm would probably require too many pages to make it worthwhile to a large audience, and the paper contains enough details to allow the interested reader to infer the algorithm and proof, if need be.) The performance data are promising, although the benchmark programs do not exercise the most complex part of the algorithm; since this algorithm is supposed to be used in compilers, it would have been interesting to see what the cost penalties due to its worst-case exponential time complexity are. As emphasized by a detailed related work section, the subject addressed in this paper is important for today's parallelizing technology, and the paper should be of significant interest to researchers working on optimizing and parallelizing compilers. Although rather technical, the paper is clearly written. It uses helpful drawings to give an intuition about what is going on in the algorithm, although I regret that color was not used to enhance their readability.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments