Electrical computers and digital processing systems: processing – Processing architecture – Array processor
Reexamination Certificate
2001-06-12
2002-10-01
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: processing
Processing architecture
Array processor
C370S406000
Reexamination Certificate
active
06460128
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method of transmitting information within a network.
2. Description of Related Art
To increase the size, speed and scalability of computer systems, computers may be linked together within a network to process information in parallel. Such systems are commonly referred to as parallel processing networks. Parallel processing networks typically have a plurality of microprocessor based components coupled together by busses and associated hardware. Each processor based component functions as a node which can transmit information to other nodes within the network.
The nodes can be arranged as a plurality of interconnected cubes, commonly referred to as a hypercube. Hypercubes require a large number of data links, which increase the size of the system.
The nodes can also be arranged in a two-dimensional array, commonly referred to as a network mesh.
FIGS. 1
a-d
show a method of exchanging information within a mesh that is commonly referred to as the Direct Exchange Algorithm. In the Direct Exchange method, information is exchanged from one node to another node within the same row of the mesh. The process is repeated until the information of one node is transferred to each of the nodes within the row. For example, as shown in
FIG. 1
a
, in the first step, the information from node
1
is transferred to node
3
, node
2
transfers information to node
1
, node
3
transfers information to node
4
and the information of node
4
is transferred to node
2
. The process of exchanging information between nodes is repeated in accordance with the patterns shown in
FIGS. 1
b
,
1
c
and
1
d
. The information can then be exchanged between rows and the process is repeated. Although the Direct Exchange Algorithm has a relatively high transmission rate, the number of messages and the start-up time to send the messages from each node rapidly increases with the size of the mesh.
FIGS. 2
a-f
and
3
a-d
show other methods of exchanging information within a mesh, commonly referred to as the Binary Exchange Algorithm and the Quadrant Exchange Algorithm, respectively. Both of theses methods utilize a store and forward approach, wherein each node can both receive and forward information transmitted by another node. As shown in
FIG. 2
a
, in the first step of the Binary Exchange method, the nodes in one half of the mesh transmit information to nodes in the other half of the mesh in a horizontal direction. The process is repeated by sending the information from one half of the mesh to the other half of the mesh in a vertical direction, as shown in
FIG. 2
b
. As shown in
FIGS. 2
c-f
, the information is then exchange within quadrants and subquadrants of the mesh.
In the Quadrant Exchange method, information is exchanged within rectangular groups of nodes as shown in
FIGS. 3
a
and
3
b
. As shown in
FIG. 3C
, the information is then exchanged within separate quadrants of the mesh. Although both the Binary and Quadrant Exchange methods can be used in large mesh networks, the start-up time and transmission rate are relatively slow. Additionally, the Quadrant method is susceptible to node contention. It would be desirable to provide an algorithm for a mesh network, that was not susceptible to node contention and had a relatively high complete information exchange rate.
SUMMARY OF THE INVENTION
The present invention is a method for exchanging information within a mesh network that has an array of nodes defined by four quadrants. The method includes the initial steps of exchanging information from a set of nodes in one quadrant to a set of nodes located in an adjacent quadrant. The exchange of information simultaneously occurs in both a vertical and horizontal direction within the array. Information is then exchanged between nodes within the same quadrant and subquadrants.
REFERENCES:
patent: 4709327 (1987-11-01), Hills et al.
patent: 5038386 (1991-08-01), Li
patent: 5103343 (1992-04-01), Harris et al.
patent: 5170393 (1992-12-01), Peterson et al.
patent: 5333279 (1994-07-01), Dunning
patent: 5465379 (1995-11-01), Li
patent: 5689719 (1997-11-01), Miura et al.
Shahid H. Bokhari & Harry Berryman; Complete Exchange on a Circuit Switched Mesh; 0-8186-2775-1/92 1992 IEEE; pp. 300-306.
William Stallings; Computer Organization and Architecture, Designing for Performance, Fourth Edition; 1996; pp. 597-603; Prentice Hall, Upper Saddle River, NJ.
Richard Dorf; The Electrical Engineering Handbook, Chapter 89, Parallel Processors; 1993; pp. 2052-2060; CRC Press, Boca Raton, FL.
John P. Hayes; Computer Architecture and Organization; 1978; pp. 230-236 & 405-409; McGraw-Hill Book Company.
Jean-Loup Baer; Computer Systems Architecture; 1980; pp. 527-555; Computer Science Press, Inc., Rockville, MD.
Dan I. Moldovan; Parallel Processing, From Applications to Systems; 1993; pp. 191-227, 235-239, 287-296, 330-344 & 376-384; Morgan Kaufman Publishers, San Mateo, CA.
M. Barnett, R. Littlefield, D.G. Payne. R. Van De Geijn; Efficient Communication Primitives on Mesh Architectures with Hardware Routing; 6th SIAM Conference on Parallel Processing for Scientific Computing; Mar. 22-24, 1993; pp. 943-948.
W.J. Dally; A VLSI Architecture for Concurrent Data Structures; Kluwer Academic Publishers; 1987, pp. 1-242.
S.L. Johnsson & C-H. Ho; Optimum Broadcasting and Personalized Communication in Hypercubes; IEEE Trans. on Comp., C-38(9); Sep.1989; pp. 1249-1268.
William Dally and Charles Seitz; Deadlock-Free Message Routing in Multiprocessor Interconnection Networks; IEEE vol. C-36, No. 5, May 1987; pp. 547-553.
M. Barnett, R. Littlefield, D.G. Payne. R. Van De Geijn; Global Combine on Mesh Architectures with Wormhole Routing; Proceedings of the 7th International Parallel Processing Symposium held Apr. 13-16, 1993 IEEE; pp. 156-162.
S.H. Bokhari; Multiphase Complete Exchange on a Circuit Switched Hypercube; Intel. Conf. on Parallel Processing; 1991, pp. I525-I529.
David S. Scott; Efficient All-to-All communication Patterns in Hypercube and Mesh Topologies; The 6thDistributed Memory Computing Conference Proceedings, Apr. 28-May 1, 1991; 0-8186-2290-3/91.0000/0398 IEEE; pp. 398-403.
Shahid H. Bakhari, Complete Exchange on the iPSC-860, Nasa CR-187498, ICASE Report No. 91-4, 1/91, 32 pages.
Lai, et al., Placement of the Processors of a Hypercube, Jun. 1991, pp. 714-722.
Baxter Brent
Gupta Satyanarayan
Hawkinson Stuart
Intel Corporation
Kim Matthew
Tran Denise
LandOfFree
Mesh network with method and apparatus for interleaved... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Mesh network with method and apparatus for interleaved..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mesh network with method and apparatus for interleaved... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2978466