Patent US5509135A successfully refreshed from Google Patents.
US5509135A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Multi-index multi-way set-associative cache
Assignee: Hewlett Packard Development Co LP
•
Filing: 1992-09-25
•
Granted: 1996-04-16
•
Expires: 2012-09-25
Abstract
Abstract A plurality of indexes are provided for a multi-way set-associate cache of a computer system. The cache is organized as a plurality of blocks for storing data which are a copies of main memory data. Each block has an associated tag for uniquely identifying the block. The blocks and the tags are addressed by indexes. The indexes are generated by a Boolean hashing function which converts a memory address to cache indexes by combining the bits of the memory address using an exclusive OR function. Different combination of bits are used to generate a plurality of different indexes to address the tags and the associated blocks to transfer data between the cache and the central processing unit of the computer system.
Inventors
- 👤 Simon C. Steely, Jr.
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 03:45
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0864
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
225 words
An apparatus for a central processing unit to address data in a second memory, the data in the second memory being a copy of data in a first memory, the first memory having a plurality of bytes storing data, each byte of the first memory addressable by a memory address, comprising: means for storing a plurality of tags and a plurality of blocks in the second memory, each tag associated with one block, and each tag and said associated one block addressable by an index; means, connected to an input of the second memory, for converting a selected memory address to a selected tag and a plurality of different indexes, each different index individually addressing one of said plurality of tags in the second memory; means, connected to said means for converting and said means for storing said plurality of tags, for comparing said selected tag with each of said plurality of tags individually addressed by each of said plurality of different indexes; and means, connected to said means for comparing and said means for storing said plurality of blocks and responsive to said selected tag being equal to one of said plurality of tags individually addressed by each of said different indexes, for addressing a selected block associated with said selected tag to transfer data from the central processing unit to the second memory.
Claim 2
Independent Claim
225 words
An apparatus for a central processing unit to address data in a second memory, the data in the second memory being a copy of data in a first memory, the first memory having a plurality of bytes storing data, each byte of the first memory addressable by a memory address, comprising: means for storing a plurality of tags and a plurality of blocks in the second memory, each tag associated with one block, and each tag and said associated one block addressable by an index; means, connected to an input of the second memory, for converting a selected memory address to a selected tag and a plurality of different indexes, each different index individually addressing one of said plurality of tags in the second memory; means, connected to said means for converting and said means for storing said plurality of tags, for comparing said selected tag with each of said plurality of tags individually addressed by each of said plurality of different indexes; and means, connected to said means for comparing and said means for storing said plurality of blocks and responsive to said selected tag being equal to one of said plurality of tags individually addressed by each of said different indexes, for addressing a selected block associated with said selected tag to transfer data from the central processing unit to the second memory.
Claim 3
Dependent Claim
48 words
The apparatus as in claim 1 whereto said means for converting includes means for translating said selected memory address to said selected tag and a selected index, and a plurality of means for combining said selected tag and said selected index to generate said plurality of different indexes.
Claim 4
Dependent Claim
18 words
The apparatus as in claim 2 wherein each of said means for combining includes a boolean hashing function.
Claim 5
Dependent Claim
16 words
The apparatus as in claim 3 wherein said boolean hashing function includes an exclusive OR function.
Claim 6
Dependent Claim
41 words
The apparatus as in claim 1 wherein said plurality of tags and said plurality of blocks are organized into a plurality of sets of tags and blocks, one set of tags and blocks for each of said plurality of different indexes.
Claim 7
Dependent Claim
50 words
The apparatus as in claim 1 wherein said plurality of tags are concurrently addressable by said plurality of different indexes and further comprising: a plurality of sets of lines connecting said means for converting, each one of said sets of lines for carrying one of said plurality of different indexes.
Claim 8
Independent Claim
158 words
A method for a central processing unit to address data in a second memory, the data in the second memory being a copy of data in a first memory, the first memory having a plurality of bytes storing data, each byte of the first memory addressable by a memory address, the method comprising: organizing the second memory into a plurality of tags and a plurality of blocks, each tag associated with one block, and each tag and said associated one block addressable by an index; converting a selected memory address to a selected tag and a plurality of different indexes, each different index individually addressing a different tag in the second memory; comparing said selected tag with each of said different tags; and addressing, as determined by said selected tag being equal to one of said different tags, a selected block associated with said selected tag to transfer data between the central processing unit and the second memory.
Claim 9
Independent Claim
158 words
A method for a central processing unit to address data in a second memory, the data in the second memory being a copy of data in a first memory, the first memory having a plurality of bytes storing data, each byte of the first memory addressable by a memory address, the method comprising: organizing the second memory into a plurality of tags and a plurality of blocks, each tag associated with one block, and each tag and said associated one block addressable by an index; converting a selected memory address to a selected tag and a plurality of different indexes, each different index individually addressing a different tag in the second memory; comparing said selected tag with each of said different tags; and addressing, as determined by said selected tag being equal to one of said different tags, a selected block associated with said selected tag to transfer data between the central processing unit and the second memory.
Claim 10
Dependent Claim
46 words
The method in claim 7 wherein said step for converting includes the step of translating said selected memory address to said selected tag and a selected index, and a step for combining said selected tag and said selected index to generate said plurality of different indexes.
Claim 11
Dependent Claim
30 words
The method as in claim 8 wherein said step for combining includes the step of hashing by a plurality of boolean hashing functions to generate said plurality of different indexes.
Claim 12
Dependent Claim
16 words
The method as in claim 9 wherein said hashing step includes the step of exclusive ORing.
Claim 13
Dependent Claim
41 words
The method as in claim 7 including the step of organizing said plurality of rags and said plurality of blocks into a plurality of sets of tags and blocks, one set of tags and blocks for each of said different indexes.
Claim 14
Dependent Claim
31 words
The method as in claim 7 including the step of concurrently addressing said plurality of tags by said selected tag and addressing said selected block by said plurality of different indexes.
Claim 15
Independent Claim
318 words
An apparatus for a central processing unit to address data in a second memory, the data in the second memory being a copy of data in a first memory, the first memory having a plurality of bytes storing data, each byte of the first memory addressable by a memory address, comprising: means for storing a plurality of tags and a plurality of blocks in the second memory, each tag associated with one block, and each tag and said associated one block concurrently addressable by an index, said plurality of tags and said plurality of blocks organized into a plurality of sets of tags and blocks, one set of tags and blocks for each of said different indexes; means, connected to an input of the second memory, for translating a selected memory address to a selected tag and a selected index, said selected tag, said selected index, and said selected memory address each having a plurality of bits, the number of bits of said selected tag plus the number of bits of said selected index equal to the number of bits of said selected memory address; a plurality of means, connected to said means for translating, for combining said bits of said selected tag and an equal number of bits of said selected index to generate a plurality of different indexes, each different index individually addressing a different tag in the second memory, the number of different indexes equal to the number of said sets into which said tags and said associated blocks are organized; means, connected to an output of the second memory, for comparing said selected tag with each of said different tags; and means, connected to said means for comparing and responsive to said selected tag being equal to one of said different tags, for addressing a selected block associated with said selected tag to transfer data between the central processing unit and the second memory.
Claim 16
Independent Claim
318 words
An apparatus for a central processing unit to address data in a second memory, the data in the second memory being a copy of data in a first memory, the first memory having a plurality of bytes storing data, each byte of the first memory addressable by a memory address, comprising: means for storing a plurality of tags and a plurality of blocks in the second memory, each tag associated with one block, and each tag and said associated one block concurrently addressable by an index, said plurality of tags and said plurality of blocks organized into a plurality of sets of tags and blocks, one set of tags and blocks for each of said different indexes; means, connected to an input of the second memory, for translating a selected memory address to a selected tag and a selected index, said selected tag, said selected index, and said selected memory address each having a plurality of bits, the number of bits of said selected tag plus the number of bits of said selected index equal to the number of bits of said selected memory address; a plurality of means, connected to said means for translating, for combining said bits of said selected tag and an equal number of bits of said selected index to generate a plurality of different indexes, each different index individually addressing a different tag in the second memory, the number of different indexes equal to the number of said sets into which said tags and said associated blocks are organized; means, connected to an output of the second memory, for comparing said selected tag with each of said different tags; and means, connected to said means for comparing and responsive to said selected tag being equal to one of said different tags, for addressing a selected block associated with said selected tag to transfer data between the central processing unit and the second memory.
Claim 17
Dependent Claim
18 words
The apparatus as in claim 13 wherein each of said means for combining includes an exclusive OR function.
Claim 18
Dependent Claim
25 words
The apparatus as in claim 13 wherein said means for comparing includes a comparator and said means for addressing said selected block includes a multiplexer.
Claim 19
Dependent Claim
15 words
The apparatus as in claim 13 wherein the second memory is a cache buffer memory.
Claim 20
Dependent Claim
16 words
The apparatus as in claim 13 wherein each of said sets is a random access memory.
References Cited (Backward Citations)
US4860199A
Cited
US4942520A
Cited
US5133061A
Cited
US5067078A
Cited
US5182799A
Cited
US5155832A
Cited
US5091851A
Cited
US5136700A
Cited
US5014195A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-04-16 | 1999-10-16 | 2000-04-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-04-16 | 2003-10-16 | 2004-04-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-04-16 | 2007-10-16 | 2008-04-16 | $7700.00 | Window Closed / Lapsed |