Method for reducing cache conflict misses

• US 7,299,318 B2
• Filed: 04/04/2002
• Issued: 11/20/2007
• Est. Priority Date: 12/20/2001
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Stoutamire, David P.
• Primary Examiner(s): Shah; Sanjiv
• Assistant Examiner(s): Rojas; Midys
• Application Number:
  US10/117,020
• Publication Number:
  US 20030120866A1
• Time in Patent Office: 2,056 Days
• Field of Search: 711/118, 711/170, 711/171, 711/172
• US Class Current: 711/118
• CPC Class Codes: G06F 8/4442 Reducing the number of cache misses; Data prefetching cache prefetching G06F12/0862

Abstract

An invention is provided for reducing cache conflict misses via specific placement of non-split functions and data objects in main memory based on cache size. A cache size of a computer cache memory is determined, and a first data block is placed within a main computer memory. The first data block includes a first sub-block that will be frequently referenced. In addition, the first sub-block ends at a first ending address. A second data block is then placed within the main computer memory. The second data block includes a second sub-block that will be frequently referenced, and is placed such that the second sub-block will be contiguous with the first sub-block in the computer cache memory during execution.

Claims

1. A method for reducing computer cache conflict misses, comprising the operations of:

determining a cache size of a computer cache memory;

placing a first data block within a main computer memory, the first data block occupying a contiguous portion of the main computer memory, wherein the first data block includes a first sub-block that will be frequently referenced, and wherein the first sub-block ends at a first ending address; and

placing a second data block within the main computer memory, the second data block including a second sub-block that will be frequently referenced, the second data block occupying a contiguous portion of the main computer memory, wherein the second data block is placed such that the second sub-block will be contiguous with the first sub-block in the computer cache memory during execution, and the second sub-block is located at a main memory address that is offset by at least one or a multiple of the cache size from the first ending address of the first sub-block to prevent cache conflict misses.

2. A method as recited in claim 1, further comprising the operation of placing a third data block within the main computer memory, the third data block including a third sub-block that will be frequently referenced, wherein the third data block is placed such that the third sub-block will be contiguous with the first sub-block and the second sub-block in the computer cache memory during execution.

3. A method as recited in claim 2, wherein the third data block is placed such that the third sub-block is located at a main memory address that is offset by a multiple of the cache size from an ending address of the second sub-block to prevent cache conflict misses.

4. A method as recited in claim 3, wherein the first data block, the second data block, and the third data block each is a data object.

5. A method as recited in claim 3, wherein the first data block, the second data block, and the third data block each is a function.

6. A computer program embodied on a computer readable medium for reducing computer cache conflict misses, comprising:

a code, segment that places a first data block within a main computer memory, the first data block occupying a first contiguous portion of the main computer memory, wherein the first data block includes a first sub-block that will be frequently referenced, and wherein the first sub-block ends at a first ending address; and

a code segment that places a second data block within the main computer memory, the second data block occupying a second contiguous portion of the main computer memory, the second data block including a second sub-block that will be frequently referenced, wherein the second data block is placed such that the second sub-block is located at a main memory address that is offset by at least one or a multiple of a cache size of the computer cache from the first ending address of the first sub-block to prevent cache conflict misses so that the second sub-block will be contiguous with the first sub-block in the computer cache during execution.

7. A computer program as recited in claim 6, further comprising a code segment that determines which sub-blocks of a data block will be frequently accessed.

8. A computer program as recited in claim 6, further comprising a code segment that determines the cache size.

9. A computer program as recited in claim 6, wherein the first data block is not split in main memory, and wherein the second data block is not split in main memory.

10. A computer program as recited in claim 6, further comprising a code segment that places a third data block within the main computer memory, the third data block including a third sub-block that will be frequently referenced, wherein the third data block is placed such that the third sub-block will be contiguous with the first sub-block and the second sub-block in the computer cache memory during execution.

11. A computer program as recited in claim 10, wherein the third data block is placed such that the third sub-block is located at a main memory address that is offset by a multiple of the cache size from an ending address of the second sub-block to prevent cache conflict misses.

12. A computer program as recited in claim 10, wherein the first data block, the second data block, and the third data block each is a data object.

13. A computer program as recited in claim 11, wherein the first data block, the second data block, and the third data block each is a function.

14. A method for reducing computer cache conflict misses, comprising the operations of:

determining a cache size of a computer cache memory;

placing a first data block within a main computer memory, the first data block occupying a contiguous portion of the main computer memory, wherein the first data block includes a first sub-block that will be frequently referenced, and wherein the first sub-block ends at a first ending address; and

placing a second data block within the main computer memory, the second data block occupying a contiguous portion of the main computer memory, the second data block including a second sub-block that will be frequently referenced, wherein the second data block is placed such that the second sub-block is located at a main memory address that is offset by at least one or a multiple of the cache size from the first ending address of the first sub-block to prevent cache conflict misses so that the second sub-block will be contiguous with the first sub-block in the computer cache during execution.

15. A method as recited in claim 14, wherein each data block is a data object, and wherein each sub-block is a field.

16. A method as recited in claim 15, further comprising the operation of placing a third data object within the main computer memory, the third data object including a third field that will be frequently referenced, wherein the third data object is placed such that the third field is located at a main memory address that is offset by a multiple of the cache size from the ending address of the second sub-block to prevent cache conflict misses.

17. A method as recited in claim 14, wherein each data block is a function, and wherein each sub-block is a basic block.

18. A method as recited in claim 17, further comprising the operation of placing a third function within the main computer memory, the third function including a third basic block that will be frequently referenced, wherein the third function is placed such that the third basic block is located at a main memory address that is offset by a multiple of the cache size from the ending address of the second basic block to prevent cache conflict misses.

19. A method for reducing computer cache conflict misses, comprising the operations of:

determining a cache size of a computer cache memory;

placing a first data block within a main computer memory, without splitting the first data block, wherein the first data block includes a first sub-block that will be frequently referenced, and wherein the first sub-block ends at a first ending address; and

placing a second data block within the main computer memory, without splitting the second data block, the second data block including a second sub-block that will be frequently referenced, wherein the second data block is placed such that the second sub-block will be contiguous with the first sub-block in the computer cache memory during execution, and the second sub-block is located at a main computer memory address that is offset by at least one or a multiple of the cache size from the first ending address of the first sub-block to prevent cache conflicting misses.