Interconnection Networks: An Engineering Approach

Interconnection Networks: An Engineering Approach

J. Duato, S. Yalamanchili, L. Ni
ISBN: 1-55860-852-4, 624, Morgan Kaufmann

© 2002, Elsevier Science (USA) |

image002Interconnection networks are becoming increasingly pervasive in many different applications, with the operational costs and characteristics of these networks considerably depending on the application. For some applications, interconnection networks have been studied in depth for decades. This is the case for telephone networks, computer networks (telecommunications), and backplane buses. The design and operation of these networks are covered in many excellent books.  However, in the last 10 years we have seen a rapid evolution of the interconnection network technology that is currently being infused into a new generation of multiprocessor systems. The technology is mature enough to find its way into commercial products, while constantly presenting new avenues for growth and application. This is the case for the interconnection networks used in multi-computers and distributed shared-memory multiprocessors. At the current time, the basic design issues governing this new generation of multiprocessor network technology are diffused over a large number of technical papers. This book is an attempt to present a coherent description of this technology in a form that emphasizes the engineering aspects of their construction and use.

Overview of the Text

Lecture Slides [pdf]
These slides are for my graduate course on Interconnection Networks. They do not exhaustively cover this text, and include material not found in the text.

Chapter 1  Introduction
The introductory chapter provides a presentation of the various classes of interconnection networks and seeks to present them in the context of recent advances in engineering high-performance interconnection networks.

Chapter 2  Message Switching Layer:
This chapter describes the components that comprise the switching layer, including flow-control protocols and buffering mechanisms that have been proposed in recent years. The major mechanisms employed in all currently available routers are covered.

Chapter 3 Deadlock, Livelock, and Starvation:
This chapter is the heart of the basic issues covered in this book. Descriptions are provided for developing deadlock-free routing protocols and ensuring livelock-free routing. The emphasis is on constructive principles rather than formal proofs.

Chapter 4  Routing Algorithms:
This chapter presents a taxonomy of routing protocols and descriptions of representative routing algorithms in each class. Methodologies are presented for constructing deadlock-free routing algorithms for different switching techniques.

Chapter 5  Collective Communication Support:
Modern algorithms for collective communication are described that exploit the properties of pipelined networks. Hardware and software support for broadcast, multicast, barrier synchronization, and other collective communication operations is described.

Chapter 6  Fault-Tolerant Routing:
As parallel computing architectures grow in size and find their way into mission critical applications, the need for robust and reliable communication grows. Chapter 6 covers the current generation of fault-tolerant routing algorithms. Particular attention is paid to paradigms, fault models, and network features in support of such routing algorithms.

Chapter 7  Network Architectures:
Optimizing the design of networks is a process of optimizing performance in the presence of physical constraints such as wiring density, pin-out, and chip area. This chapter covers models for optimizing the network topology as well as the design of router architectures to date.

Chapter 8  Messaging Layer Software:
As “time on the wire” continues to drop, the software overheads start becoming an increasingly large portion of the overall message latency. This chapter covers the issues facing the design of the software messaging layer, and the implementation of two current lightweight message layers: active messages and fast messages. A brief introduction and pointers to the Message Passing Interface (MPI) standard are also provided as an example of a user-level application programming interface.

Chapter 9 Performance Evaluation:
Accurate and reliable estimates of the network performance are crucial in developing and assessing design approaches. This chapter takes a detailed walk through evaluation of routing algorithms, network design parameters, and switching techniques. Network interfaces and support for collective communication and fault tolerance are evaluated as well. Emphasis is placed in evaluation techniques and interpretation of simulation results.