EFFICIENT DETERMINISTIC MULTIPROCESSING

• US 20090235262A1
• Filed: 03/11/2009
• Published: 09/17/2009
• Est. Priority Date: 03/11/2008
• Status: Active Grant

• Current Assignee: University of Washington
• Original Assignee: University of Washington
• Inventors: Lucia, Brandon Michael, Devietti, Joseph Luke, Oskin, Mark H., Ceze, Luis
• Granted Patent: US 8,739,163 B2
• Time in Patent Office: Days
• US Class Current: 718/102
• CPC Class Codes: G06F 11/3632 of specific synchronisation aspects
• CPC Class Codes: G06F 9/30087 Synchronisation or serialisation instructions
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A hardware and/or software facility for controlling the order of operations performed by threads of a multithreaded application on a multiprocessing system is provided. The facility may serialize or selectively-serialize execution of the multithreaded application such that, given the same input to the multithreaded application, the multiprocessing system deterministically interleaves operations, thereby producing the same output each time the multithreaded application is executed. The facility divides the execution of the multithreaded application code into two or more quantum specifying a deterministic number of operations, and the facility specifies a deterministic order in which the threads execute the two or more quantum. The deterministic number of operations may be adapted to follow the critical path of the multithreaded application. Specified memory operations may be executed regardless of the deterministic order, such as those accessing provably local data. The facility may provide dynamic bug avoidance and sharing of identified bug information.

Claims

1. A multiprocessing system for controlling the interleaving of threads of a multithreaded application on a critical path of the multithreaded application, the system comprising:

multithreaded application code specifying a plurality of threads;

a quantum builder component to divide the multithreaded application code into two or more quanta, each quantum constituting a predetermined number of operations;

a deterministic execution component to specify a deterministic order in accordance with which synchronization code causes threads of the multithreaded application to execute the two or more quanta; and

an adaptive quantum builder component to monitor thread execution and determine whether to invoke the synchronization code prior to executing its predetermined number of operations; and

a quantum completion component to monitor thread execution and, if the synchronization code is not invoked by the adaptive quantum builder component, to invoke the synchronization code in response to a thread executing its predetermined number of operations;

wherein, when a particular input is specified for multiple executions passes of the multithreaded application code, each execution pass produces the same output for the particular input.

2. The multiprocessing system of claim 1 wherein the adaptive quantum builder component monitors thread execution for a change to an application-level synchronization primitive.

3. The multiprocessing system of claim 2 wherein the change to an application-level synchronization primitive is a release of a lock.

4. The multiprocessing system of claim 2 wherein, when the lock is released, the adaptive quantum builder component ends the quantum boundary.

5. The multiprocessing system of claim 1 wherein the adaptive quantum builder component monitors thread access to shared memory.

6. The multiprocessing system of claim 5 wherein, when a threshold number of operations access memory other than memory designated as shared memory, the adaptive quantum builder component ends the quantum boundary.

7. The multiprocessing system of claim 1 wherein the adaptive quantum builder component monitors thread execution by inserting code within the multithreaded application code.

8. The multiprocessing system of claim 7 wherein the inserted synchronization code includes a sharing table for tracking memory operations.

9. The multiprocessing system of claim 1 wherein the deterministic component implements a token that is used to specify the deterministic order and wherein the adaptive quantum builder component monitors thread execution of a thread specified by the token.

10. The method of claim 1 wherein the method is performed exclusively in hardware.

11. The method of claim 1 wherein the method is performed exclusively in software.

12. The method of claim 1 wherein the method is performed using a combination of hardware and software.

13. A method in a multiprocessing system for controlling the order of memory operations executed by threads of a multithreaded application, the method comprising:

executing multithreaded application code on a multiprocessing system, the multithreaded application code specifying a plurality of threads;

dividing the execution of the multithreaded application code into two or more quanta, each quantum constituting a predetermined number of operations that include memory operations;

specifying a deterministic order in which the plurality of threads execute the two or more quanta, wherein, when the multithreaded application code is executed, inter-thread communication specifying memory operations is deterministic; and

monitoring thread execution of a quantum to determine whether to end a quantum prior to execution of the predetermined number of operations.

14. The method of claim 13 wherein the deterministic order in which the plurality of threads execute the two or more quanta is specified by a token such that, when the token matches an identifier of a thread, the thread executes a quantum.

15. The method of claim 14 wherein monitoring thread execution includes:

tracking a number of accesses to private data issued by the thread whose identifier matches the token; and

ending the quantum prior to the execution of the predetermined number of operations when the number of accesses to private data issued by the thread exceed a predefined number.

16. The method of claim 14 wherein monitoring thread execution includes:

receiving an indication that an application-level synchronization primitive is released by the thread whose identifier matches the token; and

ending the quantum prior to execution of the predetermined number of operations in response to the release of the application-level synchronization primitive.

17. The method of claim 13 wherein monitoring thread execution includes inserting synchronization code within the multithreaded application code.

18. A computer-readable storage medium storing code that is capable of causing a multiprocessing system to control the order of memory operations executed by threads of a multithreaded application, the code comprising:

code to divide multithreaded application code into multiple quanta, each quantum constituting a predetermined number of memory operations;

code to specify a deterministic order in which the multiple quanta are to be executed; and

code to end a quantum before a thread completes execution of the predetermined number of memory operations so that the deterministic execution of the multithreaded application follows a critical path of the multithreaded application.

19. A method in a multiprocessing system for deploying a multithreaded application and controlling the order of memory operations executed by threads of the multithreaded application, the method comprising:

executing multithreaded application code within a virtual machine executing on a multiprocessing system, the multithreaded application code specifying a plurality of threads;

dividing the execution of the multithreaded application code into a plurality of quanta, each quantum constituting a predetermined number of operations that include memory operations;

specifying a deterministic order in which particular threads execute quanta among the plurality of quanta, wherein, when the multithreaded application code is executed, memory operations specifying inter-thread communication are executed deterministically;

tracking the inter-thread communication within the virtual machine to determine whether the specified deterministic order matches a known order in which particular threads execute quanta observed to result in a crash; and

in response to determining that the specified deterministic order matches a known order, avoiding further execution of the known order.

20. The method of the claim 19 wherein avoiding further execution of the known order includes specifying a new deterministic order in which particular threads execute quanta among the plurality of quanta.

21. The method of claim 19 wherein avoiding further execution of the known order includes changing the predetermined number of operations in a quantum.

22. The method of claim 21 wherein the change is random.

23. A multiprocessing system for dynamic bug avoidance in a deployed multithreaded application, the multiprocessing system comprising:

deployed multithreaded application code specifying a plurality of threads;

a quantum builder component to divide the code into two or more quanta, each quantum constituting a deterministic number of operations;

a deterministic component to specify a deterministic order in which threads of the multithreaded application execute the two or more quanta; and

a dynamic bug avoidance component to monitor communications between the plurality of threads in the specified deterministic order and avoid execution of a known concurrency bug, wherein the known concurrency bug is a sequence of communication between the plurality of threads that previously caused the multithreaded application to crash.

24. The multiprocessing system of claim 23 wherein the code is deployed within a virtual machine.

25. The multiprocessing system of claim 23 wherein the monitored communications are memory operations accessing shared memory.

26. The multiprocessing system of claim 23 wherein execution of a known concurrency bug is avoided by the deterministic component specifying a new deterministic order.

27. The multiprocessing system of claim 23 wherein execution of a known concurrency bug is avoided by the quantum builder component specifying a new deterministic number of operations and dividing the code into two or more quanta, each quantum specifying the new deterministic number of operations.

28. The multiprocessing system of claim 23 wherein the multiprocessing system further comprises:

a local bug library storing a plurality of known concurrency bugs; and

a bug reporting component to identify a deterministic order and a sequence of communication between the plurality of threads when the multithreaded application crashes and to update the local bug library to include a new known concurrency bug corresponding to the identified deterministic order and the identified sequence of communication.

29. The multiprocessing system of claim 28 wherein the bug reporting component sends an update including information associated with the new known concurrency bug to a bug aggregator system.

30. The multiprocessing system of claim 28 wherein the bug reporting component receives updates from a bug aggregator system, wherein the updates include information associated with concurrency bugs of the multithreaded application and wherein the bug reporting component updates the local bug library to include the received information.

31. A method in a multiprocessing system for recovering parallelism in a multithreaded application specifying a plurality of threads that are executed in a deterministic order, the method comprising:

dividing multithreaded application code specifying a plurality of threads into two or more quanta, each quantum constituting a predetermined number of operations to be executed by a thread;

for each quantum to be executed by a thread,

identifying any operations that access memory locations that are provably local to the thread; and

inserting synchronization code within the multithreaded application code to specify a deterministic order in which the plurality of threads execute the two or more quanta, wherein the inserted synchronization code implements a shared-memory data structure for monitoring operations that access memory locations other than the identified operations that access memory locations that are provably local to the thread.

32. The method of claim 31 further comprising:

executing the multithreaded application code; and

when the thread issues an operation to access a memory location that is identified in the sharing table as private to another thread, suspending execution of the thread until each of the plurality of threads reaches a deterministic point in execution and the deterministic order specifies that the thread is to proceed with execution.

33. The method of claim 32 further comprising:

when the thread issues an operation to access a memory location that is provably location to the thread, executing the operation regardless of the specified deterministic order.

34. A computer-readable storage medium storing code that is capable of causing a multiprocessing system to control the order of memory operations executed by threads of a multithreaded application, the code comprising:

code to divide multithreaded application code into multiple quanta, each quantum constituting a predetermined number of memory operations;

code to specify a deterministic order in which the multiple quanta are to be executed; and

code to make deterministic the execution, by different threads, of memory operations that access memory locations not proven to be local to a single thread, while allowing concurrent execution, by the single thread, of memory operations that access a memory location proven to be local to the single thread.

35. A method in a multiprocessing system for recovering parallelism in a multithreaded application specifying a plurality of threads that are executed in a deterministic order, the method comprising:

dividing multithreaded application code specifying a plurality of threads into two or more quanta, each quantum constituting a predetermined number of operations to be executed by a thread;

parsing a quantum that, for each of one or more different memory locations, contains at least one memory operation that accesses the memory location, for at least one of the memory locations the quantum containing a plurality of memory operations that each access the memory location; and

generating from the multithreaded application code result code in which, for each of the different accessed memory locations, synchronization code is inserted only for a first-occurring memory operation that accesses the memory location, wherein the synchronization code is used to specify a deterministic order in which the plurality of threads execute the two or more quanta.

36. The method of claim 35 further comprising:

executing the result code.

37. A method in a multiprocessor system for testing multithreaded applications, the method comprising:

receiving from a development computer a request to test a multithreaded application specifying a plurality of threads;

in the absence of any payment in connection with the received request;

dividing multithreaded application into two or more quanta, each quantum constituting a predetermined number of operations to be executed by a thread of the plurality of threads;

specifying a deterministic order in which the plurality of threads execute the two or more quanta; and

for a plurality of execution passes of the multithreaded application, identifying for each execution pass whether a bug exists for a specified input;

when no bug is identified, sending to the development computer an indication that no bug was identified in the multithreaded application; and

when one or more bugs are identified,

sending to the development computer an indication that one or more bugs were identified; and

offering to reveal the identified bugs for a fee.

38. The method of claim 37 further comprising:

receiving from the development computer an indication that the offer to reveal the identified bugs for a fee is accepted; and

revealing the identified bugs.

39. The method of claim 38 further comprising:

providing a mechanism to replay the identified bugs at the development computer.

40. The method of claim 37 wherein a new deterministic order is specified for each execution pass.

41. The method of claim 37 wherein, for each execution pass, the multithreaded application is divided into two or more quanta, each quantum constituting a new predetermined number of operations to be executed by a thread of the plurality of threads.

42. The method of claim 37 wherein the fee is based on the number of bugs identified.

43. A computer-readable medium whose contents are capable of causing a computing system to perform a method for testing a computer program, the method comprising:

receiving from a development computer a request to test an identified computer program;

in the absence of any payment in connection with the received request;

testing the computer program to attempt to identify bugs contained by the computer program;

when no bug is identified, sending to the development computer an indication that no bug was identified in the computer program; and

when one or more bugs are identified,

sending to the development computer an indication that one or more bugs were identified; and

offering to reveal the identified bugs for a fee.