High density search engine

A content addressable memory (CAM) search engine is disclosed. The CAM search engine includes a data compare plane having a content addressable memory die including an array of comparison cells. The CAM search engine further includes a memory stack on the data compare plane. The memory stack has stacked memory dies including memory banks. The array of comparison cells includes parallel interconnects. The parallel interconnects electrically connect to outputs of the memory banks. The comparison cells are time-shared among the one or more memory banks.

FIELD OF INVENTION

This invention relates generally to a content addressable memory (CAM) and, more particularly, to a stacked, three-dimensional (3D) device providing a high-capacity CAM search engine.

BACKGROUND

A CAM is a storage device in which data can be identified through a parallel search operation. A CAM typically includes an array of storage cells arranged in rows and columns, where each row of the CAM array corresponds to a stored word of reference data. The storage cells in a given row couple to a word line and a match line associated with the row. The word line is used to select the row for a read/write operation while the match line is used to signal a match or a miss during the search operation. Each column of the conventional CAM array corresponds to the same bit position in all of the words. The storage cells in a particular column are coupled to a pair of bit lines and a pair of search-lines associated with the column.

During a search operation, the match line develops a signal that indicates whether the word stored in the row matches a word of search data. The search data is applied to each pair of search lines, which have a pair of complementary binary signals or unique ternary signals thereon that represent a bit of an input value. Each CAM cell changes the voltage on the associated match line if the storage cell stores a bit that does not match the bit represented on the attached search lines. If the voltage on a match line remains unchanged during a search, the word stored in that row of storage cells matches the entire word of search data.

CAMs are much faster than conventional random access memory (RAM) for searching stored data because a search of all the words can be performed in parallel. However, use of CAMs is limited because of their large size, high cost, and large amounts of heat generated in comparison to conventional RAMs. For example, CAM cells are conventionally implemented using two static RAM (SRAM) cells and bit-compare circuitry (e.g., 16 transistors), which can require a large area ten times larger than conventional dynamic RAM (DRAM).

SUMMARY

In an aspect of the invention, a CAM search engine comprises a data compare plane having a content addressable memory die including an array of comparison cells. The CAM search engine further comprises a memory stack on the data compare plane. The memory stack has stacked memory dies including memory banks. The array of comparison cells comprises parallel interconnects. The parallel interconnects electrically connect to outputs of the memory banks. The comparison cells are time-shared among the one or more memory banks.

In further aspects of the invention, a method comprises providing a subset of reference data selected from reference data stored in a memory stack onto an array of parallel vertical interconnects of a data compare plane. The method also comprises applying search data to the subset of reference data on the vertical interconnects via search lines of the data compare plane. The method further comprises reading results of the applied the search data to the subset of reference data from match lines of the data compare plane. Additionally, the method comprises storing the results in a match analysis plane.

In further aspects, a stacked, three-dimensional CAM search engine comprises a memory stack comprising memory dies including a plurality of memory banks. The CAM search engine further comprises a data comparison die comprising search lines, match lines and an array of comparison cells. The comparison cells comprise an array of vertical interconnects electrically connected to respective outputs of the memory stack. The search lines connect the comparison cells in columns to an input register. The match lines connect the comparison cells in rows to outputs.

In another aspect of the invention, a design structure tangibly embodied in a machine readable storage medium for designing, manufacturing, or testing an integrated circuit is provided. The design structure comprises the structures of the present invention. In further embodiments, a hardware description language (HDL) design structure encoded on a machine-readable data storage medium comprises elements that when processed in a computer-aided design system generates a machine-executable representation of a CAM search engine, which comprises the structures of the present invention. In still further embodiments, a method in a computer-aided design system is provided for generating a functional design model of the CAM search engine. The method comprises generating a functional representation of the structural elements of the CAM search engine.

DETAILED DESCRIPTION

This invention relates generally to a content addressable memory (CAM) and, more particularly, to a stacked, three-dimensional (3D) device providing high-capacity CAM search engine. The CAM search engine in accordance with aspects of the invention integrates a memory stack with a data comparison plane. In embodiments, parallel thru-silicon vias (TSVs) vertically connect outputs of the memory stack to an array of comparison cells of the data compare plane. The CAM search engine streams a serial stream of reference data from high-density memory in the memory stack to the compare plane. The comparison cells of the data compare plane are time-shared by the high-density memory in the memory stack, which provides for higher bandwidth and lower power consumption than a similar capacity conventional CAM.

For example, embodiments of the present invention connect DRAMs in the memory stack to the data compare plane using TSVs having, for example, a 2.5 μm pitch. The pitch of the TSVs reduces cell density of the CAM search engine by a factor of about 10 to 30 in comparison to a conventional CAM. However, the density of the DRAMs in the memory stack increases the storage capacity of the CAM search engine by a factor of more than 400; that is, when operated at twenty times lower speed (e.g., during data search operations), the CAM search engine in accordance with the present invention can occupy 400 times less space than the conventional CAM. Accordingly, the CAM search engine can occupy about 20-40 times less space than a conventional CAM of similar size while providing performance that is about equal.

FIG. 1shows an exemplary environment100for implementing the steps in accordance with aspects of the invention. To this extent, the environment100includes a server or other computing infrastructure112that can perform the processes described herein. In particular, the computer infrastructure112includes a computing device114. The computing device114can be resident on a network infrastructure or computing device of a third party service provider (any of which is generally represented inFIG. 1).

The computing device114also includes a processor120, memory122A, an I/O interface124, and a bus116. The memory122A can include local memory employed during actual execution of program code, bulk storage, and cache memories which provide temporary storage of at least some program code in order to reduce the number of times code must be retrieved from bulk storage during execution. In addition, the computing device114includes a read-only memory (ROM)122B, a random access memory (RAM)122C (e.g., SRAM), and an operating system (O/S). The computing device114is in communication with a storage system128. The bus116provides a communication link between each of the components in the computing device114.

In general, the processor120executes computer program code (e.g., program control144), which can be stored in the memory122A and/or the storage system128. Moreover, in accordance with aspects of the invention, program control144controls a search module148to perform one or more of the processes described herein using CAM search engine150. The search module148can be implemented as one or more sets of program code in the program control144stored in memory122A as separate or combined modules. Additionally, the search module148can be implemented as a state machine, as separate dedicated processors, or a single or several processors to provide the functionality described herein. In embodiments, the search module148can be integrated in the CAM search engine150.

While executing the computer program code, the processor120can read and/or write data to/from memory122A,122B, and122C, storage system128, and CAM search engine150. The program code executes the processes of the invention.

In embodiments of the invention, the search module148includes computer program code stored in, for example, memory122A and/or122B that, when executed by the processor120, causes computing device114to perform a search that compares search data to reference data using the CAM search engine150. In embodiments, the search module148receives search data from a software module (e.g., a user interface module, an address look-up module, or a pattern recognition module), and initiates a search of reference data stored in the CAM search engine150. Additionally, in embodiments, the search module148controls the search performed by the CAM search engine150. For example, the search module148may implement one or methods for serially providing reference data stored in a memory stack of the CAM search engine150to a data compare plane of the CAM search engine150. Further, in embodiments, the search module148can change and/or update the reference data by writing information to the memory stack of the CAM search engine150. Moreover, based on the results provided by the CAM engine150, the search module148may determine search data and/or reference data for a subsequent search. For example, using the results of an initial search of the reference data, the search module148may perform a subsequent search to obtain narrower results.

FIG. 2illustrates an exemplary binary CAM (“BCAM”)200. The BCAM200includes an input register205, search line pairs210A/210A′ . . .210D/210D′, match lines215A . . .215C, sense amplifiers220A . . .220C, and an array of storage cells225. The storage cells225have two states: a high state (i.e., “1”) and a low state (i.e., “0”). The high state and the low state may represent a high digital logic voltage (e.g., 1.0V) and a low digital logic voltage (e.g., 0.0V), respectively. The input register205stores a row of search data230, which is a word comprised of bits to be searched in the array of storage cells225. Each bit of the input register205corresponds to a respective column of the search line pairs210A/210A′ . . .210D/210D′.

The search line pairs210A/210A′ . . .210D/210D′ connect individual bits of data stored in the input register with respective columns in the array of storage cells225. The first bit (i.e., the most significant bit) of the input register205is connected to a column of the array of storage cells225along the search line pair210A/210A′, the second bit of the input register205is connected to a column of the array of storage cells225along the search line pair210B/210B′, the third bit of the input register205is connected to a column of the array of storage cells225along the search line pair210C/210D′, and the fourth bit (i.e., the least significant bit) of the input register205is connected to a column of the array of storage cells225along the search line pair210D/210D′. The match lines215A . . .215C connect rows of the array storage cells225to respective ones of output sense amplifiers220A . . .220C. Match line215A connects row235A to sense amplifier220A, match line215B connects row235B to sense amplifier220B, and match line215C connects row235C to sense amplifier220C. The storage cells225in each row220A . . .220C contain reference data, which are words comprised of digital bits. A processor (e.g., processor120executing search module148) can store the reference data in the storage cells225using conventional techniques for storing information in a computer memory or storage device. For example, the words of reference data may addresses information corresponding to a database.

The BCAM200performs a search of the reference data by applying the search data in the input register205to reference data stored in the array of storage cells225of the BCAM200along each of the search line pairs210A/210A′ . . .210D/210D′. In parallel, search results develop a voltage on the match lines215A . . .215C. A digital voltage (e.g., 0.0 V or 1.0 V) on each of the match lines215A . . .215C indicates whether value of the corresponding word of the reference data misses or matches with the search data. The output sense amplifiers220A . . .220C detect the voltages developed on the match lines215and generate signals at outputs240A . . .240C having digital voltage indicting the miss or the match between the search data230and the respective reference data in rows215A . . .215C.

For example, the search data230in the input register of the BCAM200inFIG. 2can have the value 1-0-1-0. The array of storage cells225in rows215A . . .215C of the BCAM200store three words of reference data, including 0-1-0-1, 1-0-1-0, and 1-0-1-1. Each bit of the search data230is compared to the respective bits of the reference data in rows215A . . .215C along the search line pairs210A/210A′ . . .210D/210D. If there are any mismatches between a particular bit of the search data230and a corresponding bit of the reference data, then the respective one of match lines215A . . .215C develops a first predetermined voltage (e.g., 0.0V). In this example, if reference data stored in the fourth storage cell225of rows215C does not match a corresponding bit of search data in the input register205along match line pair210D/210D′, the match line215C develops the first predetermined voltage, which is detected by the output sense amplifier220C to generate an output logic signal240C indicating a mismatch. On the other hand, if all the bits of the search data match the corresponding bits of the reference data, then the respective ones of match lines215A . . .215C develops a second predetermined voltage (e.g., 1.0V). For instance, if the reference data stored in each of the storage cell225of row215B matches the corresponding bits of search data in the input register205along match line pairs210A/210A′ . . .210D/210D′; the match line215B develops the second predetermined voltage. This second predetermined voltage is detected by the output sense amplifier220B to generate output logic signal240B indicating a match.

As described above, the BCAM200performs a parallel search of all the reference data in a single clock cycle. Thus, the BCAM200provides a fastest known way to implement compare search data within, for example, a look-up table. Notably, the BCAM200shown inFIG. 2includes four columns and three rows for the sake of illustration. However, the BCAM200can include a greater amount of columns and rows.

FIG. 3illustrates an exemplary ternary CAM (TCAM)300. The TCAM300includes input register205, search line pairs210A/210A′ . . .210D/210D′, match lines215A . . .215D, output sense amplifiers220A . . .220C, and outputs240A . . .240C, which may the same as those already described herein. Additionally, the TCAM300includes an array of storage cells325that each can have three states, including a high state (i.e., “1”), a low state (i.e., “0”), and a wildcard state (i.e., “X”). The high state and the low state may represent a high digital logic voltage (e.g., 1.0V) and a low digital logic voltage (e.g., 0.0V), respectively. The wildcard value “X” is neither a 0 nor a 1. More specifically, a TCAM can encode data using two storage cells per bit of data. In embodiments, the low state of the bit is stored in the two cells as 0/1, the high state is stored in the two cells as 1/0, and the wildcard stated can be stored in the two cells 0/0. Wildcards are used, for example, in routing tables to allow longest prefix matching for network addresses. A value stored in a particular storage cell325that is an X is considered to match a corresponding bit of the search data230regardless of whether has the high state or the low state. For example, the exemplary TCAM300inFIG. 3includes three words in the storage cells325, including a first word235A (0-1-0-1), a second word235B (1-0-X-X), and a third word235C (1-X-X-X). As is evident inFIG. 3, the value of the second word235B (1-0-X-X) matches the value of the search data230of the input register205(1-0-1-0) because the first two bits are the same and the last two bits of the second word are wildcards. Similarly, the third word235C (1-X-X-X) matches the value of the search data230of the input register205(1-0-1-0) because the first bits are the same and the last three bits of the second word are wildcards.

FIG. 4illustrates a single row235A in an embodiment of an exemplary TCAM400. The ternary CAM400includes search line pairs210A/210A′ . . .210D/201D′, match line215A, and output sense amplifier220A, which can be the same as those already described herein. Additionally, row235A includes an array of storage cells425, which can be the same as the storage cells shownFIGS. 2 and 3. Each of the storage cells425include respective pairs of sub-cells425A/425A′ . . .425D/425D′ that each store two values representing the data stored in the storage cells425. The sub-cells425A/425A′ . . .425D/425D′ in each storage cell425can be, for example, SRAM cells. The pairs of sub-cells425A/425A′ . . .425D/425D′ take on the same or different logic states (i.e., high or low). For example, if the values425A and425A′ are “0” and “1”, then the logic state is low. On the other hand, if the values425A and425A′ are “1” and “0”, then the logic state is high. And, if the values425A and425A′ are “0” and “0” then the logic state is Wildcard (i.e., “X”). The fourth state when the values425A and425A′ are “1” and “1” is the always-miss state and is not typically used in a TCAM.

To perform a search operation, the TCAM400initially resets the search lines210A/210A′ . . .210D/210D′ to ground voltage (e.g., 0.0V). The match line215A is precharged to a nominal voltage (e.g., 1.0V). Then, the TCAM400applies search data (e.g., search data230) to each of the search lines210A/210A′ . . .210D/210D′ (e.g., via the input register205). Any mismatches between the search data on the search lines210A/210A′ . . .210D/210D′ and the respective values stored in the storage cells425A . . .425D are detected on the match line215A as logic voltage and outputted by the sense amplifier220A. For example, a mismatch between a bit of search data (e.g., search data230) applied to the pair of search lines210A/210A′ can change the value to the match line215A from the nominal voltage to a ground voltage (e.g., from 1.0V to 0.0V). The resulting voltage of the match line215A causes the sense amplifier220A to output a digital logic signal (e.g., 0.0V), which indicates mismatch. On the other hand, if all of the search data on search lines210A/210A′ . . .210D/210D′ match the respective bits of the reference data (i.e., the reference data has the same value as the search data or a wildcard value), then the resulting voltage of the match line215A will remain at the nominal voltage (e.g., about 1.0V). This causes the sense amplifier220A to output a high digital logic voltage (e.g., about 1.0V), which indicates a match. WhileFIG. 4shows only a single row235A of the array of storage cells425, the array can have any size. The TCAM400can compare search data with reference data of the entire search array of storage cells425in one memory cycle.

FIG. 5illustrates an exemplary high-density CAM search engine500in accordance with aspects of the present invention. In embodiments, the CAM search engine500is a stacked, 3D device including a memory stack510, a data formatting plane520, and a data compare plane530. The CAM search engine500provides a serial stream of reference data from the memory stack510into the data compare plane530for comparison with search data (e.g., search data230). Memory banks in the memory stack time-share comparison cells in the comparison plane, which results in high-density, high-bandwidth, and power-efficient search engine.

In accordance with aspects of the invention, the memory stack510is a stacked, 3D memory array comprising memory dies515, each of which includes one or more memory banks. In embodiments, the memory stack510is a stack of DRAM banks. For example, the memory stack510can be formed using several substantially identical memory dies515including one or more DRAM banks, which provide high-density storage of reference data (e.g., greater than 64 gigabytes) in the CAM search engine500.

In accordance with aspects of the present invention, the data formatting plane520is a die in the CAM search engine500that interfaces the memory stack510with the data compare plane530. The data formatting plane520aggregates reference data provided from the memory stack510and remaps the reference data into a format for the data compare plane530. The data formatting plane520includes parallel interconnects that make electrical connections between the outputs of memory banks in the memory stack510and the comparison cells in the data compare plane530. In embodiments, the parallel interconnects include TSVs through the data compare plane520. The parallel interconnects of the data formatting plane520can route the reference data to comparison cells in the data compare plane530using an array of parallel vertical TSVs that vertically align with the comparison cells. Accordingly, by implementing aspects of the invention the parallel interconnects of the data formatting plane520physically route outputs of the memory stack510that are not in direct alignment with corresponding comparison cells in the data compare plane530. For example, the memory stack510can connect to the data formatting plane510at the locations corresponding to the output pins of DRAM banks of the memory stack510.

In accordance with aspects of the invention, the data compare plane530is one or more dies in the CAM search engine500that determines whether reference data matches a given set of search data. The data compare plane530can have a structure similar to the CAMs described previously (e.g., BCAM200, TCAM300, and TCAM400). However, the data compare plane530is not limited to the CAM structures shown inFIGS. 2-4, and other types of TCAM structures can be used in embodiments of the invention. For example, the data compare plane530can be structured as a hybrid NOR/NAND TCAM, an algorithmic TCAM, a binary tree, a hashing, or other such conventional CAM structures.

In accordance with aspects of the invention, the CAM search engine500uses logic (e.g., search module148) and data storage (e.g., memory122A) that controls the streaming of reference data from the memory stack510to the data compare plane530. The logic and data storage can be incorporated in any one of the memory stack510, the data formatting plane520, and the data compare plane530, or distributed amongst them. High-density macros (e.g., search module148) control the CAM search engine500to stream reference data in a predictable manner from the memory stack510, though the data formatting plane520, to the data compare plane530by cycling though each word of reference data. For example, control logic in the data formatting plane may maintain a data buffer that queues a selected subset of the reference data provided by the memory stack. The data buffer can output the subset of reference data in parallel to the array of parallel load vertical interconnects of the data compare plane520via the wiring and/or TSVs of the data formatting plane520.

Additionally, in embodiments of the invention, bandwidth is increased using DRAM data bursting (e.g., cycling though DRAM decodes), wherein each memory bank provides data in parallel, rather than using global data lines to their peripheries. The data compare plane530compares search data to the burst serial data provided by the memory stack510. Further, in embodiments, refresh controllers for memory banks (e.g., DRAM refresh controllers) can be simplified because of the predictable access pattern (e.g., vertical or horizontal sequential retrieval of reference data). Moreover, in embodiments, the CAM search engine can be an algorithmic CAM to improve area at the cost of performance in particular applications.

Further,FIG. 5shows the memory stack510connected to the data compare plane530though the data formatting plane520. In embodiments of the invention, the data compare530can be directly connected to the memory stack510without the data formatting plane520. For example, the memory stack510can includes a shift register that supplies information from the memory stack data510to comparators on the data compare plane530.

FIG. 6shows an exemplary data formatting plane520in accordance with aspects of the present invention. The data formatting plane520is one or more dies that provide a physical and logical interface between the memory stack510and the data compare plane530. For example, the data formatting plane520implements TSV image reformatting and data organization in the CAM search engine500to interface the memory stack510with the data compare plane530. In accordance with aspects of the invention, the data formatting plane520physically integrates the memory stack510with the data compare plane530.

In embodiments, the data formatting plane520includes a die605having an upper surface610and lower surface615. The upper surface610includes upper connectors620and the lower surface includes lower connectors625. For clarity,FIG. 6shows a partially exploded view in which lower connectors625are illustrated apart from the data formatting plane520. However, the exploded view is merely provided to better show the arrangement of the lower connectors625. The lower connectors625are located on the lower surface625of die615and can be in direct electrical connection with the corresponding ones of the upper pins610. As such, in embodiments of the invention, the lower connectors625are arranged in an array, having locations corresponding to an array of parallel vertical interconnects (e.g., TSVs) in the data compare plane530. By comparison, the upper connectors620are arranged to correspond to output connections of the memory stack510.

According to aspects of the invention, the upper surface610of the data formatting plane520interfaces with the memory stack510. The upper surface610includes the upper connectors620and memory shadow areas630. The upper connectors620can be metal contacts (e.g., connector pins and/or TSVs). The memory shadow areas630are regions beneath (i.e., in the shadow of) memory banks of the memory stack510. This is because input/output connections (e.g., pins) of the memory banks (e.g., DRAMs) are typically located around the periphery of the memory banks, and not directly below the bodies of the memory banks. Thus, in accordance with aspects of the invention, the data formatting plane520has upper connections (e.g., input pins)620at locations corresponding to the input/output connections of the memory banks, and lacks pins at locations directly beneath the bodies of the memory banks (i.e., the memory shadow regions630). In embodiments, the memory shadow regions630are areas on the upper surface610of the data formatting plane520that lack any input/output signal connections to the memory stack510. The lower surface615interfaces with the data compare plane530via the lower connectors625. In embodiments, the lower connectors625are distributed as an array pattern that corresponds to locations of comparison cells arrayed in the data compare plane530. The lower connectors may be distributed uniformly with respect to the data compare plane530.

FIG. 7shows an exemplary data compare plane530in accordance with aspects of the invention. In embodiments, the data compare plane530includes input register205, search line pairs210A/210A′ . . .210D/210D′, match lines215A . . .215C, and sense amplifiers220A . . .220C, which may be arranged and function the same as those already described herein. Additionally, in accordance with aspects of the invention, the data compare plane530includes an array of data comparison cells725that are electrically connected to storage cells in the memory stack510via the data formatting plane520, by respective pairs of parallel vertical interconnects730. The vertical interconnects730can be, for example, TSVs.

In operation according to aspects of the invention, search data (e.g., search data230) input to the input register (e.g., by processor120) is applied to the search lines210A/210A′ . . .210D/210D′. Reference data stored in the memory stack510is iteratively read and applied to the data comparison cells725through respective ones of the vertical interconnects730. For each iteration of reference data applied to the search lines210A/210A′ . . .210D/210D′, the match lines215A . . .215C indicate whether the reference data matches the search data in a similar manner to that described above with regard toFIGS. 2-4. The sense amplifiers220A . . .220C receive the result of matching from the match lines215A . . .215C and output a corresponding digital logic voltage.

In embodiments, the sets of reference data are serially provided from the memory stack510to the data compare plane530. For example, each subset of reference data retrieved from a memory stack (e.g., memory stack510) can be applied to the vertical interconnects730of the comparison cells725. As such, a number of iterations are used to compare an entire set of reference data in the memory stack to the search data. Due to the high data capacity, the CAM search engine500can provide the same or better parallel performance as a conventional CAM using 20 to 40 times less space.

FIG. 8Aillustrates a CAM search engine800in accordance with additional aspects of the present invention. The CAM search engine800includes memory stack510, data formatting plane520, and data compare plane530that may the same as those already described herein. Additionally, in accordance with aspects of the invention, the CAM search engine800includes a match analysis plane810. In embodiments, the match analysis plane810includes one or more data storage hardware devices that stores previous data that has returned a match and, additionally, stores pertinent record information (e.g., identifying information, source addresses, and count of matches). Results from multiple different searches executed on the data from the partial or full memory stack can be kept in the match analysis plane810for further analysis. Thus, results of this search of the memory stack510can be communicated to a system (e.g., computer infrastructure112). Additionally, the match analysis plane810can perform a secondary search of the search results (e.g., a combined-search). More specifically, in embodiments, the search results are stored in the memory stack510and can be used to select a subset of reference data for a subsequent search.

FIG. 8Billustrates a functional block diagram of exemplary CAM search engine800in accordance with aspects of the present invention. The CAM search engine800is a stacked, 3D device including, search module148, memory stack510, data formatting plane520, data compare plane530, and match analysis plane810, which may be the same as those already described herein. In accordance with aspects of the invention, the search module148controls processes of the CAM search engine150. Additionally, in embodiments, the search module148controls power and redundancy of the memory stack510and data compare plane530. The search module148can be external to the CAM search engine800or it can be incorporated (partially or entirely) within to the CAM search engine800. In embodiments, the search module148is one or more sets of program code stored in memory (e.g., memory122A) and executed by a processor (e.g., processor120) of a computer device (e.g., computing device114) that includes the CAM search engine800(which may be the represented as CAM search engine150). In other embodiments, the search module148is implemented as a state machine or as separate dedicated processors, incorporated in the CAM search engine800.

In accordance with aspects of the invention, the memory stack510includes the memory dies515. Each of the memory dies515includes one or more memory banks910, which form a stacked, 3D memory device. The memory banks910can be, for example, DRAM cores. The inputs and outputs of the memory stack510can be through the bottommost one of the memory dies515, which is stacked on the data formatting plane520.

In accordance with aspects of the present invention, the data formatting plane520aggregates and routes information reference data provided from the memory stack510to the data compare plane530. In embodiments, the data formatting plane520includes a data buffer915and parallel vertical die interconnects920. In embodiments, the parallel die interconnects920are TSVs through the die of the data compare plane520. The data buffer915queues a selected subset of the reference data from the memory stack510before providing the subset of reference data to the data comparison plane530. For example, the search module148can select the subset of the reference data in one or more of the memory banks910for comparison with search data. The selected subset of reference data is queued in the data buffer915and then provided to the data comparison plane530. In this manner, the comparison cells of the data compare plane530are time-shared among the memory banks910. Notably, while the data buffer915is shown inFIG. 8Bin the data formatting plane, the data buffer915and/or its functionality can, instead, be incorporated in the memory stack510or the data compare plane530.

Additionally, in accordance with aspects of the present invention, the data formatting plane520includes wiring917that provide electrical connections between the outputs of memory banks910in the memory stack510and the comparison cells725in the data compare plane530. In accordance with aspects of the invention, the wiring917and the parallel die interconnects920physically route outputs of the memory stack510that are not in direct alignment with corresponding comparison cells725in the data compare plane530. For example, the memory stack510may connect to the data formatting plane510at the locations corresponding to output pins of DRAM banks of the memory stack510. The data formatting plane520routes the reference data to the comparison cells725in the data compare plane530using the array parallel die interconnects920that are vertically aligned with the comparison cells725in the CAM search engine800.

In accordance with aspects of the invention, the data compare plane530includes input register205, search lines210, match lines215, sense amplifiers220, outputs240, comparison cells725, and parallel vertical interconnects730, which may be the same as those already described herein. In embodiments, the search module148loads a word of search data into the input register205and controls the data buffer915to provide the subset of reference data provided from the memory stack510to the comparison cells725via the parallel vertical interconnects730. The search module148controls the input register205to apply the word of search data to the subset of reference data via the search lines210. Then the search module148reads and/or stores results provided from the match lines215to the sense amplifiers220via the outputs240.

In accordance with aspects of the invention, the match analysis810plane includes a hardware data storage device925. In embodiments, the search module148stores the results provided by the data compare plane in the data storage device925for further reference and/or analysis. In addition, the search module148can store metadata in association with the results that describes subset of reference data (e.g., identification information, address information, and count information). Additionally, in accordance with aspects of the present invention, the stored search results generated from one or more subsets of reference data can be used as reference data in subsequent comparison iterations executed by the CAM search engine800to produce a narrower result. In embodiments, the search module148feeds back search results stored on the match analysis plane810to the memory stack510for use reference data that is compared to another word of search data by the CAM search engine800.

FIG. 9depicts an exemplary flow of a process900for searching a CAM search engine (e.g., CAM search engine500or CAM search engine800) in accordance with aspects of the invention. In embodiments, a logic module (e.g., search module148) controls the CAM engine to serially stream words of reference data from a memory stack (e.g., memory stack510) and provided to a data compare plane (e.g., data compare plane530) via a data formatting plane (e.g., data formatting plane520). Also, in embodiments, the reference can be provided using burst mode communication, which increases the data transfer rate between individual memory banks in the memory stack510and the data comparison plane530.

At step903, the logic module stores a search (e.g., search word230) into an input register (e.g., input register205). At step905, the logic module reads a selected subset of the reference data stored in the memory stack onto parallel vertical interconnects (e.g., vertical interconnects730) in comparison cells (e.g., comparison cells725) of the data compare plane via the data formatting plane. In embodiments, the subset reference data is retrieved from a number of predefined addresses of the memory stack. For example, the memory stack may include a number of DRAMs that each have a range of predetermined, consecutive memory addresses that contain the reference data. The logic module can maintain data registers that store pointers to current memory addresses being processed by the CAM search engine. Accordingly, the CAM search engine can read the reference data stored at the current memory addresses of the memory stack in one or more memory banks (e.g., memory banks910). In accordance with aspects of the invention, the outputs of the memory stack are connected to corresponding vertical interconnects in an array of data compare cells (e.g., data compare cells725) of the data compare plane by parallel vertical interconnects (e.g., TSVs) included in the data formatting plane, which compares the search data in the input register.

At step907, the logic module applies the word of search data from step903to the subset of reference data provided at step905via search lines (e.g., search lines210A/210A′ . . .210D/210D′). At step909, the CAM search engine reads the results of comparisons between the search data and the current reference data from match lines (e.g., match lines215A . . .215C) of the data compare plane. For example, a sense amplifier (e.g., sense amplifier220A) at the output of the match line in the data compare plane can output a digital logic voltage indicating whether the search data matches the reference data at the TSVs along the corresponding match line. Thus, if the search data matches the reference data (exactly or based on wildcards), then the sense amplifier outputs a first digital logic value. If the search data does not match the reference data, then the sense amplifier outputs a second digital logic value.

At step911, the logic module stores the results read at step909in the match analysis plane. In embodiments, the digital logic voltage output of each sense amplifiers in the data compare plane is stored as word of data in the storage cells of the match analysis plane.

At step913, the logic module determines whether a predefined target is obtained. For example, the target may be to identify a predetermined number of matches (e.g., 1) between the search data and the reference data in a portion of the memory stack510or in the entire the memory stack510. If the target is obtained, then the process ends. Otherwise, at step915, the logic module determines whether the reference data is the last reference data. In embodiments, the logic module determines whether current memory address is the last memory address in the range of memory addresses of the memory stack. If not, the logic module increments the value of the current memory address and iteratively returns to step903. If so, the process ends.

FIG. 10shows an exemplary data compare plane1000that performs 2D matching in accordance with aspects of the invention. The data compare plane1000includes input registers1005xand1005y, search lines1010xand1010y, match lines1015xand1015y, sense amplifiers1020, and an array of comparison cells1025, which may be the same as those already described herein. The input register1005xand the input register1005yinclude respective words of search data that are compared to reference data applied to the array of comparison cells1025. The operation of the data compare plane1000is similar to that already described herein. However, in the present embodiment, the data compare plane1000performs a 2D comparison of search data and reference data. That is, the word of search data in the input register1005xis applied to the array of comparison cells1025by the search lines1010xand results develop on match lines1015x. In parallel, the word of search data in the input register1005yis applied to the array of comparison cells1025by the search lines1010yand results develop on match lines1015y. The search data applied to the input registers1005xand1005ycan be the same word. The comparison cells1025can be BCAM cells or TCAM cells.

Thus, in accordance with aspects of the invention, the data compare plane1000enables a CAM search engine (e.g., CAM search engine800) to perform a 2D search operation with a parallel data load of reference data from a memory stack (e.g., memory stack510). 2D search operations can be used in, for example, image recognition, 2D pattern matching, data graph analysis, and data compression.

FIG. 11shows an exemplary TCAM bit compare circuit1100that performs 2D matching in accordance with aspects of the invention. TCAM bit compare circuit1100includes pairs of search lines1010x/1010x′ and1010y/1010y′, match lines1015xand1015y, sense amplifiers1020, and pairs comparison cells1025/1025′, which may be the same as those already described herein. Reference data (e.g., from memory stack510) is applied to the comparison cells1025/1025′. The search lines1010x/1010x′ apply first search data (e.g., from input register1005x) to the comparison cells1025/1025′, respectively. A corresponding first result indicating whether there is a match between the first search data and the reference data on the pairs of comparison cells1025/1025′ develops on the match line1015x. Simultaneously, the search lines1010y/1010y′ apply second search data (e.g., from input register1005y) to the comparison cells1025/1025′, respectively. A corresponding second result indicating whether there is a match between the second search data and the reference data on the pairs of comparison cells1025/1025develops on the match line1015y.

FIG. 12shows an exemplary BCAM bit compare circuit1200that performs 2D matching in accordance with aspects of the invention. The BCAM bit compare circuit1200includes pairs of search lines1010x/1010x′ and1010y/1010y′, match lines1015xand1015y, sense amplifiers1020, which may be the same as those already described herein. Because the BCAM bit compare circuit1200is binary implementation, it includes a comparison cell1205and an inverter1210. The comparison cell1205may be the same as those described previously. The inverter1210generates a compliment of the value in the comparison cell1205. Thus BCAM bit compare circuit includes a single comparison cell1205rather than pairs of comparison cells (e.g., comparison cells1025/1025′). Reference data (e.g., from memory stack510) is applied to the comparison cell1205and the inverter1210. As discussed previously, the reference data can have two states, including a high state (i.e., 1/0) and a low state (i.e., 0/1), and a wildcard state (i.e., 0/0). The search lines1010x/1010x′ apply first search data (e.g., from input register1005x) to comparison cell1205and the inverter1210, respectively. A corresponding first result indicating whether there is a match between the first search data and the reference data on the pairs of comparison cell1205and the inverter1210develops on the match line1015x. Simultaneously, search lines1010y/1010y′ apply a second search data (e.g., from input register1005y) to comparison cell1205and the inverter1210, respectively. A corresponding second result indicating a whether there is a match between the second search data and reference data on the pairs of comparison cell1205and the inverter1210develops on the match line1015y.

Design flow1300may modify depending on the type of representation being designed. For example, a design flow1300for building an application specific IC (ASIC) may differ from a design flow1300for designing a standard component or from a design flow1300for instantiating the design into a programmable array, for example a programmable gate array (PGA) or a field programmable gate array (FPGA) offered by Altera® Inc. or Xilinx® Inc.

FIG. 13illustrates multiple such design structures including an input design structure1320that is preferably processed by a design process1310. Design structure1320may be a logical simulation design structure generated and processed by design process1310to produce a logically equivalent functional representation of a hardware device. Design structure1320may also or alternatively comprise data and/or program instructions that when processed by design process1310, generate a functional representation of the physical structure of a hardware device. Whether representing functional and/or structural design features, design structure1320may be generated using electronic computer-aided design (ECAD) such as implemented by a core developer/designer. When encoded on a machine-readable data transmission, gate array, or storage medium, design structure1320may be accessed and processed by one or more hardware and/or software modules within design process1310to simulate or otherwise functionally represent an electronic component, circuit, electronic or logic module, apparatus, device, or system such as those shown inFIGS. 5-8Band10-12. As such, design structure1320may comprise files or other data structures including human and/or machine-readable source code, compiled structures, and computer-executable code structures that when processed by a design or simulation data processing system, functionally simulate or otherwise represent circuits or other levels of hardware logic design. Such data structures may include hardware-description language (HDL) design entities or other data structures conforming to and/or compatible with lower-level HDL design languages such as Verilog and VHDL, and/or higher level design languages such as C or C++.

Design process1310employs and incorporates logic and physical design tools such as HDL compilers and simulation model build tools to process design structure1320together with some or all of the depicted supporting data structures along with any additional mechanical design or data (if applicable), to generate a second design structure1390.

Design structure1390may also employ a data format used for the exchange of layout data of integrated circuits and/or symbolic data format (e.g. information stored in a GDSII (GDS2), GL1, OASIS, map files, or any other suitable format for storing such design data structures). Design structure1390may comprise information such as, for example, symbolic data, map files, test data files, design content files, manufacturing data, layout parameters, wires, levels of metal, vias, shapes, data for routing through the manufacturing line, and any other data required by a manufacturer or other designer/developer to produce a device or structure as described above and shown inFIGS. 5-8Band10-12. Design structure1390may then proceed to a stage1395where, for example, design structure1390: proceeds to tape-out, is released to manufacturing, is released to a mask house, is sent to another design house, is sent back to the customer, etc.