Patent Publication Number: US-5428565-A

Title: Single stage sensing apparatus for a content addressable memory

Description:
FIELD OF THE INVENTION 
     The present invention relates to an apparatus for determining a hit or miss when operating a lookup table of a content addressable or associative memory. 
     BACKGROUND OF THE INVENTION 
     As the processing speed of microprocessors (CPUs) increases associated apparatus such as memories must keep pace in order to avoid being performance bottlenecks in the microprocessor system. The present invention is directed to improving the effective bandwidth of content addressable or associative memories by improving the ability to detect and access a specific piece of data in a content addressable memory (CAM). One important class of CAMs, known as a cache memory, is a fast memory in the hierarchical memory structure that is most closely associated with the CPU. However, the present invention is directed to all CAM structures in diverse applications including use in associative processors. A common characteristic of all CAMs is that data is retrieved from memory locations based on their content. The CAM searches in parallel over all or part of its entire storage using a target content description and comparing it with a corresponding field of bits in each memory location. 
     Because of the importance of cache memories, most of the following description is couched in terms of cache memories, however, it will be recognized by those practicing the underlying art that the inventive principles expounded are more broadly applicable. 
     High performance, modern microprocessors (CPUs) typically include an on-chip cache memory in order to minimize instruction latencies. Cache memories are effective because of the temporal locality phenomenon of typical instructions that tends to reuse portions of code so that access to memory tends to slowly drift with the progress of the instruction program. Consequently, portions of memory currently being addressed are likely to be accessed again in the near term so that if a fast local memory (cache) is provided, on-chip repeated access to slower, off-chip main memory can be reduced. As the temporal locality shifts, new data from main memory is acquired by the on-chip cache. 
     Critical to the efficient operation of the cache memory is the speedy determination of whether the current information required by the CPU is resident in cache: if present (a cache &#34;hit&#34;) access can then be made to cache, and if not (a cache &#34;miss&#34;) access must be made to the slower main memory. 
     Main memory consists of a large set of lines with consecutive addresses. Cache memory holds many lines (e.g. the Intel i486™ microprocessor cache memory is physically split into four 2-K blocks, each with 128 lines and 128 21-bit tags) but not necessarily in any particular order. When the CPU requires access to memory, the CPU first searches the cache to see if the desired data is present. Typically, the search is an associative process in which each line stored in cache has an address tag that indicates which lines of main memory are resident in cache. A comparison is made between the CPU provided tag and the tags associated with lines stored in cache. A match between the two indicates a &#34;hit&#34; while the lack of a match indicates a &#34;miss&#34;, requiring an access to main memory. The data line acquired from main memory is stored in cache by replacing a previously stored line based on a prescribed replacement policy such as replacing the least recently used (LRU) line. 
     Because of the need to perform a tag comparison each time that the cache is accessed, the speed with which the comparison can be done is critical in determining the effective bandwidth of the cache memory. 
     The word TAG is used hereafter to mean a field of bits representative of the content addressable portion of a line of data stored in CAM. 
     A line of data is used to mean a standard unit of data storage which may include one or more bytes or words. 
     SUMMARY OF THE INVENTION 
     According to the present invention, a single stage sensing apparatus for sensing of a hit or miss comparison is provided in order to increase the speed of comparison of a CPU provided TAG with the CAM TAGs. 
     One object is to provide a fast single stage TAG comparator and sensing apparatus for use in CAMs by means of a small signal sensing amplifier to predict the onset of a comparator output change from a first state to a second state by comparing the single stage comparator output with a reference voltage representative of the first state and amplifying the difference voltage. 
     Another object is to provide a fully associative CAM that uses single stage sensing. 
     Another object is to provide a direct mapped CAM that uses single stage sensing. 
     Another object is to provide a set associative CAM that uses single stage sensing. 
     Another object is to provide a sector mapped CAM that uses single stage sensing. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The present invention may be understood more fully from the detailed description given below and from the accompanying drawings of the preferred embodiments of the invention which, however, should not be taken to limit the invention to the specific embodiment but are for explanation and understanding only. 
     FIGS. 1(a) and 1(b) show two basic cache memory look-up table configurations. 
     FIGS. 2(a) and 2(b) show a one-bit TAG look-up table storage and comparator network, and the corresponding truth table. 
     FIGS. 3(a) and 3(b) show another one-bit TAG look-up table storage and comparator network and the corresponding truth table. 
     FIG. 4 shows a wired-OR multi-bit TAG storage and comparator network. 
     FIG. 5 shows circuit details of a one-bit TAG storage and comparator network. 
     FIG. 6 shows a prior art multi-stage multi-bit TAG look-up table storage and comparator network. 
     FIG. 7 shows a single-stage multi-bit TAG look-up table storage and comparator network for use with a single TAG table entry. 
     FIG. 8 is a graphical representation of the miss/hit detection method used in the single stage comparator. 
     FIG. 9 is a block diagram of a complete TAG look-up table for a direct mapped cache using single stage detection and multiplexed small signal sense amplifier. 
     FIGS. 10(a) and 10(b) show a small signal sense amplifier circuit and the corresponding symbolic schematic. 
     FIGS. 11(a) and 11(b) show a schematic for pre-charging the detection circuit to V CC  and the associated HIT/MISS waveform. 
     FIGS. 12(a) and 12(b) show a schematic for pre-charging the detection circuit to V CC  /2 and the associated HIT/MISS waveform. 
     FIG. 13 is a block diagram of a fully associative CAM using a single stage sensing directory with fully decoded SRAM line control. 
     FIG. 14 is a block diagram of a direct mapped CAM using a multiplexed single stage sensing directory. 
     FIG. 15 is a set associative CAM with a TAG directory using single stage sensing techniques. 
     FIG. 16 is an M-sector mapped CAM with a single stage sensing directory. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENT(S) 
     A single stage sensing apparatus for a look-up table associated with a cache memory is described. The preferred embodiment is shown using specific hardware circuitry as well as block diagrams representing circuitry that is well known in the art in order to more clearly convey the essence of the invention by avoiding unnecessary details. It should be recognized, however, that the specific implementation shown is by way of example and as such does not imply any limitation on the spirit and scope of the invention. 
     Content addressable memories (CAMs), also known as associative memories are random access memories (RAMs) that, in addition to having a conventional addressing means also have logic means for simultaneously comparing a set of bits for all stored lines of data in memory during a single memory cycle. This allows accessing of data without the use of a location address because a portion of the line contents may be used to identify and access the desired line. The most popular form of CAMs are the cache memories. 
     Cache memories are part of a hierarchical memory organization wherein the cache is the smaller and faster memory placed in close association with the central processing unit (CPU) while slower main memory used for bulk storage is more removed. The basic unit of information that moves between main memory and cache is called a &#34;line&#34;. Therefore, main memory consists of a large set of lines with consecutive addresses. 
     Cache memory contains a subset of lines, each line being a copy of a main memory line but not necessarily stored in any particular order. Search of cache is usually &#34;associative&#34;. That is, each line or set of lines has an associated address &#34;TAG&#34; that indicates which lines of main memory these lines represent. The lines are usually compared simultaneously with the CPU provided line address TAG. A match indicates a &#34;hit&#34;. A non-hit or &#34;miss&#34; indicates that main memory must be accessed because the required data is not resident in cache. The CPU supplied address goes through an address map to strip-out the TAG and to determine which line or set of lines are to be searched. Cache memories are also known as content addressable memories (CAMs). 
     Cache memories may be classified according to the type of memory mapping used, as follows: 
     (1) a fully associative cache may have any line in main memory stored in any cache line and uses one TAG comparator per line providing a fully decoded cache memory set of line select lines; 
     (2) a direct mapped cache is arranged so that each cache line contains one line of a specific main memory subset of non-overlapping subsets in which a line is identified by a SET field designating the main memory subset and a TAG field designating the particular line within the subset; 
     (3) a set associative cache is a combination of fully associative and direct mapped organizations in which disjoint sets of lines are directly mapped to a line using a SET field to identify the line address and a fully associative search is done over the set of lines using a TAG field; and 
     (4) a sector mapped cache uses a TAG field to identify a particular set of contiguous addresses (a sector) of main memory while a SET field is used to designate a line within the sector. 
     FIGS. 1(a) and 1(b) show two examples of cache look-up table implementations that may be used. FIG. 1(a) shows a look-up table configuration for a cache directory that may be used for either a fully associative cache, the fully associative portion of a set associative cache, or for the associative look-up of a sector in a sector mapped cache. It is a fast method because all lines are compared in parallel. 
     The accessing CPU supplies a cache address word 18 in which the high order bit field TAG 11 contains the TAG information while the lower order field 19 contains address data specifying word and/or byte locations. TAG table 12 contains N TAG entries which are compared with TAG field 11 in the set of N comparators 15, with one comparator per TAG entry. The output of comparator set 15 is a set of N binary lines with one state representing a hit between the corresponding TAG entry of table 12 and TAG field 11, and the other state indicating a miss. 
     In the case of a fully associative cache having N lines of data, the N output lines of comparator set 15 constitute a fully decoded set of memory addressing lines that access the cache memory line corresponding to a hit. 
     In the case of a set associative cache, the structure shown in FIG. 1(a) may be used to implement the fully associative portion of the cache directory in which TAG field 11 identifies the particular set of a line selected by SET field 17 of CPU cache address 18. Speed of access is enhanced by the parallel comparisons in comparison set 15 and the fully decoded hit/miss output lines. 
     In the case of a sector mapped cache, the structure of FIG. 1(a) may be used as a means for selecting a particular sector from the set of sectors resident in cache using the fully decoded set of output lines from comparator set 15 while the SET field 17 is used to select a particular line of the sector selected by a hit-active output line of comparator set 15. 
     FIG. 1(b) shows a direct mapped cache memory in which SET field 17 of CPU cache address word 18 is used to identify a line index corresponding to a specific main memory subset and TAG field 11 designates the line index within the specified main memory subset. In this case, a single TAG comparator 14 is used to determine if the TAG specified line is resident at the location specified by SET field 17. If it is, a hit results at the output of comparator 14 and data is read out of the line in random access memory (RAM) 13 corresponding to line index specified by SET field 17. 
     A key element of the CAMs is the comparator. The speed and efficiency of the comparator, other than the RAM cycle time, controls the effective bandwidth of the CAM. 
     A simple one bit content addressable memory (CAM) storage and comparator cell is shown in FIG. 2(a). Flip-flop (FF) 21 represents a single bit storage cell for storing a TAG bit (A k ) of a TAG directory entry which is compared with a corresponding bit (B k ) of target TAG field 11 presented on line 22 and inverter 24 forms the logical compliment, B k . Logic circuit 23 forms the exclusive-OR (EXOR) of the bits as follows: 
     
         EXOR(A.sub.k,B.sub.k)=A.sub.k ⊕B.sub.k =A.sub.k ·B.sub.k +A.sub.k ·B.sub.k 
    
     where (+)indicates a Boolean OR operation and (·) indicates a Boolean AND operation. The truth table for EXOR(A k ,B k ) shown in FIG. 2(b) indicates that the output state of logic circuit 23 is high if A k  ≠B k , corresponding to a MISS. A MISS for any bit pair of the TAG is a miss for the entire TAG comparison. Hence it is sufficient to logically OR all one-bit CAM comparator outputs (one for each TAG bit) to determine if the comparison is a HIT or MISS. Alternatively, the complement of EXOR may be used to combine the one-bit comparisons of the directory TAG bits, {A k  }, with the target TAG bits, {B k  }. 
     The exclusive-NOR (EXNOR) operation may be expressed as 
     
         EXNOR(A.sub.k,B.sub.k)=A.sub.k ⊕B.sub.k =A.sub.k ·B.sub.k +A.sub.k ·B.sub.k 
    
     and its implementation is shown in FIG. 3(a) and the corresponding truth table is shown in FIG. 3(b). In this case, if A k  ≠B k , the output is low. 
     FIG. 4 shows a wired-OR configuration for a multi-bit TAG directory TAG word storage and comparator network. A multiplicity of one-bit CAM comparator cells 30 are wired-OR connected to a common HIT/MISS line 27&#39;. Each one-bit CAM comparator cell 30 contains a flip-flop 21 for storing one TAG bit, A k , and an input line 22 for accepting the corresponding bit, B k , from the cache address TAG field. AND-gates 25 and 26 form the Boolean terms A k  ·B k , and A k  ·B k , respectively. HIT/MISS line 27&#39; performs to logical OR-ing to form the Boolean term (A k  ·B k  +A k  ·B k ) which corresponds to the EXNOR term A k  ⊕B k . Thus, if the TAG field bits, B 0  B 1  . . . B N-1  do not identically match the corresponding TAG bits in the TAG table directory addressed by SET, line 27&#39; is pulled low, indicating a MISS, in accordance with the truth table given in FIG. 3(b). Conversely, if all corresponding bits match, line 27&#39; remains high indicating a HIT. 
     FIG. 5 shows a circuit for a preferred embodiment of a one-bit CAM storage and comparison cell 30&#39; used in TAG directory 12. Flip-flop 21 is used to store bit A k  using cross-coupled inverters. Writing to flip-flop 21 is accomplished by activating word-line 31, thereby causing transistors 32 and 33 to connect flip-flop 21 to bit-lines 22 and 22&#39;. The desired state of the bit to be stored is applied to bit-line 22 and its complement to bit-line 22&#39;. In this manner, flip-flop 21 is forced into the desired state. Deactivating word-line 31 leaves the flip-flop in a state representative of the bit applied to bit lines 22 and 22&#39;. 
     When a TAG comparison is to be made, the appropriate bit, B k , from the cache address word, TAG-field 11, is applied to bit-line 22 and its complement, B k , to line 22&#39;. The state of A k  in flip-flop 21 and B k  on line 22 is applied to AND-gate 25 comprising series connected transistors 34 and 35. The series connected transistors forms an AND-gate so that if A k  ·B k  is true, HIT/MISS line 27&#39; is pulled low indicating a MISS (A k  ≠B k ), and if A k  ·B k  is false, the series connected transistors form an open circuit indicating a HIT and leaving MISS/HIT LINE 27&#39; unaffected. 
     Similarly, bits A k  and B k  are applied to AND-gate 26 comprising series connected transistors 36 and 37 so that if A k  ·B k  is true, MISS/HIT line 27&#39; is pulled low, also indicating a MISS because A k  ≠B k . In this manner, the state of MISS/HIT line 27&#39; corresponds to the exclusive-NOR of bit A k  and B k , (A k  ⊕B k ). 
     The circuit of FIG. 5 may be used to form a multi-bit TAG comparator unit similar to that shown in FIG. 4, by commonly connecting MISS/HIT LINE 27&#39; of individual one-bit CAM cells 30&#39;. However, when the TAG has a large number of bits requiring the cascading of many one-bit CAM comparator 30 cells, heavy capacitive loading of the commonly connected MISS/HIT line 27&#39; may result, causing the response-time of line 27&#39; to significantly increase. 
     The prior art approach to minimizing the slow-down due to capacitive loading of MISS/HIT line 27&#39; involves breaking-up the TAG bits into subgroups in order to keep the capacitive loading on the subgroup MISS/HIT line 27&#39; at a tolerable level, buffering and detecting the state of each subgroup&#39;s MISS/HIT line 27&#39;, and then logically combining the HIT/MISS line 27&#39;, and state of each subgroup to obtain a complete HIT/MISS decision for the entire TAG field. This technique, known as a multiple-stage domino method, may be implemented as shown in FIG. 6, for example. 
     In the example of FIG. 6, the TAG field is broken-up into 4-bit subgroups 40, each subgroup comprising 4 one-bit CAM comparison units 30&#39;, each sharing a common MISS/HIT line 27&#39;, and a stage-1 domino network 41 that buffers MISS/HIT line 27&#39; and outputs the MISS/HIT line state on line 42. 
     Each of the stage 1 domino network 41 outputs for a number of subgroup 40 units are combined into a second level by means of stage-2 domino circuit 43. The number of subgroups accommodated is determined by the fan-in capability of the particular stage-2 domino circuit. The buffered output of stage-2 domino circuit 43 represents the Boolean AND of all the inputs received from the associated subgroup 40 units. 
     Additional hierarchical domino levels may be accommodated by providing stage-3 domino circuit 44 to combine a number of additional stage-2 domino circuits and, possibly, a stage-4 domino circuit 45 for combining additional stage-3 domino circuits. 
     The number of hierarchical levels are determined by the fan-in capabilities of the various domino circuits to ensure acceptable speed of response for determining the state of the MISS/HIT indicator. However, as the size of the cache look-up table increases, the number of TAG-bits increase, and the number of domino circuit hierarchical levels increase causing a larger response time for each TAG MISS/HIT decision. A concomitant penalty of the multi-stage domino method is the larger on-chip area required to implement the cache table directory. 
     The disadvantages of the prior art multi-stage domino method may be overcome by using a single stage look-up table TAG comparator circuit 60, as shown in FIG. 7. 
     Unit 50 of FIG. 7 is a group of CAM comparison cells 30&#39;, all sharing a common MISS/HIT line 27&#39;. Each CAM unit 30&#39; is implemented as shown in FIG. 5. The output of unit 50, MISS/HIT line 27&#39;, is connected to small signal sense amplifier 52 where it is compared (differenced) with a stable precision reference voltage applied to line 51. Small signal sense amplifier 52 is a high gain differential amplifier and thresholding device that amplifies small differences between the MISS/HIT line voltage and the reference voltage which, when applied to the threshold device produces a two-state output signal indicative of the state of MISS/HIT line 27&#39;. 
     FIG. 8 shows how the increase in speed of detection is achieved by the single stage look-up table TAG comparator of FIG. 7. The reference voltage, V R , represents the high logic level. V H  and V L  represent the high logic state and low logic state thresholds, respectively so that all voltage levels above V H  are classified as high-state and those below V L  are classified as low-state signals. Signals with levels between V L  and V H  are indeterminate. The voltage level of MISS/HIT line 27&#39; is a dynamic signal that is subject to high-to-low state transitions whenever a MISS is detected in one of the CAM comparator 30&#39; units. In FIG. 8 such a transition is shown being initiated at time t 0 . The rate at which this signal decreases toward the low state threshold level is a function of the number of CAM comparison cells 30&#39; that share the common HIT/MISS line 27&#39;, the rate being slower as CAM cells 30&#39; are added. In the example shown, v 27&#39;  crosses the low logic state threshold at time t 2  so that the total time interval for detection is Δt 2  =t 2  -t 0  if normal logic level detection techniques are used. However, the use of small signal sense amplifier with its high internal differential gain permits the early detection of the onset of the high-to-low transition by amplifying the difference Δv=v R  -v 27&#39;  so that when the gain, K, of the differential amplifier is applied to Δv, a voltage level K·Δv results that exceeds the high logic level threshold, V H , at time t 1 , a time significantly earlier than time t 2 . The detection interval (Δt 1  =t 1  -t 0 ) is improved by a ratio of Δt 2  /Δt 1 . 
     In this manner, the number of CAM comparison cells 30&#39; that can be commonly OR-connected is significantly greater than the number of CAM comparison cells 30&#39; that can be included in a subgroup 40 of the prior art multiple-stage domino method shown in FIG. 6. 
     FIG. 9 shows a complete TAG look-up table based on the single stage detection principle, as described above. Each unit 50 constitutes a complete CAM detection circuit for a single TAG entry by having one CAM cell 30&#39; for each TAG bit. The complete TAG directory table 12 of FIG. 1 is made up of one unit 50 for each TAG entry. The output MISS/HIT line 27&#39; of each unit 50 is connected to an input of MUX (selector) 53 which is controlled by the SET bit-field of the cache-line address word so that the proper unit 50 is selected as the CAM searches through TAG directory 12. 
     Because the time for determining a miss has been substantially reduced by using the single stage detection principle, the search through the look-up table can be made at a higher rate and thus significantly improve the effective bandwidth of a CAM. 
     FIG. 10(a) shows an implementation of small signal sense amplifier 52 in the form of a long-tail transistor pair (91 and 92) differential amplifier used to compare the signal on MISS/HIT line 27&#39; with V REF  on input line 51. Transistor 93 is the long-tail pair current source, controlled by the ENABLE signal on input line 97. Control signal, ENABLE, also controls the state of p-channel transistor switch 96 that connects the source terminals of transistors 91 and 92 when ENABLE is false (low), equalizing the voltages of the sources of transistors 91 and 92. P-channel transistors 94 and 95 act as active loads for transistors 91 and 92, respectively. The HIT output terminal 61 is connected through an inverting buffer to the source of transistor 91 while the MISS output is connected to through an inverting buffer to the source of transistor 92. When ENABLE is set high, transistor 93 is turned-on while transistor 96 is turned-off, allowing the source voltage of transistors 91 and 92 to vary. If MISS/HIT line 27&#39; is high relative to V REF , transistor 91 increases its conductance, causing more current to flow through transistor 91 than through transistor 92. This, in turn, causes the drain voltage of transistor 92 to increase while the voltage on the drain of transistor 91 decreases. The cross-coupling of the drains of p-channel transistor 94 and 95 causes the voltage drop across transistor 94 to increase, thus decreasing the source voltage of transistor 91. The inverting buffer output on output HIT line 61 consequently goes high indicating a hit conductor while MISS terminal 61&#39; begins to swing low. Conversely, if a MISS condition is initiated on HIT/MISS line 27&#39;, the drain voltage of transistor 92 begins to swing low causing output MISS terminal 61&#39; to begin to swing high indicating the onset of MISS condition. Thus, the cross-coupling of transitions 94 and 95 provide regenerative feedback within the differential amplifier that aids in the early detection and thresholder of the state of the MISS/HIT line. 
     FIG. 10(b) shows a schematic symbol for small signal sense amplifier 52. 
     FIG. 11(a) is a schematic for a small signal sense amplifier circuit 52 including auxiliary apparatus for initializing the detection of a hit or miss. As in FIG. 10(a), MISS/HIT line 27&#39; from CAM comparator 30 units and V REF  from reference generator 110 are connected to the input data terminals of small signal sense amplifier 52. Reference generator 110 includes transistors 104 and 105 with the gate of transistor 104 connected to the ENABLE line 97. Transistor 105, with its gate connected to its source terminal, causes transistor 105 to behave like a zener diode constant current source. Thus, when ENABLE is low, transistor 104 is non-conducting causing a constant current from transistor 105 to flow to capacitor C, connected to the V REF  output line 51 of reference generator 110. If PRECHARGE# is set low, MISS/HIT line 27&#39; and V REF  line 51 are connected by the conducting state of transistor 103. Also, transistors 101 and 102 are also conducting causing lines 27&#39; and 51 to rise to V CC . If PRECHARGE# is set to high, and ENABLE is also set to high, MISS/HIT line 27&#39; and V REF  line 51 are made independent. Capacitor C begins to discharge through transistor 104, which is in a conducting state, causing the capacitor voltage to fall exponentially to V CC  /2, the voltage across transistor 104, as shown in FIG. 11(b). If the state of line 27&#39; indicates a HIT, it remains at V CC . However, if line 27&#39; begins to drop from V CC  indicating an onset of a MISS. the voltage drops towards V SS  as indicated by the dotted-line labeled MISS. Capacitor C is chosen so that its discharge path time-constant causes it to approach V CC  /2 at twice the rate that line 27&#39; is approaching V SS , in the worst case condition when only one bit is a miss. Small signal sense amplifier 52 is able to distinguish between a hit condition causing a differential voltage of V at time t 1  after the start of the comparison. Similarly, if a MISS is initiated on line 27&#39;, a differential of at least V will be sensed at time t 1  indicating a MISS. 
     Another circuit arrangement for performing the early onset of a HIT or MISS is shown in FIGS. 12(a) and 12(b). In this case, reference generator 112 produces a stable output voltage of V CC  /2 on line 51 which is compared with the voltage level on line 27&#39; by small signal sense amplifier 52. Solid state switch 107 is a transfer gate switch that is controlled by EQUAL line 108. It connects lines 27&#39; and 51 in order to initialize the charge so that each line is at V CC  /2, as shown in FIG. 12(b) during the time interval before t 0 . At time T 0 , COMPARE line 109 is raised high causing transistor 106 to stop conducting and the comparison begins. If HIT/MISS line 27&#39; represents a HIT, the voltage will begin rising towards V CC  while V REF  remains at V CC  /2. Conversely, the onset of a MISS will cause line 27&#39; to fall towards V SS  as indicated by the dotted-line labeled MISS. At a pre-set time interval, corresponding to time t 1 . ENABLE is switched to high on line 97. The worst case MISS condition will produce a change of at least ΔV for a MISS and also a change of ΔV for a HIT, enabling small signal sense amplifier to make an early detection of the comparison result. 
     A fully associative CAM with a faster response time, but with greater complexity that results in greater chip area use, can be structured as shown in FIG. 13. Unit 62 is a CAM TAG directory made up of individual single stage look-up table TAG comparator circuits 60, each with output lines 61. Each output line 61 functions as a fully decoded line access control line for selecting access to a corresponding line of SRAM 13&#39; that shows a hit. 
     FIG. 14 shows a direct mapped CAM employing a multiplexed input small signal sense amplifier 52 as shown in FIG. 9 in which the table address used to control selector 53 is also used as a line address for SRAM 13. The output of small signal sense amplifier 52 is used to enable access when its output indicates a hit. 
     FIG. 15 shows a set associative CAM used as a cache memory with M-ways. The CPU provided cache address word 18 contains a TAG field 11, SET field 17, and word and/or byte address field 19. The target TAG of TAG field 11 is applied to M-way TAG directory 80, more specifically to each of the M TAG tables 82. Each TAG table 82 is made up of N single stage TAG comparator circuits 60. Access to a specific line of TAG comparators 60 is made by the line address specified by SET field 17. Thus, a line of TAG comparator corresponds to a TAG subdirectory similar to the TAG directory 62 of the fully associative CAM of FIG. 13. The set of output lines 61 constitute a fully decoded set of control lines for controlling way selector 86. Cache RAM 81 comprises M-ways with N lines of data each, the content of each line addressed by SET field 17 sot hat corresponding lines of RAM 81 and TAG directory 80 are simultaneously selected. The contents of the selected line (line k in this example)is made available on output lines 87 to the input of way selector 86. Line k of a particular RAM way 83 is shown for output by way selector 86 by the fully decoded output lines 61 of TAG directory 80. The active line corresponding to a hit selects the corresponding way 83 of RAM 81. 
     FIG. 16 shows a sector mapped CAM used as a sector mapped cache comprising a TAG directory 62, a RAM 84 organized with M sectors (0, 1, . . . , M-1) of N lines each. TAG field 11 of CPU cache address word 18 contains the target TAG that is applied to TAG directory 62 comprised of single stage TAG comparators 60 each with an output line 61. If a TAG hit is made, the corresponding output line 61 is activated and selects its corresponding sector of RAM 84. SET field 17 of CPU address word 18 then selects one-of-N lines in the selected sector for outputting.