Computer apparatus including a main memory prefetch cache and method of operation thereof

• US 5,566,324 A
• Filed: 12/24/1992
• Issued: 10/15/1996
• Est. Priority Date: 12/24/1992
• Status: Expired due to Term

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: NCR Corporation
• Inventors: Kass, William J.
• Primary Examiner(s): Kim, Matthew M.
• Application Number:
  US07/996,533
• Time in Patent Office: 1,391 Days
• Field of Search: 395/425, 395/400, 395/375, 395/464, 395/414, 395/449, 395/375, 395/421.03, 395/487, 395/403, 371/40.2, 364/DIG. 1
• US Class Current: 711/160
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 2212/6022 Using a prefetch buffer or dedicated prefetch cache
• CPC Class Codes: G06F 9/3802 Instruction prefetching
• CPC Class Codes: G06F 9/3814 Implementation provisions of instruction buffers, e.g. prefetch buffer; banks

Abstract

A computer system is provided including a main memory prefetch cache which enhances the retrieval of instructions (code and data) stored in the main memory of a computer. The computer system includes a processor and a processor cache coupled thereto. A memory controller is coupled to the processor and includes a main memory prefetch cache. The memory controller also includes control circuitry which determines if a current line requested by the processor is stored in the prefetch cache, and if so, the memory controller retrieves the current line from the prefetch cache and provides the current line to the processor. The next line is then retrieved from the main memory and is overwritten over the current line in the prefetch cache. Otherwise, if the memory controller determines that the prefetch cache does not contain the current line requested by the processor, then the current line is retrieved from the main memory and is provided to the processor. The next line is then retrieved from the main memory and is stored in the prefetch cache at a register location which was occupied by the least recently used line in the cache. The invention includes circuitry and methodology for determining the least recently used line stored within the prefetch cache.

Claims

1. A computer system comprising:

a processor;

a processor cache coupled to said processor;

a memory controller coupled to said processor;

a main memory coupled to said memory controller;

said memory controller including

a main memory prefetch cache, and

control means coupled to said prefetch cache for determining if a cache hit has occurred wherein a current line requested by said processor is stored in said prefetch cache, and if so, then retrieving said current line from said prefetch cache for use by said processor and overwriting said current line in said prefetch cache with a next line from said main memory, or otherwise when said prefetch cache does not contain said current line requested by said processor thus signifying a cache miss, then retrieving said current line from said main memory for use by said processor and substantially concurrently retrieving said next line from said main memory and storing said next line in said prefetch cache such that said next line is transferred to said prefetch cache prior to a request for said next line from said processor.

2. The computer system of claim 1 wherein said prefetch cache comprises x prefetch cache registers for storing instructions prefetched from said main memory, wherein x is a number.

3. The computer system of claim 2 further comprising x least recently used (LRU) counters, each LRU counter corresponding to a respective one of said prefetch cache registers, each counter containing a count value indicating how recently and instruction in corresponding prefetch cache register has been used.

4. The computer system of claim 3 further comprising clearing means for clearing a count value designated HIT COUNT in an LRU counter corresponding to a prefetch cache register in which a cache hit has occurred.

5. The computer system of claim 4 further comprising first incrementing means, coupled to said LRU counters, for incrementing all LRU counters whose count value is less than said HIT COUNT value when a cache hit occurs, the count value of the remaining LRU counters remaining unchanged when a cache hit occurs.

6. The computer system of claim 5 further comprising purging means, coupled to said prefetch cache, for purging said prefetch cache of a least recently used line when a cache miss occurs by writing said next line to the particular cache register corresponding to the LRU counter exhibiting a maximum count value.

7. The computer system of claim 6 further comprising second incrementing means, coupled to said LRU counters, for incrementing those LRU counters other than the LRU counter corresponding to said particular cache register into which said next line is written when a cache miss occurs.

8. The computer system of claim 1 wherein said processor cache comprises an internal processor cache integrated in said processor.

9. The computer system of claim 1 wherein said processor cache comprises an external processor cache externally coupled to said processor.

10. The computer system of claim 2 wherein said processor cache further comprises an external processor cache externally coupled to said processor.

11. A computer system comprising:

a processor;

a processor cache coupled to said processor;

a memory controller coupled to said processor;

a main memory coupled to said memory controller;

said memory controller including

a main memory prefetch cache, and

control means coupled to said prefetch cache for fetching from said prefetch cache a current line when requested by said processor if a cache hit occurs, and in that case substantially concurrently overwriting said current line in said prefetch cache with a next line sequentially following said current line in said main memory prior to receiving a request from said processor for said next line.

12. The computer system of claim 11 wherein said prefetch cache comprises x prefetch cache registers for storing instructions prefetched from said main memory, wherein x is a number.

13. The computer system of claim 12 further comprising x least recently used (LRU) counters, each LRU counter corresponding to a respective one of said prefetch cache registers, each counter containing a count value indicating how recently and instruction in corresponding prefetch cache register has been used.

14. The computer system of claim 13 further comprising clearing means for clearing a count value designated HIT COUNT in an LRU counter corresponding to a prefetch cache register in which a cache hit has occurred.

15. The computer system of claim 14 further comprising first incrementing means, coupled to said LRU counters, for incrementing all LRU counters whose count value is less than said HIT COUNT value when a cache hit occurs, the count value of the remaining LRU counters remaining unchanged when a cache hit occurs.

16. The computer system of claim 15 further comprising purging means, coupled to said prefetch cache, for purging said prefetch cache of a least recently used line when a cache miss occurs by writing said next line to the particular cache register corresponding to the LRU counter exhibiting a maximum count value.

17. The computer system of claim 16 further comprising second incrementing means, coupled to said LRU counters, for incrementing those LRU counters other than the LRU counter corresponding to said particular cache register into which said next line is written when a cache miss occurs.

18. The computer system of claim 11 wherein said processor cache comprises an internal processor cache integrated in said processor.

19. The computer system of claim 11 wherein said processor cache comprises an external processor cache externally coupled to said processor.

20. The computer system of claim 18 wherein said processor cache further comprises an external processor cache externally coupled to said processor.

21. A computer system comprising:

a processor;

a processor cache memory which is accessible to said processor;

a main memory for storing a sequence of instructions for execution by said processor;

a memory controller, coupled to said processor and said main memory, for controlling access by said processor to the instructions stored in said main memory, said memory controller including

a main memory prefetch cache for storing instructions prefetched from said main memory prior to a request therefor from said processor, and

cache control means, coupled to said prefetch cache, for determining if a current instruction N requested by said processor is contained in said prefetch cache and, if so, retrieving said current instruction N from said prefetch cache and providing said current instruction N to said processor and retrieving a next instruction N+1 from said main memory and overwriting said current instruction N with said next instruction N+1, or otherwise when said prefetch cache does not contain a current instruction N requested by said processor, then retrieving said current instruction N from said main memory and providing said current instruction N to said processor and substantially concurrently retrieving a next instruction N+1 from said main memory and storing said next instruction N+1 in said prefetch cache memory prior to receiving a request for said next instruction from said processor.

22. The computer system of claim 21 wherein said prefetch cache comprises x prefetch cache registers for storing instructions prefetched from said main memory, wherein x is a number.

23. The computer system of claim 22 further comprising x least recently used (LRU) counters, each LRU counter corresponding to a respective one of said prefetch cache registers, each counter containing a count value indicating how recently an instruction in the corresponding prefetch cache register has been used.

24. The computer system of claim 23 further comprising clearing means for clearing a count value designated HIT COUNT in an LRU counter corresponding to a prefetch cache register in which a cache hit has occurred.

25. The computer system of claim 24 further comprising first incrementing means, coupled to said LRU counters, for incrementing all LRU counters whose count value is less than said HIT COUNT value when a cache hit occurs, the count value of the remaining LRU counters remaining unchanged when a cache hit occurs.

26. The computer system of claim 25 further comprising purging means, coupled to said prefetch cache, for purging said prefetch cache of a least recently used instruction when a cache miss occurs by writing said next instruction N+1 to the particular cache register corresponding to the LRU counter exhibiting a maximum count value.

27. The computer system of claim 26 further comprising second incrementing means, coupled to said LRU counters, for incrementing those LRU counters other than the LRU counter corresponding to said particular cache register into which said next instruction N+1 is written when a cache miss occurs.

28. The computer system of claim 21 wherein said processor cache comprises an internal processor cache integrated in said processor.

29. The computer system of claim 21 wherein said processor cache comprises an external processor cache externally coupled to said processor.

30. The computer system of claim 28 wherein said processor cache further comprises an external processor cache externally coupled to said processor.

31. In a computer system including a processor employing a processor cache, a method of accessing a main memory comprising:

providing said main memory with a main memory prefetch cache including a plurality of prefetch registers for storing a plurality of lines from main memory;

initiating a memory cycle to said main memory to retrieve a current line;

determining if a cache hit occurs in said prefetch cache for said current line during said memory cycle;

prefetching, if a cache hit occurs, said current line from said prefetch cache and then overwriting said current line in said prefetch cache with a next line from said main memory during said memory cycle;

determining the least recently used line in said prefetch cache,

retrieving, if a cache miss occurs, said current line from said main memory, and

storing during said memory cycle, if a cache miss occurs, a next line from main memory subsequent to said current line in the particular prefetch register occupied by said least recently used line.

32. In a computer system including a processor employing a processor cache, a method of accessing a main memory comprising:

providing a main memory prefetch cache situated in a memory controller and coupled to said main memory;

initiating a main memory cycle to retrieve a current line from said main memory;

determining, by said memory controller, if said current line is stored in said prefetch cache, and

if said current line is determined to be stored in said prefetch cache, then retrieving said current line from said prefetch cache and providing said current line to said processor, and retrieving a next line form said main memory and overwriting said current line in said prefetch cache with said next line during said memory cycle, and

if said current line is determined not to be stored in said prefetch cache, then retrieving said current line from said main memory and providing said current line to said processor, and retrieving said next line from said main memory and storing said next line in said prefetch cache during said memory cycle.

33. The method of claim 32 wherein said determining step further comprises modifying said main memory cycle to retrieve the next line from said main memory rather than said current line when in said determining step it is determined that the current line is stored in said prefetch cache.

34. The method of claim 32 wherein said prefetch cache includes X registers wherein X is a number, said method further comprising the steps of:

providing a respective least recently used (LRU) counter corresponding to each of the registers in said prefetch cache;

initializing each of said LRU counters at a unique predetermined count value between 0 and X inclusive;

if in said determining step said current line is determined to be stored in said prefetch cache as per a cache hit, then

clearing a count value stored in the particular LRU counter corresponding to a register in said prefetch cache for which said cache hit occurred;

incrementing said LRU counters whose count values are less than the count value of said particular LRU counter prior to said clearing step;

if in said determining step said current line is determined not to be stored in said prefetch cache as per a cache miss, then

storing said next line in a register in said prefetch cache corresponding to an LRU counter having a maximum count X, and

incrementing the remaining counters.

35. A method for enhancing the processing of instructions stored in a main memory of a computer system, said computer system including a processor with a processor cache memory coupled thereto, a sequence of instructions being stored in said main memory which is controlled by a memory controller, said method comprising:

providing said main memory with a prefetch cache memory situated in said memory controller;

issuing a request, by said processor to said memory controller, for a current instruction N in said sequence of instructions stored in said main memory;

determining, by said memory controller, if said current instruction N is stored in said prefetch cache memory, and

if said prefetch cache memory is determined to be storing said current instruction N, then

retrieving said current instruction N from said prefetch cache memory and providing said current instruction N to said processor,

and, during a same memory cycle, retrieving a next instruction N+1 from said main memory and overwriting said current instruction N in said prefetch cache memory with said next instruction N+1, or

if said prefetch cache memory is determined not to contain said current instruction N, then

retrieving said current instruction N from said main memory and providing said current instruction N to said processor

and

substantially concurrently retrieving a next instruction N+1 from said main memory and storing said next instruction N+1 in said prefetch cache memory.

36. The method of claim 35 wherein said determining step further comprises modifying said main memory cycle to retrieve the next instruction N+1 from said main memory rather than said current instruction N when in said determining step it is determined that the current instruction N is stored in said prefetch cache.

37. The method of claim 35 wherein said prefetch cache includes X registers wherein X is a number, said method further comprising the steps of:

providing a respective least recently used (LRU) counter corresponding to each of the registers in said prefetch cache;

initializing each of said LRU counters at a unique predetermined count value between 0 and X-1 inclusive;

if in said determining step said current instruction N is determined to be stored in said prefetch cache as per a cache hit, then

clearing a count value stored in the particular LRU counter corresponding to a register in said prefetch cache for which said cache hit occurred;

incrementing said LRU counters whose count values are less than the count value of said particular LRU counter prior to said clearing step;

if in said determining step said current instruction N is determined not to be stored in said prefetch cache as per a cache miss, then

storing said next instruction N+1 in a register in said prefetch cache corresponding to an LRU counter having a maximum count X, and

incrementing the remaining counters.

38. A method for enhancing the processing of instructions stored in a main memory of a computer system, said computer system including a processor with a processor cache memory coupled thereto, a sequence of lines of code and data stored in said main memory which is controlled by a memory controller, said method comprising:

providing said main memory with a prefetch cache memory integrated within said memory controller and coupled to said main memory;

issuing a request, by said processor to said memory controller, for a particular line in said sequence of lines stored in said main memory, said particular line being designated a current line;

initiating a main memory cycle by said memory controller to retrieve said current line;

determining, by said memory controller, if said current line is stored in said prefetch cache memory, and

if said prefetch cache memory is determined to be storing said current line, then

retrieving said current line from said prefetch cache memory and providing said current line to said processor and said processor cache,

and

modifying the main memory request begun in said initiating step to retrieve a current line+1 from said main memory and overwriting said current line in said prefetch cache memory with said current line+1 during said main memory cycle, and

if said prefetch cache memory is determined not to contain said current line, then

continuing said main memory cycle to retrieve said current line from said main memory and providing said current line to said processor,

and

further continuing said main memory cycle to retrieve said current line+1 from said main memory and storing said current line+1 in said prefetch cache memory.

39. The method of claim 38 wherein said prefetch cache includes X registers wherein X is a number, said method further comprising the steps of:

providing a respective least recently used (LRU) counter corresponding to each of the registers in said prefetch cache;

initializing each of said LRU counters at a unique predetermined count value between 0 and X-1 inclusive;

if in said determining step said current line is determined to be stored in said prefetch cache thus signifying a cache hit, then

clearing the count value stored in the particular LRU counter corresponding to the register in said prefetch cache for which said cache hit occurred;

incrementing said LRU counters whose count values are less than the count value of said particular LRU counter prior to said clearing step;

if in said determining step said current line is determined not to be stored in said prefetch cache as per a cache miss, then

storing said current line+1 in the register in said prefetch cache corresponding to the LRU counter having a maximum count X, and

incrementing the remaining counters.