Bulk-synchronous parallel computer

Claim 2

A multiple instruction, multiple data, parallel processor system comprising: a plurality of computational and memory elements; a hashing module for providing each of the computational elements with a common hashing function associated therewith for assigning data to the memory elements creating an apparently randomized memory space; a parallel router for routing data transfers between computational and memory elements in parallel, the parallel router routing the data transfers independently of continued computation and storage access in the computational and memory elements and masking any substantial latency therein; and a synchronizer for synchronizing multiple instruction computational tasks in individual computational elements in supersteps of a plurality of computational steps such that individual computational and routing tasks are completed in all synchronized computational elements before the elements proceed to subsequent tasks, wherein each computational element may proceed through the superstep without needing results from other computational elements.

Claim 3

A systems as claimed in claim 1 wherein the computational bandwidth of the elements is substantially matched to the communication bandwidth of the router in that a ratio g of the first to the second is less than or equal to 10.

Claim 4

A system as claimed in claim 2 wherein a program being processed is compiled to a plurality of virtual processor routines processed by the computational elements, the plurality of virtual processor routines of at least about plog p where p is the number of computational elements in the system.

Claim 5

A system as claimed in claim 2 wherein the synchronizer synchronizes computations in computational elements in supersteps of L computational steps where L is at least about glog p.

Claim 6

A system as claimed in claim 1 wherein a program being processed is compiled to a plurality of virtual processor routines processed by the computational elements, the plurality of virtual processor routines of at least about plog p where p is the number of computational elements in the system.

Claim 7

A system as claimed in claim 5 wherein the synchronizer synchronizes computations in computational elements in supersteps of L computational steps where L is at least about glog p.

Claim 8

A system as claimed in claim 1 wherein the synchronizer synchronizes computations in computational elements in supersteps of L computational steps where L is at least about glog p, where p is the number of computational elements in the system, and g is the ratio of the computational bandwidth of the computational elements to the communication bandwidth of the router.

Claim 9

A system as claimed in claim 1 wherein each computational element comprises a hashing module.

Claim 10

A system as claimed in claim 8 wherein each hashing module is a hardware module.

Claim 11

A system as claimed in claim 1 wherein latency in the router is masked by a pipelined router.

Claim 12

A system as claimed in claim 1 wherein the router is of low latency.

Claim 13

A multiple instruction, multiple data, parallel processor system comprising: a plurality of computational and memory elements; a hashing module associated with each computational element for providing each of the computational elements with a common hashing function associated therewith for assigning data to the memory elements creating an apparently randomized memory space; a program compiled to a plurality of virtual processor routines processed by the computational elements, the plurality of virtual processor routines of at least about plog p where p is the number of computational elements in the system; a parallel router for routing data transfers between computational and memory elements in parallel, the parallel router routing the data transfers independently of continued computation and storage access in the computational and memory elements and masking any substantial latency therein; and a synchronizer for synchronizing multiple instruction computational tasks in individual computational elements in supersteps of L computational steps where L is at least about glog p, where p is the number of computational elements in the system, and g is the ratio of the computational bandwidth of the computational elements to the communication bandwidth of the router, such that individual computational and routing tasks are completed in all synchronized computational elements before the elements proceed to subsequent tasks, wherein L is chosen so that each computational element may proceed through the superstep without needing results from other computational elements.

Claim 14

A multiple instruction, multiple data, parallel processor system comprising: a plurality of computational and memory elements; a hashing module associated with each computational element for providing each of the computational elements with a common hashing function associated therewith for assigning data to the memory elements creating an apparently randomized memory space; a program compiled to a plurality of virtual processor routines processed by the computational elements, the plurality of virtual processor routines of at least about plog p where p is the number of computational elements in the system; a parallel router for routing data transfers between computational and memory elements in parallel, the parallel router routing the data transfers independently of continued computation and storage access in the computational and memory elements and masking any substantial latency therein; and a synchronizer for synchronizing multiple instruction computational tasks in individual computational elements in supersteps of L computational steps where L is at least about glog p, where p is the number of computational elements in the system, and g is the ratio of the computational bandwidth of the computational elements to the communication bandwidth of the router, such that individual computational and routing tasks are completed in all synchronized computational elements before the elements proceed to subsequent tasks, wherein L is chosen so that each computational element may proceed through the superstep without needing results from other computational elements.

Claim 17

A method as claimed in claim 13 wherein the computational bandwidth of the elements is substantially matched to the communication bandwidth of the router in that a ratio g of the first to the second is less than or equal to 10.

Claim 18

A method as claimed in claim 14 further comprising compiling a program to a plurality of virtual processor routines processed by the computational elements, the plurality of virtual processor routines of at least about plog p where p is the number of computational elements in the system.

Claim 19

A method as claimed in claim 15 wherein the computational tasks are synchronized in supersteps of L computational steps where L is at least about glog p.

Claim 20

A method as claimed in claim 14 wherein the computational tasks are synchronized in supersteps of L computational steps where L is at least about glog p.

Claim 21

A method as claimed in claim 13 further comprising compiling a program to a plurality of virtual processor routines processed by the computational elements, the plurality of virtual processor routines of at least about plog p where p is the number of computational elements in the system.

Claim 22

A method as claimed in claim 18 wherein the computational tasks are synchronized in supersteps of L computational steps where L is at least about glog p.

Claim 23

A method as claimed in claim 13 wherein the computational tasks are synchronized in supersteps of L computational steps where L is at least about glog p.

Claim 24

A method as claimed in claim 13 wherein the hashing function is applied in a hashing module in each computational element.

Claim 25

A method as claimed in claim 21 wherein each hashing module is a hardware module.

Claim 26

A method as claimed in claim 13 wherein routing latency is masked by pipelining.

Claim 27

A method as claimed in claim 13 wherein there is no substantial latency.

Claim 28

A multiple instruction, multiple data, parallel processor system comprising: a plurality of computational and memory elements; a hashing module for providing each of the computational elements with a common hashing function associated therewith for assigning data to the memory elements creating an apparently randomized memory space; a program compiled to a plurality of virtual processor routines processed by the computational elements, the plurality of virtual processor routines of at least about plog p where p is the number of computational elements in the system; a parallel router for routing data transfers between computational and memory elements in parallel, the parallel router routing the data transfers independently of continued computation and storage access in the computational and memory elements and masking any substantial latency therein; and a synchronizer for synchronizing multiple instruction computational tasks in individual computational elements in supersteps of L computational steps where L is at least about glog p, where g is the ratio of the computational bandwidth of the computational elements to the communication bandwidth of the router, such that individual computational and routing tasks are completed in all synchronized computational elements before the elements proceed to subsequent tasks, wherein L is chosen so that each computational element may proceed through the superstep without needing results from other computational elements, wherein the computational bandwidth of the elements of the system is substantially matched to the communication bandwidth of the router in that a ratio of the first to the second is less than or equal to 10.

Claim 29

A multiple instruction, multiple data, parallel processor system comprising: a plurality of computational and memory elements; a hashing module for providing each of the computational elements with a common hashing function associated therewith for assigning data to the memory elements creating an apparently randomized memory space; a program compiled to a plurality of virtual processor routines processed by the computational elements, the plurality of virtual processor routines of at least about plog p where p is the number of computational elements in the system; a parallel router for routing data transfers between computational and memory elements in parallel, the parallel router routing the data transfers independently of continued computation and storage access in the computational and memory elements and masking any substantial latency therein; and a synchronizer for synchronizing multiple instruction computational tasks in individual computational elements in supersteps of L computational steps where L is at least about glog p, where g is the ratio of the computational bandwidth of the computational elements to the communication bandwidth of the router, such that individual computational and routing tasks are completed in all synchronized computational elements before the elements proceed to subsequent tasks, wherein L is chosen so that each computational element may proceed through the superstep without needing results from other computational elements, wherein the computational bandwidth of the elements of the system is substantially matched to the communication bandwidth of the router in that a ratio of the first to the second is less than or equal to 10.