A dual-ported AND-type match-line circuit includes at least one dual-ported dynamic AND gate. The dual-ported dynamic AND gate includes a group of CAM cells and a dual-ported dynamic circuit. A group of CAM cells connected to a dual-ported dynamic circuit and to the GND. The dual-ported dynamic circuit is connected to a group of CAM cells. The dual-ported dynamic circuit includes a setting circuit, a first directing circuit, a second directing circuit, a first AND dynamic output circuit and a second AND dynamic output circuit.

FIELD OF THE INVENTION

The present invention relates to a dual-ported AND-type match-line circuit using in content-addressable memory (“CAM”) and, more particularly, to a dual-ported AND-type match-line circuit using in CAM that can store two look-up tables in single memory array and search two stored look-up tables in each match operation. This invention not only improves the area utilization of the CAM but also enhances the search speed and reduces the power consumption.

DESCRIPTION OF THE RELATED ARTS

The CAM is an important element for a high-speed search engine. The CAM can store data such as S RAM and match input data with stored data. Therefore, the cells of a CAM contain the additional transistors for match operation expect for the transistors for storing data.

The match-line circuit collects the matching results which are generated by CAM cells. The design of the match-line circuit has a major impact on search speed and power consumption. The match-line circuits of CAM include NOR-type match-line circuits and NAND-type match-line circuits. It is generally recognized that NOR-type match-line circuits achieve high search speed but at the expense of high power consumption, while NAND-type match-line circuits are power efficient with the penalty of low speed. A NOR-type match-line circuit is often used in a search engine due to high search speed.

Recently, an AND-type match-line circuit constructed with the pseudo-footless clock-and-data pre-charged dynamic (“PF-CDPD”) logic was proposed to achieve high speed and low power. Referring toFIG. 1, a match-line circuit100of a CAM includes a plurality of PF-CDPD AND gate circuits101each including a plurality of cells102. The evaluation of each PF-CDPD AND gate circuit101in the match-line circuit100is triggered by the evaluated result of previous stage. If there is no data-matched for a PF-CDPD AND gate circuit101, the following PF-CDPD AND gate circuits101will not be evaluated. Therefore, the match-line circuit100has characteristic of low power consumption, such as NAND-type match-line circuit. Since the input of the gate electrode G of the N-type metal oxide semiconductor (“NMOS”)103in each cell102has been determined before the PF-CDPD AND gate circuit101enter evaluation phase. If the input of the gate electrode G of the NMOS103in each cell102of PF-CDPD and gate circuit101is “1” that is, all data stored in the cells of PF-CDPD AND gate circuit101is matched with the input data), the drain electrode D and source electrode S of the NMOS103will be discharge to 0 V, such as pseudo ground. The delay of each PF-CDPD match-line circuit101is almost the same as two inverters. The search speed of match-line circuit can be greatly increased, even higher than that of the NOR-type match-line circuits.

In the design of CAM, the area utilization is also an important design consideration because a CAM cell includes much more transistors than a general random access memory (“RAM”) Because of large area of CAM, the design of search engine can not arbitrarily adopt CAM due to large cost. Therefore, area is often a concern in the design of a CAM. There are attempts to include dynamic cells in a CAM; however, it requires a special process so that they cannot widely be used and can not easily be integrated.

SUMMARY OF THE INVENTION

The primary objective of the present invention is to increase the area utilization and reduce the power consumption of a CAM.

According to the present invention, a dual-ported AND-type match-line circuit includes at least one dual-ported dynamic AND gate. The dual-ported dynamic AND gate includes a group of CAM cells and a dual-ported dynamic circuit. A group of CAM cells connected to a dual-ported dynamic circuit and to the GND. The dual-ported dynamic circuit is connected to a group of CAM cells. The dual-ported dynamic circuit includes a setting circuit, a first directing circuit, a second directing circuit, a first AND dynamic output circuit and a second AND dynamic output circuit.

Other objectives, advantages and features of the present invention will become apparent from the following description referring to the attached drawings.

DETAILED DESCRIPTION OF EMBODIMENT

Referring toFIGS. 2 through 11, there is shown a dual-ported AND-type match-line circuit for improving the area utilization and reducing the power consumption according to the present invention.

A cell of ternary content-addressable memory (“TCAM”) can store “0” “1” and “don't care.” Therefore the area of a TCAM is much larger than that of a binary CAM (“BiCAM”). According to the present invention, a dual-ported AND-type match-line circuit is devised to increase the area utilization by reduced the space stored “don't care”. Moreover, the power consumption is reduced.

Referring toFIG. 2, there are shown a single-ported CAM201and another single-ported CAM202. In each CAM, data are sorted according to the prefix lengths. Therefore, each CAM is divided into two regions; one (“matching region”) for storing binary data and the other (“none-matching region”) for storing “don't care”. The matching operation will ignore the cells for storing “don't care”. Therefore, then one-matching region is useless for the TCAM but occupies large area and consumes much energy. The concept of the present invention is to devise a dual-ported AND-type match-line circuit to store the matching region of the CAM202into the none-matching region of the CAM201.

According to the present invention, a TCAM203is used to store the data in matching region of the CAMs201and202. For the clarity of the description, a phantom boundary210is shown inFIG. 2to separate a region211from another region212. The region211is assigned to store the data in matching region of the CAM201. The region212is assigned to store the data in matching region of the CAM202. The prevent invention reduces the number of cells205for storing “don't care”. The use of one memory array to store the data in matching region of two memories improves the area utilization and reduces the power consumption.

The dual-ported AND-type match-line circuit includes two matching output ports208and209according to the present invention. The matching result of region211will be propagated to matching output port208. The matching result of region212will be propagated to matching output port209. In this design, the matching result of region211does not interfere with the matching result of region212. The matching result of each region will be propagated to corresponding output port according to assignment of region.

Referring toFIG. 3, a dual-ported dynamic AND gate301includes a dual-ported dynamic circuit302and a group303of cells304. The number of the cells304could be decided by designer. The result of matching the data stored in the cells304with external data is reflected at the gate electrode G of a transistor305. If the stored data matched with the external data, the gate electrode G will be charged to a high voltage level, and the transistor will be turned on. Otherwise, the gate electrode G will be discharged to a 0 V, and the transistor305will be turned off. If whole data stored in the cells304of the group303and external data are matched, a node X will be discharged to 0 V by the turn-on transistors305. Otherwise, the node X will be retained at a high voltage level. From the voltage of the node X, it can be learned whether there is a match for each cell304of the group303or not.

The dual-ported dynamic circuit302transmits the matching result X of the group303to a match line ML1or ML2depend on the control of a setting circuit306. The setting circuit306can store data and determine whether the matching result of the dual-ported dynamic AND gate301belongs to the match line ML1or ML2in the initialization of the circuit. The setting circuit306includes two complementary outputs set_p and set_n. If the output set_p is at a high voltage level, the output set_n will be at a low voltage level, and vice versa. To assign the matching result of the dual-ported dynamic AND gate301to the match line ML1, the output set_p is set at the low voltage level. A transistor308of a second directing circuit316and a transistor309of a first directing circuit315are turned off. A transistor307of the second directing circuit316and a transistor310of the first directing circuit315are turned on. If the previous dual-ported dynamic AND gate of the match line ML1has data-matched, an input320of a first dynamic output circuit313will be at a high voltage level. The matching result of the group303will be transmitted to a node n1through the transistor310of the first directing circuit315and a transistor311of the first dynamic output circuit313and further to the output321of the first dynamic output circuit313.

The concept of the present invention is to store the data of a first memory into then one-matching region of a second memory2. The match line ML2treats the stored data of group303belong to match line ML1as “don't care”. The match line ML2will always output data-matched through the turn-on transistor307and the turn-off transistor308no matter what the matching result of the group303. The matching result of the group303will not be transmitted to node n2. If the previous dual-ported dynamic AND gate of the match line ML2has data-matched, an input322of a second dynamic output circuit314will be at a high voltage level and the node n2will be discharged to a low voltage by the turn-on transistors312and307. Therefore output323of second dynamic output circuit314will output high according to the low voltage of node n2.

The setting circuit306could be implemented by SRAM cell, flip-flop or other storage elements. Referring toFIG. 4, the setting circuit306includes the SRAM cells of six transistors according to a first embodiment of the present invention. A word line is designated “WL”. Two write bit lines are designated “WBLP” and “WBLN”, respectively. The design of the word lines and write bit line is identical to that of the S RAM and therefore will not be described in detail.

Referring toFIG. 5, there is shown a dual-ported AND-type match-line circuit according to the first embodiment of the present invention. The match line ML1is made by using a wire501to connect the output321of a current stage to the input320of a following stage. The match line ML2is made by using a wire502to connect the output323of the current stage to the input322of the following stage.

Since the dual-ported AND-type match-line circuit is made of dual-ported dynamic AND gate, the dual-ported AND-type match-line circuit work as the general dynamic circuit that has pre-charge phase and evaluation phase. Each of the pre-charge and evaluation phases takes half a clock cycle. The first half clock cycle is the pre-charge phase wherein both of phi1and phi2are at a low voltage. Therefore, the outputs321and323and inputs320and322of each dual-ported dynamic AND gates are at a low voltage. In this phase, the external datum begins to compare with all the data previously written and stored into the cells304, and the voltage at gate electrode G of each memory cell goes toward its final value. If the external datum matches with the stored data of all cells304, the node X will be set at the low voltage.

The second half clock cycle is the evaluation phase wherein both of phi1and phi2are going to high from low voltage level. If the first stage has data-matched, the outputs321and323of the first stage will be set at the high voltage, and a high voltage signal will be transmitted to the inputs320and322of a second stage. If the second stage also has data-matched, the high voltage signal meant data-matched will be transmitted to the third stage, and so on. The match operation of the match line ML1is started from the leftmost dual-ported dynamic AND gate and propagate the matching signal to the right. If all dual-ported dynamic AND gate of entire match line ML1are data-matched, the output of match line “ML1Result” will go to logic “1”. Otherwise, the output of match line “ML1Result” will keep logic “0”. The match operation of the match line ML2is started from the rightmost dual-ported dynamic AND gate and propagate the matching signal to the left. If all dual-ported dynamic AND gate of entire match line ML2are data-matched, the output of match line “ML2Result” will go to logic “1”. Otherwise, the output of match line “ML2Result” will keep logic “0”. The matching signals of the match lines ML1and ML2do not interfere with each other as discussed above.

Referring toFIG. 6, there is shown a dual-ported AND-type match-line circuit according to a second embodiment of the present invention. The match lines ML1and ML2are further branched for high search speed. The search speed of match line could be enhanced by more branches of match line according to the designer's discretion. There are two branches as shown inFIG. 6. The designer can however design a match line to include three branches or more. The operation principle of the dual-ported AND-type match-line circuit does not change with the number of the branches. The operation of the second embodiment is like that of the first embodiment and therefore will not be described in detail.

Referring toFIG. 7, the layouts of all components in whole match-line circuit are designed as the same layout height and the layout of entire match-line circuit can be stack arrangement. The design of the layout of the circuit will be very easy.

Referring toFIG. 8, the signal of word line is generated by an address decoder802. The external datum is fed into cells304through searching and writing buffer801when the CAM performs writing and searching operation.

Referring toFIGS. 9 and 10, when the CAM performs the writing operation, the “write” signal will be set to high voltage. Now, the external datum is fed to the WBLP/WBLN by the searching and writing buffer801. At the same time, the address decoder802decodes the address and set the corresponding word line as high voltage. Therefore, the datum can be written into the cells304of corresponding row. When the CAM performs the matching operation, the “match” signal will be set to high voltage. In the positive half clock cycle of matching operation, the matching circuit enters pre-charge phase. In this phase, the external datum is fed into a SBLP/SBLN and matched with the stored data in all cells304of memory array. In the negative half clock cycle of matching operation, the matching circuit enters evaluation phase. In this phase, the triggered signals phi1and phil2of the matching circuit will go to high voltage. If the stored datum of entire row is matched with the external datum, the output of the match line will be the logic “1”.

Although the embodiments are designed based on the properties of ternary CAM cells, the present invention can be embodied in binary CAM cells so that the area of the memory can further be reduced.

Referring toFIG. 11, a CAM1101includes a bit width of 32 bits. It is composed of eight dual-ported dynamic AND gates1107,1108and1109with four cells. The setting circuit306divides a memory array1104into region1105and1106. The design of the regions1105and1106are like that of the regions211and212shown inFIG. 2. In the region1105, the cells of the first eight bits do not store the “don't care” according to analysis. Therefore, the cells of the first eight bits can be replace by the dual-ported dynamic AND gates with four binary cells. The other cells are still composed of ternary cells to increase the storing flexibility. We name such a new design as BiTCAM, since it combines binary and ternary cells. The embodiment further includes a searching and writing buffer1102and an address decoder1103.

As discussed above, the dual-ported dynamic AND gate according to the present invention exhibits the following advantages:

Firstly, based on the design of the match-line circuit with the dual-ported dynamic AND gate, the content-addressable memory can store two lookup tables in one memory array. Therefore, the area utilization could be greatly improved and the problems with the large area of the TCAM could be overcome.

Secondly, the dual-ported AND-type match-line circuit could generate two matching result in each matching operation. The searching energy of each datum is much lower than single-ported match-line circuit. Besides, the dual-ported AND-type match-line circuit adopts AND-type match-line circuit with the characteristic of low power consumption. According to the two reasons, the dual-ported AND-type match-line circuit achieves low power consumption and high throughput rate.

Thirdly, the memory can store two lookup tables. The setting of the boundaries of the lookup table is flexible and at the designer's discretion.

Fourthly, the BiTCAM make the binary cell and ternary cell can be used together for an optimized design, thus further reducing the area and the power consumption.

Fifthly the stack arrangement of layout renders the design of the dual-ported AND-type match-line circuit very easy.

The present invention has been described via the detailed illustration of the embodiments. Those skilled in the art can derive variations from the embodiments without departing from the scope of the present invention. Therefore, the embodiments shall not limit the scope of the present invention defined in the claims.