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

In this paper, we propose a binomial tree based parallel load-balancing met hod (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 co ndensed processor graph. Based on the condensed processor graph, a prefix c ode tree is built. From the prefix code tree, a schedule for performing loa d transfer among processors can be determined by concurrently and recursive ly dividing the prefix code tree into two subtrees and finding a maximum ma tching for processors in the two subtrees until the leaves are reached. Sin ce each leaf is a binomial tree and a binomial tree can also be divided int o two equal halves of binomial trees, the approach used to determine the sc hedule of a prefix code tree could also be applied to the binomial trees. W e have implemented the BINOTPLB method on an SP2 parallel machine and compa red 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 cri teria, the execution time of mapping/load-balancing methods, the execution time of an application program under different mapping/load-balancing metho ds, and the speedups achieved by mapping/load-balancing methods for an appl ication program, are used for the performance evaluation. The experimental results show that the BINOTPLB method outperforms other methods for most of test samples.