TIMESTAMP BASED TRANSACTIONAL MEMORY

• US 20080301378A1
• Filed: 06/01/2007
• Published: 12/04/2008
• Est. Priority Date: 06/01/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Carrie, Susan E.
• Granted Patent: US 7,644,238 B2
• Time in Patent Office: Days
• US Class Current: 711/147
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A hardware implemented transactional memory system includes a mechanism to allow multiple processors to access the same memory system. A set of timestamps are stored that each correspond to a region of memory. A time stamp is updated when any memory in its associated region is updated. For each memory transaction, the time at which the transaction begins is recorded. Write operations that are part of a transaction are performed by writing the data to temporary memory. When a transaction is to be recorded, the hardware automatically commits the transaction by determining whether the timestamps associated with data read for the transaction are all prior to the start time for the transaction. In this manner, the software need not check the data for all other processes or otherwise manage collision of data with respect to different processes. The software need only identify which reads and writes are part of a transaction.

Claims

1. A computing apparatus, comprising:

a main memory system;

multiple processing units in communication with said main memory system, said processing units execute software that performs transactions of memory accesses for said main memory system, said transactions include transactional write operations and transactional read operations;

a transaction processing control circuit in communication with said multiple processing units;

a first memory circuit in communication with said transaction processing circuit, said transaction processing circuit stores temporary write data in said first memory circuit in response to transactional write operations; and

a second memory circuit in communication with said transaction processing circuit, said second memory circuit stores timestamps, each time stamp is associated with data for said main memory system, said transactional processing system commits a particular transaction by allowing data from said first memory circuit corresponding to a transaction write for said particular transaction to be written to said main memory system if a set of one or more timestamps stored in said second memory system that correspond to transactional reads for said particular transaction are prior to a start time for said particular transaction.

2. A computing apparatus according to claim 1, further comprising:

a third memory circuit storing transaction start times; and

an interface circuit connected to said transaction processing control circuit and said multiple processing units.

3. A computing apparatus according to claim 1, wherein:

each timestamp in said second memory circuit corresponds to multiple data entries in said main memory system.

4. A computing apparatus according to claim 1, wherein:

said main memory system is grouped into blocks of memory;

each block of memory stores multiple data entries; and

said second memory circuit stores multiple timestamps for each block of memory that can be dynamically configured to correspond to any data entry in a corresponding block.

5. A computing apparatus according to claim 1, further comprising:

a third memory circuit in communication with said transaction processing control circuit, said third memory circuit stores identifications of transactions and stores identifications of processing units allowed to access said transactions, said transaction processing control circuit prevents access to transactions for processing units not identified for a particular transaction in said third memory circuit.

6. A computing apparatus according to claim 1, wherein:

said first memory circuit stores transactional write addresses; and

each transactional write address includes a first set of bits and a second set of bits, said first set of bits identifies an address in said main memory system, said second set of bits identifies one transaction.

7. A computing apparatus according to claim 1, wherein:

said first memory circuit stores transactional write addresses;

each transactional write address includes a first set of bits, a second set of bits and a third set of bits;

said first set of bits identifies an address in said main memory system;

said second set of bits identifies whether an operation is transactional; and

said third set of bits identifies one transaction.

8. A computing apparatus according to claim 1, further comprising:

a cache system in communication with said main memory system and said transaction processing control circuit, said timestamps are only maintained for data in said cache system.

9. A computing apparatus according to claim 1, wherein:

said first memory circuit is part of a cache system; and

at least a subset of entries in said cache system include a memory address, a transaction identification, a transaction flag, a cache tag and data.

10. A computing apparatus according to claim 1, wherein:

said first memory circuit is part of a cache system; and

at least a subset of entries in said cache system include a memory address, a time stamp, a cache tag and data.

11. A computing apparatus according to claim 1, further comprising:

a timestamp adjustment control circuit in communication with said second memory circuit, said timestamp adjustment control circuit automatically adjusts timestamps stored in said second memory circuit to be no older than a predetermined adjustment period.

12. A method performed by a computing system that performs transactions of memory accesses, said transactions includes transactional writes and transactional reads, said method comprising:

storing read addresses in response to transactional reads;

storing write data in a temporary condition in response to transactional writes;

using hardware to create timestamps and associate said timestamps with memory, said timestamps are not referenced by software; and

committing transactions, said committing transactions is performed by hardware without software in said computing system checking other processes'"'"' data to avoid collisions of memory accesses.

13. A method according to claim 12, wherein:

committing a particular transaction includes taking atomic control of said computing system and determining whether timestamps for all transactional reads for said particular transaction are prior to a start time for said particular transaction and, if so, moving said write data from said temporary condition to a standard condition.

14. A method according to claim 12, further comprising:

preventing access to data for transactional writes and transactional reads associated with a particular transaction for entities that did not request creation of said particular transaction.

15. A method according to claim 12, further comprising:

automatically adjusting timestamps to be no older than a time defined by a predetermined adjustment period and a current time.

16. A method according to claim 12, wherein:

said write data and said time stamps are stored in a multi-level cache system;

said storing write data includes storing a transaction flag in said cache system indicating that said write data is for a transactional write and storing a transaction identification in said cache system identifying a transaction associated with write data; and

said committing transactions includes allowing said write data to move from said cache system to main memory.

17. A computing apparatus, comprising:

a main memory system;

multiple processing units in communication with said main memory system, said processing units execute software that performs transactions of memory accesses for said main memory system, said transactions includes transactional reads and transactional writes;

an interface circuit in communication with said processing units and said main memory system;

a transactional control circuit in communication with said interface circuit;

a memory circuit, in communication with said transactional control circuit, that stores transactional start times;

a memory circuit, in communication with said transactional control circuit, that stores transactional identifications;

a memory circuit, in communication with said transactional control circuit, that stores transactional read addresses;

one or more memory circuits, in communication with said transactional control circuit, that store transactional write addresses and transactional write data; and

a memory circuit, in communication with said transactional control circuit, that stores timestamps associated with said main memory system.

18. A computing apparatus according to claim 17, wherein:

said main memory system is grouped into blocks of memory;

each block of memory stores multiple data entries; and

said memory circuit that stores timestamps includes multiple timestamps for each block of memory that can be dynamically configured by said transactional control circuit to correspond to any data entry in a corresponding block.

19. A computing apparatus according to claim 17, further comprising:

a memory circuit, in communication with said transactional control circuit, that stores correspondence between transactions and entities that request transactions.

20. A computing apparatus according to claim 17, wherein:

said one or more memory circuits that store transactional write addresses and transactional write data are part of a cache system.