Circuit and method for detection of idle word in associative memory

Description: TECHNICAL FIELD [Detailed description of the invention]

【0001】

[Technical field to which the invention belongs]

The present invention relates to an associative memory (CAM), and more particularly to an idle word detection circuit having no data to be searched in a CAM having a valid cell and a method for detecting the idle word.

【0002】

[Conventional technology]

The associative memory (CAM) detects whether or not there is data in the memory that matches the input search data in addition to the normal data read / write operation by adding a data search device to the semiconductor memory. It is a semiconductor memory that outputs the address if there is matching data, and outputs that there is no matching data if there is no matching data. As shown in FIG. 1, a general CAM is composed of an address / data circuit (bus) 1, an input / output / control circuit 2, and a plurality of memory blocks 3.

【0003】

FIG. 2 is a diagram showing a memory block 3 of a conventional CAM. In addition to the address decoder 10, the data writing driver 11, the data reading sense amplifier 12, and the CAM cell array 13 found in general memory, the memory block 3 includes a data search driver 11, a word match line 14, and a valid cell 15. , Valid 16, word match circuit 17, address encoder 18 included. Since the data search driver can also be used as a data write driver, it is indicated by the same reference numeral 11 in FIG. 2 and has a function of sending the search data to the bit line of the cell array at the time of data search. The valid cell 15 is a memory cell that exists for each word address. The valid cell 15 holds "false" (bit "0") when no data is written to its word address, and "true" (bit "1") is written when data is written. It is a memory that holds this.

【0004】

The word match line 14 outputs the result of comparing the search data and the data in the memory cell for each word address at the time of data search. The word match circuit 17 is connected to the CAM cell array 13 via the word match line 14. The word match circuit 17 is a circuit that receives the output 16 of the word match line 14 and the valid cell 15 and determines the presence or absence of matching data and outputs the same. The address encoder 18 receives the output of the word match circuit 17, creates an address with specific weighting, and outputs the address. Specific weighting means, for example, increasing the priority of low addresses.

【0005】

Next, the operation of the CAM shown in FIG. 2 will be described. FIG. 3 is a diagram for explaining the flow of data in the CAM. In FIG. 3, seven data illustrated from word addresses 0 to addresses 6 of the CAM cell array are stored. Bits "1" indicating that the data to be searched exists are stored in the valid cells of word addresses 0, 1, 3, 5, and 6. It also indicates that the valid cells at word addresses 2 and 4 do not have the data to search for (the data is invalid), in other words, the data has not yet been written or has been invalidated since it was written. Bit "0" is stored.

【0006】

Now, it is assumed that the search data indicated by reference numeral 20 in FIG. 3 is input by the data search driver 11 (FIG. 2). The word match line 14 outputs the result of comparing the search data and the data in the memory cell for each word address at the time of data search. The word match circuit 17 receives the valid 16 which is the output of the word match line 14 and the valid cell 15, detects the presence or absence of matching data, and outputs the matching data. If the search data 20 and the data in the cell match, bit "0" is output. On the contrary, if the search data 20 and the data in the cell do not match, bit "1" is output. In the example of FIG. 3, the data match at word addresses 1, 2, and 6. However, in the case of address 2, since the bit "0" is set in the valid cell, the output of the word match circuit is "1". Therefore, only the word match output of addresses 1 and 6 is "0", and the remaining addresses are "1".

【0007】

The address encoder 18 receives the output of the word match circuit 17 and outputs the smallest address. In the example of FIG. 3, the smaller address 1 of the two matching addresses 1 and 6 is output. At the same time, "true" is output as match output.

【0008】

The conventional CAM described with reference to FIGS. 1 to 3 has the following problems. That is, (1) It is unknown whether there is a "free address" (idle word) for which no data has been written to the CAM. (2) It is unknown which address of CAM is a "free address". (3) In order to solve the problems of (1) and (2) and to know the existence of "free address" (idle word) and if there is "free address" (idle word), it is new outside the CAM. It is necessary to provide a circuit.

【0009】

[Problems to be Solved by the Invention]

The present invention has been made to solve the above-mentioned problems of CAM. The purpose is to enable the CAM to know the presence or absence of a "free address" (idle word) and the address if there is a "free address" (idle word).

【0010】

An object of the present invention is to make it possible to know the presence / absence of an idle word and the word address of the idle word, if any, without providing a new circuit outside the CAM.

【0011】

An object of the present invention is to enable a CAM having a valid cell to detect and output an idle word by using the data of the valid cell and an address encoder.

【0012】

[Means for solving problems]

According to the first aspect of the present invention, the idle word detection circuit of the associative memory having the ballid cell includes means for supplying the output of the valid cell to the address encoder in response to the idle word detection signal. An idle word detection circuit is provided.

【0013】

According to the invention of claim 5, the associative memory (CAM) uses the output of the CAM cell, the valid cell, the word match line, the word match circuit, the address encoder, and the valid cell to generate an idle word. An associative memory is provided that includes a circuit for detection.

【0014】

According to the invention of claim 9, it is a method of detecting an idle word in an associative memory having a valid cell, in which a step of writing bit data indicating the presence or absence of valid data in the valid cell and an address according to an idle word detection signal. A step of outputting bit data of the ballid cell to the encoder and a method of detecting an idle word including are provided.

【0015】

BEST MODE FOR CARRYING OUT THE INVENTION

Embodiments of the present invention will be described in detail with reference to the drawings. FIG. 4 is a diagram for conceptually showing a method for detecting an idle word according to the present invention. FIG. 4 is the same as FIG. 3 except for arrow 22. In a word, the present invention focuses on a valid cell and detects a free address (idle word) by using the data of the valid cell. That is, conceptually, as shown by the arrow 22 in FIG. 4, the idle word is detected by passing the data of the valid cell to the address encoder.

【0016】

In the example of Figure 4, the valid cell word addresses 2 and 4 do not have the data to search for (the data is invalid), in other words, the data has not yet been written or is invalid after it has been written. The bit "0" indicating that is stored. The address encoder receives the data of addresses 2 and 4 of this valid cell and outputs the smallest address, address 2. At the same time, the address encoder outputs "true" as the match output.

【0017】

5 and 6 are diagrams that concretely represent the concept of the present invention shown in FIG. 5 and 6 are diagrams showing the configuration from the CAM cell array 13 to the address encoder 18 of the CAM of the present invention. The other configurations of the CAM (address decoder 10, driver 11, sense amplifier 12) are the same as the conventional example shown in FIG.

【0018】

In the first example of FIG. 5, the idle word detection circuit (selection circuit) 19 of the present invention is installed before the input of the address encoder 18. Then, using the idle word detection signal (IWD) as the control signal, the output of the valid cell 15 (idle word search output) and the output of the word match circuit 17 (data search output) are switched to the address encoder 18. Output. The idle word detection signal (IWD) can be generated as a new signal, but if the idle word address is always output during operations other than the data search operation, the data search signal is the idle word detection signal (IWD). Can be used as. Although the detection circuit (selection circuit) 19 is shown as an independent circuit in FIG. 5, it can also be incorporated in the address encoder 17.

【0019】

On the other hand, in the second example of FIG. 6, the idle word detection circuit (selection circuit) 19 of the present invention is installed before the input of the word match circuit 17, and the idle word detection signal (IWD) outputs the valid cell 15. This is a method of switching between the valid 16 (idle word search output) and the word match line output (data search output) and outputting them to the word match circuit 17. Although the detection circuit (selection circuit) 19 is shown as an independent circuit in FIG. 6, it can also be incorporated in the word match circuit 17.

【0020】

FIG. 7 is a diagram showing a configuration example of the ballid cell 15. This ballid cell can be used in common with the CAMs shown in FIGS. 6 and 7. The ballid cell in FIG. 7 utilizes a general latch circuit and is composed of an N-type FET 30 and three inverters 31, 32, and 33. The operation is to set the input (DATA) and gate (GATE) of the N-type FET30 to "1" (high) when data is written to a certain word address or when you want to search the data at that address. At this time, the output (VALID) passed through the two inverters 31 and 32 is set to "1", and at the same time, the output (VALID) "1" is held by the inverters 31 and 33. If you want to exclude the data at that address from the search target, set the input (DATA) to "0" (low), set the gate (GATE) to "1" (high), and set the output (VALID) to "0". At this time, the output (VALID) "0" is self-held by the inverters 31 and 33.

【0021】

FIG. 8 is a diagram showing a configuration example of the word match circuit 17 in the CAM of FIG. The word match circuit of FIG. 8 is composed of an N-type FET 40, a P-type FET 41, and a sense amplifier (SA) 42. In the word match circuit, various sense methods can be adopted depending on the comparison method for each CAM cell and word address. The sense amplifier (SA) outputs "0" when the input is lower than a certain reference potential and "1" when the input is higher than a certain reference potential. The input (WMLINE) is a signal that becomes "0" when the input search data and the data in the memory match in word address units, and becomes "1" when they do not match. For example, when the output of the ballid cell, VALID 16, is "1", the N-type FET 40 is turned on and the P-type FET 41 is turned off at the same time. At this time, the node (WM SENSE) is connected to the word match line (WMLINE), and the sense amplifier (SA) outputs the value corresponding to the signal on the word match line (WMLINE) to the word match (WM). When the VALID 16 is "0", the address is not subject to data search, so the N-type FET 40 is turned off and the P-type FET 41 is turned on at the same time. At this time, the node (WMSENSE) and the word match line (WMLINE) are separated, the potential of the node (WMSENSE) becomes high, and "1" is output to the word match (WM).

【0022】

FIG. 9 is a diagram showing a further specific example of the detection circuit 19 of the first example of FIG. In the example of FIG. 9, the selection circuit 50 switches between word match output (WM) and VALID (VALID) according to the idle word detection signal (IWD) of FIG. That is, in the case of normal data retrieval, the idle word detection signal (IWD) becomes "0 (low)", and the word match output (WM) is output from the selection circuit 50 to the address encoder 51. In the case of idle word detection, the idle word detection signal (IWD) becomes "1 (high)", and the VALID is output from the selection circuit 50 to the address encoder 51.

【0023】

FIG. 10 is a diagram showing a further specific example of the detection circuit 19 of the second example of FIG. In the example of FIG. 10, the selection circuit 43 is provided in the input stage of the sense amplifier 42 of the word match circuit of FIG. The selection circuit 43 switches between a word match output (WM) and a valid output (VALID) according to the idle word detection signal (IWD). That is, in the case of normal data retrieval, the idle word detection signal (IWD) becomes "0 (low)", and the word match output (WM) is output from the selection circuit 43 to the sense amplifier (SA) 42. In the case of idle word detection, the idle word detection signal (IWD) becomes "1 (high)", and the output (VALID) of the valid cell is output from the selection circuit 43 to the sense amplifier (SA) 42.

【0024】

11 to 13 show details (examples) of the selection circuits 43 and 50 of the present invention. The selection circuit of FIG. 11 is composed of an inverter 60, an AND circuit 61, 62, and an OR circuit 63. The selection circuit of FIG. 12 is composed of an inverter 64, an OR circuit 65, 66, and an AND circuit 67. FIG. 13 is a selection circuit including an inverter 68, an N-type FET 69, 71, and a P-type FET 70, 72. In any of the configurations of FIGS. 11 to 13, when the idle word detection signal (IWD) is "0", the output of the selection circuit becomes the word match line output (WMSENSE) or the word match output (WM), which is normal. Perform a data search. When the idle word detection signal (IWD) is "1", the output of the selection circuit becomes the VALID output (VALID), and the idle word search can be performed.

【0025】

Although various examples of the present invention have been described above with reference to the drawings, the present invention is not limited to the above-described examples. In addition, the present invention can be carried out in a mode in which various improvements, modifications, and modifications are added based on the knowledge of those skilled in the art without departing from the spirit of the present invention.

[Simple explanation of drawings]

[Figure 1]

It is a figure which shows the configuration example of a general CAM.

[Figure 2]

It is a figure which shows the memory block of the conventional CAM.

[Fig. 3]

It is a figure for demonstrating the flow of data in a conventional CAM.

[Fig. 4]

It is a figure which conceptually showed the detection method of the idle word which concerns on this invention.

[Fig. 5]

It is a figure which shows the CAM (1st example) including the detection circuit of the idle word of this invention.

[Fig. 6]

It is a figure which shows the CAM (the second example) including the detection circuit of the idle word of this invention.

[Fig. 7]

It is a figure which shows the example of the valid cell of this invention.

[Fig. 8]

FIG. 5 is a diagram showing a configuration example of a word match circuit in the CAM of the present invention shown in FIG.

[Fig. 9]

It is a figure which shows the detail of the 1st detection circuit of FIG.

[Fig. 10]

It is a figure which shows the detail of the 2nd detection circuit of FIG.

[Fig. 11]

It is a figure which shows the detail of the selection circuit of this invention.

[Fig. 12]

It is a figure which shows the detail of the selection circuit of this invention.

[Fig. 13]

It is a figure which shows the detail of the selection circuit of this invention.

[Explanation of symbols]

1: Address / data circuit (bus) 2: Input / output / control circuit 3: Memory block 10, 51: Address decoder 11: Driver for writing data 12: Sense amplifier for reading data 13: CAM cell array 14: Word match line 15: Ballid cell 16: Ballid 17: Word match circuit 18: Address encoder 19, 43, 50: Idle word detection circuit (selection circuit) 20: Search data