Data prefetching based on store information in multi-processor caches

• US 5,214,766 A
• Filed: 08/19/1992
• Issued: 05/25/1993
• Est. Priority Date: 04/28/1989
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Liu, Lishing
• Primary Examiner(s): Chan, Eddie P.
• Application Number:
  US07/933,003
• Time in Patent Office: 279 Days
• Field of Search: 395/425, 364/DIG. 1
• US Class Current: 711/124
• CPC Class Codes: G06F 12/0822 Copy directories local copy tags for implementing a bus snooping protocol G06F12/0831
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 2212/6024 History based prefetching

Abstract

A mechanism using CH_Loc (change-local) type information is used for data prefetch (D-prefetch) decision making. This information is stored in history tables H, there being one such table for each central processor (CP) at, for example, the buffer control element (BCE). For each line L, H[L] indicates the information for L in H. Two different types of histories may be kept at H:

(1) Cross-interrogate (XI)-invalidates--At each H[L], there is recorded whether L was XI-invalidated without refetching.

(2) CH_Loc --At each H[L], there is also recorded local-change history, i.e., whether L was stored into since the last fetch.

It is also possible to keep a global H at the storage control element (SCE). In this case, the SCE maintains a table I recording, for each line L, information I[L] recording whether L involved XI-invalidates during the last accesses by a CP. Upon a cache miss to L from a processor CP_i, the SCE prefetches some of those lines that involved XI-invalidates (indicated by I) into cache C_i, if missing there. The management of table I is simple. When an XI-invalidate on L occurs, e.g., upon a store or an EX fetch, the corresponding entry is set. When L is accessed, e.g., upon D-fetch misses, without XI-invalidate, the entry in I is reset. Another criteria for turning an I entry OFF is when the line is fetched, e.g., on demand or upon prefetch.

Claims

1. In a multi-processor system comprising a plurality of processors, a shared main storage and a storage control element, each said processors having a local cache memory and a buffer control element, a computer implemented method of data prefetching comprising the steps of:

establishing a local history table at each of said processors, each said local history table containing for each line in cache memory a record of one of whether said line was cross-interrogate invalidated without refetching said line from said shared main storage and whether said line was stored into by the processor corresponding to each said local history table since a last fetch of said line;

setting an entry in said local history table when one of

a) said line is cross-interrogate invalidated from any processor and

b) the buffer control element receives

a data store for said line occurs, corresponding to said record in said local history table, and resetting said entry corresponding to said record in said local history table when said processor fetches said line into its cache memory from said shared main storage; and

examining entries in said local history table for selected lines which have addresses having a predetermined relationship to a particular line to be accessed by the processor corresponding to said local history table, said predetermined relationship indicating an increased likelihood of a respective one of said selected lines being required, and when

a) said particular line is not available in said local cache memory and

b) said local history table contains at least one entry which is set corresponding to a respective one of at least one selected line having said predetermined relationship to said particular line,

fetching said particular line and prefetching only ones of said selected lines having said predetermined relationship to said particular line and also correspond to ones of said entries in said local history table which are set.

2. The method of data prefetching recited in claim 1 wherein said main storage is divided by blocks, each block containing lines of data, and the step of prefetching is performed by prefetching selected lines of a block of data from said main storage containing said line to be accessed.

3. The method of data prefetching recited in claim 2 wherein said selected lines of data comprises a line sequentially preceding said line and two lines next sequentially following said line to be accessed.

4. The method of data prefetching recited in claim 1 wherein said step of establishing local history tables is performed by storing said local history tables in the buffer control elements for each said processors.

5. In a multi-processor system comprising a plurality of processors, a shared main storage and a storage control element, each of said processors having a local cache memory and a buffer control element, a computer implemented method of data prefetching comprising the steps of:

establishing a history table at said storage control element, said history table containing for each line in said cache memories of said processors a record of one of whether said line was cross-interrogate invalidated without refetching said line from said shared main storage and whether said line was stored into since the last fetch of said line by a particular processor;

setting an entry in said history table when one of

a) said line is cross-interrogate invalidated from any processor and

b) the buffer control element of said particular processor receives a data store for said line

occurs, corresponding to a record in said history table, and resetting the entry when said particular processor fetches said line into its cache memory from said shared main storage; and

,

examining entries in said history table for selected lines which have addresses having a predetermined relationship to a particular line to be accessed by the processor corresponding to said history table, said predetermined relationship indicating an increased likelihood of a respective one of said selected lines being required, and when

a) said particular line is not available in said local cache memory of said particular processor and

b) said history table contains at least one entry which is set corresponding to a respective one of at least one selected line having said predetermined relationship to said particular line,

fetching said particular line and prefetching only ones of said selected lines having said predetermined relationship to said particular line and also correspond to ones of said entries in said history table which are set.

6. The method of data prefetching recited in claim 5 wherein said main storage is divided by blocks, each block containing lines of data, and the step of prefetching is performed by prefetching selected lines of a block of data from said main storage containing said line to be accessed.

7. The method of data prefetching recited in claim 6 wherein said selected lines of data comprises a line sequentially preceding said particular line and two lines next sequentially following said particular line to be accessed.

8. In a multi-processor system comprising a plurality of processors, a shared main storage and a storage control element, each of said processors having a local cache memory and a buffer control element, a computer implemented method of data prefetching comprising the steps of:

establishing a history table at said storage control element, said history table containing for each line in said cache memories of said processors a record of one of whether said line was cross-interrogate invalidated without refetching said line from said shared main storage and whether said line was stored into since the last fetch of said line by a particular processor;

setting an entry in said history table when one of

a) said line is cross-interrogate invalidated from any processor and

b) the storage control element of said particular processor receives a data store for said line

occurs, corresponding to a record in said history table, and resetting said entry when said particular processor fetches said line into its cache memory from said shared main storage; and

,

examining entries in said history table for selected lines which have addresses having a predetermined relationship to a particular line to be accessed by the processor corresponding to said history table, said predetermined relationship indicating an increased likelihood of a respective one of said selected lines being required, and when

a) said particular line is not available in said local cache memory of said particular processor and

b) said history table contains at least one entry which is set corresponding to a respective one of at least one selected line having said predetermined relationship to said particular line,

fetching said particular line and prefetching only ones of said selected lines having said predetermined relationship to said particular line and also correspond to ones of said entries in said history table which are set.

9. The method of data prefetching recited in claim 8 wherein said main storage is divided by blocks, each block containing lines of data, and the step of prefetching is performed by prefetching at least one selected line of data from said main storage containing said line to be accessed.

10. The method of data prefetching recited in claim 9 wherein said selected lines of data comprise a line sequentially preceding said particular line and two lines next sequentially following said particular line to be accessed.

11. A multi-processor data processing system having a plurality of processors, a shared main storage and a storage control element, each of said processors in said multi-processor data processing system having a local cache memory and a buffer control element, said multi-processor data processing system including

a history table containing an entry for each line of at least one of said local cache memories,

means for setting an entry in said history table upon the occurrence of at least one of a cross-interrogate invalidate of the line corresponding to said entry in said at least one of said cache memories and a data store for the line corresponding to said entry in said at least one of said cache memories,

means for resetting said entry when a processor associated with said at least one cache memory fetches said line into its cache memory from said shared main storage,

means for detecting that a particular line is unavailable to a processor from its cache, and

means for fetching said particular line and means for prefetching only selected lines from said shared main storage which correspond to ones of said entries in said history table which are set and also which have a predetermined relationship to said particular line, said predetermined relationship indicating an increased likelihood of said line being required.

12. A multi-processor data processing system as recited in claim 11, wherein said history table is a local history table containing an entry for each line in said cache memory of at least one processor of said multi-processor data processing system.

13. A multi-processor data processing system as recited in claim 11, wherein said history table is a global history table containing an entry for each cache memory of each of said processors of said multi-processor data processing system.

14. A multi-processor data processing system as recited in claim 13, wherein said means for setting an entry in said global history table includes means for setting said entry when a line corresponding to said entry is cross-interrogate invalidated from any processor.

15. A multi-processor data processing system as recited in claim 11, wherein said predetermined relationship to said particular line defines a block of consecutive lines.

16. A multi-processor data processing system as recited in claim 15, wherein said block of lines includes a line preceding said particular line and two lines following said particular line.

17. A multi-processor data processing system as recited in claim 11, wherein at least one said buffer control element contain said history table.