{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,24]],"date-time":"2025-09-24T08:47:01Z","timestamp":1758703621786},"reference-count":42,"publisher":"Wiley","issue":"6","license":[{"start":{"date-parts":[[2006,10,30]],"date-time":"2006-10-30T00:00:00Z","timestamp":1162166400000},"content-version":"vor","delay-in-days":4169,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Softw Pract Exp"],"published-print":{"date-parts":[[1995,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In many scientific applications, arrays containing data are indirectly indexed through indirection arrays. Such scientific applications are called irregular programs and are a distinct class of applications that require special techniques for parallelization.<\/jats:p><jats:p>This paper presents a library called CHAOS, which helps users implement irregular programs on distributed\u2010memory message\u2010passing machines, such as the Paragon, Delta, CM\u20105 and SP\u20101. The CHAOS library provides efficient runtime primitives for distributing data and computation over processors; it supports efficient index translation mechanisms and provides users high\u2010level mechanisms for optimizing communication. CHAOS subsumes the previous PARTI library and supports a larger class of applications. In particular, it provides efficient support for parallelization of adaptive irregular programs where indirection arrays are modified during the course of computation. To demonstrate the efficacy of CHAOS, two challenging real\u2010life adaptive applications were parallelized using CHAOS primitives: a molecular dynamics code, CHARMM, and a particle\u2010in\u2010cell code, DSMC.<\/jats:p><jats:p>Besides providing runtime support to users, CHAOS can also be used by compilers to automatically parallelize irregular applications. This paper demonstrates how CHAOS can be effectively used in such a framework. By embedding CHAOS primitives in the Syracuse Fortran 90D\/HPF compiler, kernels taken from the CHARMM and DSMC codes have been automatically parallelized.<\/jats:p>","DOI":"10.1002\/spe.4380250603","type":"journal-article","created":{"date-parts":[[2006,11,17]],"date-time":"2006-11-17T18:04:20Z","timestamp":1163786660000},"page":"597-621","source":"Crossref","is-referenced-by-count":47,"title":["Runtime and language support for compiling adaptive irregular programs on distributed\u2010memory machines"],"prefix":"10.1002","volume":"25","author":[{"given":"Yuan\u2010Shin","family":"Hwang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bongki","family":"Moon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shamik D.","family":"Sharma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ravi","family":"Ponnusamy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raja","family":"Das","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joel H.","family":"Saltz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,30]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"Fortran D language specification","author":"Fox G.","year":"1990"},{"key":"e_1_2_1_3_2","unstructured":"D. Loveman (Ed.) \u2018Draft high performance Fortran language specification version 1.0\u2019 Technical Report CRPC\u2010TR92225 Center for Research on Parallel Computation Rice University (January1993)."},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1155\/1992\/258136"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1994.1039"},{"key":"e_1_2_1_6_2","unstructured":"R.V. Hanxleden K.KennedyandJ.Saltz \u2018Value\u2010based distributions in fortran d \u2010 a preliminary report\u2019 Technical Report CRPC\u2010TR93365\u2010S Center for Research on Parallel Computation Rice University (December1993). To appear in Journal of Programming Languages \u2010 Special Issue on Compiling and Run\u2010Time Issues for Distributed Address Space Machines."},{"key":"e_1_2_1_7_2","unstructured":"RaviPonnusamy JoelSaltz AlokChoudhary Yuan\u2010ShinHwangandGeoffreyFox \u2018Runtime support and compilation methods for user\u2010specified irregular data distributions\u2019 Technical Report CS\u2010TR\u20103194 and UMIACS\u2010TR\u201093\u2010135 University of Maryland Department of Computer Science and UMIACS (November1993). To appear in IEEE Transactions on Parallel and Distributed Systems."},{"key":"e_1_2_1_8_2","doi-asserted-by":"crossref","unstructured":"R.Mirchandaney J. H.Saltz R. M.Smith D. M.NicolandKayCrowley \u2018Principles of runtime support for parallel processors\u2019 Proceedings of the 1988 ACM International Conference on Supercomputing July1988 pp.140\u2013152.","DOI":"10.1145\/55364.55378"},{"key":"e_1_2_1_9_2","doi-asserted-by":"crossref","unstructured":"D. J.Mavriplis \u2018Three dimensional unstructured multigrid for the Euler equations paper 91\u20131549cp\u2019 AIAA 10th Computational Fluid Dynamics Conference June1991.","DOI":"10.2514\/6.1991-1549"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1002\/jcc.540040211"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1002\/jcc.540020311"},{"key":"e_1_2_1_12_2","unstructured":"W. F.Van GunsterenandH. J. C.Berendsen \u2018Gromos: Groningen molecular simulation software\u2019 Technical Report Laboratory of Physical Chemistry University of Groningen Nijenborgh The Netherlands (1988)."},{"key":"e_1_2_1_13_2","unstructured":"P.Venkatkrishnan J.SaltzandD.Mavriplis \u2018Parallel preconditioned iterative methods for the compressible navier stokes equations\u2019 12th International Conference on Numerical Methods in Fluid Dynamics Oxford England July1990."},{"key":"e_1_2_1_14_2","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198561958.001.0001","volume-title":"Molecular Gas Dynamics and the Direct Simulation of Gas Flows","author":"Bird Graeme A.","year":"1994"},{"key":"e_1_2_1_15_2","unstructured":"J.Saltzet al. \u2018A manual for the CHAOS runtime library\u2019 Technical Report University of Maryland (1993)."},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.4330030607"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.2514\/3.263"},{"key":"e_1_2_1_18_2","unstructured":"RaviPonnusamy Yuan\u2010ShinHwang JoelSaltz AlokChoudharyandGeoffreyFox \u2018Supporting irregular distributions in FORTRAN 90D\/HPF compilers\u2019 Technical Report CS\u2010TR\u20103268 and UMIACS\u2010TR\u201094\u201057 University of Maryland Department of Computer Science and UMIACS (May 1994). To appear in IEEE Parallel and Distributed Technology Spring1995."},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1994.1104"},{"issue":"5","key":"e_1_2_1_20_2","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1109\/TC.1987.1676942","article-title":"A partitioning strategy for nonuniform problems on multiprocessors","volume":"36","author":"Berger M. J.","year":"1987","journal-title":"IEEE Trans. on Computers"},{"key":"e_1_2_1_21_2","unstructured":"B.Nour\u2010Omid A.RaefskyandG.Lyzenga \u2018Solving finite element equations on concurrent computers\u2019 Proc. of Symposium on Parallel Computations and theis Impact on Mechanics Boston December1987."},{"key":"e_1_2_1_22_2","first-page":"16","article-title":"Parallelization of charmm for mimd machines","volume":"7","author":"Brooks B. R.","year":"1992","journal-title":"Chemical Design Automation News"},{"key":"e_1_2_1_23_2","doi-asserted-by":"crossref","unstructured":"D. F. G.RaultandM. S.Woronowicz \u2018Spacecraft contamination investigation by direct simulation Monte Carlo \u2010 contamination on UARS\/HALOE\u2019 Proceedings AIAA 31th Aerospace Sciences Meeting and Exhibit Reno Nevada January1993.","DOI":"10.2514\/6.1993-724"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.75137"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.76406"},{"key":"e_1_2_1_26_2","doi-asserted-by":"crossref","unstructured":"F.Bodin P.Beckman D.Gannon S.NarayanaandS.Yang \u2018Distributed pC++: Basic ideas for an object parallel languages\u2019 Report Indiana University (January1993).","DOI":"10.1155\/1993\/158246"},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/0611030"},{"key":"e_1_2_1_28_2","unstructured":"R. D.WilliamsandR.Glowinski \u2018Distributed irregular finite elements\u2019 Technical Report C3P 715 Caltech Concurrent Computation Program (February1989)."},{"key":"e_1_2_1_29_2","doi-asserted-by":"publisher","DOI":"10.2514\/3.12012"},{"key":"e_1_2_1_30_2","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.4330030502"},{"key":"e_1_2_1_31_2","unstructured":"N.Mansour \u2018Physical optimization algorithms for mapping data to distributed\u2010memory multiprocessors\u2019 Technical Report Ph. D. Dissertation School of Computer Science Syracuse University (1992)."},{"key":"e_1_2_1_32_2","doi-asserted-by":"crossref","unstructured":"W. E.Leland \u2018Load\u2010balancing heuristics and process behavior\u2019 Proceedings of Performance 86 and ACM SIGMETRICS 86 1986 pp.54\u201369.","DOI":"10.1145\/317499.317539"},{"key":"e_1_2_1_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(91)90078-N"},{"key":"e_1_2_1_34_2","unstructured":"V.Venkatakrishnan H. D.SimonandT. J.Barth \u2018A MIMD implementation of a parallel Euler solver for unstructured grids submitted to Journal of Supercomputing\u2019 Report RNR\u201091\u2010024 NAS Systems Division NASA Ames Research Center (September1991)."},{"key":"e_1_2_1_35_2","doi-asserted-by":"crossref","unstructured":"A.Vidwans Y.KallinderisandV.Venkatakrishnan \u2018A new parallel dynamic load balancing algorithm for 3d adaptive unstructured grids\u2019 Proceedings of the 11th AIAA CFD Conference Orlando FL July1993.","DOI":"10.2514\/6.1993-3313"},{"issue":"1","key":"e_1_2_1_36_2","article-title":"Programming abstractions for dynamically partitioning and coordinating localized scientific calculations running on multiprocessors","volume":"12","author":"Baden S.","year":"1991","journal-title":"SIAM J. Sci. and Stat. Computation."},{"key":"e_1_2_1_37_2","volume-title":"Third ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming","author":"Lam M.","year":"1991"},{"key":"e_1_2_1_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(91)90107-K"},{"key":"e_1_2_1_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/173284.155350"},{"key":"e_1_2_1_40_2","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/B978-0-444-88712-2.50012-3","volume-title":"Languages, Compilers and Run\u2010time Environments for Distributed Memory Machines","author":"Hiranandani S.","year":"1992"},{"key":"e_1_2_1_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/99163.99183"},{"key":"e_1_2_1_42_2","unstructured":"L. C.LuandM. C.Chen \u2018Parallelizing loops with indirect array references or pointers\u2019 Proceedings of the Fourth Workshop on Languages and Compilers for Parallel Computing Santa Clara CA August1991."},{"key":"e_1_2_1_43_2","unstructured":"J.Wu J.Saltz S.HiranandaniandH.Berryman \u2018Runtime compilation methods for multicomputers\u2019 Proceedings of the 1991 International Conference on Parallel Processing Volume 2 1991 pp.26\u201330."}],"container-title":["Software: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fspe.4380250603","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/spe.4380250603","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,8]],"date-time":"2024-02-08T10:07:42Z","timestamp":1707386862000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/spe.4380250603"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,6]]},"references-count":42,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1995,6]]}},"alternative-id":["10.1002\/spe.4380250603"],"URL":"https:\/\/doi.org\/10.1002\/spe.4380250603","archive":["Portico"],"relation":{},"ISSN":["0038-0644","1097-024X"],"issn-type":[{"value":"0038-0644","type":"print"},{"value":"1097-024X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,6]]}}}