Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1997-09-05
2001-01-16
Vu, Huy D. (Department: 2733)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S389000
Reexamination Certificate
active
06175566
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a broadcast transfer method for transferring the same data from one node to every other nodes, i.e., one of the functions of a interconnection network which is the key element of a parallel processing computer, and more particularly, to a broadcast transfer method adapted for a packet switching hierarchical interconnection network using a distributed routing control method and a packet of multiple tags.
2. Description of the Related Art
In general, an interconnection network is a network which connects between processors or between a processor and a storage device in a parallel processing computer. The transfer method of the interconnection network includes a point-to-point transfer, a broadcast transfer, and a multicast transfer.
The broadcast transfer, one of the important functions of the interconnection network is to transfer data from a transmitting node to every other receiving nodes connected to the interconnection network by a single operation when the same data is transferred to all nodes. However, in the interconnection network wherein a broadcast transfer is not supported, the same data should be transferred by a point-to-point transfer a number of times which corresponds to the number of receiving nodes. This ultimately results in the degradation of the transmission efficiency and the system performance because the traffic of the interconnection network and the latency are increased.
The routing switch as disclosed in U.S. Pat. No. 4,890,281 (Dec. 26, 1989) to Gian P. Balboni, et al. entitled “Switching Element for Self-Routing Multistage Packet-Switching Interconnection Network” is a 2×2 switching element constituting a multistage interconnection network for packet transmission, performs a self-routing function, and transfer data to a receiving node. Since an address representation area of only one bit is needed for each routing switch to perform a routing control in the multistage interconnection network consisting of a 2×2 routing switch, a maximum of 8 stages of an address representation can be allowed when a 8-bit data length is provided for each port.
The above multistage interconnection network is made of a non-hierarchical structure, not a hierarchical structure. This interconnection network provides a low expandability compared to an interconnection network of a hierarchical structure, and performs a point-to-point transfer and broadcast transfer using a single tag structure. The single tag structure has an advantage over a multitag structure that less load is given to a transmitting node generating a tag, however the multistage interconnection of a single tag structure has a limitation in expansion due to a constraint on the structure of the tag.
A non-blocking multicast multistage interconnection network as disclosed in U.S. Pat. No. 5,179,551 (Jan. 12, 1993) issued to Jonathan S. Turner which efficiently provides a multicast transmission uses a 4×4 routing switch as a basic element. Turner solved the problem of blocking which can be occurred when performing a multicast transmission by expanding the stages of a basic multistage interconnection network having a blocking characteristic. The broadcast transfer is a part of the multicast transfer, and thus the availability of a multicast transfer implies the availability of a broadcast transfer. However, although the above interconnection network has a packet switching structure, it has a problem that each switch does not perform a routing control function because it uses a central routing control scheme instead of a distributed routing control scheme wherein a routing control is performed by each routing switch by using a tag of each transfer packet.
In the distributed routing control scheme, a routing control is performed in each routing switch constituting the interconnection network, while in the central routing control scheme, each switch is controlled by one central control unit to perform a routing control.
A shunt interconnection network, one of interconnection networks of a hierarchical structure, as disclosed in the paper entitled “A Fault-Tolerant GaAs/CMOS Interconnection Network for Scalable Multiprocessors,” in IEEE Journal of Solid-State Circuits, pp. 692-705, May 1991 by Steven E. Butner, et al. is a crossbar interconnection network having a hierarchical structure. The shunt interconnection network supports an expandability of data length as well as an expandability of a hierarchical structure through a bit slice concept. However a basic block constituting an interconnection network is a set consisting of a plurality of switches, a plurality of network interface elements and a controller for controlling the switches and the elements, instead of a single switch. The proposed switch block has a circuit switching structure.
In the circuit switching structure, only pure data is transferred without a tag for routing control, once a transmission path has been established, compared to a packet switching structure. In the packet switching hierarchical interconnection network using a distributed routing control method, a tag structure having an address representation area encoded on a hierarchical basis is used to represent a receiving node on a tag of a packet. For example, three groups of address representation areas for specifying a port address of the interconnection network of a first layer, a port address of the interconnection network of a second layer and a port address (receiving node) of the interconnection network of the first layer to represent a receiving node in an interconnection network of two layers.
As the system expansion is performed in a parallel processing system having an expandability, most hierarchical interconnection network requires many hierarchical layers and more address representation areas for representing receiving nodes. When it is difficult to assign these address representation areas to a tag having the size of a data length, the use of multiple tags is essential. One of multiple tags represents a port address of one layer or multiple layers of the interconnection network. However, one tag of the multiple tags is generally designed to represent one layer of the hierarchical interconnection network since the functions of the interconnection network become complex and difficult to implement when address representation areas of multiple layers are assigned to one tag of the multiple tags. The hierarchical interconnection network using multiple tags is exhausted after it confirms a port address in the corresponding layer represented by one tag. This is because only after the corresponding tag is eliminated in the corresponding layer, a port can be specified with an exact address of the tag in the next layer. To this end, the interconnection network transfers the remaining packets after the corresponding tag has been eliminated.
For the point-to-point packet transfer, the transmitting node transmitting a packet generates the corresponding multiple tags in accordance with the location of the corresponding receiving node, and transfers them to the receiving node along with data of the packet. The receiving node receives pure data portion with the multiple tags eliminated in the packet which has passed each layer of the interconnection network. However, for the broadcast packet transfer where data is transferred simultaneously from one transmitting node to all receiving nodes, one packet transmitted from the transmitting node is copied and broadcasted as it passes through each layer of the interconnection network. Thus, when the broadcast transfer is performed using multiple tags, the number of multiple tags is set based on the receiving node passing through the largest number of layers among receiving nodes.
When the multiple tags are used in the same manner as in the point-to-point packet transfer, the problem arises that different packets are received according to the receiving group of each layer. In other words, some receiving nodes passing through the layers of th
Hahn Jong-Seok
Sim Won-Sae
Yoon Suk-Han
Boakye Alexander
Cohen & Pontani, Lieberman & Pavane
Electronics and Telecommunications Research Institute
Vu Huy D.
LandOfFree
Broadcast transfer method for a hierarchical interconnection... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Broadcast transfer method for a hierarchical interconnection..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Broadcast transfer method for a hierarchical interconnection... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2509647