Method and apparatus for accessing a cache memory utilization distingushing bit RAMs

A method for determining a location of a requested data element in a cache memory including the steps of:

• encoding a plurality of selected values each stored in a different one of a plurality of tag address sub-stores, each of the tag address sub-stores corresponding to one of a plurality of banks of the cache memory, the encoding step yielding a plurality of encoded selected values;
• calculating one or more bit number locations of differences between each of the plurality of encoded selected values, each of the bit number locations being unique;
• storing the one or more bit number locations in storage locations of a distinguishing bit RAM, the storage locations being addressable by an index portion of an address associated with the selected values stored in the plurality of tag address sub-stores;
• storing a portion of each of the plurality of encoded selected values, in the corresponding storage locations of the plurality of distinguishing bit RAMs, the portion identified by the one or more bit number locations;
• outputting the one or more bit number locations and the portions of the encoded selected values, from the distinguishing bit RAM in response to a cache index having a value equivalent to the index portion of the address associated with the selected values stored in the plurality of tag address sub-stores, the cache index being a portion of an address of a requested data element;
• encoding a tag portion of the address of the requested data element, in a manner that is functionally equivalent to a manner used in the first encoding step to encode the plurality of selected values stored in the tag address sub-store;
• selecting one or more sections of the encoded tag portion of the address of the requested data element that correspond to the bit number location output from the distinguishing bit RAM;
• and
• comparing each of the one or more selected sections of the tag portion of the address with a corresponding section of the plurality of tag address sub-stores and, upon determining an equivalency, selecting a corresponding bank of the cache memory.

A cache memory apparatus including a reduced size distinguishing bit RAM, comprising:

• a first memory having a plurality of locations for storing data, the first memory partitioned into a plurality of banks, each of the banks being addressable by a first index, the first index comprised of an index portion of a main memory address and a determination value;
• a bank determination logic including circuits for outputting the determination value in response to the index portion of the main memory address and in response to an encoded tag portion of the main memory address output from a first encoding logic coupled to the determination logic;
• a tag store, coupled to the determination logic to receive the first index and coupled to a tag portion of the main memory address, the tag store including a plurality of sub-stores corresponding to the plurality of banks of the first memory, each of the sub-stores having a plurality of locations related to the plurality of locations in the corresponding banks of the first memory;
• a bit number select logic for determining a difference value as between each value in the plurality of locations of the plurality of sub-stores such that the difference is determined between each of a first selected value in one of the plurality of locations of the plurality of sub-stores and a second value in a corresponding one of the plurality of locations of another of the plurality of sub-stores;
• a second encoding logic included in the bit number select logic for encoding the difference value, the second encoding logic encoding the difference value in a manner that is functionally equivalent to the first encoding logic.

A cache apparatus, comprising:

• a first memory having a plurality of locations for storing data, the first memory partitioned into a plurality of banks each of the banks being addressable by a predetermined one of a first plurality of indexes, each of the first plurality s of indexes comprised of an index portion of a main memory address and one of a plurality of determination values;
• a bank determination logic including circuits for outputting the plurality of determination values in response to the index portion of the main memory address and in response to a tag portion of the main memory address, the bank determination logic including:
• a pluralit of distinguishing bit RAMs each including a plurality of locations corresponding to the plurality of locations of a corresponding one of the substores wherein each location of each of the distinguishing bit RAMs stores one of the distinguishing bit numbers and one of a plurality of complement values each of the plurality of distinguishing bit RAMs including an output for outputting the distinguishing bit numbers and one of the complement values in response to a corresponding value of the index portion of the main memory address:
• a plurality of selection logics, each having a control input coupled to a corresponding one of the outputs of the plurality of distinguishing bit RAMs and each having a data input coupled to the tag portion of the main memory address, each selection logic for selecting a portion of the tag portion of the main memory address responsive to the output of the corresponding distinguishing bit RAM;
• a plurality of comparison logics, each coupled to a different one of the plurality of selection logics and to a different portion of the distinguishing bit RAM outputs for comparing the portion of the tag portion of the main memory address with the complement value to form the plurality of determination values;
• a tag store, coupled to the bank determination logic for receiving the first plurality of indexes and coupled to a tag portion of the main memory address, the tag store including a plurality of sub-stores each corresponding to one of the plurality of banks of the first memory, each of the sub-stores having a plurality of locations related to the plurality of locations in the corresponding bank of the first memory;
• a bit number select logic for determining a difference value between each value in each one of the plurality of locations of the plurality of sub-stores and each value in a corresponding one of the plurality of locations of another of the plurality of sub-stores, the bit number select logic further including a distinguishing bit selection logic for outputting a unique distinguishing bit number for each difference value determined.