Multiple level minimum logic network Number:7,426,214 from the United States Patent and Trademark Office (PTO) owispatent A network or interconnect structure 100 utilizes a data flow technique that is based on timing and positioning of messages communicating through the interconnect structure. Switching control is distributed throughout multiple nodes 102 in the structure so that a supervisory controller providing a global control function and complex logic structures are avoided. The interconnect structure operates as a "deflection" or "hot potato" system in which processing and storage overhead at each node is minimized. Elimination of a global controller and buffering at the nodes greatly reduces the amount of control and logic structures in the interconnect structure, simplifying overall control components and network interconnect components 104 and improving speed performance of message communication.<H Multiple, network, Multiple, level, , 7426214.html, Patent, pto, 7426214

Title: Multiple level minimum logic network

Abstract: A network or interconnect structure 100 utilizes a data flow technique that is based on timing and positioning of messages communicating through the interconnect structure. Switching control is distributed throughout multiple nodes 102 in the structure so that a supervisory controller providing a global control function and complex logic structures are avoided. The interconnect structure operates as a "deflection" or "hot potato" system in which processing and storage overhead at each node is minimized. Elimination of a global controller and buffering at the nodes greatly reduces the amount of control and logic structures in the interconnect structure, simplifying overall control components and network interconnect components 104 and improving speed performance of message communication.

Patent Number: 7,426,214 Issued on 09/16/2008 to Reed

Inventors: Reed; Coke S. (Cranbury, NJ)
Assignee: Interactic Holdings, LLC (New York, NY)

Appl. No.: 10/773,693

Filed: June 16, 2004

Related U.S. Patent Documents


Application Number	Filing Date	Patent Number	Issue Date
09852009	May., 2001	7068671
09850953	May., 2001
09397333	Sep., 1999	6272141
08505513	Jul., 1995	5996020

Current U.S. Class: 370/404 ; 370/258; 709/238

Current International Class: H04L 12/28 (20060101); H04L 12/56 (20060101)

Field of Search: 370/404,258

References Cited [Referenced By]

U.S. Patent Documents


5684959	November 1997	Bhat et al.
5715251	February 1998	Du
5737320	April 1998	Madonna
5781551	July 1998	Born

Primary Examiner: Nguyen; Brian D
Attorney, Agent or Firm: Koestner Bertani LLP Koestner; Ken J.

Parent Case Text

RELATED APPLICATIONS

This application is a continuation of Ser. No. 09/852009 filed May 7, 2001 U.S. Pat. No. 7,068,671, a division of U.S. patent application Ser. No. 09/850,953, filed May 7, 2001 now abandoned, and a division of Ser. No. 09/397333, filed Sep. 14, 1999 U.S. Pat No. 6,272,141 and Ser. No. 08/505513 filed Jul. 21, 1995 U.S. Pat. No. 5,996,020, all entitled "Minimum Level Minimum Logic Network", invented by Coke S. Reed, claiming an earliest effective filing date of Jul. 21, 1995.

Claims

The invention claimed is:

1. An interconnect structure S containing a plurality of nodes and a plurality of interconnects selectively coupling the nodes, the interconnect structure S comprising: a node set T; an interconnect set I that selectively connects nodes in the node set T; a device set A mutually exclusive of the node set T with each device in the device set A sending data to one or more nodes in the node set T; a device set Z mutually exclusive of the node set T with each device in the device set Z receiving data from one or more nodes in the node set T; and a collection C of node subsets of the node set T, each node in the node set T being contained in exactly one member of the collection C such that: for a device x in the device set Z, a sequence cx=cx.sub.0, cx.sub.1, cx.sub.2, . . . , cx.sub.J exists with each member of the sequence cx being a node set in the collection C, the sequence cx passing data from devices in the device set A to the device x on a plurality of paths, among the plurality of paths being a path set P(x) characterized in that a path R is included in the path set P(x) only if each node on the path R is in a member of the sequence cx, a node of the path R that receives a message directly from a device in the device set A being a member of node set cx.sub.L and a node of the path R that sends data directly to the device x being a member of node set cx.sub.V with U being larger than V; for a member Y of the collection C, a corresponding set of devices Z(Y) exists in the device set Z such that a device y is included in the set of devices Z(Y) only if the member Y is also a member of a sequence cy; for members cx.sub.H and cx.sub.K of the sequence cx with H>K, a device set Z(cx.sub.K) is a subset of a device set Z(cx.sub.H); the sequence cx includes two members cx.sub.L and cx.sub.m with L>M and with a device set Z(cx.sub.M) being a subset of a device set Z(cx.sub.L) and a device exists in the device set Z(cx.sub.L) that is not included in the device set Z(cx.sub.M); and the node set T includes three distinct nodes p, q, and r, the node p being in a member cx.sub.D of the sequence cx, the nodes q and r being in a member cx.sub.E of the sequence cx with D>E, in one path of the plurality of paths P(x) a message moves directly from the node, p to the node r and in another path of the plurality of paths P(x) a message moves directly from the node q to the node r.

2. An interconnect structure according to claim 1 wherein: the plurality of paths of the sequence cx include a path such that if a message hops from a node in a member cx.sub.n to a node in a member cx.sub.m, then n>m.

3. An interconnect structure according to claim 1 further comprising: an arrangement of the nodes in the interconnect structure into a hierarchy of levels of node sets LV=LV.sub.0, LV.sub.1, . . . LV.sub.J, each member of the hierarchy LV being a node set that is subset of the node set T and each node in the node set T is contained in exactly one member of the node sets LV; and for the device x of the device set Z a node set cx.sub.N is a subset of a level N node set L.sub.N, with N not exceeding J.

4. An interconnect structure according to claim 3 wherein: the collection C includes 2.sup.J-N members on a level N; the collection C includes three members D, E and F such that member node set D is on a level LV.sub.N and member node sets E and F are on a level LV.sub.N-1; the interconnect set I includes interconnects positioned to allow data to pass directly from the member node set D to the member node set E and to pass directly from the node set D to the node set F; and the device set Z includes device sets Z(D), Z(E), and Z(F) that correspond to the three members D, E, and F, the device sets Z(E) and Z(F) being mutually exclusive device sets, and the device set Z(D) is the union of the device sets Z(E) and Z(F).

5. An interconnect structure according to claim 1 further comprising: a logic L.sub.p associated with the node p wherein for a message Mp that arrives at the node p, the logic Lp uses information concerning the sending of messages from the node q for the logic Lp to determine where the node p is to send the message Mp.

6. An interconnect structure according to claim 1 wherein: the node q has priority over the node p to send data to the node r so that a message Mq located at the node q is not blocked from being sent to the node r by a message Mp at the node p; and the node q sends a control signal to the node p wherein the purpose of the control signal is to enforce the priority of the node q over the node p to send data to the node r.

7. An interconnect structure according to claim 1 wherein: the node set T includes a node s distinct from the nodes p, q, and r, the node s being in the member cx.sub.D, so that in one path of the plurality of paths P(x), a message moves from the node p directly to the node s.

8. An interconnect structure comprising: a plurality of nodes including a node N.sub.E and a node set P, the node set P including a plurality of nodes that send data to the node N.sub.E; and a plurality of interconnect paths interconnecting the plurality of nodes, the interconnect paths including data interconnect paths that couple nodes in pairs, a node pair including a sending node and a receiving node, the sending node sending data to the receiving node; the nodes in the node set P having a priority relationship for sending data to the node N.sub.E, the nodes in the node set P including distinct nodes N.sub.F and N.sub.A, the node N.sub.F having a highest priority among the nodes in the node set P for sending data to the node N.sub.E so that a message M.sub.F arriving at the node N.sub.F is not blocked from traveling to the node N.sub.E by a message M.sub.A arriving at the node N.sub.A; and for a message M arriving at the node N.sub.A and the message M is blocked front being sent to the node N.sub.E, then the blocking of the message M from being sent to the node N.sub.E causes sending of the message M from the node N.sub.A to a node distinct from the node N.sub.E, wherein: when a message M arrives at the node N.sub.A and is targeted for the node N.sub.E and not blocked by a message M' arriving at a node in the node set P having a higher priority than the node N.sub.A for sending messages to the node N.sub.E, the node N.sub.A sends the message M to the node N.sub.E.

9. An interconnect structure S containing a plurality of nodes and a plurality of interconnects selectively coupling the nodes, the interconnect structure comprising: a node set T; an interconnect set I that selectively connects nodes in the node set T; a device set A mutually exclusive with the node set T with each device in the device set A sending data to a node in the node set T; a device set Z mutually exclusive with the node set T with each device in the device set Z receiving data from a node in the node set T; a set of data paths P, each path of the path set P carrying data from a device in the device set A to a device in the device set Z, each node on the path of the path set P, is included in the node set T, and each interconnect in the path is included in the interconnect set I; a node set U characterized as the set of nodes within the node set T that are on a path included in the path set P; for a node N in the node set T such that the node N is on a path in the path set P, a corresponding set of devices Z(N) exists in the device set Z such that a device w is included in the device set Z(N) only if a path exists in the path set P from a member of the device set A to the device w such that the path contains the node N; the node set U includes three distinct nodes N.sub.A, N.sub.D, and N.sub.E such that the node N.sub.A sends data to the node N.sub.D and the node N.sub.E, and a device set Z(N.sub.A) is the same as a device set Z(N.sub.D), and a device set Z(N.sub.E) is a proper subset of the device set Z(N.sub.A); an interconnect link IL in interconnect set I, the interconnect link IL being an interconnect link on a path in the path set P such that a corresponding set of devices Z(IL) exists in the device set Z such that a device w is included in the device set Z(IL) only if a path containing the interconnect link IL in the path set P exists from a device in the device set A to the device w; and the node set U includes distinct nodes N.sub.A, N.sub.D, and N.sub.E such that the node N.sub.A sends data to the node N.sub.D on a link L.sub.AD, the node N.sub.A sends data to the node N.sub.E on a link L.sub.AE, and a device set Z(L.sub.AE) is a proper subset of a device subset Z(L.sub.AD).

10. An interconnect structure S comprising: a plurality of nodes including nodes N.sub.A, N.sub.D, and N.sub.E; a plurality of interconnect lines selectively coupling the nodes in the structure S; a plurality of devices in a device set I that is mutually exclusive of the plurality of nodes, the devices in the device set I sending data to one or more of the plurality of nodes; and a plurality of devices in a device set Z that is mutually exclusive of the plurality of nodes, the devices in the device set Z receiving data from one or more of the plurality of nodes, the device set Z comprising a plurality of device subsets further comprising: a device subset T.sub.A consisting of devices t.sub.A such that a message can be sent from a device in the device set I through the node N.sub.A to the devices t.sub.A; a device subset T.sub.D consisting of devices t.sub.D such that a message can be sent from a device in the device set I through the node N.sub.A to the devices t.sub.D; and a device subset T.sub.E consisting of devices t.sub.E such that a message can be sent from a device in the device set I through the node N.sub.E to the devices t.sub.E; wherein: the node N.sub.A sends data to the node N.sub.D; the node N.sub.A sends data to the node N.sub.E; the devices in the device subset T.sub.A are included in the device subset T.sub.D; and a device t.sub.A exists that is included in the device subset T.sub.A and excluded from the device subset T.sub.E.

11. An interconnect structure S according to claim 10 further comprising: a logic L that controls passage of messages sent through the interconnect structure S, wherein: a plurality of messages P can be sent to a plurality of nodes from a plurality of devices in the device set I; the plurality of messages P includes a message M.sub.A having a target device in the device subset T.sub.A; and the logic L routs the message M.sub.A through the node N.sub.A to a device in the device subset T.sub.A.

12. An interconnect structure S according to claim 11 wherein: the message M.sub.A has a header; and the logic L routs the message M.sub.A through the interconnect structure S using information in the header of the message M.sub.A.

13. An interconnect structure S according to claim 11 wherein: the logic L is distributed among one or more nodes of the plurality of nodes; the plurality of nodes includes a node N; and logic of the logic L associated with the node N uses control signals to route messages though the node N.

14. An interconnect structure S containing a plurality of nodes and a plurality of interconnects selectively coupling the nodes, the interconnect structure S comprising: a node set T including three distinct nodes N.sub.A, N.sub.D, and N.sub.E; a device set I mutually exclusive of the node set T and containing devices that send data to at least one node in the node set T; a device set Z mutually exclusive of the node set T and containing devices that receive data from at least one node in the node set T; a plurality of paths P that carry data through the interconnect structure S to devices in the device set Z; a device subset T.sub.A exists such that a message can be sent on a path in the paths P from a device in the device set I through the node N.sub.A to a device in the device subset T.sub.A; a device subset T.sub.D exists such that a message can be sent on a path in the paths P from a device in the device set I through the node N.sub.D to a device in the device subset T.sub.D; a device subset T.sub.E exists such that a message can be sent on a path in the paths P from a device in the device set I through the node N.sub.E to a device in the device subset T.sub.E; wherein: the node N.sub.A sends data to the node N.sub.D along a path in the paths P; the node N.sub.A sends data to the node N.sub.E along a path in the paths P; the devices in the device subset T.sub.A are included in the device subset T.sub.D; and a device exists that is included in the device subset T.sub.A that is not included in the device subset T.sub.E.

15. An interconnect structure S according to claim 14 further comprising: a logic L.sub.A associated with the node N.sub.A controls data flow from the node N.sub.A.

16. An interconnect structure S containing a plurality of nodes and a plurality of interconnects selectively coupling the nodes, the interconnect structure S comprising: a node set T including three distinct nodes N.sub.A, N.sub.C, and N.sub.E; a device set I mutually exclusive of the node set T and containing devices that send data to at least one node in the node set T; a device set Z mutually exclusive of the node set T and containing devices that receive data from at least one node in the node set T; a plurality of paths P that carry data through the interconnect structure S to devices in the device set Z; a device subset T.sub.A exists such that a message can be sent on a path in the paths P from a device in the device set I through the node N.sub.A to a device in the device subset T.sub.A; a device subset T.sub.C exists such that a message can be sent on a path in the paths P from a device in the device set I through the node N.sub.C to a device in the device subset T.sub.C; a device subset T.sub.E exists such that a message can be sent on a path in the paths P from a device in the device set I through the node N.sub.E to a device in the device subset T.sub.E; wherein: the node N.sub.C sends data to the node N.sub.E along a path in the paths P; the node N.sub.A sends data to the node N.sub.E along a path in the paths P; the devices in the device subset T.sub.C are included in the device subset T.sub.E; and a device exists that is included in the device subset T.sub.A that is not included in the device subset T.sub.E.

17. An interconnect structure S according to claim 16 further comprising: a logic L.sub.A associated with the node N.sub.A controls data flow from the node N.sub.A.

18. An interconnect structure S according to claim 17 wherein: a message M arriving at the node N.sub.A has a header and the logic L.sub.A uses information in the header to decide where to send the message M.

19. An interconnect structure S according to claim 17 wherein: the logic L.sub.A uses information from the node N.sub.C to decide where to send the message M.

Description

FIELD OF INVENTION

The present invention relates to interconnection structures for computing and communication systems. More specifically, the present invention relates to multiple level interconnection structures in which control and logic circuits are minimized.

BACKGROUND OF THE INVENTION

Many advanced computing systems, including supercomputers for example, utilize multiple computational units to improve performance in what is called a parallel system. The system of interconnections among parallel computational units is an important characteristic for determining performance. One technique for interconnecting parallel computational units involves construction of a communication network similar to a telephone network in which groups of network elements are connected to switching systems. The switching systems are interconnected in a hierarchical manner so that any switching station manages a workable number of connections.

One disadvantage of a network connection is an increase in the latency of access to another computational unit since transmission of a message traverses several stages of a network. Typically, periods of peak activity occur in which the network is saturated with numerous messages so that many messages simultaneously contend for the use of a switching station. Various network types have been devised with goals of reducing congestion, improving transmission speed and achieving a reasonable cost. These goals are typically attained by rapidly communicating between nodes and minimizing the number of interconnections that a node must support.

One conventional interconnection scheme is a ring of nodes with each node connected to two other nodes so that the line of interconnections forms a circle. The definition of a ring, in accordance with a standard definition of a ring network in the art of computing (IBM Dictionary of Computing, McDaniel G. ed., McGraw-Hill, Inc., 1994, p. 584) is a network configuration in which devices are connected by unidirectional transmission links to form a closed path. Another simple conventional scheme is a mesh in which each node is connected to its four nearest neighbors. The ring and mesh techniques advantageously limit the number of interconnections supported by a node. Unfortunately, the ring and mesh networks typically are plagued by lengthy delays in message communication since the number of nodes traversed in sending a message from one node to another may be quite large. These lengthy delays commonly cause a computational unit to remain idle awaiting a message in transit to the unit.

The earliest networks, generally beginning with telephone networks, utilize circuit switching in which each message is routed through the network along a dedicated path that is reserved for the duration of the communication analogous to a direct connection via a single circuit between the communicating parties. Circuit switching disadvantageously requires a lengthy setup time. Such delays are intolerable during the short and quick exchanges that take place between different computational units. Furthermore, a dedicated pathway is very wasteful of system bandwidth. One technique for solving the problems arising using circuit switching is called packet switching in which messages sent from one computational unit to another does not travel in a continuous stream to a dedicated circuit. Instead, each computational unit is connected to a node that subdivides messages into a sequence of data packets. A message contains an arbitrary sequence of binary digits that are preceded by addressing information. The length of the entire message is limited to a defined maximum length. A "header" containing at least the destination address and a sequence number is attached to each packet, and the packets are sent across the network. Addresses are read and packets are delivered within a fraction of a second. No circuit setup delay is imposed because no circuit is set up. System bandwidth is not wasted since there is no individual connection between two computational units. However, a small portion of the communication capacity is used for routing information, headers and other control information. When communication advances in isolated, short bursts, packet switching more efficiently utilizes network capacity. Because no transmission capacity is specifically reserved for an individual computational unit, time gaps between packets are filled with packets from other users. Packet switching implements a type of distributed multiplexing system by enabling all users to share lines on the network continuously.

Advances in technology result in improvement in computer system performance. However, the manner in which these technological advances are implemented will greatly determine the extent of improvement in performance. For example, performance improvements arising from completely optical computing strongly depend on an interconnection scheme that best exploits the advantages of optical technology.

SUMMARY OF THE INVENTION

In accordance with the present invention, a multiple level minimum logic network interconnect structure has a very high bandwidth and low latency. Control of interconnect structure switching is distributed throughout multiple nodes in the structure so that a supervisory controller providing a global control function is not necessary. A global control function is eliminated and complex logic structures are avoided by a novel data flow technique that is based on timing and positioning of messages communicating through the interconnect structure. Furthermore, the interconnect structure implements a "deflection" or "hot potato" design in which processing and storage overhead at each node is minimized by routing a message packet through an additional output port rather than holding the packet until a desired output port is available. Accordingly, the usage of buffers at the nodes is eliminated. Elimination of a global controller and buffering at the nodes greatly reduces the amount of control and logic structures in the interconnect structure, simplifying overall control components and network interconnect components, improving speed performance of message communication and potentially reducing interconnection costs substantially. Implementation of the interconnect structure is highly flexible so that fully electronic, fully optical and mixed electronic-optical embodiments are achieved. An implementation using all optical switches is facilitated by nodes exploiting uniquely simple logic and elimination of buffering at the nodes.

The multiple level minimum logic network interconnect architecture is used for various purposes. For example, in some embodiments the architecture is used as an interconnect structure for a massively parallel computer such as a supercomputer. In other exemplary embodiments, the architecture forms an interconnect structure linking a group of workstations, computers, terminals, ATM machines, elements of a national flight control system and the like. Another usage is an interconnect structure in various A telecommunications applications or an interconnect structure for numerous schedulers operating in a business main frame.

In accordance with one aspect of the present invention, an interconnect apparatus includes a plurality of nodes and a plurality of interconnect lines selectively connecting the nodes in a multiple level structure in which the levels include a richly interconnected collection of rings. The multiple level structure includes a plurality of J+1 levels in a hierarchy of levels and a plurality of 2.sup.JK nodes at each level. If integer K is an odd number, the nodes on a level M are situated on 2.sup.J-M rings with each ring including 2.sup.MK nodes. Message data leaves the interconnect structure from nodes on a level zero. Each node has multiple communication terminals. Some are message data input and output terminals. Others are control input and output terminals. For example, a node A on level 0, the innermost level, receives message data from a node B on level 0 and also receives message data from a node C on level 1. Node A sends message data to a node D on level 0 and also sends message data to a device E that is typically outside the interconnect structure. One example of a device E is an input buffer of a computational unit. Node A receives a control input signal from a device F which is commonly outside the interconnect structure. An example of a device F is an input buffer of a computational unit. Node A sends a control signal to a node G on level 1.

All message data enters the interconnect structure on an outermost level J. For example, a node A on level J, the outermost level, receives message data from a node B on level J and also receives message data from a device C that is outside the interconnect structure. One example of device C is an output buffer of a computational unit. Node A sends message data to a node D on level J and also sends message data to a node E on level J-1. Node A receives a control input signal from a node F on level J-1. Node A sends a control signal to a device G that is typically outside the interconnect structure. An example of a device G is an output buffer of a computational unit.

Nodes between the innermost level 0 and the outermost level J communicate message data and control signals among other nodes. For example, a node A on a level T that is neither level 0 or level J receives message data from a node B on level T and also receives message data from a node C on level T+1. Node A sends message data to a node D on level T and also sends message data to a node E on level T-1. Node A receives a control input signal from a node F on level T-1. Node A sends a control signal to a node G on level T+1. Level M has 2.sup.j-m rings, each containing 2.sup.MK nodes for a total of 2.sup.JK nodes on level M. Specifically: Level 0 has 2.sup.j rings, each containing 2.sup.0K=K nodes for a total of 2.sup.jK nodes on level 0. Level 1 has 2.sup.j-1 rings, each containing 2.sup.1K=2K nodes for a total of 2.sup.jK nodes on level 1. Level 2 has 2.sup.j-2 rings, each containing 2.sup.2K=4K nodes for a total of 2.sup.jK nodes on level M. Level J-2 has 2.sup.j-(J-2) =4 rings, each containing 2.sup.(J-2) K nodes for a total of 2.sup.JK nodes on level J-2. Level J-1 has 2.sup.J-(J-1)=2 rings, each containing 2.sup.(J-1)K nodes for a total of 2.sup.JK nodes on level J-1. Level J has 2.sup.J-J =1 ring containing 2.sup.(J-0) K nodes for a total of 2.sup.JK nodes on level J.

For a ring R.sub.T on a level T which is not the outermost level J, then one ring R.sub.T+1 on level T+1 exists such that each node A on ring R.sub.T receives data from a node B on ring R.sub.T and a node C on ring R.sub.T+1. For a ring R.sub.T on a level T which is not the innermost level 0, then there exist exactly two rings R1.sub.T-1 and R2.sub.T-1 on level T-1 such that a node A on ring R.sub.T sends message data to a node D on ring R.sub.T and a node E on either ring R1.sub.T-1 or ring R2.sub.T-1. A message on any level M of the interconnect structure can travel to two of the rings on level M-1 and is eventually able to travel to 2.sup.M of the rings on level 0.

In the following discussion a "predecessor" of a node sends message data to that node. An "immediate predecessor" sends message data to a node on the same ring. A "successor" of a node receives message data from that node. An "immediate successor" receives message data to a node on the same ring.

For a node ART on ring RT on level T, there are nodes BRT and DRT on ring RT of level T such that node BRT is an immediate predecessor of node ART and node DRT is an immediate successor of node ART. Node ART receives message data from node BRT and sends message data to node DRT. Node ART receives message data from a device C that is not on the ring RT and sends data to a device E that is not on ring RT. If the level is not the innermost level 0, then device E is a node on level T-1 and there is an immediate predecessor node F on the same ring as device E. Node ART receives control information from device F. If node ART is on node T equal to zero, then device E is outside the interconnect structure and device E sends control information to node ART. For example, if device E is an input buffer of a computational unit, then the control information from device E to node ART indicates to node ART whether device E is ready to receive message data from node ART. Node DRT receives message data from a device G that is not on ring RT. Node ART sends a control signal to device G.

Control information is conveyed to resolve data transmission conflicts in the interconnect structure. Each node is a successor to a node on the adjacent outer level and an immediate successor to a node on the same level. Message data from the immediate successor has priority. Control information is send from nodes on a level to nodes on the adjacent outer level to warn of impending conflicts.

When the levels are evenly spaced and the nodes on each ring and each level are evenly spaced, the interconnect structure forms a three-dimensional cylindrical structure. The interconnect structure is fully defined by designating the interconnections for each node A of each level T to devices or nodes B, C, D, E, F and G. Each node or device has a location designated in three-dimensional cylindrical coordinates (r,e,z) where radius r is an integer which specifies the cylinder number from 0 to J, angle e is an integer multiple of 2 /K, which specifies the spacing of nodes around the circular cross-section of a cylinder from 0 to K-1, and height z is a binary integer which specifies distance along the z-axis from 0 to 2.sup.J-1. Height z is expressed as a binary number because the interconnection between nodes in the z-dimension is most easily described as a binary digit manipulation. On the innermost level 0, one ring is spanned in one pass through the angles e from 0 to K-1 and each height z designates a ring. On level 1, one ring is spanned in two passes through the angles e and two heights z are used to designate one ring. The ring structure proceeds in this manner through the outermost ring J in which one ring is spanned in all 2.sup.J heights along the z-axis.

Node A on a ring R receives message data from a node B, which is an immediate predecessor of node A on ring R. For a node A located at a node position N(r,e,z), node B is positioned at N(r, (e-1)mod K,H.sub.r(z)) on level r. (e-1)mod K is equal to K-1 when e is equal to 0 and equal to e-1 otherwise. The conversion of z to H.sub.r(z) on a level r is described for z=[z.sub.J-1, z.sub.J-2, . . . , z.sub.r, z.sub.r-1, . . . , z.sub.2, z.sub.1, z.sub.0] by reversing the order of low-order z bits from z.sub.r-1 to z.sub.0] into the form z=[z.sub.J-1, z.sub.J-2, . . . , z.sub.r, z.sub.0, z.sub.1, z.sub.2, . . . , z.sub.r-1], subtracting one (modulus 2.sup.r) from the low-order bits and reversing back the modified low-order z bits.

Node A also receives message data from a device C which is not on level r. If node A is positioned on the outermost level r=J, then device C is outside of the interconnect structure. If node A is not positioned on the outermost level, then device C is a node located at position N(r+1,(e-1)mod K,z) on level r+1.

Node A sends message data to a node D, which is an immediate successor to node A on ring R. Node D is located at node position N(r, (e+1)mod K,h.sub.r(z)) on level r. (e+1)mod K is equal 0 when e is equal to K-1 and equal to e+1 otherwise. The conversion of z to h.sub.r(z) on a level r is described for z=[z.sub.J-1, z.sub.J-2, . . . , z.sub.r, z.sub.r-1, . . . , z.sub.2, z.sub.1, z.sub.0] by reversing the order of low-order z bits from z.sub.r-1 to z.sub.0] into the form z=[z.sub.J-1, z.sub.J-2, . . . , z.sub.r, z.sub.0, z.sub.1, z.sub.2, . . . , z.sub.r-1], adding one (modulus 2.sup.r) to the low-order bits and reversing back the low-order z bits.

Note that the term hr looks forward in z and the term H.sub.r looks backward. Thus, h.sub.r and H.sub.r are mutual inverse so that H.sub.r(h.sub.r(z))=h.sub.r(H.sub.r(z))=z.

Node A also sends message data to a device E that is not on the same level r as node A. If node A is on the innermost level r=0, node A at node position N(r,e,z) is interconnected with a device (e.g. a computational unit) outside of the interconnect structure. Otherwise, node A is interconnected to send message data to device E, which is a node located at node position N(r-1, (e+1)mod K,z) on level r-1.

Node A receives control information from a device F. If node A is on the innermost level r=0, the device F is the same as device E. If node A is not on the innermost level, device F is a node which is distinct from the device E. Node F is located at node position N(r-1,e,H.sub.r-1(z)) on level r-1.

Node A sends control information to a device G. If node A is on the outermost level r=J, then device G is positioned outside of the interconnect structure. Device G is a device, for example a computational unit, that sends message data to node D. If node A is not positioned on level r=J, then device G is a node which is located at node position N(r+1, .theta.,h.sub.r(z)) on level r+1 and device G sends message data to node D.

In accordance with a second aspect of the present invention, a method is shown of transmitting a message from a node N to a target destination in a first, a second and a third dimension of three dimensions in an interconnect structure arranged as a plurality of nodes in a topology of the three dimensions. The method includes the steps of determining whether a node en route to the target destination in the first and second dimensions and advancing one level toward the destination level of the third dimension is blocked by another message, advancing the message one level toward the destination level of the third dimension when the en route node is not blocked and moving the message in the first and second dimensions along a constant level in the third dimension otherwise. This method further includes the step of specifying the third dimension to describe a plurality of levels and specifying the first and second dimensions to described a plurality of nodes on each level. A control signal is sent from the node en route to the node N on a level q in the third dimension, the control signal specifying whether the node en route is blocked. Transmission of a message is timed using a global clock specifying timing intervals to keep integral time modulus the number of nodes at a particular cylindrical height, the global clock time interval being equal to the second time interval and the first time interval being smaller than the global time interval. A first time interval a is set for moving the message in only the first and second dimensions. A second time interval a-a is set for advancing the message one level toward the destination level. A third time interval is set for sending the control signal from the node en route to the node N, the third time interval being equal to a.

In accordance with a third aspect of the present invention, a method is shown of transmitting a message from an input device to an output device through an interconnect structure. The message travels through the interconnect structure connecting a plurality of nodes in a three dimensional structure. The message has a target destination corresponding to a target ring on level 0 of the interconnect structure. A message M at a node N on level T en route to a target ring on level 0 advances to a node N' on level T-1 so long as the target ring is accessible from node N' and no other higher priority message is progressing to node N' to block the progress of message M. Whether the target ring is accessible from node N' is typically efficiently determined by testing a single bit of a binary code designating the target ring. Whether a higher priority message is blocking the progress of message M is efficiently determined using timed control signals. If a message is blocked at a time t, the message is in position to progress to the next level at time t+2. If a message is blocked by a message M' on level T-1, then a limited time duration will transpire before the message M' is able to block message M again.

A global clock controls traffic flow in the interconnect structure. Data flow follows rules that allow much of the control information to be "hidden" in system timing so that, rather than encoding all control information in a message packet header, timing considerations convey some information. For example, the target ring is encoded in the message packet header but, in some embodiments of the interconnect structure, designation of the target computational unit is determined by the timing of arrival of a message with respect to time on the global clock.

The disclosed multiple level interconnect structure has many advantages. One advantage is that the structure is simple, highly ordered and achieves fast and efficient communication for systems having a wide range of sizes, from small systems to enormous systems.

In addition, the interconnect structure is highly advantageous for many reasons. The interconnect structure resolves contention among messages directed toward the same node and ensures that a message that is blocked makes a complete tour of the nodes on a level before the blocking message is in position to block again. In this manner, a message inherently moves to cover all possible paths to the next level. A blocking message typically proceeds to subsequent levels so that overlying messages are not blocked for long.

BRIEF DESCRIPTION OF THE DRAWINGS

The features of the invention believed to be novel are specifically set forth in the appended claims. However, the invention itself, both as to its structure and method of operation, may best be understood by referring to the following description and accompanying drawings.

FIGS. 1A, 1B, 1C and 1D are abstract three-dimensional pictorial illustrations of the structure of an embodiment of a multiple level minimum logic interconnect apparatus.

FIG. 2 is a schematic diagram of a node, node terminals and interconnection lines connected to the terminals.

FIGS. 3A, 3B and 3C are schematic block diagrams that illustrate interconnections of nodes on various levels of the interconnect structure.

FIG. 4 is an abstract schematic pictorial diagram showing the topology of levels of an interconnect structure.

FIG. 5 is an abstract schematic pictorial diagram showing the topology of nodes of an interconnect structure.

FIG. 6 is an abstract schematic pictorial diagram which illustrates the manner in which nodes of the rings on a particular cylindrical level are interconnected.

FIG. 7 illustrates interconnections of a node on level zero.

FIG. 8 depicts interconnections of a node on level one.

FIG. 9 depicts interconnections of a node on level two.

FIG. 10 depicts interconnections of a node on level three.

FIG. 11 is an abstract schematic pictorial diagram which illustrates interconnections between devices and nodes of a ring on the low level cylinder.

FIG. 12 is an abstract schematic pictorial diagram which illustrates interconnections among nodes of two adjacent cylindrical levels.

FIG. 13 is an abstract schematic pictorial diagram showing interconnections of nodes on cylindrical level one.

FIG. 14 is an abstract schematic pictorial diagram showing interconnections of nodes on cylindrical level two.

FIG. 15 is an abstract schematic pictorial diagram showing interconnections of nodes on cylindrical level three.

FIG. 16 is an abstract schematic pictorial diagram illustrating the interaction of messages on adjacent levels of an embodiment of the interconnection structure.

FIG. 17 is a timing diagram which illustrates timing of message communication in the described interconnect structure.

FIG. 18 is a pictorial representation illustrating the format of a message packet including a header and payload.

FIG. 19 is a pictorial diagram which illustrates the operation of a lithium niobate node, a first exemplary node structure.

FIG. 20 is a pictorial diagram which illustrates the operation of a nonlinear optical loop mirror (NOLM), a second exemplary node structure.

FIG. 21 is a pictorial diagram which illustrates the operation of a terahertz optical asymmetrical demultiplexer (TOAD) switch, a third exemplary node structure.

FIG. 22 is a pictorial diagram showing the operation of a regenerator utilizing a lithium niobate gate.

FIG. 23 is an abstract schematic pictorial diagram illustrating an alternative embodiment of an interconnect structure in which devices issue message packets to multiple nodes.

FIG. 24 is an abstract schematic pictorial diagram illustrating an alternative embodiment of an interconnect structure in which devices receive message packets from multiple nodes.

FIG. 25 is an abstract schematic pictorial diagram illustrating an alternative embodiment of an interconnect structure in which devices issue message packets to nodes at various interconnect levels.

DETAILED DESCRIPTION

Referring to FIGS. 1A, 1B, 1C and 1D, an embodiment of a multiple level minimum logic interconnect apparatus 100 includes multiple nodes 102 which are connected in a multiple level interconnect structure by interconnect lines. The multiple level interconnect structure is shown illustratively as a three-dimensional structure to facilitate understanding.

The nodes 102 in the multiple level interconnect structure are arranged to include multiple levels 110, each level 110 having a hierarchical significance so that, after a message is initiated in the structure, the messages generally move from an initial level 112 to a final level 114 in the direction of levels of a previous hierarchical significance 116 to levels of a subsequent hierarchical significance 118. Illustratively, each level 110 includes multiple structures which are called rings 120. Each ring 120 includes multiple nodes 102. The term "rings" is used merely to facilitate understanding of the structure of a network in the abstract in which visualization of the structure as a collection of concentric cylindrical levels 110 is useful.

The different FIGS. 1A, 1B, 1C and 1D are included to more easily visualize and understand the interconnections between nodes. FIG. 1A illustrates message data transmission interconnections between nodes 102 on the various cylindrical levels 110. FIG. 1B adds a depiction of message data transmission interconnections between nodes 102 and devices 130 to the interconnections illustrated in FIG. 1A. FIG. 1C further shows message data interconnections between nodes 102 on different levels. FIG. 1D cumulatively shows the interconnections shown in FIGS. 1A, 1B and 1C in addition to control interconnections between the nodes 102.

The actual physical geometry of an interconnect structure is not to be limited to a cylindrical structure. What is important is that multiple nodes are arranged in a first class of groups and the first class of groups are arranged into a second class of groups. Reference to the first class of groups as rings and the second class of groups as levels is meant to be instructive but not limiting.

The illustrative interconnect apparatus 100 has a structure which includes a plurality of J+1 levels 110. Each level 110 includes a plurality of 2.sup.JK nodes 102. Each level M contains 2.sup.J-M rings 120, each containing 2.sup.MK nodes 102. The total number of nodes 102 in the entire structure is (J+1)2.sup.JK. The interconnect apparatus 100 also includes a plurality 2.sup.JK devices 130. In the illustrative embodiment, each device of the 2.sup.JK devices 130 is connected to a data output port of each of the K nodes 102 in each ring of the 2.sup.J rings of the final level 114. Typically, in an interconnect structure of a computer a device 130 is a computational unit such as a processor-memory unit or a cluster of processor-memory units and input and output buffers.

Referring to FIG. 2, an interconnect structure 200 of a node 102 has three input terminals and three output terminals. The input terminals include a first data input terminal 210, a second data input terminal 212 and a control input terminal 214. The output terminals include a first data output terminal 220, a second data output terminal 222 and a control output terminal 224. The data input and output terminals of a node communicate message data with other nodes. The control terminals communicate control bits with other nodes for controlling transmission of message data. The number of control bits for controlling message transmission is efficiently reduced since much of the logic throughout the interconnect structure 200 is determined by timing of the receipt of control bits and message data in a manner to be detailed hereinafter. Only one control bit enters a node and only one control bit leaves at a given time step. Messages are communicated by generating a clock signal for timing time units. Message transmission is controlled so that, during one time unit, any node 102 receives message data from only one input terminal of the data input terminals 212 and 214. Since, a node 202 does not have a buffer, only one of the node's output ports is active in one time unit.

Referring to FIGS. 3 through 16, the topology of an interconnect structure 300 is illustrated. To facilitate understanding, the structure 300 is illustrated as a collection of concentric cylinders in three dimensions r, e and z. Each node or device has a location designated (r, e, z) which relates to a position (r, 2 e/K, z) in three-dimensional cylindrical coordinates where radius r is an integer which specifies the cylinder number from 0 to J, angle e is an integer which specifies the spacing of nodes around the circular cross-section of a cylinder from 0 to K-1, and height z is a binary integer which specifies distance along the z-axis from 0 to 2.sup.J-1. Height z is expressed as a binary number because the interconnection between nodes in the z-dimension is most easily described as a manipulation of binary digits. Accordingly, an interconnect structure 300 is defined with respect to two design parameters J and K.

FIGS. 3A, 3B and 3C are schematic block diagrams that show interconnections of nodes on various levels of the interconnect structure. FIG. 3A shows a node A.sub.RJ 320 on a ring R of outermost level J and the interconnections of node A.sub.RJ 320 to node B.sub.RJ 322, device C 324, node D.sub.RJ 326, node E.sub.R(J-1) 328, node F.sub.R(J-1) 330 and device G 332. FIG. 3B shows a node A.sub.RT 340 on a ring R of a level J and the interconnections of node A.sub.RT 340 to node B.sub.RT 342, node C.sub.R(T+1) 344, node D.sub.RT 346, node E.sub.R(T-1) 348, node F.sub.R(T-1) 350 and node G.sub.R(T+1) 352. FIG. 3C shows a node A.sub.R0 360 on a ring R of innermost level 0 and the interconnections of node A.sub.R0 360 to node B.sub.R0 362, node C.sub.R1 364, node D.sub.R0 366, device E 368 and node G.sub.R1 372.

In FIGS. 3A, 3B and 3C interconnections are shown with solid lines with arrows indicating the direction of message data flow and dashed lines with arrows indicating the direction of control message flow. In summary, for nodes A, B and D and nodes or devices C, E, F, G: (1) A is on level T. (2) B and C send data to A. (3) D and E receive data from A. (4) F sends a control signal to A. (5) G receives a control signal from A. (6) B and D are on level T. (7) B is the immediate predecessor of A. (8) D is the immediate successor to A. (9) C, E, F and G are not on level T.

The positions in three-dimensional cylindrical notation of the various nodes and devices is as follows: (10) A is positioned at node N(r,e,z). (11) B is positioned at node N(r, e-1, H.sub.T(z)). (12) C is either positioned at node N(r+1, e-1, z) or is outside the interconnect structure. (13) D is positioned at node N(r, e+1, h.sub.T(z)). (14) E is either positioned at node N(r-1, e+1, z) or is outside the interconnect structure and the same as device F. (15) F is either positioned at node N(r-1, e, H.sub.T-1(z)) or is outside the interconnect structure and the same as device E. (16) G is either positioned at node N(r+1, e, h.sub.T(z)) or is outside the interconnect structure.

Note that the terms e+1 and e-1 refer to addition and subtraction, respectively, modulus K.

In this notation, (e-1)mod K is equal K when e is equal to 0 and equal to e-1 otherwise. The conversion of z to H.sub.r(z) on a level r is described for z=[z.sub.J-1, z.sub.J-, . . . , z.sub.r, z.sub.r-1, . . . , z.sub.2, z.sub.1, z.sub.0] by reversing the order of low-order z bits from z.sub.r-1 to z.sub.0] into the form z=[z.sub.J-1, z.sub.J-2, . . . , z.sub.r, z.sub.0, z.sub.1, z.sub.2, . . . , z.sub.r-1], subtracting one (modulus 2.sup.r) and reversing back the low-order z bits. Similarly, (e+1)mod K is equal 0 when e is equal to K-1 and equal to e+1 otherwise. The conversion of z to h.sub.r(z) on a level r is described for z=[z.sub.J-, z.sub.J-2, . . . , z.sub.r, z.sub.r-1, . . . , z.sub.2, z.sub.1, z.sub.0] by reversing the order of low-order z bits from z.sub.r-1 to z.sub.0] into the form z=[z.sub.J-1, z.sub.J-2, . . . , z.sub.r, z.sub.0, z.sub.1, z.sub.2, . . . , z.sub.r-1], adding one (modulus 2.sup.r) and reversing back the low-order z bits.

Referring to FIG. 4, concentric cylindrical levels zero 310, one 312, two 314 and three 316 are shown for a J=3 interconnect structure 300 where level 0 refers to the innermost cylindrical level, progressing outward and numerically to the outermost cylindrical level 3. A node 102 on a level T is called a level T node.

An interconnect structure has J+1 levels and 2.sup.JK nodes on each level. Referring to FIG. 5, the design parameter K is set equal to 5 so that the interconnect structure 300 has four levels (J+1=3+1=4) with 40 (2.sup.JK=(2.sup.3)5=40) nodes on each level.

Referring to FIGS. 6 through 10, the notation is modified, and made more concise, so that a letter at a node location (r,e,z) is denoted as the letter followed by the location designation. For example, node A at location (r,e,z) is designated node A(r,e,z).

Referring to FIG. 6, the interconnect structure is fully defined by designating the interconnections for each node A 530 of each level T to devices or nodes B 532, C 534, D 536, E 538, F 540 and G 542.

Node A(r,e,z) 530 is interconnected with an immediate predecessor node B(r,(e-1)mod K, H.sub.r(z)) 532 on level r. If node A(r,e,z) 530 is on the outermost level r=J, node A(r,e,z) 530 is interconnected with a device (e.g. a computational unit of a computer) outside of the interconnect structure. Otherwise, node A(r,e,z) 530 is interconnected with a predecessor node C(r+1, (e-1)mod K,z) 534 on level r+1.

Node A(r,e,z) 530 is interconnected with an immediate successor node D(r, (e+1)mod K,h.sub.r(z)) 536 on level r. If node A(r,e,z) 530 is on the innermost level r=0, node A(r,e,z) 530 is interconnected with a device (e.g. a computational unit) outside of the interconnect structure. Otherwise, node A(r,e,z) 530 is interconnected with a successor node E(r-1, (e+1)mod K,z) 538 on level r-1 to send message data.

If node A(r,e,z) 530 is on the innermost level r=0, node A(r,e,z) 530 is interconnected with a device (e.g. a computational unit) outside of the interconnect structure. Otherwise, node A(r,e,z) 530 is interconnected with a node F(r-1,e,H.sub.r(z)) 540 on level r-1 which supplies a control input signal to node A(r,e,z) 530.

If node A(r,.theta.,z) 530 is on the outermost level r=J, node A(r,.theta., z) 530 is interconnected with a device (e.g. a computational unit) outside of the interconnect structure. Otherwise, node A(r,.theta.,z) 530 is interconnected with a node G(r+1,.theta.,h.sub.r(z)) 542 on level r+l which receives a control input signal from node A(r,.theta.,z) 530.

Specifically, the interconnections of a node A for the example of an interconnect structure with interconnect design parameters J=3 and K=5 are defined for all nodes on a ring. Every ring is unidirectional and forms a closed curve so that the entire structure is defined by designating for each node A, a node D that receives data from node A.

Referring to FIG. 7 in conjunction with FIG. 3C, interconnections of a node A on level zero are shown. Node A(0,e,z) 360 is interconnected to receive message data from immediate predecessor node B(0, (e-1)mod 5,z) 362 on level 0 and to send message data to immediate successor node D(0, (e+1)mod 5,z) 366 on level 0. Although the interconnection term in the second dimension for nodes B and D is previously defined as H.sub.r(z) and h.sub.r(z), respectively, on level zero, H.sub.r(z)=H.sub.0(z)=z and h.sub.r(z)=h.sub.0(z)=z. Node A(0,e,z) 360 is also interconnected to receive message data from predecessor node C(1, (e-1)mod 5,z) 364 on level 1 and to send message data to a device E(e,z) 368. Node A(0,e,z) 360 is interconnected to receive control information from the device E(e, z) 368 outside the network and to send a control output signal to node G(1,e,h.sub.0(z)) 372 on level 1.

Referring to FIG. 8 in conjunction with FIG. 6, interconnections of a node A on level one are shown. Node A(1,e,z) 530 is interconnected to receive message data from immediate predecessor node B(1, (e-1)mod 5, H.sub.1(z)) 532 on level 1 and to send message data to immediate successor node D(1, (e+1)mod 5,h.sub.1(z)) 536 on level 1. Height z is expressed as a binary number (base 2) having the form [z.sub.2,z.sub.1,z.sub.0]. For level one, when z is [z.sub.2,z.sub.1,0] then h.sub.1(z) and H.sub.1(z) are both [z.sub.2,z.sub.1,1]. When z is [z.sub.2,z.sub.l,1] then h.sub.1(z) and H.sub.1(z) are both [z.sub.2,z.sub.1,0]. Node A(1,e,z) 530 is also interconnected to receive message data from predecessor node C(2, (e-1)mod 5,z) 534 on level 2 and to send message data to successor node E(0, (e+1)mod 5,z) 538 on level 0. Node A(1,e,z) 530 is interconnected to receive a control input signal from a node F(0,e,H.sub.0(z)) 540 on level zero and to send a control output signal to node G(2,e,h.sub.1(z)) 542 on level 2.

Referring to FIG. 9 in conjunction with FIG. 6, interconnections of a node A on level two are shown. Node A(2,e,z) 530 is interconnected to receive message data from immediate predecessor node B(2, (e-1)mod 5,H.sub.2(z)) 532 on level 2 and to send message data to immediate successor node D(2,(e+1)mod 5,h.sub.2(z)) 536 on level 2. Height z is expressed as a binary number (base 2) having the form [z.sub.2,z.sub.1,z.sub.0]. For level two, when z is [z.sub.2,0,0] then h.sub.2(z) is [z.sub.2,1,0] and H.sub.2(z) is [z.sub.2,1,1]. When z is [z.sub.2,0,1] then h.sub.2(z) is [z.sub.2,1,1] and H.sub.2(z) is [z.sub.2,1,0]. When z is [z.sub.2,1,0] then h.sub.2(z) is [z.sub.2,0,1] and H.sub.2(z) is [z.sub.20,0]. When z is [z.sub.2,1,1] then h.sub.2(z) is [z.sub.2,0,0] and H.sub.2(z) is [z.sub.2,0,1]. Node A(2,e,z) 530 is also interconnected to receive message data from predecessor node C(3, (e-1)mod 5,z) 534 on level 3 and to send message data to successor node E(1,(e+1)mod 5,z) 538 on level 1. Node A(2,e,z) 530 is interconnected to receive a control input signal from a node F(1,e,H.sub.1(z)) 540 on level 1 and to send a control output signal to node G(3,e,h.sub.2(z)) 542 on level 3.

Referring to FIG. 10 in conjunction with FIG. 6, interconnections of a node A on level three of an interconnect structure with J>3 and K=5 are shown. Node A(3,e,z) 530 is interconnected to receive message data from immediate predecessor node B(3, (e-1)mod 5,H.sub.3(z)) 532 on level 3 and to send message data to immediate successor node D(3, (e+1)mod 5,h.sub.3(z)) 536 on level 3. For level three, when z is [0,0,0] then h.sub.3(z) is [1,0,0] and H.sub.3(z) is [1,1,1]. When z is [0,0,1] then h.sub.3(z) is [1,0,1] and H.sub.3(z) is [1,1,0]. When z is [0,1,0] then h.sub.3(z) is [1,1,0] and H.sub.3(z) is [1,0,0]. When z is [0,1,1] then h.sub.3(z) is [1,1,1] and H.sub.3(z) is [1,0,1]. When z is [1,0,0] then h.sub.3(z) is [0,1,0] and H.sub.3(z) is [0,0,0]. When z is [1,0,1] then h.sub.3(z) is [0,1,1] and H.sub.3(z) is [0,0,1]. When z is [1,1,0] then h.sub.3(z) is [0,0,1] and H.sub.3(z) is [0,1,0]. When z is [1,1,1] then h.sub.3(z) is [0,0,0] and H.sub.3(z) is [0,1,1]. Node A(3,e,z) 530 is also interconnected to receive message data from predecessor node C(4, (e-1)mod 5,z) 534 on level 4 and to send message data to successor node E(2, (e+1)mod 5,z) 538 on level 2. Node A(3,e,z) 530 is interconnected to receive a control input signal from a node F(2,e,H.sub.2(z)) 540 on level 2 and to send a control output signal to node G(4,e,h.sub.3(z)) 542 on level 4.

FIG. 11 illustrates interconnections between devices 130 and nodes 102 of a ring 120 on the cylindrical level zero 110. In accordance with the description of the interconnect structure 200 of a node 102 discussed with respect to FIG. 2, a node 102 has three input terminals and three output terminals, including two data input terminals and one control input terminal and two data output terminals and one control output terminal. In a simple embodiment, a device 130 has one data input terminal 402, one control bit input terminal 404, one data output terminal 406 and one control bit output terminal 408.

Referring to FIG. 11, nodes 102 at the lowest cylindrical level 110, specifically nodes N(0,e,z), are connected to devices CU(e,z). In particular, the data input terminal 402 of devices CU(e,z) are connected to the second data output terminal 222 of nodes N(0,e,z). The control bit output terminal 408 of devices CU(e,z) are connected to the control input terminal 214 of nodes N(0,e,z).

The devices CU(.theta.,z) are also connected to nodes N(J,.theta.,z) at the outermost cylinder level. In particular, the data output terminal 406 of devices CU(e,z) are connected to the second data input terminal 212 of nodes N(J,.theta.,z). The control bit input terminal 404 of devices CU(.theta.,z) are connected to the control output terminal 224 of nodes N(J,.theta.-1,.sub.J(z)). Messages are communicated from devices CU(.theta.,z) to nodes N(J,.theta.,z) at the outermost cylindrical level J. Then messages move sequentially inward from the outermost cylindrical level J to level J-1, level J-2 and so forth until the messages reach level 0 and then enter a device. Messages on the outermost cylinder J can reach any of the 2.sup.J rings at level zero. Generally, messages on any cylindrical level T can reach a node on 2.sup.T rings on level zero.

FIG. 12 illustrates interconnections among nodes 102 of two adjacent cylindrical levels 110. Referring to FIG. 12 in conjunction with FIG. 2, nodes 102 at the T cylindrical level 110, specifically nodes N(T,e,z) 450, have terminals connected to nodes on the T level, the T+1 level and the T-1 level. These connections are such that the nodes N(T,e,z) 450 have one data input terminal connected to a node on the same level T and one data input terminal connected to another source, usually a node on the next outer level T+1 but for nodes on the outermost level J, a device is a source. In particular, nodes N(T,e,z) 450 have a first data input terminal 210 which is connected to a first data output terminal 220 of nodes N(T+1,e-1,z) 452. Also, nodes N(T,e,z) 450 have a first data output terminal 220 which is connected to a first data input terminal 210 of