- AI91.Corinne Ancourt and Pran(jois Irigoin. Scanning polyhedra with do loops. In PPOPP '91, 1991. Google ScholarDigital Library
- AK87.J.R. Allen and K. Kennedy. Automatic translation of Fortran programs to vector form. A CM Transactions on Programming Languages and Systems, 9(4):491- 542, October 1987. Google ScholarDigital Library
- All83.J.R. Allen. Dependence Analysis for Subscripted Variables and Its Application to Program Transformations. PhD thesis, Rice University, April 1983. Google ScholarDigital Library
- Ban88.U. Banerjee. Dependence AnaIyszs }or Supercomputing. Kluwer Academic Publishers, Boston, MA, 1988. Google ScholarDigital Library
- BC86.M. Burke and R. Cytron. Interprocedural dependence analysis and parallelization. In em Proceedings of the SIGPLAN '86 Symposium on Compiler Construction, Palo Alto, CA, July 1986. Google ScholarDigital Library
- BK89.V. Balasundaram and K. Kennedy. A technique for summarizing data access and its use in parallelism enhancing transformations. In SIGPLAN Conference on Programming Language Design and Implementation, '89, June 1989. Google ScholarDigital Library
- DE73.G.B. Dantzig and B.C. Eaves. Fourier-Motzkin elimination and its dual. Journal of Combinatorial Theory (A), 14:288-297, 1973.Google ScholarCross Ref
- GKT91.G. Goff, Kenn Kennedy, and Chau-Wen Tseng. Practical dependence testing. In ACM SIGPLAN'91 Conference on Programming Language Design and Implementation, 1991. Google ScholarDigital Library
- HK90.Paul Havlak and Ken Kennedy. Experience with interprocedural analysis of array side effects. In Supercomputing '90, 1990. Google ScholarDigital Library
- HP90.M. Haghighat and C. Polychronopoulos. Symbolic dependence analysis for high performance parallelizing compilers. In Proceedings of the Third Workshop on Language8 and Compilers for Parallel Computing, August 1990.Google Scholar
- IJT91.Pranqois Irigoin, Pierre Jouvelot, and P&mi Triolet. Semantical interprocedural paxallelization: An overview of the pips project. In ICS '91, 1991. Google ScholarDigital Library
- KMC72.D. Kuck, Y. Muraoka, and S. Chen. On the number of operations simultaneously executable in FORTRAN- like programs and their resulting speedup. IEEE Transactions on Computers, 1972.Google ScholarDigital Library
- LC90.L. Lu and M. Chen. Subdomain dependence test for massive parallelism. In Proceedings of Supercomputing '90, New York, NY, November 1990. Google ScholarDigital Library
- LT88.A. Lichnewsky and F. Thomasset. Introducing symbolic problem solving techniques in the dependence testing phases of a vectorizer. In Proceedings of the Second International Conference on Supercomputing, St. Malo, France, July 1988. Google ScholarDigital Library
- LY90.Z. Li and P. Yew. Some results on exact data dependence analysis. In D. Gelernter, A. Nicolau, and D. Padua, editors, Languages and Compilers for Parallel Computing. The MIT Press, 1990. Google ScholarDigital Library
- LYZ89.Z. Li, P. Yew, and C. Zhu. Data dependence analysis on multi-dimensional array references. In Proceedings of the 1989 A CM International Conference on Supercomputing, June 1989. Google ScholarDigital Library
- MHL91.D. E. Maydan, J. L. Hennessy, and M. S. Lain. Efficient and exact data dependence analysis. In A CM SIGPLAN'91 Conference on Programming Language Design and Implementation, 1991. Google ScholarDigital Library
- Mur71.Y. Muraoka. Parallelism Exposure and Exploitation in Programs. PhD thesis, Dept. of Computer Science, University of Illinois at Urbana-Champaign, February 1971. Google ScholarDigital Library
- Pug91.William Pugh. Uniform methods for loop optimization. In 1991 International Conference on Supercomputing, Cologne, Germany, June 1991. Google ScholarDigital Library
- Sho81.R. Shostak. Deciding linear inequalities by computing loop residues. Journal of the A CM, 28(4):769-779, October 1981. Google ScholarDigital Library
- Tri85.R. Triolet. Interprocedural analysis for program restructuring with Parafrase. CSRD Rpt. 538, Dept. of Computer Science, University of Illinois at Urbana- Champaign, December 1985.Google Scholar
- Wal88.D. Wallace. Dependence of multi-dimensional array references. In Proceedings of the Second International Conference on Supercomputing, St. Malo, France, July 1988. Google ScholarDigital Library
- Wol82.M.J. Wolfe. Optimzzing SupercompiIers for Supercomputers. PhD thesis, Dept. of Computer Science, University of Illinois at Urbana-Champaign, October 1982. Google ScholarDigital Library
- Wol89.Michael Wolfe. Optimizing Supercompilers for Supercomputers. Pitman Publishing, London, 1989. Google ScholarDigital Library
- Wol91.Michael Wolfe. The tiny loop restructuring research tool. In Proc of 1991 International Conference on Parallel Processing, 1991.Google Scholar
- WT90.Michael Wolfe and Chau-Wen Tseng. The power test for data dependence. Technical Report CS/E 90-015, Oregon Graduate Institute, August 1990.Google Scholar
Index Terms
- The Omega test: a fast and practical integer programming algorithm for dependence analysis
Recommendations
Fast Integer Sorting in Linear Space
STACS '00: Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer ScienceWe present a fast deterministic algorithm for integer sorting in linear space. Our algorithm sorts n integers in linear space in O(n(log log n)1:5) time. This improves the O(n(log log n)2) time bound given in [11]. This result is obtained by combining ...
Improved Fast Integer Sorting in Linear Space
We present a fast deterministic algorithm for integer sorting in linear space. Our algorithm sorts n integers in the range {0, 1, 2, , m 1} in linear space in O(n log log n log log log n) time. When log m log2+ n, >0, we can further achieve O(n log log ...
Parallel integer sorting and simulation amongst CRCW models
AbstractIn this paper a general technique for reducing processors in simulation without any increase in time is described. This results in an O(√logn) time algorithm for simulating one step of PRIORITY on TOLERANT with processor-time product of O(n log ...
Comments