Patent Publication Number: US-6707752-B2

Title: Tag design for cache access with redundant-form address

Description:
FIELD OF THE INVENTION 
     The invention relates to field of memories particularly those using redundant-form addresses. 
     PRIOR ART AND RELATED ART 
     The latency of on-chip caching has become more and more important to the overall performance of microprocessors. To speed up cache access, a redundant-form addressing system is known which permits cache access before the final complete address becomes available. In general, the ordinary binary address is replaced with a more complex address (redundant-form). In effect, address components from an adder are used since these are more quickly available. For instance, these components are not delayed by the carry chain needed to complete the ordinary address. Aspects of this technology are described in PCT Application WO 99/64953; co-pending application Ser. No. 09/532,411 entitled “Shared Cache Word Line Decoder For Redundant And Regular Addresses” filed Mar. 22, 2000; and application Ser. No. 09/538,553 entitled “Cache Column Multiplexing Using Redundant Form Addresses” filed Mar. 29, 2000. 
     One problem associated with using redundant-form addresses is that it is costly to do redundant-form tag compares. Substantial additional circuitry is required to handle the redundant-form tag comparison. 
     As will be seen, the present invention solves this problem. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram illustrating an embodiment of the present invention. 
     FIG. 2 is a flow diagram illustrating the steps of one embodiment of the present invention. 
     FIG. 3 is a timing diagram used in conjunction with the block diagram of FIG.  1 . 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     A memory is described particularly useful for caching where redundant-form addresses are used. In the following description, embodiments of the invention are described for a cache memory having a particular architecture. It will be apparent to one skilled in the art that the invention may be practiced without these specific embodiments. In other instances, well-known circuits, such as comparators, have not been shown in detail in order not to obscure the present invention. 
     Overview of One Embodiment 
     The memory array (which includes at least the tag fields and associated data for one embodiment) is first divided into odd and even entries (sometimes also referred herein to as subarrays). A redundant-form address is used by decoders to select a line in both the even and odd subarrays. Also a small differential voltage is developed at the bit lines in the arrays. While this is occurring, the least significant bit (LSB) for the ordinary (non redundant-form address) is generated along with the final (non redundant) address bits. The LSB is used to enable the sense amplifiers associated with one of the odd or even subarrays. The output of the sense amplifiers drive a common data bus, shared by both odd and even subarrays. The tag field of the data from the selected subarray is coupled to a ordinary (non redundant-form) comparator. This allows the tag to be accessed early with a redundant-form address. While the non redundant-form tag bits are being completed, the tag bit lines are activated and subsequently used for developing a hit/miss generation (way select). By doing this, the very costly redundant-form compare is avoided without incurring a speed penalty. Additionally, since only one set of sense amplifiers is selected during the redundant-form access, the sensing power is minimized. Moreover, the shared data buses between the subarrays provides metal trace reduction in the fabrication of an integrated circuit employing the disclosed memory. 
     Embodiment of FIG.  1   
     Referring to FIG. 1, the memory includes an even subarray shown as arrays  10   a  and  10   b  and an odd subarrays comprising arrays  11   a  and  11   b . These are ordinary static random-access memory (SRAM) arrays such as are often found in a cache memory. Arrays  10   a  and  10   b  are associated with the sense amplifiers  12 . A tag field from array  10   a  or  10   b  may be sensed by the amplifiers  12  and coupled to the comparators  25  on data bus  26 . Similarly, the arrays  11   a  and  11   b  are associated with the sense amplifiers  13 . When lines are selected in these arrays, they are sensed by the sense amplifiers  13  with a tag field being coupled to the comparator  25  on data bus  26 . It should be noted that the data bus  26  is common to both subarrays; however, as will be seen, only one set of sense amplifiers  12  or  13  are activated at any one time. 
     Decoders  15  are redundant-form address decoders which receive the redundant-form address on lines  16  and which select a line or lines in both of the subarrays. These decoders are described in more detail in the references cited in the “Prior Art And Related Art” section of this application. 
     The ordinary tag position of the address (that is the non redundant-form address) is coupled on lines  17  to the comparator  25 . Within the comparator  25 , this address is compared with the stored tag to provide a hit or miss indication on line  28  as is typically done. The comparators, as mentioned previously, are ordinary non redundant-form comparators, and operate on the ordinary address on lines  17  and a tag from the arrays. 
     Most typically, the hit/miss signal is coupled to a data array for selecting the data. For instance, in a four-way associative cache, one of four lines of data may be selected. 
     The LSB of the ordinary address is coupled to the AND gate  21  and also through inverter  20  to the AND gate  22 . A sense amplifier enable signal (SAE) on line  19  is also coupled to the gates  21  and  22 . If the LSB is even (a binary 1), the sense amplifiers  12  are selected when SAE is active. On the other hand, if the LSB is odd, the sense amplifiers  13  are selected through the output of the gate  22  when the SAE is active. 
     As shown in FIG. 3, at time  30 , assume that a redundant-form address is coupled to the decoders  15 . The redundant-form address is decoded during time  31 . This causes at lease one line to be selected in each of the subarrays  10  and  11 , that is the word lines in both subarrays are turned on. Additionally, in one embodiment, a small differential voltage is developed at the bit lines in the arrays. 
     At time  32 , the LSB of the ordinary address will have been determined. This bit and its complement are coupled to the gates  21  and  22 , respectively. As mentioned, if the LSB is even, then the amplifiers  12  are selected whereas if it is odd, the amplifiers  13  are selected. During time  33 , the sense amplifiers can sense the tag field being coupled to the comparator  25  from the selected subarray. At time  34 , the ordinary address will become available and is coupled to the comparator  25  on line  17 . At time  35 , the comparison will have been completed and a hit or miss signal will be provided on the line  28  allowing, for instance, the selection of data from the data array. 
     Method of the Present Invention 
     Referring now to FIG. 2, the method of the present invention is shown beginning with step  100  where the decoding of the redundant-form memory address occurs. This decoded address is used as mentioned to select one or more lines in the each of the subarrays as shown by step  101 . 
     Now as show by step  102 , selected lines from only one of the subarrays is selected based on the redundant-form address, for instance, based on the LSB of the ordinary address signal. 
     The tag field selected by step  102  is then compared with the bits of the non redundant-form address to provide a hit or miss signal as indicated by step  103 . 
     In the above description, the array was divided into odd and even subarrays, and the least significant bit was used to select between these arrays. In another embodiment, it is possible to use the two least significant bits, or for that matter, any number of least significant bits, and to divide the array for instance, into four subarrays and to select between the four subarrays using the two least significant bits. Also in the above description, it was assumed that the tag field and related data were read from the array at the same time. It is also possible to first compare the tag field with the non redundant-form address and then, for instance, read data based on the status of a hit/miss signal. Other alternate embodiments will be apparent to one skilled in the art. 
     Thus, a cache memory implying redundant-form addresses and non redundant-form addresses where the compare function has been described.