DIMACS TR: 94-49

Issues in parallel computing with hypercube multiprocessors

Author: Afonso Ferreira


The hypercube architecture has been extensively used in the design of parallel algorithms and for the construction of parallel computers. The aim of this report is to serve as a concise introduction to computational issues related to parallel and communication algorithms for hypercube multiprocessors.

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