ABSTRACT
Chapter 4
Hypercube Networks
In the following chapters we consider general undirected graphs, espe-
cially hypercubes and meshes, but also star graphs and related networks.
We concentrate on packet routing algorithms, for which theoretical re-
sults are richer. Although architectural issues, such as virtual shared
memory, prefetching, multithreading, and cache coherence play a promi-
nent role in the design of massively parallel systems, numerous eÆcient
platform-independent parallel solutions are derived directly from either
hypercube or mesh based algorithms. Unless otherwise specied, we as-
sume full duplex (bidirectional) links, and the constant model for node
to neighbor communication. For detailed description and analysis of
some important communication algorithms contained here, the reader
is referred to [401]. System issues are discussed in [137, 294]. Paral-
lel algorithms, mainly for meshes and hypercubes, are covered in de-
tail in [200, 300, 364, 561, 580]. Sorting algorithms are examined in
[21, 114, 384, 587].