| In a multicomputer consisting of processors that communicate over point-to-point full-duplex communication lines, the distance between two processors is the number of message forwarding steps required for them to communicate. The diameter of a network is the longest distance between processors, and the degree is the largest number of lines from any one processor. We examine the problem of minimizing the diameter k of a network as a function of the number N of processors, for a fixed degree d.;These new families have a regular structure that admits efficient routing algorithms. They have a close relationship with previously-proposed (less dense) families, allowing us to exploit known results on algorithm-mapping and VLSI layout.;Finally, we explore the issue of reliability. An intricate proof shows that our degree-3 families are 3-connected (the best possible connectivity for degree-3 networks)--that is, at least three node failures are required to partition the network. We then propose two new measures of network reliability, called local reroutability and average random failset size, that are particularly appropriate for evaluating multicomputer topologies. Both by the standard of connectivity and by our proposed measures, our double-exchange families of interconnection topologies are highly reliable as well as exceptionally dense.;We define a new general method, the double-exchange topology, that produces families of interconnection topologies that are denser than any families previously proposed. In particular, we have discovered families of networks with d = 3, k = 1.47 lg N; d = 4, k = 0.947 lg N; and d = 5, k = .75 lg N. The best previously-known results were d = 3, k = 2 lg N; d = 4, k = lg N; and d = 5, k = .77 lg N. |
