Systems and methods for providing deterministic execution
Devices and methods for providing deterministic execution of multithreaded applications are provided. In some embodiments, each thread is provided access to an isolated memory region, such as a private cache. In some embodiments, more than one private cache are synchronized via a modified MOESI coherence protocol. The modified coherence protocol may be configured to refrain from synchronizing the isolated memory regions until the end of an execution quantum. The execution quantum may end when all threads experience a quantum end event such as reaching a threshold instruction count, overflowing the isolated memory region, and/or attempting to access a lock released by a different thread in the same quantum.
1. A computer-implemented method of deterministic multithreaded execution, the method comprising:
executing one or more threads via one or more execution pipelines, wherein each thread is configured to access an isolated memory region; and
in response to determining that all of the one or more threads have detected end of execution quantum events, synchronizing the isolated memory regions;
wherein the end of execution quantum events include an instruction count event, wherein the instruction count event indicates execution of a predetermined number of machine instructions by a thread, and wherein the number of machine instructions includes memory instructions and arithmetic instructions.
2. The computer-implemented method of claim 1 , further comprising tracking a number of machine instructions executed by the thread.
3. The computer-implemented method of claim 2 , wherein tracking a number of machine instructions executed by the thread includes incrementing an instruction count by an amount based on a type of instruction executed by the thread.
4. The computer-implemented method of claim 1 , wherein the end of execution quantum events include a memory full event, wherein the memory full event indicates the isolated memory region associated with a thread is full.
5. The computer-implemented method of claim 1 , wherein the end of execution quantum events include a lock request event, wherein the lock request event indicates that a thread requested a lock that had previously been released by a different thread during a current quantum.
6. The computer-implemented method of claim 1 , wherein synchronizing each of the isolated memory regions includes merging contents of the isolated memory regions using a z-buffer algorithm.
7. The computer-implemented method of claim 1 , wherein a number of threads in the one or more threads is greater than a number of execution pipelines in the one or more execution pipelines.
8. A non-transitory computer-readable medium having computer-executable instructions stored thereon that, if executed by one or more processors of a computing device, cause the computing device to perform the method of claim 1 .
9. A computing device configured to deterministically execute multiple concurrent threads, the computing device comprising:
a set of isolated memory regions;
at least one execution pipeline, wherein each execution pipeline of the at least one execution pipelines is associated with an isolated memory region of the set of isolated memory regions; and
a physical computer-readable medium having computer-executable instructions stored thereon that, in response to execution by the computing device, cause the computing device to provide:
an isolated memory space monitor configured to detect a state wherein at least one isolated memory region is full;
an instruction count monitor configured to detect execution of a predetermined number of processing instructions by a thread; and
a deterministic synchronization library configured to detect a request by a thread for a lock previously released by a different thread during a current execution quantum.
10. The computing device of claim 9 , wherein the computing device further comprises a coherence controller, and wherein the coherence controller is configured to refrain from synchronizing contents of the isolated memory regions until an end of an execution quantum is detected.
11. The computing device of claim 10 , wherein each isolated memory region includes at least one private cache associated with one of the execution pipelines.
12. The computing device of claim 11 , wherein the at least one private cache includes an L1 cache.
13. The computing device of claim 10 , wherein each isolated memory region comprises a plurality of cache lines, and wherein each cache line is associated with a write mask.
14. The computing device of claim 13 , wherein the coherence controller is configured to synchronize contents of the isolated memory regions using a modified MOESI cache coherence protocol, wherein:
the coherence controller is configured to respond to requests for a cache line having a non-null write mask with a NACK;
the coherence controller is configured to transition a cache line to a shared state before writing to the cache line; and
the coherence controller is configured to transition a cache line to an owned state after publishing contents of the cache line.
15. The computing device of claim 14 , further comprising a directory data store configured to store information regarding buffered versions of cache lines, wherein the coherence controller is configured to deterministically merge cache lines buffered in more than one isolated memory region based on information stored in the directory data store.
16. The computing device of claim 9 , wherein each execution pipeline is configured to update an instruction count upon executing one or more instructions, and wherein the instruction count monitor is configured to receive an instruction count trap from an execution pipeline in response to the execution pipeline detecting that the instruction count for a thread has exceeded a threshold.
17. The computing device of claim 9 , wherein the instruction count monitor is configured to receive an instruction count value from an executable user program that has been instrumented to provide instruction counts during execution.
18. The computing device of claim 9 , wherein the isolated memory space monitor is configured to receive a buffer full trap from an isolated memory region in response to a memory region full condition being detected.
19. The computing device of claim 9 , further comprising at least one buffered data store configured to store information from an isolated memory region for a thread that is not currently being executed by an execution pipeline.
20. A computer-implemented method of deterministic multithreaded execution, the method comprising:
executing one or more threads via one or more execution pipelines, wherein each thread is configured to access an isolated memory region; and
in response to determining that all of the one or more threads have detected end of execution quantum events, synchronizing the isolated memory regions,
wherein the end of execution quantum events include a lock request event, and
wherein the lock request event indicates that a thread requested a lock that had previously been released by a different thread during a current quantum.