Paper Description: GorLe95b
BibTeX entry:
@InProceedings{GorLe95b,
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: