N-graphs: Scalable topology and design of balanced divide-and-conquer algorithms
A parallel implementation of binary, balanced divide-and-conquer is derived systematically from its functional specification. The implementation makes use of a new processor topology, called N-graph, and has the following properties: there are not more than 4 links per processor, the processor network is of an arbitrary fixed size, the load is balanced and all communications are local. A parallel mergesort algorithm is used to illustrate the derivation process and the parallel target program with message passing. Experiments on a 64-node transputer network are presented.
divide-and-conquer transputer parallel topologies transformations