摘要或動機

An exact solution to many current computational problems, such as the famous Travelling Salesman Problem (TSP), require a complete tree traversal in order to determine. This is often unfeasible, as the time complexity of the tree traversal grows exponentially with the size of the input, thus leading to an essentially computationally intractable problem. The branch and bound technique is an approach commonly used to speed this process. It entails dynamically pruning off branches of the tree in which the answer is probably not found in, hence reducing the amount of data that is needed to be traversed and the total time and resources required to perform the computation. In this paper, we introduce a new load-balancing strategy for the execution of such a branch and bound algorithm in parallel, using a three-tiered hierarchical approach, to perform fractal image compression, which is essentially a complete tree traversal problem. This novel heuristic is aimed at achieving optimal load-balancing and minimising unnecessary network traffic and bottlenecking, which functions by predicting the optimum search depth and hence controlling the coarseness of the input that is assigned to each worker node. Our scheme additionally enables us to tailor to the specifications of different clusters, as the heuristic is adjusted based on network speed and processor speed, which vary appreciably from cluster to cluster. We further discuss how to apply our method to other large tree search problems, such as the TSP and other NP-complete problems. We have also enhanced an existing load-balancing strategy outlined in Crivelli et. al. (2004, IBM Journal of Research and Development), by prioritising the reallocation of idle worker nodes such that supervisors who are in need of more help receive a larger share of the free workers.