Efficient Load-Balancing Method and System for Tree-Based Applications

摘要

In a system having multiple parallel processors, a process to enhance performance of tree based applications by balancing the processing load amongst all available parallel processors when processing the tree structure. Tree nodes and leaves are uniformly sampled at random to estimate the corresponding work (such as node counts and leave work). This is done through novel uniform node sample and weighted random depth probing. A linear workload mapping then maps subtrees into sub-intervals of a one-dimensional interval. Such mapping facilities inverse mapping of the estimated workload to achieve efficient partitioning of the tree. The process further adaptively decides upon subtrees to sample allowing for matching with the characteristics of input trees, decreasing the number of probes, while resulting in accurate load-balancing. The process provides for fast load balancing for complex tree-based applications by exploiting statistical random sampling and requires only modest memory resources for such process making it suitable and applicable to even modest embedded devices. A significant speedup in processing is achieved which increases with the number of available processors.