Electrical computers and digital processing systems: processing – Processing architecture – Array processor
Reexamination Certificate
1997-11-17
2001-05-08
Chan, Eddie (Department: 2183)
Electrical computers and digital processing systems: processing
Processing architecture
Array processor
C712S016000, C709S238000, C709S242000
Reexamination Certificate
active
06230252
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the field of high-speed digital data processing systems, and more particularly, to interconnection architectures for interconnecting processor element nodes in multiprocessor computer systems.
BACKGROUND OF THE INVENTION
Multiprocessor computer systems comprise a number of processing element nodes connected together by an interconnect network. Each processing element node includes at least one processing element. The interconnect network transmits packets of information or messages between processing element nodes. Multiprocessor computer systems having up to hundreds or thousands of processing element nodes are typically referred to as massively parallel processing (MPP) systems. In a typical multiprocessor MPP system, every processing element can directly address all of memory, including the memory of another (remote) processing element, without involving the processor at that processing element. Instead of treating processing element-to-remote-memory communications as an I/O operation, reads or writes to another processing element's memory are accomplished in the same manner as reads or writes to the local memory.
In such multiprocessor MPP systems, the infrastructure that supports communications among the various processors greatly affects the performance of the MPP system because of the level of communications required among processors.
Several different topologies have been proposed to interconnect the various processors in such MPP systems, such as rings, stars, meshes, hypercubes, and torus topologies. Regardless of the topology chosen, design goals include a high communication bandwidth, a low inter-node distance, a high network bisection bandwidth and a high degree of fault tolerance.
Inter-node distance is defined as the number of communications links required to connect one node to another node in the network. Topologies are typically specified in terms of the maximum inter-node distance or network diameter: the shortest distance between two nodes that are farthest apart on the network.
Bisection bandwidth is defined as the number of links that would be severed if the network were to be bisected by a plane at a place where the number of links between the two halves is a minimum. In other words, bisection bandwidth is the number of links connecting two halves of the network where the halves are chosen as the two halves connected by the fewest number of links. It is this worst-case bandwidth which can potentially limit system throughput and cause bottlenecks. Therefore, it is a goal of network topologies to maximize bisection bandwidth.
One way to describe bisection bandwidth is in terms of the number of nodes in the network to enable comparison of the relative bisection bandwidths of networks of various sizes. For a network having k nodes, bisection bandwidth is defined in terms of the number of nodes as x*k. For example, as described below, a conventional hypercube has a bisection bandwidth of (½)k. This bisection bandwidth remains constant (relative to the number of nodes) at k/2 regardless of the dimension of the conventional hypercube.
Note that it may be more appropriate to define bisection bandwidth as the number of communications links times the bandwidth of each link. However, assuming a constant bandwidth/link regardless of the topology, relative bisection bandwidth comparisons among the topologies can simply be addressed in terms of the number of links. Therefore, as a matter of convention, bisection bandwidth is defined in this document in terms of the number of communications links.
In a torus topology, a ring is formed in each dimension where information can transfer from one node, through all of the nodes in the same dimension and back to the original node. An n-dimensional torus, when connected, creates a n-dimensional matrix of processing elements. A bi-directional n-dimensional torus topology permits travel in both directions of each dimension of the torus. For example, each processing element node in the 3-dimensional torus has communication links in both the + and − directions of the x, y, and z dimensions. Torus networks offer several advantages for network communication, such as increasing the speed of transferring information. Another advantage of the torus network is the ability to avoid bad communication links by sending information the long way around the network. Furthermore, a toroidal interconnect network is also scalable in all n dimensions, and some or all of the dimensions can be scaled by equal or unequal amounts.
In a conventional hypercube network, a plurality of microprocessors are arranged in an n-dimensional cube where the number of nodes k in the network is equal to 2
n
. In this network, each node is connected to each other node via a plurality of communications paths. The network diameter, the longest communications path from any one node on the network to any other node, is n-links.
One feature of the conventional hypercube is that the maximum distance between any two nodes (i.e., the diameter) in a hypercube having k nodes is given by log
2
(k). Thus, even as the number of nodes increases, the maximum distance between any two nodes only increases as log
2
. As a result, the number of nodes, and hence the number of processors or I/O ports, can be doubled while only requiring a unitary increase in the network diameter between any two nodes. Thus, for each increase in the dimension of the topology (i.e., to expand from an n-dimensional to an (n+1)-dimensional hypercube), an additional edge must be connected to each node. Thus, it is axiomatic that to increase the dimension of a hypercube, each node must have an additional port to support the additional connection. As a result, as the dimension of the hypercube increases the number of ports in each node increases as well.
Another advantage of the conventional hypercube is a high bisection bandwidth. With a conventional hypercube, the bisection bandwidth always remains constant at k/2, for a hypercube having k nodes.
Several extensions or variations of the conventional hypercube have been proposed and/or implemented in multiprocessor systems. One such variation, presented in Louri, et al.,
Scalable optical hypercube-based interconnection network for massively parallel computing
, Applied Optics, Vol. 33, No. 32, Nov. 10, 1994, pp 7588-7598, is the multi-mesh hypercube. One disadvantage of the multi-mesh hypercube over the conventional hypercube is a large network diameter. For a multi-mesh hypercube made up of an l×m array of n-dimensional hypercubes, the maximum distance is ((l−1)+(m−1)+n). A second disadvantage of the multi-mesh hypercube topology is a low bisection bandwidth relative to the number of nodes in the network. For a symmetrical mesh (where l=m), the bisection bandwidth is k/4, where k is the number of nodes.
A second variation on the conventional hypercube is presented in Malluhi, et al.,
The Hierarchical Hypercube: A New Interconnection Topology for Massively Parallel Systems
, IEEE Transactions on Parallel and Distributed Systems, vol. 5, No. 1, January 1994, pp. 17-30. According to Malluhi, each of the nodes of an n-dimensional hypercube is itself an n′-dimensional hypercube. This topology has two disadvantages over the conventional hypercube: a lower bisection bandwidth and a greater maximum distance for the same number of nodes.
Consider, for example, a three-dimensional hierarchical hypercube according to Malluhi, where each node is itself a three-dimensional hypercube (i.e., n=3, n′=3). In such a network, there are 64 nodes, and the bisection bandwidth is 4 edges, or k/16. Contrast this to the conventional hypercube having 64 nodes with a bisection bandwidth of 32 edges, or k/2. Also, Malluhi's hierarchical hypercube has a maximum diameter of (n+2n′) which, for the n=3 and n′=3 network of the current example yields a maximum diameter of nine edges. For a conventional
Galles Michael B.
Passint Randal S.
Thorson Greg
Chan Eddie
Monestime Mackly
Schwegman Lundberg Woessner & Kluth P.A.
Silicon Graphics Inc.
LandOfFree
Hybrid hypercube/torus architecture does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hybrid hypercube/torus architecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hybrid hypercube/torus architecture will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2563219