Hit/miss logic for a cache memory

• US 4,363,095 A
• Filed: 12/31/1980
• Issued: 12/07/1982
• Est. Priority Date: 12/31/1980
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Honeywell Information Systems, Inc. (Honeywell International Inc.)
• Inventors: Peters, Arthur, Woods, William E.
• Primary Examiner(s): Springborn, Harvey E.
• Application Number:
  US06/221,851
• Time in Patent Office: 706 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 711/206
• CPC Class Codes: G06F 12/0851 Cache with interleaved addressing

Abstract

In a data processing system a cache memory comprises level one and level two even and odd data stores and level one and level two even and odd directory stores. The directory stores include a plurality of storage locations for storing the most significant bits of the address numbers associated with the data words stored in the level one and level two even and odd data stores. The level one and level two even and odd directory stores are addressed by the least significant bits of the address numbers. Comparator circuits compare the high order bits of an address number supplied in a memory request to the high order bits stored in the level one even and odd directory stores at storage locations identified by both the low order bits of the address supplied in the memory request and the low order address bits incremented by one. A hit detector circuit determines whether one, both, or none of the requested words are stored in the cache memory by analyzing the outputs of the comparators.

Claims

1. In a data processing system including a system memory for addressably storing a plurality of data words identified by a like plurality of associated odd and even address numbers, each address number including a first portion and a second portion, and wherein system elements generate requests for the transfer of a pair of data words identified by successive address numbers, a transfer request including a memory request address number identifying the first of the pair of data words requested, a cache memory for selectively storing a subset of the data words stored in the system memory and for supplying the requested data words in the place of the system memory if the requested data words are stored in the cache memory, the cache memory comprising:

memory means for storing said subset of said data words stored in said system memory, said memory means including an odd memory module for storing said data words identified by said odd address numbers and an even memory module for separately storing said data words identified by said even address numbers;

an odd directory memory for storing said address numbers identifying said data words stored in said odd memory modules;

an even directory memory for storing said address numbers identifying said data words stored in said even memory modules;

means for receiving each of said address numbers supplied by said system elements and for determining if said received memory request address number and the next successive address number are stored in said odd or even directory memories; and

hit detector circuit means coupled to said receiving and determining means for generating a full hit signal if both said supplied memory request address number and said next successive address number are determined to be stored in said odd and even directory memories, a partial hit signal if only one of said supplied memory request address number and said next successive address number are determined to be stored in said odd and even directory memories, and a no hit signal if neither said supplied memory request address number nor said next successive address numer are determined to be stored in said odd and even directory memories.

2. A cache memory according to claim 1 wherein said odd memory module comprises a first odd data random access memory for storing data words associated with said odd address numbers in a plurality of first odd storage locations, each said first odd storage location being addressable by said first portion of said address number associated with said data word stored therein, and a second odd data random access memory for storing data words associated with said odd address numbers in a plurality of second odd storage locations, each said second odd storage location being addressable by said first portion of said address number associated with said data word stored therein, each said first odd storage location being associated with a different one of said second odd storage location, each said associated first and second odd storage locations being further associated with a plurality of odd system address numbers having identical said first portions.

3. A cache memory according to claim 2 wherein said even memory module comprises a first even data random access memory for storing data words associated with said even address numbers in a plurality of first even storage locations, each said first even storage location being addressable by said first portion of said address number associated with said data word stored therein, and a second even data random access memory for storing data words associated with said even address numbers in a plurality of second even storage locations, each said second even storage location being addressable by said first portion of said address number associated with said data word stored therein, each said first even storage location being associated with a different one of said second even storage locations, each said associated first and second even storage locations being further associated with a plurality of even system address numbers having identical said first portions.

4. A cache memory according to claim 3 wherein said odd directory memory comprises a first odd directory random access memory for storing said second portions of said address numbers associated with said data words stored in said first odd data random access memory in a plurality of first odd directory storage locations, each said first odd directory storage location being addressable by said first portion of a said address associated with said second address portions stored therein, and a second odd directory random access memory for storing said second portions of said address numbers associated with said data words stored in said second odd data random access memory in a plurality of second odd directory storage locations, each said second odd directory storage location being addressable by said first portion of a said address associated with said second address portion stored therein, each said first odd directory storage location being associated with a different one of said second odd directory storage locations, each said associated first and second odd directory storage locations being further associated with a plurality of said odd system address numbers having identical first address portions.

5. A cache memory according to claim 4 wherein said even directory memory comprises a first even directory random access memory for storing said second portions of said address numbers associated with said data words stored in said first even data random access memory in a plurality of first even directory storage locations, each said first even directory storage location being addressable by a said first portion of a said address associated with said second address portion stored therein, and a second even directory random access memory for storing said second portions of said address numbers associated with said data words stored in said second even data random access memory in a plurality of second even directory storage locations, each said second even directory storage location being addressable by a said first portion of a said address associated with said second address portion stored therein, each said second even directory storage location being associated with a different one of said second even directory storage locations, each said associated first and second even directory storage locations being further associated with a plurality of said even system address numbers having identical first address portions.

6. A cache memory according to claim 5 wherein said receiving and determining means comprises:

an odd address driver circuit means for addressing said first odd directory random access memory and said second odd directory random access memory with said first address portion of said memory request address number to cause said first odd directory random access memory and said second odd directory random memory to output said second address portions stored in said first and second odd directory storage locations addressed by said second address portion of said memory request address number; and

comparator means for first comparing said second address portion outputted by said first odd directory random access memory to said second address portion of said memory request address number and for generating a level one odd hit signal having a first value if said first compared address portions are equal and a second value if said first compared address portions are unequal and for secondly comparing said second address portion outputted by said second odd directory random access memory to said second address portion of said memory request address number and for generating a level two odd hit signal having said first value if said secondly compared address portions are equal and said second value if said secondly compared address portions are unequal.

7. A cache memory according to claim 6 wherein said receiving and determining means further comprise:

an even address driver circuit means for addressing said first even directory random access memory and said second even directory random access memory with said first address portion of said memory request address number to cause said first even directory random access memory and said second even directory random access memory to output said second address portions stored in said first and second even directory storage locations addressed by said first address portion of said memory request address number; and

comparator means for first comparing said second address portion outputted by said first even directory random access memory to said second address porton of said memory request address number and for generating a level one even hit signal having said first value if said first compared second address portions are equal and said second value if said first compared second address portions are unequal and for secondly comparing said second address portion outputted by said second even directory random access memory to said second address portion of said memory request address number and for generating a level two even hit signal having said first value if said secondly compared second address portions are equal and said second value if said secondly compared second address portions are unequal.

8. A cache memory according to claim 7 wherein said hit detector circuit means comprises a first signal selector circuit for receiving said level one and level two odd hit signals and said level one and level two even hit signals and for generating a left hit signal having said first value if (1) said memory request address number is odd and either said level one odd hit signal or said level two odd hit signal has said first value, or (2) said memory request address number is even and either said level one even hit signal or said level two even hit signal has said first value.

9. A cache memory according to claim 8 wherein said hit detector circuit means further comprises a second signal selector circuit for receiving said level one and level two odd hit signals and said level one and level two even hit signals and for generating a right hit signal having said first value if (1) said memory request address number is odd and either said level one even hit signal or said level two even hit signal has said first value or (2) said memory request address number is even and either said level one odd hit signal or said level two odd hit signal has said first value.

10. A cache memory according to claim 9 wherein said hit detector circuit means further comprises a third signal selector circuit for generating a full hit signal having said first value if both said left hit signal and said right hit signal have said first value and said full hit signal having said second value if either one of said left hit signal or said right hit signal has said second value or if both said left hit signal and said right hit signal have said second value.

11. A cache memory according to claim 10 further including cache update logic means comprising:

an odd update random access memory having a plurality of odd update storage locations, each said odd update storage location being associated with one of said associated pairs of first and second odd directory storage locations and being addressed by said first address portion of a said memory request address number, each said odd update storage location selectively storing an odd module update signal having a first value to designate said associated first odd directory storage location as the one to be updated if a said data word identified by a said system memory address number associated with said pair of associated first and second odd directory storage locations is to be stored in said cache memory or a second value to designate said associated second odd directory storage location as the one to be updated if said data word identified by said system memory address number associated with said pair of associated first and second odd directory storage locations is to be stored in said cache memory.

12. A cache memory according to claim 11 wherein said cache update logic further includes:

an even update random access memory having a plurality of even update storage locations, each said even update storage location being associated with one of said associated pairs of first and second even directory storage locations and being addressed by said first address portion of a said memory request address number, each said even update storage location selectively storing an even module update signal having a first value to designate said associated first even directory storage location as the one to be updated if a said data word identified by a said system memory address number associated with said pair of associated first and second even directory storage locations is to be stored in said cache memory or a second value to designate said associated second even directory storage location as the one to be updated if a said data word identified by a said system memory address number associated with said pair of associated first and second even directory storage locations is to be stored in said cache memory.

13. In a data processing system including a system memory for addressably storing a plurality of data words identified by a like plurality of odd and even address numbers having a first address portion and a second address portion wherein system elements supply a memory request address number also having first and second address portions when requesting a transfer of a pair of data words identified by successive address numbers, a cache memory comprising:

memory means for storing a subset of said data words stored in said system memory, said memory means including a plurality of memory locations, each said memory location for storing a said data word identified by one of a different plurality of address numbers, said plurality of memory locations being separated into an odd memory module for addressably storing said data words identified by said odd address numbers and an even memory module for addressably storing said data words identified by said even address numbers;

a directory memory module for storing in a second plurality of memory locations singly associated with said first plurality of memory locations the second address portions of said address numbers identifying said data words stored in said associated first plurality of memory locations, said second plurality of memory locations being separated into an odd directory for addressably storing said second address portions of said associated odd address numbers and an even directory for addressably storing said second address portion of said associated even address numbers;

means for receiving said memory request address numbers supplied by said system elements and for incrementing each of said received memory request address numbers by one such that said received memory request address number and said incremented address number comprise a pair of successive address numbers including an odd address number and an even address number;

means for comparing said second address portion of said even address number of said pair of address numbers to said second address portions of said address numbers stored in said even directory to determine whether said data word identified by a said even address number of said pair of address numbers is stored in said even memory module, and for comparing said second address portion of said odd address number of said pair of address members to said second address portions of said address numbers stored in said odd directory to determine whether said data word identified by said odd address number of said pair of address numbers is stored in said odd memory module; and

hit detector circuit means coupled to said comparing means for generating a full hit signal if said comparing means determines that said data words identified by said pair of address numbers are both stored in said memory means, a partial hit signal if said comparing means determines that said data word identified by only one of said pair of address numbers is stored in said memory means, and a no hit signal if said comparing means determines that neither of said data words identified by said pair of address numbers is stored in said memory means.