US5794059A — N-dimensional modified hypercube

Claim 1

Independent Claim 118 words

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.

Claim 2

Dependent Claim 118 words

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.

Claim 3

Dependent Claim 16 words

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

Claim 4

Dependent Claim 48 words

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.

Claim 5

Dependent Claim 67 words

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.

Claim 6

Dependent Claim 35 words

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.

Claim 7

Dependent Claim 21 words

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

Claim 8

Dependent Claim 168 words

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 1 nodes interconnected as a ring which may be `simply connected`, `braided`, `cross connected`, or `fully connected`, and wherein m 2 of the rings are linked together by sequentially connecting each of the m 2 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 2 rings is connected to a first one of the m 2 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 1 , m 2 and m i are positive integers.

Claim 9

Dependent Claim 53 words

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.

Claim 10

Dependent Claim 49 words

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.

Claim 11

Dependent Claim 96 words

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.

Claim 12

Dependent Claim 49 words

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.

Claim 13

Dependent Claim 64 words

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.

Claim 14

Dependent Claim 114 words

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 n , 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.

Claim 15

Dependent Claim 31 words

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.

Claim 16

Dependent Claim 113 words

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 1 nodes, and m 2 rings are formed into a cluster structure by interconnecting +Y to -Y ports into a ring for corresponding nodes, wherein m 1 and m 2 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.

Claim 17

Dependent Claim 42 words

A computer system according to claim 15 wherein for m 1 =m 2 =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.

Claim 18

Dependent Claim 56 words

A computer system according to claim 16 wherein sets of m 3 clusters are interconnected in rows using the +Z to -Z ports, and m 4 rows are then interconnected using the +W to -W ports, whereby for m 1 = m 2=m 3 =m 4 =8 the computer system includes 8 4+1 processor memory elements.

Claim 19

Dependent Claim 35 words

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.

Claim 20

Dependent Claim 24 words

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.

Claim 21

Dependent Claim 33 words

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.

Claim 22

Dependent Claim 60 words

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.

Claim 23

Dependent Claim 84 words

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.

Claim 24

Dependent Claim 84 words

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.

Claim 25

Dependent Claim 61 words

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.

Claim 26

Dependent Claim 61 words

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.

Claim 27

Dependent Claim 95 words

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.

Claim 28

Dependent Claim 95 words

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.

Claim 29

Dependent Claim 124 words

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.

Claim 30

Dependent Claim 124 words

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.

Claim 31

Dependent Claim 140 words

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.

Claim 32

Dependent Claim 140 words

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.

Claim 33

Dependent Claim 94 words

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.

Claim 34

Dependent Claim 94 words

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.

Claim 35

Dependent Claim 391 words

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.

Claim 36

Dependent Claim 391 words

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.

Claim 37

Dependent Claim 183 words

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 n , 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.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2001-08-10	2002-02-09	2002-08-11	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2005-08-10	2006-02-09	2006-08-11	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2009-08-10	2010-02-09	2010-08-11	$7700.00	Window Closed / Lapsed

N-dimensional modified hypercube

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag