N-dimensional modified hypercube

• US 5,794,059 A
• Filed: 07/28/1994
• Issued: 08/11/1998
• Est. Priority Date: 11/13/1990
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Dieffenderfer, James Warren, Collins, Clive Allan, Rolfe, David Bruce, Dapp, Michael Charles, Barker, Thomas Norman, Knowles, Billy Jack
• Primary Examiner(s): Sheikh, Ayaz R.
• Assistant Examiner(s): DARBE, VALERIE A
• Application Number:
  US08/282,101
• Time in Patent Office: 1,475 Days
• Field of Search: 395/800.1, 395/800.11, 395/800.12, 395/800.13, 395/800.15, 395/800.01
• US Class Current: 712/10
• CPC Class Codes: G06F 15/17343 wherein the interconnection is dynamically configurable, e.g. having loosely coupled nearest neighbor architecture reconfigurable processors arrays G06F15/7867
• CPC Class Codes: G06F 15/17381 Two dimensional, e.g. mesh, torus
• CPC Class Codes: G06F 15/803 Three-dimensional arrays or hypercubes
• CPC Class Codes: G06F 9/30036 Instructions to perform operations on packed data, e.g. vector, tile or matrix operations
• CPC Class Codes: G06F 9/30076 to perform miscellaneous control operations, e.g. NOP
• CPC Class Codes: G06F 9/30145 Instruction analysis, e.g. decoding, instruction word fields
• CPC Class Codes: G06F 9/30167 of immediate specifier, e.g. constants
• CPC Class Codes: G06F 9/30189 according to execution mode, e.g. mode flag
• CPC Class Codes: G06F 9/3802 Instruction prefetching
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/3838 Dependency mechanisms, e.g. register scoreboarding
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units
• CPC Class Codes: G06F 9/3887 controlled by a single instruction for multiple data lanes [SIMD]
• CPC Class Codes: G06F 9/3889 controlled by multiple instructions, e.g. MIMD, decoupled access or execute

Abstract

A parallel array processor for massively parallel applications is formed with low power CMOS with DRAWM processing while incorporating processing elements on a single chip, with nodes connected in an n-dimensional modified non-binary hypercube. In a 4-dimensional modified non-binary hypercube embodiment, each node includes either processor memory elements on a single chip, each processor memory element having its own associated processing element, significant memory, and I/O, with each processor memory element supporting an external port. Pairs of ports are associated with each dimension, labeled X, Y, W, and Z. Eight nodes are connected in the X dimension to form a ring. Corresponding nodes from eight such rings are connected into rings in the Y dimension to form an 8×8 array of nodes, referred to as a cluster. Corresponding nodes of eight clusters are connected into ring (64 rings) in the Z dimension, forming an 8×8×8 array of nodes referred to as a "cluster ring". Corresponding nodes of eight cluster rings are connected into rings in the W dimension.

Claims

1. A computer system, comprising:

N nodes organized as a massively parallel machine, N having a positive integer value; and

wherein said nodes are interconnected as a n-dimensional modified non-binary hypercube such that two nodes are connected if and only if respective n-digit indices identifying said nodes differ in exactly one digit, wherein n is a positive integer having a value greater than three, and each node is identifiable by a respective one of said n-digit indices, each one of said indices having one digit per dimension and each digit having a respective arbitrary radix, wherein at least one radix is of a base greater than two, and wherein N equals a product of each said respective arbitrary radix.

2. A computer system according to claim 1 wherein each node includes a multi-processor memory computer system.

3. A computer system according to claim 2 wherein said multi-processor memory computer system includes a plurality of processor memory elements having parallel internal communication paths interconnecting the processor memory elements, and includes parallel external communication paths interconnecting the processor memory elements to processor memory elements of another node.

4. A computer system according to claim 2 wherein said multi-processor memory computer system includes a plurality of processor memory elements integrated on a chip, each of the processor memory elements integrated to pass data between the processor memory element and other processor memory elements on the chip, said chip having chip pins most of which are used for input/output functions between processor memory elements of different chips.

5. A computer system according to claim 3, wherein said parallel internal communication paths and said parallel external communication paths provide an approximate optimal diameter of hypercubes with reduced wiring and logic density and greater bandwith.

6. A computer system according to claim 3 wherein each node of the modified non-binary hypercube utilizes only point to point interconnections.

7. A computer system according to claim 1 wherein a node is part of a set of nodes forming a processing array and wherein said n-dimensional modified non-binary hypercube for n greater than three, includes a set of m₁ nodes interconnected as a ring which may be `simply connected`, `braided`, `cross connected`, or `fully connected`, and wherein m₂ of the rings are linked together by sequentially connecting each of the m₂ rings into a toroid by connecting each node in a given ring to a respective node in a next given ring, wherein a last one of the m₂ rings is connected to a first one of the m₂ rings thereby resulting in a torus, and wherein a i+1d modified non-binary hypercube is formed from an id modified non-binary hypercube by connecting into rings all of the respective m_i level nodes of m_i+1 sets of i-d modified non-binary hypercubes, wherein i, m₁, m₂ and m_i are positive integers.

8. A computer system according to claim 7 wherein n equals four and I/O to an external system is made by logically `unzipping` an edge and attaching it to an external system bus, the edge representing interconnections between corresponding nodes of the rings interconnected to provide a given dimension of the modified non-binary hypercube.

9. A computer system according to claim 7 wherein an interface to an external I/O is provided by logically breaking any or all of the rings, thereby logically providing two ends for each broken ring, wherein the two ends of the broken ring are selectively connected to external I/O buses.

10. A computer system according to claim 9 wherein the selective connection is performed according to a logical operation so as to permit regular inter-processor memory element communication at certain time intervals while permitting I/O at other time intervals and the breaking process at a level of rings within the modified hypercube effectively `unzips` rings for I/O purposes and provides a separate interface into the array which may exist on 1 to n edges of the modified hypercube and supports either parallel input into multiple dimensions of the array or broadcast to multiple dimensions of an array.

11. A computer system according to claim 1, further comprising a controller, wherein a node has (i) 2n processor memory elements and (ii) a broadcast and control interface coupled to the controller, wherein the processor memory elements are coupled according to sets of rings formed into the modified non-binary hypercube.

12. A computer system according to claim 1 further comprising a controller, wherein each of said N nodes has (i) 2n processor memory elements and (ii) a broadcast and control interface coupled to the controller, and whereby a 4d modified non-binary hypercube has eight processor memory elements in each node, and whereby a 5d modified non-binary hypercube has ten processor memory elements in each node.

13. A computer system according to claim 1 wherein the computing system forms a non-binary hypercube comprising:

a plurality of nodes, N, where N=bⁿ, b and n being positive integers and b>

2 and n corresponding to the dimensionality of the n-dimensional modified non-binary hypercube, each node having an identifying address numbered according to a number system base b; and

there are means for interconnecting each node to nodes having addresses differing from the node'"'"'s address by exactly one digit, the number of connections per node being mu*log_b (N), where mu=2d, 1<

=d<

=b/2 if b is even and 1<

=d<

=(b-1)/2 if b is odd, except if b is even and d=b/2, in which case mu=b-1.

14. A computer system according to claim 1 wherein said n-dimensional modified non-binary hypercube is four dimensional, and wherein each node is connected to eight other nodes via eight respective external ports.

15. A computer system according to claim 1 wherein n is four and each node includes eight external ports, labeled +X, +Y, +Z, +W, -X, -Y, -Z, -W, and wherein a ring is constructed by connecting the +X to -X ports for m₁ nodes, and m₂ rings are formed into a cluster structure by interconnecting +Y to -Y ports into a ring for corresponding nodes, wherein m₁ and m₂ are integers and wherein labels +X and -X correspond to an X dimension, labels +Y and -Y correspond to a Y dimension, labels +Z and -Z correspond to a Z dimension, and labels +W and -W correspond to a W dimension.

16. A computer system according to claim 15 wherein for m₁ =m₂ =8 the cluster includes 512 processor memory elements and is a common building block for differing sizes of computer systems according to the +Z, -Z, +W, and -W ports.

17. A computer system according to claim 16 wherein sets of m₃ clusters are interconnected in rows using the +Z to -Z ports, and m₄ rows are then interconnected using the +W to -W ports, whereby for m₁ =_m 2=m₃ =m₄ =8 the computer system includes 8⁴⁺¹ processor memory elements.

18. A computer system according to claim 16 wherein only a single cluster on a single card is employed for a processor, and wherein the unused Z and W ports are interconnected on the single card.

19. A computer system according to claim 16 wherein the cluster is the building block for a fine-grained scalable processor having workstation and avionics applications.

20. A computer system according to claim 15 wherein +/ports are connected together in the Z and W pairs, thereby providing for a workstation organization that permits debug, test and large machine software development.

21. A computer system according to claim 15 wherein the cluster is characterized by a burst rate having a maximum potential transfer rate of 3.65 Gbytes/s, with a set of eight nodes along a row or a column of the cluster capable of achieving 57 Mbyte/s burst data rate, each of the nodes using one pair of the eight external ports.

22. A computer system having a plurality of processors and memory, comprising:

a plurality of nodes of multiple processor memory elements interconnected as a massively parallel array processor,

each of said processor memory elements having a plurality of communication paths for a n dimensional modified non-binary hypercube interconnection among nodes of the system, wherein n is a positive integer greater than three,

each processor memory element having a communication path for communication external to said node to another like scalable node of the computer system.

23. A computer system having a plurality of processors and memory, comprising:

a plurality of nodes of multiple processor memory elements interconnected as a massively parallel array processor;

each of said processor memory elements having a plurality of communication paths for a n dimensional modified non-binary hypercube interconnection among nodes of the system wherein n is a positive integer greater than 3.

24. A computer system having a plurality of processors and memory, comprising:

a plurality of nodes of multiple processor memory elements interconnected as a massively parallel array processor,

each of said processor memory elements having a plurality of communication paths for a n-dimensional modified non-binary hypercube interconnection among nodes of the system, where n is an integer greater than 3,

wherein the processor memory element to processor memory element interconnection in the node has two rings of processor memory elements, with each processor memory element having a connection to a processor memory in the other ring.

25. A computer system having a plurality of processors and memory, comprising:

a plurality of nodes of multiple processor memory elements interconnected as a massively parallel array processor in a n-dimensional non-binary hypercube, wherein n is an integer greater than three,

each of said processor memory elements having a plurality of communication paths providing interconnection among nodes of the system, wherein the processor memory element to processor memory element interconnections within a node are implemented as two rings of processor memory elements, and each processor memory element provides for the escape of one bus from the node, in which the escaped buses from one ring are labeled +X, +Y, +W and +Z, while those from the other ring are labeled -X, -Y, -W, and -Z.

26. A computer system having a plurality of processors and memory, comprising:

a plurality of nodes, each node having eight ports labeled +X, -X, +Y, -Y, +W, -W, +Z, and -Z, and wherein the nodes are connected using +X, -X, +Y and -Y into an array to create a cluster, and where the number of nodes in each dimension of the array is greater than two, and wherein the nodes are intercoupled using +W, -W, +Z, and -Z into an array of clusters, wherein, the number of clusters in each dimension of the array of clusters is arbitrary, enabling coupling as a 4-dimensional hypercube of nodes, and wherein the system can be extended to a 5-dimensional hypercube of ten processor memory element nodes using additional two buses, labeled +E and -E to connect the 4-dimensional hypercube into a vector of hypercubes.

27. A computer system having a plurality of processors and memory, comprising:

a plurality of nodes connected as an n-dimensional modified non-binary hypercube, wherein each node has (i) k * n processor memory elements and (ii) a broadcast and control interface (BCI) section for interconection to an external controller, where "n" represents the number of dimensions or rings of the n-dimensional modified non-binary hypercube topology and where "k" represents the number of rings that characterize the processor memory elements in the node, where k and n are positive integers and n is greater than three.

28. A computer system having a plurality of processors and memory, comprising:

a plurality of nodes, each node having a plurality of processor memory elements and wherein the interconnection methods for a modified non-binary hypercube topology for interconnecting a plurality of nodes in a network of PMEs is provided according to;

a. defining an expansion set of integers e1, e2, e3, . . . e_m such the product of all elements of the set equals the number of processor memory elements in the network called M, while the product of all elements in the set excepting e1 and e2 is the number of nodes called N, the integer ej represents the number of elements e(j-1) used in the jth level of expansion, where j is an integer from 1 to m and e1 is at least 1, and the number of elements in the set called m defines the dimensionality of the network n by the relationship n=m-2,

b. addressing a processor memory element located by a set of address indexes a1, a2, . . . am, where each index represents the processor memory element position in a level of expansion corresponding to the expansion set elements such that the index ai is in the range of zero to ei-1 for i equal to 1, 2, to m., the addressing represented by the formula ( . . . (a(m) * e(m-1)+a (m-2))e(m-1) . . . a(2)*e(1))+a(1) where the notation a(i) has the normal meaning of the the ith element in the list of elements called a, or equivalently for e,

c. connecting two processor memory elements having addresses r and s if and only if either of the following two conditions hold;

1) the integer part of r/(e1 * e2) equals the integer part of s/(e1 * e2) and;

a) the remainder part of r/e1 differs from the remainder part of s/e1 by 1 or,

b) the remainder part of r/e2 differs from the remainder part of s/e2 by 1 or e2-1, and

2) the remainder part of r/ei differs from the remainder part of s/ei for i in the range 3, 4, . . . m and the remainder part of r/e1 equals the remainder part of s/e2 which equals i minus three, and the remainder part of r/e2 differs from the remainder part of s/e2 by e2 minus one.

29. A computer system according to claim 28 wherein

the computing system nodes form an n-dimensional modified non-binary hypercube, with the potential for each dimension having a different radix, where a node is defined as an array of processor memory elements which supports 2*n ports, and

wherein, if the set of integers e3, e4, . . . em, which define the specific extent of each dimension of a particular modified hypercube are all taken as equal to b, and if e1 and e2 are taken equal to 1, then the addressability and connections are prescribed by:

a. N=bⁿ, where b is an integer greater than two, in accordance with a non-binary base

b. addressing a processing memory element as a number represented in the base b numbering system

c. connecting two computing elements represented by addresses r and s if and only if the address r differs from the address s in exactly one base b digit, using the rule that 0 and b-1 are separated by 1; and

d. the number of connections supported by each processor memory element is 2*n.