Section 2 describes structural characteristics of the hypercube topology, that made it very attractive for the realization of the interconnection network of parallel computers. Graph properties and embeddings are studied.
Section 3 surveys algorithms and techniques for implementing inter-processor communication in hypercubes. On- and off-line permutation routing techniques in store \& forward mode are detailed.
Section 4 is devoted to the study of useful algorithmic tools for the fine-grain hypercube. These include semigroup and data movement operations, as well as merging and sorting, that are used for implementing all kinds of synchronous algorithms.
Section 5 presents some important algorithms that were designed for the fine-grain hypercube. Main issues such as the implementation of concurrent data-structures are discussed.
A large number of references to more in-depth research papers are given to those willing to pursue investigation in this challenging domain.
Relation to Dimacs:
Part of this work was done when the author was visiting Dimacs
in May, partially supported by Dimacs NSF grant STC--91--199999 and
the NJ Commission.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-49.ps
DIMACS Home Page