Patent ID: 8438370

Claim:
A method for generating a plurality of data values, the method comprising: defining a thread array having a plurality of threads, each thread being assigned to perform an iteration of a loop to compute a different one of a plurality of data values, each thread being configured to execute a same program, wherein each thread in the plurality of threads performs a different iteration of the same loop; assigning each thread to one of a plurality of subsets of threads that are independent of each other, the plurality of subsets including at least a first subset and a second subset, by: identifying threads for the first subset of threads, wherein none of the threads in the first subset of threads depend on values to be computed by any of the other threads in the first subset of threads; and identifying threads for the second subset of threads, wherein none of the threads in the second subset of threads depend on values to be computed by any of the other threads in the second subset of threads, wherein none of the threads in the first subset depend on data values to be computed by any of the threads in the second subset and at least some of the threads in the second subset depend on data values to be computed by at least some of the threads in the first subset; determining an order of execution based on data dependencies that exist between the first subset of threads and the second subset of threads; and executing the thread array, wherein execution of the thread array includes: for each of the threads in the first subset, computing a data value and storing the data value in a memory, wherein computing the data value is performed in parallel for at least two of the threads in the first subset; and for each of the threads in the second subset, computing a data value and storing the data value in the memory, wherein computing the data value is performed in parallel for at least two of the threads in the second subset and wherein for at least some of the threads in the second subset, computing the data value includes reading from the memory at least one of the data values generated by the threads in the first subset, wherein the act of storing the data value in the memory is performed for all of the threads in the first subset before the act of computing the data value is performed for any of the threads in the second subset.