Patent Document ID: 8381195
Application ID: 12817466

Base Claim:
1. At a computer system including one or more processors and system memory, a method for implementing iterations of a serial loop in parallel by storing any variable assignments made during each iteration of the serial loop in a corresponding temporary copy and then merging the temporary copies, the method comprising: an act of determining that a specified number of loop iterations of a loop are to be executed, one or more iterations in the specified number of loop iterations assigning one of a plurality of different values to a variable used in the serial loop; an act of providing a temporary copy of the variable to each loop iteration; an act of concurrently executing one or more different pluralities of loop iterations from among the specified number of loop iterations to determine if a value and what value is assigned to the variable for each different loop iterations, including for at least one loop iteration: an act of assigning one of the plurality of different values to the temporary copy of the variable provided for the loop iteration; and an act of indicating that the temporary copy of the variable provided for the loop iteration was assigned a value; an act of ordering the temporary copies of the variable provided for the loop iterations based on when each loop iteration would have been executed serially during serial execution of the loop; and an act of merging the ordered temporary copies of the variable to the variable according to a reduction operation, the reduction operation including: analyzing the ordering of the temporary copies of the variable corresponding to the loop iterations; based on the analyzing, identifying the loop iteration closest to the last loop iteration that has assigned a value to its temporary copy of the variable; and in response to the identifying, assigning to the variable the value that the loop iteration closest to the last loop iteration assigned to its temporary copy of the variable.

---

Claim 6:
6. The method as recited in claim 1 , wherein the act of indicating that that temporary copy of the variable provided for the loop iteration was assigned a value comprises an act of maintaining an extra bit flag for each temporary copy of the variable.