{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,12]],"date-time":"2025-01-12T00:40:11Z","timestamp":1736642411497,"version":"3.32.0"},"reference-count":27,"publisher":"Wiley","issue":"7","license":[{"start":{"date-parts":[[2006,10,27]],"date-time":"2006-10-27T00:00:00Z","timestamp":1161907200000},"content-version":"vor","delay-in-days":4044,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Concurrency: Pract. Exper."],"published-print":{"date-parts":[[1995,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>To efficiently execute a finite element program on a 2D torus, we need to map nodes of the corresponding finite element graph to processors of a 2D torus such that each processor has approximately the same amount of computational load and the communication among processors is minimized. If nodes of a finite element graph do not increase during the execution of a program, the mapping only needs to be performed once. However, if a finite element graph is solution\u2010adaptive, that is, nodes of a finite element graph increase discretely due to the refinement of some finite elements during the execution of a program, a dynamic load\u2010balancing algorithm has to be performed many times in order to balance the computational load of processors while keeping the communication cost as low as possible. In the paper we propose a parallel dynamic load\u2010balancing algorithm (LB) to deal with the load\u2010imbalancing problem of a solution\u2010adaptive finite element program on a 2D torus. The algorithm uses an iterative approach to achieve load\u2010balancing. We have implemented the proposed algorithm along with two parallel mapping algorithms, parallel orthogonal recursive bisection (ORB) and parallel recursive mincut bipartitioning (MC), on a simulated 2D torus. Three criteria, the execution time of load\u2010balancing algorithms, the computation time of an application program under different load balancing algorithms, and the total execution time of an application program (under several refinement phases) are used for performance evaluation. Simulation results show that (1) the execution of LB is faster than those of MC and ORB; (2) the mappings of LB are better than those of ORB and MC; and (3) the speedups of LB are better than those of ORB and MC.<\/jats:p>","DOI":"10.1002\/cpe.4330070704","type":"journal-article","created":{"date-parts":[[2006,11,18]],"date-time":"2006-11-18T07:35:46Z","timestamp":1163835346000},"page":"615-631","source":"Crossref","is-referenced-by-count":2,"title":["A parallel dynamic load\u2010balancing algorithm for solution\u2010adaptive finite element meshes on 2D tori"],"prefix":"10.1002","volume":"7","author":[{"given":"Yeh\u2010Ching","family":"Chung","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yaa\u2010Jyun","family":"Yeh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.\u2010S","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,27]]},"reference":[{"volume-title":"Numerical Solution of Partial Differential Equations in Science and Engineering","year":"1983","author":"Lapidus L.","key":"e_1_2_1_2_2"},{"key":"e_1_2_1_3_2","unstructured":"C.Aykanat F.Ozguner S.MartinandS. M.Doraivelu \u2018Parallelization of a finite element application program on a hypercube multiprocessor \u2019Hypercube Multiprocessor 662\u2013673(1987)."},{"issue":"12","key":"e_1_2_1_4_2","first-page":"1554","article-title":"Iterative algorithms for solution of large sparse systems of linear equations on hypercubes","volume":"37","author":"Aykanat C.","year":"1988","journal-title":"IEEE Trans."},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.4330030502"},{"key":"e_1_2_1_6_2","unstructured":"G. C.Foxet al. \u2018A classification of irregular loosely synchronous problems and their support in scalable parallel software systems \u2019 NPAC\u2010SCCS Technical Report Syracuse University April1992."},{"key":"e_1_2_1_7_2","unstructured":"S.HammondandR.Schreiber \u2018Mapping unstructured grid problems to the connection machine \u2019 Technical Report 90.22 RIACS October1990"},{"key":"e_1_2_1_8_2","unstructured":"D. L.Whitaker D. C.SlackandR. W.Walters \u2018Solution algorithms for the two\u2010dimensional Euler equations on unstructured meshes \u2019Proceedings of AIAA 28th Aerospace Science Meeting Reno Nevada January1990"},{"key":"e_1_2_1_9_2","doi-asserted-by":"crossref","unstructured":"D. J.Mavriplis \u2018Three dimensional unstructured multigrid for the Euler equations \u2019Proceedings of AIAA 10th Computational Fluid Dynamics Conference June1991","DOI":"10.2514\/6.1991-1549"},{"key":"e_1_2_1_10_2","doi-asserted-by":"crossref","unstructured":"P. C.Liewer B. A.Zimmerman V. K.Decyk J. M.DawsonandG. C.Fox \u2018A general concurrent algorithm for plasma particle\u2010in\u2010cell simulations \u2019Technical Report C3P\u2010758 California Institute of Technology March1989","DOI":"10.1145\/63047.63063"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(89)90153-8"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.2514\/3.8951"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1002\/jcc.540040211"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/0909044"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(90)90115-P"},{"issue":"5","key":"e_1_2_1_16_2","first-page":"570","article-title":"A partitioning strategy for nonuniform problems on multiprocessors","volume":"36","author":"Berger M. J.","year":"1987","journal-title":"IEEE Trans."},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1987.5009494"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1981.1675756"},{"key":"e_1_2_1_19_2","unstructured":"H.Jordan \u2018A special purpose architecture for finite element analysis \u2019Proceedings of International Conference on Parallel Processing 1978 pp.263\u2013266."},{"key":"e_1_2_1_20_2","doi-asserted-by":"crossref","unstructured":"A. Y.GramaandV.Kumar \u2018Scalability analysis of partitioning strategy for finite element graphs: a summary of results \u2019Proceedings of Supercomputing '92 1992 pp.83\u201392.","DOI":"10.1109\/SUPERC.1992.236707"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00155802"},{"key":"e_1_2_1_22_2","doi-asserted-by":"crossref","unstructured":"Y. C.ChungandS.Ranka \u2018Mapping finite element graphs onto hypercubes \u2019Proceedings of Frontier of Massively Parallel Computations 1990. pp.135\u2013144.","DOI":"10.1109\/FMPC.1990.89449"},{"key":"e_1_2_1_23_2","doi-asserted-by":"crossref","unstructured":"D. Y.Hinz \u2018A run\u2010time load balancing strategy for highly parallel systems \u2019Proceedings of Distributed Memory Multiprocessor Conference 1990 pp.951\u2013961.","DOI":"10.1109\/DMCC.1990.556304"},{"key":"e_1_2_1_24_2","doi-asserted-by":"crossref","unstructured":"D.KingandE. J.Wegman \u2018Hypercube dynamic load balancing \u2019Proceedings of Distributed Memory Multiprocessor Conference 1990 pp.962\u2013965.","DOI":"10.1109\/DMCC.1990.556305"},{"key":"e_1_2_1_25_2","doi-asserted-by":"crossref","unstructured":"V. K.Saletore \u2018A distributed and adaptive dynamic load\u2010balancing algorithm for parallel processing of medium\u2010grain tasks \u2019Proceedings of Distributed Memory Multiprocessor Conference 1990 pp.994\u2013999.","DOI":"10.1109\/DMCC.1990.556310"},{"key":"e_1_2_1_26_2","doi-asserted-by":"crossref","unstructured":"J.XuandK.Hwang \u2018Heuristic methods for dynamic load balancing in a message\u2010passing supercomputer \u2019Proceedings of Supercimputing '90 1990 pp.888\u2013897.","DOI":"10.1109\/SUPERC.1990.130115"},{"key":"e_1_2_1_27_2","unstructured":"R. D.Williams \u2018DIME: a user's manual \u2019 Caltech Concurrent Computation Report C3P 861 February1990"},{"volume-title":"Solving Problems on Concurrent Processors","year":"1990","author":"Angus I. G.","key":"e_1_2_1_28_2"}],"container-title":["Concurrency: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fcpe.4330070704","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/cpe.4330070704","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,12]],"date-time":"2025-01-12T00:09:18Z","timestamp":1736640558000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/cpe.4330070704"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,10]]},"references-count":27,"journal-issue":{"issue":"7","published-print":{"date-parts":[[1995,10]]}},"alternative-id":["10.1002\/cpe.4330070704"],"URL":"https:\/\/doi.org\/10.1002\/cpe.4330070704","archive":["Portico"],"relation":{},"ISSN":["1040-3108","1096-9128"],"issn-type":[{"type":"print","value":"1040-3108"},{"type":"electronic","value":"1096-9128"}],"subject":[],"published":{"date-parts":[[1995,10]]}}}