Deterministic parallelization through atomic task computation

A computer system comprising:

• at least one processor;
• memory coupled to the at least one processor;
• a computer-readable storage media coupled to the at least one processor, wherein the computer-readable storage media contains program instructions executing a computer-implemented method comprising the steps of:
• creating a data structure in the memory of the computer system, the data structure configured to manage a lock on a shared resource in a parallel computing environment and the data structure specifies an owner of the lock that is provided exclusive access to the shared resource;
• defining a plurality of tasks for performance in the parallel computing environment, with each task including a set of threads;
• implementing scheduler logic configured to deterministically control a selection of one or more threads from the set of threads within a queue of the data structure;
• for each given thread of each task of the plurality of tasks, calculating a deterministic time for each of the one or more threads within the queue, said deterministic time indicating a count of read or write operations of the memory to be carried out by the given thread wherein calculating the deterministic time for each of the one or more threads within the queue comprises:
• resetting each of the one or more threads;
• selecting a loop programmatically specified for execution in the corresponding one of the threads;
• resetting a loop count of a number of iterations executed for the loop;
• computing a number of memory access operations for the loop;
• executing the loop and incrementing the loop count;
• and
• iteratively additionally executing the loop with a corresponding incrementing of the loop count until exiting the loop in response to which a loop deterministic time for the loop is computed as a product of the loop count and a number of memory accesses directed for each iterative execution of the loop with a total deterministic time for the corresponding one of the threads being augmented by the loop deterministic time;
• comparing the deterministic time for each of the one or more threads within the queue;
• selecting the thread from the queue with a shortest deterministic time;
• and
• establishing the thread from the queue with the shortest deterministic time as the owner of the lock, providing the thread with the shortest deterministic time with exclusive access to the shared resource.

A computer program product comprising:

• one or more computer-readable storage media having computer-readable program instructions stored on the one or more computer-readable storage media, said program instructions executes a computer-implemented method comprising the steps of:
• creating a data structure in memory, the data structure configured to manage a lock on a shared resource in a parallel computing environment and the data structure specifies an owner of the lock that is provided exclusive access to the shared resource;
• defining a plurality of tasks for performance in the parallel computing environment, with each task including a set of threads;
• implementing scheduler logic configured to deterministically control a selection of one or more threads from the set of threads within a queue of the data structure;
• for each given thread of each task of the plurality of tasks, calculating a deterministic time for each of the one or more threads within the queue, said deterministic time indicating a count of read or write operations of the memory to be carried out by the given thread wherein calculating the deterministic time for each of the one or more threads within the queue comprises:
• resetting each of the one or more threads;
• selecting a loop programmatically specified for execution in the corresponding one of the threads;
• resetting a loop count of a number of iterations executed for the loop;
• computing a number of memory access operations for the loop;
• executing the loop and incrementing the loop count;
• and
• iteratively additionally executing the loop with a corresponding incrementing of the loop count until exiting the loop in response to which a loop deterministic time for the loop is computed as a product of the loop count and a number of memory accesses directed for each iterative execution of the loop with a total deterministic time for the corresponding one of the threads being augmented by the loop deterministic time;
• comparing the deterministic time for each of the one or more threads within the queue;
• selecting the thread from the queue with a shortest deterministic time;
• and
• establishing the thread from the queue with the shortest deterministic time as the owner of the lock, providing the thread with the shortest deterministic time with exclusive access to the shared resource.