JPH05242000A - Multistage network system - Google Patents

Abstract

PURPOSE: To execute an integrated network job adding multiple functions by providing a replacement pass between devices in the same network. CONSTITUTION: Multiplexers(MUX) 2 and 3 executes an output consisting of two encoded bits for deciding which one of the four, for example, replacement passes is selected at the point of time when they are given. MUXs 2 and 3 are controlled by a re-trial counter 4 which is reset to zero at every new message start. In the counter 4 and a replacement pass control counter 5, the tried pass is prevented and addition is executed based on REJECT signal. When the count of the re-trial counter 4 is zero, one or two, a replacement pass number being the output of the counter 5 is selected in MUX control and the counter generates re-arrayal. The replacement pass number is selected from the lowest- order address bit of reception node addresses which are stored in a node address register 1 in MUX control concerning the other whole values of the re-trial counter 4.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a multifunction network, and more particularly to a multifunction network system capable of operating as a multi-stage asynchronous network.

[0002]

BACKGROUND OF THE INVENTION Multi-stage switching networks are used as a means for interconnecting multiple devices within a computer system. The system requires multiple paths through the switching network to perform different functions. An early work by Peter Franasxek at IBM, "Multipath Hierarchies in Interconnection N."
etworks) "shows two hierarchical paths for a network, one with low latency message transfer and the other with guaranteed transfer of message transfer, i.e. guaranteed transfer of messages with longer latency. I do. First the message is attempted via the low latency path. If this transmission fails due to blocking or contention,
It will be retried over this guaranteed transfer path. This allows about 90% of normal messages to be sent over the low latency path, and retransmission ensures the transfer of messages blocked on this low latency path.

US Pat. No. 4,952,930 discloses a method using a second buffering path which is somewhat similar to the method currently used. However, this requires multiple switches. Although there is no problem in adopting the technology disclosed herein, a simpler and more flexible method for creating a multistage network is desired.

Multi-tier networks are recognized as a means for interconnecting multiple devices within a computer system. These are alternatives to traditional crossbar interconnects. Crossbars are still the most effective method of network interconnection, but are becoming impractical for large systems. The NxM crossbar enables a total simultaneous interconnection, where all N devices can communicate with different numbers of M devices simultaneously. The crossbar is one M for which the given N devices are IDLE (ie not connected to other N devices).
It is "non-blocking" because it does not have anything inside it that prevents it from being connected to the device. If one N device wants to connect to one M device that is BUSY (ie already connected to another N device), it cannot do that until the previous connection is broken. However, this is a “competition”, not a “block”.

For large values of N and M (typically greater than 32 or 64), the complexity increases at a rate of N × M and their pin counts increase at a rate of (N × M) × W. Therefore, it is very difficult to make a crossbar. Here, W is the number of pins per port. A large-scale network is generally made up of a multi-stage network configured by cascade-connecting several stages of small crossbars to form one extended network. The drawback of a multi-tier network is that it cannot connect to one M device that is IDLE because there is no available path in the network to provide the necessary connection to the IDLE device,
It is a "stop" type.

US Pat. No. 4,914,571 discloses a method of addressing and finding resources to be added to a network, but does not touch the hardware of the actual network itself.

US Pat. No. 4,455,605 is a bus type system, not a multistage network. Similarly, U.S. Pat. No. 4,396,984 shows I / O bus channels rather than multistage networks. U.S. Pat.No. 4,570,
No. 261 is also concerned with disaster recovery via bus-type systems rather than multi-stage networks.

US Pat. No. 4,207,609 relates to I / O bus channels and is not a multistage network.

Although US Pat. No. 4,873,517 is a different type of network overall, it is not the equidistant multi-stage network contemplated by the present invention. Further, U.S. Pat. No. 4,932,021 relates to bus wiring paths within a computer box, not a multi-tier network. U.S. Pat. No. 4,733,391 discloses a ring interconnection network different from a multistage network. Furthermore, U.S. Pat. No. 4,811,201 4811201 discloses a technique that cannot be applied to a multistage network. U.S. Pat. No. 4,754,395 relates to a ring interconnection network.

[0010]

In the conventional multistage network, the problem of blocking has not been solved.

Therefore, it is an object of the present invention to provide a multi-stage network system which can solve the conventional blocking problem.

[0012]

The above problem is solved by creating an alternate path between all N and M devices in the same network. This allows a non-blocking path between two devices to be "rearranged", i.e. detected by the act of trying until a non-blocking connection is made or searching for a different alternate bus. This also allows some of those alternative buses to be used in guaranteed transfers, a special high priority transfer mode that ensures that a connection is made to the IDLE device as soon as possible. In addition, these alternative buses provide a much more fault tolerant network than is provided by known methods.

[0013]

According to the present invention, a single, unidirectional, capable of performing a comprehensive network job including multiple functions,
An unbuffered multi-stage network is provided.

This functional complexity is such that four or more well-known multistage networks are required to perform the same job. The single network shown allows bidirectional traffic, is non-blocking due to alternate buses and reordering, incorporates guaranteed transfers and fault tolerance, and is very compact and inexpensive to implement. It is profitable. Moreover, the network is modular in nature and readily adaptable to systems of any size.

[0015]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT Before entering the description of the drawings, US patent application Ser. No. 07/6
8 × as shown in No. 77,543 (filing date March 29, 1991)
It should be appreciated that ALL-NODE switches such as 8 switches and 4x4 switches are applicable to the present invention. In such a switch, two sets of four data lines are used to make eight data lines, to which the features of the present invention are added. Thus, the switch can be dual priority or dual priority.

The preferred switch is therefore an asynchronous, inter-node, low latency crossbar switch that self-routes serial data transferred through it at the same high rate within two cycle times. In the normal mode of this switch, no synchronization means between any of the input and output ports that interface to the switch is required. This switch does not use any centrally controlled clock and data buffers. Data passing through this switch suffers only three gate delays: on-chip receiver, multiplexer, and off-chip driver. Conflicts are detected and resolved on-chip, logic implementation is simple and gate counts are low (fewer gates). Such a switch includes a plurality of input ports and output ports per node of one network, one connection control circuit for each input port, one multiplexer control circuit for each output port, and I and Z Connect any of the I inputs to any of the Z outputs as two or more unique values.

The basic element of the construction of this multistage network is one 8 × 8 crossbar switch 10 as shown in FIG. This 8x8 crossbar switch is AL
It does not have to be the same as the L-NODE unidirectional switch, but is described here as the same.

The switch is unidirectional in that it can receive inputs from eight different sources and connect them to any of eight different destinations. It can support 8 interconnects simultaneously. By connecting the output port from one crossbar switch to the input port of another crossbar switch in cascade,
It is possible to create multi-stage networks larger than × 8. For the data line 11, any input is the data line 11.
It is connected by a switch 10 so that data can be sent to any output via the. 8 if there are 8 data lines
It is possible to connect up to the same number at the same time. Broadcast is possible, and the broadcast shown in the related application is the preferred mode. Guaranteed transfer is US Patent Application No. 07 / 799,262
Given by HI-PRI, VALID and REJECT controls, as indicated in the issue.

The network itself is unidirectional,
Multiple unidirectional 8x8 crossbar switches (CROSSBAR S
WITCH). Two-way transfer can be performed with only one unidirectional network. This will be described with reference to FIG. 2A showing the interconnection between the N processors shown by the block of the processor 22 and the N memories shown by the block of the memory 23 via the multistage network. Usually, the processors are located on one side of the network and the memory is located on the other side. Therefore, communication between the two requires a unidirectional network 24 in each direction. However, modern parallel processors
A node concept is used where one node contains a processor and memory. That is, the processor and the memory are arranged on the same side of this network as shown in FIG. Thus, one unidirectional network 2
4 allows complete communication between all nodes. As shown in FIG. 2B, each of the N nodes, node 1 and node 2, has two interfaces to this unidirectional network. That is, the interface 26 becomes a data source to the network, and the other interface 27 receives data from the network 24. On the other hand, the source data from any node is two sources: 1) REQUEST (request.
One processor can request memory access from other nodes) or 2) RESPONSE (response; its memory can respond to access requests from other nodes). Therefore, the node needs to time multiplex the two functions into a set of source interface lines to the network by standard multiplexing methods well known to those skilled in the art. Similarly, data destined for any node and coming in through a single incoming connection will be in one of two locations: MEMORY (memory; other nodes can request memory access from this node),
Or 2) PROCESSOR (a processor; other nodes can return the memory access requested by the processor).

In summary, it is possible to support bidirectional communication between all nodes using a single unidirectional network. There are two types of data that travel in this network. That is, sending REQUEST and RESPONSE to other nodes and receiving REQUEST or RESPONSE from other nodes. The most efficient and flexible is this type of network. This is therefore the basic network extended by the present invention for multi-functional integration.

FIG. 3A shows interconnection of 16 nodes (node 1 using a multi-function network composed of four 8 × 8 crossbar switch 10 functional blocks). ~ Node 16 indicates that connection). These 16 nodes are fully interconnected with only partial use of the available crossbar switch output ports. That is, the right side of each of the two 8x8 switches 10A and 10B that receive unidirectional input from 16 nodes is the two 8x8 crossbar switches that send unidirectional output to these 16 nodes. Make two active connections to the left of each of 10C and 10D. As a result, as shown in FIG. 3A, each of the two 8 × 8 switches 10 receiving the unidirectional input from the 16 nodes has 6 unused output ports, and the 16 nodes have a single output port. Two 8s sending directional output
Each of the x8 switches 10 has six unused input ports. This interconnection method gives one path between any two nodes (no alternate path). However, the alternate path has six unused ports 6 in FIG. 3 (B).
It can be made by connecting as shown in.
Here there are four alternative paths 40, 41, 42, 43 that allow any node to connect to any other node. For example, node 1 may have any of four different network connections, namely paths 40, 41, 4
Similarly unidirectional RE to node 7 via 2 or 44
Can be connected to send QUEST or RESPONSE.

This concept of alternative paths can be applied to any number of nodes. For example, in FIG. 4A, one 64-node network having one path 60 to 68 between nodes and no other additional path is formed from two stages.
It shows how to change it to introduce an alternate path. FIG. 4 (B) shows a network in which one stage is added to form a three-stage network, which is expanded to form eight alternative paths.

This network is applied as a multi-stage network that creates alternative paths and uses those alternative paths by reordering to bypass the blocking portion of the network. Devices that send data to this network select one alternate path randomly or based on the lower order address bits of the node accessed through this network. This data sending node will attempt to connect to the node receiving it via the selected alternate path. If the path is blocked, the node receives a REJECT indication. At this time, the path selection decision is rearranged and a different alternative path is selected. This selection is made randomly or by storing the least significant bit of the node being addressed by the binary counter, incrementing this counter by +1 each time a REJECT indication comes in, and defined by this binary counter. The method of this embodiment is adapted to retry the connection via the newly selected alternate path. This reordering can continue indefinitely because the counter circulates, thus retrying alternate paths one after another or randomly until the blocking is successfully bypassed. Figure 3
The network for making four alternative paths in (B) first selects one path based on the lower two digit address bits of the addressed node, and stores those two bits in a two-bit counter to expand the rearrangeability. ..

Heidelberger and Franazek are “Traffic Studies of Unbuffer”
ed Delta Networks ”(RC14103 (# 63219), Computer Science, 10/17/88, and IBM Technical
Journal, January 1991) shows the existence of two types of simulated network traffic, "Hot" and "Cold". "Cold" is random traffic and "hot" is traffic that is concentrated on one particular node. According to this study, "cold" traffic was found in one of the first few trials of rearrangement.
Pass through the network with a very high probability. However, this is less likely to be successfully transferred on each retry and tends to interfere with the network "hot".
Not true for traffic. Therefore, although the rearrangement method of the present invention can be effectively applied to "cold" traffic in unbuffered networks, something needs to be added to handle "hot" traffic.

A solution to the problem of "hot" traffic is to limit that "hot" traffic to a particular alternate path and "cold" as it is transmitted over other alternate paths.
It is important not to affect the traffic. Furthermore,
Regular and efficient to be processed as quickly as possible, and starvation of any particular node
What is needed is a way to handle "hot" traffic to prevent (blocking the connection of a particular node to a node experiencing "hot" traffic). The method of providing the required regular service of "hot" traffic and the prevention of starvation is called "guaranteed transfer" or "high priority mode". This is shown in US patent application Ser. No. 07 / 799,262. In this application, the second level of network interoperability is defined as a high priority network operation mode that reserves a partial path for "hot" transmission to a blocking point. In this high priority mode, the stage gets the right to interrupted "hot" traffic as soon as the blocked stage becomes available. The transmitter is informed that the block has been cleared and a retry will only occur at the earliest time and when guaranteed use of the previously blocked stage. Details of this point are about 0 in the above-mentioned application.

Thus, the total rearrangement method performed by this multifunctional network efficiently handles both "hot" and "cold" traffic as follows.

1) Assuming that the traffic is "cold" in the first few attempts, it will traverse the network based on the random selection of alternative paths or the lowest address bits of the node receiving the message, as described above. Make the first connection. If the alternative path originally selected is not blocked, the connection is successful and "cold traffic" is sent. However, if this first alternative path has blocking, the multifunction network will reject the connection. As described above, the second alternative path is randomly selected by the hardware by automatically increasing the lowest address bit of the address of the receiving node. It retries in the same way until it succeeds, makes a connection and makes a network transfer. In general,
The discovery of the non-blocking path and the subsequent message transmission through the multifunctional network all occur for "cold" traffic.

2) There is a need for a means to detect "hot" traffic and switch the mode of transmission through the multifunction network to a second and more efficient mode by handling "hot" traffic. The reordering retry counter counts the number of times a message has been attempted through the network (the number of alternate path selections made). A programmable threshold is placed in this retry counter,
Causes traffic to be reclassified as "hot" traffic again after the number of retries defined by this threshold has been exceeded. For example, assume that this retry threshold is set to a total of three attempts in making one connection as "cold" traffic through the network. This time the message is reclassified as "hot" traffic after the third failed attempt,
And new methods for transfer through multi-function networks come into play. The transfer reordering (“cold”) method is replaced by the “guaranteed transfer” (“hot”) method.

3) "Guaranteed Transfer" is one of two methods: a) chooses one or several alternative paths that receive all "hot" traffic and no "cold" traffic. Or
b) "hot" traffic and "cold" on the same alternate path by selecting the "hot" path based on the least significant node address bits (the same bits that limited the first path to be tried in the rearrangement method). This can be done by mixing the traffic. The latter is the preferred embodiment for explaining the present invention. For this method, the path selected for "hot" traffic is forced into a guaranteed transfer mode. The advantage of this method is that all traffic to a "hot" node is the same alternative path regardless of the number of nodes trying to send a message to that node because the selection of the "hot" alternative path is based on the node address. Is to be forced to. This frees all other alternative paths for "cold" traffic, and limits the "hot" traffic block to one "hot" alternative path (although it may be several or even simultaneously experiencing "hot" traffic). It is possible to have several or many alternate paths operating simultaneously in “hot” mode for many nodes, and there is no limit to the number of alternate paths that can operate simultaneously in “hot” or “cold” mode. ..). Multiple "hot" spots require the occupancy of more than one alternate path if the lowest node address bits are different for different hotspots, but this method still makes multiple "hot" spots efficient. It will be processed well. In addition, during normal reordering, it is possible to try to use the "hot" alternate path for some "cold" traffic, but it is rejected and subsequent reordering will cause the "cold" alternate path through the network. Will continue to look for.

Another advantage of this method is that in the absence of "hot" traffic, all alternate paths can be used to handle "cold" traffic for the case of regular random traffic. .. Thus, in the normal case all alternative paths can be used to increase the bandwidth of the network.

FIG. 5 shows simple hardware for reordering, hot spot detection and switching to a guaranteed transfer mode. FIG. 5 illustrates hardware that enables detection of non-blocking paths through a multi-tiered network and the detour of "hot" spots in network traffic using one method that is automatic and transparent with respect to software. .. The one shown is for controlling four alternate paths, this hardware includes two 1-bit multiplexers (MUX-2 and MUX-3) and two counters (retry counter 4 and alternate path control counter 5). ) Only. These multiplexers provide an output consisting of two encoded bits which, at any given time, determine which of these four alternative paths should be selected. The multiplexers 2 and 3 are controlled from a retry counter 4 which is reset to 0 at the start of each new message. Counters 4 and 5 are incremented based on the REJECT signal indicating that the attempted path was blocked and the next REJECT indication was issued. Retry counter 4
If the count of 0 is 0 or 1, the control of the multiplexer selects the alternate path number that is the output of counter 5, which causes the rearrangement. For all other values of the retry counter 4, the multiplexer control selects an alternate path number from the lowest address bits of the receiving node's address stored in the node address register 1. Thus, for the first attempted and guaranteed transfer, the alternate path number comes from the least significant bit of node address register 1. If the content of the retry counter 4 is 3 or more, "hot" traffic detection is performed and the transfer mode guaranteed by this hardware is entered. The control counter 5 is loaded with the lower bit of the node address register 1 which is incremented for each rejection during the first attempt.

This alternative path method is also a single path system because many element or wiring failures use only one or a few of the alternative paths, leaving some available paths. It is more tolerant of disabilities compared to.

If high tolerance to failure or greater network bandwidth is required, then multiple copies of the above simple network can be made with each copy making its own set of alternate paths.

[0034]

According to the present invention, it is possible to construct a single / unidirectional non-buffer multistage network capable of performing a comprehensive network job including multiple functions. Moreover, the network according to the invention is modular in nature and can easily be adapted to systems of any size.

[Brief description of drawings]

FIG. 1 shows the basic elements of the network which are 8 × 8 crossbar switches.

FIG. 2A is a diagram showing a connection of N processors to N memories via a multi-stage network, and FIG. 2B is a node type embodiment in which processors and memories are arranged on the same side of the network. Fig.

FIG. 3A is a diagram showing the interconnection of 16 nodes using one multifunctional network consisting of four 8 × 8 crossbar switch chips, and FIG. 3B was not previously used. The figure which shows the alternative path which can be made by connecting a port.

FIG. 4 (A) is a diagram showing a 64-node network having two stages with one path between nodes and no additional path, and FIG. The figure which shows what was applied to a 32-node system as a stage network, and was made so that eight alternative paths could be given between arbitrary two nodes.

FIG. 5 shows simple hardware for reordering, hotspot detection and switching to guaranteed transfer mode.

[Explanation of symbols]

 10 crossbar switch 11 data line 22 processor 23 memory 24 unidirectional network 26, 27 interface 40, 41, 42, 43 alternative path 60-68 path

 ─────────────────────────────────────────────────── ─── Continuation of the front page (72) Inventor Thomas, Norman, Barker, New York, USA, Vestal, Sunset, Avenue, 136 (72) Inventor Peter, Anthony, Franacek New York, USA, Katna, Pine, Tree, Drive (No house number) (72) Inventor Philip, Heidelberger, New York, USA, Peakskill, Lakeview, Avenue, West, 24 (72) Inventor Bukharat, Deep, Lathi New York, USA Mahopack, Lakeview, Drive, Route, 8,167-Sea (72) Inventor Anoujan, Mangala, Balma San, California, United States , Cruz, Hager, coat, 102

Claims (9)

[Claims] 1. A multi-stage network means for interconnecting a plurality of system elements configured to use a network for communication between a plurality of system elements, and any two optional devices added to the network. A multi-stage network system comprising alternative path means for providing the network with a plurality of alternative paths through which commands and messages can be sent between system elements. 2. The system of claim 1, further comprising reordering means for detecting different alternate paths in the network by detection of blocking conditions until non-blocking connections are made between system elements. 3. Allocation means for allocating some of said alternative paths as to be used for guaranteed transfers and for allocating some of said alternative paths. The system of claim 1 comprising. 4. The system of claim 1, further comprising a unique interface line provided between each system element to distinguish the guaranteed transfer alternate path from the normal network path. 5. The system of claim 1 further comprising alternate path means for providing fault tolerance to the network and enabling bypass of a faulty component. 6. The system of claim 1, further comprising an unused connection or additional stage path used to form an alternative path for communication between system elements of the network. 7. Retry counter means for controlling the automatic switch to a guaranteed transfer mode when one path between system elements is blocked or disabled. 1 system. 8. Retry means for retrying a path between system elements over a number of paths and through the same path when routing between system elements is not found for the requested communication. The system of claim 1, wherein: 9. An integrated function that finds one non-blocking path through a multi-tiered network and bypasses "hot" spots in network traffic is made in hardware and is completely selected, automatic and transparent to software. The system of claim 1 performed on.