JP4795740B2 - Semiconductor device - Google Patents

Description

  The present invention relates to a semiconductor device, and in particular, stores information of various bit lengths in a semiconductor device including a content addressable memory cell (CAM cell) that compares information stored in a memory cell with input information. Alternatively, the present invention relates to a technique that is effective when applied to a semiconductor device having a CAM cell array to be compared.

  With the development of information terminal equipment, the demand for voice recognition processing and image recognition processing is increasing. However, as the processing becomes more sophisticated, the computational load of pattern matching processing increases, and its speeding up is an issue. Yes. As a means for solving this problem in terms of hardware, attention has been paid to content addressable memory (CAM).

For example, Patent Document 1 describes a conceptual diagram of a configuration of a CAM device. As shown in FIG. 2, an m word × n bit CAM cell array, an I / O circuit that drives write data, read data, and search data, a decoder that decodes an address signal ADR and specifies a CAM word, and storage data And a priority encoder that encodes the address of the CAM word in which the search data match and outputs the highest priority hit address HHA according to the priority order.
Further, for example, Non-Patent Document 1 discloses a ternary content addressable memory that stores and compares three values of mask data “X” (don't care) in addition to data “0” and data “1”. A (TCAM) memory cell configuration is shown. In the memory cell shown in FIG. 3, storage node data called cell data 1 (cell data 1) and cell data 2 (cell data 2), search data (SD) and search data bar (SDB) are divided into 4 Comparison is performed using a comparison circuit including two NMOS transistors T1, T2, T3, and T4. Then, a signal corresponding to the comparison result is output to a match line.

  Here, in CAM, “entry” is usually used as a word corresponding to a word widely used in DRAM and SRAM. Since an entry is a word indicating data stored in each word, in this specification, stored data is referred to as an entry, and comparison data is referred to as a search key in accordance with the convention.

JP 2002-237190 A "IE Proceeding of 2003 CUSTOM INTEGRATED CIRCUITS CONFERENCE", September 2003, "Proceeding of 2003 Custom Integrated Circuits Conference, Digest of Technical Papers" p. 387-340

  Prior to the present application, the inventors of the present application examined data stored and compared by the CAM. In particular, when the characteristics of data to be processed for each CAM application destination were examined, the following two problems were found.

  The first problem is that the amount of information detected and detected from the natural world covers a wide range, and it is predicted that it is necessary to store these data efficiently. The TCAM can store or compare data having an arbitrary bit length by restricting a data area to be compared by using mask data as a search key. However, in the conventional TCAM, the configuration of the cell array is physically or logically fixed. For this reason, if the configuration is set in accordance with data having a large amount of information, the TCAM consumes memory wastefully, which may easily lead to depletion of memory capacity. In the case of a search system using TCAM, if it is attempted to secure a capacity using a plurality of TCAMs, the mounting cost may increase. In order to solve such a problem, it is desirable to have a cell array configuration with a variable bit length.

  The second problem is that, for example, the search operation for data in which the head position of the search key is not specified, such as streaming data or computer virus, is not good. There are two ways to solve this problem as described below. The first method is a method in which a plurality of data shifted by one bit is stored in advance. By this method, a plurality of comparison operations can be executed at a time without reducing the throughput. However, even in this case, there is a drawback that the memory capacity of the CAM is exhausted. The second method is a method in which a buffer is provided inside or outside the CAM chip or module, and a search key is input while being shifted bit by bit to perform a search. This method can avoid the above-mentioned memory capacity depletion problem, but conversely has a disadvantage that the throughput decreases because the search cycle increases.

  Therefore, in view of such problems and the like, an object of the present invention is to provide an advanced search system capable of flexibly storing and comparing various data while maintaining the memory capacity and search speed of a semiconductor device including a CAM. It is to be realized.

  The above and other objects and novel features of the present invention will be apparent from the description of this specification and the accompanying drawings.

  Of the inventions disclosed in the present application, the outline of typical ones will be briefly described as follows.

  A semiconductor device according to the present invention includes a CAM cell array, an entry attribute flag signal register, a latency control circuit group, and a priority determination circuit group. The entry attribute flag signal register is set to a value corresponding to the bit length of the entry. In addition, the latency control circuit group performs signal logical operation and latency addition according to the comparison result in each entry in accordance with the set value of the register. Further, the priority determination circuit group sequentially outputs the matching signal corresponding to the entry having a long bit length according to the set value of the register. With the above configuration and operation, the CAM according to the present invention stores entries of various bit lengths in one CAM cell array, compares them with a search key having a long bit length, and further supports entries with high similarity. It is possible to output sequentially from the coincidence signal.

  The semiconductor device according to the present invention includes a plurality of banks, and further includes a CAM cell array and a latency control circuit. Here, the banks are determined to have different bit lengths of entries that can be stored, and the banks are arranged so that row addresses (row addresses) are allocated to the entries in the bit length order. The latency control circuit has the same number of D flip-flops for each entry regardless of the bank. With the above configuration and operation, the CAM according to the present invention can search for entries having various bit lengths and simultaneously output a match signal. Further, since the position information of the entry indicates the similarity of the match signal, the priority determination operation for the match signal can be omitted, and the search operation cycle can be shortened.

  Furthermore, the semiconductor device according to the present invention comprises a CAM cell array and a search key register group. Here, the memory cell in the CAM cell array is composed of one memory element and a plurality of comparison circuits. The search key register group has a shift register function and generates a plurality of search keys. With the above configuration and operation, the CAM according to the present invention can generate a plurality of search keys from continuously input data such as streaming data, and simultaneously perform these search operations.

  The effects obtained by typical ones of the inventions disclosed in the present application will be briefly described to improve availability or expand functionality of a semiconductor device including a CAM.

  Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings. Note that components having the same function are denoted by the same reference symbols throughout the drawings for describing the embodiment, and the repetitive description thereof will be omitted. The circuit elements constituting each functional block of the embodiment are not particularly limited, but are formed on a semiconductor substrate such as single crystal silicon by a known integrated circuit technology such as a CMOS (complementary MOS transistor). .

  Note that, in the embodiment, a MOS (Metal Oxide Semiconductor) transistor is used as an example of a MISFET (Metal Insulator Semiconductor Field Effect Transistor). In the drawing, a P-channel MOS transistor (PMOS transistor) is distinguished from an N-channel MOS transistor (NMOS transistor) by adding an arrow symbol to the gate. Although the connection of the substrate potential of the MOS transistor is not particularly specified in the drawing, the connection method is not particularly limited as long as the MOS transistor can operate normally.

(Embodiment 1)
<< Overall configuration of CAM >>
First, the overall configuration of the CAM will be described. FIG. 4 is a block diagram showing a basic configuration example of a main block of a CAM included in the semiconductor device according to the first embodiment of the present invention. The CAM according to the present invention has the following three features. The first feature is that an entry having a long bit length is stored using a plurality of words. The second feature is that a search operation is performed after entries having different bit lengths are stored in advance in the same CAM cell array. The third feature is that the comparison result of the entry having the short bit length is temporarily held until the comparison of the entry having the long bit length is completed, and the matching result of the entry having the long bit length is preferentially output. . The CAM according to the present invention includes a CAM cell array CAMARY, a search line drive circuit group SDBK, a word driver group WDBK, a read / write circuit group RWBK, an entry attribute flag signal register group EAFRBK, a register read / write circuit group RRWBK, a match determination circuit group MDBK, and latency control. A circuit group LYBK, a priority determination circuit group PDCBK, and a priority encoder PE are included. In the figure, for the sake of simplicity, attention is paid to the path through which signals related to the search operation are transmitted and received, and the row decoder, which is an address-related circuit block, and the command decoder for specifying the operation mode are omitted. Yes.

  The CAM cell array CAMARY has a configuration in which, for example, a plurality of known memory cells as shown in FIG. 3 are arranged in a matrix of m words (rows) × n bits (columns). The CAM cell array CAMARY is connected to the word driver group WDBK via the word line group WLBS1, and is connected to the memory cell connected to one word line selected in the write operation from the read / write control circuit group RWBK to the bit line group BLBS. The data is written via Alternatively, in the read operation, the data stored in the memory cell is read from the bit line group BLBS via the read / write control circuit group RWBK. The CAM cell array CAMARY is connected to the search line drive circuit group SDBK via the search line group SLBS, and a search key is input in the search operation. Further, the CAM cell array CAMARY is connected to the match determination circuit group MDBK via the match line group MLBS, and a signal generated on the match line for each entry is discriminated in the match determination circuit group MDBK according to the comparison result.

  The entry attribute flag signal register group EAFRBK is composed of registers for storing information related to entries stored across a plurality of words. As will be described in detail later, similarly to the CAM cell array CAMARY, it is connected to the word driver group WDBK via the word line group WLBS2, and to the register read / write search circuit group RRWBK via the register bit group RBLBS. Value is set.

  The latency control circuit group LYBK adjusts the time until a comparison result is output to the hit line group HTBS2 in a search operation between a search key input in a time-sharing manner and entries of various lengths. It is a block. Although details will be described later, a match / mismatch signal for each word generated by the match determination circuit group MDBK is received via the hit line group HTBS1, and information stored in the entry attribute flag signal register group EAFRBK is further stored in the entry attribute flag. Receive via signal group EAFBS. Based on these signals, a signal corresponding to the comparison result is output to the hit line group HTBS2 for each entry, and further transmitted to the priority determination circuit group PDCBK. At the same time, a plurality of entry length flag signals are output to the priority determination circuit group PDCBK via the entry length flag signal group ELBS.

  FIG. 5 shows a configuration example corresponding to the word in the i-th row (i = 1, 2,..., M) for each of the CAM cell array CAMARY, the match determination circuit group MDBK, and the entry length control register group ELRBK shown in FIG. Is schematically shown. In the figure, for simplicity, attention is paid to signals related to the search operation, and word lines, bit lines, and the like are omitted.

  The CAM cell array element PWMEi (i = 1, 2,..., M) in the i-th row is composed of n memory cells MCij (j = 1, 2,..., N). Each memory cell receives the search key input via the corresponding search line SLj, SLBj (j = 1, 2,..., N), compares it with the stored entry, and shows the result as shown in FIG. Are output to the match line MLi which is a component of the match line group MLBS shown in FIG. Here, the search lines SLj and SLBj are components of the search line group SLBS.

  The match determination circuit element PWMEi (i = 1, 2,..., M) in the i-th row includes the match determination circuit MDi (i = 1, 2,..., M) and the latch LAi (i = 1, 2,..., M). ). The match determination circuit MDi discriminates a minute signal generated on the corresponding match line MLi, and outputs a signal voltage corresponding to the comparison result between the entry and the search key to the latch LAi. The latch LAi receives the comparison result according to the latch control signal φ1 and temporarily stores it.

The entry control register element PWREi (i = 1, 2,..., M) in the i-th row is composed of a plurality of registers. Here, it is assumed that the CAM cell array can store and search up to an entry having a bit length of 3n (that is, 3 word length), and is composed of two registers RGi1, RGi2 (i = 1, 2,..., M). An example to be shown is shown. The entry attribute flag signals EAFi1, EAFi2 (i = 1, 2,..., M) are components of the entry attribute flag signal group EAFBS shown in FIG. 4, and are set to voltages according to information stored in the registers RGi1, RGi2. Driven. When storing an entry of 1 word length in the i-th row, for example, as shown in FIG. 6, the logical values of the entry attribute flag signals EAFi2 and EAFi1 are set to “0” and “1”, respectively. Further, when storing an entry having a 2-word length from the i-th row to the (i + 1) -th row, for example, as shown in FIG. 7, the logical values of the entry attribute flag signals EAFi2 and EAFi1 in the first row are set to “1”. , “1”, the logical values of the entry attribute flag signals EAF (i + 1) 2 and EAF (i + 1) 1 in the second row are set to “1” and “0”, respectively. Further, when storing an entry of 3 word length from the i-th row to the (i + 2) -th row, as shown in FIG. 8, for example, the logical values of the entry attribute flag signals EAFi2 and EAFi1 in the first row are set to “1” , “1”, the logical values of the entry attribute flag signals EAF (i + 1) 2 and EAF (i + 1) 1 in the second row are “1” and “1”, the entry attribute flag signals in the third row, EAF (i + 2) 2 , EAF (i + 2) 1 logical values are set to “0” and “0”, respectively. Here, the logical value “1” is a high level such as the power supply voltage VDD, and the logical value “0” is a low level such as the ground voltage VSS. The CAM according to the present embodiment stores an entry wider than the bit width of the CAM cell array CAMARY while associating words using the above-described entry attribute flag signal, and matches generated for each entry during a search operation. The time required until the signal is output, that is, the latency is kept constant regardless of the entry length. Hereinafter, the configuration and operation of the latency control circuit group LYBK and the priority determination circuit group PDCBK specific to the CAM according to the present embodiment will be described in detail while paying attention to this point.
《Latency control circuit group》
FIG. 9 shows a configuration example of the latency control circuit element PWLYEi in the i-th row (i = 1, 2,..., M) for the latency control circuit group LYBK shown in FIG. This circuit element includes a multi-division entry combination circuit MEMMB, a latency control decoder LYDEC, a latency selection gate LYSG, and a latency adjustment circuit LYAJT. This circuit has the following two features. The first feature is that, using the multi-partition entry combination circuit MEMMB, a logical product operation is performed on the comparison result of entries stored across a plurality of rows, and a search result of an entry having a long bit length is generated. . The second feature is that the latency until the comparison result is output to the hit signal group HTBS2 is made constant regardless of the bit length of the entry by using the latency adjustment circuit LYAJT.

  The multi-divided entry coupling circuit MEMMB has a configuration in which a NAND circuit ND61 and an inverter circuit IV61 are cascade-connected. A signal corresponding to the result of the logical product operation of the hit lines HT1i and HTME (i-1) is generated on the hit line HTCMBi and output to the latency selection gate LYSG. Here, a voltage signal corresponding to the comparison result of the entries stored in the (i-1) th row is generated on the hit line HTME (i-1). However, the default logical value is “1”, as will be apparent from the description of the latency selection gate LYSG described later.

  The latency selection decoder LYDEC is a decoder for selecting a transfer path of signals generated on the hit lines HT1i and HTCMBi according to the value held by the entry control register element shown in FIG. 5, that is, the bit length of the entry. . In the figure, a configuration example of a 2-bit decoder using the entry attribute flag signals EAFi2 and EAFi1 as input signals corresponding to the configuration of the entry control register element shown in FIG. 5 is shown. Inverter circuits IV66 and IV67 output inversion signals EAFBi1 and EAFBi2 of entry attribute flag signals EAFi1 and EAFi2, respectively. From these signals, complementary entry length flag signals SWETi, SWEBi, DWETi, DWEBi, TWETi, TWEBi, METi, MEBi (i) using NAND circuits ND62, ND63, ND64, ND65 and inverter circuits IV62, IV63, IV64, IV65. = 1, 2,..., M) respectively. FIG. 10 is a truth table of the latency selection decoder LYDEC.

  The latency selection gate LYSG is a switching circuit that transfers signals generated on the hit lines HT1i and HTCMB1i to a latency adjustment circuit LYAJT, which will be described later, according to the output signal of the latency selection decoder LYDEC. In the figure, a configuration example of a circuit that leads to four transfer paths is shown corresponding to the configuration of the latency selection decoder LYDEC. In the first transfer path, the hit line HT1i is connected to the hit line HT11i through the CMOS transmission gate CTG61 to which the entry length flag signals SWETi and SWEBi are respectively input to the gate terminals. The hit line HT11i is also grounded via the CMOS transmission gate CTG62 in response to the entry length flag signals SWECTi and SWEBi. In the second transfer path, the hit line HTCMBi is connected to the hit line HT12i via the CMOS transmission gate CTG63 to which the entry length flag signals DWETi and DWEBi are respectively input to the gate terminals. Hit line HT12i is also grounded via CMOS transmission gate CTG64 in response to entry length flag signals DWETi and DWEBi. In the third transfer path, the hit line HTCMBi is connected to the hit line HT13i via a CMOS transmission gate CTG65 to which entry length flag signals TWETi and TWEBi are respectively input to the gate terminals. The hit line HT13i is also grounded via the CMOS transmission gate CTG66 in response to the entry length flag signals TWETi and TWEBi. In the fourth transfer path, the hit line HTCMBi is connected to the hit line HT14i via the CMOS transmission gate CTG67 to which the entry length flag signals METi and MEBi are respectively input to the gate terminals. The hit line HT14i is also connected to the power supply voltage VDD power supply terminal via the CMOS transmission gate CTG68 in accordance with the entry length flag signals DETi and DEBi.

  The latency adjustment circuit LYAJT is a circuit that holds the output signal of the above-described latency selection gate LYSG for a certain period. In the figure, the latency is set to 3 cycles corresponding to 3 (that is, the maximum bit length is 3n) which is the maximum word length value of the entries that can be searched by the CAM cell array CAMARY shown in FIGS. A configuration example of a circuit to be controlled is shown. The D flip-flops DFF61 and DFF62 are cascade-connected through the NOR circuit NR61 and the inverter circuit IV68. Hit line HT11i is connected to input terminal D of D flip-flop DFF61, and hit line HT12i is connected to the other input terminal of NOR circuit NR61. The output terminal Q of the D flip-flop DFF62 is connected to one input terminal of the NOR circuit NR62, and the hit line HT13i is connected to the other terminal. A signal obtained by inverting the output signal of the NOR circuit NR62 by the inverter circuit IV69 is output to the hit line HT2i. Hit line HT14i is connected to input terminal D of D flip-flop DFF63, and its output terminal is connected to hit line HTME1Fi. The circuit operation in the above configuration will be described next in consideration of entry attributes.

  First, when storing an entry of 1 word length in the i-th row, the entry attribute flag signal is EAFi2 = "0" and EAFi1 = "1", so the first path is selected. When the CMOS transmission gate CTG62 is cut off and the CMOS transmission gate CTG61 is turned on, a signal generated on the hit line HT1i according to the comparison result of the entry in the i-th row passes through two stages of D flip-flops DFF61 and DFF62. Thus, the data is output to the hit line HT2i two cycles after the search operation is performed. When storing entries stored across a plurality of words, the logical values of the entry length flag signals SWETi and SWEBi are “0” and “1”, respectively, so that the CMOS transmission gate CTG 61 is cut off and the CMOS The transmission gate CTG62 is turned on. Therefore, the hit line HT11i is held at the logical value “0”.

  Next, when storing the first row of an entry of 2 words in the i-th row, the entry attribute flag signal is EAFi2 = "1" and EAFi1 = "1", so the fourth path is selected. When the CMOS transmission gate CTG 68 is cut off and the CMOS transmission gate CTG 67 is turned on, the signal generated on the hit line HT1i according to the comparison result of the entry in the i-th row is sent to the hit line via the D flip-flop DFF 63. It is transferred to HTMEi, that is, the circuit block in the (i + 1) th row. Even when the first or second row of the three-word entry is stored, the signal corresponding to the comparison result of the i-th row entry is transferred to the hit line HTMEi via the same path. When storing entries other than those described above, the logical values of the entry length flag signals MWETi and MWEBi are “0” and “1”, respectively, so that the CMOS transmission gate CTG67 is cut off and the CMOS transmission gate CTG68 is turned on. Is done. Therefore, the hit line HT14i, that is, the hit line HTME1i is held at the logical value “1”. In this state, as described above, the hit signal HTMEi, which is one input signal of the multi-divided entry combination circuit MEMMB, is set to a logical value “1” by default.

  Further, when storing the first row of a 2-word entry in the (i-1) th row and the second row of a 2-word entry in the i-th row, the entry attribute flag signal is EAFi2 = "1", Since EAFi1 = "0", the second route is selected. When the CMOS transmission gate CTG64 is cut off and the CMOS transmission gate CTG63 is turned on, the signal generated on the hit line HT1i according to the comparison result of the entry in the i-th row passes through the D flip-flop DFF62. i-1) Two cycles after the coincidence signal is generated in the row, it is output to the hit line HT2i. When storing entries other than those described above, the logical values of the entry length flag signals DWETi and DWEBi are “0” and “1”, respectively, so that the CMOS transmission gate CTG63 is cut off and the CMOS transmission gate CTG64 is turned on. Is done. Therefore, the hit line HT12i is held at the logical value “0”.

  Finally, the first line of the entry of 3 words in the (i-2) line, the first line of the entry of 3 words in the (i-1) line, and the 3 of the entry of 3 words in the i line. When the row is stored, the entry attribute flag signal is EAFi1 = "0" and EAFi2 = "0", so the third route is selected. When the CMOS transmission gate CTG 66 is cut off and the CMOS transmission gate CTG 65 is turned on, a signal generated on the hit line HT 1 i according to the comparison result of the entry in the i-th row is 3 words in the (i−2) -th row. Two cycles after the cycle in which the first row of the long entry is compared is output to the hit line HT2i. When storing entries other than those described above, the logical values of the entry length flag signals TWETi and TWEBi are “0” and “1”, respectively, so that the CMOS transmission gate CTG65 is cut off and the CMOS transmission gate CTG66 is turned on. Is done. Therefore, the hit line HT13i is held at the logical value “0”.

With the above configuration and operation, the following effects can be obtained. First, an entry longer than the bit length per word of the CAM cell array CAMARY is multi-divided by performing an AND operation on the comparison result of the entries stored in adjacent rows using the multi-divided entry combination circuit MEMMB. Can be stored and stored in multiple lines. Second, by using the latency selection decoder LYDEC, the latency selection gate LYSG, and the latency adjustment circuit LYAJT, the cycle time from when the search key is input until the signal corresponding to the search result is output to the hit line HT2i, that is, The latency can be kept constant (here, 3 cycles) regardless of the bit length of the entry.
《Priority determination circuit group》
FIG. 11 shows a configuration example of the priority determination circuit group element PDCBKi in the i-th row (i = 1, 2,..., M) for the priority determination circuit group PDCBK shown in FIG. This circuit element is composed of a plurality of cascaded D flip-flops, and the number of D flip-flops included in the path for transferring the signal generated on the hit line HT2i to the hit line HT3i is shown in FIG. It is characterized in that it is controlled by the entry length flag signal shown in FIG. In FIG. 11, two stages of Ds corresponding to 3 (that is, the maximum bit length is 3n) which is the maximum word length value of the entries that can be searched by the CAM cell array CAMARY shown in FIGS. In this example, the flip-flops DFF71 and DFF72 are used, and the transfer path is controlled by three entry length flag signals SWETi, DWETi, and TWETi.

First, the first path FP is configured by a circuit in which D flip-flops DFF71 and DFF72, NAND circuits ND75 and ND76, and D flip-flop DFF73 are cascade-connected in this order. The entry length flag signal SWETi is input to the other input terminal of the NAND circuit ND75. As can be seen from the following description, the power supply voltage VDD (logical value “1”) is applied to the other input terminal of the NAND circuit ND76 by default. The D flip-flop DFF 73 is arranged to hold the signal output to the hit line HT3i for one cycle.
Next, the second path SP is configured by a circuit in which a D flip-flop DFF71, NAND circuits ND73 and ND74, an inverter circuit IV72, a NAND circuit ND76, and a D flip-flop DFF73 are connected in cascade. The entry length flag signal DWETi is input to the other input terminal of the NAND circuit ND73. As can be seen from the following description, the power supply voltage VDD (logical value “1”) is applied to the other input terminal of the NAND circuit ND74 by default.

  Finally, the third path TP includes NAND circuits ND71 and ND72, an inverter circuit IV71, a NAND circuit ND74, an inverter circuit IV72, a NAND circuit ND76, and a D flip-flop DFF73 in cascade. The entry length flag signal TWETi is input to the other input terminal of the NAND circuit ND71. The power supply voltage VDD (logical value “1”) is applied to the other input terminal of the NAND circuit ND72. For this reason, as described above, the outputs of the NAND circuits ND72 and ND74 have a logical value “1” by default.

  In such a configuration, when the entry in the i-th row is 1 word long (that is, n bits long), the entry length flag signal SWETi is activated to select the first path, and the search result is In response, the signal generated on hit line HT2i is output to hit line HT3i two cycles later. If the entry in the i-th row is the second word having a length of 2 words (that is, 2n bits), the entry length flag signal DWETi is activated to select the second path, and the search result is displayed. In response, the signal generated on hit line HT2i is output to hit line HT3i after one cycle. Further, when the entry in the i-th row is the third word having a length of 3 words (that is, 3n bit length), the entry length flag signal TWETi is activated, so that the third path is selected and the search result is displayed. In response, a signal generated on hit line HT2i is output to hit line HT3i within the cycle.

With the above configuration and operation, the following effects can be obtained. By switching the signal transfer path using the entry length flag signal and controlling the number of stages of D flip-flops included in the path, the time until the signal generated on the hit line HT2i is output to the hit line HT3i can be reduced. It can be adjusted according to the bit length of the entry. That is, the signal generated on the hit line HT2i can be output to the hit line HT3i sequentially from the signal corresponding to the entry having a long bit length.
<< Overall operation of CAM >>
FIG. 12 shows a timing chart of the search operation in the CAM according to this embodiment. Here, it is assumed that the CAM cell array CAMARY shown in FIG. 4 has a 5-bit width (n = 5), and stores three entries as shown in FIG. 13 as an example. That is, the first entry is a three-word entry, and data “00100 0010 0001” is stored across the first to third rows. The second entry is a two-word entry, and data “00100 000XX” is stored across the fourth to fifth rows. The third entry is an entry having a length of one word, and data “00100” is stored in the sixth row. Further, the search key is “00100 0010 11111”, and 5 bits are input per cycle and compared with each entry. Further, the match determination circuit shown in FIG. 4 assumes a so-called “charge injection method” as described in Non-Patent Document 1 as an example, and drives the match line to a voltage higher than the logical threshold voltage VREF. It is assumed that they are coincident when they are applied and that they are inconsistent when the voltage is low.

  First, when the search key “00100” is input in the first cycle, the entries in the first row, the fourth row, and the sixth row are determined to match, and the hit lines HT11, HT14, and HT16 are set to the power supply voltage VDD. Driven. The signal driven to this state is hereinafter referred to as “match signal”. Among these coincidence signals, the signals of the first row and the fourth row are the signals of the second row and the fifth row through the hit lines HT141 and HT144 from the hit lines HTCMB1 and HTCMB4 in the fourth path in FIG. Each is transferred to a circuit element.

  Next, when the search key “00010” is input in the second cycle, it is determined that the entries in the second and fifth rows match, and a match signal is generated on the hit lines HT12 and HT15. Among them, the coincidence signal in the second row is transferred from the hit line HTCMB2 in the fourth path in FIG. 9 to the circuit element in the third row via the hit line HT142. On the other hand, the coincidence signal of the sixth row generated in the previous cycle is transferred from the hit line HT111 in the first path to the hit line DHT126 via the D flip-flop DFF61.

  Further, when the search key “11111” is input in the third cycle, it is determined that the entries in all the rows do not match. Therefore, hit lines HT11-HT16 and HTCMB3 are driven to ground voltage VSS. A signal driven in this state is hereinafter referred to as a “mismatch signal”. The mismatch signal in the third row is output from the hit line HTCMB3 in the third path in FIG. 9 to the hit line HT23 via HT133. On the other hand, the coincidence signal of the fifth row generated in the second cycle is sent from the hit line HTCMB5 in the second path in FIG. 9 to the hit line HT25 via the hit line HT125, D flip-flop DFF62, and hit line DHT135. Is output. The coincidence signal of the sixth row transferred to the hit line DHT 126 in the second cycle is further output to the hit line HT26 via the D flip-flop DFF62 and the hit line DHT136.

  In the subsequent 4th to 6th cycles, the CAM cell array CAMARY receives a new search key “11111 11111 11111” and repeats the search operation of the first to third cycles. In this case, it can be easily understood that the comparison results are all inconsistent. On the other hand, the priority determination circuit group PDCBK classifies the above-mentioned coincidence signals and outputs them to the priority encoder PE in descending order of priority. First, in the fourth cycle, in the first to sixth rows of interest, the third path in the priority determination circuit element PWPDCEi is selected, that is, the entry length flag signal TWETi indicating a 3-word length entry. Is activated to the logical value “1” only in the third row. By the third cycle, a mismatch signal is output to the hit line HT33 in response to the mismatch signal output to the hit line HT23. This means that there is no entry that matches the search key among the three-word entries. On the other hand, the coincidence signals generated on the hit lines HT25 and HT26 in the fifth and sixth rows in the third cycle are transferred to the hit lines DHT215 and DHT216 via the D flip-flop DFF71 in the corresponding circuit element, respectively. Is done.

  In the fifth cycle, in the first to sixth rows of interest, the selection of the second path in the priority determination circuit element PWPDCEi, that is, the entry length flag signal TWETi indicating the 2-word length entry is the logical value “1”. Only the fifth line is activated. By the fourth cycle, a match signal is output to the hit signal HT35 in accordance with the match signal transferred to the hit line DHT215. This means that an entry that matches the search key exists in the 4th to 5th lines among the entries of 2 words in length. On the other hand, in the sixth row, by the fourth cycle, the coincidence signal transferred to the hit line DHT 216 is transferred to the hit line DHT 226 via the D flip-flop DFF 72 in the corresponding circuit element.

In the 6th cycle, in the first to sixth rows of interest, the selection of the first path in the priority determination circuit element PWPDCEi, that is, the entry length flag signal TWETi indicating the one word length entry is the logical value “1”. Only the sixth line is activated. By the fifth cycle, a match signal is output to the hit signal HT36 in accordance with the match signal output to the hit line DHT226. This means that an entry that matches the search key exists in the sixth line among the entries of one word length. Thereafter, the same operation is repeated and the search operation is continued.
<Effect of CAM>
Summarizing the above configuration and operation, the following three effects can be obtained. The first effect is that an entry having an arbitrary bit length wider than the bit width of the CAM cell array can be stored using a plurality of words by setting a relationship between words using the entry attribute flag signal register group. There is a point that can be done. The second effect is that the comparison result is accurately detected even for an entry having a long bit length by performing an AND operation on the comparison result of the adjacent entry according to the value of the entry attribute flag signal register group in the search operation. There is in point that can. By these first and second effects, it is possible to realize a CAM capable of efficiently storing entries having various bit lengths and performing a search operation. The third effect is that the latency control circuit group LYBK is used to temporarily hold the comparison result of the short bit length entry until the comparison of the long bit length entry is completed, and the priority determination circuit group PDCBK is used to By outputting the matching results to the priority encoder in order from the longest entry, even in the CAM storing the entries having different bit lengths, it is possible to detect in order from the entry with the higher similarity (that is, the shorter distance). is there. That is, it is possible to realize a CAM capable of generating an address signal corresponding to an entry having the shortest distance from the search key.

  In the above description, the CAM according to the present embodiment has been described on the assumption that a bit length of 3 words is stored and searched. However, the bit length is not limited to 3 words, and it can be easily understood that longer entries can be processed. In this case, together with the number of bits in the register element PWREi in the entry attribute flag signal register group EAFRBK, the number of cascaded stages of D flip-flops in each element circuit PWLYEi and PWPDCEi in the latency control circuit group LYBK and the priority determination circuit group PDCBK By increasing the number, it becomes possible to realize a CAM that performs search processing for entries having a longer bit length.

(Embodiment 2)
In the second embodiment, another configuration example and an operation example of the CAM described in the first embodiment will be described.

  FIG. 1 is a block diagram illustrating a basic configuration example of a main block of a CAM included in a semiconductor device according to a second embodiment of the present invention. There are two features of this configuration as follows. The first feature is that the CAM cell array is divided into a plurality of banks, and each bank stores only an entry having a specific bit length and performs a search operation. The second feature is that the priority encoder has a hierarchical structure, and a match address corresponding to the highest priority match entry is generated from the priority encoder of each bank via the global priority encoder. is there. In the following, it is assumed that the CAM shown in FIG. 1 can store the same number of entries having a length of 1 to 3 words (that is, n bits to 3n bits) and can perform a search operation. A configuration composed of six CAM banks CAMBK1 to CAMBK6 will be described while paying attention to differences from the configuration shown in FIG. In the figure, for simplification of description, only circuit blocks and signals related to a search operation are shown, and a read / write circuit group, a word driver group, and the like are omitted.

  First, the CAM banks CAMBK1 to CAMBK6 have a CAM cell array CAMARY composed of memory cells of m words (rows) × n bits (columns) like the CAM shown in FIG. A search key is received from the SDBK via the search line group SLBS. In addition, the CAM banks CAMBK1 to CAMBK3 store only a three-word length entry in advance, and then perform a search operation. The CAM banks CAMBK4 to CAMBK5 store only two-word entries in advance, and then perform a search operation. The CAM bank CAMBK6 stores only one-word-length entries in advance and then performs a search operation. Further, the coincidence address preferentially generated by the priority encoder is associated with the storage location of the entry. Corresponding to the fact that row addresses are allocated in the order of CAM banks CAMBK1 to CAMBK6, the description will be continued assuming that the entry in the first row of CAM bank CAMBK1 has the highest priority.

  The CAM banks CAMBK1 to CAMBK3 are configured by a match determination circuit group MDBK, a latency adjustment circuit group LY3WBK, and a priority encoder PE in addition to the CAM cell array CAMARY. The latency adjustment circuit group LY3WBK receives the hit line group HTBS1, performs a logical product operation on the comparison result of each row, temporarily holds it, and then outputs the result to the priority encoder PE via the hit line group HT3WBS.

  The CAM banks CAMK4 to CAMBK5 have the same configuration as the CAM banks CAMBK1 to CAMBK3 except that the latency adjustment circuit group LY3WBK is replaced with the latency adjustment circuit group LY2WBK. The latency adjustment circuit group LY2WBK receives the hit line group HTBS1, performs an AND operation on the comparison result of each row, temporarily holds it, and then outputs the result to the priority encoder PE via the hit line group HT2WBS.

  The CAM bank CAMBK6 has the same configuration as the CAM banks CAMBK1 to CAMBK5 except for the latency adjustment circuit group LY1WBK. The latency adjustment circuit group LY1WBK receives and temporarily holds the hit line group HTBS1, and then outputs the result to the priority encoder PE via the hit line group HT1WBS.

  FIG. 14 shows a configuration example of the latency adjustment circuit group LY3WBK. This circuit group has a latency adjustment circuit element LY3Wf (f = 1, 2,...) Every three rows in correspondence with the CAM banks CAMBK1 to CAMBK3 storing an entry having a three word length. The latency adjustment circuit element LY3W1 corresponding to the entries in the first to third rows will be described as an example. The D flip-flops DFF91 and DFF92, NAND circuits ND91 and ND92, and inverter circuits IV91 and IV92 controlled by the internal clock ICLK are used. Composed. The hit line HT1 is connected to the input terminal D of the D flip-flop DFF91, and the hit line DHT1 is connected to the output terminal Q. Further, the AND operation of the hit lines DHT1 and HT2 is performed by the NAND circuit ND91 and the inverter circuit IV91, and the result is input to the D flip-flop DFF92 via the hit line HT12. Further, hit line DHT1 is connected to output terminal Q of D flip-flop DFF92, AND operation of hit lines DHT1 and HT3 is performed by NAND circuit ND92 and inverter circuit IV92, and the result is output to hit line HT3W1. With such a configuration, as will be described later, the comparison result in the entries in the first row to the second row determined by the comparison with the search key input in multiple divisions is held, and the third result is held. The logical product operation with the comparison result in the row entry can be performed, and the comparison result of the entry of 3 words in 3 cycles can be comprehensively determined.

  FIG. 15 shows a configuration example of the latency adjustment circuit group LY2WBK. This circuit group has a latency adjustment circuit element LY2Wg (g = 1, 2,...) For every two rows, corresponding to the fact that the CAM banks CAMBK4 to CAMBK5 store entries of 2 words length. Compared with the latency adjustment circuit element LY3W1 shown in FIG. 14 by taking the latency adjustment circuit element LY2W1 corresponding to the entries of the first row to the second row as an example, the NAND circuit ND92, the inverter corresponding to the decrease in the number of rows The circuit IV92 is omitted, and the hit line HT3W1 is directly connected to the output terminal Q of the D flip-flop DFF92. With such a configuration, a logical product operation is performed on the comparison results in the entries in the first row to the second row, which are determined to be matched by comparison with a search key input in multiple divisions, and two words are obtained in two cycles. The comparison result of the long entry is comprehensively determined, and the result is held in the D flip-flop DFF 92 for one cycle, so that the comparison result for the same search key system as that searched in the CAM banks CAMBK1 to CAMBK3 is obtained. , CAM banks CAMBK1 to CAMBK3 can be output simultaneously.

  FIG. 16 shows a configuration example of the latency adjustment circuit group LY1WBK. This circuit group has a latency adjustment circuit element LY1Wh (h = 1, 2,...) For each row corresponding to the fact that the CAM bank CAMBK6 stores an entry of one word length. Taking the latency adjustment circuit element LY1W1 corresponding to the entry in the first row as an example and comparing with the latency adjustment circuit element LY2W1 shown in FIG. 15, the NAND circuit ND91 and the inverter circuit IV91 further correspond to the decrease in the number of rows. Is deleted, the D flip-flops DFF91 and DFF92 are connected in cascade, and the hit line HT1W1 is directly connected to the output terminal Q of the D flip-flop DFF92. With such a configuration, the comparison result in the entry in the first row is held for two cycles, so that the comparison result for the same search key system as that searched in the CAM banks CAMBK1 to CAMBK5 is output simultaneously with the CAM banks CAMBK1 to CAMBK5. can do.

  FIG. 17 shows a timing chart of the search operation in the CAM according to this embodiment. Here, in order to make it easy to understand the difference from the timing chart of the search operation shown in FIG. 12 of the first embodiment, the CAM cell array CAMARY is assumed to be 5 bits wide (n = 5), and an example 13 are assumed to be stored in the CAM banks CAMBK1, CAMBK4, and CAMBK6, respectively, as shown in FIG. The search key is “00100 0010 11111” as in the search operation shown in FIG. 12, and 5 bits are input every cycle and sequentially input to the CAM bank. Note that the numbers in parentheses in the figure indicate the CAM bank number, and indicate that the signal is a signal in the CAM bank.

  First, when the search key “00100” is input in the first cycle, the entries in the first row in the CAM banks CAMBK1, CAMBK4, and CAMBK6 are determined to match, and a match signal is generated on the hit line HT1.

  Next, when the search key “00010” is input in the second cycle, the entries in the second row in the CAM banks CAMBK1 and CAMBK4 are determined to match, and a match signal is generated on the hit line HT2. On the other hand, the coincidence signal generated in the first row of the CAM banks CAMBK4 and CAMBK6 in the previous cycle is transferred to the hit line DHT1 via the D flip-flop DFF91 in the latency adjustment circuit. An AND operation of this signal and the hit line HT2 is performed in the NAND circuit ND91, whereby a coincidence signal is generated on the hit line HT12.

  Subsequently, when the search key “11111” is input in the third cycle, it is determined that the entry in the third row in the CAM bank CAMBK1 does not match. An AND operation of this signal and the coincidence signal generated from the hit line HT12 to the hit line DHT12 through the D flip-flop DFF92 in the latency adjustment circuit is performed in the NAND circuit ND92, so that the hit line HT3W1 is applied. A mismatch signal is generated. On the other hand, the coincidence signal generated on the hit line HT12 in the first row of the CAM banks CAMBK4 and CAMBK6 in the previous cycle is further output to the hit lines HT2W1 and HT1W1 via the D flip-flop DFF92 in the latency adjustment circuit. .

  Further, in the fourth cycle, the priority encoder PD and the global priority encoder GPD in each CAM bank CAMBK generate an address signal corresponding to the aforementioned coincidence signal generated on the hit lines HT2W1 and HT1W1. That is, among the matching entries found by comparing the search key “00100 0010 11111” with the search key “00100” in the first cycle with the entry of 1 word length to 3 words length The address signals corresponding to the first to second rows of the CAM bank CAMBK4 in which the entry having the longest bit length is stored are generated. On the other hand, in parallel with this processing, a search key “11111” comparison operation is performed in accordance with the comparison result of the search key “00010 00001 11111” having a three-word length starting from the search key “00010” in the second cycle. The generated signal is generated on the hit line group in each CAM bank. Thereafter, the above operation is repeated.

  With the configuration and operation described above, the CAM according to the present embodiment obtains the following three effects. The first effect is that when a plurality of coincidence signals are generated in a search operation by classifying entries by bit length and storing them in a banked CAM cell array, the priority is instantly determined from the entry storage location. It is in the point that can be identified. That is, as compared with the CAM of the first embodiment, the time required for the CAM that searches for entries having various bit lengths to transfer the coincidence signal to the priority encoder, that is, the latency is shortened from 6 cycles to 3 cycles. Is possible. The second effect is that the entries are classified into the bit lengths and stored in the banked CAM cell array, so that the registers and the priority determination circuit for holding the information regarding the attribute of the entry used in the first embodiment are not required. It is in the point. That is, since the chip or module area is reduced by suppressing the number of circuits constituting the CAM using the CAM according to the present embodiment, the mounting cost of the search system using the CAM can be reduced. It becomes. The third effect is that the latency described in the first effect is the same value as the searchable search key and the maximum word length of the entry. The search operation can be performed without being aware of the above. In other words, since pattern matching is possible for data that is continuously input such as streaming data, the degree of freedom of the search key is increased, so the availability of the search system using the CAM according to the present embodiment is improved. It becomes possible to improve. In addition, the throughput of the search operation can be improved.

In the above description, the CAM according to the present embodiment has been described on the assumption that a bit length of 3 words is stored and searched. However, the bit length is not limited to 3 words, and it can be easily understood that longer entries can be processed. In this case, by increasing the number of cascaded stages of D flip-flops in the latency control circuit group, it is possible to realize a CAM that performs a search process for a desired entry.
(Embodiment 3)
In the third embodiment, another example of the configuration and operation of the CAM cell array used in the CAM described in the first and second embodiments will be described. FIG. 19 is a circuit block diagram showing a configuration example of the CAM according to the third embodiment of the present invention. The feature of this CAM is that a search key that is continuously input like streaming data is received, temporarily stored using a shift register, and a plurality of search keys are generated from one search key. The comparison operation of these keys and entries is performed simultaneously. Hereinafter, description will be made by paying attention to the difference from the CAM configuration of FIGS. The CAM shown in FIG. 19 includes a read / write circuit group RWBK, which is a basic block of a conventional CAM, a new word driver group WDBK13, a search line drive circuit group SDBK13, a CAM cell array CAMARY13, and a match determination circuit group that are unique to this embodiment. In addition to the MDBK13, a search key register group SRGBK13 is further provided.

  The CAM cell array CAMARY 13 has a configuration in which memory cells are arranged in a matrix of m words (rows) × n bits (columns). The word driver group WDBK13 is obtained by removing the function of driving the word line group WLBS2 from the word driver group WDBK shown in FIG. A feature of this CAM cell array is that a plurality of match lines are arranged per row, and a plurality of search line pairs are arranged per column in a direction orthogonal to the word. As an example, FIG. 20 shows a configuration example of a CAM cell array of 8 rows × 8 bits. The match line group MLBS13 includes a plurality of match lines MLum (u = 1, 2,..., 8, m = 1, 2,..., 8), and connects the CAM cell array CAMARY13 and the match determination circuit group MDBK13. .

  FIG. 21 is a circuit diagram showing a configuration example of the memory cell MCO 18 shown in FIG. 20 as an example. The feature of this memory cell is that it has a plurality of comparison circuits CMPn (n = 1, 2,..., 8) for one memory element ME that stores binary or ternary data. Each of the comparison circuits CMPn (n = 1, 2,..., 8) has a known configuration as a TCAM comparison circuit as shown in FIG. Each of the match lines MLu1 (u = 1, 2,..., 8) and the search line SL2t (t = 1, 2,..., 8) is arranged at each intersection, and is composed of four NMOS transistors N161, N162, N163, and N164. Is done. Further, common signal lines SNb and SN that are driven to voltages according to data stored in the memory element are connected to the gate electrodes of the transistors N162 and N164 in each comparison circuit CMPn, respectively.

  FIG. 22 is a circuit block diagram schematically showing the configuration of the search key / register group SRGBK13. This search key register group is composed of two register groups RGBK131 and RGBK132, and has a so-called shift register function. In the same figure, in correspondence with the fact that the bit width of the CAM cell array CAMARY13 is assumed to be 8, an example constituted by 8 registers REG1n, REG2n (n = 1, 2,..., 8), respectively. It is shown. Each of these registers is connected to a corresponding search line ISL1n (n = 1, 2,..., 8) among the components of the search line group ISLBS1. As shown in FIG. 23, the search line ISL1n (n = 1, 2,..., 8) is a search line ISL2n (n = 1, n) that is a component of the search line group ISLBS1 connected to the output terminal of the register group RGBK132. 2, ..., 8) are regularly combined and connected to the CAM cell array CAMARY13 via the search line drive circuit group SDBK13. Here, although the constituent elements of the search line group SLBS13 are complementary signals, only the non-inverted signals SL28 to SL28 and SL18 to SL11 are shown for simplicity.

  Next, the search key in the search operation will be described with reference to FIGS. FIG. 24 shows the search keys received by the CAM according to the present embodiment via the data bus DBS for each cycle. FIG. 25 shows search keys input to the CAM cell array CAMARY 13 for each cycle. In each table, an 8-bit search key is shown corresponding to the fact that the bit width of the CAM cell array CAMARY13 is assumed to be 8 bits. First, in the (n−1) cycle, as shown in FIG. 24, the search key An (n = 1, 2,..., 8) is received and held in the register group RGBK131.

  Subsequently, in the nth cycle, the search key Bn (n = 1, 2,..., 8) is received while transferring the search key An (n = 1, 2,..., 8) to the register group RGBK132. It is held in the register RGBK group RGBK131. In this state, as shown in FIG. 25, the search bit An (n = 1, 2,..., 8) and Bn (n = 1, 2,..., 8) are arranged in descending order from the data pattern. By generating 8 types of search keys shifted by 1 bit and inputting them into the CAM cell array, the search operations for the 8 search keys are simultaneously performed.

  Further, in the (n + 1) cycle, while the search key Bn (n = 1, 2,..., 8) is transferred to the register group RGBK132, the search key Cn (n = 1, 2,...) Is transferred as shown in FIG. , 8) are received and stored in the register RGBK group RGBK131. In this state, as shown in FIG. 25, the search bits Bn (n = 1, 2,..., 8), Cn (n = 1, 2,. By generating eight new search keys shifted by 1 bit and inputting them into the CAM cell array, the search operations for the eight search keys are simultaneously performed.

With the above configuration and operation, the CAM according to the present embodiment provides the following effects. That is, by arranging a plurality of comparison circuits in a memory cell, a plurality of search keys can be searched simultaneously. In addition, a plurality of search keys can be generated from the time-division search keys using the search key register group SRGBK13. Therefore, it is possible to realize a CAM that performs an advanced search operation for detecting a desired data pattern from data continuously input such as streaming data at high speed and without being aware of the head of the search key. It becomes possible.
(Embodiment 4)
In the fourth embodiment, another configuration and operation example of the CAM having the function described in the third embodiment will be described. FIG. 26 is a circuit block diagram showing a configuration example of the CAM according to the fourth embodiment of the present invention. There are two features of this CAM as follows. The first feature is that continuous input data such as streaming data is received via the data bus DBS, and a search key and entry search operation having a bit width wider than that of the data bus is performed. In the point. The second feature is that a plurality of search keys in which data patterns are shifted in units of a plurality of bits are generated and these search operations are performed simultaneously. In order to realize this operation, this CAM has a search line drive circuit group of SDBK15, a CAM cell array of CAMARY15, a match determination circuit group of MDBK15, and a search key register group of SRGBK15, as compared with the CAM configuration shown in FIG. And a 1: 4 demultiplexer DMUX is newly added.

  The CAM cell array CAMARY15 has a configuration in which memory cells are arranged in a matrix of m words (rows) × N bits (columns) (where N = n). Here, it is assumed that the data bus width is n bits and that a search key is generated by shifting the received data pattern in units of n bits. As an example, considering a search operation for character string data, since one character is represented by a 1-byte code, it is sufficient to generate a search key having a different data pattern in units of 8 bits (ie, n = 8). is there. FIG. 27 shows a configuration example of a CAM cell array of 8 rows × 32 bits, taking such a character string data search operation as an example. In this example, since there are four search keys to be processed at the same time, four match lines MLu1 (u = 1, 2,..., 4) are arranged for each word. The match line group MLBS15 shown in FIG. 26 is composed of the plurality of match lines MLum (u = 1, 2,..., 4, m = 1, 2,..., 8), and the CAM cell array CAMARY15 and the match determination circuit group. Connect to MDBK15.

  FIG. 28 is a circuit diagram showing a configuration example of the memory cell MCQ18 shown in FIG. 27 as an example. The feature of this memory cell is that it has a plurality of comparison circuits CMPu (u = 1, 2,..., 4) for one memory element ME that stores binary or ternary data.

  FIG. 29 is a circuit block diagram schematically showing the configuration of the search key / register group SRGBK15. This search key register group is composed of two register groups RGBK151 and RGBK152, and has a so-called shift register function. In the same figure, 32 registers REG1w, REG2w (w = 1, 2,...) Corresponding to the assumption that the bit width of the CAM cell array CAMARY15 is 32 (= N = 4n, n = 8). , 32), respectively. The register group RGBK 151 receives the search key from the n (here, n = 8) bit data bus DBS via the 1: 4 demultiplexer DMUX and the data bus IDBS. The held values are output to the register group RGBK152 and the search line drive circuit group SDBK15 via the search line group ISLBS151, respectively. In addition, the register group RGBK152 outputs the held value to the search line driving circuit group SDBK15 via the search line group ISLBS152. Here, the search line group ISLBS 151 includes search lines ISL1w (w = 1, 2,..., 32), and the search line group ISLBS 152 includes search lines ISL2w (w = 1, 2,..., 32). As shown, they are combined in units of 8 bits, and are connected from the search line driving circuit group SDBK15 to the CAM cell array CAMARY15 via the search line group SLBS15. Further, although the constituent elements of the search line group SLBS15 are complementary signals, only non-inverted signals are shown for simplicity.

  Next, search keys in the search operation will be described with reference to FIGS. 29, 31, and 32. FIG. FIG. 31 shows search keys for each cycle received by the CAM according to the present embodiment via the data bus DBS. FIG. 32 shows the search key input to the CAM cell array CAMARY15 for each cycle. First, in (n-8) cycle to (n-5) cycle, the search key An (n = 1, 2,..., 32) divided into four as shown in FIG. 31 is received, and the register group RGBK151 is received. Hold on.

  Subsequently, while transferring the search key An (n = 1, 2,..., 32) to the register group RGBK132, the search key Bn (n = 1, 2,...) In the (n-4) cycle to (n-1) cycle. .., 32) are received and held in the register RGBK group RGBK131. In this state, as shown in FIG. 32, the search bit An (n = 1, 2,..., 32) and Bn (n = 1, 2,..., 32) are arranged in descending order from the data pattern. By generating four types of search keys shifted by 8 bits and inputting them into the CAM cell array, the search operations for the four search keys are performed simultaneously.

  Further, while transferring the search key Bn (n = 1, 2,..., 32) to the register group RGBK132, as shown in FIG. 31, the search key Cn (n = 1, 2,..., 32) are received and held in the register RGBK group RGBK131. In this state, as shown in FIG. 32, the first bit is extracted from the data pattern in which the search keys Bn (n = 1, 2,..., 32) and Cn (n = 1, 2,. By newly generating four types of search keys shifted by 8 bits and inputting them into the CAM cell array, the search operations for the four search keys are simultaneously performed.

  With the above configuration and operation, the CAM according to the present embodiment can obtain the following two effects. The first effect is to receive continuously input data such as streaming data via a demultiplexer and temporarily hold it by using a search key register group, thereby making it more effective than the data bus. A plurality of search keys having a wide bit width can be generated and these search operations can be performed simultaneously. The second effect is that by generating a plurality of search keys in which data patterns are shifted in units of a plurality of bits and performing these search operations simultaneously, the number of necessary comparison circuits of the memory cells can be suppressed. is there. Therefore, by suppressing the memory cell area, it is possible to realize a low-cost CAM.

In the above, the case where the bus width of the data bus DBS is 8 bits has been described. However, the bus width is not limited to this, and various modifications can be made. For example, in the case of 32 bits, a 1: 4 demultiplexer is unnecessary, and a search key is stored in the shift register group in two cycles. In this state, four search keys are generated and searched simultaneously, so that the throughput can be further improved.
(Embodiment 5)
In the fifth embodiment, a configuration example of the memory cell element ME in the memory cell described in the first to fourth embodiments will be described. FIG. 33 shows a known configuration called a so-called twin cell in a dynamic random access memory (DRAM). Here, an example is shown in which the plate voltage VPLT is applied to the counter electrode of the capacitor. NMOS transistors N211 and N212, capacitors C211 and C212, and storage nodes SN and SNb are held at a voltage level corresponding to storage data. Here, in the case of the memory cell configuration shown in FIG. 3, Cell Data 1 and Cell Data 2 correspond to the storage nodes SNb and SN. In this configuration, since the memory element is configured with a small number of elements, the degree of integration of the CAM can be improved.

  FIG. 34 shows the same configuration as a memory cell in a static random access memory (SRAM) as another example of the memory cell element ME. This is composed of NMOS transistors N221 and N222, PMOS transistors P221 and P222, and NMOS transistors N225 and N226 for selecting memory cells, which are cross-coupled to hold data. Since this memory element can be configured using the same CMOS transistor as the logic circuit other than the CAM, the manufacturing process of the CAM is simplified and can be manufactured at low cost. Therefore, it is suitable for realizing a system LSI called a so-called system on chip (SoC) on which the present CAM is mounted at low cost.

FIG. 35 shows a configuration in which two memory elements including NMOS transistors N231, N232, N235, N236 and PMOS transistors P231, P232 are combined in addition to the memory elements shown in FIG. Search lines BL8T and BL8B are added to exchange complementary signals with the respective memory elements. In addition, a storage node serving as a contact point for the comparison circuit is determined for each SRAM cell. Such a configuration stores ternary data (“0”, “1”, “X”: mask data) if the twin cell configuration shown in FIG. 33 is replaced with a dynamic type instead of a static type. You can easily understand that you can.
(Embodiment 6)
The CAM according to the present invention is not limited to an off-chip, that is, a single device, but can be applied to a CAM block mounted on a system LSI called a so-called system on chip (SoC) as shown in FIG. The same effects as those of the above-described embodiments can be obtained, and a system LSI that performs advanced pattern matching processing can be realized. In the example shown in the figure, a central processing unit CPU, a read only memory ROM, a random access memory RAM, an interface control module IOCTL, various accelerators ACR, and a search engine SE equipped with a CAM according to the present invention A configuration connected via a bus SYSBS.
(Embodiment 7)
The CAM according to the present invention can be further applied to a search accelerator which is a kind of peripheral device of an information processing apparatus as shown in FIG. The same effects as those of the embodiments described above can be obtained, and a system with high added value can be realized. The example in the figure shows a central processing unit CPU, graphic chip GRPC, RAM module RAMMDL, memory controller MCTL, IO controller IOCTL, local area network interface LANIF, universal serial bus port USBPT, PCI 1 shows a basic system configuration of a so-called personal computer (PC) including a port PCIPT, a hard disk drive HDD, and a basic input / output system BIOS.

In such a system, by adding a search engine card SECD equipped with a CAM according to the present invention via the PCI port PCIPT, it is possible to realize a system that performs advanced pattern matching processing. In addition, since it becomes possible to open the bus between the memory controller MCTL and the IO controller IOCTL and the central processing unit CPU, other tasks such as browsing the web and viewing images while performing virus scanning, As in the case of the single operation, it can be performed smoothly.
(Embodiment 8)
In the conventional pattern matching process, the search algorithm is executed and the search is performed sequentially, so that it is difficult to shorten the search time. On the other hand, if a dedicated LSI is used, it is expected that the pattern matching process will be significantly accelerated. The CAM according to the present invention is suitable for virus search and file search in a main storage device such as a hard disk drive of an information processing device, from the embodiments described so far.

  The example of FIG. 38 shows a configuration example of a main circuit block when the present CAM is applied to a hard disk drive HDD used in the personal computer (PC) shown in FIG. The hard disk drive shown in FIG. 1 includes a mechanical part including a magnetic disk MDSK and a head HD and a control circuit group CTLBK in which a plurality of semiconductor devices are mounted on a printed circuit board. In the figure, the latter CTLBK control circuit group CTLBK includes a read / write channel RWCNL, a hard disk control circuit HDCTL, an interface circuit IFBK, a micro processor unit MPU, a motor driver MDRV, a cache CS, and a virus search accelerator. And VACL. The read / write channel RWCNL is connected to the head HD via the internal bus BS261, and exchanges data with the magnetic disk. These data are controlled by the hard disk control circuit HDCTL connected via the internal bus BS262. The hard disk control circuit HDCTL also exchanges data with the external IO controller IOCTL from the internal bus BS263 via the interface circuit IFCKT and the integrated device electronics bus IDEBS. The hard disk control circuit HDCTL is further connected to the micro processor unit MPU via the internal bus BS264, the cache CS via the internal bus BS266, and the virus detection accelerator VACL via the internal bus BS267. The microprocessor unit MPU analyzes the data transferred by the hard disk control circuit HDCTL and outputs a control signal and an address signal corresponding to the operation to each circuit block. For example, one of these signals is output to the motor driver MDRV via the internal bus 265 and transmitted to the magnetic disk MDSK and the head HD via the motor control bus MCBS, so that the head HD is moved to a desired position. It moves and performs a read operation from the rotating magnetic disk MDSK or a write operation to the magnetic disk MDSK. The cache CS is a circuit block that temporarily holds data exchanged by the hard disk control circuit HDCTL. The virus search accelerator VACL is a semiconductor device on which the content addressable memory CAM 26 according to the present invention is mounted. The virus search accelerator VACL stores in advance a virus data pattern as an entry and uses data transferred by the hard disk control circuit HDCTL as a search key. Receive and perform pattern matching.

  In the pattern matching process with the above configuration, the following two effects can be obtained. First, since pattern matching processing is performed in the hard disk drive, data access time and pattern matching processing time are shortened, and the time required for virus scanning and file scanning is shortened. Is possible. Second, since pattern matching processing is performed in the hard disk drive, it is possible to open the bus between the memory controller MCTL and the IO controller IOCTL shown in FIG. 36 and the central processing unit CPU. It becomes. Therefore, it is possible to smoothly perform other tasks such as browsing the web and viewing images while performing virus scanning, as in the case of the single operation.

  FIG. 39 shows an example of a main circuit block of the content addressable memory CAM 26 mounted in the virus detection accelerator VACL shown in FIG. The CAM core CAMCR is applied with the CAM described in the above embodiments, and is connected from the internal bus INTBS to the internal bus BS267 via the encryption circuit CRYCKT. The encryption circuit CRYCKT is a circuit that encrypts the entry and the search key, and the CAM core CAMCR performs a pattern matching process on the encrypted data. With such a configuration and operation, entries can be protected, and a highly reliable virus detection system can be realized.

  As mentioned above, the invention made by the present inventor has been specifically described based on the embodiment. However, the present invention is not limited to the embodiment, and various modifications can be made without departing from the scope of the invention. Needless to say. For example, the memory cell may have a configuration other than a DRAM cell or SRAM cell. For example, a memory cell such as a flash memory, a ferroelectric RAM (ferroelectric random access memory), an MRAM (magnetoressive random access memory), or a phase change memory can be applied. In this case, since both have a nonvolatile memory cell structure, the search operation can be resumed in a short time even if a power interruption accident occurs. Further, by appropriately combining the first to seventh embodiments, a search system that performs high-level pattern matching processing with high throughput can be realized at low cost.

In the semiconductor device of Embodiment 2 of this invention, it is a block diagram which shows the basic structural example of the principal part block of CAM contained in it. It is a circuit block diagram which shows the basic composition of the principal part block of CAM examined as a premise of this invention. It is a circuit block diagram showing a memory cell of CAM examined as a premise of the present invention. In the semiconductor device of Embodiment 1 of this invention, it is a block diagram which shows the basic structural example of the principal part block of CAM contained in it. FIG. 5 is a circuit block diagram illustrating a configuration of a CAM cell array, an entry attribute flag signal register group, and a match determination circuit group in FIG. 4. 6 is a table showing a setting example of an entry attribute flag signal register group in FIG. 5. 6 is a table showing another setting example of the entry attribute flag signal register group of FIG. 5. 6 is a table showing another setting example of the entry attribute flag signal register group of FIG. 5. FIG. 5 is a circuit diagram illustrating a detailed configuration example of a latency control circuit in FIG. 4. 10 is a table showing truth values of output signals of the latency control circuit group of FIG. 9. FIG. 5 is a circuit diagram illustrating a detailed circuit configuration example of a priority determination circuit group in FIG. 4. FIG. 5 is a waveform diagram showing an example of an operation when searching for a search key having a three-word length in the CAM of FIG. 4. 5 is a table showing an example of entries stored in the CAM cell array in FIG. 2 is a circuit diagram showing a detailed configuration example of a latency control circuit group in a CAM bank 1 in the CAM of FIG. 2 is a circuit diagram showing a detailed configuration example of a latency control circuit group in a CAM bank 4 in the CAM of FIG. 2 is a circuit diagram showing a detailed configuration example of a latency control circuit group in a CAM bank 6 in the CAM of FIG. FIG. 2 is a waveform diagram showing an example of an operation when searching for a search key having a three-word length in the CAM of FIG. 1. 3 is a table showing an example of entries stored in the CAM of FIG. 1. In the semiconductor device of Embodiment 3 of this invention, it is a block diagram which shows the basic structural example of the principal part block of CAM contained in it. FIG. 20 is a circuit block diagram illustrating a configuration example of a CAM cell array in FIG. 19. FIG. 21 is a circuit diagram illustrating a detailed configuration example of a memory cell in FIG. 20. FIG. 20 is a circuit block diagram illustrating a configuration example of a search key register group in FIG. 19. 20 is a table showing an example of connection of search keys in the CAM cell array of FIG. It is a table | surface which shows the example of the search key into which CAM of FIG. 19 is input. It is a table | surface which shows the example of the search key input into the CAM cell array of FIG. In the semiconductor device of Embodiment 4 of this invention, it is a block diagram which shows the basic structural example of the principal part block of CAM contained in it. FIG. 27 is a circuit block diagram illustrating a configuration example of a CAM cell array in FIG. 26. FIG. 28 is a circuit diagram illustrating a detailed configuration example of a memory cell in FIG. 27. FIG. 27 is a circuit block diagram illustrating a configuration example of a search key register group in FIG. 26. 27 is a table showing an example of connection of search keys in the CAM cell array of FIG. 26. It is a table | surface which shows the example of the search key into which CAM of FIG. 26 is input. 27 is a table showing an example of a search key input to the CAM cell array of FIG. FIG. 3 is a circuit diagram showing a configuration example of a dynamic memory element in a CAM memory cell according to the present invention. FIG. 3 is a circuit diagram showing a configuration example of a static type memory element in a CAM memory cell according to the present invention. FIG. 5 is a circuit diagram showing another configuration example of a static memory element in a CAM memory cell according to the present invention; In the semiconductor device of Embodiment 5 of this invention, it is a block diagram which shows the basic structural example of the principal part block of the system LSI which mounts CAM by this invention. It is a block diagram which shows the basic structural example of the principal part block of the system which mounts CAM by this invention in the information processing apparatus of Embodiment 6 of this invention. In the information processing apparatus of Embodiment 7 of this invention, it is a block diagram which shows the basic structural example of the principal part block of the hard disk drive which mounts CAM by this invention. It is a circuit block diagram which shows the structural example of the virus detection accelerator in FIG.

Explanation of symbols

CAMARY, CAMARY13, CAMARY15 ... CAM cell array,
SDBK, SDBK13, SDBK15... Search line driving circuit group,
WDBK: Word driver group,
RWBK: Read / write circuit group,
ELRBK ... Entry attribute flag signal register group,
RRWBK: Register read / write search circuit group,
MDBK, MDBK13, MDBK15 ... match determination circuit group,
LYBK, LY1WBK, LY2WBK, LY3WBK ... latency control circuit group,
PDCBK ... priority determination circuit group,
PE ... priority encoder,
GPE ... Global priority encoder,
SRGBK13, SRGBK15 ... Search key register group,
RGBK131, RGBK132, RGBK151, RGBK152 ... registers,
DBS ... Data bus,
SLBS, SLBS13, SLBS15, ISLBS131, ISLBS132, ISLBS151, ISLBS152 ... search line group,
WLBS1, WLBS2 ... word line group,
BLBS ... bit line group,
MLBS, MLBS13, MLBS15 ... match line group,
RBLBS: Register bit line group,
MLBS ... match line group,
HTBS1, HTBS2, HTBS3, HTBS4 ... Hit line group,
EAFBS ... entry attribute flag signal group,
ELBS: Entry length flag signal group,
PWMEi (i = 1, 2,..., M)... CAM cell array element per word,
PWREi (i = 1, 2,..., M)... Entry attribute flag signal register element per word,
PWMEi (i = 1, 2,..., M)... Match determination circuit element per word,
LY1Wh (h = 1, 2,..., M)... Latency control circuit element per word,
LY2Wg (g = 1, 2,..., M)... Latency control circuit element per entry,
LY3Wf (f = 1, 2,..., M)... Latency control circuit element per entry,
MCin (i = 1, 2,..., M), MCOij, MCQij (i = 1, 2,..., M, j = 1, 2,..., N).
REGi1, REGi2 (i = 1, 2, ..., m) ... registers,
MDi (i = 1, 2,..., M) ... match determination circuit,
LAi (i = 1,2, ..., m) ... Latch,
φ1 ... Latch control signal,
SLi, SLBi (i = 1, 2,..., M), SLti, SLBi (t = 1, 2,..., 8, i = 1, 2,..., M).
MLi (i = 1, 2,..., M), MLsi (s = 1, 2,..., N, i = 1, 2,..., M), MLum (u = 1, 2,..., 4, m = 1,2, ..., 8) ... match line,
HT1i, HT2i, HT3i, HTMEi, HTCMBi, DHT12i, DHT13i, HT12i, HT13i, HT14i, DHT21i, DHT22i (i = 1, 2,..., M), DHT1, HT12, DHT12.
EAFi1, EAFBi1, EAFi2, EAFBi2 ... entry attribute flag signal,
SWETi, SWEBi, DWETi, DWEBi, TWETi, TWEBi, MWETi, MWECBi (i = 1, 2,..., M)... Entry length flag signal,
PWLYEi (i = 1, 2,..., M) ... Latency control circuit element LYDEC ... Latency control decoder,
LYSG ... Latency selection gate,
LYAJT ... Latency adjustment circuit,
MEMMB: Multi-segment entry coupling circuit,
IV61, IV62, IV63, IV64, IV65, IV66, IV67, IV68, IV69, IV71, IV72, IV91, IV92 ... inverter circuit,
CTG61, CTG62, CTG63, CTG64, CTG65, CTG66, CTG67, CTG68 ... CMOS transmission gate,
ND61, ND62, ND63, ND64, ND65, ND71, ND72, ND73, ND74, ND75, ND76, ND91, ND92 ... NAND circuit,
NR61, NR62 ... NOR circuit,
DFF61, DFF62, DFF63, DFF71, DFF72, DFF73, DFF91, DFF92 ... D plip flop,
ICLK: Internal clock signal,
FP, SP, TP ... arrows indicating signal propagation paths,
Memory element ... ME,
N151, N152, N161, N162, N163, N164, N211, N212, N221, N222, N223, N224, N231, N232, N233, N234 ... NMOS transistors,
P221, P222, P231, P232 ... PMOS transistors,
C211, C212 ... capacitors,
CPU: Central processing unit,
ROM ... Read only memory,
RAM ... Random access memory,
IOCTL: Interface control module,
ACR ... various accelerators,
SE ... Search engine SE,
SYSBS ... System bus,
GRPC: Graphic chip,
RAMMDL ... RAM module,
MCTL ... Memory controller,
IOCTL ... IO controller,
LANIF ... Local area network interface
USBPT ... Universal serial bus port,
PCIPT ... PCI port,
HDD ... Hard disk drive,
SECD: Search engine card,
BIOS ... Basic input / output system,
CAM, CAM26 ... Content addressable memory,
HDD ... Hard disk drive,
CTLBK: Control circuit group,
MDSK ... magnetic disk,
HD ... Head,
IDEBS ... IDE bus,
IFBK: Interface circuit,
HDCTL ... Hard disk control circuit,
MPU ... micro processor unit,
MDRV: Motor driver
RWCNL: Read / write channel,
CS ... Cash,
VACL: Virus scan accelerator,
CAMCR ... CAM core,
BS261, BS262, BS263, BS264, BS265, BS266, BS267 ... Internal bus,
IDEBS ... Integrated device electronics bus,
INTBS: Internal bus.

Claims (4)

A CAM cell array including a plurality of memory cells arranged in the word line and bit line directions;
A search line driving circuit group for outputting a search key to the CAM cell array;
An entry attribute flag signal register group having a plurality of registers arranged corresponding to each word of the CAM cell array,
The CAM cell array previously stores entries having different bit lengths in the memory cell, and performs a comparison operation between the search key input from the search line driving circuit group during the search operation and the entry,
The entry attribute flag signal register group holds attribute information corresponding to the bit length of the entry in each of the registers,
A match determination circuit that outputs a match signal according to the result of the comparison operation or a mismatch signal for each word;
A latency control circuit group for executing a logical operation of the match signal or the mismatch signal and adding a latency for each entry according to the attribute information held by the register;
A semiconductor device comprising: a priority determination circuit group that outputs a match signal corresponding to an entry to a priority encoder in order of increasing bit length according to the attribute information. A CAM cell array including a plurality of memory cells arranged in the word line and bit line directions;
In the CAM cell array, a sub CAM cell array banked in units of at least one word line direction;
A search line driving circuit group for outputting a search key to the sub-CAM cell array;
A global priority encoder,
The sub CAM cell array stores entries having different bit lengths in advance, and performs a comparison operation between the search key input from the search line driving circuit group during the search operation and the entry,
Further, a match determination circuit that outputs a match signal according to the result of the comparison operation or a mismatch signal for each word, and
A latency control circuit group having a plurality of D flip-flops;
A priority encoder for generating an output signal corresponding to the word in which the match signal is generated,
The global priority encoder is a semiconductor device that receives an output of the priority encoder in the plurality of sub-CAM cell arrays and outputs a coincidence address.   3. The semiconductor device according to claim 2, wherein the latency control circuit group has, for each entry, D flip-flops having the same number of stages as the number corresponding to the bit length of the entry.   3. The semiconductor device according to claim 2, wherein the sub CAM cell array is assigned row addresses in order of bit length from an entry having a preset storable bit length.

Images