Compile-time transformations and optimization of parallel Divide-and-Conquer algorithms

Publisher Website
Google Scholar
Abstract
In this paper we show how it is often possible to transform and optimize parallel algorithms based on the Divide-and-Conquer paradigm at compile time. Our goal is to make Divide-and-Conquer algorithms suitable for implementation on hypercube-like parallel architectures, such as the Connection Machine, even if the original algorithm implies a division function that is not the left-right division and/or communication pattern that cannot be implemented by direct-neighbor communication.Our tools are the formal model of the Divide-and-Conquer paradigm developed in [4] and the parallel programming language derived from this model: Divacon [2], [3].Our main results concern the replacement of last-k communication (broadcast) and mirror image communication with correspondent communication and the transformation from odd-even division to left-right division and vice versa. By using each of the techniques described in this paper it is possible to improve many Divide-and-Conquer algorithms by a factor of log(n).

This publication has 3 references indexed in Scilit: