A binomial tree based parallel load-balancing method for solution-adaptive finite element graphs on distributed memory multicomputers

摘要

In this paper, we propose a binomial tree based parallel load-balancing method (BINOTPLB) to deal with the load imbalance of solution-adaptive finite element application programs on distributed memory multicomputers. The main idea of the BINOTPLB method is first to construct a binomial tree based condensed processor graph. Based on the condensed processor graph, a prefix code tree is built. From the prefix code tree, a schedule for performing load transfer among processors can be determined by concurrently and recursively dividing the prefix code tree into two subtrees and finding maximum matching for processors in the two subtrees until the leaves are reached. Since each leaf is a binomial tree and a binomial tree can also be divided into two equal halves of binomial trees, the approach used to determine the schedule of a prefix code tree could also be applied to the binomial trees. We have implemented the BINOTPLB method on an SP2 parallel machine and compared its performance with two load-balancing methods, the directed diffusion method and the multilevel diffusion method, and three mapping methods, the JOSTLE-MS method, the MLkP method, and the PARTY library method. Three criteria, the execution time of mapping/load-balancing methods, the execution time of an application program under different mapping/load-balancing methods, and the speedups achieved by mapping/load-balancing methods for an application program are used for the performance evaluation. The experimental results show that the BINOTPLB method outperforms other methods for most of test samples.