{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,15]],"date-time":"2025-08-15T01:56:29Z","timestamp":1755222989256,"version":"3.43.0"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1997,3,1]],"date-time":"1997-03-01T00:00:00Z","timestamp":857174400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1997,3,1]],"date-time":"1997-03-01T00:00:00Z","timestamp":857174400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The Journal of VLSI Signal Processing-Systems for Signal, Image, and Video Technology"],"published-print":{"date-parts":[[1997,3]]},"DOI":"10.1023\/a:1007963228049","type":"journal-article","created":{"date-parts":[[2002,12,22]],"date-time":"2002-12-22T07:13:40Z","timestamp":1040541220000},"page":"259-274","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Finding Space-Time Transformations for Uniform Recurrences via Branching Parametric Linear Programming"],"prefix":"10.1007","volume":"15","author":[{"given":"Karl-Heinz","family":"Zimmermann","sequence":"first","affiliation":[]},{"given":"Wolfgang","family":"Achtziger","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[1997,3,1]]},"reference":[{"key":"128016_CR1","unstructured":"L. Guibas, H.T. Kung, and C.D. Thompson, \u201cDirect VLSI implementation of combinatorial algorithms,\u201d Proc. Conf. on Very Large Scale Integration: Architecture, Design and Fabrication, pp. 509\u2013525, 1979."},{"key":"128016_CR2","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1109\/MC.1982.1653825","volume":"15","author":"H.T. Kung","year":"1982","unstructured":"H.T. Kung, \u201cWhy systolic architectures?,\u201d Computer, Vol. 15, pp. 37\u201346, 1982.","journal-title":"Computer"},{"key":"128016_CR3","volume-title":"VLSI Array Processors","author":"S.Y. Kung","year":"1987","unstructured":"S.Y. Kung, VLSI Array Processors, NJ. Prentice Hall, Englewood Cliffs, 1987."},{"key":"128016_CR4","unstructured":"H.T. Kung and C.E. Leiserson, \u201cSystolic arrays (for VLSI),\u201d in Sparse Matrix Proc., Soc. Ind. App. Math., Duff et al. (Eds.), pp. 256\u2013282, 1979."},{"key":"128016_CR5","unstructured":"C. Mead and L. Conway, Introduction to VLSI Systems, Addison-Wesley, Reading, MA, 1980."},{"key":"128016_CR6","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/BF02253685","volume":"32","author":"W.L. Miranker","year":"1984","unstructured":"W.L. Miranker and A. Winkler, \u201cSpacetime representations of computational structures,\u201d Computing, Vol. 32, pp. 93\u2013114, 1984.","journal-title":"Computing"},{"key":"128016_CR7","first-page":"23","volume":"2","author":"P.R. Cappello","year":"1984","unstructured":"P.R. Cappello and K. Steiglitz, \u201cUnifying VLSI designs with linear tranformations on space time,\u201d Adv. Comput. Res., Vol. 2, pp. 23\u201365, 1984.","journal-title":"Adv. Comput. Res."},{"key":"128016_CR8","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1109\/TC.1985.1676516","volume":"C-34","author":"G. Lin","year":"1985","unstructured":"G. Lin and B.W. Wah, \u201cThe design of optimal systolic design,\u201d IEEE Trans. Comput., Vol. C-34, pp. 66\u201377, 1985.","journal-title":"IEEE Trans. Comput."},{"key":"128016_CR9","volume-title":"Regular Iterative Algorithms and Their Implementations on Processor Arrays","author":"S.K. Rao","year":"1985","unstructured":"S.K. Rao, \u201cRegular Iterative Algorithms and Their Implementations on Processor Arrays,\u201d Ph.D. thesis, Stanford University, Stanford, CA, 1985."},{"key":"128016_CR10","unstructured":"J.-M. Delosme and I.C.F. Ipsen, \u201cSystolic array synthesis: Computability and time cones,\u201d in Parallel Algorithms and Architectures, M. Cosnard et al. (Eds.), North Holland, pp. 295\u2013312, 1986."},{"key":"128016_CR11","unstructured":"J.A.B. Fortes, K.S. Fu, and B.W. Wah, \u201cSystematic approach to the design of algorithmically specified systolic arrays,\u201d Proc. ISCASSP, pp. 8.9.1\u20138.9.4, 1985."},{"issue":"2","key":"128016_CR12","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1109\/12.123393","volume":"41","author":"Y. Wong","year":"1992","unstructured":"Y. Wong and J.-M. Delosme, \u201cOptimization of computation time for systolic arrays,\u201d IEEE Transactions on Computers, Vol. 41, No. 2, pp. 159\u2013177, 1992.","journal-title":"IEEE Transactions on Computers"},{"issue":"3","key":"128016_CR13","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1145\/321406.321418","volume":"13","author":"R.M. Karp","year":"1967","unstructured":"R.M. Karp, R.E. Miller, and S. Winograd, \u201cThe organization of computations for uniform recurrence equations,\u201d Journal of the ACM, Vol. 13, No. 3, pp. 563\u2013590, July 1967.","journal-title":"Journal of the ACM"},{"key":"128016_CR14","doi-asserted-by":"crossref","unstructured":"L. Lamport, \u201cThe parallel execution of DO loops,\u201d Commun. ACM, pp. 83\u201393, 1974.","DOI":"10.1145\/360827.360844"},{"key":"128016_CR15","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"C.H. Papadimitrious","year":"1983","unstructured":"C.H. Papadimitrious and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, NJ, Prentice Hall, Englewood Cliffs, 1983."},{"issue":"6","key":"128016_CR16","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1109\/12.90251","volume":"40","author":"W. Shang","year":"1991","unstructured":"W. Shang and J.A.B. Fortes, \u201cTime optimal linear schedules for algorithms with uniform dependencies,\u201d IEEE Transaction on Computers, Vol. 40, No. 6, pp. 723\u2013742, 1991.","journal-title":"IEEE Transaction on Computers"},{"key":"128016_CR17","doi-asserted-by":"crossref","unstructured":"A. Darte, L. Khachiyan, and Y. Robert, \u201cLinear scheduling is close to optimality,\u201d Int. Conf. on Application Specific Array Processors, IEEE Computer Soc. Press, pp. 37\u201346, 1992.","DOI":"10.1109\/ASAP.1992.218583"},{"key":"128016_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-1077-8","volume-title":"Parallel Programming and Compilers","author":"C.D. Polychronopoulos","year":"1988","unstructured":"C.D. Polychronopoulos, Parallel Programming and Compilers, Kluwer, Boston, 1988."},{"issue":"5","key":"128016_CR19","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/BF01407835","volume":"21","author":"P. Feautrier","year":"1992","unstructured":"P. Feautrier, \u201cSome efficient solutions to the affine scheduling problem. I. One-dimensional time,\u201d Int. J. of Parallel Programming, Vol. 21, No. 5, pp. 313\u2013347, 1992.","journal-title":"Int. J. of Parallel Programming"},{"issue":"8","key":"128016_CR20","doi-asserted-by":"publisher","first-page":"814","DOI":"10.1109\/71.298207","volume":"5","author":"A. Darte","year":"1994","unstructured":"A. Darte and Y. Robert, \u201cConstructive methods for scheduling uniform loop nests,\u201d IEEE Trans. on Parallel and Distributed Systems, Vol. 5, No. 8, pp. 814\u2013822, 1994.","journal-title":"IEEE Trans. on Parallel and Distributed Systems"},{"issue":"2","key":"128016_CR21","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1109\/71.265946","volume":"5","author":"W. Shang","year":"1994","unstructured":"W. Shang, M.T. O'Keefe, and J.A.B. Fortes, \u201cOn loop transformations for generalized cycle shrinking,\u201d IEEE Transaction on Parallel and Distributed Systems, Vol. 5, No. 2, pp. 193\u2013205, 1994.","journal-title":"IEEE Transaction on Parallel and Distributed Systems"},{"key":"128016_CR22","unstructured":"J. McCanny and J. McWhirter, \u201cThe derivation and utilization of bit level systolic array architectures,\u201d Proc. 1986 Int. Workshop Systolic Arrays, Oxford, England, 1986, pp. 47\u201359."},{"key":"128016_CR23","first-page":"178","volume-title":"Parallel Computers: Architecture, Programming and Algorithms","author":"R.W. Hockney","year":"1981","unstructured":"R.W. Hockney and C.R. Jesshope, Parallel Computers: Architecture, Programming and Algorithms, Adam Hilder Ltd.: Bristol, pp. 178\u2013192, 1981."},{"key":"128016_CR24","doi-asserted-by":"crossref","unstructured":"K.E. Batcher, \u201cBit-serial parallel processing systems,\u201d IEEE Trans. on Computers, Vol. C-31, No. 5, pp. 377\u2013384.","DOI":"10.1109\/TC.1982.1676015"},{"key":"128016_CR25","volume-title":"The Connection Machine","author":"W.D. Hillis","year":"1985","unstructured":"W.D. Hillis, The Connection Machine, MIT Press, Cambridge, MA, 1985."},{"key":"128016_CR26","doi-asserted-by":"crossref","unstructured":"M.T. O'Keefe and Z.M. Fortes, \u201cBit level processor array: current architectures and a design and a programming tool,\u201d Int. Symposium on Circuit and System, Helsinki, Finland, 1988, pp. 2751\u20132755.","DOI":"10.1109\/ISCAS.1988.15509"},{"key":"128016_CR27","unstructured":"R.H. Kuhn, \u201cTransforming algorithms for single-stage and VLSI architectures,\u201d Proc. Workshop Interconnection Networks Parallel Distributed Processing, IEEE CH1560\u20132, pp. 11\u201319, 1980."},{"issue":"11","key":"128016_CR28","doi-asserted-by":"publisher","first-page":"1121","DOI":"10.1109\/TC.1982.1675929","volume":"C-31","author":"D.I. Moldovan","year":"1982","unstructured":"D.I. Moldovan, \u201cOn the analysis and synthesis of VLSI algorithms,\u201d IEEE Transaction on Computers, Vol. C-31, No. 11, pp. 1121\u20131126, 1982.","journal-title":"IEEE Transaction on Computers"},{"key":"128016_CR29","unstructured":"Y. Wong and J.-M. Delosme, \u201cOptimal systolic implementation of n-dimensionale recurrences,\u201d IEEE Proc. ICCD, pp. 618\u2013621, 1985."},{"issue":"12","key":"128016_CR30","first-page":"1578","volume":"C-37","author":"P. Lee","year":"1988","unstructured":"P. Lee and Z.M. Kedem, \u201cSynthesizing linear array algorithms from nested for loop algorithms,\u201d IEEE Transaction on Computers, Vol. C-37, No. 12, pp. 1578\u20131597, 1988.","journal-title":"IEEE Transaction on Computers"},{"key":"128016_CR31","unstructured":"W. Shang and Z.M. Fortes, \u201cTime optimal and conflict free mapping of uniform dependence algorithms into lower dimensional processor arrays,\u201d Int. Conference on Parallel Processing, pp. 101\u2013110, 1990."},{"key":"128016_CR32","unstructured":"K.-H. Zimmermann, \u201cLinear mappings of n-dimensional uniform recurrences onto k-dimensional systolic arrays,\u201d J. of VLSI Signal Processing (to appear)."},{"key":"128016_CR33","unstructured":"K.-H. Zimmermann and W. Achtziger, \u201cOn time optimal implementation of uniform recurrences onto array processors via quadratic programming,\u201d J. of VLSI Signal Processing, submitted."},{"key":"128016_CR34","doi-asserted-by":"crossref","unstructured":"R.T. Rockafellar, Convex Analysis, Princeton Univ. Press, Princeton, 1970.","DOI":"10.1515\/9781400873173"},{"key":"128016_CR35","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-62035-5","volume-title":"An Introduction to the Geometry of Numbers","author":"J.W.S. Cassels","year":"1959","unstructured":"J.W.S. Cassels, An Introduction to the Geometry of Numbers, Springer, Berlin, 1959."},{"key":"128016_CR36","first-page":"229","volume-title":"Automata Networks in Computer Science","author":"P. Quinton","year":"1987","unstructured":"P. Quinton, \u201cThe systematic design of systolic arrays,\u201d in Automata Networks in Computer Science, F. Folgelman-Soulie et al. (Eds.), Manchester University Press, Manchester, pp. 229\u2013260, 1987."},{"key":"128016_CR37","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/BF00930641","volume":"4","author":"X. Zhong","year":"1992","unstructured":"X. Zhong, S. Rajopadhye, and I. Wong, \u201cSystematic generation of linear allocation functions in systolic array design,\u201d J. VLSI Signal Processing, Vol. 4, pp. 279\u2013293, 1992.","journal-title":"J. VLSI Signal Processing"},{"key":"128016_CR38","volume-title":"Theory of Linear and Integer Programming","author":"A. Schrijver","year":"1986","unstructured":"A. Schrijver, Theory of Linear and Integer Programming, Wiley & Sons, New York, 1986."},{"key":"128016_CR39","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-9884-4","volume-title":"A Course in Arithmetic","author":"J.-P. Serre","year":"1973","unstructured":"J.-P. Serre, A Course in Arithmetic, New York: Springer, 1973."},{"key":"128016_CR40","unstructured":"NAG (Numerical Algorithms Group Limited) Fortran Library Manual, Mark 16, NAG Ltd., Oxford, UK, 1993."},{"key":"128016_CR41","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/1033001","volume":"33","author":"P.E. Gill","year":"1991","unstructured":"P.E. Gill, W. Murray, M.A. Saunders, and M.H. Wright, \u201cInertia-controlling methods for general quadratic programming,\u201d SIAM Review, Vol. 33, pp. 1\u201336, 1991.","journal-title":"SIAM Review"},{"issue":"1","key":"128016_CR42","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1109\/71.80125","volume":"1","author":"P. Lee","year":"1990","unstructured":"P. Lee and Z.M. Kedem, \u201cMapping nested loop algorithms into multidimensional systolic arrays,\u201d IEEE Trans. on Parallel and Distributed Systems, Vol. 1, No. 1, pp. 64\u201376, 1990.","journal-title":"IEEE Trans. on Parallel and Distributed Systems"}],"container-title":["Journal of VLSI signal processing systems for signal, image and video technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1007963228049.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1007963228049\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1007963228049.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,11]],"date-time":"2025-08-11T09:55:43Z","timestamp":1754906143000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1007963228049"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,3]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1997,3]]}},"alternative-id":["128016"],"URL":"https:\/\/doi.org\/10.1023\/a:1007963228049","relation":{},"ISSN":["0922-5773"],"issn-type":[{"type":"print","value":"0922-5773"}],"subject":[],"published":{"date-parts":[[1997,3]]},"assertion":[{"value":"1 March 1997","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}