Patent US5214766A successfully refreshed from Google Patents.
US5214766A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Data prefetching based on store information in multi-processor caches
Assignee: International Business Machines Corp
•
Filing: 1992-08-19
•
Granted: 1993-05-25
•
Expires: 2012-08-19
Abstract
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.
Inventors
- 👤 Lishing Liu
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 20:56
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0862; G06F12/0806; G06F12/0815; G06F12/0817; G06F12/0822; G06F2212/00; G06F2212/60; G06F2212/6024
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
313 words
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.
Claim 2
Dependent Claim
313 words
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.
Claim 3
Dependent Claim
49 words
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.
Claim 4
Dependent Claim
33 words
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.
Claim 5
Dependent Claim
34 words
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.
Claim 6
Dependent Claim
303 words
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.
Claim 7
Dependent Claim
303 words
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.
Claim 8
Dependent Claim
49 words
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.
Claim 9
Dependent Claim
35 words
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.
Claim 10
Dependent Claim
303 words
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.
Claim 11
Dependent Claim
303 words
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.
Claim 12
Dependent Claim
49 words
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.
Claim 13
Dependent Claim
35 words
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.
Claim 14
Dependent Claim
218 words
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.
Claim 15
Dependent Claim
218 words
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.
Claim 16
Dependent Claim
40 words
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.
Claim 17
Dependent Claim
37 words
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.
Claim 18
Dependent Claim
41 words
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.
Claim 19
Dependent Claim
24 words
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.
Claim 20
Dependent Claim
29 words
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.
Claim 21
Dependent Claim
22 words
A multi-processor data processing system as recited in claim 11, wherein at least one said buffer control element contain said history table.
References Cited (Backward Citations)
US3618040A
Cited
US4142234A
Cited
US4467421A
Cited
US4394731A
Cited
EP0062165A2
Cited
US4489378A
Cited
US4370645A
Cited
US4507656A
Cited
US4638431A
Cited
US4980823A
Cited
US5018063A
Cited
US5016168A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-05-24 | 1996-11-23 | 1997-05-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-05-24 | 2000-11-23 | 2001-05-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-05-24 | 2004-11-23 | 2005-05-25 | $7700.00 | Window Closed / Lapsed |