Architecture support of best-effort atomic transactions for multiprocessor systems

• US 20060288173A1
• Filed: 06/20/2005
• Published: 12/21/2006
• Est. Priority Date: 06/20/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Shen, Xiaowei
• Granted Patent: US 7,350,034 B2
• Time in Patent Office: Days
• US Class Current: 711/141
• CPC Class Codes: G06F 12/0833 in combination with broadcast means (e.g. for invalidation or updating)
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: G06F 9/30072 to perform conditional operations, e.g. using predicates or guards
• CPC Class Codes: G06F 9/30087 Synchronisation or serialisation instructions

Abstract

An atomic transaction includes one or more memory access operations that are completed atomically. A Best-Effort Transaction (BET) system makes its best effort to complete each atomic transaction without guaranteeing completion of all atomic transactions. When an atomic transaction is aborted, BET may provide software with appropriate runtime information such as cause of the abortion. With proper coherence layer enhancements, BET can be implemented efficiently for multiprocessor systems, using caches as buffers for data accessed by atomic transactions. Furthermore, with appropriate fairness support, forward progress can be guaranteed for atomic transactions that incur no buffer overflow.

Claims

1. A system for executing transactions, comprising

at least one processor for executing at least one transaction, the at least one processor comprising a first processor for executing a first transaction of the at least one transaction, each of the at least one transaction comprising at least one memory access operation;

a shared memory that can be accessed by the at least one processor; and

a first cache operatively associated with the first processor, wherein the first cache serves as a buffer between the first processor and the shared memory, such that the first cache maintains data accessed by the first transaction throughout the execution of the first transaction;

wherein the first cache comprises a first cache line, the first cache line comprising a first flag and a first color;

wherein, if the first cache line is currently accessed by the first transaction, the first cache sets the first flag to indicate that the first cache line is currently accessed by some transaction;

wherein, if the first cache line is currently accessed by the first transaction, the first cache sets the first color to indicate the first transaction.

2. The system of claim 1,

wherein, when the execution of the first transaction is completed, the first cache clears the first flag to indicate that the first cache line is not currently accessed by any transaction;

and

wherein, when the execution of the first transaction is aborted prior to completion, the first cache (a) clears the first flag to indicate that the first cache line is not currently accessed by any transaction, and (b) invalidates the first cache line if the first cache line is modified by the first transaction.

3. The system of claim 2, wherein the first cache aborts one of the first transaction or a second transaction of the at least one transaction, if the first cache detects at least one of a data race, a color race, or a replacement conflict, between the first transaction and the second transaction.

4. The system of claim 3, further comprising

a second cache operatively associated with a second processor of the at least one processor, the second processor for executing the second transaction;

wherein the second cache serves as a buffer between the second processor and the shared memory, such that the second cache maintains data accessed by the second transaction throughout the execution of the second transaction; and

wherein the first cache detects a data race between the first transaction and the second transaction, if at least one of the following conditions is true;

(a) the first cache receives a snoop request from the second cache, the snoop request indicating that the second transaction intends to modify data of the first cache line, the first cache line being currently accessed by the first transaction;

or

(b) the first cache receives a snoop request from the second cache, the snoop request indicating that the second transaction intends to read data of the first cache line, the first cache line being currently modified by the first transaction.

5. The system of claim 3,

wherein the first cache, in addition to maintaining data accessed by the first transaction throughout the execution of the first transaction, further maintains data accessed by the second transaction throughout the execution of the second transaction, the second transaction being executed by one of the first processor or a second processor of the at least one processor;

and

wherein the first cache detects a data race between the first transaction and the second transaction, if at least one of the following conditions is true;

(a) the first cache receives a memory write operation, the memory write operation indicating that the second transaction intends to modify the first cache line, the first cache line being currently accessed by the first transaction;

or

(b) the first cache receives a memory read operation, the memory read operation indicating that the second transaction intends to read the first cache line, the first cache line being currently modified by the first transaction.

6. The system of claim 3,

wherein the first cache, in addition to maintaining data accessed by the first transaction throughout the execution of the first transaction, further maintains data accessed by the second transaction throughout the execution of the second transaction, the second transaction being executed by one of the first processor or a second processor of the at least one processor;

and

wherein the first cache detects a color race between the first transaction and the second transaction, if the first cache receives a memory read operation, the memory read operation indicating that the second transaction intends to read the first cache line, the first cache line being currently read, but not modified, by the first transaction.

7. The system of claim 3,

wherein the first cache, in addition to maintaining data accessed by the first transaction throughout the execution of the first transaction, further maintains data accessed by the second transaction throughout the execution of the second transaction, the second transaction being executed by one of the first processor or a second processor of the at least one processor;

and

the first cache detects a replacement conflict between the first transaction and the second transaction, if (a) the first cache line is currently accessed by the first transaction, (b) the first cache receives a memory access operation generated from the second transaction, the memory access operation causing a cache miss in the first cache, and (c) a cache line replacement mechanism associated with the first cache suggests that the first cache line be used to hold requested data of the memory access operation.

8. The system of claim 3, further comprising a fairness mechanism associated with the first cache, the fairness mechanism determining which one of the first transaction or the second transaction is aborted, when the first cache detects at least one of a data race, a color race or a replacement conflict, between the first transaction and the second transaction.

9. The system of claim 2,

wherein, when the first transaction performs a memory write operation on the first cache line, if (a) the first cache line has been modified by some memory write operation, (b) data of the first cache line has not been written to the shared memory, and (c) the first cache line is currently not accessed by any transaction, the first cache writes data of the first cache line to the shared memory before the memory write operation is performed.

10. The system of claim 2,

wherein, when the first transaction performs a memory read operation on the first cache line, if (a) the first cache line has been modified by some memory write operation, (b) data of the first cache line has not been written to the shared memory, and (c) the first cache line is currently not accessed by any transaction, the first cache sets state of the first cache line to modified-with-atomic-read, without writing data of the first cache back to the shared memory;

and

wherein, when the execution of the first transaction is one of completed or aborted, if the first cache line is in a modified-with-atomic-read state, the first cache sets the first cache line to a modified state, the modified state indicating that (a) the first cache line has been modified by some memory write operation, and (b) data of the first cache line has not been written to the shared memory.

11. The system of claim 2, wherein, when the first cache detects a buffer overflow for the first transaction, the first cache aborts the first transaction.

12. The system of claim 2, further comprising:

a first backup buffer operatively associated with the first cache, wherein the first backup buffer maintains data of the first cache line, if (a) the first cache line is currently modified by the first transaction, and (b) the first cache line needs to be replaced from the first cache; and

a second backup buffer operatively associated with the first cache, wherein the second backup buffer maintains address of the first cache line, if (a) the first cache line is currently read, but not modified, by the first transaction, and (b) the first cache line needs to be replaced from the first cache.

13. A method of executing a transaction on a system, the transaction comprising at least one memory access operation, the method comprising the steps of:

receiving the transaction from software, the software being executed on the system;

executing the transaction on the system, wherein the step of executing the transaction comprises one of;

(1) completing the transaction;

or

(2) aborting the transaction, wherein the step of aborting the transaction comprises one of;

(2.1) terminating the transaction, if re-execution of the transaction is certain to cause another abortion;

or

(2.2) making best-effort to execute the transaction, if re-execution of the transaction is uncertain to cause another abortion, wherein the step of making best-effort to execute the transaction comprises one of;

(2.2.1) re-executing the transaction, if the system decides to re-execute the transaction;

or

(2.2.2) terminating the transaction, if the system decides not to re-execute the transaction.

14. The method of claim 13, wherein in the step (2) of aborting the transaction, re-execution of the transaction is certain to cause another abortion, if the abortion is caused by a buffer overflow.

15. The method of claim 13, wherein in the step (2) of aborting the transaction, re-execution of the transaction is uncertain to cause another abortion, if the abortion is caused by at least one of a data race, a color race or a replacement conflict.

16. The method of claim 13, wherein in the step (2.2) of making best-effort to execute the transaction, the system decides to re-execute the transaction, if the system guarantees forward progress of the transaction.

17. The method of claim 13, wherein the each of steps (2.1) and (2.2.2) of terminating the transaction comprises informing the software of the abortion of the transaction.

18. The method of claim 13, wherein the system provides software with appropriate runtime information about the transaction.

19. The system of claim 18, wherein the appropriate runtime information comprises at least one of the following:

(a) whether the first transaction is completed or aborted;

(b) whether the first transaction is aborted due to a data race;

(c) whether the first transaction is aborted due to a color race;

(d) whether the first transaction is aborted due to a replacement conflict;

(e) whether the first transaction is aborted due to a buffer overflow;

(f) number of times the first transaction is aborted due to a data race;

(g) number of times the first transaction is aborted due to a color race;

(h) number of times the first transaction is aborted due to a replacement conflict;

(i) number of times the first transaction is re-executed;

(j) number of cache lines accessed by the first transaction;

(k) number of cache lines read by the first transaction;

or

(l) number of cache lines modified by the first transaction.

20. A system for executing transactions, comprising:

a first instruction, the first instruction enabling software to abort a transaction in a program, the transaction comprising at least one memory access operation;

wherein, if the system executes the first instruction throughout the execution of the transaction, the system aborts the execution of the transaction, causing semantic effect of the at least one memory access operation to be cancelled, the semantic effect comprising memory modification performed by the at least one memory access operation.