Memory management for cache consistency

• US 8,898,395 B1
• Filed: 05/15/2008
• Issued: 11/25/2014
• Est. Priority Date: 04/07/2005
• Status: Active Grant

• Current Assignee: Intellectual Ventures II LLC (Intellectual Ventures LLC)
• Original Assignee: Intellectual Ventures Funding LLC (Intellectual Ventures LLC)
• Inventors: Rozas, Guillermo J.
• Primary Examiner(s): Bradley, Matthew
• Assistant Examiner(s): Otto, Alan
• Application Number:
  US12/121,531
• Time in Patent Office: 2,385 Days
• Field of Search: None
• US Class Current: 711/144
• CPC Class Codes: G06F 12/0806 Multiuser, multiprocessor or multiprocessing cache systems
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 9/3824 Operand accessing
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency
• CPC Class Codes: G06F 9/3861 Recovery, e.g. branch miss-prediction, exception handling error detection or correction G06F11/00
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units
• CPC Class Codes: G06F 9/466 Transaction processing

Abstract

Methods and systems for maintaining cache consistency are described. A group of instructions is executed. The group of instructions can include multiple memory operations, and also includes an instruction that when executed causes a cache line to be accessed. In response to execution of that instruction, an indicator associated with the group of instructions is updated to indicate that the cache line has been accessed. The cache line is indicated as having been accessed until execution of the group of instructions is ended.

Claims

1. A method of managing memory in a computer system, said method comprising:

setting a first bit of an indicator associated with a cache line in a cache memory if said cache line has been accessed in response to a processor executing an instruction in a first group of instructions;

setting a second bit of said indicator while said first bit remains set if said cache line has also been accessed in response to said processor executing an instruction in a second group of instructions;

executing a third group of instructions that causes said cache line to be accessed, wherein said third group of instructions is executed by an agent other than said processor, wherein said processing comprises rolling back said first group of instructions provided said first bit is set and rolling back said second group of instructions provided said second bit is set before allowing an instruction in said third group to access said cache line, and otherwise granting said access; and

processing said first group and said second group of instructions according to a value of said indicator.

2. The method of claim 1 wherein said processing further comprises:

determining a state of said cache line, wherein said state is specified according to a cache coherency protocol comprising at least a modified state, a shared state, and an invalid state; and

rolling back said first group of instructions provided said first bit is set and rolling back said second group of instructions provided said second bit is set, and then granting said access provided said cache line is in other than said shared state, and otherwise granting said access only when said cache line is in said shared state.

3. The method of claim 1 further comprising maintaining a first count of how many times said first group of instructions has been rolled back and a second count of how many times said second group of instructions has been rolled back.

4. The method of claim 3 further comprising eliminating one or more instructions from said first group of instructions if said first count exceeds a threshold and eliminating one or more instructions from said second group of instructions if said second count exceeds said threshold.

5. The method of claim 1 further comprising clearing said first bit when said execution of said first group of instructions is ended, wherein said second bit remains set until execution of said second group of instructions is ended.

6. The method of claim 1 further comprising:

executing a plurality of groups of instructions in parallel;

changing an indicator associated with each cache line in said cache that has been accessed because of an instruction in any of said plurality of groups of instructions; and

provided all cache lines in said cache memory are indicated as having been accessed, rolling back a group of instructions that includes an instruction that when executed attempts to replace information in a cache line of said cache memory, and otherwise continuing said executing of said plurality of groups of instructions.

7. A computer system comprising:

a processor;

a cache memory for use by said processor; and

a memory unit coupled to said processor and having stored therein instructions, said instructions comprising;

instructions to execute a first group of instructions using said processor, wherein said first group of instructions includes an instruction that causes a cache line of said cache memory to be read;

instructions to set a first bit of an indicator associated with said cache line to indicate that said cache line has been read;

instructions to execute a second group of instructions using said processor, wherein said second group of instructions includes an instruction that causes said cache line to be read;

instructions to set a second bit of said indicator while said first bit remains set to indicate said cache line has been accessed by both said first group of instructions and said second group of instructions;

instructions to execute a third group of instructions that causes said cache line to be accessed, wherein said third group of instructions is for execution by an agent other than said processor, wherein said instructions further comprise instructions to roll back said first group of instructions provided said first bit is set and to roll back said second group of instructions provided said second bit is set before allowing an instruction in said third group to access said cache line, wherein otherwise said access is granted; and

instructions to process said first group and said second group of instructions according to a value of said indicator.

8. The computer system of claim 7 wherein said instructions further comprise:

instructions to determine a state of said cache line, wherein said state is specified according to a cache coherency protocol comprising at least a modified state, a shared state, and an invalid state; and

instructions to roll back said first group of instructions provided said first bit is set and to roll back said second group of instructions provided said second bit is set, wherein said access is granted provided said cache line is in other than said shared state, and wherein otherwise said access is granted only when said cache line is in said shared state.

9. The computer system of claim 8 wherein said instructions further comprise instructions to maintain a first count of how many times said first group of instructions has been rolled back and a second count of how many times said second group of instructions has been rolled back.

10. The computer system of claim 9 wherein said instructions further comprise instructions to eliminate one or more instructions from said first group of instructions if said first count exceeds a threshold and to eliminate one or more instructions from said second group of instructions if said second count exceeds said threshold.

11. The computer system of claim 7 wherein said instructions further comprise instructions to clear said first bit when said execution of said first group of instructions is ended, wherein said second bit remains set until execution of said second group of instructions is ended.

12. The computer system of claim 7 wherein said instructions further comprise:

instructions to execute a plurality of groups of instructions in parallel using said processor;

instructions to change an indicator associated with each cache line in said cache memory that has been accessed because of an instruction in any of said plurality of groups of instructions; and

instructions to roll back a group of instructions that includes an instruction that when executed attempts to replace information in a cache line of said cache memory provided all cache lines in said cache memory are indicated as having been accessed, wherein otherwise said plurality of groups of instructions continue to be executed.

13. A method of managing shared memory in a computer system, said method comprising:

executing a first group of instructions with a processor;

associating a first state with a cache line in a cache comprising a plurality of cache lines, wherein said first state is specified according to a cache coherency protocol comprising at least a modified state, a shared state, and an invalid state;

associating a second state with said cache line during said executing of said first group of instructions, wherein said second state indicates that said cache line has been accessed because of said first group of instructions;

executing a second group of instructions with said processor;

associating a third state with said cache line during said executing of said second group of instructions, wherein said third state indicates that said cache line has been accessed because of said second group of instructions;

executing a third group of instructions that causes said cache line to be accessed; and

rolling back said first group of instructions and said second group of instructions before granting said access.

14. The method of claim 13 wherein said first group of instructions includes multiple memory operations and said second group of instructions includes multiple memory operations.

15. The method of claim 13 wherein said rolling back is only performed provided said cache line is in other than said shared state.

16. The method of claim 13 further comprising maintaining a first count of how many times said first group of instructions is rolled back and a second count of how many times said second group of instructions is rolled back.

17. The method of claim 16 further comprising eliminating one or more instructions from said first group of instructions if said first count exceeds a threshold and eliminating one or more instructions from said second group of instructions if said second count exceeds said threshold.

18. The method of claim 13 wherein said second state is indicated by setting a first bit associated with said cache line, wherein said first bit is cleared when said execution of said first group of instructions is ended, and wherein said third state is indicated by setting a second bit associated with said cache line, wherein said second bit is cleared when said execution of said second group of instructions is ended.

19. A computer system comprising:

a processor;

a cache memory coupled to said processor and having a plurality of cache lines; and

a memory unit coupled to said processor, wherein said memory unit has a plurality of indicator bits per cache line, wherein a first indicator bit associated with a cache line of said cache memory is set to indicate that said cache line has been accessed responsive to said processor executing a first group of instructions and wherein said first indicator bit is cleared when execution of said first group of instructions is ended, wherein a second indicator bit associated with said cache line is set to indicate that said cache line has been accessed responsive to said processor executing a second group of instructions in parallel with said first group and wherein said second indicator bit is cleared when execution of said second group of instructions is ended;

wherein further, in response to an agent other than said processor executing a third group of instructions that causes said cache line to be accessed, said first group of instructions is rolled back provided said first bit is set and said second group of instructions is rolled back provided said second bit is set before allowing an instruction in said third group to access said cache line, wherein otherwise said access is granted.

20. The computer system of claim 19 wherein a subset of address bits of said cache line is used to identify an entry in said memory unit, wherein an indicator bit of said entry is set in response to said cache line being accessed.