Electrical computers and digital processing systems: processing – Processing architecture – Array processor
Reexamination Certificate
1999-12-30
2003-01-07
Coleman, Eric (Department: 2783)
Electrical computers and digital processing systems: processing
Processing architecture
Array processor
Reexamination Certificate
active
06505289
ABSTRACT:
1. Field of the Invention
The present invention relates to an apparatus for connecting nodes, especially, relates to a apparatus and method for interconnecting
3
-link nodes, and parallel processing apparatus using the same.
2. Prior Art of the Invention
The parallel processing system can have good performance by managing operation in parallel, simultaneously using multiprocessor. The interconnection network connecting nodes organized multiprocessor and transferring data, is very important component dominating the characteristic and performance of a parallel processing system. Each node in the parallel processing system has multi-link for connecting the adjacent nodes. The number of link connected in nodes and the connecting method of link makes difference of the data transfer method. So, It dominates the characteristic and performance of a parallel processing system.
Currently, the interconnection networks adopted in commercial parallel processing system are mainly the bus, ring, crossbar, mesh, and Hypercube interconnection network. However the bus, ring, crossbar interconnection network have handicap in performance or cost for constructing a large scale parallel processing system, so these are used for constructing a small scale system. The mesh interconnection network can offer
2
-dimensional mesh or
2
-dimensional torus mesh connection network, when there are four connecting links in node, and can offer
3
-dimensional mesh or
3
-dimensional torus mesh connection network, when there are six connecting links in node. For example, the ASCI TFLOPS system which has been applied by the Intel organizes two x-y plane mesh interconnection network using five connecting links in node. It is difficult to be organized mesh interconnection network, when the number of connecting links is three. For solving this problem, Ivan Stojmenovic proposed a ‘Honeycomb interconnection network’ that is the modification of the mesh connection network, using fixed three connecting links in node in the paper, Ivan Stojmenovic, “Honeycomb Network: Topological Properties Also Communication Algorithms,” IEEE Transactions on Parallel Also Distributed Systems, pp 1036-1042, October 1997. The Honeycomb interconnection network has the advantage of the mesh interconnection network that can expand feely using only fixed three links. However, it is difficult to divide Honeycomb interconnection network into
2
n
(n>
1
) nodes. So, it is difficult to apply to the normal package method. The Hypercube interconnection network can offer
3
-dimension Hypercube interconnection network, when there are three connecting links in node, can offer
4
-dimension Hypercube interconnection network, when there are four connecting links in node, and can offer
5
-dimension Hypercube interconnection network, when there are five connecting links in node. The Hypercube interconnecting network tends to increase in the number of links connected in node proportionally, as the nodes for connecting increase. For correcting the handicap of the Hypercube interconnection network, the F. P. Preparata et. al. proposed the Cube connected cycle interconnection network in the paper, F. P. Preparata et. al., “The cube-connected cycles: A versatile network for parallel computation,” Communication on ACM, pp 300-309, May 1981. Also, I. Y. Lee et. al. demonstrated the relationship of the Hypercube interconnection network, the Cube connected cycle interconnection network, and the similar interconnection network in the paper, I. Y. Lee et. al., “Ring-Connected Networks and Their Relationship to Cubical Ring Connected Cycles and Dynamic Redundancy Networks,” IEEE Transactions on Parallel and Distributed Systems, pp 988-996, September 1995. The Cube connected cycle interconnection network is able to connect nŝ
2
n
nodes using links, number of n in node, so it makes a pretty improvement comparing with the Hypercube interconnection network that can connect
2
n
in node. However there is a limitation to the Cube connected cycle interconnection network, using fixed links in node, namely it is able to connect the maximum twenty four nodes when the number of connecting links is three in node. The R. Shu and others made an improvement in the Hypercube interconnection network and the Cube connected cycle interconnection network, and proposed the Improved Hypercube interconnection network in the paper, R. Shu. al., “Improved Hypercube Topology for Multiprocessors Computer Systems,” U.S. Pat. No. 5,170,482, Dec. 8, 1992. The Improved Hypercube interconnection network is able to connect more links, and to shorten data transfer delay time than the existing others. However the Improved Hypercube interconnection network is a organization added connecting links to normal hypercube interconnection network, so by misfortune, it has the problem that it is not able to connect nodes having three connecting links.
FIGS. 1A-1C
illustrate methods for connecting nodes using fixed three connecting links in existing parallel processing system.
FIG. 1A
illustrates the
3
-dimensional Hypercube interconnection network. Each node in the
3
-dimensional Hypercube interconnection network has three connecting links, and is able to connect the maximum
8
nodes. However when anyone wants to expand nodes, it is impossible to expand nodes because connecting links in each node are added proportionally.
FIG. 1B
illustrates the Cube connected cycle interconnection network. The Cube connected cycle interconnection network is improved on the Hypercube interconnection network. Namely, it expands more nodes using fixed number of connecting links than the Hypercube interconnection network does. Also it is able to expand dimension of the Hypercube form, using fixed three connecting links. However the connecting structure is complex as dimension increases, and the Cube connected cycle interconnection network is not suitable to normal packaging method installing nodes,
2
n
nodes in one cabinet.
FIG. 1C
illustrates the Honeycomb interconnection network. The Honeycomb interconnection network is improved on the Mesh interconnection network that is in a difficult organizing using three connecting links. Namely, it expands more nodes using fixed three connecting links and the connecting structure is simple, expands nodes freely as the Mesh interconnection network does. But it is hard to divide into
2
n
(n>
1
) nodes, so the Honeycomb interconnection network is not suitable to normal packaging method installing
2
n
(n>
1
) nodes in one cabinet.
SUMMARY OF THE INVENTION
An embodiment of the present invention provides a method and apparatus for expanding nodes freely using fixed three connecting links, and for offering a normal packaging method with dividing
2
n
(n>
1
) nodes. A three links node interconnection apparatus in parallel processing system, comprises four nodes. The first node has three links connected to other nodes respectively. The second node has three links, one link of them is connected to the first node, and the other two links are in charge of connection of X+ direction, X− direction. The third node has three links, one link of them is connected to the first node, and the other two links are in charge of connection of Y+ direction, Y− direction. Also the fourth node has three links, one link of them is connected to the first node, and the other two links are in charge of connection of Z+ direction, Z− direction.
A three links node interconnection method in parallel processing system, comprises four steps. The first step is connecting the three links of the first node to other nodes respectively. The second step is connecting one of the links of the second node to the first node, and is making the other two links be in charge of connection of X+ direction, X− direction. The third step is connecting one of the links of the third node to the first node, and is making the other two links be in charge of connection of Y+ direction, Y− direction. Also the fourth step is connecting one of the links
Hahn Woo Jong
Han Jong Seok
Moh Sang Man
Yoon Suk Han
Coleman Eric
Electronics and Telecommunications Research Institute
Jacobson & Holman PLLC
LandOfFree
Apparatus and method for interconnecting 3-link nodes and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for interconnecting 3-link nodes and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for interconnecting 3-link nodes and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3031600