Skip to main content
main-content

Über dieses Buch

The advent of very large scale integrated circuit technology has enabled the construction of very complex and large interconnection networks. By most accounts, the next generation of supercomputers will achieve its gains by increasing the number of processing elements, rather than by using faster processors. The most difficult technical problem in constructing a supercom­ puter will be the design of the interconnection network through which the processors communicate. Selecting an appropriate and adequate topological structure of interconnection networks will become a critical issue, on which many research efforts have been made over the past decade. The book is aimed to attract the readers' attention to such an important research area. Graph theory is a fundamental and powerful mathematical tool for de­ signing and analyzing interconnection networks, since the topological struc­ ture of an interconnection network is a graph. This fact has been univer­ sally accepted by computer scientists and engineers. This book provides the most basic problems, concepts and well-established results on the topological structure and analysis of interconnection networks in the language of graph theory. The material originates from a vast amount of literature, but the theory presented is developed carefully and skillfully. The treatment is gen­ erally self-contained, and most stated results are proved. No exercises are explicitly exhibited, but there are some stated results whose proofs are left to the reader to consolidate his understanding of the material.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Interconnection Networks and Graphs

Abstract
The topological structure of an interconnection network can be modeled by a graph. This fact has been universally accepted and used by computer scientists and engineers. Moreover, practically it has been demonstrated that graph theory is a very powerful mathematical tool for designing and analyzing topological structure of interconnection networks. For example, see books by Du and Hsu [71], Frank and Frisch [109], Hwang and Briggs [155], Leighton [177] and the two special issues by Bermond [19] and Hsu [148].
Junming Xu

Chapter 2. Design Methodology of Topological Structure of Interconnection Networks

Abstract
Due to the recent advances in hardware technology, especially in the advent of VLSI circuit technology, it is now feasible to build a large and very complex interconnection networks connecting tens of thousands of processing elements for an MPS capable of executing parallel algorithms. For example, the Connection Machine [143] contains as many as 216 processors. Thus, a systematic method is very necessary to design a topological structure for such very large scale interconnection networks.
Junming Xu

Chapter 3. Well-known Topological Structures of Interconnection Networks

Abstract
In this chapter, we will in details discuss four the well-known classes of topological structures: hypercubes, de Bruijn digraphs, Kautz digraphs and circulant digraphs, which can be constructed by the methods introduced in Chapter two. At the end of this chapter, other topological structures such as mesh, grid, pyramid, cube-connected cycle, butterfly, omega, and shuffleexchange networks will be briefly introduced.
Junming Xu

Chapter 4. Fault-Tolerant Analysis of Interconnection Networks

Abstract
There are a large number of graph optimization problems which arise in network design and analysis in the literature. Some of them have been summarized in a survey by Caccetta [46]. Our objective in this chapter is to highlight other new problems which arise in interconnection networks of large-scale parallel processing real-time systems.
Junming Xu

Backmatter

Weitere Informationen