The routing algorithms in Chapter 5 can be converted into efficient asynchronous algorithms by replacing the global clock with a synchronization scheme based on message passing. We also demonstrate that asynchronous fsra has low sensitivity to variations in link and processor speeds.

Introduction

The assumption of synchronism often greatly simplifies the design of algorithms, be they sequential or parallel. Many computation models — for example, RAM (“Random Access Machine”) [5] in the sequential setting and PRAM in the parallel setting — assume the existence of a global clock. But, this assumption will become less desirable as the number of processors increases. For one thing, a global clock introduces a single point of failure. A global clock also restrains each processor's degree of autonomy and renders the machine unable to exploit differences in running speed [42, 192], limiting the overall speed to, so to speak, that of the (“slowest” component instead of the “average” one, thus wasting cycles. Tight synchronization also limits the size of the parallel computer, since it takes time to distribute the clock-signal to the whole system [316].

Proceeding in epochs, our routing schemes in Chapter 5 assume synchronism. In fact, the very definition of ECS assumes a global clock to synchronize epochs. We show in this chapter that with synchronization done via message passing, ECSs can be made asynchronous without loss of efficiency and without global control. Much work has been done in this area; see, for example, [31, 32, 33].

It has long been recognized that computer design utilizing more than one processor is one promising approach — some say the only approach — toward more powerful computing machines. Once one adopts this view, several issues immediately emerge: how to connect processors and memories, how do processors communicate efficiently, how to tolerate faults, how to exploit the redundancy inherent in multiprocessors to perform on-line maintenance and repair, and so forth.

This book confronts the above-mentioned issues with two keys insights. There exist error-correcting codes that generate redundancy which is efficient in terms of the number of bits. Such redundancy is used to correct errors and erasures caused by component failures and resource limitations (such as limited buffer size). This insight comes from Michael Rabin. The next insight, due to Leslie Valiant, demonstrates the criticality of randomization in achieving communication efficiency.

We intend to make this book an up-to-date account of the information dispersal approach as it is applied to parallel computation. We also discuss related work in the general area of parallel communication and computation and provide an extensive bibliography in the hope that either might be helpful for researchers and students who want to explore any particular topic. Although materials in this book extend across several disciplines (algebra, coding theory, number theory, arithmetics, algorithms, graph theory, combinatorics, and probability), it is, the author believes, a self-contained book; adequate introduction is given and every proof is complete.

The simulation of the ideal parallel computation model, pram, on the hypercube network is considered in this chapter. It is shown that a class of pram programs can be simulated with a slowdown of O(log N) with almost certainty and without using hashing, where N denotes the number of processors. Also shown is that general pram programs can be simulated with a slowdown of O(log N) with the help of hashing. Both schemes are ida-based and fault-tolerant.

Introduction

Parallel algorithms are notoriously hard to write and debug. Hence, it is only natural to turn to ideal models that provide good abstraction. As these models do not assume any particular hardware configuration, they should have the additional benefit that programs written for them can be executed on any hardware that supports the model, similar to the situation in the sequential case where the existence of a, say, C compiler on a particular platform implies standard C programs can be compiled and executed there [370]. The PRAM (“Parallel Random Access Machine”) is one such model. It completely abstracts out the cost issue in communication and allows us to focus on the computational aspect. However, such convenience and generality is not without its price: the PRAM model, unlike the von Neumann machine model, is not physically feasible to build [369]. The simulation of PRAMs by feasible computers is therefore important and forms the major theme of this chapter.

After briefly examining the challenges facing designing ever more powerful computers, we discuss the important issues in parallel processing and outline solutions. An overview of the book is also given.

The von Neumann Machine Paradigm

The past five decades have witnessed the birth of the first electronic computer [257] and the rapid growth of the computing industry to exceed $1,000 billion (annual revenue) in the U.S. alone [162]. The demand for high-performance machines is further powered by the advent of many crucial problems whose solutions require enormous computing power: environmental issues, search for cures for diseases, accurate and timely weather forecasting, to mention just a few [271]. Moreover, although unre-lenting decrease in the feature size continues to improve the computing capability per chip, turning that into a corresponding increase in computing performance is a major challenge [152, 316]. All these factors point toward the necessity of sustained innovation in the design of computers.

That the von Neumann machine paradigm [37], the conceptual framework for most computers, considered at the system level will impede further performance gains is not hard to see. Input and output excluded, the von Neumann machine conceptually consists of a processing unit, a memory storing both programs and data, and a wire that connects the two.

In this final chapter, we briefly review techniques and concepts in fault-tolerant computing. Then we sketch the design of a fault-tolerant parallel computer, hpc (“hypercube parallel computer”), based on the results and ideas from previous chapters.

Introduction

A fault-free computer, or any human artifact, has never been built, and will never be. No matter how reliable each component is, there is always possibility, however small, that it will go wrong. Statistical principles dictate that, other things being equal, this possibility increases as the number of components increases. Such an event, if not anticipated and safe-guarded against, will eventually make the computer malfunction and lead to anything from small annoyance and inconvenience to disaster.

Recently, the same enormous decrease in hardware cost which makes parallel computers economically feasible also makes fault tolerance more affordable [297]. In other words, the low cost of hardware makes possible both high degree of fault tolerance using redundancy and high performance. Indeed, most fault-tolerant computers today employ multiple processors; see [241, 254, 317] for good surveys.

It is in the light of these backgrounds that we take this extra step toward designing a hypercube parallel computer (HPC for short). In the HPC processors are grouped into logical clusters consisting of physically close processors, and each program execution is replicated at all members of a cluster. Clusters overlap, however. The concept of cluster — logical or physical — introduces a two-level, instead of flat, organization and can be found in, for example, the Cm [344], Cedar [187], and FTPP (“Fault Tolerant Parallel Processor”) [148] computers.

This chapter serves two purposes: review of previous work and preview of our new results on the parallel routing problem. Our general approach to the problem is also outlined. The routing schemes and their analysis will appear in the next chapter.

Introduction

Perhaps the most important issue in parallel computers is interprocessor communication. Since processors are linked together by a relatively sparse network due to cost considerations, packets have to traverse many links and even be delayed by other packets due to conflicts or full buffers before reaching their destinations. Communication time, therefore, can easily dominate the total execution time, making designing fast communication schemes a primary concern. It is also preferable that the buffer size be a constant independent of the size of the network for the sake of scalability. Finally, as more components mean more faults [326], other things being equal, the issue of fault tolerance without loss of efficiency should be dealt with together.

We review previous work and preview our approach and results in this chapter. In the next chapter, it will be shown how the above-mentioned problems can be tackled simultaneously using information dispersal.

Fast, fault-tolerant communication schemes using constant size buffers on the hypercube and the de Bruijn networks are presented. All our schemes run with probability of successful routing 1 – N−Θ(logN) where N denotes the number of processors. A summary of this chapter's results can be found in Section 4.4.

Parallel Communication Scheme

The notion of symmetric parallel communication scheme (SPCS) captures the essence, and facilitates the analysis, of our parallel routing algorithms.

Definition 5.1In anepoched communication scheme (ECS), packets are sent inepochs, numbered from 0. In any epoch, packets that demand transmission to neighboring nodes in that epoch, as determined by the routing algorithm, are sent along the links as requested. A symmetric parallel communication scheme (SPCS) is an ECS that satisfies the following conditions.

1. Each node initially has h packets.

2. All packets are routed independently by the routing algorithm; that is, in any epoch, a packet crosses an out-going link independently with equal probability.

3. The expected number of packets at each node is h at the end of each epoch.

Such a scheme is called an h-SPCS.

Comment 5.2 Condition 3 implies that no packets can be lost. In all our schemes, however, pieces (that is, packets in the definition of ECS) can be lost due to buffer overflow. This is not a serious problem since we can analyze a scheme as if pieces over the capacity of the buffer were not lost.

We demonstrate in this chapter that, if fsra is used, a constant fraction of the wires in the hypercube network can be disabled simultaneously without disrupting the ongoing computation or degrading the routing performance. This general result can lead to efficient on-line maintenance procedures. This seems to be the first time that the important issue of on-line maintenance is addressed analytically.

Introduction

The fact that hardware deteriorates and the demand that machine be more available to the user make the property of on-line maintenance without performance penalty a desirable design goal. For example, in the Tandem/16 computer system [173], modular design allows some components to be replaced on-line. Periodic maintenance of the hardware is also key to ensuring consistent system performance; without it, one cannot safely say a particular component retains roughly the same failure rate at different times.

In this chapter we address the issue of on-line wire maintenance on the hypercube network with FSRA as the routing algorithm. It is shown that the set of edges can be partitioned into a constant number, 352, of disjoint edge sets of roughly equal sizes such that the probability of unsuccessful routing is exponentially small if any edge set in the proposed partition is disabled (Theorem 8.3). That implies little performance penalty as re-routing is extremely unlikely. The partition is also easily and locally computable.

We survey interconnection networks that link the processors in a parallel computer. Important terms and design issues pertaining to networks are also briefly discussed. This chapter is intended to be concise and sufficiently complete.

Introduction

The interconnection network in a multiprocessor specifies how the processors are tied together. The processors then communicate by sending information through the network. Since the interprocessor delay easily dominates the execution time [56] except where interprocessor communications are rare or only nearly processors exchange information, the choice of the network makes the difference between an efficient system and an inefficient one; clearly, a network where information has to traverse, say, 100 links on the average is less efficient than the one where only ten suffice, other things being equal. Besides the efficiency issue, the interconnection network also sets a limit to the number of faults a parallel computing system can sustain. For example, since a disconnected network that isolates some processors from the others makes joint computation impossible, the network should be able to withstand many faulty links.

This chapter surveys interconnection networks and related issues. In Section 3.2 some of the basic terms for networks are reviewed. A simple and useful graph- theoretical abstraction of networks is introduced in Section 3.3. Several popular networks are then briefly surveyed in Section 3.4, followed by Section 3.5, where some key issues in the choice of networks are summarized.