{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T19:40:09Z","timestamp":1736106009724,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":61,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540610434"},{"type":"electronic","value":"9783540498759"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/bfb0027118","type":"book-chapter","created":{"date-parts":[[2005,11,19]],"date-time":"2005-11-19T11:08:23Z","timestamp":1132398503000},"page":"51-86","source":"Crossref","is-referenced-by-count":0,"title":["Automatic synthesis of parallel algorithms"],"prefix":"10.1007","author":[{"given":"G. M.","family":"Megson","sequence":"first","affiliation":[]},{"given":"L.","family":"Rapanotti","sequence":"additional","affiliation":[]},{"given":"X.","family":"Chen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,17]]},"reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"C.Ancourt, F.Irigoin, \u201cScanning polyhedra with DO loops\u201d, Proceedings 3rd SIGPLAN Symposium on Principles and Practice of Parallel Programming, ACM Press, pp. 39\u201350, 1991.","DOI":"10.1145\/109625.109631"},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"R.Andonov, F.Gruau, \u201cA 2D modular toroidal systolic array for the knapsack problem\u201d, Proceedings ASAP 91, pp. 458\u2013472, 1991.","DOI":"10.1109\/ASAP.1991.238902"},{"key":"4_CR3","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/3-540-55895-0_419","volume":"no. 634","author":"R. Andonov","year":"1992","unstructured":"R.Andonov, P.Quinton, \u201cEfficient linear systolic array for the knapsack problem\u201d, Proceedings CONPAR 92, Lecture Notes in Computer Science, no. 634, pp. 247\u2013258, 1992.","journal-title":"Lecture Notes in Computer Science"},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"M.Barnett, C.Lengauer, \u201cLoop parallelization and unimodularity\u201d, Algorithmique Parall\u00e8le, M.Cosnard, M.Nivat (eds.), Masson, 1992.","DOI":"10.1142\/S0129626492000416"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"M.Barnett, C.Lengauer, \u201cUnimodularity considered non-essential\u201d, Proceedings CONPAR-92, Lecture Notes in Computer Science, no. 634, pp. 659\u2013664, Springer-Verlag, 1992.","DOI":"10.1007\/3-540-55895-0_467"},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"J.C.Bu, E.F.Deprettere, P.Dewilde, \u201cA design methodology for fixed-size systolic arrays\u201d, Proceedings International Conference on Application Specific Array, IEEE Press, pp. 591\u2013602, 1990.","DOI":"10.1109\/ASAP.1990.145495"},{"key":"4_CR7","unstructured":"B.Carr\u00e9, Graphs and networks. Oxford Applied Mathematics and Computing Science Series, Oxford University Press, 1979."},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0167-8191(90)90124-R","volume":"13","author":"G. Chen","year":"1990","unstructured":"G.Chen, M.Chern, J.Jang, \u201cPipeline architectures for dynamic programming algorithms\u201d, Parallel Computing, vol. 13, pp. 111\u2013117, 1990.","journal-title":"Parallel Computing"},{"key":"4_CR9","unstructured":"V.Chv\u00e1tal, Linear programming. W.H.Freeman and Company, 1983."},{"key":"4_CR10","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1016\/0041-5553(65)90045-5","volume":"5","author":"N.V. Chernikiva","year":"1965","unstructured":"N.V.Chernikiva, \u201cAlgorithm for finding a general formula for the non-negative solutions of a system of linear inequalities\u201d, U.S.S.R. \u2014 Computational Mathematics and Mathematical Physics, vol. 5, pp. 228\u2013233, 1965.","journal-title":"U.S.S.R. \u2014 Computational Mathematics and Mathematical Physics"},{"key":"4_CR11","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1016\/S0747-7171(06)80005-2","volume":"15","author":"P. Clauss","year":"1993","unstructured":"P.Clauss, C.Mongenet, \u201cSynthesis aspects in the design of efficient processor arrays from affine recurrence equations\u201d, Journal of Symbolic Computation, vol. 15, pp. 547\u2013569, 1993.","journal-title":"Journal of Symbolic Computation"},{"key":"4_CR12","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0167-9260(91)90026-H","volume":"12","author":"A. Darte","year":"1991","unstructured":"A.Darte, \u201cRegular partitioning for synthesizing fixed-size systolic arrays\u201d, Integration \u2014 Journal of VLSI, vol. 12, pp. 293\u2013304, 1991.","journal-title":"Integration \u2014 Journal of VLSI"},{"issue":"no.2","key":"4_CR13","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1142\/S0129626491000021","volume":"1","author":"A. Darte","year":"1991","unstructured":"A.Darte, L.Khachiyan, Y.Robert, \u201cLinear scheduling is nearly optimal\u201d, Parallel Processing Letters, vol. 1, no. 2, pp. 73\u201381, 1991.","journal-title":"Parallel Processing Letters"},{"issue":"no.8","key":"4_CR14","doi-asserted-by":"publisher","first-page":"814","DOI":"10.1109\/71.298207","volume":"5","author":"A. Darte","year":"1994","unstructured":"A.Darte, Y.Robert, \u201cConstructive methods for scheduling uniform loop nests\u201d, IEEE Transactions on Parallel and Distributed Systems, vol. 5, no. 8, pp. 814\u2013822, 1994.","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"4_CR15","first-page":"243","volume":"22","author":"P. Feautrier","year":"1988","unstructured":"P.Feautrier, \u201cParametric integer programming\u201d, RAIRO Recherche Op\u00e9rationnelle, vol. 22, pp. 243\u2013268, 1988.","journal-title":"RAIRO Recherche Op\u00e9rationnelle"},{"issue":"no.5","key":"4_CR16","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, part I, one dimensional time\u201d, Journal of Parallel Programming, vol. 21, no. 5, pp. 313\u2013348, 1992.","journal-title":"Journal of Parallel Programming"},{"issue":"no.6","key":"4_CR17","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/BF01379404","volume":"21","author":"P. Feautrier","year":"1992","unstructured":"P.Feautrier, \u201cSome efficient solutions to the affine scheduling problem, part II, multidimensional time\u201d, Journal of Parallel Programming, vol. 21, no. 6, pp. 389\u2013420, 1992.","journal-title":"Journal of Parallel Programming"},{"issue":"no.3","key":"4_CR18","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1142\/S0129626494000235","volume":"4","author":"P. Feautrier","year":"1994","unstructured":"P.Feautrier, \u201cTowards automatic distribution\u201d, Parallel Processing Letters, vol. 4, no. 3, pp. 233\u2013244, 1994.","journal-title":"Parallel Processing Letters"},{"key":"4_CR19","doi-asserted-by":"crossref","unstructured":"J.A.B.Fortes, D.Moldovan, \u201cData broadcasting in linearly scheduled array processors\u201d, Proceedings 11th Annual Symposium on Computer Architecture, pp. 224\u2013231, 1984.","DOI":"10.1145\/800015.808186"},{"key":"4_CR20","unstructured":"M.Garey, D.Johnson, Computers and intractability: a guide to the theory of NP-Completeness. Freeman, 1979."},{"key":"4_CR21","unstructured":"T.E.Gerasch, \u201cA parallel approximation algorithm for 0\/1 knapsack\u201d, Proceedings International Conference on Parallel Processing, pp. 302\u2013303, 1991."},{"key":"4_CR22","unstructured":"D.E.Goldberg, Genetic Algorithms in Search Optimisation and Machine Learning. Addison Wesley, 1989"},{"key":"4_CR23","unstructured":"L.J.Guibas, H.T.Kung, C.D.Thompson, \u201cDirect VLSI implementation of combinatorial algorithms\u201d, Proceedings Caltech Conference on VLSI, pp 509\u2013525, 1979."},{"key":"4_CR24","unstructured":"T.C.Hu, Combinatorial algorithms. Addison-Wesley Publishing Company, 1982."},{"key":"4_CR25","doi-asserted-by":"crossref","unstructured":"F.Irigoin, R.Triolet, \u201cSupernode partitioning\u201d, Proceedings 15th POPL, San Diego, California, pp. 319\u2013328, 1988.","DOI":"10.1145\/73560.73588"},{"key":"4_CR26","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/0167-739X(89)90003-4","volume":"4","author":"J. Jansen","year":"1988","unstructured":"J.Jansen, F.M.Dijstermans, \u201cParallel branch-and-bound algorithms\u201d, Future Generation Computer Systems, vol. 4, pp. 271\u2013279, 1988.","journal-title":"Future Generation Computer Systems"},{"issue":"no.3","key":"4_CR27","first-page":"563:590","volume":"14","author":"R.M. Karp","year":"1967","unstructured":"R.M.Karp, R.E.Miller, S.Winograd, \u201cThe organization of computations for uniform recurrence equations\u201d, Journal of the ACM, vol. 14, no. 3, pp. 563:590, 1967.","journal-title":"Journal of the ACM"},{"issue":"no.2","key":"4_CR28","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1145\/360827.360844","volume":"17","author":"L. Lamport","year":"1974","unstructured":"L.Lamport, \u201cThe parallel execution of DO loops\u201d, Communications of the ACM, vol. 17, no. 2, pp. 83\u201393, 1974.","journal-title":"Communications of the ACM"},{"issue":"no.12","key":"4_CR29","first-page":"1578","volume":"C-37","author":"P. Lee","year":"1988","unstructured":"P.Lee, Z.M.Kedem, \u201cSynthesizing linear array algorithms from nested loop algorithms\u201d, IEEE Transactions on Computers, vol. C-37, no. 12, pp. 1578\u20131598, 1988.","journal-title":"IEEE Transactions on Computers"},{"issue":"no.1","key":"4_CR30","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1109\/71.80125","volume":"1","author":"P. Lee","year":"1990","unstructured":"P.Lee, Z.M.Kedem, \u201cMapping nested loop algorithms into multi-dimensional systolic arrays\u201d, IEEE Transactions Parallel and Distributed Systems, vol. 1, no. 1, pp. 64\u201376, 1990.","journal-title":"IEEE Transactions Parallel and Distributed Systems"},{"key":"4_CR31","unstructured":"S.Martello, P.Toth, Knapsack problems: algorithms and computer implementation. John Wiley and Sons, 1990."},{"key":"4_CR32","unstructured":"G.M.Megson, An Introduction to Systolic Algorithm Design. Oxford Science Publications, 1992."},{"key":"4_CR33","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1080\/10637199308915436","volume":"1","author":"G.M. Megson","year":"1993","unstructured":"G.M.Megson, \u201cThe derivation of uniform recurrences for the knapsack problem\u201d, Journal of Parallel Algorithms and Applications, vol. 1, pp. 127\u2013140, 1993.","journal-title":"Journal of Parallel Algorithms and Applications"},{"key":"4_CR34","doi-asserted-by":"crossref","unstructured":"G.M.Megson, \u201cMapping a class of run-time dependencies onto regular arrays\u201d, Proceedings 7th International Parallel Processing Symposium, IEEE Computer Society Press, pp. 97\u2013104, 1993.","DOI":"10.1109\/IPPS.1993.262863"},{"key":"4_CR35","unstructured":"G.M.Megson (ed.), Transformational approaches to systolic design. Chapman-Hall Parallel and Distributed Computing Series 2, 1994."},{"key":"4_CR36","doi-asserted-by":"crossref","unstructured":"G.M.Megson, X.Chen, \u201cPartitioning and mapping for lower dimensional given arrays\u201d, Proceedings 2nd Euromicro Workshop on Parallel and Distributed Computing, IEEE Computer Society Press, pp. 149\u2013156, 1994.","DOI":"10.1109\/EMPDP.1994.592482"},{"key":"4_CR37","unstructured":"G.M.Megson, X.Chen, \u201cSynthesis of knapsack problems into fixed size arrays with lower dimensions\u201d, University of Newcastle upon Tyne, Technical Report Series, no. 486, 1994."},{"issue":"no.1","key":"4_CR38","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, A.B.Fortes, \u201cPartitioning and mapping algorithms into fixed size systolic arrays\u201d, IEEE Transaction on Computer, vol. c-35, no. 1, pp. 1\u201312, 1986.","journal-title":"IEEE Transaction on Computer"},{"key":"4_CR39","unstructured":"R.-W.Mourad, P.Feautrier, \u201cOn parallel program generation for massively parallel architectures\u201d, Proceedings High Performance Computing II, North-Holland, 1991."},{"key":"4_CR40","unstructured":"E.D.Nering, Linear algebra and matrix theory. J.Wiley & Sons Inc., 1963."},{"key":"4_CR41","unstructured":"P.Quinton, \u201cThe systematic design of systolic arrays\u201d, INRIA Technical Report, no. 216, 1983."},{"key":"4_CR42","doi-asserted-by":"crossref","unstructured":"P.Quinton, \u201cAutomatic synthesis of systolic arrays from uniform recurrent equations\u201d, IEEE\/ACM Proceedings 11th Annual International Symposium on Computer Architecture, 1984.","DOI":"10.1145\/800015.808184"},{"key":"4_CR43","unstructured":"P.Quinton, Y.Robert, Systolic algorithms and architectures. Masson and Prentice Hall International, 1991."},{"key":"4_CR44","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/BF02477176","volume":"1","author":"P. Quinton","year":"1989","unstructured":"P.Quinton, V.VanDongen, \u201cThe mapping of linear recurrence equations on regular arrays\u201d, Journal of VLSI Signal Processing, vol. 1, pp. 95\u2013113, 1989.","journal-title":"Journal of VLSI Signal Processing"},{"key":"4_CR45","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/BF01558666","volume":"2","author":"S.V. Rajopadhye","year":"1989","unstructured":"S.V. Rajopadhye, \u201cSynthesizing systolic arrays with control signals from recurrence equations\u201d, Distributed Computing, vol. 2, pp. 88\u2013105, 1989.","journal-title":"Distributed Computing"},{"key":"4_CR46","series-title":"Lecture Notes in Computer Science","volume-title":"Systolic array synthesis by static analysis of program dependencies","author":"S.V. Rajopadhye","year":"1987","unstructured":"S.V.Rajopadhye, R.M.Fujimoto, \u201cSystolic array synthesis by static analysis of program dependencies\u201d, Proceedings PARLE \u2014 Parallel Architectures and Languages Europe, Eindhoven, The Netherlands, June 1987, Lecture Notes in Computer Science, Springer-Verlag, no. 258, 1987."},{"key":"4_CR47","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/0167-9260(90)90017-U","volume":"9","author":"S.V. Rajopadhye","year":"1989","unstructured":"S.V.Rajopadhye, and R.M.Fujimoto, \u201cAutomating systolic array design\u201d, Integration \u2014 The VLSI Journal, vol. 9, pp. 225\u2013242, 1989.","journal-title":"Integration \u2014 The VLSI Journal"},{"issue":"no.2","key":"4_CR48","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0167-8191(90)90105-I","volume":"14","author":"S.V. Rajopadhye","year":"1990","unstructured":"S.V.Rajopadhye, R.M.Fujimoto, \u201cSynthesizing systolic arrays from recurrence equations\u201d, Parallel Computing, vol. 14, no. 2, pp. 163\u2013189, 1990.","journal-title":"Parallel Computing"},{"key":"4_CR49","unstructured":"S.K.Rao, Regular iterative algorithms and their Implementation on processor arrays. PhD Thesis, Stanford University, 1985."},{"key":"4_CR50","doi-asserted-by":"crossref","unstructured":"L.Rapanotti, G.M.Megson, \u201cUniformisation techniques for integral recurrence equations\u201d, The University of Newcastle upon Tyne, Computing Science, Technical Report Series, no. 478, 1994.","DOI":"10.1016\/B978-044482106-5\/50025-9"},{"key":"4_CR51","unstructured":"L. Rapanotti, G.M.Megson, \u201cPre-processing in SADE: Stage III\u201d, The University of Newcastle upon Tyne, Computing Science, Technical Report Series, no. 471, 1994"},{"key":"4_CR52","unstructured":"A.Schrijver, Theory of linear and integer programming. Wiley-Interscience Series in Discrete Mathematics and Optimization, 1986."},{"issue":"no.6","key":"4_CR53","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1109\/12.90251","volume":"40","author":"W. Shang","year":"1991","unstructured":"W.Shang, J.A.B.Fortes, \u201cTime optimal linear schedules for algorithms with uniform dependencies\u201d, IEEE Transactions on Computers, vol. 40, no. 6, pp. 723\u2013742, 1991.","journal-title":"IEEE Transactions on Computers"},{"issue":"no.3","key":"4_CR54","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1109\/71.139208","volume":"3","author":"W. Shang","year":"1992","unstructured":"W.Shang, J.A.B.Fortes, \u201cOn time mapping of uniform dependence algorithms into lower dimensional processor arrays\u201d, IEEE Transactions on Parallel and Distributed Systems, vol. 3, no. 3, pp. 350\u2013363, 1992.","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"issue":"no.2","key":"4_CR55","first-page":"190","volume":"41","author":"W. Shang","year":"1992","unstructured":"W.Shang, J.A.B.Fortes, \u201cIndependent partitioning of algorithms with uniform dependencies\u201d, IEEE Transactions on Parallel and Distributed Systems, vol. 41, no. 2, pp. 190\u2013206, 1992.","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"issue":"no.1\/2","key":"4_CR56","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/BF00927836","volume":"3","author":"J. Teich","year":"1991","unstructured":"J.Teich, L.Thiele, \u201cControl generation in the design of processor arrays\u201d, Journal of VLSI Signal Processing, vol. 3, no. 1\/2, pp. 77\u201392, 1991.","journal-title":"Journal of VLSI Signal Processing"},{"key":"4_CR57","doi-asserted-by":"crossref","unstructured":"Y.Wong, J.M.Delosme, \u201cBroadcasts removal in systolic algorithms\u201d, Proceedings International Conference on Systolic Arrays, 1988.","DOI":"10.1109\/ARRAYS.1988.18080"},{"issue":"no.2","key":"4_CR58","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0743-7315(92)90111-Y","volume":"14","author":"Y. Wong","year":"1992","unstructured":"Y. Wong, J.M.Delosme, \u201cTransformation of broadcasts into propagations in systolic algorithms\u201d, Journal of Parallel and Distributed Computing, vol. 14, no. 2, pp. 121\u2013145, 1992.","journal-title":"Journal of Parallel and Distributed Computing"},{"issue":"no.2","key":"4_CR59","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1109\/12.123393","volume":"41","author":"Y. Wong","year":"1992","unstructured":"Y.Wong, J.M.Delosme, \u201cOptimisation 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"},{"key":"4_CR60","unstructured":"J.Xue, The formal synthesis of control signals for systolic arrays. The University of Edinburgh, PhD Thesis, CTS-90-92, April 1992."},{"issue":"no.5","key":"4_CR61","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1016\/0167-8191(94)90002-7","volume":"20","author":"J. Xue","year":"1994","unstructured":"J.Xue, \u201cAutomating non-unimodular transformations of loop nests\u201d, Parallel Computing, vol. 20, no. 5, pp. 711\u2013728, 1994.","journal-title":"Parallel Computing"}],"container-title":["Lecture Notes in Computer Science","Solving Combinatorial Optimization Problems in Parallel"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0027118","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T19:15:36Z","timestamp":1736104536000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0027118"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540610434","9783540498759"],"references-count":61,"URL":"https:\/\/doi.org\/10.1007\/bfb0027118","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}