Content addressable memory with multi-row write function

A content addressable memory (CAM) device having a multi-row write function. The CAM device includes a CAM array and an address circuit. The CAM array includes a plurality of CAM cells and word lines coupled to respective rows of the CAM cells. The address circuit is coupled to the CAM array and configured to activate a plurality of the word lines simultaneously to enable a write value to be stored within a selected plurality of the rows of CAM cells.

FIELD OF THE INVENTION

The present invention relates generally to content addressable memory devices, and more particularly to ternary content addressable memory devices.

BACKGROUND

Content addressable memory (CAM) devices are often used in network switching and routing systems to determine forwarding destinations and permissions for data packets. A CAM device can be instructed to compare search data obtained from an incoming packet with contents of a forwarding or classification database stored in an associative storage array within the CAM device. If the search data matches an entry in the database, the CAM device generates a match address that corresponds to the location of the matching entry, and asserts a match flag to signal the match. The match address is then typically used to address another storage array, either within or separate from the CAM device, to retrieve a forwarding address or other routing information for the packet.

The associative storage array of a CAM device, a CAM array, is typically populated with CAM cells arranged in rows and columns. Precharged match lines are coupled to respective rows of the CAM cells, and bit line pairs and compare line pairs are coupled to respective columns of the CAM cells. Together, the bit line pairs form a data port for read and write access to address-selected rows of CAM cells, and the compare line pairs form a compare port for inputting search data to the CAM array during search operations. The CAM cells themselves are specialized store-and-compare circuits each including a data storage element to store a constituent data bit of a database entry and a compare circuit for comparing the data bit with a search bit presented on the compare lines. In a typical arrangement, the compare circuits within the CAM cells of a given row are coupled in parallel to the match line for the row, with each compare circuit switchably forming a discharge path to discharge the match line if the data bit and search bit do not match. By this arrangement if any one bit of a database entry does not match the corresponding bit of the search data, the match line for the row is discharged to signal the mismatch. If all the bits of the database entry match the corresponding bits of the search data, the match line remains in its precharged state to signal a match. Because search data is presented to all the rows of CAM cells in each compare operation, a rapid, parallel search for a matching database entry is performed.

In a prior-art ternary CAM array, depicted inFIG. 1, each CAM cell103typically includes a mask storage element (MS) to permit storage of a mask state (also called a “don't care” state) in addition to the binary ‘1’ and ‘0’ states stored in the data storage element (DS). The masked state is effected by loading the mask storage element with a mask bit that prevents the compare circuit (CP) from signaling a mismatch between the stored data bit and a search bit (i.e., complementary signals C and /C). Because both mask and data storage elements are provided in each CAM cell, the ternary CAM array provides the flexibility to apply an individually tailored mask pattern to each entry in the database. That is, mask words and data words are stored one-for-one within the ternary CAM array101as shown inFIG. 1. In some applications, however, it may be necessary to apply the same mask word to multiple data words. In the CAM application shown inFIG. 2, for example, a set of Z mask words (Mask1, Mask2, . . . , Mask Z) are applied, respectively, to Z different mask address ranges (Address Range1through Address range Z), with each address range corresponding to multiple rows of CAM cells. Unfortunately, achieving such an arrangement in the ternary CAM array101requires that each mask word be stored repeatedly in a sequence of mask write operations directed to each of the addresses within the corresponding mask address range. Repeated storage of the same mask word at different addresses undesirably consumes system resources as a host device must usually initiate a write operation directed to each different address within each different mask range (i.e., providing an instruction, address and mask value for each write operation) and in some cases may also read back each mask word to confirm proper storage.

FIG. 3illustrates a portion of another prior-art CAM array160referred to herein as a shared-mask CAM array. As shown, instead of providing a distinct set of mask storage elements within each row of CAM cells, a row of mask storage elements163is shared among multiple rows of CAM cells161. By this arrangement, a single mask write operation directed to a single row of mask storage elements163may be used to store a mask word that is applied across multiple rows of CAM cells (i.e., a range of addresses), thus reducing the number of mask write instructions that need to be issued to apply the same mask word across a given range of addresses. Unfortunately, the shared-mask CAM array160is often unsuitable in applications that require different or potentially different mask words to be stored for each data word.

DETAILED DESCRIPTION

In the following description and in the accompanying drawings, specific terminology and drawing symbols are set forth to provide a thorough understanding of the present invention. In some instances, the terminology and symbols may imply specific details that are not required to practice the invention. For example, the interconnection between circuit elements or circuit blocks may be shown or described as multi-conductor or single-conductor signal lines. Each of the multi-conductor signal lines may alternatively be single-conductor signal lines, and each of the single-conductor signal lines may alternatively be multi-conductor signal lines. Signals and signaling paths shown or described as being single-ended may also be differential, and vice-versa. Similarly, signals described or depicted as having active-high or active-low logic levels may have opposite logic levels in alternative embodiments. As another example, circuits described or depicted as including metal oxide semiconductor (MOS) transistors may alternatively be implemented using bipolar technology or any other technology in which a signal-controlled current flow may be achieved. With respect to terminology, a signal is said to be “asserted” when the signal is driven to a low or high logic state (or charged to a high logic state or discharged to a low logic state) to indicate a particular condition. Conversely, a signal is said to be “deasserted” to indicate that the signal is driven (or charged or discharged) to a state other than the asserted state (including a high or low logic state, or the floating state that may occur when the signal driving circuit is transitioned to a high impedance condition, such as an open drain or open collector condition). A signal driving circuit is said to “output” a signal to a signal receiving circuit when the signal driving circuit asserts (or deasserts, if explicitly stated or indicated by context) the signal on a signal line coupled between the signal driving and signal receiving circuits. A signal line is said to be “activated” when a signal is asserted on the signal line, and “deactivated” when the signal is deasserted. Additionally, the prefix symbol “/” attached to signal names indicates that the signal is an active low signal (i.e., the asserted state is a logic low state). A line over a signal name (e.g., ‘<signal name>’) is also used to indicate an active low signal. The term “terminal” is used to mean a point of electrical connection. The term “exemplary” is used herein to express but an example, and not a preference or requirement.

In embodiments of the present invention, enhanced write control circuitry is provided within a ternary CAM device to enable storage of a mask value simultaneously in multiple rows of CAM cells, an operation referred to herein as a multi-row write. In one embodiment, a multi-row write operation is carried out within the CAM device in response to an instruction from a host device (i.e., a control processor, network processor, application-specific integrated circuit (ASIC), or other control device) so that selection between single-row write operations and multi-row write operations may be made on an instruction-by-instruction basis by the host device. Thus, if the CAM device is to be used in a full-ternary application in which no mask sharing is needed, no multi-row write operations need be issued by the host device. If the CAM device is to be used in an application in which a mask is shared among multiple rows of CAM cells, multi-row write instructions may be issued to reduce the overall number of write instructions issued to the CAM device, thus reducing the burden on system resources. In yet other applications, the CAM device may include multiple CAM arrays (and/or a segmented CAM array) some of which are loaded using multi-row write operations while others are loaded using a combination of multi-row and single-row write operations or only single-row write operations. In an alternative embodiment, a configuration circuit (e.g., a programmable register) is programmed by a host device to select either a multi-row write mode or a single-row write mode, the enhanced write control circuitry being responsive to the programmed mode to carry out either multi-row or single-row write operations. In other embodiments, the number of rows of CAM cells written in a multi-row write operation may be established by programming a group-size value within a configuration circuit or by providing a group-size value with a multi-row write instruction. These and other aspects and embodiments of the invention are described below.

CAM Device with Multi-Row Write Function

FIG. 4illustrates a CAM device200having a multi-row write function according to an embodiment of the invention. The CAM device includes a CAM array201, key register203, instruction decoder205, address logic207, read/write circuit209, array precharge circuit221, configuration circuit212, flag circuit213and priority encoder215. The CAM device200may also include other circuit blocks, not shown, for performing error checking functions, database maintenance, self-testing and so forth. The CAM device200includes interfaces to a number of signal paths202,204,206,208to receive instructions, addresses, search keys, write values, and so forth, and to output read values, search results, status values and the like to one or more other devices (e.g., host device, associated memory). The signals received or transmitted on individual signal paths are discussed below in the context of the operations and circuit blocks to which they pertain. In alternative embodiments, any one or more of the signal paths and corresponding interfaces may be eliminated, and the signals carried on the eliminated signal paths multiplexed onto one or more others of the signal paths.

The instruction decoder205serves as a control circuit for the CAM device200, decoding instructions received via an instruction bus204and issuing various control and timing signals (shown generally at210) to other circuit blocks within the CAM device200as necessary to carry out the indicated operation. The instruction decoder205may be implemented by a state machine, micro-sequencer, or any other type of control circuit and may receive or generate one or more clock signals (not shown) for synchronizing state transitions and/or other timing control purposes. Also, virtually any type of instructions may be received and decoded by the instruction decoder205including, without limitation, search instructions, data read and write instructions, mask read and write instructions (including multi-row write instructions), configuration instructions (i.e., instructing the CAM device to program a configuration value within the configuration circuit), test instructions and so forth. Individual control and timing signals issued by the instruction decoder205in response to the various instructions are discussed below in the context of the particular operations and circuit blocks to which they pertain.

CAM array201is a ternary CAM array having a plurality of ternary CAM cells211arranged in rows and columns. Each row of CAM cells (a CAM row) is coupled to a respective word line218and precharged match line220(the match line precharging circuit is not specifically shown inFIG. 4), and each column of CAM cells (a CAM column) is coupled to a respective pair of compare lines235(CL and /CL), a respective pair of data bit lines231(DL and /DL), and a respective pair of match bit lines233(ML and /ML). The ternary CAM cells211each include a data storage element switchably coupled (i.e., coupled through transistor switches or other switching elements) to the data bit lines231for the CAM column, and a mask storage element switchably coupled to the mask bit lines233for the CAM column. The data storage element and mask storage element enable storage of data bit (D) and mask bit (M), respectively, that collectively represent one of three states: logic ‘1’ (e.g., D=1, M=0), logic ‘0’ (e.g., D=0, M=0), and a mask state, ‘X’ (e.g., D=0 or 1, M=1), where ‘X’ indicates a don't care condition. The data and mask storage elements within ternary CAM cells211may be implemented by virtually any type of storage circuit including, without limitation, volatile storage circuits (e.g., back-to-back coupled inverters, thyristor-based storage or other static volatile storage circuit; or capacitor-based or other dynamic storage circuits) and non-volatile storage circuits (e.g., floating-gate-based storage elements such as flash memory, ferroelectric storage elements, battery backed memory, etc).

In one embodiment, the CAM array201includes multiple segments that may be combined according to logical dimension information (e.g., stored within the configuration circuit212or provided in host-supplied instructions) to effect different logical array configurations. In one implementation, for example, a 288-bit wide, 1024 row CAM array includes four 72-bit segments which may be accessed individually (allowing storage of four database entries per row and effecting a 72×4096 logical array dimension), in pairs (allowing storage of two database entries per row and effecting a 144×2048 logical array dimension) or as a unit (allowing storage of a single 288-bit database entry in each row and effecting a 288×1024 logical array dimension). Other physical and logical CAM array dimensions may be provided in alternative embodiments. Also, different logical dimensions may be applied in different portions of the CAM array201and/or, in an embodiment having multiple CAM arrays201within a single CAM device, different logical dimensions may be applied to different CAM arrays201.

Still referring toFIG. 4, the key register203is used to store search keys (i.e., search data values) received via a search bus202, and includes compare line driver circuitry coupled to compare line pair235for each CAM column. Upon decoding a search instruction, the instruction decoder205initiates a search operation by outputting a search enable signal228to the key register203, thereby enabling the compare line driver circuitry to drive constituent bits of a search key (i.e., comparand bits) in complementary form onto the compare line pairs235of the CAM array201. After a predetermined time interval (e.g., after one or more clock signal transitions and/or after an asynchronous delay interval), the search enable signal228is deasserted to allow the charged compare lines to discharge in preparation for a subsequent compare operation. Though not specifically shown inFIG. 4, global masking circuitry may be provided and used to selectively prevent compare lines from being driven for one or more columns of CAM cells211, thereby masking the corresponding bit positions in all the rows of the CAM array201. In an alternative embodiment, the key register203may be omitted and the comparand bits sourced directly from the search bus202.

The comparand bits driven onto the compare line pairs are compared with data values stored within individual ternary CAM cells211which, as discussed above, may be masked to prevent mismatch detection. If each CAM cell211within a given CAM row indicates a match between the comparand bit and stored data value (i.e., due to logical match, or masking), the match line220for the CAM row remains in its precharged state to signal the match condition. If a mismatch is detected in one or more CAM cells211of a given CAM row, the mismatch-detecting CAM cell (or cells) forms a path to ground to discharge the match line220for the row and thereby signal the mismatch condition. In alternative embodiments, CAM cells211may be coupled in series with a pulled-up match line220and a mismatch-detecting CAM cell211used to interrupt a connection to ground (i.e., in such an embodiment a charged match line220may indicate a mismatch condition, while a discharged match line220indicates a match condition). Also, regardless of whether the CAM cells211are coupled in parallel or series with the match lines220, the logical states of the match lines220used to signal match and mismatch conditions may be reversed in alternative embodiments (e.g., by swapping logic low and logic high voltage connections).

Still referring toFIG. 4, the flag circuit213and priority encoder215are both coupled to the match lines220to receive match indications therefrom. In one embodiment, the flag circuit213asserts a match flag214(MF) if any of the match lines220indicate a match condition during a search operation. The flag circuit213may additionally assert a multiple match flag (not shown) if two or more match lines220indicate match conditions. Also, during read and write operations, the match lines may be driven high or low according to whether the corresponding CAM row contains a valid entry, and the match flag214may therefore be used to signal a full condition within the CAM array201(i.e., all rows of CAM cells211occupied by a valid entry). The flag circuit213may additionally output an almost-full flag during read and write operations to indicate, for example, that the CAM array201is within a predetermined number of entries of being completely filled.

The priority encoder215responds to match indications signaled on the match lines220by determining a highest-priority matching (HPM) entry (i.e., highest-priority database entry indicated to match the search value), and generating a match address216(MA) that corresponds to the storage location of the HPM entry within the CAM array201. The priority determination may be based on various different criteria including, without limitation, the numerical value of the addresses associated with the key-matching entries (e.g., lower numerical address taking priority over higher numerical address, or vice-versa), the number of unmasked bits within the key-matching entries (e.g., entry having fewer masked bits taking priority over entry having more masked bits, or vice-versa), age of key-matching entries, logical tags within the key-matching entries and so forth. Also, the priority encoder215may be programmable to allow relative priorities of database entries to be established by programming (i.e., storing) a priority value for each database entry. However match indications are prioritized, the resulting match address216may be used to index another storage array within or separate from the CAM device200, and may also be recorded within an address register (not shown inFIG. 4) within the CAM device200to enable read and write access to the HPM entry for error-checking and other purposes. Also, as discussed above, the match lines220may be driven high or low during read and write operations to indicate whether the corresponding CAM row contains a valid entry. The priority encoder215may encode the validity indications to generate an address that corresponds to the highest-priority unused storage location within the CAM array201, an address referred to herein as a next free address (NFA).

The address logic207and read/write circuit209are used to carry out data access operations within the CAM array201, including data read and write operations and mask read and write operations, the mask write operations including single-row write operations and multi-row write operations. Data access operations may be initiated by the instruction decoder205in response to host read and write instructions or in response to internal states such as detecting a lapse in the stream of host read/write instructions (indicating that read/write cycles are available), error detection (i.e., indicating that one or more entries within the CAM array are corrupted and may need to be invalidated and/or overwritten with non-corrupted data) and so forth. In the embodiment ofFIG. 4, the instruction decoder205initiates a data access operation by issuing a decode enable signal226to the address logic207to enable the address logic207to decode an address value (AD) received via address bus206(or from an internal source such as a register used to store an HPM address, next free address, or from a counter or other address generator used to generate a sequence of addresses for error checking or auto-loading purposes), and by issuing control signals to the read/write circuit209to enable the read/write circuit to drive a write value or sense a read value on the data bit lines231and/or mask bit lines233.

In a read operation, data write operation or single-row mask write operation, the address logic207activates an address-specified word line218to enable read or write access to the mask and/or data storage elements within the corresponding CAM row. More specifically, in a read operation, word line activation enables the contents of the storage elements (i.e., the data and mask words) within the CAM cells of the corresponding CAM row to be output onto the data bit line pairs231and mask bit line pairs233, respectively, the bit line pairs for each CAM column being precharged by respective bit-line precharge circuits224(PC) within array precharge circuit221(as discussed below, the multi-row write signal225(MRW) may be supplied to selected precharge elements within bit-line precharge circuits224to boost the precharge for unused bit lines during a multi-row write). After a predetermined (or clocked) settling interval, the instruction decoder (or other control logic) asserts a read strobe signal to enable sense amplifiers within the read/write circuit209to amplify the data word and/or mask word presented on the data bit lines231and mask bit lines233to logic levels. The logic level data word and/or mask word may then be output from the CAM device200via data bus208and may additionally or alternatively be provided to other circuitry within the CAM device200, such as error checking circuitry (e.g., to check for parity errors, cyclic-redundancy check errors, checksum errors, error correction code errors and so forth). As discussed below, in one embodiment, a bank of sense amplifiers is shared between the data bit lines231and mask bit lines233so that either a mask word (MASK) or data word (DATA, collectively DATA/MASK) is read in a given read operation. In an alternative embodiment, separate banks of sense amplifiers may be coupled to the data bit lines231and mask bit lines233to enable both mask and data words to be read simultaneously from a selected CAM row.

In a single-row write operation, a bank of differential write drivers within the read/write circuit209are enabled to drive a write value (e.g., received via data bus208) onto the data bit lines231and/or mask bit lines233of the CAM array200, thereby enabling storage of the write value in the data storage elements and/or mask storage elements of the address-selected CAM row (i.e., the CAM row coupled to the activated word line). In one embodiment, a single bank of differential write drivers is shared between the data bit lines231and mask bit lines233so that either a data word or a mask word is written in a given single-row write operation. In an alternative embodiment, separate differential write driver banks may be coupled to the data bit lines231and mask bit lines233to enable both mask and data words to be written simultaneously within the address-selected CAM row.

In the case of a multi-row write operation, the read/write circuit209drives a mask word onto the mask bit lines233, and the address logic207activates multiple address-selected word lines to store the mask word simultaneously within multiple CAM rows. In the particular embodiment ofFIG. 4, multi-row write operations may be used, for example, to store a mask word in multiple CAM rows in response to a single write instruction from a host device, thereby reducing the number of write instructions issued by the host device to establish a common mask word for a given address range within the CAM device200(i.e., effectively emulating the operation of a shared-mask embodiment). Because distinct mask words may be stored within each CAM row, however, the CAM device200may still be used in ternary CAM applications that require different or potentially different mask words to be stored for each data word.

Still referring toFIG. 4, configuration circuit212may be used to store device configuration information of various types including, without limitation, group-size information to indicate how many rows of CAM cells are to be accessed in a multi-row write operation (e.g., how many word lines are to be activated simultaneously), logical dimension information, timing control information, test option selections, match prioritizing policy, and so forth. The configuration circuit212may be programmed in a one-time programmable programming operation (e.g., blowing fusible elements in a production-time programming operation) or in one or more run-time programming operations in response to a host-supplied programming instruction and configuration information.

Multi-Row Address Decoder

FIG. 5illustrates an embodiment of an address decoder250that may be used within the address logic207ofFIG. 4to support multi-row write operations. The address decoder250includes a group decoder251(GDEC) and a set of row decoders2530-253G-1(RDEC). The group decoder251is coupled to receive a group address component254of an M-bit row address252(AD [M−1:0]) and a decode enable signal226(DE) from the instruction decoder. In the embodiment ofFIG. 5, the group address254includes the R most significant bits of the row address252(i.e., row address AD [M−1:J], where M−J=R). In an alternative embodiment, the group address254may include any combination of bits from the row address252.

When the decode enable signal226is asserted, the group decoder251performs an R-to-G binary decoding operation, activating one of G group select lines S0-SG-1in accordance with the group address254(e.g., activating group select line Si, where ‘i’ ranges from 0 to 2R−1 according to the numeric value of the group address254). Each of the row decoders2530-253G-1includes a group select input coupled to a respective one of the group select lines, S0-SG-1, an address input to receive a sub-group address256(e.g., the J least significant bits [J−1:0] of the row address252in the embodiment ofFIG. 5or, alternatively, if not the least significant row address bits, whichever row address bits do not form part of the group address254), and a multi-row write input coupled to receive a multi-row write signal225(MRW) from the instruction decoder. When a group select line is activated, the corresponding row decoder253is enabled to activate one or more of a group of K word lines218, depending on the state of the multi-row write signal225and sub-group address256. More specifically, if the multi-row write signal225is deasserted, then the enabled row decoder performs a J-to-K decode operation to activate one of the K word lines218in accordance with the sub-group address value. For example, if group select line S0is activated (and multi-row write signal225is deasserted), then row decoder2530activates one of word lines WL0-WLK-1according to the sub-group address256. If group select line S1is activated, then row decoder2531activates one of word lines WLK-WL2K-1according to the sub-group address256, and so forth to row decoder253G-1which activates one of word lines WLK(G-1)-WL(KG)-1in response to activation of group select line SG-1. Thus, when the decode enable signal226is asserted and the multi-row write signal225is deasserted, the address decoder250activates one of N word lines indicated by the M-bit row address252, where N=K*G=2M.

If the multi-row write signal225is asserted during a decode operation, the enabled row decoder253(i.e., the row decoder253coupled to the activated group select line) activates each of the K word lines of the selected group to enable multi-row write access to the corresponding group of CAM rows. That is, if group select line S0is activated (and multi-row write signal225is asserted), row decoder2530activates word lines WL0-WLK-1to enable a multi-row write within a first group of K CAM rows. If group select line S1is activated, row decoder2531activates word lines WLK-WL2K-1to enable a multi-row write within a second group of K CAM rows, and so forth for each group of CAM rows coupled to word lines driven by row decoders2532-253G-1.

FIG. 6illustrates an embodiment of a row decoder280(RDEC) that may be used to implement the row decoders253ofFIG. 5. The row decoder280includes a J-to-K binary decoder (J:K Decoder) (i.e., K=2J) to activate one of K output lines, D0-DK-1according to the incoming sub-group address256[J−1:0]. The D0-DK-1output lines are coupled to first inputs of respective OR gates287so that the activated one of the output lines will raise the output of the corresponding OR gate287. The second inputs of the OR gates287are coupled to receive the multi-row write signal225(MRW) so that, if the multi-row write signal225is asserted, the outputs of all the OR gates287will go high. The outputs of the OR gates287are coupled to first inputs of respective AND gates289, and the second inputs of the AND gates are coupled to receive a group select signal282(S0in this example). The outputs of the AND gates289are coupled to word lines so that, if the group select signal282is asserted, and the multi-row write signal225is deasserted, one of the word lines WL0-WLK-1is activated in accordance with the sub-group address256. If the group select signal282and multi-row write signal225are both asserted, then all the word lines WL0-WLK-1are activated. If the group select signal282is deasserted, none of the word lines are activated.

Referring toFIGS. 5 and 6, it should be noted that numerous different logic circuits may be used to decode the row address252(and the group address254and sub-group address256). Also, the number of word lines activated during a multi-row write operation may be controlled by a mode setting within the configuration circuit (e.g., element212ofFIG. 4) and/or according to incoming instructions, thereby enabling the number of rows written to in a multi-row write operation to vary from one mask write operation to the next according to application needs. As an example, in one embodiment, the multi-row write signal225is a multi-bit signal having x4 and x8 constituent signals to enable selection between single-row write operations, four-row write operations and eight-row write operations as shown in the following table (A0, A1and A2being the least significant bits of an M-bit row address and WL0-WL7being the eight word lines coupled to a given row decoder):

TABLE 1x8x4A2A1A0WL7WL6WL5WL4WL3WL2WL1WL000000000000010000100000010000100000010000011000010000010000010000001010010000000110010000000011110000000010XX00001111011XX111100001XXXX11111111
Additional and/or different group-size selections or may be used in alternative embodiments.

Enhanced Bit-Line Driver

FIG. 7illustrates a column of CAM cells2110-211N-1, bit-line driver/amplifier310and bit-line precharge circuit224according to an embodiment of the invention. Referring to the detail view of CAM cell2110, each of the CAM cells211is a ternary CAM cell having a compare circuit323, data storage element325and mask storage element335. In the particular embodiment shown, the mask and data storage elements325and335are each implemented by back-to-back coupled inverters having inverting and non-inverting nodes. The non-inverting node326and inverting node327of the data storage element325are coupled to data bit lines231aand231bvia pass gates328and329, respectively, and the non-inverting node336and inverting node337of the mask storage element335are coupled to the mask bit lines233aand233bvia pass gates340and341, respectively. The gate terminal of each pass gate328,329,340and341is coupled to word line, WL0(or, in the case of other CAM cells,2111-211N-1, to word lines WL1-WLN-1, respectively). By this arrangement, when a given word line is activated, the pass gates coupled the word line are switched to a conducting state to enable access to the data storage element325via data bit lines231and to enable access to the mask storage element335via mask bit lines233.

As an example of a read operation within the embodiment ofFIG. 7, assuming that the data bit lines231and mask bit lines233are precharged to logic-high levels (i.e., by the bit-line precharge circuit224) and that a logic ‘1’ is stored within the data storage element325of CAM cell2110. In that case, the inverting node327of the data storage element325is at a logic-low level, and the non-inverting node326of the data storage element325is at a logic-high level. Consequently, when word line WL0is activated, the inverting node327of the data storage325element draws a small current from the bit-line precharge circuit324via mask bit line233b, pulling down the mask bit line233bin accordance with the resistance of the bit-line precharge circuit224and thus developing a differential mask signal on the mask bit lines233aand233b(i.e., because mask bit line233aremains substantially at the precharged level). The logic low node of the data storage element325similarly acts to pull down one of the data bit lines231aor232bto develop a differential data signal on the data bit line pair. In the embodiment ofFIG. 7, the bit-line driver/amplifier310includes a single sense amplifier315(SA) which receives either the differential mask signal or the differential data signal via multiplexers314aand314baccording to the state of an access type signal322(AT). The access type signal322may be generated, for example, by the instruction decoder according to whether an incoming read instruction indicates a mask read or data read operation. The sense amplifier315amplifies the selected differential signal to a logic level signal that may be output from the CAM device (e.g., on data bus208ofFIG. 4) and/or provided to other circuitry within the CAM device (e.g., error checking circuitry).

In an alternative embodiment, separate sense amplifiers315may be provided for the data bit lines231and mask bit lines233within each CAM column, thereby enabling both mask and data values to be read at the same time. Also, instead of separate mask and data bit lines231and233, a single pair of bit lines may be multiplexed and separate mask and data word lines provided for each CAM row to enable the contents of either the mask storage elements or the data storage elements onto the shared bit lines.

During a single-row or multi-row write operation, a write enable signal338(WE) is asserted to enable a pair of line drivers LD311aand311b(referred to collectively herein as a differential driver311) within the bit-line driver/amplifier310to output a differential signal representative of a write bit339(provided to line drivers311aand311bas complementary values WB339aand /WB339b) onto the data bit lines231or mask bit lines233. Consequently, when a single word line is activated by the address logic (i.e., as part of a single-row write operation), the write value represented by the differential signals present on the data bit lines and/or mask bit lines is stored within the mask or data storage elements coupled to the activated word line. When multiple word lines are activated as part of a multi-row write operation, the write value is stored within the storage elements coupled to each of the activated word lines. In one embodiment, described in further detail below, the multi-row write signal325is provided to line drivers311aand311bto enable increased current draw (or increased current delivery) during multi-row write operations.

In the embodiment ofFIG. 7, multiplexers312aand312bare provided to route the differential signal generated by the differential driver311onto either the data bit lines231or the mask bit lines233according to the state of the access type signal322. Accordingly, in a single-row or multi-row mask write operation, only the mask bit lines233are driven by the differential driver311, and the data bit lines231remain nominally at their precharged levels. Conversely, in a data write operation, only the data bit lines231are driven by the differential driver311, and the mask bit lines233remain nominally at their precharged levels. In an alternative embodiment, separate differential drivers311may be provided for the data bit lines and mask bit lines, thereby enabling both pairs of bit lines to be driven at the same time and enabling simultaneous storage of data and mask words in selected write operations (e.g., single-row mask/data write operations).

FIG. 8illustrates an embodiment of a line driver350that may be used within the differential driver311ofFIG. 7(i.e., to implement either of line drivers311aor311b. The line driver350includes a logic circuit351, P-type MOS (PMOS) transistor353and N-type (NMOS) transistor355. The source terminals of transistors353and355are coupled to a supply voltage node and ground voltage node, respectively, and the drain terminals of transistors353and355are coupled to one another to form the output node356of the line driver circuit350. The gate terminals of transistors353and355are coupled to receive control signals A and B, respectively, from the logic circuit351. In one embodiment, the logic circuit351generates control signals A and B according to the state of the write enable signal338(WE) and write bit339(WB) as shown at357. That is, when the write enable signal338is low, control signals A and B are high and low, respectively, thereby switching both transistors353and355off (i.e., to a substantially non-conducting state) and rendering the line driver output in a high-impedance state. In the high-impedance state, the line driver350allows the bit line to which the line driver circuit is coupled to be pulled-up to a logic-high level by the bit-line pre-charge circuit (i.e., element224ofFIG. 7) or pulled-down by a data or mask storage element in a read operation. When the write enable signal338is high, control signals A and B are both driven to either a logic low or logic high state according to the state of write bit339, thus switching on one of transistors353,355and switching off the other. More specifically, when the write enable signal338is high and the write bit339is high, control signals A and B are both driven low to switch on transistor353and switch off transistor355and thereby drive a logic-high signal onto the bit line coupled to output node356(i.e., switchably coupling the bit line to a logic-high voltage node). Conversely, when the write enable signal338is high and the write bit339is low, control signals A and B are both driven high to switch on transistor355and switch off transistor353and thereby drive a logic-low signal onto the bit line coupled to output node356(i.e., switchably coupling the bit line to a logic-low voltage node to discharge the bit line). As shown inFIG. 7, the line drivers311aand311breceive complementary write bits339aand339bso that when one of the line drivers drives a logic-high signal onto a bit line, the other drives a logic-low signal on the counterpart bit line to effect a differential signal.

Increased Bit Line Charging and Discharging Currents

Referring toFIGS. 7 and 8, when the differential driver311is enabled to drive a differential signal onto the bit lines, whichever of the line drivers311aor311bis to drive the logic-low level component of the differential signal should pull the corresponding bit line low enough to absorb the charge transferred onto the bit line by a logic high output from the storage element coupled to the activated word line. That is, to flip the state of a storage element coupled to an activated word line, the line driver311a/311bdriving low level component of the differential signal sinks enough current to counteract the pull-up effect of the precharge circuit and the storage element being written, such current being referred to herein as a flip current, IFL. In the case of a multi-row write operation, the worst-case (i.e., highest) flip current is increased relative to a single-row write due to the increased number of storage elements switchably coupled to the low-drive bit line (i.e., the largest magnitude flip current being required when the data state in all such storage elements is being flipped in the multi-row write operation). Accordingly, in one embodiment of line driver350, the current sinking transistor355is designed to draw enough current to flip the state of up to K storage elements (thus writing to K storage elements simultaneously, where K is the maximum number of rows that may be written in a multi-row write operation) as opposed to simply enough current to flip the state of one storage element. The increased current draw may be achieved by coupling multiple current-sinking transistors in parallel or increasing the gain (e.g., by increasing the width/length ratio) of transistor355.

FIG. 9illustrates an alternative embodiment of a line driver that may be used within the differential driver ofFIG. 7. In the alternative line driver embodiment ofFIG. 9, current draw may be selectively increased according to whether a multi-row write is being performed, thus avoiding unnecessary power consumption in single-row write operations. In the line driver370ofFIG. 9, for example, one or more additional current-sinking transistors377are coupled in parallel with transistor355and controlled by a third control signal, C. A control logic circuit371generates control signals A and B in the manner described in reference toFIG. 8(with control signal B being used to switch on a current-sinking transistor355appropriately sized to flip the state of a single storage element), and additionally raises control signal C, as shown in table379, when the multi-row write signal225is asserted and a logic low write bit339is to driven onto the bit line coupled to output node378. That is, control signal C is raised during a multi-row write operation to provide the additional current draw (IBST) that may be needed to meet the worst-case flip current. In other line driver embodiments, the pull-up transistor353ofFIG. 8may be increased in size to provide additional bit line charging current if needed or desired in a multi-row write operation. Similarly, an additional transistor (or transistors) may be coupled in parallel with transistor353of line driver370to enable additional charging current to be provided during multi-row write operations, with a lower charging current (i.e., provided via transistor353) delivered during single-row write operations.

As discussed above, when a differential signal is driven onto the data bit lines231or mask bit lines233in the embodiment ofFIG. 7, the non-driven pair of bit lines remains nominally at its precharged level. Because both the data and mask storage elements coupled to the activated word line are switchably coupled to the corresponding bit line pair, however, one bit line of the non-driven bit line pair will be pulled down by the logic-low node of the non-targeted storage element (i.e., whichever of the data and mask storage elements is not being written). In the case of a single-row write operation, only one non-targeted storage element is switchably coupled to the non-driven bit lines so that the low-going non-driven line cannot affect the state of storage elements in other CAM rows. In a multi-row write operation, however, multiple non-targeted storage elements are switchably coupled to the non-driven bit lines and, depending on the pattern of ‘1’s and ‘0’s stored within the non-targeted storage elements, may discharge one of the non-driven bit lines sufficiently to effect an inadvertent data write in another of the non-targeted storage elements. Referring toFIG. 7, for example, in a multi-row mask write operation directed to sixteen rows of CAM cells211, if fifteen of the data storage elements325contain logic ‘1’ values and one of the data storage elements325contains a logic ‘0’ value, the combined bit line discharge effect of the inverting nodes327(i.e., logic ‘0’ nodes) of the fifteen same-state data storage elements325may sufficiently discharge data bit line231bto flip the state of the data storage element325containing the logic ‘0’ value (i.e., because the logic high inverting node327of such data storage element may be pulled low by the combined pull-down effect of the other fifteen data storage elements), corrupting the corresponding data base entry. In one embodiment, such unintended data writes are avoided by boosting (i.e., increasing) the charging current supplied to the data bit lines by the bit-line precharge circuit224during a multi-row write operation. Thus, as shown inFIG. 7, the multi-row write signal225(MRW) is provided to the data bit line precharge elements (PC)305aand305bwithin bit-line precharge circuit224to enable the charging current to be responsively increased. In alternative embodiments, bit line precharge elements (PC)307aand307bmay also receive the multi-row write signal225to provide additional charging current to non-driven match lines in a multi-row write operation. For example, in one embodiment word lines extend across multiple CAM arrays with only one (or at least less than all) of the CAM arrays being selected to participate in a multi-row write operation. In such an embodiment, it may be desirable to boost the charging current on all the bit lines of the unselected CAM arrays (i.e., match bit lines and data bit lines) to avoid unintended writes. Similarly, in a segmented CAM array embodiment (i.e., each row of CAM cells selectively segmented into multiple rows), only one or at least less than all of the segments may be selected to participate in a write operation so that it may be necessary or desirable to boost the charging current on all the bit lines of the unselected segments. In all such embodiments, decode signals may be provided to the precharge circuit224to enable boosted charging current only in unselected CAM arrays and/or unselected segments of a CAM array).

FIG. 10illustrates an embodiment of a precharge element400that may be used to implement the data bit line precharge elements305a,305b(and, optionally, the match line precharge elements307a,307b) within the bit-line precharge circuit224ofFIG. 7. The precharge element400includes PMOS transistors401,403and405coupled in parallel with one another between a supply voltage (VS), and the bit line to be charged407. The gate terminal of transistor401is coupled to ground (or another bias voltage) and is sized to deliver a predetermined charging current to the bit line407. The gate terminal of transistor403is coupled to receive a pulsed-precharge signal402(i.e., an active low signal, /PPC), and the gate terminal of transistor405is coupled to receive an active low version of the multi-row write signal225. During normal read and write operations, transistor403is switched on briefly (i.e., by briefly driving the pulse-precharge signal low) to deliver a burst of charging current to the bit line407and thereby more quickly restore the bit line407to a desired voltage level in preparation for a subsequent read or write operation. During a multi-row write operation, transistor405is switched on in response to assertion of the multi-row write signal to supply an additional charging current, IPCB, to a non-driven bit line407to counteract the pull-down effected by non-targeted storage elements (thus effecting multiple charging rates). The multi-row write signal may be logically combined with decoded select signals (e.g., segment select, array select, etc.) to enable the additional charging current to be selectively provided to mask bit lines in non-driven segments of a CAM array or non-selected CAM arrays within a multi-array CAM device. Also, in an alternative embodiment, transistor403may be switched on in response to both the low-going pulse-precharge signal402and assertion of the multi-row write signal. In such an embodiment, transistor405being omitted altogether or being switched on in combination with transistor403during a multi-row write operation. More generally, any circuit for selectively delivering additional charging current to non-driven bit lines during a multi-row write operation may be used in alternative embodiments.

FIG. 11illustrates an embodiment of a current sinking circuit420that may be used within the line driver370ofFIG. 9(e.g., in place of the current sinking transistor377) to enable selection of different levels of added discharge current, IBST, in accordance with the number of rows selected to participate in a multi-row write operation (thus effecting multiple discharge rates). As discussed above, the number of rows selected to participate in a multi-row write (i.e., the group-size) may be specified as part of a multi-row write instruction (i.e., in the operation code or operand) and/or may be established by programming a mode value within a configuration circuit (e.g., configuration circuit212ofFIG. 4). In the particular embodiment ofFIG. 11, group sizes of four, eight and sixteen rows are signaled by group-size signals x4, x8 and x16, respectively. When the x4 signal and control signal (C) are asserted, AND gate421and OR gate424operate to switch on transistor427, thus providing a first level of additional discharge current within a line driver. When the x8 signal and control signal C are asserted, AND gate422and OR gates424and425operate to switch on transistors427and429, providing a second, higher level of additional discharge current, and when the x16 signal and control signal C are asserted, AND gate423and OR gates424and425operate to switch on transistors427,429and431, thereby providing a third, yet-higher level additional discharge current. In one embodiment, transistors427and429are the same size (i.e., have the same gain) and transistor431has twice the gain of transistor429(transistor431being illustrated inFIG. 11by a common-gate transistor pair) to provide for an approximately doubled level of IBSTfor each doubling of the group size. Different circuit arrangements for providing different levels of additional discharge currents may be used in alternative embodiments, and more or fewer group-size signals may be provided.

FIG. 12illustrates a current sourcing circuit450that operates in substantially the same manner as the current sinking circuit ofFIG. 11to provide different levels of additional charging current (IPCB) within the precharge circuit ofFIG. 10(e.g., by substituting circuit450for transistor405). That is, AND gates451,452and453, and NOR gates454and455respond to group-size signals x4, x8 and x16 and the multi-row write signal (MRW) by selectively switching on transistors457,459and461to establish different levels of additional bit line charging current.

The section headings provided in this detailed description are for convenience of reference only, and in no way define, limit, construe or describe the scope or extent of such sections. Also, while the invention has been described with reference to specific embodiments thereof, it will be evident that various modifications and changes may be made thereto without departing from the broader spirit and scope of the invention. The specification and drawings are, accordingly, to be regarded in an illustrative rather than restrictive sense.