Tree-based parallel load-balancing methods for solution-adaptive finite element graphs on distributed memory multicomputers

To solve the load imbalance problem of a solution-adaptive finite element a pplication program on a distributed memory multicomputer, nodes of a refine d finite element graph can be remapped to processors or load of a refined f inite element graph can be redistributed based on the current load of each processor. For the former case, remapping can be performed by some fast map ping algorithms. For the latter case, a load-balancing algorithm can be app lied to balance the computational load of each processor. In this paper, th ree tree-based parallel load-balancing methods, the MCSTLB method, the BTLB method, and the CBTLB method, were proposed to deal with the load imbalanc e problems of solution-adaptive finite element application programs. To eva luate the performance of the proposed methods, we have implemented those me thods along with three mapping methods, the AE/ORB method, the AE/MC method , and the MLkP method, on an SP2 parallel machine. Three criteria, the exec ution time of mapping/load-balancing methods, the execution time of a solut ion-adaptive finite element application program under different mapping/loa d-balancing methods, and the speedups achieved by mapping/load-balancing me thods for a solution-adaptive finite element application program, are used for the performance evaluation. The experimental results show that 1) if th e initial mapping is performed by a mapping method and the same mapping met hod and load-balancing methods were used in each refinement to balance the load of processors, the execution time of an application program under a lo ad-balancing method is always shorter than that of the mapping method, and 2) the execution time of an application program under the CBTLB method is s horter than that of the BTLB method and the MCSTLB method.