Computer Cache System Providing Multi-Line Invalidation Messages

• US 20140101390A1
• Filed: 10/08/2012
• Published: 04/10/2014
• Est. Priority Date: 10/08/2012
• Status: Active Grant

• Current Assignee: Wisconsin Alumni Research Foundation (University of Wisconsin System)
• Original Assignee: Wisconsin Alumni Research Foundation (University of Wisconsin System)
• Inventors: Sohi, Gurindar S., Yoon, Hongil
• Granted Patent: US 9,223,717 B2
• Time in Patent Office: Days
• US Class Current: 711/144
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 12/0891 using clearing, invalidating or resetting means
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A computer cache system delays cache coherence invalidation messages related to cache lines of a common memory region to collect these messages into a combined message that can be transmitted more efficiently. This delay may be coordinated with a detection of whether the processor is executing a data-race free portion of the program so that the delay system may be used for a variety of types of programs which may have data-race and data-race free sections.

Claims

1. A computer architecture comprising:

a cache memory holding lines of data that may be individually invalidated;

a processor for executing program instructions operating on data from the cache memory;

a cache controller communicating with the cache memory and operating to;

(a) detect access of cache lines by operations of the processor where the access requires a transmission of invalidation messages for coherent cache operation;

(b) delay communication of the invalidation messages; and

(c) collect multiple delayed invalidation messages in a single combined invalidation message and transmit the single combined invalidation message instead of multiple invalidation messages.

2. The computer architecture of claim 1 wherein the cache controller further operates to detect whether current execution of instructions by the processor are from a data-race free region of the program, the data-race free region being a sequence of instructions operating on data that is unlikely to be invalidated by other processors during execution of the data-race free region by the processor and to perform steps (b) and (c) based on detecting that the current execution of instructions if from a data-race free region of the program.

3. The computer architecture of claim 2 wherein the multiple delayed messages are selected to be collected in a single combined invalidation message according to whether the multiple delayed messages relate to cache lines from a common region of a main memory.

4. The computer architecture of claim 3 wherein the combined invalidation message provides an address in the main memory of the common region and provides subaddresses of the invalidated lines whereby data transmitted in the combined invalidation message is less than the total data of the individual invalidation messages that are combined;

wherein the subaddresses are selected from the group consisting of bit vectors having a bit for each line of the common region and address offsets from an address of the common region.

5. The computer architecture of claim 2 wherein the cache controller further operates to not delay communication of the invalidation messages when the current execution of instructions are not from a data-race free region of the program and transmits the invalidation messages without combination with other invalidation messages.

6. The computer architecture of claim 2 wherein the cache controller further operates to receive a combined invalidation message relating to multiple cache lines and to transmit a combination acknowledgement message combining multiple acknowledgement messages for each cache line of the combined invalidation message.

7. The computer architecture of claim 2 wherein transmitting the combined invalidation message is triggered by current execution of instructions by the processor leaving the data-race free region of the program.

8. The computer architecture of claim 1 wherein the cache controller operates to delay communication of the invalidation message associated with a cache line only if a delay permission is granted for that cache line wherein the delay permission indicates that only the cache having the delay permission can delay the communication of an invalidation message.

9. The computer architecture of claim 8 wherein the cache controller operates to transmit a request for permission for cache lines from a directory.

10. The computer architecture of claim 9 wherein the request for permission is triggered by a first required invalidation messages for a region of main memory not common to current delayed invalidation messages.

11. The computer architecture of claim 10 wherein the request for permission includes that first required invalidation message.

12. The computer architecture of claim 1 wherein processors are selected from the group consisting of single cores, multiple cores and graphic processor units.

13. The computer architecture of claim 1 wherein detection of data-race free regions detects instructions in the program demarcating boundaries of data-race free regions in the program.

14. A method of reducing data communication burden for cache coherence protocols in a multiprocessor system having multiple processors associated with cache memory holding lines of data that may be individually invalidated, the method comprising the steps at each processor of:

(a) collecting cache line invalidation messages according to common regions of main memory;

(b) combining the collected cache line invalidation messages in a compressed form; and

(c) transmitting the combined compressed invalidation messages.

15. The method of claim 14 wherein step (a) is conditional on a determination at each processor that a given processor is executing a portion of a program free of potential data-races for data of the cache lines being combined.

16. A method of operating a computer of a type having a cache memory holding lines of data that may be individually invalidated and a processor executing program instructions operating on data from the cache memory, the method comprising the steps of operating a cache controller communicating with the cache memory to:

(a) detect access of cache lines by operations of the processor where the access requires a transmission of invalidation messages for coherent cache operation;

(b) detect whether current execution of instructions by the processor are from a data-race free region of the program, the data-race free region being a sequence of instructions operating on data that is unlikely to be invalidated by other processors during execution of the data-race free region by the processor; and

(c) delay communication of the invalidation messages when the current execution of instructions is from a data-race free region of the program.

17. The method of claim 16 further including the step of collecting multiple delayed invalidation messages in a single combined invalidation message and transmitting the single combined invalidation message instead of multiple invalidation messages.

18. The method of claim 17 wherein the multiple delayed messages are selected to be collected in a single combined invalidation message according to whether the multiple delayed messages relate to cache lines from a common region of a main memory.

19. The method of claim 18 wherein the combined invalidation message provides an address in the main memory of the common region and provides subaddresses of the invalidated lines whereby data transmitted in the combined invalidation message is less than the total data of the individual invalidation messages that are combined;

wherein the subaddresses are selected from the group consisting of bit vectors having a bit for each line of the common region and address offsets from an address of the common region.