{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T06:26:47Z","timestamp":1770272807601,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":60,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540572084","type":"print"},{"value":"9783540479680","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-57208-2_28","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T07:18:36Z","timestamp":1330240716000},"page":"398-416","source":"Crossref","is-referenced-by-count":86,"title":["Loop parallelization in the polytope model"],"prefix":"10.1007","author":[{"given":"Christian","family":"Lengauer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,27]]},"reference":[{"key":"28_CR1","doi-asserted-by":"crossref","unstructured":"C. Ancourt and F. Irigoin. Scanning polyhedra with DO loops. In Proc. 3rd ACM SIGPLAN Symp. on Principles & Practice of Parallel Programming (PPoPP), pages 39\u201350. ACM Press, 1991.","DOI":"10.1145\/109625.109631"},{"issue":"2\u20133","key":"28_CR2","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1142\/S0129626492000416","volume":"2","author":"M. Barnett","year":"1992","unstructured":"M. Barnett and C. Lengauer. Unimodularity and the parallelization of loops. Parallel Processing Letters, 2(2\u20133):273\u2013281, 1992.","journal-title":"Parallel Processing Letters"},{"key":"28_CR3","doi-asserted-by":"crossref","unstructured":"M. Barnett and C. Lengauer. Unimodularity considered non-essential (extended abstract). In L. Boug\u00e9, M. Cosnard, Y. Robert, and D. Trystram, editors, Parallel Processing: CONPAR 92-VAPP V, Lecture Notes in Computer Science 634, pages 659\u2013664. Springer-Verlag, 1992.","DOI":"10.1007\/3-540-55895-0_467"},{"key":"28_CR4","doi-asserted-by":"crossref","unstructured":"M. Barnett and C. Lengauer. A systolizing compilation scheme for nested loops with linear bounds. In P. E. Lauer, R. Janicki, and J. Zucker, editors, Functional Programming, Concurrency, Simulation and Automated Reasoning (FPCSAR), Lecture Notes in Computer Science. Springer-Verlag, 1993. To appear.","DOI":"10.1007\/3-540-56883-2_17"},{"key":"28_CR5","unstructured":"J. Bu. Systematic Design of Regular VLSI Processor Arrays. PhD thesis, Department of Electrical Engineering, Delft University of Technology, May 1990."},{"key":"28_CR6","first-page":"341","volume-title":"Algorithms and Parallel VLSI-Architectures","author":"J. Bu","year":"1991","unstructured":"J. Bu and E. F. Deprettere. Processor clustering for the design of optimal fixed-size systolic arrays. In E. F. Deprettere and A.-J. van der Veen, editors, Algorithms and Parallel VLSI-Architectures, volume A, pages 341\u2013362. Elsevier (North-Holland), 1991."},{"issue":"1","key":"28_CR7","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1109\/71.113078","volume":"3","author":"P. R. Cappello","year":"1992","unstructured":"P. R. Cappello. A processor-time-minimal systolic array for cubical mesh algorithms. IEEE Trans. on Parallel and Distributed Systems, 3(1):4\u201313, January 1992.","journal-title":"IEEE Trans. on Parallel and Distributed Systems"},{"key":"28_CR8","doi-asserted-by":"crossref","unstructured":"P. R. Cappello and K. Steiglitz. Unifying VLSI array design with linear transformations of space-time. In F. P. Preparata, editor, Advances in Computing Research, Vol. 2: VLSI Theory, pages 23\u201365. JAI Press, 1984.","DOI":"10.1117\/12.944011"},{"key":"28_CR9","doi-asserted-by":"crossref","unstructured":"M. Chen, Y. Choo, and J. Li. Crystal: Theory and pragmatics of generating efficient parallel code. In B. K. Szymanski, editor, Parallel Functional Languages and Compilers, Frontier Series, chapter 7. ACM Press, 1991.","DOI":"10.1145\/107214.129259"},{"issue":"4","key":"28_CR10","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1016\/0743-7315(86)90010-9","volume":"3","author":"M. C. Chen","year":"1986","unstructured":"M. C. Chen. A design methodology for synthesizing parallel algorithms and architectures. J. Parallel and Distributed Computing, 3(4):461\u2013491, 1986.","journal-title":"J. Parallel and Distributed Computing"},{"key":"28_CR11","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF00128176","volume":"2","author":"M. C. Chen","year":"1988","unstructured":"M. C. Chen, Y. Choo, and J. Li. Compiling parallel programs by optimizing performance. J. Supercomputing, 2:171\u2013207, 1988.","journal-title":"J. Supercomputing"},{"issue":"1","key":"28_CR12","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/BF00930616","volume":"4","author":"P. Clauss","year":"1992","unstructured":"P. Clauss, C. Mongenet, and G. R. Perrin. Calculus of space-optimal mappings of systolic algorithms on processor arrays. J. VLSI Signal Processing, 4(1):27\u201336, February 1992.","journal-title":"J. VLSI Signal Processing"},{"issue":"3","key":"28_CR13","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0167-9260(91)90026-H","volume":"12","author":"A. Darte","year":"1991","unstructured":"A. Darte. Regular partitioning for synthesizing fixed-size systolic arrays. Integration, 12(3):293\u2013304, December 1991.","journal-title":"Integration"},{"key":"28_CR14","doi-asserted-by":"crossref","unstructured":"E. W. Dijkstra and C. S. Scholten. Predicate Calculus and Program Semantics. Texts and Monographs in Computer Science. Springer-Verlag, 1990.","DOI":"10.1007\/978-1-4612-3228-5"},{"issue":"3","key":"28_CR15","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1051\/ro\/1988220302431","volume":"22","author":"P. Feautrier","year":"1988","unstructured":"P. Feautrier. Parametric integer programming. Operations Research, 22(3):243\u2013268, 1988.","journal-title":"Operations Research"},{"key":"28_CR16","unstructured":"P. Feautrier. Semantical analysis and mathematical programming. In M. Cosnard, Y. Robert, P. Quinton, and M. Raynal, editors, Parallel & Distributed Algorithms, pages 309\u2013320. North-Holland, 1989."},{"issue":"1","key":"28_CR17","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/BF01407931","volume":"20","author":"P. Feautrier","year":"1991","unstructured":"P. Feautrier. Dataflow analysis of array and scalar references. Int. J. Parallel Programming, 20(1):23\u201353, February 1991.","journal-title":"Int. J. Parallel Programming"},{"key":"28_CR18","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability. Freeman, 1979."},{"key":"28_CR19","doi-asserted-by":"crossref","unstructured":"P. Held and E. F. Deprettere. HiFi: From parallel algorithm to fixed-size VLSI processor array. In F. Catthoor and L. Svensson, editors, Application-Driven Architecture Synthesis, pages 71\u201392. Kluwer Academic Publishers, 1993.","DOI":"10.1007\/978-1-4615-3242-2_4"},{"key":"28_CR20","unstructured":"C.-H. Huang and P. Sadayappan. Communication-free hyperplane partitioning of nested loops. In D. Gelernter, A. Nicolau, and D. Padua, editors, Languages and Compilers for Parallel Computing. The MIT Press, 1990."},{"issue":"3","key":"28_CR21","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1145\/321406.321418","volume":"14","author":"R. M. Karp","year":"1967","unstructured":"R. M. Karp, R. E. Miller, and S. Winograd. The organization of computations for uniform recurrence equations. J. ACM, 14(3):563\u2013590, July 1967.","journal-title":"J. ACM"},{"key":"28_CR22","volume-title":"PhD thesis","author":"R. H. Kuhn","year":"1980","unstructured":"R. H. Kuhn. Optimization and Interconnection Complexity for Parallel Processors, Single-Stage Networks and Decision Trees. PhD thesis, University of Illinois at Urbana-Champaign, 1980."},{"key":"28_CR23","unstructured":"H. T. Kung and C. E. Leiserson. Algorithms for VLSI processor arrays. In C. Mead and L. Conway, editors, Introduction to VLSI Systems, chapter 8.3. Addison-Wesley, 1980. Previously published as: Systolic arrays for VLSI, in SIAM Sparse Matrix Proceedings, 1978, 245\u2013282."},{"issue":"2","key":"28_CR24","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1145\/360827.360844","volume":"17","author":"L. Lamport","year":"1974","unstructured":"L. Lamport. The parallel execution of DO loops. Comm. ACM, 17(2):83\u201393, February 1974.","journal-title":"Comm. ACM"},{"key":"28_CR25","doi-asserted-by":"crossref","unstructured":"H. Le Verge. Reduction operators in ALPHA. In D. Etiemble and J.-C. Syre, editors, Parallel Architectures and Languages Europe (PARLE '92), Lecture Notes in Computer Science 605, pages 397\u2013410. Springer-Verlag, 1992.","DOI":"10.1007\/3-540-55599-4_101"},{"key":"28_CR26","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/BF00925828","volume":"3","author":"H. Verge Le","year":"1991","unstructured":"H. Le Verge, C. Mauras, and P. Quinton. The ALPHA language and its use for the design of systolic arrays. J. VLSI Signal Processing, 3:173\u2013182, 1991.","journal-title":"J. VLSI Signal Processing"},{"issue":"12","key":"28_CR27","first-page":"1578","volume":"C-37","author":"P. Lee","year":"1988","unstructured":"P. Lee and Z. Kedem. Synthesizing linear-array algorithms from nested for loop algorithms. IEEE Trans. on Computers, C-37(12):1578\u20131598, December 1988.","journal-title":"IEEE Trans. on Computers"},{"issue":"3","key":"28_CR28","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/BF00925834","volume":"3","author":"C. Lengauer","year":"1991","unstructured":"C. Lengauer and J. Xue. A systolic array for pyramidal algorithms. J. VLSI Signal Processing, 3(3):239\u2013259, 1991.","journal-title":"J. VLSI Signal Processing"},{"issue":"2","key":"28_CR29","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/0743-7315(91)90090-V","volume":"13","author":"J. Li","year":"1991","unstructured":"J. Li and M. Chen. The data alignment phase in compiling programs for distributed memory machines. J. Parallel and Distributed Computing, 13(2):213\u2013221, October 1991.","journal-title":"J. Parallel and Distributed Computing"},{"key":"28_CR30","unstructured":"W. Li and K. Pingali. A singular loop transformation framework based on non-singular matrices. Technical Report TR 92-1294, Department of Computer Science, Cornell University, July 1992."},{"key":"28_CR31","doi-asserted-by":"crossref","unstructured":"W. L. Miranker and A. Winkler. Space-time representation of computational structures. Computing, pages 93\u2013114, 1984.","DOI":"10.1007\/BF02253685"},{"issue":"1","key":"28_CR32","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1109\/PROC.1983.12532","volume":"71","author":"D. I. Moldovan","year":"1983","unstructured":"D. I. Moldovan. On the design of algorithms for VLSI systolic arrays. Proc. IEEE, 71(1):113\u2013120, January 1983.","journal-title":"Proc. IEEE"},{"issue":"1","key":"28_CR33","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TC.1986.1676652","volume":"C-35","author":"D. I. Moldovan","year":"1986","unstructured":"D. I. Moldovan and J. A. B. Fortes. Partitioning and mapping algorithms into fixed-size systolic arrays. IEEE Trans. on Computers, C-35(1):1\u201312, January 1986.","journal-title":"IEEE Trans. on Computers"},{"key":"28_CR34","doi-asserted-by":"crossref","unstructured":"G. L. Nemhauser and L. A. Wolsey. Integer and Combinatorial Optimization. Interscience Series in Discrete Mathematics and Optimization. Wiley & Sons, 1988.","DOI":"10.1002\/9781118627372"},{"key":"28_CR35","unstructured":"D. D. Prest. Translation of abstract distributed programs to occam 2. 4th-Year Report, Department of Computer Science, University of Edinburgh, June 1992."},{"key":"28_CR36","doi-asserted-by":"crossref","unstructured":"P. Quinton. Automatic synthesis of systolic arrays from uniform recurrent equations. In Proc. 11th Ann. Int. Symp. on Computer Architecture, pages 208\u2013214. IEEE Computer Society Press, 1984.","DOI":"10.1145\/800015.808184"},{"key":"28_CR37","unstructured":"P. Quinton and Y. Robert. Systolic Algorithms and Architectures. Prentice-Hall, 1990."},{"issue":"2","key":"28_CR38","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/BF02477176","volume":"1","author":"P. Quinton","year":"1989","unstructured":"P. Quinton and V. van Dongen. The mapping of linear recurrence equations on regular arrays. J. VLSI Signal Processing, 1(2):95\u2013113, October 1989.","journal-title":"J. VLSI Signal Processing"},{"key":"28_CR39","unstructured":"S. V. Rajopadhye. Algebraic transformations in systolic array synthesis: A case study. In L. J. M. Claesen, editor, Formal VLSI Specification and Synthesis (VLSI Design Methods-I), pages 361\u2013370. North-Holland, 1990."},{"key":"28_CR40","unstructured":"S. V. Rajopadhye and M. Muddarangegowda. Parallel assignment, reduction and communication. In Proc. SIAM Conference on Parallel Processing for Scientific Computing, pages 849\u2013853. SIAM, 1993."},{"issue":"4","key":"28_CR41","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1109\/71.97903","volume":"2","author":"J. Ramanujam","year":"1991","unstructured":"J. Ramanujam and P. Sadayappan. Compile-time techniques for data distribution in distributed memory machines. IEEE Trans, on Parallel and Distributed Systems, 2(4):472\u2013482, 1991.","journal-title":"IEEE Trans, on Parallel and Distributed Systems"},{"key":"28_CR42","unstructured":"S. K. Rao. Regular Iterative Algorithms and their Implementations on Processor Arrays. PhD thesis, Department of Electrical Engineering, Stanford University, October 1985."},{"issue":"3","key":"28_CR43","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1109\/5.4402","volume":"76","author":"S. K. Rao","year":"1988","unstructured":"S. K. Rao and T. Kailath. Regular iterative algorithms and their implementations on processor arrays. Proc. IEEE, 76 (3):259\u2013282, March 1988.","journal-title":"Proc. IEEE"},{"key":"28_CR44","unstructured":"H. B. Ribas. Automatic Generation of Systolic Programs from Nested Loops. PhD thesis, Department of Computer Science, Carnegie-Mellon University, June 1990. Technical Report CMU-CS-90-143."},{"key":"28_CR45","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1016\/0167-8191(92)90084-K","volume":"18","author":"Y. Robert","year":"1992","unstructured":"Y. Robert and S. W. Song. Revisiting cycle shrinking. Parallel Computing, 18:481\u2013496, 1992.","journal-title":"Parallel Computing"},{"key":"28_CR46","unstructured":"V. Roychowdhury, L. Thiele, S. K. Rao, and T. Kailath. On the localization of algorithms for VLSI processor arrays. In R. Brodersen and H. Moscovitz, editors, VLSI Signal Processing III, pages 459\u2013470. IEEE Press, 1988."},{"key":"28_CR47","unstructured":"A. Schrijver. Theory of Linear and Integer Programming. Series in Discrete Mathematics. Wiley & Sons, 1986."},{"issue":"1\u20132","key":"28_CR48","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/BF00927836","volume":"3","author":"J. Teich","year":"1991","unstructured":"J. Teich and L. Thiele. Control generation in the design of processor arrays. J. VLSI Signal Processing, 3(1\u20132):77\u201392, 1991.","journal-title":"J. VLSI Signal Processing"},{"issue":"3","key":"28_CR49","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/0167-9260(93)90013-3","volume":"14","author":"J. Teich","year":"1993","unstructured":"J. Teich and L. Thiele. Partitioning of processor arrays: A piecewise regular approach. INTEGRATION, 14(3):297\u2013332, 1993.","journal-title":"INTEGRATION"},{"key":"28_CR50","doi-asserted-by":"crossref","unstructured":"L. Thiele. CAD for signal processing architectures. In P. Dewilde, editor, The State of the Art in Computer Systems and Software Engineering, pages 101\u2013151. Kluwer Academic Publishers, 1992.","DOI":"10.1007\/978-1-4615-3506-5_4"},{"key":"28_CR51","unstructured":"A. van der Hoeven. Concepts and Implementation of a Design System for Digital Signal Processing. PhD thesis, Department of Electrical Engineering, Delft University of Technology, October 1992."},{"key":"28_CR52","unstructured":"V. van Dongen. Quasi-regular arrays: Definition and design methodology. In J. V. McCanny, J. McWhirter, and E. E. Swartzlander, editors, Systolic Array Processors, pages 126\u2013135. Prentice Hall, 1989."},{"key":"28_CR53","unstructured":"V. van Dongen and M. Petit. PRESAGE: A tool for the parallelization of nested loop programs. In L. J. M. Claesen, editor, Formal VLSI Specification and Synthesis (VLSI Design Methods-I), pages 341\u2013359. North-Holland, 1990."},{"issue":"4","key":"28_CR54","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1109\/71.97902","volume":"2","author":"M. Wolf","year":"1991","unstructured":"M. Wolf and M. Lam. A loop transformation theory and an algorithm to maximize parallelism. IEEE Trans. on Parallel and Distributed Systems, 2(4):452\u2013471, October 1991.","journal-title":"IEEE Trans. on Parallel and Distributed Systems"},{"key":"28_CR55","doi-asserted-by":"crossref","unstructured":"M. Wolfe. Multiprocessor synchronization for concurrent loops. IEEE Software, pages 34\u201342, January 1988.","DOI":"10.1109\/52.1992"},{"key":"28_CR56","unstructured":"M. Wolfe. Optimizing Supercompilers for Supercomputers. Research Monographs in Parallel and Distributed Computing. MIT Press, 1989."},{"key":"28_CR57","unstructured":"Y. Wong and J. M. Delosme. Optimal systolic implementations of n-dimensional recurrences. In Proc. IEEE Int. Conf. on Computer Design (ICCD 85), pages 618\u2013621. IEEE Press, 1985. Also: Technical Report 8810, Department of Computer Science, Yale University, 1988."},{"issue":"2","key":"28_CR58","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1142\/S0129626491000033","volume":"1","author":"J. Xue","year":"1992","unstructured":"J. Xue. Specifying control signals for systolic arrays by uniform recurrence equations. Parallel Processing Letters, 1(2):83\u201393, 1992.","journal-title":"Parallel Processing Letters"},{"key":"28_CR59","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0167-9260(92)90008-M","volume":"14","author":"J. Xue","year":"1992","unstructured":"J. Xue and C. Lengauer. The synthesis of control signals for one-dimensional systolic arrays. INTEGRATION, 14:1\u201332, 1992.","journal-title":"INTEGRATION"},{"key":"28_CR60","unstructured":"H. Zima. Supercompilers for Parallel and Vector Computers. Frontier Series. Addison-Wesley (ACM Press), 1990."}],"container-title":["Lecture Notes in Computer Science","CONCUR'93"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57208-2_28.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T21:00:32Z","timestamp":1619557232000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57208-2_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540572084","9783540479680"],"references-count":60,"URL":"https:\/\/doi.org\/10.1007\/3-540-57208-2_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993]]}}}