Patent US3835089A successfully refreshed from Google Patents.
US4426682A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Fast cache flush mechanism
Assignee: Harris Corp
•
Filing: 1981-05-22
•
Granted: 1984-01-17
•
Expires: 2001-05-22
Abstract
Abstract A fast cache flush mechanism includes, associated with the cache, an auxiliary portion (termed a flush count memory) that references a flush counter during the addressing of the cache. This flush counter preferably has a count capacity of the same size as the number of memory locations in the cache. Whenever the cache is updated, the current value of the flush counter is written into the location in the flush count memory associated with the memory location in the cache pointed to by an accessing address, and the valid bit is set. Whenever it is desired to flush the cache, the contents of the flush counter are changed (e.g. incremented) to a new value which is then written as the new cache index into the location of the flush count memory associated with that flush count, and the associated valid bit is cleared or reset. Any access to the cache by the address requires that the cache index in the associated flush count memory location match the current contents of the flush counter and that the valid bit be set. When the cache is flushed by the above procedure, these conditions cannot be fulfilled, since the current contents of the flush counter do not match any cache index or the valid bit has been reset. As a result, for each addressed memory location that has not been accessed since the last cache flush command (corresponding to the latest incrementing of the flush counter), the total contents of that memory location (i.e. data, cache index and validity bit) are updated in the manner described above. Through this procedure, once the contents of the flush counter have recycled back to a previous value, it is guaranteed that each memory location in the cache will have been flushed and, in many instances, updated with valid data.
Inventors
- 👤 Josephus Riffe
- 👤 Rajiv Sinha
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 16:01
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0891
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
316 words
For use in a data processing system having a cache in which information to be employed during the operation of said system may be stored and accessed, an arrangement for controlling the validity of the information stored within said cache comprising: a first memory section, respective memory locations of which are associated with respective cache memory locations in which said information is stored in the cache; a second memory section for storing data representative of whether or not information contained in the respective cache memory locations in which said information is stored in the cache is valid information; first means for storing a reference code, the value of which is selectively variable; second means, responsive to a request to store valid information in a selected cache memory location, for storing, in the associated memory location in said first memory section, the reference code stored by said first means and for storing, in the associated memory location in said second memory section, data representative of the validity of said information; third means, coupled to said first and second memory sections and to said first means, and responsive to a request to access valid information stored in a selected cache memory location, for comparing the contents of the associated memory location in said first memory section with the reference code stored by said first means, and for generating an output indicative that the information stored in said selected cache memory location is invalid in response to a mismatch between the contents of the associated memory location in said first memory section and said reference code stored by said first means or in response to the data contained in the associated location in said second memory section representing that the information is invalid; and fourth means, responsive to a request to render invalid all information stored in said cache, for changing the reference code stored by said first means.
Claim 2
Dependent Claim
316 words
For use in a data processing system having a cache in which information to be employed during the operation of said system may be stored and accessed, an arrangement for controlling the validity of the information stored within said cache comprising: a first memory section, respective memory locations of which are associated with respective cache memory locations in which said information is stored in the cache; a second memory section for storing data representative of whether or not information contained in the respective cache memory locations in which said information is stored in the cache is valid information; first means for storing a reference code, the value of which is selectively variable; second means, responsive to a request to store valid information in a selected cache memory location, for storing, in the associated memory location in said first memory section, the reference code stored by said first means and for storing, in the associated memory location in said second memory section, data representative of the validity of said information; third means, coupled to said first and second memory sections and to said first means, and responsive to a request to access valid information stored in a selected cache memory location, for comparing the contents of the associated memory location in said first memory section with the reference code stored by said first means, and for generating an output indicative that the information stored in said selected cache memory location is invalid in response to a mismatch between the contents of the associated memory location in said first memory section and said reference code stored by said first means or in response to the data contained in the associated location in said second memory section representing that the information is invalid; and fourth means, responsive to a request to render invalid all information stored in said cache, for changing the reference code stored by said first means.
Claim 3
Dependent Claim
70 words
An arrangement according to claim 1, wherein said fourth means includes means for storing said changed reference code in the memory location of said first memory section identified by the reference code stored by said first means and for causing the data in the associated memory location in said second memory section to be representative that the information stored in the associated memory location in the cache memory is invalid.
Claim 4
Dependent Claim
71 words
An arrangement according to claim 1, wherein said fourth means includes means for storing said changed reference code in a plurality of memory locations of said first memory section associated with the reference code stored by said first means and for causing the data in associated memory locations in said second memory section to be representative that the information stored in the associated memory locations in the cache memory is invalid.
Claim 5
Dependent Claim
22 words
An arrangement according to claim 3, wherein said first means comprises a binary counter a prescribed number of N bits in size.
Claim 6
Dependent Claim
16 words
An arrangement according to claim 4, wherein said cache memory contains M×2 N cache memory locations.
Claim 7
Dependent Claim
37 words
An arrangement according to claim 1, wherein said first means comprises a counter and said fourth means comprises means for causing the counter to count in a prescribed direction, thereby changing its contents and said reference code.
Claim 8
Dependent Claim
24 words
An arrangement according to claim 6, wherein said fourth means comprises means for incrementing the contents of said counter to a new reference code.
Claim 9
Dependent Claim
69 words
An arrangement according to claim 7, wherein said fourth means includes means for causing the changed reference code to be stored in the memory location of said first memory section identified by said change reference code and for causing the data in the associated memory location in said second memory section to be representative that the information stored in the associated memory location in the cache memory is invalid.
Claim 10
Dependent Claim
142 words
An arrangement according to claim 8, wherein said request to access valid information stored in said selected cache memory location comprises an address access code for accessing data from said selected cache memory location; said arrangement further includes a third memory section, respective memory locations of which are associated with the respective cache memory locations in which said information is stored in the cache and contain memory address codes respectively associated with said cache memory locations; and said third means includes means for comparing said address access code with the memory address code stored in the memory location of said third memory section associated with said selected cache memory location and generating an output indicative that the information stored in said selected cache memory location is invalid in response to a mismatch between said address access code and said memory address code.
Claim 11
Dependent Claim
88 words
An arrangement according to claim 9, wherein said third means includes means for generating an output indicating that the information stored in said selected cache memory location is valid in response to: a match between the contents of said associated memory location in said first memory section and the reference code stored by said first means and a match between said address access code and said memory address code; and the data contained in the associated location in said second memory section representing that the information is valid.
Claim 12
Dependent Claim
51 words
An arrangement according to claim 10, wherein said address access code comprises an address and wherein said arrangement further includes fifth means for converting said address into a memory location selection code through which associated memory locations of said first, second and third memory sections and said cache memory are addressed.
Claim 13
Dependent Claim
20 words
An arrangement according to claim 6, wherein said counter is a binary counter a prescribed number N bits in size.
Claim 14
Dependent Claim
16 words
An arrangement according to claim 12, wherein said cache memory contains 2 N cache memory locations.
Claim 15
Dependent Claim
32 words
An arrangement according to claim 13, wherein said second memory section comprises a validity bit memory section having a 2 N storage locations respectively associated with said 2 N cache memory locations.
Claim 16
Dependent Claim
60 words
An arrangement according to claim 14, wherein said first memory section comprises an (N+1) ×2 N memory, the N most significant bits of cache memory address of which being associated with said data corresponding to the reference code stored by said counter, and the least significant bit of each memory address corresponding to the validity of said second memory section.
Claim 17
Dependent Claim
37 words
An arrangement according to claim 14, wherein said first memory section comprises an N×2 N memory, the N bits of each memory address being associated with said data corresponding to the reference code stored by said counter.
Claim 18
Dependent Claim
427 words
For use in a data processing system having a cache in which information to be employed during the operation of said system may be stored and accessed, an arrangement for controlling the validity of the information stored within said cache comprising: a first memory section, respective memory locations of which are associated with respective cache memory locations in which said information is stored in the cache; a second memory section for storing data representative of whether or not information contained in the respective cache memory locations in which said information is stored in the cache is valid information; first means for storing a reference code, the value of which is selectively variable; second means, responsive to a request to store valid information in a selected cache memory location, for storing, in the associated memory location in said first memory section, the reference code stored by said first means and for storing, in the associated memory location in said second memory section, data representative of the validity of said information; third means, coupled to said first and second memory sections and to said first means, and responsive to a request to access valid information stored in a selected cache memory location, for comparing the contents of the associated memory location in said first memory section with the reference code stored by said first means, and for generating an output indicative that the information stored in said selected cache memory location is invalid in response to a mismatch between the contents of the associated memory location in said first memory section and said reference code stored by said first means or in response to the data contained in the associated location in said second memory section representing that the information is invalid; and wherein said request to access valid information stored in said selected cache memory location comprises an address access code for accessing data from said selected cache memory location; said arrangement further includes a third memory section, respective memory locations of which are associated with the respective cache memory locations in which said information is stored in the cache and contain memory address codes respectively associated with said cache memory locations; and said third means includes means for comparing said address access code with the memory address code stored in the memory location of said third memory section associated with said selected cache memory location and generating an output indicative that the information stored in said selected cache memory location is invalid in response to a mismatch between said address access code and said memory address code.
Claim 19
Dependent Claim
427 words
For use in a data processing system having a cache in which information to be employed during the operation of said system may be stored and accessed, an arrangement for controlling the validity of the information stored within said cache comprising: a first memory section, respective memory locations of which are associated with respective cache memory locations in which said information is stored in the cache; a second memory section for storing data representative of whether or not information contained in the respective cache memory locations in which said information is stored in the cache is valid information; first means for storing a reference code, the value of which is selectively variable; second means, responsive to a request to store valid information in a selected cache memory location, for storing, in the associated memory location in said first memory section, the reference code stored by said first means and for storing, in the associated memory location in said second memory section, data representative of the validity of said information; third means, coupled to said first and second memory sections and to said first means, and responsive to a request to access valid information stored in a selected cache memory location, for comparing the contents of the associated memory location in said first memory section with the reference code stored by said first means, and for generating an output indicative that the information stored in said selected cache memory location is invalid in response to a mismatch between the contents of the associated memory location in said first memory section and said reference code stored by said first means or in response to the data contained in the associated location in said second memory section representing that the information is invalid; and wherein said request to access valid information stored in said selected cache memory location comprises an address access code for accessing data from said selected cache memory location; said arrangement further includes a third memory section, respective memory locations of which are associated with the respective cache memory locations in which said information is stored in the cache and contain memory address codes respectively associated with said cache memory locations; and said third means includes means for comparing said address access code with the memory address code stored in the memory location of said third memory section associated with said selected cache memory location and generating an output indicative that the information stored in said selected cache memory location is invalid in response to a mismatch between said address access code and said memory address code.
Claim 20
Dependent Claim
88 words
An arrangement according to claim 17, wherein said third means includes means for generating an output indicating that the information stored in said selected cache memory location is valid in response to: a match between the contents of said associated memory location in said first memory section and the reference code stored by said first means and a match between said address access code and said memory address code; and the data contained in the associated location in said second memory section representing that the information is valid.
Claim 21
Dependent Claim
51 words
An arrangement according to claim 17, wherein said address access code comprises an address and wherein said arrangement further includes fourth means for converting said address into a memory location selection code through which associated memory locations of said first, second and third memory sections and said cache memory are addressed.
Claim 22
Dependent Claim
59 words
An arrangement according to claim 17, wherein said arrangement further includes fourth means, responsive to the output of said third means indicating that the information stored in said selected cache memory location is invalid, for causing said address access code to be stored in the memory location of said third memory section associated with said selected cache memory location.
Claim 23
Dependent Claim
45 words
An arrangement according to claim 20, wherein said fourth means includes means for updating the information stored in said selected cache memory location in response to the output of said third means indicating that the information stored in said selected cache memory location is invalid.
Claim 24
Dependent Claim
59 words
An arrangement according to claim 21, wherein said arrangement further includes fifth means, responsive to the output of said third means indicating that the information stored in said selected cache memory location is invalid, for causing said address access code to be stored in the memory location of said third memory section associated with said selected cache memory location.
Claim 25
Dependent Claim
45 words
An arrangement according to claim 22, wherein said fourth means includes means for updating the information stored in said selected cache memory location in response to the output of said third means indicating that the information stored in said selected cache memory location is invalid.
Claim 26
Dependent Claim
28 words
An arrangement according to claim 23, wherein said fourth means includes means for causing said second memory section to store data representative that said updated information is valid.
Claim 27
Dependent Claim
326 words
For use in a data processing system having a cache in which information to be employed during the operation of said system may be stored and accessed, an arrangement for controlling the validity of the information stored within said cache comprising: a first memory section, respective memory locations of which are associated with respective cache memory locations in which said information is stored in the cache; a second memory section for storing data representative of whether or not information contained in the respective cache memory locations in which said information is stored in the cache is valid information; first means for storing a reference code, the value of which is selectively variable; second means, responsive to a request to store valid information in a selected cache memory location, for storing, in the associated memory location in said first memory section, the reference code stored by said first means and for storing, in the associated memory location in said second memory section, data representative of the validity of said information; third means, coupled to said first and second memory sections and to said first means, and responsive to a request to access valid information stored in a selected cache memory location, for comprising the contents of the associated memory location in said first memory section with the reference code stored by said first means, and for generating an output indicative that the information stored in said selected cache memory location is invalid in response to a mismatch between the contents of the associated memory location in said first memory section and said reference code stored by said first means or in response to the data contained in the associated location in said second memory section representing that the information is invalid; and fourth means for updating the information stored in said selected cache memory location in response to the output of said third means indicating that the information stored in said selected cache memory location is invalid.
Claim 28
Dependent Claim
326 words
For use in a data processing system having a cache in which information to be employed during the operation of said system may be stored and accessed, an arrangement for controlling the validity of the information stored within said cache comprising: a first memory section, respective memory locations of which are associated with respective cache memory locations in which said information is stored in the cache; a second memory section for storing data representative of whether or not information contained in the respective cache memory locations in which said information is stored in the cache is valid information; first means for storing a reference code, the value of which is selectively variable; second means, responsive to a request to store valid information in a selected cache memory location, for storing, in the associated memory location in said first memory section, the reference code stored by said first means and for storing, in the associated memory location in said second memory section, data representative of the validity of said information; third means, coupled to said first and second memory sections and to said first means, and responsive to a request to access valid information stored in a selected cache memory location, for comprising the contents of the associated memory location in said first memory section with the reference code stored by said first means, and for generating an output indicative that the information stored in said selected cache memory location is invalid in response to a mismatch between the contents of the associated memory location in said first memory section and said reference code stored by said first means or in response to the data contained in the associated location in said second memory section representing that the information is invalid; and fourth means for updating the information stored in said selected cache memory location in response to the output of said third means indicating that the information stored in said selected cache memory location is invalid.
References Cited (Backward Citations)
US3588829A
Cited
US3541529A
Cited
US3800286A
Cited
US3840862A
Cited
US3845474A
Cited
US3896419A
Cited
US4056844A
Cited
US4095269A
Cited
US4181937A
Cited
US4092713A
Cited
US4142234A
Cited
US4167782A
Cited
US4169284A
Cited
US4197580A
Cited
US4168541A
Cited
US4228503A
Cited
US4314331A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1987-01-16 | 1987-07-18 | 1988-01-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1991-01-16 | 1991-07-18 | 1992-01-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1995-01-16 | 1995-07-18 | 1996-01-17 | $7700.00 | Window Closed / Lapsed |