Automated Transformation of Sequential Divide-And-Conquer Algorithms into Parallel Programs

Abstract

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.