N-GRAPHS - SCALABLE TOPOLOGY AND DESIGN OF BALANCED DIVIDE-AND-CONQUER ALGORITHMS

A parallel implementation of binary, balanced divide-and-conquer is de rived systematically from its functional specification. The implementa tion makes use of a new processor topology, called N-graph, and has th e following properties: there are not more than 4 links per processor, the processor network is of an arbitrary fixed size, the load is bala nced and all communications are local. A parallel mergesort algorithm is used to illustrate the derivation process and the parallel target p rogram with message passing. Experiments on a 64-node transputer netwo rk are presented.