DETERMINISTIC MULTIPROCESSING

• US 20090165006A1
• Filed: 12/12/2008
• Published: 06/25/2009
• Est. Priority Date: 12/12/2007
• Status: Active Grant

• Current Assignee: University of Washington
• Original Assignee: University of Washington
• Inventors: Ceze, Luis H., Oskin, Mark H.
• Granted Patent: US 8,694,997 B2
• Time in Patent Office: Days
• US Class Current: 718/102
• CPC Class Codes: G06F 9/463 Program control block organisation
• CPC Class Codes: G06F 9/466 Transaction processing
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/522 Barrier synchronisation
• CPC Class Codes: G06F 9/544 Buffers; Shared memory; Pipes

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 facility may operate together with a transactional memory system. When the facility operates together with a transactional memory system, each quantum is encapsulated in a transaction that, may be executed concurrently with other transactions, and is committed according to the specified deterministic order.

Claims

1. A method in a computing system of augmenting a multithreaded application to provide deterministic execution of the multithreaded application on a multiprocessing system, the method comprising:

accessing multithreaded application code specifying two or more threads of execution; and

automatically inserting synchronization code into the multithreaded application code capable of causing the two or more threads to each execute in a deterministic order operations that are capable of affecting a state accessible by at least one other of the two or more threads when the multithreaded application code is executed.

2. The method of claim 1 wherein the deterministic order is the order in which the two or more threads were created.

3. The method of claim 1 wherein the deterministic order is determined according to a value of a token, and wherein the method further comprises:

for each thread of the two or more threads, prior to executing an operation capable of affecting a state accessible by at least one of the two or more threads;

invoking the synchronization code to determine the value of the token;

when the determined value of the token matches a thread identifier of the thread, allowing execution of the operation; and

when the determined value of the token does not match a thread identifier of the thread, suspending execution of the thread.

4. The method of claim 1 wherein the inserted synchronization code includes one or more locks.

5. The method of claim 1 wherein the method is performed by a compiler.

6. A method in a computing system for augmenting a transactional memory system to provide deterministic execution of a multithreaded application, the method comprising:

accessing code for a transactional memory system, the code including one or more implementations of an interface called by code compiled from source code of a multithreaded application, wherein the multithreaded application source code declares one or more code blocks as atomic blocks, and wherein the multithreaded application source code specifies two or more threads; and

augmenting the accessed code to include synchronization code such that when the multithreaded application code is executed the two or more threads commit transactions in a deterministic order.

7. The method of claim 6 further comprising augmenting the accessed code to include synchronization code such that, when the multithreaded application code is executed, the two or more threads begin transactions in the deterministic order.

8. The method of claim 6 wherein transactions are executed concurrently.

9. The method of claim 6 wherein the deterministic order is the order in which the two or more threads were created.

10. The method of claim 6 wherein the deterministic order is determined with reference to a token;

and

prior to committing a transaction for one of the two or more threads, invoking the synchronization code to determine whether the token matches a thread identifier of the thread,

when the token matches the thread identifier, committing the transaction; and

when the token does not match the thread identifier, suspending the transaction.

11. The method of claim 6 further comprising, prior to committing a distinguished transaction,

invoking the synchronization code to determine whether an operation executed by a thread during a distinguished transaction conflicts with another operation executed by another thread;

and

when a conflict exists, aborting the distinguished transaction.

12. The method of claim 11 wherein a conflict exists when the operations resulted in the thread accessing a state affected by the other thread.

13. The method of claim 11 wherein a conflict exists when the operations resulted in the thread affecting a state accessed by the other thread, and wherein the deterministic order is such that the other thread will be presented with an opportunity to commit a transaction prior to the thread committing the distinguished transaction.

14. The method of claim 13 wherein the distinguished transaction and the other transaction are aborted.

15. The method of claim 14 further comprising prior to restarting the distinguished transaction, restarting and committing the other transaction.

16. A multiprocessing system comprising:

code of a transactional memory system, wherein the code includes an interface specifying a function to commit a transaction;

multithreaded application code specifying two or more threads that invoke the function of the interface of the transactional memory system to commit transactions; and

an augmentation component to insert synchronization code into the multithreaded application code such that when the function to commit a transaction is invoked, the two or more threads commit transactions in a deterministic order.

17. The multiprocessing system of claim 16 wherein the multiprocessing system includes at least one multi-core processor.

18. The multiprocessing system of claim 16 wherein the multiprocessing system includes at least two processors.

19. The multiprocessing system of claim 16 wherein the transactional memory system is a software transactional memory system.

20. The multiprocessing system of claim 16 wherein the transactions are executed concurrently.

21. The multiprocessing system of claim 16 wherein the interface further specifies a function to begin a transaction, and wherein the augmentation component inserts code into the multithreaded application code such that when the function to begin a transaction is invoked, the two or more threads begin transactions in a deterministic order.

22. The multiprocessing system of claim 16 wherein the deterministic order is the order in which the two or more threads were created.

23. The multiprocessing system of claim 16 further comprising a token, wherein the token deterministically specifies as its value a thread identifier corresponding to one of the two or more threads;

wherein the deterministic order is determined by examining the value of the token; and

wherein, when a transaction is committed by a thread whose thread identifier matches the value of the token, the value of the token is advanced to specify a next thread identifier of one of the two or more threads.

24. The multiprocessing system of claim 23 wherein, prior to committing a transaction, the synchronization code is invoked by a thread to determine whether a thread identifier value of the thread matches the value of the token;

when the thread identifier matches the value of the token, the thread commits the transaction; and

when the thread identifier does not match the value of the token, the thread waits to commit the transaction until the value of the token matches the thread identifier.

25. The multiprocessing system of claim 23 wherein, prior to committing a transaction, the synchronization code is invoked by a distinguished thread to determine whether a conflict exists between an operation performed by the distinguished thread and an operation performed by another thread;

and wherein, when a conflict exists, aborting the transaction.

26. The multiprocessing system of claim 25 wherein a conflict exists when the operation performed by the distinguished thread resulted in the distinguished thread accessing a state affected by the operation performed by the other thread.

27. The multiprocessing system of claim 25 wherein a conflict exists when the operation performed by the distinguished thread resulted in the distinguished thread affecting a state accessed by the operation of the other thread when the token deterministically specifies the thread identifier of the other thread prior to advancing the value of the token to specify the thread identifier of the distinguished thread;

and

wherein a conflict does not exist when the operation performed by the distinguished thread resulted in the distinguished thread affecting a state access by the operation of the other thread when the token deterministically specifies the thread identifier of the distinguished thread prior to advancing the value of the token to specify the thread identifier of the other thread.

28. A computer-readable storage medium storing a data structure usable to deterministically control the global interleaving of threads of a multithreaded application when the multithreaded application is executed on a multiprocessing system, the data structure comprising:

a thread container storing a thread identifier for each of a plurality of threads of the multithreaded application; and

a token variable specifying a value that corresponds to a thread identifier stored in the thread container, wherein the value of the token variable advances deterministically according to a sequence in which the thread identifiers are stored in the thread container.

29. The computer-readable storage medium of claim 28 wherein the thread identifiers are stored in the thread container in an order in which the plurality of threads were created.

30. The computer-readable storage medium of claim 28 wherein the thread identifiers are stored in the thread container in an order specified by a user.

31. The computer-readable storage medium of claim 28 wherein the data structure further comprises a commit block size specifying a predetermined number of operations, and wherein the value of the token is deterministically advanced when a thread whose thread identifier matches the value of the token variable executes the predetermined number of operations specified by the commit block size.

32. The computer-readable storage medium of claim 31 wherein only operations that capable of affecting a state accessible by another thread are included in the predetermined number of operations.

33. The computer-readable storage medium of claim 31 wherein the commit block size is specified by a user.

34. The computer-readable storage medium of claim 28 wherein the computer-readable storage medium further comprises a transactional memory system, and wherein the token is deterministically advanced when a thread whose thread identifier matches the value of the token variable commits a transaction.

35. The computer-readable storage medium of claim 33 wherein the transactional memory system is a software transactional memory system.

36. The computer-readable storage medium of claim 33 wherein the transactional memory system is a hardware transactional memory system.

37. A method is a multiprocessing system for controlling the order of memory operations, 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 specifying a deterministic number of operations that include memory operations; and

specifying a deterministic order in which the plurality of threads execute the two or more quantum,

wherein, when the multithreaded application code is executed, inter-thread communication specifying memory operations is deterministic.

38. The method of claim 37 wherein the inter-thread communication occurs when at least one thread of the plurality of threads loads data that is privately held by another thread of the plurality of threads.

39. The method of claim 38 further comprising, when a thread attempts to load data that is privately held by another thread, suspending execution of the thread until each of the plurality of threads reaches a deterministic point in its execution and the deterministic order specifies that the thread is to proceed with execution.

40. The method of claim 39 wherein a thread reaches a deterministic point in its execution when it completes execution of a quantum.

41. The method of claim 37 wherein the inter-thread communication occurs when one thread of the plurality of threads stores data that is not privately held by the one thread.

42. The method of claim 41 further comprising, when a thread attempts to store data that is not privately held by the thread, suspending execution of the thread until each of the plurality of threads reaches a deterministic point in its execution and the deterministic order specifies that the thread is to proceed with execution.

43. The method of claim 42 wherein a thread reaches a deterministic point in its execution when it is suspended.

44. The method of claim 37 wherein specifying a deterministic order includes inserting synchronization code within the multithreaded application code.

45. The method of claim 44 wherein the inserted synchronization code includes one or more locks.

46. The method of claim 44 wherein the inserted code implements a sharing table to monitor the inter-thread communication.

47. The method of claim 44 wherein the multiprocessing system includes a transactional memory system,

wherein inserting synchronization code includes encapsulating each quantum within a transaction, and

wherein the transactional memory system commits each transaction in the specified deterministic order.

48. The method of claim 47 wherein the transactional memory system begins each transaction in the specified deterministic order.

49. The method of claim 47 wherein the transactions are executed concurrently.

50. The method of claim 49 further comprising:

detecting a conflict between two transactions;

aborting at least one of the conflicted transactions; and

restarting the at least one aborted transaction according to the specified deterministic order.

51. The method of claim 50 wherein the conflict is detected by the transactional memory system.

52. The method of claim 50 wherein the conflict is detected by the augmenting an interface of the transactional memory system to callback to a deterministic function for each memory operation specified by a transaction.

53. The method of claim 47 wherein the transactional memory system is a software transactional memory system.

54. The method of claim 47 wherein the transactional memory system is a hybrid hardware-software transactional memory system.

55. The method of claim 47 wherein the transactional memory system is a hardware transactional memory system.

56. The method of claim 37 wherein the method is performed exclusively in hardware.

57. The method of claim 37 wherein the multiprocessing system includes one or more multi-core processors.

58. The method of claim 37 wherein the method selectively serializes execution of the multithreaded application code.

59. The method of claim 58 wherein the specified deterministic number of operations further includes system operations.

60. The method of claim 37 wherein the deterministic order is specified by the order in which the threads are created.

61. The method of claim 37 wherein the deterministic order is specified by a user.

62. The method of claim 37 wherein the deterministic order is specified according to a value of a token, and wherein the method further comprises:

for each of the plurality of threads, prior to executing a memory operation;

determining the value of the token;

when the determined value of the token matches a thread identifier of the thread, allowing execution of the memory operation when every other thread of the plurality of threads reaches a deterministic point in its execution; and

when the determined value of the token does not match a thread identified of the thread, suspending execution of the thread.

63. A multiprocessing system for controlling the interleaving of threads of a 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 specifying a deterministic number of operations; and

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

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

64. The system of claim 63 wherein the multithreaded application code on is executed on the multiprocessing system, and wherein the multiprocessing system is operated by a software developer of the multithreaded application code.

65. The system of claim 63 wherein the quantum builder component is implemented in hardware.

66. The system of claim 63 wherein the deterministic component is implemented in hardware.

67. The system of claim 63 wherein the quantum builder component selectively serializes execution of the multithreaded application code by including within the specified deterministic number of operations only particular operations that have been designated as controlled operations.

68. The system of claim 67 wherein the operations designated as controlled operations include system operations.

69. The system of claim 67 wherein the operations designated as controlled operations include memory operations.

70. The system of claim 69 wherein, when one thread of the plurality of threads is to perform a memory operation that is capable of affecting the state of another one of the plurality of threads, the quantum builder component determines whether the memory operation will violate the deterministic order specified by the deterministic component,

wherein, when the memory operation violates the deterministic order, the multiprocessing system suspends execution of the memory operation until each thread of the plurality of threads reaches a deterministic point in their execution and the deterministic component specifies that the thread is to proceed, and

wherein, when the memory operation does not violate the deterministic order, the multiprocessing system permits execution of the memory operation.

71. The system of claim 70 wherein the memory operation does not violate the deterministic order when the memory operation specifies that the thread is to load or store data that is regarded as privately held by the thread.

72. The system of claim 70 wherein the memory operation does not violate the deterministic order when the memory operation specifies that the thread is to load data that is regarded as shared by the plurality of threads.

73. The system of claim 70 wherein the memory operation violates the deterministic order when the memory operation specifies that the thread is to load or store data that is regarded as privately held by another thread.

74. The system of claim 70 wherein the memory operation violated the deterministic order when the memory operation specifies that the thread is to store data that is regarded as shared by the plurality of threads.

75. The system of claim 70 wherein the memory operation violates the deterministic order when the memory operation specifies that the thread is to load or store data that has not previously been accessed by any of the plurality of threads.

76. The system of claim 70 wherein each thread of the plurality of threads reaches a deterministic point in their execution when the multiprocessing system has suspended execution of each thread.

77. The system of claim 70 wherein each thread of the plurality of threads reaches a deterministic point in their execution when each thread is completes execution of a quantum.

78. The system of claim 69 wherein the quantum builder component divides the multithreaded application code into two or more quantum by inserting synchronization code within the multithreaded application code.

79. The system of claim 78 wherein the inserted synchronization code includes one or more locks.

80. The system of claim 78 wherein the inserted synchronization code includes a sharing table for tracking memory operations.

81. The system of claim 78 further includes a transactional memory system, wherein the inserted synchronization code encapsulates each quantum within a transaction;

and wherein each transaction is committed in the deterministic order specified by the deterministic component.

82. The system of claim 81 wherein the transactions are executed concurrently.

83. The system of claim 82 wherein when a conflict exists between two or more concurrently executed transactions, at least one of the transactions is aborted and restarted according to the deterministic order.

84. The system of claim 83 wherein the conflict is identified by the transactional memory system.

85. The system of claim 83 wherein the conflict is identified by the quantum builder component.

86. The system of claim 81 wherein the included transactional memory system is selected from the group comprising:

a hardware transactional memory system, a software transactional memory system, a hybrid hardware-software transactional memory system, and a combination of transactional memory systems.

87. The system of claim 69 wherein the deterministic order is specified based on an order in each of the plurality of threads was created.

88. The system of claim 69 wherein the deterministic order is specified to the deterministic component by a software developer of the multithreaded application code.

89. The system of claim 69 wherein the deterministic component implements a token that is used to specify the deterministic order.

90. The system of claim 89 wherein the token is passed in the specified deterministic order between processors or cores of the multiprocessing system on which the plurality of threads execute.

91. The system of claim 89 wherein the token is passed in the specified deterministic order between each of the plurality of threads.

92. The system of claim 89 wherein, prior to a thread executing a memory operation, the multiprocessing system compares the token to an identifier of the thread;

when the token matches the identifier of the thread, allowing execution of the memory operation when each of the plurality of threads reaches a deterministic point in its execution; and

when the token does not match the identifier, suspending execution of the thread until the token matches the identifier of the thread and each of the plurality of threads reaches a deterministic point in its execution.

93. 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 specifying a finite, deterministic number of memory operations; and

code to encapsulate each quantum within a transaction that is deterministically committed by one of two or more threads specified by the multithreaded application;

wherein the multiprocessing system operates together with a transactional memory system.

94. The computer-readable storage medium of claim 93 wherein the transactional memory system is selected from the group comprising:

a hardware transactional memory system, a software transactional memory system, a hybrid hardware-software transactional memory system, and a combination of transactional memory systems.

95. The computer-readable storage medium of claim 93 wherein each quantum that is encapsulated within a transaction is deterministically committed by one of the two or more threads according to an order in which the two or more threads are created.

96. The computer-readable storage medium of claim 93 wherein transactions are executed concurrently.

97. The computer-readable storage medium of claim 96 further storing a token that is used to specify an order in which the two or more threads deterministically commit transactions.

98. The computer-readable storage medium of claim 97 further storing:

code to identify a conflict between one or more concurrently executed transactions;

code to abort at least one of the one or more conflicted transactions when a conflict is identified; and

instructions to deterministically restart the at least on aborted transaction according to the order specified by the token.

99. The computer-readable storage medium of claim 98 wherein,

a conflict is identified when a memory operation of the at least one transaction specifies that one of the two or more threads is to load or store data that is regarded as privately held by another one of the two or more threads;

a conflict is identified when a memory operation of the at least one transaction specifies that one of the two or more threads is to store data that is regarded as shared by the two or more threads; and

a conflict is identified when a memory operation of the at least one transaction specifies that one of the two or more threads is to load or store data that has not previously been accessed by another one of the two or more threads.

100. The computer-readable storage medium of claim 98 wherein, a conflict is not identified when a memory operation of the at least one transaction specifies that one of the two or more threads is to load or store data that is regarded as privately held by the one thread;

and

a conflict is not identified when a memory operation of the at least one transaction specifies that one of the two or more threads is to load data that is regarded as shared by the two or more threads.

101. The computer-readable storage medium of claim 97 further storing code to, before a transaction is committed by one of the two or more threads, suspend execution of the one thread until,

each of the two or more threads reaches a deterministic point in its execution;

and

the token specifies that the thread is to commit the transaction.

102. The computer-readable storage medium of claim 101 wherein each thread reaches a deterministic point in its execution when each thread has completed execution of a transaction.

103. The computer-readable storage medium of claim 93 wherein the code is provided by a runtime system.

104. The computer-readable storage medium of claim 93 wherein the code is used to augment the multithreaded application code.

105. The computer-readable storage medium of claim 104 wherein the multithreaded application code includes one or more transactional memory blocks specified by a software developer of the multithreaded application code, and wherein the code is further used to augment the one or more transactional memory blocks.

106. The computer-readable storage medium of claim 93 wherein the code is used to augment an interface provided by the transactional memory system.