{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,20]],"date-time":"2025-10-20T17:34:14Z","timestamp":1760981654831},"reference-count":29,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2006,10,20]],"date-time":"2006-10-20T00:00:00Z","timestamp":1161302400000},"content-version":"vor","delay-in-days":5802,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Concurrency: Pract. Exper."],"published-print":{"date-parts":[[1990,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present a fully distributed dynamic load balancing algorithm for parallel MIMD architectures. The algorithm can be described as a system of identical parallel processes, each running on a processor of an arbitrary interconnected network of processors. We show that the algorithm can be interpreted as a Poisson (heath) equation in a graph. This equation is analysed using Markov chain techniques and is proved to converge in polynomial time resulting in a global load balance. We also discuss some important parallel architectures and interconnection schemes such as linear processor arrays, tori, hypercubes, etc. Finally we present two applications where the algorithm has been successfully embedded (process mapping and molecular dynamic simulation).<\/jats:p>","DOI":"10.1002\/cpe.4330020403","type":"journal-article","created":{"date-parts":[[2006,11,18]],"date-time":"2006-11-18T06:18:15Z","timestamp":1163830695000},"page":"289-313","source":"Crossref","is-referenced-by-count":142,"title":["Load balancing and Poisson equation in a graph"],"prefix":"10.1002","volume":"2","author":[{"given":"J. E.","family":"Boillat","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,20]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"Parallel Computers 2","author":"Hockney R. W.","year":"1988"},{"key":"e_1_2_1_3_2","volume-title":"ESPRIT 86: Results and Achievments, Directorate General","author":"Harp J. G.","year":"1987"},{"key":"e_1_2_1_4_2","first-page":"457","volume-title":"CONPAR 90\u2014VAPP IV Proceedings","author":"Boillat J. E.","year":"1990"},{"key":"e_1_2_1_5_2","volume-title":"Solving Problems on Concurrent Processors I","author":"Fox G.","year":"1988"},{"key":"e_1_2_1_6_2","volume-title":"Hypercube Multiprocessors","author":"Fox G.","year":"1987"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1986.6312961"},{"key":"e_1_2_1_8_2","unstructured":"J. E.Boillat F.Brug\u00e9andP. G.Kropf. \u2018A dynamic load balancing algorithm for molecular dynamics simulation on multi\u2010processor systems\u2019 (Submitted for publication)."},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1966.5273"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1972.5009071"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.55.601"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF03023823"},{"issue":"100","key":"e_1_2_1_13_2","doi-asserted-by":"crossref","first-page":"619","DOI":"10.21136\/CMJ.1975.101357","article-title":"A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory","volume":"25","author":"Fiedler M.","year":"1975","journal-title":"Czes. Math. J."},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-71243-2"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(72)90011-0"},{"key":"e_1_2_1_16_2","unstructured":"H.Carnal.1989. Private communication."},{"key":"e_1_2_1_17_2","volume-title":"Spectra of Graphs","author":"Cvetkovi\u010d D. M.","year":"1979"},{"key":"e_1_2_1_18_2","volume-title":"Applying Transputer Based Parallel Machines","author":"Baude F.","year":"1989"},{"key":"e_1_2_1_19_2","volume-title":"Mathematica","author":"Wolfram S.","year":"1988"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(89)90021-X"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01048271"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1981.1675756"},{"key":"e_1_2_1_23_2","volume-title":"Assignment Problems in Parallel and Distributed Computing","author":"Bokhari S. H.","year":"1988"},{"issue":"4","key":"e_1_2_1_24_2","volume":"18","author":"May D.","year":"1983","journal-title":"Occam. ACM SIGPLAN Notices"},{"key":"e_1_2_1_25_2","volume-title":"OCCAM 2 Reference Manual","author":"INMOS","year":"1988"},{"key":"e_1_2_1_26_2","volume-title":"Transputer Reference Manual","author":"INMOS","year":"1988"},{"key":"e_1_2_1_27_2","unstructured":"J. E.Boillat P. G.Kropf D. Chr.MeierandA.Wespi. \u2018An analysis and reconfiguration tool for mapping parallel programs onto transputer networks\u2019. In OPPT T. Muntean (ed.) Grenoble 1987."},{"key":"e_1_2_1_28_2","unstructured":"J. E.Boillat P. G.Kropf D.Ch.MeierandA.Wespi.Automatische Multiprozessorkonfiguration. Technical Report IAM\u2010PR\u20108687 University of Bern Informatics 1987."},{"key":"e_1_2_1_29_2","unstructured":"J. E.Boillat P. G.KropfandS.Feller.Automatische Multiprozessorkonfiguration. Technical Report IAM\u2010PR\u20108788 University of Bern Informatics 1987."},{"key":"e_1_2_1_30_2","volume-title":"Tenth International Conference on Application and Theory of Petri Nets","author":"B\u00fctler B.","year":"1989"}],"container-title":["Concurrency: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fcpe.4330020403","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/cpe.4330020403","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,22]],"date-time":"2023-10-22T09:31:42Z","timestamp":1697967102000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/cpe.4330020403"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,12]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1990,12]]}},"alternative-id":["10.1002\/cpe.4330020403"],"URL":"https:\/\/doi.org\/10.1002\/cpe.4330020403","archive":["Portico"],"relation":{},"ISSN":["1040-3108","1096-9128"],"issn-type":[{"value":"1040-3108","type":"print"},{"value":"1096-9128","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,12]]}}}