{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T07:46:32Z","timestamp":1759131992967,"version":"3.32.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[1995,11,1]],"date-time":"1995-11-01T00:00:00Z","timestamp":815184000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Form. Asp. Comput."],"published-print":{"date-parts":[[1995,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>An SPMD parallel implementation schema for divide-and-conquer specifications is proposed and derived by formal refinement (transformation) of the specification schema. The specification is in the form of a mutually recursive functional definition. In a first phase, a parallel functional program schema is constructed which consists of a communication tree and a functional program that is shared by all nodes of the tree. The fact that this phase proceeds by semantics-preserving transformations in the Bird-Meertens formalism of higher-order functions guarantees the correctness of the resulting functional implementation. A second phase yields an imperative distributed message-passing implementation of this schema. The derivation process is illustrated with an example: a two-dimensional numerical integration algorithm.<\/jats:p>","DOI":"10.1007\/bf01211000","type":"journal-article","created":{"date-parts":[[2005,2,25]],"date-time":"2005-02-25T12:43:49Z","timestamp":1109335429000},"page":"663-682","source":"Crossref","is-referenced-by-count":13,"title":["Parallelization of divide-and-conquer in the Bird-Meertens formalism"],"prefix":"10.1145","volume":"7","author":[{"given":"Sergei","family":"Gorlatch","sequence":"first","affiliation":[{"name":"Fakult\u00e4t f\u00fcr Mathematik und Informatik, Universit\u00e4t Passau, D-94030, Passau, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Lengauer","sequence":"additional","affiliation":[{"name":"Fakult\u00e4t f\u00fcr Mathematik und Informatik, Universit\u00e4t Passau, D-94030, Passau, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","reference":[{"key":"e_1_2_1_2_1_2","doi-asserted-by":"publisher","DOI":"10.1137\/0218035"},{"key":"e_1_2_1_2_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0096-0551(93)90036-Z"},{"key":"e_1_2_1_2_3_2","unstructured":"Axford T.: The divide-and-conquer paradigm as a basis for parallel language design. In L. Kronsjo and D. Shumsheruddin editors Advances in Parallel Algorithms. Chapter 2 . Blackwell 1992."},{"key":"e_1_2_1_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/359576.359579"},{"key":"e_1_2_1_2_5_2","doi-asserted-by":"crossref","unstructured":"Bird R. S.: Lectures on constructive functional programming. In M. Broy editor Constructive Methods in Computing Science NATO ASO Series F: Computer and Systems Sciences. Vol. 55 pages 151\u2013216. Springer Verlag 1988.","DOI":"10.1007\/978-3-642-74884-4_5"},{"key":"e_1_2_1_2_6_2","doi-asserted-by":"crossref","unstructured":"Cox S. Huang S. Kelly P. Liu J. and Taylor F.: An implementation of static functional process networks. In D. Etiemble and J.-C. Syre editors PARLE'92 Parallel Architecture and Languages Europe Lecture Notes in Computer Science 605 pages 497\u2013512 1992.","DOI":"10.1007\/3-540-55599-4_107"},{"key":"e_1_2_1_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/122616.122620"},{"key":"e_1_2_1_2_8_2","unstructured":"Cole M.: Algorithmic skeletons: A structured approach to the management of parallel computation. Ph.D. Thesis. Technical Report CST-56-88 Department of Computer Science University of Edinburgh 1988."},{"key":"e_1_2_1_2_9_2","unstructured":"Cole M.: Parallel programming list homomorphisms and the maximum sum problem. Technical Report CSR-25-93 Department of Computer Science University of Edinburgh May 1993."},{"key":"e_1_2_1_2_10_2","doi-asserted-by":"crossref","unstructured":"Darlington J. Field A. Harrison P. Kelly P. Sharp D. Wu Q. and While R.: Parallel programming using skeleton functions. In A. Bode M. Reeve and G. Wolf editors PARLE '93 Parallel Architectures and Languages Europe Lecture Notes in Computer Science 694 pages 146\u2013160. 1993.","DOI":"10.1007\/3-540-56891-3_12"},{"key":"e_1_2_1_2_11_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/36.3.254"},{"key":"e_1_2_1_2_12_2","doi-asserted-by":"crossref","unstructured":"Dijkstra E. W. and Scholten C. S.: Predicate Calculus and Program Semantics . Texts and Monographs in Computer Science. Springer-Verlag 1990.","DOI":"10.1007\/978-1-4612-3228-5"},{"key":"e_1_2_1_2_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(91)90022-P"},{"key":"e_1_2_1_2_14_2","unstructured":"Feldcamp D. Sreekantaswamy H. Wagner A. and Chanson S.: Towards a skeleton-based parallel programming environment. In A. Veronis and Y. Parker editors Transputer Research and Applications pages 104\u2013115. IOS Press 1992."},{"key":"e_1_2_1_2_15_2","doi-asserted-by":"crossref","unstructured":"Gorlatch S. and Lengauer C.: Systematic development of an SPMD implementation schema for mutually recursive divide-and-conquer specifications. In H. J. Siegel editor Proc. Eighth Int. Paral. Proc. Symp. (IPPS'94) pages 368\u2013375. IEEE Computer Society Press 1994.","DOI":"10.1109\/IPPS.1994.288275"},{"key":"e_1_2_1_2_16_2","doi-asserted-by":"crossref","unstructured":"Gorlatch S.: Parallel program development for a recursive numerical algorithm: A case study. Technical Report SFB 342\/7\/92 Institut f\u00fcr Informatik TU M\u00fcnchen March 1992.","DOI":"10.1007\/3-540-55599-4_134"},{"key":"e_1_2_1_2_17_2","unstructured":"Gorlatch S.: Formal derivation and implementation of divide-and-conquer on a transputer network. In A. De Gloria M. Jane and D. Marini editors Transputer Applications and System '94 pages 763\u2013776. IOS Press 1994."},{"key":"e_1_2_1_2_18_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/35.6.555"},{"key":"e_1_2_1_2_19_2","doi-asserted-by":"publisher","DOI":"10.5555\/21545.21553"},{"key":"e_1_2_1_2_20_2","unstructured":"Jones G. and Gibbons J.: Linear-time breadth-first tree algorithms: An exercise in the arithmetic of folds and zips. Technical Report TR-31-92 Oxford University Computing Laboratory 1992."},{"key":"e_1_2_1_2_21_2","doi-asserted-by":"crossref","unstructured":"Lengauer C.: Loop parallelization in the polytope model. In E. Best editor CONCUR '93 Lecture Notes in Computer Science 715 pages 398\u2013416. Springer-Verlag 1993.","DOI":"10.1007\/3-540-57208-2_28"},{"key":"e_1_2_1_2_22_2","doi-asserted-by":"crossref","unstructured":"Lengauer C. and Huang C.-H.: A mechanically certified theorem about optimal concurrency of sorting networks. In Proc. 13th Ann. ACM Symp. on Principles of Programming Languages (POPL) pages 307\u2013317 1986.","DOI":"10.1145\/512644.512673"},{"key":"e_1_2_1_2_23_2","unstructured":"Mou Z. G. Constantinescu C. and Hickey T. J.: Divide-and-conquer on three-dimensional meshes. In W. Joosen and E. Milgrom editors Parallel Computing: From Theory to Sound Practice pages 344\u2013355. IOS Press 1992."},{"key":"e_1_2_1_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00129780"},{"key":"e_1_2_1_2_25_2","doi-asserted-by":"crossref","unstructured":"McBurney D. and Sleep M.: Transputer-based experiments with the ZAPP architecture. In J. de Bakker A. Nijman and P. Treleaven editors PARLE Parallel Architectures and Languages Europe Lecture Notes In Computer Science 258 pages 242\u2013259. 1987.","DOI":"10.1007\/3-540-17943-7_132"},{"key":"e_1_2_1_2_26_2","unstructured":"Nation W. G. Saghi G. and Siegel H. J.: Properties of inteconnection networks for large-scale parallel processing systems. In P. Tvrd\u00edk editor ISIPCALA'93 pages 51\u201379 1993."},{"key":"e_1_2_1_2_27_2","doi-asserted-by":"crossref","unstructured":"Pepper P.: Deductive derivation of parallel programs. In R. Paige J. Reif and R. Wachter editors Parallel Algorithm Derivation and Program Transformation pages 1\u201353. Kluwer Academic Publishers 1993.","DOI":"10.1007\/978-0-585-27330-3_1"},{"key":"e_1_2_1_2_28_2","doi-asserted-by":"crossref","unstructured":"Swiestra D. and de Moor O.: Virtual data structures. In B. Moeller H. Partsch and S. Schuman editors Formal Program Development Lecture Notes in Computer Science 755 pages 355\u2013371.","DOI":"10.1007\/3-540-57499-9_26"},{"key":"e_1_2_1_2_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/2.62092"},{"key":"e_1_2_1_2_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(93)90014-G"},{"key":"e_1_2_1_2_31_2","doi-asserted-by":"crossref","unstructured":"Smith D. and Lowry M.: Algorithm theories and design tactics. In J. L. A. van de Snepscheut editor Mathematics of Program Construction Lecture Notes in Computer Science 375 pages 379\u2013398 1989.","DOI":"10.1007\/3-540-51305-1_23"},{"key":"e_1_2_1_2_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(87)90010-4"},{"key":"e_1_2_1_2_33_2","unstructured":"Wagner A. Sreekantaswamy H. and Chanson S.: Performance issues in the design of a processor farm template. In R. Grebe et al. editors Transputer Applications and Systems. Vol. 1 pages 438\u2013450. IOS Press 1993."},{"key":"e_1_2_1_2_34_2","unstructured":"Zenger C.: Sparse grids. Technical Report SFB-Nr. 342\/18\/90 A Institut f\u00fcr Informatik TU M\u00fcnchen October 1990."}],"container-title":["Formal Aspects of Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01211000.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01211000\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1007\/BF01211000","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T22:18:12Z","timestamp":1734992292000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1007\/BF01211000"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,11]]},"references-count":34,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1995,11]]}},"alternative-id":["10.1007\/BF01211000"],"URL":"https:\/\/doi.org\/10.1007\/bf01211000","relation":{},"ISSN":["0934-5043","1433-299X"],"issn-type":[{"type":"print","value":"0934-5043"},{"type":"electronic","value":"1433-299X"}],"subject":[],"published":{"date-parts":[[1995,11]]}}}