Title: An Efficient Load Balancing Method for Tree Algorithms,
Abstract: Nowadays, multiprocessing is mainstream with exponentially increasing number
of processors. Load balancing is, therefore, a critical operation for the
efficient execution of parallel algorithms. In this paper we consider the
fundamental class of tree-based algorithms that are notoriously irregular, and
hard to load-balance with existing static techniques. We propose a hybrid load
balancing method using the utility of statistical random sampling in estimating
the tree depth and node count distributions to uniformly partition an input
tree. To conduct an initial performance study, we implemented the method on an
Intel Xeon Phi accelerator system. We considered the tree traversal operation
on both regular and irregular unbalanced trees manifested by Fibonacci and
unbalanced (biased) randomly generated trees, respectively. The results show
scalable performance for up to the 60 physical processors of the accelerator,
as well as an extrapolated 128 processors case.