Interleaved exchange in a network mesh

Details Interleaved exchange in a network mesh Interleaved exchange in a network mesh

1996-12-23

2001-01-09

Cabeca, John W. (Department: 2752)

Electrical computers and digital processing systems: processing

Processing architecture

Array processor

Reexamination Certificate

active

06173387

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 exchanging 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 exchanged 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), Hillis et al.
patent: 5038386 (1991-08-01), Li
patent: 5103393 (1992-04-01), Harris et al.
patent: 5170393 (1992-12-01), Peterson et al.
patent: 5333279 (1994-07-01), Dunning
Lai et al., “Placement of the Processors of a Hypercube”, Jun. 1991, 714-722.
Lai et al., “Placement of the Processors of a Hypercube,” IEEE Transactions on Computers, vol. 40, No. 6, pp. 714-722.
Shahid H. Bakhari, Complete Exchange on the iPSC-860, Nasa CR-187498, ICASE Report No. 91-4, Jan. 1991, 32 pages.
Shahid H. Bokhari & Harry Berryman; Complete Exchange on a Circuit Switched Mesh; 0-8186-2775-Jan. 1992 1992 IEEE; pp. 300-306.
William Stallings; Computer Organization and Architecture, Designing for Perfomance, 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-334 & 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./ 1525-1529.
David S. Soctt; 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.

Affiliated with

Also associated with

Rating

Interleaved exchange in a network mesh does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Interleaved exchange in a network mesh, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interleaved exchange in a network mesh will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2486233