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.
The load-balancing problem has been addressed previously but not in the manner proposed in this work. Several load balancing algorithms are available, for example Round Robin and Randomized Algorithms, Central Manager Algorithm and Threshold Algorithm. However, these algorithms depend on static load balancing. It requires that the workload is initially known to the balancing algorithm that runs before any real computation. Dynamic algorithms, such as the Central Queue algorithm and the Local Queue algorithm @cite_3 , introduce runtime overhead, as they provide general tasking distribution mechanisms that do not exploit tree aspects. Gursoy suggested several data composition schemes @cite_4 ; however, they are concerned mainly with tree-based k-means clustering, which does not target general trees. Another related work is that of El-Mahdy and ElShishiny @cite_5 ; that method is the closest to our work in terms of the adopted hybrid static and dynamic approach; however, the method targets the statically structured objects of images, and does not access irregular data structures, such as trees.
@cite_5 @cite_4 @cite_3
2231778486 1907099735 2118663179
A method and system for load balancing the work of NP processors (NP≧3) configured to generate each image of multiple images in a display area of a display device. The process for each image includes: dividing the display area logically into NP initial segments ordered along an axis of the display area; assigning each processor to a corresponding initial segment; assigning a thickness to each initial segment; simultaneously computing an average work function per pixel for each initial segment; generating a cumulative work function from the average work function per pixel for each initial segment; partitioning a work function domain of the cumulative work function into NP sub-domains; determining NP final segments of the display area by using the cumulative work function to inversely map boundaries of the sub-domains onto the axis; assigning each processor to a final segment, and displaying and or storing the NP final segments. Developing fast algorithms for clustering has been an important area of research in data mining and other fields. K-means is one of the widely used clustering algorithms. In this work, we have developed and evaluated parallelization of k-means method for low-dimensional data on message passing computers. Three different data decomposition schemes and their impact on the pruning of distance calculations in tree-based k-means algorithm have been studied. Random pattern decomposition has good load balancing but fails to prune distance calculations effectively. Compact spatial decomposition of patterns based on space filling curves outperforms random pattern decomposition even though it has load imbalance problem. In both cases, parallel tree-based k-means clustering runs significantly faster than the traditional parallel k-means. Studies the performance of a randomized algorithm for balancing load across a multiprocessor executing a dynamic irregular task tree. Specifically, we show that the time taken to explore a task tree is likely to be within a small constant factor of an inherent lower bound for the tree instance. Our model permits arbitrary task times and overlap between computation and load balance, and thus extends earlier work (R.M. Karp and Y. Zhang, 1988) which assumed fixed cost tasks and used a bulk synchronous style in which the system alternated between distinct computing and load balancing steps. Our analysis is supported by experiments with application codes, demonstrating that the efficiency is high enough to make this method practical. >