METHOD AND SYSTEM FOR GENERATING PSEUDORANDOM NUMBERS IN PARALLEL

摘要

The disclosed embodiments relate to a system that generates a pseudorandom number. During operation, the system maintains a current dot-product for a thread, wherein the current dot-product is a dot-product between a pedigree for the thread and an array of coefficients, wherein the pedigree for the thread comprises an array of elements that specify a path to the thread from a root in a dynamic multi-threading hierarchy, and wherein the array of coefficients includes a coefficient for each level in the dynamic multi-threaded hierarchy. To generate the pseudorandom number, the system incrementally computes a new dot-product from the current dot-product without performing a multiplication operation by adding a coefficient associated with the thread's level in the dynamic multi-threading hierarchy to the current dot-product. Next, the system performs a mixing operation on the new dot-product to produce the pseudorandom number. Finally, the system updates the current dot-product to the new dot-product.

主权项

1. A computer-implemented method for generating a pseudorandom number, comprising:
maintaining a current dot-product for a thread, wherein the current dot-product is a dot-product between a pedigree for the thread and an array of coefficients, wherein the pedigree for the thread comprises an array of elements that specify a path to the thread from a root in a dynamic multi-threading hierarchy, and wherein the array of coefficients includes a coefficient for each level in the dynamic multi-threaded hierarchy; incrementally computing a new dot-product from the current dot-product without performing a multiplication operation by adding a coefficient associated with the thread's level in the dynamic multi-threading hierarchy to the current dot-product; performing a mixing operation on the new dot-product to produce the pseudorandom number; and updating the current dot-product to the new dot-product.