{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T14:22:15Z","timestamp":1774880535057,"version":"3.50.1"},"reference-count":26,"publisher":"Wiley","issue":"5","license":[{"start":{"date-parts":[[2006,10,25]],"date-time":"2006-10-25T00:00:00Z","timestamp":1161734400000},"content-version":"vor","delay-in-days":4103,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Concurrency: Pract. Exper."],"published-print":{"date-parts":[[1995,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The paper presents a generic technique for mapping parallel algorithms onto parallel architectures. The proposed technique is a fast recursive mapping algorithm which is a component of the Cluster\u2010M programming tool. The other components of Cluster\u2010M are the Specification module and the Representation module. In the Specification module, for a given task specified by a high\u2010level machine\u2010independent program, a clustered task graph called Spec graph is generated. In the Representation module, for a given architecture or computing organization, a clustered system graph called Rep graph is generated. Given a task (or system) graph, a Spec (or Rep) graph can be generated using one of the clustering algorithms presented in the paper. The clustering is done only once for a given task graph (system graph) independent of any system graphs (task graphs). It is a machine\u2010independent (application\u2010independent) clustering, and therefore it is not repeated for different mappings. The Cluster\u2010M mapping algorithm presented produces a sub\u2010optimal matching of a given Spec graph containing M task modules, onto a Rep graph of N processors, in O(MN) time. This generic algorithm is suitable for both the allocation problem and the scheduling problem. Its performance is compared to other leading techniques. We show that Cluster\u2010M produces better or similar results in significantly less time and using fewer or an equal number of processors as compared to the other known methods.<\/jats:p>","DOI":"10.1002\/cpe.4330070505","type":"journal-article","created":{"date-parts":[[2006,11,17]],"date-time":"2006-11-17T15:11:37Z","timestamp":1163776297000},"page":"391-409","source":"Crossref","is-referenced-by-count":5,"title":["A fast recursive mapping algorithm"],"prefix":"10.1002","volume":"7","author":[{"given":"Song","family":"Chen","sequence":"first","affiliation":[]},{"given":"Mary M.","family":"Eshaghian","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,25]]},"reference":[{"issue":"2","key":"e_1_2_1_2_2","first-page":"42","article-title":"A taxonomy of scheduling in general\u2010purpose distributed computing systems","volume":"14","author":"Casavant T. L.","year":"1988","journal-title":"IEEE Trans."},{"key":"e_1_2_1_3_2","volume-title":"Task Scheduling in Parallel and Distributed Systems","author":"El\u2010Rewini H.","year":"1994"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288685"},{"issue":"1","key":"e_1_2_1_5_2","first-page":"85","article-title":"Multiprocessor scheduling with the aid of network flow algorithms","volume":"3","author":"Stone H. S.","year":"1977","journal-title":"IEEE Trans."},{"issue":"1","key":"e_1_2_1_6_2","first-page":"48","article-title":"Partitioning problem in parallel, pipelined, and distributed computing","volume":"37","author":"Bokhari S. H.","year":"1988","journal-title":"IEEE Trans."},{"issue":"6","key":"e_1_2_1_7_2","first-page":"583","article-title":"A shortest tree algorithm for optimal assignments across space and time in a distributed processor system","volume":"7","author":"Bokhari S. H.","year":"1981","journal-title":"IEEE Trans."},{"issue":"11","key":"e_1_2_1_8_2","article-title":"Allocating modules to processors in a distributed systems","volume":"15","author":"Fernandez\u2010Baca D.","year":"1989","journal-title":"IEEE Trans."},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/66451.66454"},{"key":"e_1_2_1_10_2","volume-title":"Partitioning and Scheduling Parallel Programs for Execution on Multiprocessors","author":"Sarkar V.","year":"1989"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(90)90004-9"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/71.80160"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(92)90012-C"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/71.308533"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1981.1675756"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1985.1676563"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1987.1676925"},{"issue":"11","key":"e_1_2_1_18_2","first-page":"1384","article-title":"Heuristic algorithms for task assignment in distributed systems","volume":"37","author":"Lo V. M.","year":"1988","journal-title":"IEEE Trans."},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(90)90042-N"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/71.210815"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(87)90018-9"},{"key":"e_1_2_1_22_2","unstructured":"S. J.KimandJ. C.Browne \u2018A general approach to mapping of parallel computation upon multiprocessor architectures\u2019 inProc. International Conference on Parallel Processing Vol. 3 1988 pp.1\u20138."},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0129053394000147"},{"key":"e_1_2_1_24_2","unstructured":"S.Chen M. M.EshaghianandY.Wu \u2018Mapping arbitrary non\u2010uniform task graphs onto arbitrary non\u2010uniform system graphs \u2019 inProc. International Conference on Parallel Processing August1995."},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(90)90115-P"},{"key":"e_1_2_1_26_2","unstructured":"V. M.Lo S.Rajopadhye S.Gupta D.Keldsen M. A.MohamedandJ. A.Telle \u2018Oregami: Software tools for mapping parallel computations to parallel architectures\u2019 inProc. International Conference on Parallel Processing 1990."},{"key":"e_1_2_1_27_2","doi-asserted-by":"crossref","unstructured":"R.Ponnusamy N.Mansour A.ChoudharyandG. C.Fox \u2018Mapping realistic data sets on parallel computers\u2019 inProc. 7th International Parallel Processing Symposium April1993 pp.123\u2013128.","DOI":"10.1109\/IPPS.1993.262867"}],"container-title":["Concurrency: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fcpe.4330070505","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/cpe.4330070505","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,11]],"date-time":"2025-01-11T23:50:24Z","timestamp":1736639424000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/cpe.4330070505"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,8]]},"references-count":26,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1995,8]]}},"alternative-id":["10.1002\/cpe.4330070505"],"URL":"https:\/\/doi.org\/10.1002\/cpe.4330070505","archive":["Portico"],"relation":{},"ISSN":["1040-3108","1096-9128"],"issn-type":[{"value":"1040-3108","type":"print"},{"value":"1096-9128","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,8]]}}}