Patent ID: 9652301
Date: 2017-05-16
CPC Classifications: G06F

Claim:
1. A method of executing computational operations of a program in parallel on multiple processors, the method comprising the steps of: (a) identifying in the program the computational operations accessing sets of data elements, each of the sets of data elements having a write token and a plurality of read tokens; wherein the write token of a given data element is available only when no read tokens from the given data element are currently taken by other computational operations, and the read tokens for each data element are represented by a tally that may be increased and decreased to indicate a taking or return of the read tokens, a read token from the given data element is only available if the write token of the given data element is not currently taken by other computational operations; (b) establishing a serial execution order of the computational operations by following dynamically determined loops, jumps and branches between computational operations of the program; (c) contemporaneously with execution of each given computational operation needing to write to a given data element of the sets of data elements: (d) upon the completion of execution of the given computational operation, returning the write token; (e) contemporaneously with execution of each given computational operation reading a given data element; (f) while a given computational operation has taken and not returned a write token associated with a given data element, blocking other computational operations associated with the given data element that are waiting for a read token and that are after the given computational operation in the serial execution order; and (g) after the given computational operation has returned the write token associated with the given data element, cease blocking all other computational operations associated with the given data element that waiting for a read token and after the given computational operation in the serial execution order up to a first other computational operation in the serial execution order waiting for a write token, and (h) wherein processors of the multiple processors are associated with at least one processor queue and wherein the given computational operation is placed in the processor queue to be executed by a processor only after it is permitted to execute and all necessary write tokens are taken by the given computational operation.