Patent ID: 8924984

Claim:
A method of executing an algorithm in a parallel manner using a plurality of concurrent threads, comprising: generating a lock-free barrier that includes a variable that is configured to be updated using a lock-free technique and that stores a total participants count, a current participants count, and a flag, the total participants count indicating a total number of threads in the plurality of concurrent threads that are participating in a current phase of the algorithm, the current participants count indicating a total number of threads in the plurality of concurrent threads that have completed the current phase, and the flag indicating whether the current phase is an odd phase or an even phase, wherein the barrier is a sense-reversing barrier that tracks whether the current phase is odd or even, and wherein the total participants count, the current participants count, and the flag stored in the integer variable are configured to be updated using a single compare-and-swap (CAS) operation; blocking, with the lock-free barrier, the threads that have completed the current phase; dynamically updating the total participants count during execution of the current phase of the algorithm; and wherein the generating, blocking, and dynamically updating are performed by at least one processor.