ACCELERATING UNBOUNDED MEMORY TRANSACTIONS USING NESTED CACHE RESIDENT TRANSACTIONS

• US 20110145802A1
• Filed: 12/15/2009
• Published: 06/16/2011
• Est. Priority Date: 12/15/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Levanoni, Yosseff, Sheaffer, Gad, Adl-Tabatabai, Ali-Reza
• Granted Patent: US 8,539,465 B2
• Time in Patent Office: Days
• US Class Current: 717/151
• CPC Class Codes: G06F 9/467 Transactional memory G06F9/528 takes precedence

Abstract

Using cache resident transaction hardware to accelerate a software transactional memory system. The method includes identifying a plurality of atomic operations intended to be performed by a software transactional memory system as transactional operations as part of a software transaction. The method further includes selecting at least a portion of the plurality of atomic operations. The method further includes attempting to perform the portion of the plurality of atomic operations as hardware transactions using cache resident transaction hardware.

Claims

1. In a computing environment, a method of using cache resident transaction hardware to accelerate a software transactional memory system, the method comprising:

identifying a plurality of atomic operations intended to be performed by a software transactional memory system as transactional operations as part of a software transaction;

selecting at least a portion of the plurality of atomic operations; and

attempting to perform the portion of the plurality of atomic operations as hardware transactions using cache resident transaction hardware.

2. The method of claim 1, wherein selecting at least a portion of the plurality of atomic operations comprises selecting a number of operations such that N>

T/(I−

M) where N;

number of operations in a batch;

I;

average cost of a non-contended software based atomic operation;

M;

average cost of a successfully monitored and buffered operation in a cache resident transaction;

T;

average cost of initiating and committing a cache resident transaction.

3. The method of claim 2, wherein N is reduced exponentially after a failed attempt to perform a hardware transaction.

4. The method of claim 2, wherein N is increased linearly after a successful attempt to perform a hardware transaction.

5. The method of claim 1, further comprising reverting to a software transactional system to perform the portion of the plurality of atomic operations after attempting to perform the portion of the plurality of atomic operations as hardware transactions using cache resident transaction hardware due to a failure of the hardware transaction.

6. The method of claim 1, further comprising reverting to a software transactional system to perform the portion of the plurality of atomic operations after attempting a predetermined number of times to perform the portion of the plurality of atomic operations as hardware transactions using cache resident transaction hardware due to a failure of the hardware transaction a predetermined number of times.

7. The method of claim 1, wherein attempting to perform the portion of the plurality of atomic operations as hardware transactions using cache resident transaction hardware comprises attempting implicit transactions where atomic operations are replaced with implicitly monitored and buffered reads and writes.

8. The method of claim 1, wherein attempting to perform the portion of the plurality of atomic operations as hardware transactions using cache resident transaction hardware comprises attempting explicit transactions where atomic operations are replaced with explicitly monitored and buffered reads and writes.

9. The method of claim 1, wherein identifying a plurality of atomic operations intended to be performed by a software transactional memory system as transactional operations comprises identifying a log of operations for a software transactional memory transaction.

10. The method of claim 1, wherein attempting to perform the portion of the plurality of atomic operations as hardware transactions using cache resident transaction hardware comprises a compiler introducing nested cache resident transactions into generated code.

11. The method of claim 10, wherein a compiler introducing nested cache resident transactions into generated code comprises the compiler statically placing cache resident transaction boundaries into the generated code.

12. The method of claim 1, wherein attempting to perform the portion of the plurality of atomic operations as hardware transactions using cache resident transaction hardware does not include a compiler introducing nested cache resident transactions into generated code.

13. The method of claim 12, further comprising aborting a cache resident transaction, and as a result, aborting the software transaction.

14. The method of claim 1, wherein attempting to perform the portion of the plurality of atomic operations as hardware transactions using cache resident transaction hardware comprises performing the operations within the scope of an already existing cache resident transaction.

15. The method of claim 1, wherein attempting to perform the portion of the plurality of atomic operations as hardware transactions using cache resident transaction hardware comprises starting a new cache resident transaction with the purpose of performing the portion of the plurality of atomic operations as hardware transactions using cache resident transaction hardware.

16. A computer readable medium comprising computer executable instructions that when executed by one or more processors cause the one or more processors to perform the following:

identifying a plurality of atomic operations intended to be performed by a software transactional memory system as transactional operations as part of a software transaction;

selecting at least a portion of the plurality of atomic operations; and

attempting to perform the portion of the plurality of atomic operations as hardware transactions using cache resident transaction hardware.

17. The method of claim 16, wherein selecting at least a portion of the plurality of atomic operations comprises selecting a number of operations such that N>

T/(I−

M) where N;

number of operations in a batch;

1;

average cost of a non-contended software based atomic operation;

M;

average cost of a successfully monitored and buffered operation in a cache resident transaction;

T;

average cost of initiating and committing a cache resident transaction.

18. The method of claim 17, wherein N is reduced exponentially after a failed attempt to perform a hardware transaction

19. The method of claim 17, wherein N is increased linearly after a successful attempt to perform a hardware transaction

20. A computer system comprising:

one or more processors;

one or more computer memory coupled to the one or more processors, the computer memory having stored thereon computer executable instructions that when executed by the one or more processors cause the one or more processors to perform the following;

identifying a plurality of atomic operations intended to be performed by a software transactional memory system as transactional operations as part of a software transaction;

selecting at least a portion of the plurality of atomic operations, wherein selecting at least a portion of the plurality of atomic operations comprises selecting a number of operations such that N>

T/(I−

M) where N;

number of operations in a batch;

I;

average cost of a non-contended software based atomic operation;

M;

average cost of a successfully monitored and buffered operation in a cache resident transaction;

T;

average cost of initiating and committing a cache resident transaction; and

attempting to perforin the portion of the plurality of atomic operations as hardware transactions using cache resident transaction hardware, including a compiler introducing nested cache resident transactions into generated code, including statically placing cache resident transaction boundaries into the generated code.