4 - Introduction to Parallel Routing

Summary

[E]very time that I went out for a walk

I used to be afraid that the house would

catch fire and the manuscript [of

Principia Mathematica] get burnt up

—Bertrand Russell

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.