Automatic Parallelization of Divide{and{Conquer Algorithms

Abstract. In this paper we present a system that automatically partitions sequential divide{and{conquer algorithms programmed in C into indepen-dent tasks, maps these to a MEIKO transputer system and executes them in parallel. The feasibility of our approach is illustrated by parallelizing several example algorithms and measuring the resulting performance speedups. 1 General Approach and System Description Our approach for mapping divide{and{conquer algorithms to a multiprocessor ar-chitecture is to use the partitioning information inherently included in the algorithm and let one processor divide the initial problem into two subproblems, pass one of these to a further processor and keep the other one to itself [2]. Every processor repeats this step recursively until the problem size is suciently small and performs the computation assigned to it, which logically constitutes a mapping to a binomial tree topology. The results are propagated up the tree and combined in the reverse order in which the subproblems were passed down. The fundamental communication pattern used in our system is based on a mas