Solutions of two minmax recurrences in parallel processing with variable recombination overhead

摘要

A variety of parallel algorithms are based on the paradigm of recursion. However, because of the partition and recombination overheads involved, such algorithms may perform poorly on real architectures. This paper deals with solutions of two minmax recurrence relations that result from optimal execution of parallel recursive algorithms in the presence of variable recombination overheads and constant partition overheads. We solve two models with the recombination overheads shown as a linear function of the partition size and the problem size, respectively. For model 1, we show that the optimal partition sizes for problem size n at any stage of the recursion can easily be found in O(log log n) time using an O(log n) size table. Model 2 is solved for cases k ≤ λ and k > λ, where k and λ are constants related to the parallel computing overheads. For the first case, the optimal partition size is derived to be [n2] and a closed-form solution of the complexity is exactly characterized. For the second case, the optimal partition size is found to be in the range [(n − t)2] ± 1, where t is a nonnegative constant that depends on k and λ, and the overall complexity is shown to be O(2λn + (k − λt)log2(n + t)). This paper develops the theory of solutions of minmax recurrences and provides some insight into this area of computational mathematics which has received little attention so far.