Parallel pseudorandom number generation

1. A method of generating pseudo-random numbers, comprising:

in a runtime system configured to run on a parallel-processing computer system that includes a first processor and a plurality of co-processors and memory storing one or more programs for execution by the first processor and the plurality of co-processors,

at runtime:

receiving one or more operation requests from an application, the one or more operation requests comprising requests for a plurality of pseudo-random number sub-streams;

selecting respective ones of the plurality of co-processors for executing the pseudo-random number generators;

generating a plurality of sub-streams of pseudo-random numbers, wherein the sub-streams are generated in parallel by the selected co-processors; and

providing the plurality of sub-streams to respective co-processors, wherein each co-processor is configured to employ one of the plurality of sub-streams to execute the application;

wherein generating the plurality of sub-streams comprises:

in the first processor, storing a state associated with a first element in a respective sub-stream of the plurality of sub-streams;

in the first processor, advancing the state;

providing the advanced state to a respective co-processor of the plurality of co-processors, wherein the respective co-processor calculates a second element in the respective sub-stream in accordance with the advanced state; and

at one of the plurality of co-processors:

computing, for a sub-stream, an index location; and

reading, from an indexed table, a value stored at the computed index location, wherein the indexed table for a respective sub-stream is stored in a texture memory of one of the co-processors that is a graphics processing unit.

2. The method of claim 1 , wherein the first processor is a CPU.

3. The method of claim 2 , wherein the respective co-processor is a GPU.

4. The method of claim 1 , wherein the first processor is a first core of a multi-core CPU.

5. The method of claim 4 , wherein at least one of the plurality of co-processors is a second core of the multi-core CPU.

6. The method of claim 1 , wherein the application is a Monte Carlo simulation.

7. The method of claim 1 , wherein the application is one of stock option pricing, electronic circuit place-and-route, controller optimization, disk scheduling, production planning, analysis of DNA sequence shuffling, data clustering, information retrieval, or cryptography.

8. The method of claim 1 , wherein a respective sub-stream in the plurality of sub-streams is generated by a blocking algorithm wherein the plurality of sub-streams can be cascaded one by one into a random number sequence such that each sub-stream occupies a consecutive portion of the random number sequence.

9. The method of claim 1 , wherein a respective sub-stream in the plurality of sub-streams is generated by a leapfrogging algorithm wherein members of the plurality of sub-streams are evenly distributed within a random number sequence such that any two consecutive members of each sub-stream are separated from each other by a predefined distance within the random number sequence.

10. The method of claim 1 , wherein the selected co-processors are a plurality of graphics processing units.

11. A parallel processing system for generating pseudo-random numbers, comprising:

a first processor;

a plurality of co-processors; and

memory storing at least one program for execution by the first processor and the plurality of co-processors, the at least one program comprising instructions for:

at runtime:

receiving one or more operation requests from an application, the one or more operation requests comprising requests for a plurality of pseudo-random number sub-streams;

selecting respective ones of the plurality of co-processors for executing the pseudo-random number generators;

generating a plurality of sub-streams of pseudo-random numbers, wherein the sub-streams are generated in parallel by the selected co-processors; and

providing the plurality of sub-streams to respective co-processors, wherein each co-processor is configured to employ one of the plurality of sub-streams to execute the application;

wherein generating the plurality of sub-streams comprises:

in the first processor, storing a state associated with a first element in a respective sub-stream of the plurality of sub-streams;

in the first processor, advancing the state;

providing the advanced state to a respective co-processor of the plurality of co-processors, wherein the respective co-processor calculates a second element in the respective sub-stream in accordance with the advanced state; and

at one of the plurality of co-processors:

computing, for a sub-stream, an index location; and

reading, from an indexed table, a value stored at the computed index location, wherein the indexed table for a respective sub-stream is stored in a texture memory of one of the co-processors that is a graphics processing unit.

12. A non-transitory computer readable storage medium storing one or more programs configured to be executed by a parallel processing computer system with a first processor and plurality of co-processors, the one or more programs comprising instructions for:

at runtime:

receiving one or more operation requests from an application, the one or more operation requests comprising requests for a plurality of pseudo-random number sub-streams;

selecting respective ones of the plurality of co-processors for executing the pseudo-random number generators;

generating a plurality of sub-streams of pseudo-random numbers, wherein the sub-streams are generated in parallel by the selected co-processors; and

providing the plurality of sub-streams to respective co-processors, wherein each co-processor is configured to employ one of the plurality of sub-streams to execute the application

wherein generating the plurality of sub-streams comprises:

in the first processor, storing a state associated with a first element in a respective sub-stream of the plurality of sub-streams;

in the first processor, advancing the state;

providing the advanced state to a respective co-processor of the plurality of co-processors, wherein the respective co-processor calculates a second element in the respective sub-stream in accordance with the advanced state; and

at one of the plurality of co-processors:

computing, for a sub-stream, an index location; and

reading, from an indexed table, a value stored at the computed index location, wherein the indexed table for a respective sub-stream is stored in a texture memory of one of the co-processors that is a graphics processing unit.

13. A parallel processing system for generating pseudo-random numbers, comprising:

in a runtime system configured to run on a parallel-processing computer system that includes a first processor and a plurality of co-processors and memory storing one or more programs for execution by the first processor and the plurality of co-processors:

means for, at runtime, receiving one or more operation requests from an application, the one or more operation requests comprising requests for a plurality of pseudo-random number sub-streams;

means for, at runtime, selecting respective ones of the plurality of co-processors for executing the pseudo-random number generators;

means for, at runtime, generating a plurality of sub-streams of pseudo-random numbers, wherein the sub-streams are generated in parallel by the selected co-processors; and

means for, at runtime, providing the plurality of sub-streams to respective co-processors, wherein each co-processor is configured to employ one of the plurality of sub-streams to execute the application;

wherein generating the plurality of sub-streams comprises:

in the first processor, storing a state associated with a first element in a respective sub-stream of the plurality of sub-streams;

in the first processor, advancing the state;

providing the advanced state to a respective co-processor of the plurality of co-processors, wherein the respective co-processor calculates a second element in the respective sub-stream in accordance with the advanced state; and

at one of the plurality of co-processors:

computing, for a sub-stream, an index location; and

reading, from an indexed table, a value stored at the computed index location, wherein the indexed table for a respective sub-stream is stored in a texture memory of one of the co-processors that is a graphics processing unit.