Patent US4736293A successfully refreshed from Google Patents.
US4736293A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Interleaved set-associative memory
Assignee: Nokia Bell Labs
•
Filing: 1984-04-11
•
Granted: 1988-04-05
•
Expires: 2004-04-11
Abstract
Abstract In a processing system (10) comprising a main memory (102) for storing blocks (150) of four contiguous words (160) of information, a cache memory (101) for storing selected ones of the blocks, and a two-word wide bus (110) for transferring words from the main memory to the cache, the cache memory is implemented in two memory parts (301, 302) as a two-way interleaved two-way set-associative memory. One memory part implements odd words of one cache set (0), and even words of the other cache set (1), while the other memory part implements even words of the one cache set and odd words of the other cache set. Storage locations (303) of the memory parts are grouped into at least four levels (204) with each level having a location from each of the memory parts and each of the cache sets. The cache receives a block over the bus in two pairs of contiguous words. The cache memory is updated with both words of a word pair simultaneously. The pairs of words are each stored simultaneously into locations of one of either of the cache sets, each word into a location of a different memory part and of a different level. Cache hit check is performed on all locations of a level simultaneously. Simultaneously with the hit check, all locations of the checked level are accessed simultaneously.
Inventors
- 👤 David M. Patrick
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 19:38
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0844; G06F12/0846; G06F12/0851; G06F12/0864
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
161 words
An associative memory comprising: a plurality of memory parts each including a plurality of memory locations each for storing a word of information, the locations of the plurality of memory parts being grouped into a plurality of levels and each level having a location from each of the memory parts, each location of a level for storing any word of a plurality of words associated with that level, the plurality of parts defining a plurality of frames, each frame defined by a plurality of locations each from a different level, a frame for storing any block of words of a plurality of blocks, each block having a plurality of words each associated with a different level; means for storing a plurality of words simultaneously, each word into a location of the associated level and of a different memory part; and means for checking for presence of a desired word simultaneously in all locations of the level associated with the desired word.
Claim 2
Dependent Claim
161 words
An associative memory comprising: a plurality of memory parts each including a plurality of memory locations each for storing a word of information, the locations of the plurality of memory parts being grouped into a plurality of levels and each level having a location from each of the memory parts, each location of a level for storing any word of a plurality of words associated with that level, the plurality of parts defining a plurality of frames, each frame defined by a plurality of locations each from a different level, a frame for storing any block of words of a plurality of blocks, each block having a plurality of words each associated with a different level; means for storing a plurality of words simultaneously, each word into a location of the associated level and of a different memory part; and means for checking for presence of a desired word simultaneously in all locations of the level associated with the desired word.
Claim 3
Dependent Claim
42 words
The apparatus of claim 1 wherein the means for storing comprise: means for receiving a plurality of words simultaneously; and means for storing the received words simultaneously, each word into a location of a different memory part and of the associated level.
Claim 4
Dependent Claim
48 words
The apparatus of claim 2 wherein wherein the receiving means comprise means for simultaneously receiving a plurality of contiguous words; and wherein the storing means comprise means for storing the received words simultaneously, each word into a location of a different memory part and of a different level.
Claim 5
Dependent Claim
16 words
The apparatus of claim 1 further comprising: means for accessing all locations of a level simultaneously.
Claim 6
Dependent Claim
23 words
The apparatus of claim 1 further comprising: means operative simultaneously with the checking means for simultaneously accessing all locations of the checked level.
Claim 7
Dependent Claim
176 words
A set-associative cache memory comprising: a plurality of memory parts each including a plurality of memory locations each for storing a word of information, the locations of the plurality of memory parts being grouped into a plurality of levels and each level having a location from each of the memory parts, each location of a level for storing any word of a plurality of words associated with that level, the plurality of parts defining a plurality of sets of frames, each frame defined by a plurality of locations each from a different level, a frame of each set for storing any block of words of a plurality of blocks, each block having a plurality of words each associated with a different level; means for storing a plurality of words of a block simultaneously into one of the associated frames, each word in a location of the associated level and of a different memory part; and means for checking for presence of a desired word simultaneously in all locations of the level associated with the desired word.
Claim 8
Dependent Claim
176 words
A set-associative cache memory comprising: a plurality of memory parts each including a plurality of memory locations each for storing a word of information, the locations of the plurality of memory parts being grouped into a plurality of levels and each level having a location from each of the memory parts, each location of a level for storing any word of a plurality of words associated with that level, the plurality of parts defining a plurality of sets of frames, each frame defined by a plurality of locations each from a different level, a frame of each set for storing any block of words of a plurality of blocks, each block having a plurality of words each associated with a different level; means for storing a plurality of words of a block simultaneously into one of the associated frames, each word in a location of the associated level and of a different memory part; and means for checking for presence of a desired word simultaneously in all locations of the level associated with the desired word.
Claim 9
Dependent Claim
31 words
The apparatus of claim 6 wherein the means for storing comprise: means for receiving a plurality of contiguous words of a block simultaneously; and means for storing the received words simultaneously.
Claim 10
Dependent Claim
115 words
The apparatus of claim 7 wherein the receiving means comprise means for receiving a first plurality of contiguous words of a block simultaneously, and for receiving a second plurality of contiguous words of the block simultaneously; and wherein the storing means comprise means for selecting one of the frames associated with the block, and means for storing one of the received pluralities of words into the selected frame simultaneously, each word into a location of the associated level and of a different memory part, and for storing the other of the received pluralities of words into the selected frame simultaneously, each word into a location of the associated level and of a different memory part.
Claim 11
Dependent Claim
21 words
The apparatus of claim 6 further comprising: means for simultaneously accessing all locations of a level associated with the desired word.
Claim 12
Dependent Claim
23 words
The apparatus of claim 6 further comprising: means operative simultaneously with the checking means for simultaneously accessing all locations of the checked level.
Claim 13
Dependent Claim
233 words
A two-way set-associative two-way interleaved cache memory comprising: a pair of memory parts each comprising a plurality of storage locations each for storing a word of information, the locations of one memory part defining even locations of a first cache set of a plurality of locations and odd locations of a second cache set of a plurality of locations and the other memory part defining odd locations of the first cache set and even locations of the second cache set, the locations of the pair of memory parts being grouped into at least four levels and each level having a location from each of the memory parts and each of the cache sets; means for receiving simultaneously a first pair of contiguous words of a block of four contiguous words, and for receiving simultaneously a second pair of contiguous words of the block; means for storing one pair of the received words simultaneously into locations of one cache set, each word into a location of a different memory part and of a different level of first and second levels, and for storing the other pair of received words simultaneously in locations of the one cache set, each word into a location of a different memory part and of a different level of third and fourth levels; and means for simultaneously checking all locations of a level for presence therein of a desired word.
Claim 14
Dependent Claim
233 words
A two-way set-associative two-way interleaved cache memory comprising: a pair of memory parts each comprising a plurality of storage locations each for storing a word of information, the locations of one memory part defining even locations of a first cache set of a plurality of locations and odd locations of a second cache set of a plurality of locations and the other memory part defining odd locations of the first cache set and even locations of the second cache set, the locations of the pair of memory parts being grouped into at least four levels and each level having a location from each of the memory parts and each of the cache sets; means for receiving simultaneously a first pair of contiguous words of a block of four contiguous words, and for receiving simultaneously a second pair of contiguous words of the block; means for storing one pair of the received words simultaneously into locations of one cache set, each word into a location of a different memory part and of a different level of first and second levels, and for storing the other pair of received words simultaneously in locations of the one cache set, each word into a location of a different memory part and of a different level of third and fourth levels; and means for simultaneously checking all locations of a level for presence therein of a desired word.
Claim 15
Dependent Claim
21 words
The apparatus of claim 11 further comprising: means for simultaneously accessing all locations of a level associated with the desired word.
Claim 16
Dependent Claim
23 words
The apparatus of claim 11 further comprising: means operative simultaneously with the checking means for simultaneously accessing all locations of the checked level.
Claim 17
Dependent Claim
215 words
A processing system comprising a main memory for storing a plurality of words of information, a cache memory for storing selected ones of the main memory words, and a communication bus for transferring simultaneously a plurality of words from the main memory to the cache memory, the cache memory comprising: a plurality of memory parts each including a plurality of memory locations each for storing a word, the locations of the plurality of memory parts being grouped into a plurality of levels and each level having a location from each of the memory parts, each location of a level for storing any word of a plurality of words associated with that level, the plurality of parts defining a plurality of frames, each frame defined by a plurality of locations each from a different level, a frame for storing any block of words of a plurality of blocks, each block having a plurality of words each associated with a different level; means for receiving from the bus a plurality of words simultaneously; means for storing the received words simultaneously, each word into a location of the associated level and of a different memory part; and means for checking for presence of a desired word simultaneously in all locations of the level associated with the desired word.
Claim 18
Dependent Claim
215 words
A processing system comprising a main memory for storing a plurality of words of information, a cache memory for storing selected ones of the main memory words, and a communication bus for transferring simultaneously a plurality of words from the main memory to the cache memory, the cache memory comprising: a plurality of memory parts each including a plurality of memory locations each for storing a word, the locations of the plurality of memory parts being grouped into a plurality of levels and each level having a location from each of the memory parts, each location of a level for storing any word of a plurality of words associated with that level, the plurality of parts defining a plurality of frames, each frame defined by a plurality of locations each from a different level, a frame for storing any block of words of a plurality of blocks, each block having a plurality of words each associated with a different level; means for receiving from the bus a plurality of words simultaneously; means for storing the received words simultaneously, each word into a location of the associated level and of a different memory part; and means for checking for presence of a desired word simultaneously in all locations of the level associated with the desired word.
Claim 19
Dependent Claim
47 words
The apparatus of claim 14 wherein the receiving means comprise means for simultaneously receiving a plurality of contiguous words; and wherein the storing means comprise means for storing the received words simultaneously, each word into a location of a different memory part and of a different level.
Claim 20
Dependent Claim
16 words
The apparatus of claim 14 further comprising: means for accessing all locations of a level simultaneously.
Claim 21
Dependent Claim
23 words
The apparatus of claim 14 further comprising: means operative simultaneously with the checking means for simultaneously accessing all locations of the checked level.
Claim 22
Dependent Claim
226 words
A processing system comprising a main memory for storing a plurality of words of information, a set-associative cache memory for storing selected ones of the main memory words, and a communication bus for transferring simultaneously a plurality of words from the main memory to the cache memory, the cache memory comprising: a plurality of memory parts each including a plurality of memory locations each for storing a word, the locations of the plurality of memory parts being grouped into a plurality of levels and each level having a location from each of the memory parts, each location of a level for storing any word of a plurality of words associated with that level, the plurality of parts defining a plurality of sets of frames, each frame defined by a plurality of locations each from a different level, a frame of each set for storing any block of a plurality of blocks associated with those frames, each block having a plurality of words; means for receiving from the bus a plurality of words of a block simultaneously; means for storing the received words simultaneously into one of the associated frames, each word into a location of the associated level and of a different memory part; and means for checking for presence of a desired word in all locations of the level associated with the desired word simultaneously.
Claim 23
Dependent Claim
226 words
A processing system comprising a main memory for storing a plurality of words of information, a set-associative cache memory for storing selected ones of the main memory words, and a communication bus for transferring simultaneously a plurality of words from the main memory to the cache memory, the cache memory comprising: a plurality of memory parts each including a plurality of memory locations each for storing a word, the locations of the plurality of memory parts being grouped into a plurality of levels and each level having a location from each of the memory parts, each location of a level for storing any word of a plurality of words associated with that level, the plurality of parts defining a plurality of sets of frames, each frame defined by a plurality of locations each from a different level, a frame of each set for storing any block of a plurality of blocks associated with those frames, each block having a plurality of words; means for receiving from the bus a plurality of words of a block simultaneously; means for storing the received words simultaneously into one of the associated frames, each word into a location of the associated level and of a different memory part; and means for checking for presence of a desired word in all locations of the level associated with the desired word simultaneously.
Claim 24
Dependent Claim
115 words
The apparatus of claim 18 wherein the receiving means comprise means for receiving a first plurality of contiguous words of a block simultaneously, and for receiving a second plurality of contiguous words of the block simultaneously; and wherein the storing means comprise means for selecting one of the frames associated with the block, and means for storing one of the received pluralities of words into the selected frame simultaneously, each word into a location of the associated level and of a different memory part, and for storing the other of the received pluralities of words into the selected frame simultaneously, each word into a location of the associated level and of a different memory part.
Claim 25
Dependent Claim
21 words
The apparatus of claim 18 further comprising: means for simultaneously accessing all locations of a level associated with the desired word.
Claim 26
Dependent Claim
23 words
The apparatus of claim 18 further comprising: means operative simultaneously with the checking means for simultaneously accessing all locations of the checked level.
Claim 27
Dependent Claim
284 words
A processing system comprising a main memory for storing a plurality of blocks of four contiguous words of information, a two-way set-associative two-way interleaved cache memory for storing selected ones of the main memory blocks, and a communication bus for transferring in parallel a pair of words of a block from the main memory to the cache memory, the cache memory comprising: a pair of memory parts each comprising a plurality of memory locations each for storing a word, the locations of one memory part defining even locations of a first cache set of a plurality of locations and odd locations of a second cache set of a plurality of locations and the other memory part defining odd locations of the first cache set and even locations of the second cache set, the locations of the pair of memory parts being grouped into at least four levels and each level having a location from each of the memory parts and each of the cache sets; means for receiving simultaneously from the bus a first pair of contiguous words of a block, and for receiving simultaneously a second pair of contiguous words of the block; means for storing one pair of the received words simultaneously into locations of one cache set, each word into a location of a different memory part and of a different level of first and second levels, and for storing the other pair of received words simultaneously in locations of the one cache set, each word into a location of a different memory part and of a different level of third and fourth levels; and means for simultaneously checking all locations of a level for presence therein of a desired word.
Claim 28
Dependent Claim
284 words
A processing system comprising a main memory for storing a plurality of blocks of four contiguous words of information, a two-way set-associative two-way interleaved cache memory for storing selected ones of the main memory blocks, and a communication bus for transferring in parallel a pair of words of a block from the main memory to the cache memory, the cache memory comprising: a pair of memory parts each comprising a plurality of memory locations each for storing a word, the locations of one memory part defining even locations of a first cache set of a plurality of locations and odd locations of a second cache set of a plurality of locations and the other memory part defining odd locations of the first cache set and even locations of the second cache set, the locations of the pair of memory parts being grouped into at least four levels and each level having a location from each of the memory parts and each of the cache sets; means for receiving simultaneously from the bus a first pair of contiguous words of a block, and for receiving simultaneously a second pair of contiguous words of the block; means for storing one pair of the received words simultaneously into locations of one cache set, each word into a location of a different memory part and of a different level of first and second levels, and for storing the other pair of received words simultaneously in locations of the one cache set, each word into a location of a different memory part and of a different level of third and fourth levels; and means for simultaneously checking all locations of a level for presence therein of a desired word.
Claim 29
Dependent Claim
21 words
The apparatus of claim 22 further comprising: means for simultaneously accessing all locations of a level associated with the desired word.
Claim 30
Dependent Claim
23 words
The apparatus of claim 22 further comprising: means operative simultaneously with the checking means for simultaneously accessing all locations of the checked level.
References Cited (Backward Citations)
US3967247A
Cited
US4056845A
Cited
US4195340A
Cited
US4195342A
Cited
US4208716A
Cited
US4317168A
Cited
US4315312A
Cited
US4371928A
Cited
US4371929A
Cited
US4381541A
Cited
US4378591A
Cited
US4392201A
Cited
US4424561A
Cited
US4439829A
Cited
US4525780A
Cited
US4493026A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1991-04-05 | 1991-10-05 | 1992-04-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1995-04-05 | 1995-10-05 | 1996-04-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1999-04-05 | 1999-10-05 | 2000-04-05 | $7700.00 | Window Closed / Lapsed |