{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T06:12:04Z","timestamp":1774591924611,"version":"3.50.1"},"reference-count":21,"publisher":"Wiley","issue":"5","license":[{"start":{"date-parts":[[2006,10,27]],"date-time":"2006-10-27T00:00:00Z","timestamp":1161907200000},"content-version":"vor","delay-in-days":5505,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Concurrency: Pract. Exper."],"published-print":{"date-parts":[[1991,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>If a finite element mesh has a sufficiently regular structure, it is easy to decide in advance how to distribute the mesh among the processors of a distributed\u2010memory parallel processor, but if the mesh is unstructured the problem becomes much more difficult. The distribution should be made so that each processor has approximately equal work to do, and such that communication overhead is minimized.<\/jats:p><jats:p>If the mesh is solution\u2010adaptive, i.e. the mesh and hence the load\u2010balancing problem change discretely during execution of the code, then it is most efficient to decide the optimal mesh distribution in parallel. In this paper three parallel algorithms, orthogonal recursive bisection (ORB), eigenvector recursive bisection (ERB) and a simple parallelization of simulated annealing (SA) have been implemented for load balancing a dynamic unstructured triangular mesh on 16 processors of an NCUBE machine.<\/jats:p><jats:p>The test problem is a solution\u2010adaptive Laplace solver, with an initial mesh of 280 elements, refined in seven stages to 5772 elements. We present execution times for the solver resulting from the mesh distributions using the three algorithms, as well as results on imbalance, communication traffic and element migration.<\/jats:p><jats:p>The load\u2010balancing itself is fastest with ORB, but a very long run of SA produces a saving of 21% in the execution time of the Laplace solver. ERB is only a little slower than ORB, and yet produces a mesh distribution whose execution time is 15% faster than ORB.<\/jats:p>","DOI":"10.1002\/cpe.4330030502","type":"journal-article","created":{"date-parts":[[2006,11,17]],"date-time":"2006-11-17T16:20:10Z","timestamp":1163780410000},"page":"457-481","source":"Crossref","is-referenced-by-count":233,"title":["Performance of dynamic load balancing algorithms for unstructured mesh calculations"],"prefix":"10.1002","volume":"3","author":[{"given":"Roy D.","family":"Williams","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,27]]},"reference":[{"key":"e_1_2_1_2_2","unstructured":"N. P.Chriochoides C. E.Houstis E. N.Houstis P. N.Papachiou S. K.KortesisandJ. R.Rice Domain Decomposer: A Software Tool for Mapping PDE Computations to Parallel Architectures Perdue University Computer Science Department CSD\u2010TR\u20101025 (unpublished)."},{"key":"e_1_2_1_3_2","unstructured":"R. D.Williams DIME: A User's Manual Caltech Concurrent Computation Report C3P 861 Feb.1990."},{"key":"e_1_2_1_4_2","volume-title":"Solving Problems on Concurrent Processors","author":"Fox G. C.","year":"1988"},{"key":"e_1_2_1_5_2","volume-title":"Numerical Algorithms for Modern Parallel Computers","author":"Fox G. C.","year":"1988"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.220.4598.671"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-1627-5"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.13.2.311"},{"key":"e_1_2_1_9_2","doi-asserted-by":"crossref","unstructured":"F.BaiardiandS.Orlando \u2018Strategies for a massively parallel implementation of simulated annealing\u2019 Springer\u2010Verlag Lecture Notes in Comp. Sci. 366 273(1989).","DOI":"10.1007\/3-540-51285-3_46"},{"key":"e_1_2_1_10_2","volume-title":"Parallel Computing 90","author":"Braschi B.","year":"1990"},{"key":"e_1_2_1_11_2","unstructured":"R. D.Williams Minimization by Simulated Annealing: Is Detailed Balance Necessary? Caltech Concurrent Computation Project Report C3P 354 Sep.1986."},{"key":"e_1_2_1_12_2","unstructured":"F.BarajasandR. D.Williams Optimization with a Distributed\u2010Memory Parallel Processor Caltech Concurrent Computation Project Report C3P 465 Sep.1987."},{"key":"e_1_2_1_13_2","unstructured":"M. A.Johnson Concurrent Computation and its Application to the Study of Melting in Two Dimensions Caltech PhD thesis (1986); also Caltech Concurrent Computation Report C3P 268; see also Chap. 17 in Reference 3."},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.54.235"},{"key":"e_1_2_1_15_2","unstructured":"P. D.CoddingtonandC. F.Baillie Cluster Algorithms for Spin Models on MIMD Parallel Computers Proc. 5th Distrib. Mem. Comput. Conf. (ed.) D. W. Walker Charleston SC 1990."},{"key":"e_1_2_1_16_2","unstructured":"A.Pothen H. D.SimonandK. P.Liu Partitioning Sparse Matrices with Eigenvectors of Graphs Report RNR\u201089\u2010009 NASA Ames Research Center July1989."},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/0603056"},{"key":"e_1_2_1_18_2","doi-asserted-by":"crossref","unstructured":"R. B.Boppana Eigenvalues and Graph Bisection: an Average Case Analysis in 28th Annual Symp. Found. Comp. Sci 1987.","DOI":"10.1109\/SFCS.1987.22"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.21136\/CMJ.1973.101168"},{"key":"e_1_2_1_19_3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01591018"},{"key":"e_1_2_1_20_2","volume-title":"Matrix Computations","author":"Golub G. H.","year":"1983"},{"key":"e_1_2_1_21_2","volume-title":"The Symmetric Eigenvalue Problem","author":"Parlett B.","year":"1980"}],"container-title":["Concurrency: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fcpe.4330030502","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/cpe.4330030502","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,23]],"date-time":"2023-10-23T08:00:52Z","timestamp":1698048052000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/cpe.4330030502"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,10]]},"references-count":21,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1991,10]]}},"alternative-id":["10.1002\/cpe.4330030502"],"URL":"https:\/\/doi.org\/10.1002\/cpe.4330030502","archive":["Portico"],"relation":{},"ISSN":["1040-3108","1096-9128"],"issn-type":[{"value":"1040-3108","type":"print"},{"value":"1096-9128","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,10]]}}}