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].