JP2015225675A - Associative memory and semiconductor device - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide an associative memory which includes a memory in which a search data is input, and which stores a plurality of entry data, and a search circuit which searches an address in the memory in which entry data corresponds to the search data; and to restrict the number of entry data to be compared with the search data to a log of the total number of entry data so as to reduce power consumption.SOLUTION: In a memory, entry data re-sorted in an ascending or descending order are stored corresponding to addresses. A search circuit, in which the whole addresses where a plurality of entry data are stored are initial search areas, compares entry data and search data stored in an address of a central search area, and outputs the address as a search result when these data agree, but repeats a search operation of narrowing the search area in a next search on the basis of a result of comparison between their sizes when they do not agree.

Description

  The present invention relates to an associative memory and a semiconductor device using the same, and can be suitably used particularly for an associative memory with low power consumption.

  Content addressable memory (CAM) is used in routers and network switches, and CAM is required to have a large capacity as network traffic increases. In a virtual network realized by OpenFlow, one OpenFlow controller integrates and controls many OpenFlow switches. Large capacity, high-speed throughput, dynamic entry table, low power consumption, etc. are required for CAM installed in network devices such as OpenFlow switches.

  Patent Document 1 discloses a CAM that realizes a function of size comparison and range match comparison between data stored in a storage circuit and search data.

  Patent Document 2 discloses a cache memory that can suppress access to a main memory and improve system efficiency even when accesses to a plurality of memory entries of different tags allocated to the same cache entry compete or continue. An apparatus is disclosed.

JP 2004-295967 A JP 09-288615 A

  As a result of examination of Patent Documents 1 and 2 by the present inventors, it has been found that there are the following new problems. That is, it has been found that the CAM described in Patent Document 1 consumes a large amount of power because the search data is compared with all stored data (entry data). Such a CAM is referred to herein as a binary CAM and is abbreviated as BCAM.

  Means for solving such problems will be described below, but other problems and novel features will become apparent from the description of the present specification and the accompanying drawings.

  According to one embodiment, it is as follows.

  That is, an associative memory comprising: a memory that receives search data and stores a plurality of entry data; and a search circuit that searches for an address in the memory in which entry data that matches the search data is stored. It is configured as follows. In the memory, entry data rearranged in ascending order or descending order is stored in association with addresses. The search circuit uses the entire memory address as the initial search area, compares the entry data stored in the center address of the search area with the search data, and if they match, outputs the address as the search result and does not match In this case, the search operation for narrowing the search area for the next search is repeated based on the result of the size comparison.

  The effect obtained by the one embodiment will be briefly described as follows.

  That is, a CAM with low power consumption can be provided.

FIG. 1 is a block diagram illustrating a configuration example of a CAM that performs a binary search on an SRAM. FIG. 2 is an explanatory diagram showing an operation example of the comparison circuit 3_1 in the CAM of FIG. FIG. 3 is an explanatory diagram showing an operation example of the comparison circuit 3_2 in the CAM of FIG. FIG. 4 is an explanatory diagram showing an operation example of the comparison circuit 3_3 in the CAM of FIG. FIG. 5 is an explanatory diagram showing an operation example of the comparison circuit 3_4 in the CAM of FIG. FIG. 6 is an explanatory diagram showing an operation example of the comparison circuit 3_5 in the CAM of FIG. FIG. 7 is a block diagram illustrating a configuration example of a CAM that performs a two-stage search. FIG. 8 is a block diagram showing another configuration example of a CAM that performs a two-stage search. FIG. 9 is an explanatory diagram showing an example of the operation of a CAM that performs a two-stage search. FIG. 10 is a block diagram illustrating a configuration example of a CAM that performs a binary search on a 2-input search entry. FIG. 11 is a block diagram illustrating a configuration example of a CAM with a sorting function. FIG. 12 is a timing chart illustrating an operation example of the CAM with sort function. FIG. 13 is a block diagram showing another configuration example of the CAM with sort function. FIG. 14 is a circuit diagram showing a configuration example of a memory cell applicable to the CAM with sort function. FIG. 15 is an explanatory diagram showing a truth table representing the operation of the memory cell of FIG. FIG. 16 is a circuit diagram showing another configuration example of the memory cell applicable to the CAM with sort function. FIG. 17 is an explanatory diagram showing a truth table representing the operation of the memory cell of FIG. FIG. 18 is a block diagram illustrating a configuration example of a CAM that forms a complementary search cache with a BCAM with a sort function and includes a plurality of BSRAMs to perform a two-stage search.

1. First, an outline of a typical embodiment disclosed in the present application will be described. Reference numerals in the drawings referred to in parentheses in the outline description of the representative embodiments merely exemplify what are included in the concept of the components to which the reference numerals are attached.

[1] <Associative memory (CAM) for performing binary search on SRAM>
An associative memory (CAM) (100) according to a representative embodiment disclosed in the present application is a memory (1_1 to 1_5, 2_2 to 2_4) in which search data (Search Entry) is input and a plurality of entry data is stored. And search circuits (3_1 to 3_5, 4_1 to 4_5) for searching for an address in the memory in which entry data matching the search data is stored.

  In the memory, the plurality of entry data can be rearranged in ascending order or descending order and stored in association with addresses.

  The search circuit uses the entire address (0thw to 15thw) where the plurality of entry data is stored as an initial search area, and the entry data and the search data stored at the center address (7thw,...) Of the search area. When the address matches, the address is output as a search result. When the address does not match, the search operation for narrowing the search area is repeated based on the result of the size comparison.

As a result, only one entry data to be compared with the search data is stored at the center address of each search area, so the number of entry data to be compared is the total number of entry data (2 ^N ). Thus, it is possible to provide an associative memory with a low logarithm (log ₂ 2 ^N = N) and low power consumption. Here, the “center” address of the search area does not mean a mathematically exact half, but may be approximately the center. For example, the center address of 16 entries may be the seventh or eighth address. Although a larger error may be included, the number of steps required for the search (the number of the above “repetitions”), that is, the number of comparisons can be reduced as it is closer to ½. Hereinafter, the term “center” in this specification is defined similarly.

[2] <Pipeline configuration>
In the item 1, the memory includes first to Nth words having a number of words for each power of 2 from 1 word to 2 N-1 powers, each word being associated with the center address of the search area. It has memories (1_1 to 1_4) (N is a natural number), and the search circuit has first to Nth comparison circuits (3_1 to 3_4) provided corresponding to the first to Nth memories.

  The comparison circuit reads entry data from a corresponding memory, compares the entry data with the search data, and outputs an address at which the entry data is stored and a comparison result to a subsequent comparison circuit. The comparison circuit determines an address from which entry data to be compared is read based on the address input from the previous stage and the comparison result.

  As a result, the CAM performing the binary search can be configured by the pipeline, and the throughput can be improved.

[3] <CAM of 2 N entries>
In item 2, the memory further includes a 1-word N + 1th memory (1_5) having an address of 2 N-1, and the search circuit receives the comparison result input from the N-1th comparison circuit. And an N + 1th comparison circuit (3_5) for comparing the search data with the entry data stored in the (N + 1) th memory.

Thereby, it is possible to provide a CAM having an entry number of powers of 2 (2 ^N ) words.

[4] <Associative memory for two-step search>
In item 1, the content addressable memory having the same configuration as the content addressable memory is defined as a first content addressable memory (BSRAM, 100). The associative memory (500) for performing the two-stage search includes a second associative memory (BCAM, 200) having the same number of entries as the first associative memory, and a plurality of the first associative memories (100_1 to 100_m). And a transfer circuit (900) that reads a plurality of entry data from the second associative memory, rearranges them in ascending or descending order, and transfers them to the first associative memory.

  As a result, when the second associative memory functioning as a search cache is hit, the latency is small, and when there is no hit, a plurality of first associative memories are sequentially searched, so that a CAM with small capacity and low power consumption can be obtained. Can be provided.

[5] <Double search cache>
In item 4, the associative memory (500) includes two second associative memories (200_1, 200_2), and when transferring entry data from one to the first associative memory, the other is used as a new entry. Data write target.

  Thereby, writing of new entry data is not waited. During the period in which entry data is transferred from one second associative memory to the first associative memory, new entry data cannot be written to the second associative memory in which transfer is being performed. However, when a new entry data write request occurs during that period, new entry data can be written to the other second content addressable memory that is not to be transferred.

[6] <Search order>
In item 4 or item 5, when search data is input, the associative memory (500) first sets the second associative memory as a search target, and if the second associative memory does not hit, Among the first associative memories, search objects are searched in order from the one in which entry data is most recently written.

  Thereby, the time until hitting can be shortened.

[7] <CAM with sort function>
In item 4 or 5, the second associative memory includes a memory cell (10) having a function of comparing magnitude matches, and compares each of input data inputted and entry data inputted so far. Based on the result, a rank storage circuit (9_1 to 9_N) that obtains and stores ranks corresponding to a plurality of input entry data is further provided. The transfer circuit reads the order and entry data in association with each other, rearranges them, and transfers them to the first associative memory.

  Thereby, the time required for rearranging (sorting) entry data can be shortened.

[8] <Parallel input of multiple search data>
In item 1, the memory (2_2 to 2_4) includes a plurality of ports that can simultaneously read data from different words by a plurality of addresses, and the search circuits (3_1 to 3_5 and 4_1 to 4_5) include the plurality of ports. Each port is provided in parallel.

  As a result, a plurality of search data (Search Entry 1 and Search Entry 2) can be simultaneously input in parallel, and simultaneously searched in parallel.

[9] <Semiconductor device>
A semiconductor device comprising the associative memory according to any one of items 1 to 8 on a single semiconductor substrate.

  As a result, power consumption can be kept low in a semiconductor device in which a CAM is integrated.

[10] <Associative memory (CAM) for performing binary search on SRAM>
The associative memory according to the representative embodiment disclosed in the present application can hold 2 N power entry data (N is a natural number), and the entry matches the input search data (Search Entry). An associative memory (CAM) (100) for searching for data.

  1st to Nth memories (1_1 to 1_4) and 1 word N + 1th memory (1_5) having the number of words every power of 2 from 1 word to 2 to the N-1th power, and the first to N + 1th 1st to N + 1th comparison circuits (3_1 to 3_5) provided corresponding to the memories.

  The first comparison circuit reads entry data from the first memory, compares the search data with a magnitude match, and outputs the comparison result to the second comparison circuit.

  The second comparison circuit (3_2) reads out the entry data stored at the address (3rdw or 11thw) of the second memory calculated based on the comparison result input from the first comparison circuit, and the search data Are compared with each other, and the comparison result is output to the third comparison circuit (3_3).

  The third to N-th comparison circuits (3_3 to 3_4) are configured to compare the entry to be compared based on the address where the entry data to be compared by the comparison circuit in the previous stage is stored and the comparison result input from the previous stage. The address from which data is read is determined, the entry data is read from the corresponding memory, the magnitude comparison is compared with the search data, and the result of the comparison is output to the comparison circuit at the subsequent stage.

  The N + 1th comparison circuit (3_5) compares whether the search data matches the entry data stored in the N + 1th memory (1_5).

  When there is entry data that matches the search data, the search data is determined based on the number of the memory that stores the matching entry data and the address in the memory where the matching entry data is stored. It is calculated and output what number entry data when the N-th entry data is sorted.

As a result, only one entry data to be compared with the search data is stored at the center address of each search area, so the number of entry data to be compared is the total number of entry data (2 ^N ). Thus, it is possible to provide an associative memory with a low logarithm (log ₂ 2 ^N = N) and low power consumption.

[11] <Storage of sorted entry data>
In item 10, the first memory stores 2 N-1th data of the 2 N entry data, and the N + 1 memory stores 2 of the 2 N entry data. To the Nth power.

  The i-th memory (i is a natural number greater than or equal to 2 and less than N) is the first memory of j × 2 N−i-th entry data, where j is all natural numbers less than 2 to the i power. To entry data other than the entry data stored in the (i-1) th memory.

  When there is entry data that matches the search data, the associative memory outputs the j × 2 Ni-th power value−1 corresponding to the matching entry data.

  As a result, the entry data is sorted and stored, and the rank of the entry data that matches the search data is output as the stored address.

[12] <Pipeline configuration>
In Item 11, the first to (N + 1) th comparing circuits sequentially operate in different pipeline stages for the same search data.

  As a result, the CAM performing the binary search can be configured by the pipeline, and the throughput can be improved.

[13] <Associative memory performing two-step search>
In item 11, the content addressable memory having the same configuration as the content addressable memory is defined as a first content addressable memory (BSRAM, 100). The associative memory (500) for performing the two-stage search includes a second associative memory (BCAM, 200) having the same number of entries as the first associative memory, and a plurality of the first associative memories (100_1 to 100_m). And a transfer circuit (900) that reads a plurality of entry data from the second associative memory, rearranges them in ascending or descending order, and transfers them to the first associative memory.

  As a result, when the second associative memory functioning as a search cache is hit, the latency is small, and when there is no hit, a plurality of first associative memories are sequentially searched, so that a CAM with small capacity and low power consumption can be obtained. Can be provided.

[14] <Double search cache>
In item 13, the associative memory (500) includes two second associative memories (200_1, 200_2), and when transferring entry data from one to the first associative memory, the other is used as a new entry. Data write target.

  Thereby, writing of new entry data is not waited. During the period in which entry data is transferred from one second associative memory to the first associative memory, new entry data cannot be written to the second associative memory in which transfer is being performed. However, when a new entry data write request occurs during that period, new entry data can be written to the other second content addressable memory that is not to be transferred.

[15] <Search order>
In the item 13 or the item 14, when the search data is input, the associative memory (500) first sets the second associative memory as a search target, and if the second associative memory does not hit, Among the first associative memories, search objects are searched in order from the one in which entry data is most recently written.

  As a result, the time until the hit can be shortened, and the power consumption can be reduced by not performing the search after the hit.

[16] <CAM with sort function>
Item 13 or Item 14 is that the second associative memory is configured by a memory cell (10) having a function of comparing magnitude matches, and compares each of input data input and input data input so far. Based on the result, a rank storage circuit (9_1 to 9_N) that obtains and stores ranks corresponding to a plurality of input entry data is further provided. The transfer circuit reads the order and entry data in association with each other, rearranges them, and transfers them to the first associative memory.

  Thereby, the time required for rearranging (sorting) entry data can be shortened.

[17] <Parallel input of a plurality of search data>
In Item 11, each of the second to Nth memories has a plurality of ports that can simultaneously read data from different words by a plurality of addresses, and the search circuits (4_1 to 4_5) are connected to the plurality of ports. Prepare each in parallel.

  Thereby, a plurality of search data can be simultaneously input in parallel and searched simultaneously in parallel.

[18] <Semiconductor device>
Item 18. A semiconductor device comprising the content addressable memory according to any one of Items 10 to 17 on a single semiconductor substrate.

  As a result, power consumption can be kept low in a semiconductor device in which a CAM is integrated.

2. Details of Embodiments Embodiments will be further described in detail.

[Embodiment 1] <CAM for performing binary search on SRAM>
An associative memory (CAM) according to a representative embodiment disclosed in the present application receives search data (Search Entry), stores a plurality of entry data, and stores entry data that matches the search data. And a search circuit for searching for an address in the memory. In the memory, a plurality of entry data is rearranged in ascending order or descending order, and each is associated with an address and stored. For example, if the memory is 2 ^N words, 2 ^N entry data are stored in ascending order, so that entry data having a minimum value in 0w (word) and entry data having a maximum value in 2 ^N -1w are stored. Is stored. Here, the memory is, for example, an SRAM (Static Random Access Memory), and may be a large-capacity SRAM capable of storing all the entry data in one, but for each appropriate number of words as described later. It is preferable to be configured by a plurality of divided SRAMs. This is because the performance can be improved by adopting a pipeline configuration in which each of the plurality of SRAMs has a pipeline step. Further, another storage device having an equivalent function may be used.

The search circuit uses the entire address 0w to 2 ^N -1w where a plurality of entry data is stored as an initial search area, and the entry data and search data (Search) stored at the address 2 ^N-1 -1w at the center of the search area Entry). When they match, the address (2 ^N-1 -1w) is output as a search result, and when they do not match, the search area is narrowed based on the result of size comparison. That is, when the search data (Search Entry) is smaller than the entry data stored at the center address 2 ^N-1 -1w of the search area, the next search area is smaller than the center address 2 ^N-1 -1w. change the region ^{0w~2 N-1} -2w, when large changes the next search area in the middle of the address ^{2 N-1} greater than -1W region ² N-1 ^w~2 N -1w. As in this example, the search area is preferably narrowed to ½ for each repeated step.

Next, the search circuit compares the entry data stored at the center address of the changed (narrowed) search area with the search data (Search Entry). That is, when the search area is changed from 0w to 2 ^N-1 -2w in the previous stage, the entry data stored in the central address 2 ^N-2 -1w is compared with the search data (Search Entry). when the search area is changed to ² N-1 ^w~2 N ^-1w compares the entry data stored in the center of the address 3 × ^{2 N-2} -1w a search data (search entry).

  The search circuit repeats this operation until the search area cannot be divided, and outputs the value of the address storing the entry data that matches the search data (Search Entry) in the process as a hit address, and there is no matching entry data Is output as a miss-hit.

Thus, only one entry data to be compared with the search data is stored at the center address of each search area. The search circuit searches the entry data that matches the search data (Search Entry) while sequentially repeating the comparison and the change of the search area. Therefore, even when searching all areas, the search circuit compares N times. It is because it is enough to do. As a result, it is possible to provide an associative memory in which the number of entry data to be compared is reduced to the logarithm (log ₂ 2 ^N = N) of the total number of entry data (2 ^N ) and power consumption is reduced.

  Here, unlike the conventional CAM, the above memory may be a simple RAM that can read and write data by designating an address. This is because the comparison with the search data (Search Entry) is performed in the search circuit. Although an example in which a plurality of entry data are sorted in ascending order and stored in the order of memory addresses has been described, it is only necessary that the sorting method and the comparison method in the search circuit correspond to each other. When sorting / comparing as numerical values, it is possible to perform a size comparison assuming that the numerical values are expressed in complement, or to compare them as absolute values. Further, some order other than numerical values (for example, alphabetical order) may be defined, and comparison of magnitude relations in the order may be adopted. Further, the entry data may include a plurality of the same numerical values.

When the number of entry data is less than the size of the memory address area (0w to ^2N- 1w in the above example), each entry data is provided with a valid flag (Valid flag) to manage validity / invalidity. , Invalid entry data is excluded from comparison. Thereby, even when the number of entry data is small, search data (Search Entry) can be searched. The valid flag (Valid flag) may be provided in each CAM in the following embodiments. However, in order to facilitate understanding of the configuration and operation of the entire CAM, the valid flag (Valid flag) Description of is omitted.

  A more specific configuration example of the CAM that performs binary search on the SRAM according to the first embodiment will be described.

  FIG. 1 is a block diagram illustrating a configuration example of a CAM that performs a binary search on an SRAM. N = 4 and entry data was 128 bits × 16 words.

  The above-described memory is divided and mounted on five SRAMs 1_1 to 1_5, and a pipeline is configured as a whole. Input search data (Search Entry) is a shift register composed of 128-bit registers 6_1 to 6_8, and is sequentially transferred to the subsequent pipeline stage. The search circuit described above is configured by comparison circuits 3_1 to 3_5 that compare search data (Search Entry) with entry data. Functions of the comparison circuits 3_1 to 3_5 will be described later. Further, 128-bit registers 6_1 to 6_8 and flip-flops (FF) 7_1 to 7_8 are provided for timing adjustment.

  The first-stage SRAM 1_1 is an SRAM of only one word and stores only the entry data of the seventh word (7thw). SRAM1_2 is a two-word SRAM, and stores entry data of the third word (3rdw) and the eleventh word (11thw). SRAM1_3 is a 4-word SRAM, and stores entry data of a first word (1stw), a fifth word (5thw), a ninth word (9thw), and a thirteenth word (13thw). The SRAM 1_4 is an 8-word SRAM, the 0th word (0thw), the 2nd word (2ndw), the 4th word (4thw), the 6th word (6thw), the 8th word (8thw), and the 10th word (10thw). The entry data of the 12th word (12thw) and the 14th word (14thw) are stored. The SRAM 1_5 is an SRAM of only one word, and stores only the entry data of the 15th word (15thw). Since SRAM1_1 and SRAM1_5 are 1-word SRAMs, no address is required, and each may be configured with simple registers. Each wiring shown in FIG. 1 is composed of one-bit or plural-bit wiring, but the bus notation is omitted in the drawing.

  The operation of the CAM shown in FIG. 1 will be described.

  The 16 entry data are sorted in advance in ascending order, for example, and stored in the above-described words of the five SRAMs 1_1 to 1_5. Larger entry data is stored in a word having a larger word number, the largest entry data is stored in the 15th word (15thw) of SRAM1_5, and the smallest entry data is stored in the 0th word (0thw) in SRAM1_4. Here, the seventh word (7thw) stored in the first-stage SRAM 1_1 is the center address of the 0th word (0thw) to the 15th word (15thw) as the search area.

  The search data (Search Entry) is compared with the entry data of the seventh word (7thw) stored in the SRAM 1_1 by the comparison circuit 3_1. FIG. 2 is an explanatory diagram illustrating an operation example of the comparison circuit 3_1. Since the comparison circuit 3_1 is the first stage, “0” indicating mismatch is input as the comparison result of the previous stage, and “7” is input as the address of the entry data to be compared. At this time, the comparison result between the search data (Search Entry) and the entry data of the seventh word (7thw) input from the SRAM 1_1 is “small”, “large”, and “match”. When the comparison result is “small”, the comparison circuit 3_1 indicates “0” indicating an inconsistency and an address “3”, and when the comparison result is “large”, the comparison circuit 3_1 indicates “0” indicating an inconsistency and an address “11”. When “match”, “1” indicating the match and address “7” are output. When the comparison result is “small”, the search area is changed to a range smaller than the seventh word (7thw), so the search area becomes 0 to 6 and the center address “3” is output. When the comparison result is “large”, the search area is changed to a range larger than the seventh word (7thw), so the search area becomes 8 to 15 and the center address “11” is output. As described above, as a result of one comparison, the search area is narrowed to ½, and the center address of the target search area is output to the next stage.

  The address output from the comparison circuit 3_1 is input to the SRAM 1_2, and the entry data of the third word (3rdw) or the eleventh word (11thw) is read out and supplied to the comparison circuit 3_2 through the register 6_9. The comparison result and address output from the comparison circuit 3_1 are supplied to the comparison circuit 3_2 via the flip-flops 7_1 and 7_2. FIG. 3 is an explanatory diagram illustrating an operation example of the comparison circuit 3_2. The comparison circuit 3_2 receives “1” indicating coincidence or “0” indicating disagreement as the comparison result of the preceding stage, and “3” or “11” is input as the address of the entry data to be compared. .

  When the input address from the previous stage is “3”, the entry data of the third word (3rdw) is read from the SRAM 1_2 and compared with the search data (Search Entry) by the comparison circuit 3_2. When the comparison result is “small”, the comparison circuit 3_2 indicates “0” indicating an inconsistency and an address “1”, and when the comparison result is “large”, the comparison result is “0” and an address “5”. When “match”, “1” indicating the match and address “3” are output.

  When the input address from the previous stage is “11”, the entry data of the eleventh word (11thw) is read from the SRAM 1_2 and compared with the search data (Search Entry) by the comparison circuit 3_2. When the comparison result is “small”, the comparison circuit 3_2 indicates “0” indicating an inconsistency and an address “9”. When the comparison result is “large”, the comparison circuit 3_2 indicates “0” indicating an inconsistency and an address “13”. When “match”, “1” indicating the match and address “11” are output.

  When the input from the previous stage is “match” and the address is “7”, the comparison circuit 3_2 outputs “1” indicating that the comparison result is “match” and the address “7” without change.

  In this way, as a result of the second comparison, the search area is further reduced to 1/2 and 1/4 of the whole, and the center address of the target search area among the four search areas is output to the next stage. The

  The address output from the comparison circuit 3_2 is input to the SRAM 1_3, and the entry data of the first word (1stw), the fifth word (5thw), the ninth word (9thw), or the thirteenth word (13thw) is read. The signal is supplied to the comparison circuit 3_3 through the register 6_10. The comparison result and address output from the comparison circuit 3_2 are supplied to the comparison circuit 3_3 via the flip-flops 7_3 and 7_4. FIG. 4 is an explanatory diagram illustrating an operation example of the comparison circuit 3_3. The comparison circuit 3_3 receives “1” indicating coincidence or “0” indicating disagreement as the comparison result of the preceding stage, and “1”, “5”, “9” as addresses of entry data to be compared as addresses. Alternatively, “13” or “3”, “7”, or “11” is input as the address of the matched entry data when it matches the search data (Search Entry) in the previous stage.

  When the input address from the previous stage is “1”, the entry data of the first word (1stw) is read from the SRAM 1_3 and compared with the search data (Search Entry) by the comparison circuit 3_3. When the comparison result is “small”, the comparison circuit 3_3 indicates “0” indicating an inconsistency and an address “0”, and when the comparison result is “large”, the comparison circuit 3_3 indicates “1” indicating an inconsistency and an address “2”. When “match”, “1” indicating the match and address “1” are output.

  When the input address from the previous stage is “5”, the entry data of the fifth word (5thw) is read from the SRAM 1_3 and compared with the search data (Search Entry) by the comparison circuit 3_3. When the comparison result is “small”, the comparison circuit 3_3 indicates “0” indicating an inconsistency and an address “4”, and when the comparison result is “large”, the comparison circuit 3_3 indicates “1” indicating an inconsistency and an address “6”. When “match”, “1” indicating the match and address “5” are output.

  When the input address from the previous stage is “9”, the entry data of the ninth word (9thw) is read from the SRAM 1_3 and compared with the search data (Search Entry) by the comparison circuit 3_3. When the comparison result is “small”, the comparison circuit 3_3 indicates “0” indicating the mismatch and the address “8”, and when the comparison result is “large”, the comparison circuit 3_3 indicates “1” and the address “10” indicating the mismatch. When “match”, “1” indicating the match and address “9” are output.

  When the input address from the previous stage is “13”, the 13th word (13thw) entry data is read from the SRAM 1_3 and compared with the search data (Search Entry) by the comparison circuit 3_3. When the comparison result is “small”, the comparison circuit 3_3 indicates “0” indicating the mismatch and the address “12”, and when the comparison result is “large”, the comparison circuit 3_3 indicates “1” and the address “14” indicating the mismatch. When “match”, “1” indicating the match and address “13” are output.

  When the input from the previous stage is “match” and the address is “3”, “7” or “11”, the comparison circuit 3_2 remains as it is, and the address “1” indicating “match” is input as “ 3 "," 7 "or" 11 "is output.

  As described above, as a result of the third comparison, the search area is further reduced to 1/2 and 1/8 of the whole, and the center address of the target search area among the eight search areas is output to the next stage. The

  The address output from the comparison circuit 3_3 is input to the SRAM 1_4, and the second word (2ndw), the fourth word (4thw), the sixth word (6thw), the eighth word (8thw), the tenth word (10thw), The entry data of the 12th word (12thw) or the 14th word (14thw) is read and supplied to the comparison circuit 3_4 through the register 6_11. The comparison result and address output from the comparison circuit 3_3 are supplied to the comparison circuit 3_4 via the flip-flops 7_5 and 7_6. FIG. 5 is an explanatory diagram illustrating an operation example of the comparison circuit 3_4. The comparison circuit 3_4 receives “1” indicating coincidence or “0” indicating disagreement as the comparison result of the preceding stage, and “2”, “4”, “6” as addresses of entry data to be compared as addresses. , “8”, “10”, “12” or “14”. Alternatively, if the comparison circuit 3_4 matches the search data (Search Entry) at the previous stage, “1”, “3”, “5”, “7”, “ “9”, “11” or “13” is input.

  At this stage, since the search area is in units of one word, the search area cannot be narrowed thereafter. When the entry data specified by the address input from the previous stage matches the search data (Search Entry), the address at that time is output together with “1” indicating the match, and the input from the previous stage matches with “match” If the current address is input, the input address together with “1” indicating coincidence is output as it is. At this stage, the comparison between the entry data from the 0th word (0thw) to the 14th word (14thw) and the search data (Search Entry) is substantially completed.

  FIG. 6 is an explanatory diagram illustrating an operation example of the comparison circuit 3_5. When the output from the comparison circuit 3_4 in the previous stage is “0” indicating a mismatch, the comparison circuit 3_5 includes the entry data of the 15th word (15thw) stored in the SRAM 1_5, the search data (Search Entry), In the case of coincidence, “15” is output as the address, and in the case of non-coincidence, “miss hit” representing the non-coincidence is finally output. When the output from the comparison circuit 3_4 in the previous stage is “1” indicating coincidence, the input address is output as it is.

As described above, each time the comparison operation by the comparison circuits 3_1 to 3_5 is performed in one stage, the search range is narrowed to ½. Therefore, when the number of comparisons is 2 ^N , the logarithm with 2 as the base is The obtained log ₂ 2 ^N = N. In the conventional BCAM that compares the search data with all entries, the number of comparisons is 2 ^N equal to the number of entries. Therefore, in the CAM according to the present embodiment, the number of comparisons can be suppressed to N / ^2N . If the power consumption of the content addressable memory (CAM) is approximately proportional to the number of comparisons, the power consumption of the CAM of this embodiment can be suppressed to N / 2 ^N of the conventional BCAM. Note that this is a theoretical approximation, and when mounted on an actual circuit element, an error corresponding to the mounting state occurs. For example, in the above example, the number of comparisons is 5 for N = 4. On the other hand, since the comparison circuit is composed of a normal logic circuit, the power consumed by one comparison operation may be larger than that of the comparison circuit in the cell. Rather it is suppressed.

  The CAM shown in this embodiment is preferably formed on a single semiconductor substrate together with other control circuits, and integrated on a single chip LSI (Large Scale Integrated Circuit). Such an LSI is formed on a silicon substrate, for example, using a known complementary metal-oxide-semiconductor field effect transistor (CMOS) semiconductor manufacturing technique. The CAM shown in the present embodiment is provided as a macro cell library in a design environment for designing a system LSI, or an appropriate macro cell can be generated by freely specifying the number of bits and the number of entries. It may be provided as a compiler. The CAM providing method described above is not limited to the present embodiment, and is similarly applicable to the other embodiments 2 to 6.

[Embodiment 2] <CAM performing two-stage search>
The CAM (hereinafter abbreviated as BSRAM) that performs a binary search on the SRAM shown in the first embodiment has a remarkable effect of reducing power consumption as described above, but all entry data are sorted. Is the premise. Therefore, partial writing that overwrites old entry data with the latest entry data is not permitted, and an operation that reads, sorts, and rewrites all necessary entry data is necessary. On the other hand, the conventional CAM (BCAM) compares the search data with all the entry data at the same time, so that the entry data can be rewritten (added or overwritten) freely.

  In the second embodiment, a BCAM functioning as a search cache is provided before the BSRAM, and a two-stage search is performed. New entry data is sequentially written to the BCAM, sorted when the number of BSRAM entries is reached, and transferred to the BSRAM. In search of search data, first, BCAM is set as a search target, and BSRAM is set as a search target when a miss occurs in BCAM. Thereby, rewriting (additional writing, overwriting) of entry data can be performed freely, and power consumption can be suppressed. By configuring a CAM that performs a two-stage search by combining one BCAM and a number of BSRAMs, the effect of reducing power consumption becomes more prominent.

  FIG. 7 is a block diagram illustrating a configuration example of a CAM that performs a two-stage search.

  The CAM 500 that performs a two-stage search includes one binary CAM (BCAM) 200 that functions as a search cache, and CAMs (BSRAM) 100_1 to 100_m that perform a binary search on m SRAMs that function as a main search. Consists of. The BCAM 200 is, for example, 256 entries. When one search data is input, the BCAM 200 compares simultaneously with a maximum of 256 entry data already stored, and indicates an address or mismatch that stores matching entry data. Outputs “Mishit”. In the BCAM 200, each entry has a valid flag (Valid flag), and only Valid entry data is targeted for search, so the result of comparison with Invalid entry data is ignored. New entry data can be written in the Invalid entry, and this writing can be executed in parallel with the search operation. Each of the BSRAMs 100_1 to 100_m has the same 256 entries as the BCAM 200, and when one search data is input, the stored 256 entry data are compared with the algorithm described in the first embodiment. , The address for storing the matching entry data or “mishit” indicating the mismatch is output.

  Entry data input to the CAM 500 is written to the BCAM 200. When entry data is written in all 256 entries of the BCAM 200, that is, when FULL is reached, the 256 entries are read from the BCAM 200, sorted, and transferred to one of the BSRAMs 100_1 to 100_m (900). All 256 entries of the BCAM 200 are set to invalid, and entry data writing is permitted. Further, when 256 new entry data are written in the BCAM 200, the 256 entries are read again, sorted and transferred to another one of the BSRAMs 100_1 to 100_m (900). In this way, 256 entry data written to the BCAM 200 are sorted by 256 and sequentially transferred to the BSRAMs 100_1 to 100_m. The sort and transfer operations may be executed by providing a dedicated logic circuit 900 for performing the operations, or may be executed by software as one of the tasks of the processor that controls the CAM 500.

  When search data is input, the BCAM 200 searches (searches), and when the BCAM 200 outputs a miss hit, that is, entry data that matches the input search data is included in the entry data stored in the BCAM 200. If not found, the search data is sent to one of the BSRAMs 100_1 to 100_m and searched. The search order is BCAM 200 first, and after that, among the BSRAMs 100_1 to 100_m, it is preferable to set the search target in order from the BSRAM to which entry data has been transferred recently. Since recently written entry data has a higher probability of hitting, the time to hit is shortened, and power consumption can be reduced by not performing a search after the hit.

  As described above, when the BCAM 200 functioning as a search cache is hit, the latency is small, and when there is no hit, the BSRAMs 100_1 to 100_m are sequentially searched, thereby providing a CAM with a large capacity and low power consumption. .

  For example, by setting m = 255, the entire CAM 500 has a large capacity of 64K (65536) entries. When this is constituted by one BinaryCAM, a comparison operation with 65536 entry data occurs simultaneously for one search data, and the power associated therewith is consumed. On the other hand, in the CAM 500 of the second embodiment, the number of entry data to be compared with respect to one search data even when all areas of all the CAMs (BCAM 200 and BSRAM 100_1 to 100_m) are searched. Is a total of 4336: 256 in the BCAM and 16 × 255 in the BSRAMs 100_1 to 100_m, which can be reduced to about 1/15. If a hit occurs in the middle, the subsequent comparison can be canceled, so that it can be further reduced.

  In the present embodiment, the number of entries of each CAM is 256, and in the above description, an example is shown in which m = 255 and a 64K entry CAM is configured as a whole. it can. Further, although the number of entries in BCAM 200 is the same as the number of entries in each BSRAM, it may be more than the number of entries in each BSRAM. By making the number of entries in the BCAM 200 larger than the number of entries in each BSRAM, it is possible to write new entry data to the BCAM 200 even during a period in which entry data is transferred from the BCAM 200 to the BSRAM.

[Third Embodiment] <CAM (Complementary Search Cache) that Performs Two-Step Search>
7 has only one BCAM 200 that functions as a search cache. Depending on the configuration of the BCAM 200, the BCAM 200 becomes FULL and the entry data is transferred to the BSRAM during the period. In some cases, writing of new entry data to the BCAM 200 is restricted or prohibited. In order to solve such a problem, the search cache is composed of two BCAMs 200_1 and 200_2 that operate in a complementary manner.

  FIG. 8 is a block diagram illustrating another configuration example of the CAM 500 that performs a two-stage search.

  The CAM 500 includes two complementary BCAMs 200_1 and 200_2 that function as search caches, and CAMs (BSRAM) 100_1 to 100_m that perform binary search on m SRAMs that function as main searches. . Each of the BCAMs 200_1 and 200_2 has, for example, 256 entries, and operates in the same manner as the BCAM 200 in the second embodiment. BSRAMs 100_1 to 100_m are similar to BSRAMs 100_1 to 100_m in the second embodiment.

  Entry data input to the CAM 500 is written to one of the BCAMs 200_1 and 200_2, for example, the BCAM 200_2. When the BCAM 200_2 becomes FULL, all entries are read from the BCAM 200_2, sorted, and transferred to one of the BSRAMs 100_1 to 100_m (902). During this read / sort / transfer period, the other BCAM 200_1 is a target for writing entry data that is newly input. When the BCAM 200_1 becomes FULL, all entries are read from the BCAM 200_1, sorted, and transferred to one of the BSRAMs 100_1 to 100_m (901). Is the target of writing. In this way, the BCAMs 200_1 and 200_2 are alternately subjected to writing of input data to be input and are subjected to reading, sorting, and transfer, so that writing of new entry data is not waited for.

  As for the search operation, BCAMs 200_1 and 200_2 are alternately searched, and if any of them becomes a miss hit, BSRAMs 100_1 to 100_m as the main search are set as search targets. Since the details of the search operation are the same as those in the second embodiment, description thereof is omitted.

[Embodiment 4] <Search order>
In the CAM 500 shown in the second and third embodiments, the search order between the BSRAMs 100_1 to 100_m, which is the main search, can be flexibly changed. Here, when applied to an application system in which entry data is frequently rewritten, it has been found that newly written entry data tends to have a higher probability of hit. Therefore, by setting the newly written entry data as a search target with higher priority, it is possible to hit faster, and by controlling so that the subsequent search is not performed at the time of the hit, power consumption is further increased. Can be reduced.

  FIG. 9 is an explanatory diagram showing an example of the operation of a CAM that performs a two-stage search. The BSRAM number is shown in the horizontal direction, and the pipeline stage is shown in the vertical direction. In order to facilitate understanding, the number of BSRAMs m = 8 and numbers 0 to 7 are given. One stage of the pipeline stage represents a period for writing or searching in one entire BSRAM, and the stages from the first (1st) to the eighth (8th) are shown. “W” indicates an entry data write operation, that is, an entry data transfer operation with sorting from the search cache (BCAM 200 or BCAM 200_1 and 200_2). “Data0” to “data7” indicate that a search operation using the data as search data is being executed.

  The entry data write “W” proceeds to the BSRAM 7 of the seventh stage in the order of the BSRAM 0 of the first stage and the BSRAM 1 of the second stage, and although not shown, the process returns to the BSRAM 0 and is repeated thereafter.

  In the first stage, BSRAM0 is to be written, and BSRAM7 that has been written immediately before is storing the latest entry data. Therefore, the first search object after the search data data0 is miss-hit in the search cache is BSRAM7. In the case of a miss-hit in the BSRAM 7 as well, the BSRAM 6 is searched in the second stage. If the miss-hit continues, the BSRAM 5 in the third stage, the BSRAM 4 in the fourth stage, the BSRAM 3 in the fifth stage, the BSRAM 2 in the sixth stage, the seventh stage BSRAM1 and BSRAM0 in the eighth stage are sequentially searched. Assuming the above-mentioned writing order, the larger the number assigned to the BSRAM, the more new entry data is stored.

  In the second stage, BSRAM1 is the object of writing, and BSRAM0, which has been written immediately before, stores the latest entry data. Therefore, the first search target after a miss hit in the search cache for the search data data1 is BSRAM0. Thereafter, BSRAM7, BSRAM6, BSRAM5, BSRAM4, BSRAM3, BSRAM2, and BSRAM1 are continued. The same applies to the third and subsequent stages.

  Here, in the fifth stage, the BSRAM 4 is a write target, and the BSRAM 4 to which writing has been completed immediately before stores the latest entry data. Therefore, the search data data4 after the miss hit in the search cache is stored. It is the first search target. However, the same fifth stage is the timing at which the search for the search data data0 is also executed. As described above, two search data data4 and data0 are simultaneously input to one BSRAM. The same phenomenon also occurs in the sixth stage BSRAM2 and BSRAM4, the seventh stage BSRAM1, BSRAM3 and BARAM5, and the eighth stage BSRAM0, BSRAM2, BSRAM4 and BSRAM6.

  In this case, the following three types of solutions can be taken. The first solution is to make the search operation wait. For example, in the fifth stage, the problem can be solved by waiting for the search operation of the search data data4 or data0. The second solution is to stop the search operation for one search data. The search operation for data 0 in the BSRAM 3 may be meaningless as a search target in the fifth stage next to the BSRAM 4 in the fourth stage because the entry data of the BSRAM 3 in the fourth stage is rewritten. In this case, the search result of data 0 is set to “miss hit”, and the subsequent search is stopped, so that the search data contention problem is solved. A third solution is to configure the BSRAM so that a plurality of search data can be searched simultaneously in parallel.

  FIG. 10 is a block diagram illustrating a configuration example of a CAM that performs a binary search on a 2-input search entry. The difference from the CAM that performs a binary search on the SRAM shown in FIG. 1 includes dual-port SRAMs 2_2 to 2_4 instead of the SRAMs 1_2 to 1_4, and further includes comparison circuits 4_1 to 4_5 in addition to the comparison circuits 3_1 to 3_5. Is a point. Registers 6_12 to 6_22 and flip-flops 7_9 to 7_16 constituting the pipeline are also provided in parallel. The two search data Search Entry 1 and Search Entry 2 are simultaneously compared with the entry data in parallel by the comparison circuits 3_1 to 3_5 and the comparison circuits 4_1 to 4_5. The entry data to be compared is read independently from each port of the dual port SRAMs 2_2 to 2_4. Each wiring shown in FIG. 10 is composed of one or a plurality of bits, but the bus notation is omitted in the drawing.

  The operations other than the point that enables the parallel operation are the same as the operations described in the first embodiment with reference to FIG.

[Embodiment 5] <BCAM with sort function>
As described above, the CAM that performs the binary search on the SRAM shown in FIGS. 1 and 10 needs to sort and write the entry data.

  FIG. 11 is a block diagram illustrating a configuration example of the CAM 300 with a sorting function. In the CAM performing the two-stage search shown in FIGS. 7 and 8, the BCAM 200 or 200_1 and 200_2 functioning as the searcher cache is changed to the CAM 300 with sort function shown in FIG. 902 is simplified.

  The CAM 300 with a sort function includes a BCAM array 201 that uses a cell with a comparison function having a size comparison function in addition to a match, rank registers 9_1 to 9_N provided corresponding to each entry, and a comparison result by a cell with a comparison function And a logic circuit (Logic) 8 for writing appropriate values to the rank registers 9_1 to 9_N. The BCAM array 201 can read / write data by inputting an address in the same way as a normal memory (RAM mode), and can input search data (Search Data) to store matching entry data. Can be output as a hit address (CAM mode).

  The CAM 300 with a sort function appropriately updates all ranks stored in the rank registers 9_1 to 9_N each time new entry data is written. When new entry data is input, the BCAM array 201 using the cell with a comparison function compares the input new entry data with the entry data held in each entry in the BCAM array 201. Then, a match and large / small comparison result is output for each entry. The logic circuit (Logic) 8 appropriately updates all ranks stored in the rank registers 9_1 to 9_N based on the comparison result for each entry. At this time, an example of the algorithm for updating the rank will be described as “operation of the CAM 300 with sort function”, but the algorithm is not limited to the example and is arbitrary.

  Each wiring shown in FIG. 11 is composed of a plurality of bits, but the bus notation is omitted in the drawing. For example, the cell described in FIG. 14 or FIG. 16 or Patent Document 1 can be used as the cell with a comparison function having the matching and size comparison functions. Although the detailed configuration and operation will be described later, a comparison is made between a value stored for each entry and a value input from the search entry, and coincidence or magnitude relations are simultaneously output in parallel.

  The operation of the CAM 300 with sort function will be described.

  The data of all entries and the values of the rank registers 9_1 to 9_N corresponding to the data are initialized to 0.

  The data to be written is compared / matched with all other entry data regardless of whether or not the entry data has already been written.

  For a write non-target entry, when the write target data is “smaller” than the entry data stored in the write non-target entry, the corresponding rank register is incremented by 1 (+1). If the rank of the entry not to be written is higher than the original rank of the entry to be written, the entry is decremented by 1 (-1). The rank of the write target entry is written in the rank register with the number of the write target data being “larger” than the entry data of each entry as a rank as a result of comparison with each entry.

  Thus, every time entry data is written, the order of all entries is appropriately updated, and the correct order is always maintained.

  Here, in the above algorithm, the same rank is assigned to the entry data having the same value. On the other hand, as a result of comparison with each entry, the number of data to be written is replaced with the number of data that is “larger” than the entry data of each entry. By writing the entry rank in the corresponding rank register, it is possible to give different ranks to the entry data having the same value. Thus, the order update algorithm by the logic circuit (Logic) 8 can be variously changed.

  FIG. 12 is a timing chart illustrating an operation example of the CAM with sort function. In order to help understanding, the number of entries will be described as four. The horizontal axis represents time, and the valid flag (Valid flag), entry data, and value of the rank register of each entry are shown in order from the top in the vertical axis direction.

  At time t0, the data and rank of all entries are initialized to zero.

  Data “1” is written to entry 0 at time t1. Since the comparison results of the entries not to be written are all “large”, “3”, which is the number of “large”, is written to the rank register 0.

  Data “3” is written to entry 1 at time t2. Since the comparison results of the entries not to be written are all “large”, “3”, which is the number of “large”, is written to the rank register 1. The entry 0 that is not to be written is decremented by 1 because the original rank “3” of the entry 0 that is not to be written, which is the value of the rank register 0, is larger than the original rank “0” of the entry 1 to be written. Thus, the value of the rank register 0 is “2”.

  Data “2” is written to entry 2 at time t3. The comparison result of the entry not to be written is “large” for entries 0 and 3 and “2”, which is “large” because entry 1 is “small”, and is written to the rank register 2. The entry 0 not to be written is decremented by 1 because the original rank “2” of the entry 0 not to be written, which is the value of the rank register 0, is larger than the original rank “0” of the entry 2 to be written. Thus, the value of the rank register 0 is “1”. For entry 1 that is not to be written, an operation of increasing (+1) the value of the corresponding rank register 1 and an operation of decrementing (-1) the counter register 1 are performed to cancel each other. "No change. Since the write target data “2” is “smaller” than the entry data “3” stored in the non-write target entry, the rank of the corresponding rank register 1 is increased by 1 (+1) while the write target data “2” is increased. This is because the original rank “3” of the entry 1 not to be written, which is the value of the rank register 1, is larger than the original rank “0” of the entry 2, so that 1 is reduced (−1).

  Data “0” is written to entry 3 at time t4. Since the comparison result of the entry not to be written is “small” in the entries 0 to 2, “0” which is the number of “large” is written in the rank register 3. For entries 0, 1, and 2 that are not to be written, an operation of increasing (+1) the order of the corresponding rank registers 0, 1, and 2, and an operation of decreasing (-1) are canceled out. The values of the rank registers 0, 1, and 2 remain “1”, “3”, and “2”. Since the write target data “0” is “smaller” than the entry data “1”, “3”, and “2” stored in each non-write target entry, the corresponding rank registers 0, 1, and 2 While the value is incremented by 1, the original ranks “1”, “3” and “2” of the non-write entries 0, 1 and 2 are larger than the original rank “0” of the write target entry 3. This is because each one is reduced.

  As described above, every time new entry data is written, the rank of all entries is appropriately updated, and the correct rank is always maintained.

  FIG. 13 is a block diagram illustrating another configuration example of the CAM 300 with a sorting function. Unlike the CAM shown in FIG. 11, the rank registers 9_1 to 9_N are configured by the CAM 202, and are configured to be able to search for an address by inputting the rank. The address input to the BCAM 201 includes a selector 11 that selectively switches between a sort address output from the CAM 202 functioning as a rank register and a logical address input from the outside. By sequentially inputting the rank from the input address, the corresponding entry is output from the BCAM 201 corresponding to the rank.

  In the CAM 300 with a sort function shown in FIG. 11, the rank value is sequentially output from the rank registers 9_1 to 9_N, and the entry data of the corresponding entry is sequentially read from the BCAM 201 in the RAM mode, thereby corresponding to the entry data. The order is read out. By writing the corresponding entry data in the BSRAM entry using the rank as the BSRAM address, the sorted entry data can be written in the BSRAM.

  In the CAM 300 with a sorting function shown in FIG. 13, the corresponding entry data can be read from the BCAM 201 in the order specified by sequentially inputting the ranks to the input addresses, so that the BSRAM performs random access in writing the entry data. There is no need to make the configuration possible. Further, since the CAM 300 with a sort function shown in FIG. 13 can read the corresponding entry by randomly specifying the rank, in addition to the search cache of the CAM 500 that performs the two-stage search shown in the second and third embodiments. Can be applied.

  The configuration and operation of a cell with a comparison function that has a function of comparing size in addition to coincidence will be described.

  FIG. 14 is a circuit diagram showing a configuration example of the memory cell 10 applicable to the CAM with sort function, and FIG. 15 is an explanatory diagram showing a truth table showing the operation of the memory cell.

  In the memory cell 10, an inverter constituted by an inverter constituted by an N-channel transistor MN1 and a P-channel transistor MP1 constitutes a memory element with their outputs connected to other inputs. The output of the inverter composed of MN1 and MP1 is connected to the bit line BL via MN3 controlled by the word line WL, and the output of the inverter composed of MN2 and MP2 is controlled by the word line WL. Is connected to the inverted bit line / BL via the MN4. BL and / BL constitute a pair of bit lines which are logically opposite in polarity and complementary. The logical inversion is originally distinguished by the “upper line” shown above the signal line name, but “/” (slash) is substituted due to the limitation of the font that can be used in the specification. One bit of the search data (Search Data) is input to the complementary search data line pair SL and / SL. SL is connected to the gate of MN5, and / SL is connected to the gate of MN6. The gate of MP3 is connected to the output of the inverter composed of MN1 and MP1, the gate of MP4 is connected to the output of the inverter composed of MN2 and MP2, and the drains of MP3 and MN4 are both of the composite logic gate 12. Input to non-inverting input terminal. The non-inverting input terminal of the composite logic gate 12 is precharged to VDD through MN7 controlled by the precharge enable signal PE, and a discharge path through MP3 and MN5 or MP4 and MN6 is formed. The non-inverting input terminal of the composite logic gate 12 is discharged to a low level when either MP3 and MN5 or MP4 and MN6 are both on. The case where both MP3 and MN5 or MP4 and MN6 are turned on is a case where the held data and the search data do not match. The output of the composite logic gate 12 is the inversion logic / ML of the match line ML indicating “match”, and the match line pre / ML from the adjacent cell on the upper bit side is input to the inversion input terminal of the composite logic gate 12. Have been entered. When the match line pre / ML input from the upper bit side is low, “match” is detected in all the bits higher than the cell 10, and when “match” is detected in the cell 10 as well. , Low is output from the match line / ML.

  The magnitude determination line BG outputs a high “1” when the data held in the cell 10 is larger than the search data, a low “0” when the data is smaller, and a high impedance (HiZ) when the data match. The size determination line BG is short-circuited between a plurality of cells 10 constituting the same entry, and the bit of the entry data held from the cell 10 which does not match for the first time when compared in order from the upper bit. Output via MP5, MP6 and MN8. As a result, it is possible to compare the size of the entry data of a plurality of bits.

  FIG. 16 is a circuit diagram showing another configuration example of the memory cell 10 applicable to the CAM with sort function, and FIG. 17 is an explanatory diagram showing a truth table representing the operation of the memory cell. The circuit shown in FIG. 15 is a dynamic circuit, whereas the circuit shown in FIG. 16 is a full static circuit. Therefore, the precharge enable PE is not required, and the BG indicating the size comparison result is input with the input preBG from the adjacent cell and is output as BG in the subsequent stage. MP7 to MP19 are provided in place of MN7 for controlling precharge, and composite logic gates 13 and 14 are provided in place of MP5, MP6 and MN8. The realized logic is the cell shown in FIG. 10 is the same.

  In the cell with a comparison function having a matching and size comparison function used in the BCAM 201 shown in FIG. 11 and FIG. 13, a comparison is made between the value stored for each entry and the value input from the search entry. A cell is used that can determine and output a match or magnitude relationship in parallel. It is not limited to the cells shown in FIGS. 14 and 16 described above, and other circuit configurations may be used. For example, the cell described in Patent Document 1 can be used.

[Embodiment 6] <CAM with high throughput and low power consumption>
FIG. 18 is a block diagram illustrating a configuration example of a CAM that forms a complementary search cache with a BCAM with a sort function and includes a plurality of BSRAMs to perform a two-stage search.

  The CAM 500 includes two complementary BCAMs 300_1 and 300_2 that function as search caches, and CAMs (BSRAM) 100_1 to 100_m that perform binary search on m SRAMs that function as main searches. . The BCAMs 300_1 and 300_2 are BCAMs with a sort function as exemplified in the fifth embodiment, and each has, for example, 256 entries.

  Since the entry data input to the CAM 500 is alternately written to the input data BCAM 300_1 and 300_2, and is read, sorted, and transferred, new entry data is provided as in the third embodiment. There is no waiting for writing. Here, since the BCAMs 300_1 and 300_2 are BCAMs with a sorting function, as exemplified in the fifth embodiment, the entry data can be read in the sorted order or together with the corresponding ranks. In the transfer operation or transfer circuits 911 and 912, the sort function can be omitted or greatly simplified.

  Regarding the search operation, the BCAMs 300_1 and 300_2 are alternately searched, and if any of the BCAMs 300_1 and 300_2 become a miss hit, the BSRAMs 100_1 to 100_m, which are the main search, are searched. Since the details of the search operation are the same as those in the second embodiment, description thereof is omitted.

  As a result, it is possible to provide a CAM that can achieve both high throughput and low power consumption.

  Although the invention made by the present inventor has been specifically described based on the embodiments, it is needless to say that the present invention is not limited thereto and can be variously modified without departing from the gist thereof.

  For example, the memories constituting the BSRAMs 100_1 to 100_m have been described as SRAMs, but need not be limited to SRAMs. For example, a RAM using other storage elements may be used, and in a system in which entry data is fixed, an electrically rewritable ROM (Read Only Memory) or a non-rewritable ROM may be used. .

1 RAM
2 2-port RAM
3, 4 Comparison circuit 5 Address decoder (ADR)
6 registers (128b reg.)
7 Flip-flop (FF)
8 logic circuit 9 rank register 10 memory cell 11 selector 12 logic gate 100 CAM (BSRAM) for performing binary search on SRAM
200, 202 Binary CAM (BCAM)
201 BCAM with comparison function
300 BCAM with sort function
500 CAM for two-stage search
900, 901, 902 Operation or circuit for sorting and transferring 911, 912 Transfer operation or transferring circuit

Claims (18)

An associative memory comprising: a memory that receives search data and stores a plurality of entry data; and a search circuit that searches for an address in the memory in which entry data that matches the search data is stored.
The memory can store the entry data in ascending or descending order and associated with addresses.
The search circuit sets the entire address where the plurality of entry data is stored as an initial search area, and compares the search data with the entry data stored at the center address of the search area. An associative memory that outputs the address as a search result and repeats a search operation for narrowing the search area based on a result of size comparison when there is a mismatch. 2. The memory according to claim 1, wherein the memory includes first to first words each having a power of 2 from 1 word to 2 N−1 power, in which each word is associated with a central address of the search area. An N memory (N is a natural number), and the search circuit includes first to Nth comparison circuits provided corresponding to the first to Nth memories,
The comparison circuit reads entry data from a corresponding memory, compares the entry data with the search data, and outputs an address where the entry data is stored and a comparison result to a comparison circuit at a subsequent stage,
The associative memory, wherein the comparison circuit determines an address from which entry data to be compared is read based on an address input from a previous stage and a comparison result.   3. The memory according to claim 2, further comprising a 1-word N + 1-th memory having an address of 2 N-1 and the search circuit is based on a comparison result input from the N-1-th comparison circuit. An associative memory further comprising an (N + 1) th comparison circuit for comparing the search data with entry data stored in the (N + 1) th memory.   The associative memory having the same configuration as the associative memory is a first associative memory, a second associative memory having the same number of entries as the first associative memory, a plurality of the first associative memories, An associative memory further comprising a transfer circuit that reads a plurality of entry data from the second associative memory, rearranges them in ascending or descending order, and transfers them to the first associative memory.   5. The associative memory according to claim 4, comprising two said second associative memories, wherein when the entry data is transferred from one to the first associative memory, the other is to be written with new entry data.   5. When search data is input according to claim 4, first, when the second associative memory is set as a search target and the second associative memory does not hit, among the plurality of first associative memories, An associative memory to be searched in order from the most recently written entry data.   5. The second associative memory according to claim 4, wherein the second associative memory is composed of memory cells having a function of comparing magnitude matches, and is based on a result of comparing each of input data inputted and entry data inputted so far. And a rank storage circuit for obtaining and storing ranks corresponding to a plurality of inputted entry data, and the transfer circuit reads the ranks and entry data in association with each other and rearranges them in the first associative memory. Associative memory to be transferred.   2. The associative memory according to claim 1, wherein the memory includes a plurality of ports that can simultaneously read data from different words by a plurality of addresses, and includes the search circuit in parallel for each of the plurality of ports.   A semiconductor device comprising the content addressable memory according to claim 1 on a single semiconductor substrate. 2 is an associative memory that can store N-th power entry data (N is a natural number) and searches for entry data that matches the input search data,
First to Nth memories having a number of words every power of 2 from 1 word to 2 to the (N-1) th power, N + 1th memory of one word, and first to N + 1th memories are provided corresponding to the first to N + 1th memories. 1 to (N + 1) th comparison circuit,
The first comparison circuit reads entry data from the first memory, compares the search data with a magnitude match, and outputs the comparison result to the second comparison circuit;
The second comparison circuit reads entry data stored in the address of the second memory calculated based on the comparison result input from the first comparison circuit, and compares the search data with a magnitude match And outputting the result of the comparison to the third comparison circuit,
The third to (N-1) th comparison circuits read out the entry data to be compared based on the address where the entry data to be compared by the previous comparison circuit was stored and the comparison result input from the previous stage. Decide the address, read the entry data from the corresponding memory, perform a magnitude match comparison with the search data, and output the result of the comparison to the comparison circuit in the subsequent stage,
The N + 1th comparison circuit compares whether the search data matches the entry data stored in the N + 1th memory,
When there is entry data that matches the search data, the search data is determined based on the number of the memory that stores the matching entry data and the address in the memory where the matching entry data is stored. An associative memory that calculates and outputs what number of entry data matches when the N-th entry data are sorted. In claim 10,
The first memory stores 2 N-1th data out of the 2 N entry data.
The N + 1th memory stores 2Nth data among the 2Nth entry data,
The i-th memory (i is a natural number greater than or equal to 2 and less than N) is the first memory of j × 2 N−i-th entry data, where j is all natural numbers less than 2 to the i power. To entry data other than the entry data stored in the i-1th memory,
An associative memory that outputs, when there is entry data that matches the search data, a value −1 of the power of j × 2 corresponding to the matching entry data.   12. The associative memory according to claim 11, wherein the first to (N + 1) th comparison circuits sequentially operate at different pipeline stages for the same search data.   12. The associative memory having the same configuration as the associative memory is a first associative memory, a second associative memory having the same number of entries as the first associative memory, a plurality of the first associative memories, An associative memory further comprising a transfer circuit that reads a plurality of entry data from the second associative memory, rearranges them in ascending or descending order, and transfers them to the first associative memory.   14. The associative memory according to claim 13, comprising two of the second associative memories, wherein when the entry data is transferred from one to the first associative memory, the other is to be written with new entry data.   The search method according to claim 13, wherein when the search data is input, the second associative memory is first set as a search target, and when no hit occurs in the second associative memory, among the plurality of first associative memories, An associative memory to be searched in order from the most recently written entry data.   14. The second associative memory according to claim 13, wherein the second associative memory is composed of memory cells having a function of comparing magnitude matches, and is based on a result of comparing input data inputted and entry data inputted so far. And a rank storage circuit for obtaining and storing ranks corresponding to a plurality of inputted entry data, and the transfer circuit reads the ranks and entry data in association with each other and rearranges them in the first associative memory. Associative memory to be transferred.   12. The memory according to claim 11, wherein each of the first to Nth memories has a plurality of ports that can simultaneously read data from different words by a plurality of addresses, and the search circuit is arranged in parallel for each of the plurality of ports. Equipped with associative memory.   A semiconductor device comprising the associative memory according to claim 10 on a single semiconductor substrate.

Images