Login| Sign Up| Help| Contact|

Patent Searching and Data


Title:
A CAM MEMORY
Document Type and Number:
WIPO Patent Application WO/2018/015839
Kind Code:
A2
Abstract:
A CAM memory (Content Addressable Memory) is described, comprising a plurality of memory cells (2), organized in rows and columns, adapted to store a plurality of data words, a plurality of bit lines (BL, BLN) for receiving the bits of a word to be stored, a plurality of write lines (WL, WLN) to enable writing of a sequence of memory cells, so as to store the bits present on the bit lines (BL, BLN), a plurality of search lines (SL, SLN) arranged in the column direction to transmit a word to be searched in the memory cells, a matching circuit to compare bits of the word to be searched with bits of the words stored in the memory cells. At least two of the write lines (WL0, WL1) are intertwined, so that on a same row of the CAM memory (10) are stored alternately bits of at least two different words. In this way, the length of the search lines and/ or of the bit lines can be reduced.

More Like This:
Inventors:
STABILE, Alberto (Via E. Fermi 40, Frascati, 00044, IT)
ANNOVI, Alberto (Via E. Fermi 40, Frascati, 00044, IT)
FRONTINI, Luca (Frascati, 00044, IT)
LIBERALI, Valentino (Via E. Fermi 40, Frascati, 00044, IT)
Application Number:
IB2017/054171
Publication Date:
January 25, 2018
Filing Date:
July 11, 2017
Export Citation:
Click for automatic bibliography generation   Help
Assignee:
ISTITUTO NAZIONALE DI FISICA NUCLEARE (Via E. Fermi 40, Frascati, 00044, IT)
International Classes:
G11C15/00; G11C8/14; G11C15/04
Attorney, Agent or Firm:
LISA, Elisabetta et al. (Corso Vittorio Emanuele II 3, Torino, 10125, IT)
Download PDF:
Claims:
CLAIMS

1. A CAM memory (10), comprising

a plurality of memory cells (2) adapted to store a plurality of data words, said memory cells being organized in rows and columns,

a plurality of bit lines (BL, BLN) for receiving the bits of a word to be stored, a plurality of write lines (WL, WLN) to enable writing of a sequence of cells of said plurality of cells, so as to store the bits present on said plurality of bit lines (BL, BLN),

a plurality of search lines (SL, SLN) arranged in the column direction to transmit a word to be searched in said plurality of memory cells,

a matching circuit to compare bits of the search word with bits of the words stored in said memory cells,

characterized in that

at least two write lines (WLO, WL1) of said plurality are intertwined, so that on a same row of the CAM memory (10) are stored alternately bits of at least two different words.

2. CAM memory (10) according to claim 1, wherein said memory cells comprise a SRAM (20) to store a data and wherein the matching circuit includes, for each cell, a logic XOR gate (21) for comparing the data with the one present on a search line (SL).

3. CAM memory (10) according to claim 2, wherein the metalization of at least one of said search lines (SL, SLN) is in electrical contact with the silicon used to make a terminal in common between two transistors belonging to two different logical XOR gates (21) of two memory cells.

4. CAM memory (10) according to claim 1 or 2 or 3, wherein the search lines (SL, SLN) are made in a metalization layer higher with respect to transistors local interconnections.

5. CAM memory (10) according to any of the previous claims, wherein the matching circuit comprises a kill circuit (102), the kill circuit in turn comprising

a) a first input for receiving a KILL_IN signal,

b) a second input for receiving the data stored in a memory cell of said plurality of memory cells,

c) a third input for receiving the negative value of the data stored in a memory cell of said plurality of memory cells,

d) a fourth input for receiving the searched data being present on a search line of said plurality of search lines,

e) a fifth input for receiving the negative value of the searched data being present on a search line of said plurality of search lines,

f) an output for providing in output a KILL_OUT signal

the kill circuit being configured to implement the following map of Karnaugh

Wherein NKILLJN is the negative of the KILL_IN signal.

6. CAM memory according to claim 5, wherein a row of the CAM memory includes

M, with M a positive integer, memory cells (100) that comprise a SRAM (101) and a kill circuit (102) according to claim 5,

M-1 inverters

wherein the KILL_OUT signal of a memory cell (100) is supplied to the input of one of said M-1 inverters and wherein the output of said one inverter is provided as a KILL_IN input signal to a subsequent cell of said M memory cells (100). 7. CAM memory (10) according to any of claims 1 to 5, wherein the matching circuit comprises a kill circuit (202), the kill circuit in turn comprising a) a first input for receiving a KILL_IN signal,

b) a second input for receiving the data stored in a memory cell of said plurality of memory cells,

c) a third input for receiving the negative value of the data stored in a memory cell of said plurality of memory cells,

d) a fourth input for receiving the searched data being present on a search line of said plurality of search lines,

e) a fifth input for receiving the negative value of the searched data being present on a search line of said plurality of search lines,

f) an output for providing in output a KILL_OUT signal

the kill circuit being configured to implement the following map of Karnaugh

Wherein NKILL_OUT is the name of the KILL_OUT signal. 8. CAM memory according to claim 7 when dependent on claim 5, wherein a row of the CAM memory includes

memory cells of a first type (100) that comprise a SRAM (101) and a kill circuit (102) according to claim 5, and

memory cells of a second type (200) that comprise a SRAM (201) and a kill circuit (202) according to claim 6,

wherein the KILL_OUT signal of a memory cell (100) of the first type is provided as KILL_IN signal in input to a memory cell (200) of the second type.

Description:
"A CAM MEMORY"

DESCRIPTION

TECHNICAL FIELD

The present invention relates to a cell of the associative memory (or Content Addressable Memory - abbreviated as CAM), and chips using it.

In one embodiment, the invention relates to a memory cell according to the preamble of claim 1.

STATE OF THE ART CAM memories are semiconductor memories accessed, in addition to physical addresses of memory cells, also and mainly by content.

A CAM is generally constituted by an array of memory cells organized in rows and columns, in which each row contains a stored data word.

The content (or data) to search is presented in input on search lines (SL) that pass through the columns, and compared bit by bit with all the words stored in the CAM in a single clock cycle. For this reason, CAMs find application as look-up tables in routing systems, pattern recognition systems, etc., where it is necessary to compare quickly data with a plurality of stored data.

Examples of CAMs and their operation are described in the articles by Frontini et al. ([1]) and in Anh Tuan Do et al. ([2]), where solutions are proposed for the CAMs with different structures, which use NAND, NOR or XOR gates for bit by bit comparison among the data present on the SLs and those stored in the cells.

Regardless of the structure of the CAM, with the technology progress and the reduction of the dimensions of transistors composing the memory cells of the CAM, the area occupied tends much to be reduced, while the thickness of materials increases. Consequently, the intercapacitance between interconnection wires becomes dominant with respect to the capacitance between the wire and the ground plane.

Therefore, the need of a design that allows to minimize the intercapacitance between lines, and the consequent energy consumption of CAM, is felt, while respecting the constraint to maintain a regular grid diagram in two dimensions (in order to form a lattice in the plane of the surface of the silicon wafer), to define the geometries of transistors with a dimension smaller than the wavelength of the ultraviolet light used for the photolithographic process.

Another element that affects considerably the energy consumption of CAMs is given by matching circuits, i.e. those circuits that provide the CAM with an output indication if there is a coincidence between the content searched and the stored data.

For example, [1] each cell of the CAM provides an output bit (called OUT) whose value indicates if there is a coincidence between the bit stored in the cell and the searched one. To check if the searched word is present in a CAM row, [1] it proposes the use of a tree of NOR and NAND gates that receives in input the output bits of the cells of a row, and provides in output a matching bit, whose logic value is high when there is a coincidence among all the bits of the input data and the ones stored in the row.

Since a tree of this type is present for each row of the CAM, it is apparent how the propagation of electrical signals along the tree consumes energy.

Therefore, the need to optimize the design of the CAM in order to reduce the consumption of matching circuits is felt.

Citations

[1] L. Frontini, S. Shojaii, A. Stabile and V. Liberali, "A new XOR-based Content Addressable Memory architecture", Electronics, Circuits and Systems (ICECS), 2012 19th IEEE International Conference on, Seville, 2012, pages 701-704.

[2] Anh Tuan Do et al., "Content Addressable Memory Using Small Match Line Swing and Automated Background Checking Scheme for Variation Tolerance", IEEE JOURNAL OF SOLID-STATE CIRCUITS, vol. 49, pages 1487-1498, 2014.

OBJECTS AND SUMMARY OF THE INVENTION

The object of the present invention is to overcome the drawbacks of the known art.

In particular, an object of the present invention is to optimize the energy consumption of a CAM.

More particularly, an object of the invention is to optimize the design of the CAM to reduce the length of data lines and to reduce the energy consumption related to the propagation of the data thereon. Yet, an object of the invention is to optimize the matching circuits in order to reduce the consumption of the CAM during the step of content search.

These and other objects of the present invention are achieved by a CAM incorporating the features of the appended claims, which form an integral part of the present description.

In one embodiment, the CAM comprises

a plurality of memory cells (2), organized in rows and columns, adapted to store a plurality of data words,

a plurality of bit lines (BL, BLN) for receiving the bits of a word to be stored, a plurality of write lines (WL, WLN) to enable writing of a sequence of memory cells, so as to store the bits present on the bit lines (BL, BLN),

a plurality of search lines (SL, SLN) arranged in the column direction to transmit a word to be searched in the memory cells,

a matching circuit to compare bits of the word to be searched with bits of the words stored in the memory cells.

In this embodiment, at least two of the write lines (WLO, WLl) are intertwined, so that on a same row of the CAM memory are stored alternately bits of at least two different words.

In this way, the length of the search lines and/ or of the bit lines can be reduced, thus reducing the CAM consumption.

Advantageously, in an embodiment the CAM memory comprises memory cells which, in turn, comprise an SRAM to store data using a XOR logic gate to compare the data with the one present on a search line. Actually, this solution is suitable to exploit silicon optimally.

Advantageously, to reduce the consumption, search lines are formed in a metalization layer higher than the local transistors interconnections. This reduces the phenomena of parasitic capacitances and the consequent energy consumption.

According to an advantageous feature, taken alone or in combination with others, the matching circuit of the CAM comprises a kill circuit. The kill circuit in turn comprises a) a first input for receiving a KILL_IN signal, b) a second input for receiving the data stored in a memory cell of said plurality of memory cells,

c) a third input for receiving the negative value of the data stored in a memory cell of said plurality of memory cells,

d) a fourth input for receiving the searched data being present on a search line of said plurality of search lines,

e) a fifth input for receiving the negative value of the searched data being present on a search line of said plurality of search lines,

f) an output for providing in output a KILL_OUT signal

The kill circuit being configured to implement the following map of Karnaugh of Table 1

Table 1

Wherein NKILL_IN is the negative of the KILL_IN signal.

The use this type of matching circuit allows to reduce the energy consumption related to the step of content search in the CAM.

In one embodiment, in order to exploit a matching circuit with a kill signal of the type indicated above, the CAM memory is realized in such a way that one of its rows comprises, with M being a positive integer, M-1 inverters and M memory cells which comprise an SRAM and a kill circuit. The KILL_OUT signal of a memory cell is supplied in input to one of M-1 inverters, whereas the output of said one inverter is provided as a KILL_IN input signal to a subsequent memory cell.

In another embodiment, the CAM memory provides cells in which the matching circuit comprises a different kill circuit that comprises

a) a first input for receiving a KILL_IN signal,

b) a second input for receiving the data stored in a memory cell of said plurality of memory cells,

c) a third input for receiving the negative value of the data stored in a memory cell of said plurality of memory cells,

d) a fourth input for receiving the searched data being present on a search line of said plurality of search lines,

e) a fifth input for receiving the negative value of the searched data being present on a search line of said plurality of search lines,

f) an output for providing in output a KILL_OUT signal

This different kill circuit being configured to implement the following map of Karnaugh of Table 2

Table 2

In one embodiment, the CAM memory is realized in such a way that one of its rows comprises memory cells of a first type which comprise an SRAM and a kill circuit that realizes the map of Karnaugh of Table 1, and memory cells (200) that comprise an SRAM (201) and a kill circuit that realizes the map of Karnaugh of Table 2. The cells of the first and the second type are connected in such a way that the KILL_OUT signal of a memory cell of the first type is provided as KILL_IN signal in input to a memory cell of the second type.

Further advantageous features of the present invention will become more apparent from the description that follows and from the appended claims, which form an integral part of the present invention.

BRIEF DESCRIPTION OF THE DRAWINGS

The invention will be described hereinbelow with reference to non-limiting examples, provided for the purposes of explanation, and not limitation in the accompanying drawings. These drawings illustrate different aspects and embodiments of the present invention and, where appropriate, reference numbers showing illustrating components, materials and/ or similar elements in different figures are denoted by similar reference numerals.

Figure 1 illustrates a 4-bit memory cell for CAM memories.

Figure 2 schematically illustrates a CAM comprising a plurality of cells of the type of Figure 1.

Figure 3 illustrates the layout of the cell of Figure 1.

Figure 4 illustrates a 1-bit memory cell for CAM memories.

Figure 5 illustrates the map of Karnaugh of the kill circuit of the cell of Figure 4.

Figure 6 illustrates a row of a CAM realized with cells of the type of Figure 4.

Figure 7 illustrates a row of a CAM realized with cells of the type of Figure 4 and cells of the type of Figure 9.

Figure 8 illustrates the map of Karnaugh of the kill circuit of the cell of Figure 9.

Figure 9 illustrates a 1-bit memory cell for CAM memories with a negative logic kill circuit compared to the cell of Figure 4.

Figure 10 illustrates a comparison between the energy consumptions of CAM cells realized according to different solutions of the present invention and known CAM cells.

DETAILED DESCRIPTION OF THE INVENTION

While the invention is susceptible to various modifications and alternative constructions, some non-limiting embodiments, provided for explanatory purposes, are described in detail hereinbelow.

It should be understood, however, that there is no intention to limit the invention to the specific embodiments illustrated, but, on the contrary, the invention is intended to cover all modifications, alternative constructions, and equivalents which fall within the scope of the invention as defined in the claims.

In the following description, therefore, the use of "for example", "etc.", "or", "either" indicates not exclusive alternatives without any limitation, unless otherwise indicated; the use of "also" means "including, but not limited to" unless otherwise indicated; the use of "includes/comprises" means "includes/ comprises but not limited to" unless otherwise indicated.

In Figure 1, a wiring diagram of a cell 1 of a CAM according to one embodiment of the present invention is shown.

In this exemplary embodiment, cell 1 is a cell containing 4 bits, but obviously it is possible making cells containing a larger number of bits.

From the circuit point of view, cell 1 comprises 4 XORAM cells, indicated with reference numeral 2, of the type described in [1], and two NOR gates, indicated with the reference numeral 3.

Each i th XORAM cell 2 comprises:

• An SRAM (Static Random-Access Memory) 20, made in a known manner by a pair of crossed inverters (transistors Nl, PI, N2, P2) and a pair of input transistors (N3, N4) connecting the inverters to two-bit lines (bit lines) BL and BLN. The input transistors gates N3 and N4 are connected to a write line (write line, WL). When WL has a high logic value, it allows to write in the memory the bit value present on BL, while when it has a low logic value, it allows to read the stored bit.

• An XOR gate 21 is constituted by two pair of transistors (N5, P5) and (N6, P6), whose gates are respectively connected to the input of one of the two inverters of the SRAM. The two transistors of each pair are connected to one another by means of the drain connector and to search lines (search lines) SL and SLN by means of source connectors. The drain connectors of the two pairs of transistors are then connected to one another in a node Oi. In this way, the XOR gate compares the data present on the search lines SL and provides the node O with an output bit that has a high logic value when there is coincidence between the value of the input bit and the one stored in the SRAM.

As can be seen in Figure 1, the cell 1 comprises two write lines WLO and WLl that intersect, so that the bits of the two words that can be read and written by varying the value of WLO or WLl are interlaced.

By making a CAM with a plurality of cells 1, bits of consecutive words are therefore arranged in a checker-board pattern as shown in Figure 2. In this Figure, the CAM 10 is formed using a plurality of cells 1 arranged side by side, and it stores N bit words A=[A0, Al, A2, ... AN], B=[B0, Bl, B2 ... BN], etc...

From the schematic illustration of Figure 2, it is easy to see that the bits of the same word are alternated with those of another word, thus, for example, on a same row there are alternately the bits of odd order of word A and those of even order of word B.

Returning to Figure 1, the cell 1 comprises two NOR gates 3, one for each WL.

Each NOR gate is constituted by two pairs of transistors (N7, P7) and (N8, P8). Each pair of transistors is constituted by a transistor N and a transistor P connected in series between ground and supply voltage, and with the gates in common. The NOR logic gate inputs correspond to two common gates of the two pairs of transistors, while the output is taken on the drain connector of the two transistors N connected to the ground. Obviously, other circuit configurations can be adopted in order to make the NOR gates.

In cell 1, the outputs of the two cells XORAM 2 activated by the same WL are connected to the inputs of a same NOR gate. In Figure 1, in order not to complicate the drawing, the connection between the two nodes X-X and between the nodes Y-Y has been omitted.

The NOR gates 3 are a first part of the matching circuit of the CAM. In a CAM of the type of Figure 2, made arranging various cells 1 side by side, the outputs of the NOR gates of a same word are connected to one another by means of suitable logic gates, for example in a tree as described in [1], in such a way that the output of such matching circuit takes a desired value (e.g. a high logic value) only if there is a correspondence between the searched content (distributed on the search lines) and the stored word. The particular configuration of Figures 1 and 2, with crossed write lines, allows to optimize the length of the search lines, and consequently to reduce the consumption of the CAM during the step of content search.

As can be seen from the layout of the 4-bit cell 1, illustrated in Figure 3, the diagram of Figure 1 can be used for transistors stacked using the technique of stacked transistors, which allows to reduce the dimensions in the plane of the cell.

In Figure 3, the two memory cells 2 are seen arranged side by side, with the p-mos type transistors in the higher part of the layout, and the n-mos transistors in the lower one. To improve the readability of the Figure, the metal layers have been omitted, except those of SL and SLN, and the metalizations of BL and BLN signals, since they are secondary regarding the power consumption.

As can be appreciated, the p-mos and n-mos transistors share the silicon area thanks to the stacking thereof. As is known, when two transistors of the same type have in common a source or drain connector in a diagram, they may be designed so as to share the area of this connector in the layout: for example, transistors P9 and P10 share the space for the source connector, which is connected to the positive supply. This allows to optimize the circuit area and the length of interconnections required for routing signals, reducing the consumption. Moreover, in the layout of Figure 3, an arrangement of stacked transistors was found that allows to reduce also the area of the SL and SLN metalizations since contacts 25, 26, 27, 28 are formed on the silicon in common between a pair of transistors of the same type: for example, the contact 25 is formed in the silicon between transistors P6 and Pll that belong to two different XOR logical gates. The reduction of the area of the SL and SLN metalizations and the reduction of the number of contacts contributes to the reduction of power consumption.

Advantageously, to further optimize the consumption, the SLs are formed in a metalization level higher than the transistors local interconnections, and other interconnection levels are not provided in the vicinity thereof to avoid the addition of parasitic capacitances.

To optimize the consumption related to the switching activity of matching signals, in an embodiment a kill signal is used, that propagates in sequence (the technical term is pipeline) along the cells which store the data of a same word. Doing so, when a cell does not find any correspondence (the stored bit is different from the one present on the SL) the kill signal turns off the downstream cells in the pipeline. In this way (bit by bit), the power consumption is reduced. The last signal kill in the pipeline is also the matching signal; if this signal is active, then it indicates that all cells have a correspondence.

An example of a 1-bit cell that generates a kill signal is illustrated in Figure 4.

The cell 100 comprises an SRAM 101 (transistors N1-N3 and P1-P3) that stores data A (namely a bit having a logic value 0 or 1) that is available (straight and negative) at the outputs of inverters Nl, PI and N2, P2.

The cell 100 comprises also a circuit 102 for propagating the kill signal.

The circuit 102 receives in input the kill signal KILL_IN from the previous cell, and generates in output a kill signal KILL_OUT for the next cell.

The KILL_IN signal is applied to the gate of transistors P13 and N13 that have a common drain connector, where the KILL_OUT signal is made available.

Transistors N9 and N10, driven respectively by the data present on SL and by the data

NA, as well as transistors Nil and N12, driven respectively by SLN and A, are connected in series between the drain connector of P13 and the ground line.

Transistors P9 and P10, driven respectively by NA and SLN, as well as transistors Pll and P12, driven respectively by A and SL, are connected in series between the source connector of P13 and the supply line VDD.

In this way, the circuit 102 realizes the map of Karnaugh shown in Figure 5: in the case where the KILL_IN signal is low, then the KILL_OUT output will be high, whereas if the KILL_IN signal is high, then the KILL_OUT signal will be low in case of coincidence between the searched bit (present on the SLs) and the stored one (A), and high in case of non-coincidence.

A row of a CAM can therefore be realized as illustrated in Figure 6, by arranging N cells 100 side by side and by interposing an inverter 103 among them. In case of coincidence between the bit present on SL0 and the data contained in the first cell, then the KILL_OUT signal of the first cell will be low, and the inverter 103 that receives it in input brings it as high in input to the next cell. When in a pipeline cell there is no correspondence between the SL data and the data A stored in the SRAM 101, then the KILL_OUT signal is high and the inverter brings it as low, therefore in all subsequent cells there will be a low KILL_IN signal that propagates up to the last cell, where the KILL_OUT signal is taken as matching signal.

The use of the kill signal inhibits the switching of output signals of cells 100 downstream, thus allowing to reduce the energy consumption.

Advantageously, in order to minimize the number of transistors, in an embodiment illustrated in Figure 7, two types of cells are used, one (which will be called in straight logic, indicated with the reference numeral 100 and identical to that of Figure 4) which generates a kill signal equal to '1' when the propagation needs to be inhibited, the other (which will be called in negative logic 200) which generates a kill signal equal to Ό' under the same conditions.

In this way, by connecting alternately, as illustrated in Figure 7, cells with straight logic 100 and cells with negative logic 200, the need of the inverters 103 is suppressed and the number of CAM transistors is minimized.

An example of a cell 200 is illustrated in Figure 9, and as for cell 100 of Figure 4, it comprises an SRAM 201 and a circuit that generates a NKILL_OUT kill signal.

The KILL_IN signal is applied to the transistor gates P14 and N14 that have a common drain connector, where the NKILL_OUT signal is made available.

Transistors N9 and N10, driven respectively by the data present on the SLN and the data NA, as well as transistors Nil and N12, driven respectively by SL and A, are connected in series between the source connector of N14 and the ground line.

Transistors P9 and P10, driven respectively by A and SLN, as well as transistors Pll and P12, driven respectively by NA and SL, are connected in series between the drain connector of N13 and the supply line VDD.

In this way, the circuit 202 realizes the map of Karnaugh shown in Figure 8: in the case where the KILL_IN signal is high, then the NKILL_OUT output will be low, whereas if the KILL_IN signal is low, then the NKILL_OUT signal will be high in case of coincidence between the searched bit (present on the SLs) and the stored one (A), and low in case of non-coincidence.

Experimental tests have allowed to check that the above described solutions allow to reduce the energy consumption with respect to the CAMs commercially available at present and known by the inventors. Figure 10 shows the experimental data related to the consumption of CAM cells made with memory cells according to Figure 1 (DOXORAM) and CAM memory cells made with cells according to Figure 9 (KOXORAM). These data show a consumption of KOXORAM lower than 0.2 fj/comparison/bits, and a consumption of DOXORAM lower than 0.6 fj/ comparison/ bit, much lower than the XORAM cells made according to [1], whose data are illustrated for 28 nm and 65 nm technologies.

It is however clear that the embodiment examples described above should not be construed as limiting of the present invention, and that many variations may be made by a person skilled in the art without departing from the scope of protection, as it results from appended claims.

In particular, although the examples have been described with reference to circuits in MOSFET technology, it is clear that other technologies can be used.

Moreover, it is clear that the solutions described above with reference to individual embodiment examples can be mixed together to obtain further variants.

For example, it is possible to provide a CAM memory with at least two interlaced write lines, so that on a same row of the CAM memory, bits of at least two different words (as in the example of Figure 2) are stored alternately, but using cells of the type shown in Figure 4 or 9 whose matching circuit propagates a kill signal.