Electrical computers and digital processing systems: processing – Processing architecture
Reexamination Certificate
1999-02-12
2003-07-22
Jean, Frantz B (Department: 2155)
Electrical computers and digital processing systems: processing
Processing architecture
C712S011000, C712S012000, C712S015000, C712S016000, C712S029000, C709S238000
Reexamination Certificate
active
06598145
ABSTRACT:
BACKGROUND OF THE INVENTION
An interconnection network consists of a set of nodes connected by channels. Such networks are used to transport data packets between nodes. They are used, for example, in multicomputers, multiprocessors, and network switches and routers. In multicomputers, they carry messages between processing nodes. In multiprocessors, they carry memory requests from processing nodes to memory nodes and responses in the reverse direction. In network switches and routers, they carry packets from input line cards to output line cards. For example, pending U.S. patent application Ser. No. 08/918,556, filed by William J. Dally, Philip P. Carvey, Larry R. Dennison and P. Alan King for Internet Switch Router, describes the use of a three-dimensional torus interconnection network to provide the switching fabric for an internet router.
The arrangement of the nodes and channels in a network defines its topology.
FIG. 1
, for example, illustrates a two-dimensional, radix-8 torus topology, also called an 8-ary 2-cube. In this topology each node is designated by a two-digit radix-8 address. Channels in both directions connect each pair of nodes whose addresses differ by one in exactly one digit modulo 8. That is, node (a,b) is connected to nodes (a−1,b),(a+1,b),(a,b−1), and (a,b+1) where the addition and subtraction are performed modulo-8. Each node in this topology has degree 4 since it is connected to four other nodes. A related topology, an 8-ary 2-mesh, is shown in FIG.
2
. This network is identical to the 8-ary 2-cube except that the ‘end-around’ connections from node
7
to node
0
in each dimension are omitted. While the mesh network is simpler to wire, it has significantly lower performance than the torus network as will be described below.
Meshes and tori may be constructed with different radices and numbers of dimensions, and other network topologies are possible such as crossbars, trees, and butterfly networks. Several popular topologies are described, for example, by William J. Dally, “Network and Processor Architectures for Message-Driven Computers,” in
VLSI and Parallel Computation
, Edited by Suaya and Birtwistle, Morgan Kaufmann, 1990.
The topology chosen for an interconnection network is constrained by the technology used to implement the network. Pin-count constraints on chips, circuit boards, and backplanes, for example, limit the maximum degree of each network node. Wire-length constraints limit the maximum distance a single channel can traverse when the network is mapped into a physical packaging structure.
Low-dimensional (2-3 dimensions) torus and mesh networks have become popular in recent years in part because they offer good performance while having a small node degree and uniformly short wires when mapped to two or three dimensional electronic packaging systems. While at first it may appear that the end-around channels in a torus network result in long wires, these long wires can be avoided by folding the torus as illustrated in FIG.
3
. The figure shows how an 8×4 torus that is folded in the x-dimension is mapped onto a set of backplanes
20
. Each node is packaged on a circuit card and eight of these circuit cards are inserted in each backplane
20
. The circuit cards in each backplane span two x coordinates and the entire y dimension. The y-dimension channels are realized entirely in the backplane while the x-dimension channels are realized by connections between backplanes. Folding the torus allows this topology to be realized with each x-channel connecting no further than the adjacent backplane.
To expand the network of
FIG. 3
, it is necessary to first break the loopback connection
22
or
24
at the end of the x-dimension and then make a connection to a new backplane. An efficient method for reconfiguring the network in this manner is disclosed in pending U.S. patent application Ser. No. 09/083,722, filed by Philip P. Carvey, William J. Daily and Larry R. Dennison for Apparatus and Methods for Connecting Modules Using Remote Switching.
Two important measures of the quality of a topology are average path length and maximum channel load. The average path length, D
avg
, of a network is the average number of channels that must be traversed to send a packet between two randomly selected nodes in a network. In the radix-8, two-dimensional torus network of
FIG. 1
, the average packet traverses two channels in each dimension, giving P
avg
=4. In general, the average path length in a k-ary n-cube is kn/4 (for k even) and n(k/4-1/4k) (for k odd) while the average path length in a k-ary n-mesh is n(k/3-1/3k). Average path length is a good predictor of network latency. The lower the average path length of a topology, the lower is the latency of a network using that topology, assuming the latency of an individual channel remains constant.
The maximum channel load of a network, C
max
, is the largest number of packets that traverse a single channel when all nodes send packets to all other nodes divided by the number of nodes squared. In the 8-ary 2-cube network of
FIG. 1
, for example, the channel load is uniform with C
max
=C
i
=1 for every channel i. In general, the maximum channel load in a k-ary n-cube is k/8 while the maximum channel load in a k-ary n-mesh is k/4. Maximum channel load is a good predictor of the throughput of a network. The lower the maximum channel load of a topology, the higher is the throughput of a network using that topology, assuming the bandwidth of an individual channel remains constant.
SUMMARY OF THE INVENTION
While the folded torus network offers a method of packaging a regular k-ary n-cube network so that all of the channels remain short, it is inherently inefficient because nodes that are packaged very close to one another can communicate only via circuitous routes. For example, in
FIG. 3
, nodes (
2
,
0
) and (
7
,
0
) are on the same backplane. A message from (
2
,
0
) to (
7
,
0
), however, must leave this backplane and traverse five backplane-backplane connections before arriving back at the backplane. The problem becomes even more acute as the x-dimension grows in radix. A more efficient topology would minimize this off-backplane communication by allowing direct communication between nodes on the same backplane. A more efficient topology would also provide good performance without needing an end-around connection that must be removed for expansion.
One mechanism for increasing system performance in terms of average path length and maximum channel load and for making a network less susceptible to loss of end around connections is to add one or more dimensions to the network. However, adding a dimension increases the node degree by two, thus increasing the complexity of each node.
In accordance with one aspect of the invention, benefits of an added dimension without the increased node degree can be obtained by connecting one subset of channels within the network in one dimension and connecting another subset of the network channels in a different dimension. By distributing the nodes connected by the two channel subsets throughout the network, messages transferred through the network always have ready access to each dimension, but since each node need only be connected to one dimension or the other, there is no increase in degree. The concept of interleaving differing connections along one or more dimensions can be extended to other configurations for improved performance. Further, connections can be modified to assure that all nodes on a backplane, for example, are connected in a single cycle. The increased path lengths between some nodes resulting from the addition of such local connections can generally be masked by alternating the configurations from backplane to backplane.
In accordance with the invention, a plurality of channels connect a plurality of nodes in each connection network. A first subset of the channels connects the nodes is in a first dimension. A second subset of the channels connects the nodes in at least a second dimension, and connection
Carvey Philip P.
Dally William J.
Mann William F.
Avici Systems
Hamilton Brook Smith & Reynolds P.C.
Jean Frantz B
LandOfFree
Irregular network does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Irregular network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Irregular network will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3028871