Paper Description: GorLe95b

BibTeX entry:

author = "S. Gorlatch and C. Lengauer",
title = "$\cal N$-Graphs: A Topology for Parallel Divide-and-Conquer on Transputer Networks",
booktitle = {Transputer Applications and Systems '95},
editor = {B.~M.\ Cook and M.~R.\ Jane and P.\ Nixon and P.~H.\ Welch},
year = 1995,
publisher = {IOS Press},
pages = {\mbox{396--409}}
abstract =
"A parallel implementation of the divide-and-conquer template (skeleton) is derived systematically from a functional specification. A new topology, named N-graph, is introduced which is well suited for transputer networks: there are not more than 4 links per processor, overlapping of computations and communication within a processor is exploited, the processor network is of an arbitrary fixed size, the load is balanced and all communications between processors are local. The derivation proceeds by semantics-preserving transformations in the Bird-Meertens formalism which guarantees the correctness of the parallel implementation. A parallel merge-sort algorithm is used to illustrate the derivation process and the target program with message passing."

Paper itself:

Cross links: