Automated transformation of sequential divide–and– conquer algorithms into parallel programs

Divide{and{conquer algorithms obtain the solution to a given problem by dividing it into subproblems, solving these recursively and combining their solutions. In this paper we present a system that automatically transforms sequential divide{and{conquer algorithms written in the C programming language into parallel code which is then executed on message{passing multicomputers. The user of the system is expected to add only a few annotations to an existing sequential program. The strategies required for transforming sequential source code to executable binaries are discussed. The performance speedups attainable will be illustrated by several examples. Keywords: divide{and{conquer algorithms, automatic parallelization, parallelizing compilers, message{ passing multicomputers, transputer systems, workstation clusters Abbreviated title: Parallelization of Divide{and{Conquer Algorithm