Patent ID: 8601486
Filing Date: 2013-12-03
Classification: G06F

Abstract:
1. A parallel computing data processing system configured for deterministic locking in a parallel computing environment, the system comprising: a plurality of threads of execution in memory of a computing system; a shared resource shared by the threads; a deterministic lock for the shared resource comprising a data structure subsisting in the memory of the computing system and encapsulating a reference to an owner of the lock and a queue of ones of the threads able to seek exclusive access to the shared resource, the queue comprising a plurality of entries, each entry comprising an identifier for a corresponding one of the threads in the queue and a deterministic time computed for the corresponding one of the threads in the queue from a count of memory accesses occurring in the corresponding one of the threads in the queue; a deterministic lock management module executing in the memory of the computing system, the deterministic lock management module deterministically selecting a thread from the queue to receive ownership of the lock and exclusive access to the shared resource based upon a deterministic time for the selected thread as compared to other deterministic times for others of the threads in the queue; and an opportunistic signaling module executing in the memory of the computing system, the opportunistic signaling module permitting each of a grouping of the threads for a corresponding task to compute at least a portion of a problem in parallel and to write results from computing the portion of the problem into the shared resource using the deterministic lock managed by the deterministic lock management module, and enabling an individual one of the threads in the grouping of the threads with a lowest computed deterministic time acquiring an exclusive lock to the shared resource to autonomously terminate operation of remaining ones of the threads in the grouping of the threads by signaling the remaining ones of the threads in the grouping of the threads to abort processing while obtaining the deterministic lock on the shared resource, the remaining ones of the threads being unable to acquire an exclusive lock to the shared resource subsequent to the thread with the lowest computed deterministic time acquiring the exclusive lock to the shared resource, the shared resource being unable to write additional results by the remaining ones of the threads subsequent to the thread with the lowest computed deterministic time acquiring the exclusive lock to the shared resource, whereby the shared resource is deterministic when the thread with the lowest computed deterministic time acquires the exclusive lock to the shared resource.