{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:32:18Z","timestamp":1725489138808},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540040293"},{"type":"electronic","value":"9783540357674"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-35767-x_27","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T07:19:15Z","timestamp":1187248755000},"page":"411-426","source":"Crossref","is-referenced-by-count":0,"title":["Polynomial Time Array Dataflow Analysis"],"prefix":"10.1007","author":[{"given":"Robert","family":"Seater","sequence":"first","affiliation":[]},{"given":"David","family":"Wonnacott","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2003,5,13]]},"reference":[{"key":"27_CR1","unstructured":"R. Eigenmann, J. Hoeflinger, Z. Li, and D. Padua. Experience in the automatic parallelization of 4 Perfect benchmark programs. In Proceedings of the 4th Workshop on Programming Languages and Compilers for Parallel Computing, August 1991. Also Technical Report 1193, CSRD, Univ. of Illinois."},{"issue":"3","key":"27_CR2","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1142\/S0129626494000235","volume":"4","author":"P. Feautrier","year":"1994","unstructured":"Paul Feautrier. Toward automatic distribution. Parallel Processing Letters, 4(3):233\u2013244, September 1994.","journal-title":"Parallel Processing Letters"},{"key":"27_CR3","doi-asserted-by":"crossref","unstructured":"David Wonnacott. Using Time Skewing to eliminate idle time due to memory bandwidth and network limitations. In Proceedings of the 2000 International Parallel and Distributed Processing Symposium, May 2000. An earlier version is available as Rutgers University DCS TR 388.","DOI":"10.1109\/IPDPS.2000.845979"},{"issue":"8","key":"27_CR4","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1145\/135226.135233","volume":"35","author":"W. Pugh","year":"1992","unstructured":"William Pugh. The Omega test: a fast and practical integer programming algorithm for dependence analysis. Communications of the ACM, 35(8):102\u2013114, August 1992.","journal-title":"Communications of the ACM"},{"key":"27_CR5","series-title":"Lect Notes Comput Sci","volume-title":"Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing","author":"W. Pugh","year":"1993","unstructured":"William Pugh and David Wonnacott. An exact method for analysis of value-based array data dependences. In Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, volume 768 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, August 1993. Also available as Tech. Report CS-TR-3196, Dept. of Computer Science, University of Maryland, College Park."},{"issue":"3","key":"27_CR6","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1145\/291889.291900","volume":"20","author":"W. Pugh","year":"1998","unstructured":"William Pugh and David Wonnacott. Constraint-based array dependence analysis. ACM Trans. on Programming Languages and Systems, 20(3):635\u2013678, May 1998.","journal-title":"ACM Trans. on Programming Languages and Systems"},{"key":"27_CR7","doi-asserted-by":"crossref","unstructured":"D. E. Maydan, J. L. Hennessy, and M. S. Lam. Efficient and exact data dependence analysis. In ACM SIGPLAN\u2019 91 Conference on Programming Language Design and Implementation, pages 1\u201314, June 1991.","DOI":"10.1145\/113445.113447"},{"key":"27_CR8","unstructured":"G. Kreisel and J. L. Krevine. Elements of Mathematical Logic. North-Holland Pub. Co., 1967."},{"key":"27_CR9","unstructured":"Michael J. Fischer and Michael O. Rabin. Super-exponential complexity of Presburger arithmetic. In Richard M. Karp, editor, Proceedings of the SIAM-AMS Symposium in Applied Mathematics, volume 7, pages 27\u201341, Providence, RI, 1974. AMS."},{"issue":"3","key":"27_CR10","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/0022-0000(78)90021-1","volume":"16","author":"D. Oppen","year":"1978","unstructured":"D. Oppen. A $$ 2^{2^{2^{pn} } } $$ upper bound on the complexity of presburger arithmetic. Journal of Computer and System Sciences, 16(3):323\u2013332, July 1978.","journal-title":"Journal of Computer and System Sciences"},{"key":"27_CR11","unstructured":"Dror Eliezer Maydan. Accurate Analysis of Array References. PhD thesis, Computer Systems Laboratory, Stanford U., September 1992."},{"key":"27_CR12","unstructured":"Robert Seater and David Wonnacott. Polynomial time array dataflow analysis. Technical Report 2000-38, Center for Discrete Mathematics and Theoretical Computer Science, November 2000."},{"issue":"3","key":"27_CR13","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1177\/109434208900300302","volume":"3","author":"M. Berry","year":"1989","unstructured":"M. Berry et al. The PERFECT Club benchmarks: Effective performance evaluation of supercomputers. International Journal of Supercomputing Applications, 3(3):5\u201340, March 1989.","journal-title":"International Journal of Supercomputing Applications"},{"key":"27_CR14","unstructured":"Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979."},{"key":"27_CR15","doi-asserted-by":"crossref","unstructured":"William Pugh and David Wonnacott. Eliminating false data dependences using the Omega test. In SIGPLAN Conference on Programming Language Design and Implementation, pages 140\u2013151, San Francisco, California, June 1992.","DOI":"10.1145\/143095.143129"},{"key":"27_CR16","unstructured":"David G. Wonnacott. Constraint-Based Array Dependence Analysis. PhD thesis, Dept. of Computer Science, The University of Maryland, August 1995. Available as ftp:\/\/ftp.cs.umd.edu\/pub\/omega\/davewThesis\/davewThesis.ps ."},{"issue":"2","key":"27_CR17","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1145\/322123.322137","volume":"26","author":"R. E. Shostak","year":"1979","unstructured":"Robert E. Shostak. A practical decision procedure for arithmetic with function symbols. Journal of the ACM, 26(2):351\u2013360, April 1979.","journal-title":"Journal of the ACM"},{"key":"27_CR18","doi-asserted-by":"crossref","unstructured":"William Pugh and David Wonnacott. Nonlinear array dependence analysis. In Third Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, Troy, New York, May 1995.","DOI":"10.1007\/978-1-4615-2315-4_1"},{"key":"27_CR19","unstructured":"P. Downey. Undecidability of presburger arithmetic with a single monadic predicate letter. Technical Report 18-72, Center for Research in Computing Technology, Havard Univ., 1972."},{"key":"27_CR20","doi-asserted-by":"crossref","DOI":"10.1007\/978-94-010-2196-8","volume-title":"Advanced Combinatorics","author":"L. Comtet","year":"1974","unstructured":"Louis Comtet. Advanced Combinatorics. D. Reidel Publishing Company, Dordrecht, Holland, 1974."},{"key":"27_CR21","volume-title":"Optimizing Supercompilers for Supercomputers","author":"M. J. Wolfe","year":"1989","unstructured":"M. J. Wolfe. Optimizing Supercompilers for Supercomputers. The MIT Press, Cambridge, Mass., 1989."},{"key":"27_CR22","doi-asserted-by":"crossref","unstructured":"Thomas Brandes. The importance of direct dependences for automatic parallelism. In Proceedings of the 2nd International Conference on Supercomputing, pages 407\u2013417, July 1988.","DOI":"10.1145\/55364.55404"},{"key":"27_CR23","unstructured":"Hudson Ribas. Obtaining dependence vectors for nested-loop computations. In Proceedings of 1990 International Conference on Parallel Processing, pages II-212\u2013II-219, August 1990."},{"key":"27_CR24","unstructured":"Carl Rosene. Incremental Dependence Analysis. PhD thesis, Dept. of Computer Science, Rice University, March 1990."},{"key":"27_CR25","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1002\/spe.4380200203","volume":"20","author":"Thomas Gross","year":"1990","unstructured":"Thomas Gross and Peter Steenkiste. Structured dataflow analysis for arrays and its use in an optimizing compiler. Software\u2014Practice and Experience, 20:133\u2013155, February 1990.","journal-title":"Software\u2014Practice and Experience"},{"issue":"1","key":"27_CR26","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF01407931","volume":"20","author":"P. Feautrier","year":"1991","unstructured":"Paul Feautrier. Dataflow analysis of scalar and array references. International Journal of Parallel Programming, 20(1):23\u201353, February 1991.","journal-title":"International Journal of Parallel Programming"},{"key":"27_CR27","doi-asserted-by":"crossref","unstructured":"M. W. Hall, B. R. Murphy, S. P. Amarasinghe, S. Liao, and M. S. Lam. Interprocedural analysis for parallelization. In Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing, August 1995.","DOI":"10.1007\/BFb0014192"},{"key":"27_CR28","unstructured":"Saman P. Amarasinghe. Parallelizing Compiler Techniques Based on Linear Inequalities. PhD thesis, Computer Systems Laboratory, Stanford U., January 1997."},{"key":"27_CR29","doi-asserted-by":"crossref","unstructured":"Sungdo Moon, Mary W. Hall, and Brian R. Murphy. Predicated array data-flow analysis for run-time parallelization. In Proceedings of the 1998 International Conference on Supercomputing, July 1998.","DOI":"10.1145\/277830.277874"},{"key":"27_CR30","doi-asserted-by":"crossref","unstructured":"Sungdo Moon and Mary W. Hall. Evaluation of predicated array data-flow analysis for automatic parallelization. In Proceedings of the 7th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 84\u201395, May 1999.","DOI":"10.1145\/301104.301112"},{"key":"27_CR31","doi-asserted-by":"crossref","unstructured":"Zhiyuan Li. Array privatization for parallel execution of loops. In Proceedings of the 1992 International Conference on Supercomputing, pages 313\u2013322, July 1992.","DOI":"10.1145\/143369.143426"},{"key":"27_CR32","doi-asserted-by":"crossref","unstructured":"Junjie Gu, Zhiyuan Li, and Gyungho Lee. Symbolic array dataflow analysis for array privatization and program parallelization. In Supercomputing\u2019 95, San Diego, Ca, December 1995.","DOI":"10.1145\/224170.224318"},{"key":"27_CR33","doi-asserted-by":"crossref","unstructured":"Junjie Gu, Zhiyuan Li, and Gyungho Lee. Experience with efficient array data flow analysis for array privatization. In Proceedings of the 6th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 157\u2013167, Las Vegas, Nevada, June 1997.","DOI":"10.1145\/263764.263785"},{"key":"27_CR34","unstructured":"Peng Tu and David Padua. Array privatization for shared and distributed memory machines. In Workshop on Languages, Compilers, and Run-Time Environments for Distributed Memory Multiprocessors, September 1992."},{"key":"27_CR35","unstructured":"Peng Tu. Automatic Array Privatization and Demand-Driven Symbolic Analysis. PhD thesis, Dept. of Computer Science, University of Illinois at Urbana-Champaign, 1995."}],"container-title":["Lecture Notes in Computer Science","Languages and Compilers for Parallel Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-35767-X_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T04:07:37Z","timestamp":1556770057000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-35767-X_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540040293","9783540357674"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/3-540-35767-x_27","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}