Interconnection Networks: An Engineering Approach
J. Duato,
ISBN: 1-55860-852-4, 624, Morgan Kaufmann
© 2002, Elsevier Science (
Interconnection
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
I hope to slowly populate the text
below with links to vugraphs and other useful sites. In
the meantime you can visit the book’s site maintained by the publisher
Chapter 1 Introduction:[vugraphs(ps)]
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: [vugraphs(ps)]
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: [vugraphs(ps)]
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: [vugraphs(ps)]
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: [vugraphs(ps)]
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: [vugraphs(ps)]
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: [vugraphs(ps)]
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: [vugraphs(ps)]
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: [vugraphs(ps)]
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.
Resources
Errata (coming)
Simulators: This is a link to a web-based flit level simulator that
we have found very useful for conveying basic concepts of wormhole switching,
routing, and some deadlock issues.