Interleaved set-associative memory

• US 4,736,293 A
• Filed: 04/11/1984
• Issued: 04/05/1988
• Est. Priority Date: 04/11/1984
• Status: Expired due to Term

• Current Assignee: Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Original Assignee: American Telephone & Telegraph Company (AT&T, Inc.)
• Inventors: Patrick, David M.
• Primary Examiner(s): Harkcom, Gary V.
• Assistant Examiner(s): Lacasse, Randy W.
• Application Number:
  US06/599,644
• Time in Patent Office: 1,455 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 711/128
• CPC Class Codes: G06F 12/0851 Cache with interleaved addressing
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing

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.

Claims

1. 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.

2. 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.

3. 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.

4. The apparatus of claim 1 further comprising:

means for accessing all locations of a level simultaneously.

5. The apparatus of claim 1 further comprising:

means operative simultaneously with the checking means for simultaneously accessing all locations of the checked level.

6. 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.

7. 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.

8. 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.

9. The apparatus of claim 6 further comprising:

means for simultaneously accessing all locations of a level associated with the desired word.

10. The apparatus of claim 6 further comprising:

means operative simultaneously with the checking means for simultaneously accessing all locations of the checked level.

11. 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.

12. The apparatus of claim 11 further comprising:

means for simultaneously accessing all locations of a level associated with the desired word.

13. The apparatus of claim 11 further comprising:

means operative simultaneously with the checking means for simultaneously accessing all locations of the checked level.

14. 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.

15. 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.

16. The apparatus of claim 14 further comprising:

means for accessing all locations of a level simultaneously.

17. The apparatus of claim 14 further comprising:

means operative simultaneously with the checking means for simultaneously accessing all locations of the checked level.

18. 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.

19. 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.

20. The apparatus of claim 18 further comprising:

means for simultaneously accessing all locations of a level associated with the desired word.

21. The apparatus of claim 18 further comprising:

means operative simultaneously with the checking means for simultaneously accessing all locations of the checked level.

22. 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.

23. The apparatus of claim 22 further comprising:

means for simultaneously accessing all locations of a level associated with the desired word.

24. The apparatus of claim 22 further comprising:

means operative simultaneously with the checking means for simultaneously accessing all locations of the checked level.