Patent Description:
Network devices use ternary content addressable memory (TCAM) for packet processing tasks that rely on fast memory lookups, such as lookups in an access control list or route matching. Similar to a binary content addressable memory (BCAM), a TCAM allows for a fast (single clock cycle) search with a key or tag. The TCAM compares the tag to all words or entries of the TCAM. In addition to the <NUM> (match) and <NUM> (no match) states of a BCAM, the TCAM allows a third state referred to as the "don't care" or wildcard state. Packet processing leverages this wildcard state of the TCAM for partial matching of addresses and/or routes. A wildcard search may be local (i.e., one or more table entries has a bit set to be the wildcard) or global (i.e., a wildcard bit is set in the search key).

Reference is made to <CIT> which discloses a semiconductor device that includes a memory system is configured to accept input of search data and to search in parallel respective rows of a memory cell array such as a CAM and so forth for data held in a memory. The memory system detects whether an inflow amount of the search data that is input is at least a fixed amount by monitoring a packing ratio of an FIFO buffer that a search command is held. The memory system controls a speed of search processing by dividing the memory cell array into blocks and setting each block as a search processing object in accordance with a result of detection.

Reference is made to <CIT> which discloses a content search system including a CAM device having a plurality of CAM blocks and a governor logic receives a search request and compares the number of CAM blocks required to perform the requested search to a limit number, the limit number being the maximum number of CAM blocks permitted to be used in a requested search operation. If the number of CAM blocks required to perform the requested search exceeds the maximum number of CAM blocks permitted to be used in a requested search operation, then the search operation is rejected. The governing operation can be performed on each requested search, thus limiting power dissipation. The relationship between a maximum number of CAM blocks and power dissipation can be characterized, and a corresponding block limit value can be stored into a memory accessible by governor logic.

The invention is defined in independent claims <NUM>, <NUM> and <NUM>.

Embodiments of the disclosure may be better understood by referencing the accompanying drawings.

The description that follows includes example systems, methods, techniques, and program flows that embody aspects of the disclosure. However, it is understood that this disclosure may be practiced without these specific details. For instance, this disclosure refers to the <NUM> least significant bits of data values being designated for match estimation. Embodiments can designate a different number of bits and/or a different part of data values to be used for match estimation. This can be chosen based on the type of data value (e.g., network address) and design/configuration choice related to degree of accuracy versus resource consumption for storing larger match estimation patterns. In other instances, well-known instruction instances, protocols, structures and techniques have not been shown in detail in order not to obfuscate the description.

With greater demands on network devices to handle larger volumes of data traffic at increasing speeds, larger capacity TCAMs are being created to meet those demands. This increases an already large footprint and an already high dynamic power consumption, which in turn has a corresponding greater power dissipation. The dynamic power consumption by the TCAM creates large voltage swings. In addition to fast ramp rates and high dynamic currents causing wear on the power supply, the corresponding power dissipation exacerbates secondary packaging issues related to thermal management. Although precharging the match lines for a lookup is the primary contributor to high dynamic power consumption and instantaneous current demand, a larger TCAM has a greater number of search lines to drive for a lookup.

To use the larger capacity TCAMs while avoiding these issues, pre-processing can be performed on TCAM lookup requests to intelligently pipeline lookup requests according to a defined power budget that is based on TCAM and power supply specifications. Dividing lookup requests based on a power budget smooths the instantaneous current demand and dynamic power demand. This intelligent pre-processing of lookup requests allows lookup requests that satisfy a power budget based threshold to still complete within a single clock cycle while nominally reducing performance for those lookup requests that would not satisfy the power budget based threshold. When a lookup request will not satisfy the power budget based threshold, the lookup request is split into searches targeting different memory blocks of the TCAM. Thus, each of the resulting searches charges fewer search lines and draws power for a portion of the TCAM memory blocks instead of all of the TCAM memory blocks in a single cycle.

<FIG> is a block diagram of a TCAM with additional logic for tuning instantaneous current demand and dynamic power consumption for a lookup request. The additional logic tunes instantaneous current demand and dynamic power consumption by performing a lookup that exceeds a threshold defined based on a power budget on different sets of memory blocks of the TCAM over time instead of a lookup in parallel across all memory blocks of the TCAM. This amortizes the current demand and dynamic power consumption across multiple clock cycles, thus reducing the voltage swing and allowing the TCAM to perform lookups at a lower ramp rate.

<FIG> depicts a TCAM <NUM> that includes logic blocks and macro-level architectural components. <FIG> limits the depiction of the TCAM <NUM> to blocks corresponding to the splitting of lookup requests for power consumption and current demand amortization. The TCAM <NUM> includes a TCAM interface <NUM>, a block map <NUM>, ternary storage <NUM>, and a lookup power budget based amortizer <NUM>. The TCAM interface <NUM> accepts READ, WRITE, and LOOKUP or SEARCH requests from an external requestor and forwards along an appropriate path in the TCAM <NUM>. The block map <NUM> indicates memory block to logical table mappings. A TCAM will often host multiple logical tables (e.g., an access control list, routing tables of different communication layers, etc.). A request will specify which logical table(s) is being targeted. The TCAM <NUM> accesses the block map <NUM> to determine the appropriate memory blocks to access. The ternary storage <NUM> includes memory blocks or arrays of cells and peripheral circuitry to perform requests. The periphery circuitry can include bit line sense amplifiers and drivers, search line drivers, matchline precharge circuitry, and matchline sense amplifiers. The TCAM <NUM> is depicted with only memory blocks <NUM>, <NUM>. Each of the memory blocks also includes (or is associated with) an intra-block priority encoder. The ternary storage <NUM> also includes an inter-block priority encoder <NUM> to merge the outputs of the intra-block priority encoders. When lookups are performed in parallel across memory blocks of the ternary storage <NUM>, the inter-block priority encoder <NUM> selects from the intra-block priority encoders of the memory blocks <NUM>, <NUM>. For lookups split for amortization, the outputs of the intra-block priority encoders of the memory blocks <NUM>, <NUM> are synchronized before being merged (i.e., selected based on priority). Embodiments can add a command input to the intra-block priority encoders to receive a command signal from the lookup power budget based amortizer <NUM> to indicate when and which outputs are to be buffered to allow for synchronization with other outputs before transmission to the inter-block priority encoder <NUM>. Embodiments can instead add a command input to the inter-block priority encoder to receive a command signal from the amortizer <NUM> to indicate that a lookup has been split over x clock cycles and to select based on priority after elapse of the x clocks cycles to allow for receipt of the outputs. For simplicity, the TCAM <NUM> is depicted with a single search key register <NUM> that connects to the search line (SL) drivers of the different memory blocks <NUM>, <NUM>. Embodiments can input the search/lookup key to the memory blocks of ternary storage differently depending upon the TCAM architecture. The ternary storage <NUM> also includes block enable circuitry to activate or enable particular memory blocks upon which a request is to be performed.

The lookup power budget based amortizer <NUM> has visibility of at least the lookup requests received by the TCAM <NUM>. The lookup power budget based amortizer <NUM> (hereinafter "amortizer") can snoop the lines that carry requests from the TCAM interface <NUM>. When the amortizer <NUM> detects a lookup request, the amortizer <NUM> uses a match estimator <NUM>. The match estimator <NUM> estimates a number of entries in the ternary storage <NUM> that will match the lookup key of the lookup request. This estimate is based on a part of a lookup key designated for the match estimate. For instance, the <NUM> least significant bits of a lookup key can be designated or specified for match estimation. The amortizer <NUM> then compares the match estimate to a split threshold configured in a register <NUM>. If the match estimate exceeds the split threshold, then the amortizer <NUM> performs the lookup of the lookup key in each of the memory blocks <NUM>, <NUM> at different times. For instance, the amortizer <NUM> will communicate a command to the ternary storage <NUM> that enables memory block <NUM> and performs the lookup for the lookup key in memory block <NUM>. After communicating the command that performs the lookup in memory block <NUM>, the amortizer <NUM> submits a command to perform the lookup in block <NUM> - this assumes that the logical table identified in the received lookup request maps to block memory blocks <NUM>, <NUM>. Instead of precharging the matchline in parallel for both memory blocks <NUM>, <NUM> and then driving the search lines in parallel for both memory blocks <NUM>, <NUM>, the TCAM <NUM> places a demand on a power supply for individually searching the memory blocks <NUM>, <NUM>.

Configuration of the split threshold is based on TCAM architecture, power supply of the system using the TCAM, and performance requirements for the system. The number and size of memory blocks in the TCAM along with performance requirements for the system can bound the degree of split possible. For example, a TCAM with <NUM> memory blocks and a requirement that a lookup take a maximum of <NUM> clock cycles would limit the degree of block split for a lookup request to <NUM> blocks per clock cycle - assuming the TCAM can enable memory blocks at that granularity. If these parameters allow for a lookup request to be performed as <NUM> lookups on <NUM> different sets of memory blocks as a maximum degree of split, specification of the TCAM and host system would be used to set the split threshold. The amount of current to drive search lines in a memory block and the power supply capacity of the system along with reliability based limits per lookup (e.g., a maximum voltage for a lookup) can be used to calculate the split thresholds. Continuing with the maximum of <NUM> lookup request split into <NUM> lookups, each step in split (i.e., <NUM> to <NUM> lookups, <NUM> to <NUM> lookups, <NUM> to <NUM> lookups), can be associated with a threshold number of match estimates based on a calculated estimate of current demand to drive the search lines for that number of estimated matches.

While <FIG> provided a general block diagram for the amortizing TCAM, <FIG> is a flowchart of example operations for power budget aware pre-processing of a lookup request for a TCAM. <FIG> refers to an amortizer as performing the operations for consistency with <FIG>. The pre-processing is performed to determine whether or not to split a lookup request into multiple lookups across different memory blocks of ternary storage in a TCAM. The moniker "amortizer" can replaced with another moniker for logic in the TCAM that will evaluate a lookup request to determine whether to split the lookup request. For instance, this logic and/or program code may be in a TCAM controller.

At block <NUM>, an amortizer of a TCAM detects a lookup request. The different types of requests sent to a TCAM can encode a request type identifier. In some implementations, the TCAM will have a different input for lookup requests than other inputs. The receive message block can detect the lookup request based on which input path has been used.

At block <NUM>, the amortizer determines a match estimate based on the match estimate bits of the lookup key. The amortizer estimates the number of entries that will match the lookup key based on the designated part of the lookup key for match estimation. As data has been written into the TCAM and removed or overwritten, bookkeeping data has been updated to count the occurrences of various data/bit patterns in the designated bits. This partial key match is the basis for the estimate of TCAM entries that will match the lookup key.

At block <NUM>, the amortizer determines whether the match estimate satisfies the power budget based splitting threshold. If the match estimate satisfies the splitting threshold, then control continues to block <NUM>. If the match estimate does not satisfy the splitting threshold, then control continues to block <NUM>. Satisfying a threshold can be exceeding or equaling the threshold.

At block <NUM>, the amortizer determines a block activation sequence for n lookups that the lookup request is split into. Depending upon the degree of splitting (n) defined for the splitting threshold that was exceeded, the amortizer determines different sets of memory blocks to activate in each of the lookups that will be performed in sequence to carry out the detected lookup request. If the amortizer is to activate <NUM> blocks in each of <NUM> lookups for the lookup request, the amortizer will determine the block identifiers to submit to the ternary storage in each lookup command.

At block <NUM>, the amortizer inserts the n lookups into a command sequence to the ternary storage with each command either associated with or indicating a different set of memory blocks to enable. This effectively inserts the lookup commands into n stages of a pipeline to the ternary storage.

At block <NUM>, the amortizer asserts a command line to cause results of the split lookup to be merged together. The TCAM can be designed to merge the results of the split lookup. The merging of split lookup results selects based on priority across the clock cycles sufficient to complete the n lookups.

If the split threshold was not satisfied, then the lookup request is carried out conventionally in parallel across the ternary storage according to the lookup request at block <NUM>.

Embodiments can implement the above described amortizer and match estimation differently. <FIG> correspond to embodiments that maintain estimate pattern counts on the TCAM. <FIG> correspond to embodiments that maintain the estimate pattern counts externally from the TCAM but maintain a split per pattern table on the TCAM. <FIG> corresponds to embodiments that use a hardware scanner to determine estimate pattern counts and update a split per pattern table on the TCAM. <FIG> corresponds to embodiments that use a split per pattern table to evaluate lookup requests. <FIG> correspond to embodiments that use a secondary, smaller TCAM within the primary TCAM for maintaining the match estimate part of data written into the primary TCAM.

<FIG> is an example block diagram of a TCAM that maintains a match estimate pattern count on the TCAM. <FIG> depicts a TCAM <NUM> that is similar to the TCAM <NUM> from <FIG>. The TCAM <NUM> is illustrated with a ternary storage <NUM> and a match estimate pattern count table <NUM>. The ternary storage <NUM> is similar to the ternary storage <NUM> in <FIG>, but has a data path <NUM> that returns to the amortizer <NUM>.

As in <FIG>, the amortizer <NUM> includes a match estimator <NUM> and a split threshold register <NUM>. However, the amortizer <NUM> in <FIG> maintains the match estimate pattern count table <NUM> based on received write requests detected from the TCAM interface <NUM>. For writes that insert data, the amortizer <NUM> determines which pattern occurs in the match estimate part of the data to be inserted and updates a corresponding count in the match estimate pattern count table <NUM>. Likewise, the amortizer <NUM> decrements count for a match estimate pattern for data values deleted from the ternary storage <NUM>. To determine the pattern occurring in the match estimate bits of the data being deleted, the amortizer <NUM> submits to the ternary storage <NUM> a read of the address indicated in the delete type write request.

The TCAM <NUM> includes circuitry to select the data path <NUM> instead of an output data path from the ternary storage <NUM> to an external consumer. <FIG> depicts a selecting element <NUM> (e.g., switch or demultiplexer) that selects an output path for data read from the ternary storage. The selecting element <NUM> defaults to selecting the output path that provides data to an external destination with respect to the TCAM <NUM>. A control input from the amortizer <NUM> causes the selecting element <NUM> to select the data path <NUM> when the amortizer <NUM> submits a read to the ternary storage <NUM>. The control input can be sent at a clock cycle corresponding to when the result of the read will be output to the selecting element <NUM> (e.g., x pulses after the read is communicated to the ternary storage <NUM>). Embodiments can use different implementations to provide data being deleted from a TCAM to a search/lookup amortizer to allow the amortizer to update the match estimate pattern count accordingly (e.g., the selection circuitry can be external to the TCAM).

The example match estimate pattern count table <NUM> in <FIG> includes a row for each logical table in the TCAM <NUM> and column per match estimate pattern. A first column <NUM> indicates logical table identifiers. A lookup request will indicate the logical table identifier. Remaining columns <NUM>, <NUM>, <NUM>, and <NUM> each represent a different possible pattern (depicted in hexadecimal representation) of the <NUM> least significant bits (<NUM> LSBs) in a data value written into the TCAM <NUM>. This part of the data values (i.e., the <NUM> LSBs) have been selected to use for match estimation. In the column <NUM>, the counts for the pattern 0xFF for the logical tables <NUM>, <NUM>, <NUM>, and <NUM> that should currently be in the TCAM <NUM> are <NUM>, <NUM>, <NUM>, and <NUM>, respectively. In the column <NUM>, the counts for the pattern 0xFE for the logical tables <NUM>, <NUM>, <NUM>, and <NUM> that should currently be in the TCAM <NUM> are <NUM>, <NUM>, <NUM>, and <NUM>, respectively. In the column <NUM>, the counts for the pattern 0x01 for the logical tables <NUM>, <NUM>, <NUM>, and <NUM> that should currently be in the TCAM <NUM> are <NUM>, <NUM>, <NUM>, and <NUM>, respectively. In the column <NUM>, the counts for the pattern 0x00 for the logical tables <NUM>, <NUM>, <NUM>, and <NUM> that should currently be in the TCAM <NUM> are <NUM>, <NUM>, <NUM>, and <NUM>, respectively. Assuming a split threshold has been set at <NUM> for a <NUM> to <NUM> split of a lookup request, the amortizer <NUM> will split a lookup request on table <NUM> for a lookup key that includes the pattern 0x01 in the <NUM> LSBs.

<FIG> is a flowchart of example operations for maintaining a match estimate pattern count table based on detected write requests to a TCAM. The example operations refer to an amortizer as performing the example operations for consistency with earlier Figures.

At block <NUM>, the amortizer detects a write to the TCAM. Both an insert and a delete may be communicated as write requests, with the delete being an overwrite to a specified address. If the write implements an insert of a data value into the TCAM, then the amortizer reads the <NUM> LSBs of the data value ("match estimate bits") to be written to determine the match estimate pattern at block <NUM>. The pattern can also be considered/referred to as a value of the match estimate bits or match estimate part of the data value. The amortizer then accesses the table based on the logical table identifier indicated in the write request and the determined match estimate pattern at block <NUM>. The amortizer then increments the counter for the logical table and match estimate pattern at the located table entry also at block <NUM>.

For a delete write request ("delete request"), the amortizer reads the match estimate bits of a data value to be deleted at block <NUM>. The amortizer initially submits a read of an address indicated in the delete request. When the data value at the indicated address are returned from ternary storage to the amortizer, the amortizer reads the match estimate bits to determine the match estimate pattern. The amortizer then accesses the match estimate pattern count table based on the logical table identifier indicated in the delete request and the determined match estimate pattern at block <NUM>. The amortizer then the counter for the logical table and match estimate pattern at the located table entry also at block <NUM>.

<FIG> is a block diagram of a lookup amortizing TCAM that uses a split per pattern table based on externally maintained match estimate pattern counts. Data tables (e.g., access control lists and routing tables) stored within a TCAM will be stored in other storage/memory accessible to software that accesses the data tables. The data tables external to the TCAM can be leveraged for counting occurrences of match estimate patterns in data values. In <FIG>, data tables 503A in a memory or storage external to a TCAM <NUM> should be the same as data tables 503B stored in ternary storage <NUM> of the TCAM <NUM>. These data tables 503A, 503B "should" be the same, but difference can arise due to latency in updating, errors, etc..

An instance of program code identified as a match estimate monitor <NUM> includes program code for a match estimator <NUM> and maintains a power budget based splitting threshold <NUM>. The splitting threshold <NUM> can be configured via an interface or configuration file of the match estimate monitor <NUM>. The match estimator <NUM> maintains counts of occurrences of match estimate patterns in data values written to the data tables 503A. The match estimator <NUM> can snoop update requests to the data tables 503A to update match estimate pattern counts per logical table or can periodically scan the data tables <NUM> A to count match estimate pattern occurrences per table. If the match estimator <NUM> maintains the counts of match estimate pattern occurrences based on snooped/detected update requests to the data tables 503A, then the match estimator <NUM> can evaluate one or more changed counts against the splitting threshold <NUM> when or proximate to detection of the count change. If the match estimator <NUM> periodically or in response to a scan condition/trigger (e.g., manual request, detection of a threshold number of updates, etc.) scans the data tables <NUM> A, then the match estimator <NUM> may evaluate counts against the splitting threshold <NUM> while or after scanning the data tables 503A.

Based upon detecting that a match estimate pattern for a logical table(s) satisfies the splitting threshold <NUM>, the match estimate monitor <NUM> sends an update request <NUM> to the TCAM <NUM>. The update request <NUM> encodes a value indicating that the update request <NUM> is a request to update a split per pattern table <NUM> maintained by a lookup power budget amortizer <NUM>. A TCAM interface <NUM> reads the update request <NUM> and communicates the update request <NUM> to the amortizer <NUM> up determining it is an update request for the split per pattern table <NUM>. The example split per pattern table <NUM> includes a row for each logical table stored (or to be stored) in the TCAM <NUM>. A first column <NUM> indicates table identifiers. Remaining columns of the split per pattern table <NUM> correspond to the different match estimate patterns that are possible. Again, assuming that <NUM> bits (least or most significant bits) have been specified for match estimation in data values, the split per pattern table <NUM> includes <NUM> columns for the <NUM> different possible match estimate patterns. The columns can be considered bit maps for the match estimate patterns. Each column (after the table identifier column) corresponds to a bit in a bit map that maps to the match estimate patterns. Thus, the match estimate monitor <NUM> is configured to arrange or organize the match estimate pattern occurrence counts according to the bit mapping presumed by the split per pattern table <NUM>. A subset of those columns are depicted as columns <NUM>, <NUM>, <NUM>, <NUM>. The columns <NUM>, <NUM>, <NUM>, <NUM> represent four different match estimate patterns. Since occurrence counts are maintained external, the split per pattern table <NUM> indicates whether or not a lookup is to be split into multiple lookups. In this example, a single bit is used to indicate whether or not to split a lookup request. The split per pattern table <NUM> indicates that a lookup request with the match estimate pattern mapping to bit <NUM> should be split for logical tables identified as <NUM> and <NUM>. For the match estimate pattern that maps to bit <NUM>, the split per pattern table <NUM> indicates that a lookup request indicating logical table <NUM> or <NUM> should be split to comply with power budget.

<FIG> is a flowchart of example operations for maintaining a match estimate pattern count table and corresponding split per pattern table. <FIG> refers to a match estimate monitor performing the example operations to be consistent with <FIG>, although program code naming can be arbitrary. The operations depicted with blocks <NUM>, <NUM>, <NUM>, <NUM>, <NUM> are similar to the operations depicted in blocks <NUM>, <NUM>, <NUM>, <NUM>, <NUM> of <FIG>.

At block <NUM>, the match estimate monitor detects an update to data tables maintained external to a TCAM but corresponding to data tables in the TCAM. If the update is an insert to a data table, then the match estimate monitor reads the match estimate bits to be written to determine the match estimate pattern at block <NUM>. The match estimate monitor then accesses the match estimate pattern count table based on the table identifier indicated in the update request and the determined match estimate pattern at block <NUM>. The match estimate monitor then increments the counter for the data table and the match estimate pattern at the located match estimate pattern count table entry also at block <NUM>.

At block <NUM>, the match estimate monitor determines whether the incremented count satisfies a splitting threshold. Depending upon configuration, there can be multiple splitting thresholds if there a lookup request can be split into more than <NUM> lookups. For instance, the split values or split states in the split per pattern table <NUM> of <FIG> can have <NUM> bits per entry to indicate one of up to <NUM> possible split states/values: <NUM> for no split, <NUM> for <NUM> to <NUM> split, <NUM> for <NUM> to <NUM> split, and <NUM> for <NUM> to <NUM> split. Each split state would be associated with a different split threshold. If no split threshold is satisfied by the incremented counter, then the process ends.

If a split threshold is satisfied by the incremented counter, then the match estimate monitor generates an update request with the corresponding split value at block <NUM>. The update request indicates the logical table identifier corresponding to the updated data table and the match estimate pattern column or bit location depending on whether the split values are single bit or multi-bit. The match estimate monitor then communicates the update request for the split per pattern table to the TCAM at block <NUM>.

For a delete update to a data table, the match estimate monitor reads the match estimate bits of the data value to be deleted to determine the match estimate pattern at block <NUM>. The match estimate monitor then, at block <NUM>, accesses the match estimate pattern count table based on the table identifier indicated in the delete request and the determined match estimate pattern. The match estimate monitor then decrements the counter for the data table and the match estimate pattern at the located match estimate pattern count table entry, also at block <NUM>.

At block <NUM>, the match estimate monitor determines whether the decremented counter satisfies a splitting threshold. If the decremented counter satisfies a splitting threshold, then control flows to block <NUM>. It can be the case that the decremented counter now satisfied a splitting threshold corresponding to a split value of <NUM> instead of <NUM>. If the decremented counter does not satisfy a splitting threshold, the match estimate monitor performs additional operations to determine whether decrementing the counter transitioned the split value to a non-split state.

At block <NUM>, the match estimate monitor determines whether the counter prior to decrementing satisfies a splitting threshold. The match estimate monitor can store the counter to a temporary variable before decrementing and then use the pre-decrement counter value to evaluate against the splitting threshold(s). If the pre-decrement counter did not satisfy a splitting threshold, then the process ends. If the pre-decrement counter satisfied a splitting threshold, then control flows to block <NUM>.

At block <NUM>, the match estimate monitor generates an update request to set a split state for the corresponding logical table and match estimate pattern of the data value being deleted to a no split state. The match estimate monitor generates the request with indications of the logical table and the bit location or mapped position of the match estimate pattern. Control flows from block <NUM> to block <NUM>.

The use of a split per pattern table may add less circuitry to a conventional TCAM than maintaining the counts of pattern occurrences on a TCAM. However, some additional communication overhead is incurred since the counts are maintained externally. Embodiments can use a hardware scanner in the TCAM to count occurrences of values/patterns in the designated bits of data values for match estimation. Embodiments could use the existing scanner circuitry that is part of the error and redundancy circuitry. The hardware scanning can perform lookups for each match estimation pattern in ternary storage. Additional circuitry can add the hits in ternary storage to obtain a count of entries that have a match estimate pattern. <FIG> is a flowchart of operations for maintaining a split per pattern table for logical tables in a TCAM based on hardware scans of the TCAM entries. The description of <FIG> refers to an amortizer as performing the example operations.

At block <NUM>, the amortizer detects a split update state. The split update state is an event or indication that the amortizer is to run a hardware scanner to count occurrences of match estimate patterns in ternary storage of a TCAM. This can be a periodic scan.

At block <NUM>, the amortizer begins traversing the identifiers of the logical tables represented in the ternary storage. For instance, the amortizer traverses a table map that maps logical tables to memory blocks of ternary storage. At block <NUM>, the activated hardware scanner circuitry begins scanning for match estimation patterns in the match estimation bits of entries in ternary storage of the TCAM for the currently selected logical table. The hardware scanner can scan a register of the match estimation patterns. For each match estimation pattern, the hardware scanner scans across the entries to count the number of entries that match the currently selected match estimation pattern. At block <NUM>, the amortizer determines whether the count satisfies a splitting threshold. If the count does not satisfy the splitting threshold, then the amortizer sets the splitting value for that match estimation pattern for the currently selected logical table to indicate no split (e.g., <NUM> or <NUM>) at block <NUM>. If the count satisfies the splitting threshold, then the amortizer sets the splitting value for that match estimation pattern for the currently selected logical table at block <NUM>.

The amortizer iterates through the logical table identifiers and match estimation patterns. At block <NUM>, the amortizer determines whether there is another match estimation pattern to scan for within the ternary storage. If there is another match estimation pattern to scan for, control returns to block <NUM>. If not, then control flows to block <NUM> at which the amortizer selects the next logical table identifier. If there is not another logical table identifier, then the process ends. Otherwise, control returns to block <NUM>.

Performing a lookup in TCAM that utilizes the split per pattern table and performing a lookup in a TCAM that maintains counts of occurrences of match estimation patterns are similar. However, embodiments that use a split per pattern table remove the determination of whether a split threshold has been satisfied from the lookup path. <FIG> is a flowchart of example operations for power budget aware pre-processing of a lookup request for a TCAM using a split per pattern table. <FIG> refers to an amortizer as performing the operations for consistency with the other examples.

At block <NUM>, an amortizer of a TCAM detects a lookup request. The different types of requests sent to a TCAM can encode a request type identifier. In some implementations, the TCAM will have a different input path for lookup requests than other inputs. The amortizer can detect the lookup request based on which input path has been used.

At block <NUM>, the amortizer accesses a split per pattern table to determine whether or not the lookup request should be split. The split per pattern table can be implemented as a register with sufficient entries for m logical tables and p match estimate patterns. The value p is <NUM>b, with b being the number of bits specified for match estimate patterns. The value m can be a configurable parameter of the TCAM. Each entry in the register is sufficient to hold a split value, which depends on the number of splits allowed. If a single split is allowed, then each entry holds a bit. If a lookup can be split into <NUM> lookups, then each entry can hold <NUM> bits for the <NUM> possible split values. The amortizer accesses the split per pattern table with an identifier of a logical table indicated in the lookup request and the pattern or value in the designated match estimate bits of the lookup key.

At block <NUM>, the amortizer determines whether the split value at the accessed entry in the split pattern table indicates that the detected lookup request should be split. If the split value is a no split value (e.g., <NUM>), then control flows to block <NUM>. At block <NUM>, the TCAM performs the lookup in parallel across the memory blocks of ternary storage. If the split value indicates a split, then control flows to block <NUM>.

At block <NUM>, the amortizer splits the lookup into the N lookups depending upon the split value read from the accessed table entry. For example, a split value of '<NUM>' may indicate that the lookup is to be split into <NUM> lookups. The amortizer would determine three different sets of memory blocks to search which correspond to the logical table identifier indicated in the lookup request.

Another technique for determining whether to split a lookup request uses a secondary, smaller TCAM within a primary TCAM. <FIG> is a block diagram of an example TCAM that uses a smaller, internal TCAM for hosting match estimate patterns. A TCAM ("primary TCAM") <NUM> includes a secondary TCAM <NUM> and ternary storage <NUM>. The secondary TCAM <NUM> mirrors the match estimate portion of data values stored into the ternary storage <NUM>. <FIG> depicts the TCAM <NUM> as hosting data tables <NUM>, which are a portion of the data tables <NUM> in the ternary storage <NUM>.

When an amortizer <NUM> of the TCAM <NUM> receives a request from a TCAM interface <NUM>, the amortizer <NUM> duplicates the requests to the secondary TCAM <NUM>. However, the amortizer <NUM> extracts the match estimate bits from the data value of the received request. Assuming a data value is <NUM> bits and the TCAM <NUM> has been configured to treat the <NUM> LSBs as the match estimate bits, the amortizer <NUM> will extract bits <NUM> to <NUM> from selected requests and replace the <NUM> bit data value to be searched or written with an <NUM> bit data value from bits <NUM> to <NUM>. The amortizer selects for duplication lookup requests, delete write requests, and insert write requests. These requests will be processed by the TCAM <NUM>.

However, additional circuitry/logic is added to determine whether a lookup should be split. Instead of a priority encoder, the TCAM <NUM> includes an adder to add the number of hits in ternary storage of the secondary TCAM <NUM> for a lookup key. This sum is communicated to a comparator <NUM>. The comparator <NUM> will read a split value from a split value register <NUM> that has been written (e.g., via an application programming interface or user interface) into the register <NUM>. The comparator <NUM> compares the sum of hits from the TCAM <NUM> and the split value. If the TCAM <NUM> is designed or configured to making a binary split decision (i.e., split a lookup into <NUM> lookups or do not split), then the comparator <NUM> will output a do not split or split indication to the amortizer <NUM>. If the TCAM <NUM> is designed or configured for multiple levels of lookup splitting, then the comparator can output the sum to the amortizer <NUM>. The amortizer <NUM> can determine the extent of splitting based on the sum.

<FIG> is a flowchart of example operations for lookup splitting based using a secondary TCAM for counting occurrences of match estimate patterns in a primary TCAM. The example operations refer to an amortizer as performing the operations for consistency with the rest of the description. The example operations are likely performed by firmware loaded into a TCAM controller.

At block <NUM>, an amortizer detects a request for the primary TCAM. Since writes and lookups are duplicated to the secondary TCAM, read requests are not considered. The amortizer would allow the read request to flow through to ternary storage or the path for read requests would not cross the amortizer within the primary TCAM.

If the request is an insert write request, then at block <NUM> the amortizer generates a corresponding insert write request with a match estimate segment of the data being written. The generated insert write request will have the same logical table identifier as the received insert write request. At block <NUM>, the amortizer communicates the generated insert write request to the secondary TCAM or match estimate TCAM. After processing by the secondary TCAM, the secondary TCAM will have a data value entry that corresponds (the match estimate bits) to a data value entry in ternary storage of the primary TCAM.

If the request is a delete write request, then at block <NUM> the amortizer generates a corresponding delete write request. Unlike the insert write request, the delete write request can be a copy or duplicate of the received delete write request since the delete write request indicates an address or entry to overwrite and not a data value to insert.

If the request is a lookup request, then the amortizer buffers the lookup request at block <NUM> for a number of cycles sufficient for a corresponding lookup request to be performed on the secondary TCAM and a comparator to generate a split indicator output. At block <NUM>, the amortizer generates a corresponding lookup request based on the received lookup request. Similar to an insert write request, the amortizer will extract the match estimate bits of the lookup key so that the generated lookup request is a lookup for the match estimate segment of the lookup key and not the entire lookup key. At block <NUM>, the amortizer communicates the generated lookup request to the secondary TCAM.

After communicating the generated lookup request to the secondary TCAM, the amortizer will receive a lookup result from the comparator as described earlier. At block <NUM>, the amortizer determines whether the lookup result from the comparator indicates a split. If it does not indicate a split, then at block <NUM> the buffered lookup request is released to be performed on the ternary storage of the primary TCAM. If the lookup result from the comparator indicates a split, then at block <NUM> the amortizer generates multiple lookup requests that target different sets of memory blocks in ternary storage of the primary TCAM. The multiple requests effectively splits the requested lookup into multiple lookups to amortize the dynamic power demand. The amortizer will generate the lookup requests based on the lookup result from the comparator (i.e., number of lookups based on split indicator). At block <NUM>, the amortizer sequences the multiple lookups to ternary storage of the primary TCAM.

The above example illustrations describe splitting a lookup into multiple lookups across different sets of memory blocks. Instead of a lookup in parallel across the memory blocks of ternary storage, different sets of memory blocks are enabled in sequence and the lookup is performed on the enabled/activated memory blocks. Embodiments can select the memory blocks in each set based on priority. Assuming a ternary storage has <NUM> memory blocks that can be searched in parallel. Each of the memory blocks will be associated with an address or block identifier within the TCAM. Lower addresses can have higher priority than higher addresses. With a <NUM>:<NUM> split of a lookup, embodiments can generate the lookup requests to search blocks <NUM>-<NUM> in parallel, then blocks <NUM>-<NUM> in parallel, and finally blocks <NUM>-<NUM> in parallel. However, embodiments may allow for dynamic reallocation of memory blocks and dynamic prioritization of memory blocks in a TCAM.

With conventional TCAM devices, data structures or tables are allocated contiguous memory blocks. To resize a table, contiguous memory blocks are reallocated to satisfy the resizing request. As an example, a routing table with Internet Protocol (IP) version <NUM> addresses may have unused entries while a routing table with IP version <NUM> addresses needs additional entries. Dynamic block assignment of memory blocks to logical tables allows for allocation of discontinuous memory blocks, memory block reassignment, and changing prioritization of memory blocks. With dynamic memory block assignment and dynamic prioritization, resizing could be done without disrupting traffic processing. For this, a TCAM has been designed to maintain a register of priority assignments to memory blocks ("block priority register") and a block allocation map that maps logical table identifiers to memory blocks.

<FIG> is a block diagram of a TCAM configured for dynamic block assignment and prioritization. A TCAM <NUM> includes a TCAM interface <NUM> and a TCAM controller <NUM>. A TCAM controller could also include the previously described amortizer and a block map, such as the bock map <NUM> of <FIG>. Other components, such as ternary storage, have not been depicted to avoid unnecessarily complicating the illustration. The TCAM controller <NUM> maintains and uses a block allocation map <NUM> and a block priority map <NUM>. The TCAM controller <NUM> maintains these maps <NUM>, <NUM> based on configuration commands (e.g., register write requests) received via the TCAM interface <NUM>. For example, a resize request may indicate that <NUM> unused entries from table A should be re-assigned to table B.

The TCAM controller <NUM> writes blocks assignments to a register that stores the block allocation map <NUM>. In the block allocation map <NUM>, each row represents an entry that corresponds to a different logical table. In this example, each row implicitly identifies a logical table (e.g., the first row corresponds to the first logical table). Embodiments can implement the block allocation map <NUM> to explicitly identify logical tables. Within each entry, a bit position corresponds to a memory block. Assuming <NUM> memory blocks, there would be <NUM> bits. For block allocation/assignment, the TCAM controller <NUM> will set bit positions to <NUM>. In the illustrated example block allocation map <NUM>, the rightmost bit position of each entry corresponds to memory block <NUM> and the leftmost bit position corresponds to memory block <NUM>. A logical table that can be identified with table identifier <NUM> has at least been allocated memory blocks <NUM> and <NUM>. A logical table that can be identified with table identified <NUM> has been allocated memory blocks <NUM>, <NUM>, <NUM>, and <NUM>. Thus, logical tables in the TCAM <NUM> have been allocated non-contiguous memory blocks.

The TCAM controller <NUM> writes priorities to the block priority map <NUM>. A command that changes block assignment will have a counterpart priority update command, which can be resetting a priority to <NUM> for a deallocated memory block or updating to a specified priority. As discussed earlier, a TCAM includes a priority encoder to select a result when a lookup hits multiple entries. Typically, the data is written to the TCAM according to a priority scheme based, at last partly, on wildcard bits. Instead of a static, implied priority, the TCAM controller <NUM> writes priorities of memory blocks into the block priority map <NUM>. Each entry of the block priority map <NUM> corresponds to a memory block. Memory block identifiers are illustrated in the first column of block priority map <NUM>. The second column of the block priority map <NUM> indicates the assigned priority value. Block <NUM> does not have a priority assigned because block <NUM> has not been allocated to any logical tables as indicated in the illustrated block allocation map <NUM>.

When the TCAM controller <NUM> detects a read or write request, the TCAM controller <NUM> accesses the block allocation map <NUM> to determine the memory blocks on which to perform the request. For lookup requests, both the block allocation map <NUM> and the block priority map <NUM> will be used.

<FIG> is a flowchart of example operations for performing a lookup in a TCAM with dynamic memory block allocation and priority assignment. At block <NUM>, a TCAM controller detects a lookup request that indicates a table identifier and a lookup key. At block <NUM>, the TCAM controller accesses a register with the block allocation map to determine the memory blocks allocated to the identified table. At block <NUM>, the TCAM controller performs the memory lookup in ternary storage on the memory blocks determined to be allocated to the identified table. For instance, the TCAM controllers sends block identifiers for activation to ternary storage circuitry.

At block <NUM>, a priority encoder detects results of the lookup performed in the ternary storage. At block <NUM>, the priority encoder accesses a register that hosts the block priority map to determine priorities of the memory blocks indicated in the lookup results as having at least partial matches to the lookup key. Embodiments can design the priority encoder to have access to the block priority map register directly or indirectly via the TCAM controller. At block <NUM>, the priority encoder determines which of the memory blocks with a hit has highest priority according to the block priority map. The priority encoder then selects for output the value of the memory block determined to have highest priority.

Embodiments can have a TCAM controller with an amortizer and dynamic block allocation and priority assignment. For lookup splitting, the amortizer would access the block allocation map to determine which memory blocks to search and may access the block priority map to determine how to sequence split lookups. With respect to merging lookup results for a split lookup, a priority encoder may buffer results until all results are received before accessing the block priority map. In other embodiments, a priority encoder can access the block priority map as each set of results is received and store the block identifier with high priority for comparison against the highest priority in the next set of results.

The flowcharts are provided to aid in understanding the illustrations and are not to be used to limit scope of the claims. The flowcharts depict example operations that can vary within the scope of the claims. Additional operations may be performed; fewer operations may be performed; the operations may be performed in parallel; and the operations may be performed in a different order. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by program code. The program code may be provided to a processor of a general purpose computer, special purpose computer, or other programmable machine or apparatus.

As will be appreciated, aspects of the disclosure may be embodied as a system, method or computer program comprising instructions which may be stored in one or more machine-readable media and/or carried in one or more computer-readable signals. Accordingly, aspects may take the form of hardware, software (including firmware, resident software, micro-code, etc.), or a combination of software and hardware aspects that may all generally be referred to herein as a "circuit," "module" or "system. " The functionality presented as individual modules/units in the example illustrations can be organized differently in accordance with any one of platform (operating system and/or hardware), application ecosystem, interfaces, programmer preferences, programming language, administrator preferences, etc..

Any combination of one or more machine readable medium(s) may be utilized. The machine readable medium may be a machine readable signal medium or a machine readable storage medium. A machine readable storage medium may be, for example, but not limited to, a system, apparatus, or device, that employs any one of or combination of electronic, magnetic, optical, electromagnetic, infrared, or semiconductor technology to store program code. More specific examples (a non-exhaustive list) of the machine readable storage medium would include the following: a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), a portable compact disc read-only memory (CD-ROM), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing. In the context of this document, a machine readable storage medium may be any tangible medium that can contain, or store a program for use by or in connection with an instruction execution system, apparatus, or device. A machine readable storage medium is not a machine readable signal medium.

A machine readable signal medium may include a propagated data signal with machine readable program code embodied therein, for example, in baseband or as part of a carrier wave. A machine readable signal medium may be any machine readable medium that is not a machine readable storage medium and that can communicate, propagate, or transport a program for use by or in connection with an instruction execution system, apparatus, or device.

Program code embodied on a machine readable medium may be transmitted using any appropriate medium, including but not limited to wireless, wireline, optical fiber cable, RF, etc., or any suitable combination of the foregoing.

Computer program code for carrying out operations for aspects of the disclosure may be written in any combination of one or more programming languages, including an object oriented programming language such as the Java® programming language, C++ or the like; a dynamic programming language such as Python; a scripting language such as Perl programming language or PowerShell script language; and conventional procedural programming languages, such as the "C" programming language or similar programming languages. The program code may execute entirely on a stand-alone machine, may execute in a distributed manner across multiple machines, and may execute on one machine while providing results and or accepting input on another machine.

The program code/instructions may also be stored in a machine readable medium that can direct a machine to function in a particular manner, such that the instructions stored in the machine readable medium produce an article of manufacture including instructions which implement the function/act specified in the flowchart and/or block diagram block or blocks.

While the aspects of the disclosure are described with reference to various implementations and exploitations, it will be understood that these aspects are illustrative and that the scope of the claims is not limited to them. In general, techniques for splitting TCAM lookups as described herein may be implemented with facilities consistent with any hardware system or hardware systems. Many variations, modifications, additions, and improvements are possible.

Plural instances may be provided for components, operations or structures described herein as a single instance. Finally, boundaries between various components, operations and data stores are somewhat arbitrary, and particular operations are illustrated in the context of specific illustrative configurations. Other allocations of functionality are envisioned and may fall within the scope of the disclosure. In general, structures and functionality presented as separate components in the example configurations may be implemented as a combined structure or component. These and other variations, modifications, additions, and improvements may fall within the scope of the disclosure.

Claim 1:
A method comprising:
estimating a number of hits in a first ternary content addressable memory (TCAM) for a lookup key of a lookup request on the first TCAM;
determining whether the number of hits satisfies a first threshold, wherein the first threshold corresponds to a lookup power budget for the first TCAM;
based on a determination that the estimated number of hits satisfies the first threshold, splitting the lookup request into a plurality of lookup requests that each target a different set of one or more memory blocks of the first TCAM; and
pipelining the plurality of lookup requests to a storage component of the first TCAM, wherein the storage component includes the memory blocks,
wherein estimating the number of hits in the first TCAM comprises determining an estimate pattern count of a pattern that is within the lookup key and that should be stored within the first TCAM, wherein the pattern is formed from a subset of bits of the lookup key and wherein the estimated number of hits is the estimate pattern count of the pattern that should be within the first TCAM,
wherein the first TCAM hosts multiple logical tables,
further comprising the first TCAM maintaining in a register of the first TCAM counts of different patterns per logical table that should be in the storage component of the first TCAM.