A PARALLEL SCHEME USING THE DIVIDE-AND-CONQUER METHOD

A parallel scheme using the divide-and-conquer method is developed. Th is partitions the input set of a problem into subsets, computes a part ial result from each subset, and finally employs a merging function to obtain the final answer. Based on a linear recursive program as a too l for formalism, a precise characterization for problems to be paralle lized by the divide-and-conquer method is obtained. The performance of the parallel scheme is analyzed, and a necessary and sufficient condi tion to achieve linear speedup is obtained. The parallel scheme is gen eralized to include parameters, and a real application, the fuzzy join problem, is discussed in detail using the generalized scheme.