# US 7,467,129 B1 · Method and apparatus for latency and power efficient database searches > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 7,467,129 B1 - Document ID: US7467129B1 - Status: Granted - Kind: B1 - Application number: 10/325,887 - Filed: 2002-12-23 - Granted: 2008-12-16 - Earliest claimed: 2002-09-06 - Assignees: Kawasaki Microelectronics, Inc. - Inventors: James A. Bong - Web page: https://patentgrep.com/patent/US7467129B1 ## CPC - G06F 16/90339: {by using parallel associative memories or content-addressable memories} - Y02D 10/00: Energy efficient computing, e.g. low power processors, power management or thermal management - Y10S 707/99933: Query processing, i.e. searching - Y10S 707/99942: Manipulating data structure, e.g. compression, compaction, compilation - Y10S 707/99953: Recoverability - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - Y02D: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE - Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS ## Abstract Methods, apparatus and systems perform searches in a CAM memory that is divided into one or more databases. A selector selects at least two the databases for a simultaneous search, and selects at least one of the databases for a sequential search. ## Claims ### Claim 1 An apparatus that performs database searches within a content addressable memory (CAM) structure, comprising: a memory; a plurality of databases stored in the memory; a first selector that selects at least two databases of the plurality of the databases for a simultaneous search, and performs a sequential search within the CAM structure on at least one database of the selected at least two databases, wherein first portions of each database of the at least two databases are searched in parallel based on only a respective portion of a complete search data, and last portions of said each database of the at least two databases are searched individually and serially based on a remaining portion of the complete search data; one or more memory banks, said each database being stored in at least one memory bank; a plurality of segment groups in each memory bank corresponding to groups of database subcomponents, each segment group includes a plurality of segments; and an output section that outputs a search result that is based on the parallel and serial searches, wherein the complete search data for the parallel and serial searches of all of the at least two databases is provided in a number of clock cycles equal to (s−1)+m, wherein s equals a number of the segment groups within each memory bank of the memory banks, and m equals a total number of databases in the at least two databases. ### Claim 2 (depends on 1) The apparatus of claim 1, each database being divided into groups of database subcomponents, the apparatus further comprising: a second selector that selects a group of one or more database subcomponents from at least one of the databases selected by the first selector; and a third selector that selects a portion of database subcomponents selected by the second selector, wherein, portions of database subcomponents selected by the third selector in all of the at least two databases are searched during the parallel searching based on the respective portion of a complete search data provided in a single clock cycle. ### Claim 3 (depends on 2) The apparatus of claim 2, further comprising: second selector information, the second selector selects the group of database subcomponents based on at least one of the input signal and the second selector information. ### Claim 4 (depends on 3) The apparatus of claim 3, wherein a first selector information and the second selector information are stored in a memory. ### Claim 5 (depends on 4) The apparatus of claim 4, wherein the first selector information and the second selector information are at least one of lookup table and state information. ### Claim 6 (depends on 3) The apparatus of claim 3, wherein the first selector and the second selector are finite state machines. ### Claim 7 (depends on 2) The apparatus of claim 2, further comprising: third selector information, the third selector selects the portion of the database subcomponents based on at least one of an input signal and the third selector information. ### Claim 8 (depends on 7) The apparatus of claim 7, wherein the third selector information is masking information stored in a memory. ### Claim 9 (depends on 7) The apparatus of claim 7, wherein the third selector includes a register. ### Claim 10 (depends on 2) The apparatus of claim 2, wherein the third selector selects at least one of the portions of database subcomponents based on the results of a previous parallel search using one of the portions of the complete search data. ### Claim 11 (depends on 1) The apparatus of claim 1, further comprising: a receiver that receives an input signal; and first selector information, the first selector selecting the databases for at least one of simultaneous search and sequential search based on at least one of the input signal and the first selector information. ### Claim 12 (depends on 1) The apparatus of claim 1, wherein the apparatus powers down at least one of databases not selected by the first selector and groups of database subcomponents not selected by a second selector. ### Claim 13 (depends on 1) The apparatus of claim 1, wherein the complete search data for the parallel and serial searches of all of the at least two databases is provided in a number of clock cycles equal to (n−1)+m, wherein “n” equals a number of the portions of the complete search data, and “m” equals a total number of databases in the at least two databases. ### Claim 14 An apparatus that performs database searches within a content addressable memory (CAM) structure, the searches based on a complete search data that is divided into a number of parts, the apparatus comprising: a memory; a plurality of databases stored in the memory, each database is divided into groups of database subcomponents; a first selector that selects at least two databases of the plurality of the databases for a simultaneous search, and performs a sequential search within the CAM structure on at least one database of the selected at least two databases; a second selector that selects a group of the database subcomponents from the at least one database of the databases selected by the first selector, wherein first portions of each database of the at least two databases are searched in parallel based on first parts of the complete search data and last portions of said each database of the at least two databases are searched individually and serially based on a remaining part of the complete search data; one or more memory banks, said each database being stored in at least one memory bank; a plurality of segment groups in each memory bank corresponding to groups of the database subcomponents, each segment group includes a plurality of segments; and an output section that outputs a compiled result of the parallel and serial searches, wherein the complete search data for the parallel and serial searches of all of the at least two databases is provided in a number of clock cycles equal to (s−1)+m, wherein s equals a number of the segment groups within each memory bank of the memory banks, and m equals a total number of databases in the at least two databases. ### Claim 15 An apparatus for performing database searches within a content addressable memory (CAM) structure comprising: a memory; a plurality of databases stored in the memory; means for selecting at least two databases of the plurality of the databases for a simultaneous search; means for performing a sequential search within the CAM structure on at least one database of the selected at least two databases, wherein first portions of each database of the at least two databases are searched in parallel based on a part of a complete search data, and last portions of said each database of the at least two databases are searched individually and serially based on a remainder of the complete search data, one or more memory banks, said each database being stored in at least one memory bank, a plurality of segment groups in each memory bank corresponding to groups of database subcomponents, each segment group includes a plurality of segments; and an output section that outputs a search result based on the parallel and serial searches, wherein the complete search data for the parallel and serial searches of all of the at least two databases is provided in a number of clock cycles equal to (s−1)+m, wherein s equals a number of the segment groups within each memory bank of the memory banks, and m equals a total number of databases in the at least two databases. ### Claim 16 A computer implemented method for performing database searches within a content addressable memory (CAM) structure, comprising: storing a plurality of databases in a memory; selecting at least two databases of the plurality of the databases for a simultaneous search; performing a sequential search within the CAM structure on at least one database of the selected at least two databases, wherein first portions of each database of the at least two databases are searched in parallel based on only a respective portion of a complete search data, and last portions of said each database of the at least two databases are searched individually and serially based on a remaining portion of the complete search data, said each database being stored in at least one memory bank, a plurality of segment groups in each memory bank corresponding to groups of database subcomponents, and each segment group including a plurality of segments; and outputting a search result based on an accumulation of the parallel and serial searches, wherein the complete search data for the simultaneous and serial searches of the at least two databases is provided in a number of clock cycles equal to (s−1)+m, wherein s equals a number of the segment groups within each memory bank of memory banks, and m equals a total number of databases in the at least two databases. ### Claim 17 (depends on 16) The method of claim 16, further comprising: selecting the databases for one of simultaneous search and sequential search using at least one of an input signal and first selector information. ### Claim 18 (depends on 17) The method of claim 17, wherein each database is divided into groups of database subcomponents, the method further comprising: selecting a group of database subcomponents from at least one of the databases selected for either simultaneous search or sequential search, wherein, portions of database subcomponents selected in all of the at least two databases are searched during the parallel searching based on the respective portion of the complete search data provided in a single clock cycle. ### Claim 19 (depends on 18) The method of claim 18, further comprising: selecting the group of database subcomponents using at least one of the input signal and second selector information. ### Claim 20 (depends on 19) The method of claim 19, further comprising: selecting portions of a search data that are relevant to a search in a database. ### Claim 21 (depends on 20) The method of claim 20, further comprising: selecting the portions of the search data using at least one of the input signal and third selector information. ### Claim 22 (depends on 21) The method of claim 21, further comprising: powering down at least one of databases that is not selected. ### Claim 23 (depends on 21) The method of claim 21, further comprising: powering down a group of database subcomponents that is not selected. ### Claim 24 An apparatus that performs database searches within content addressable memory (CAM) structures, comprising: a memory; a CAM structure of the CAM structures that is subdivided into multiple groups of portions to be searched in parallel or sequentially, the CAM structure comprising one or more memory banks; a plurality of databases being stored on the CAM structure, each database being stored in at least one memory bank; a first selector that selects at least two databases of the plurality of the databases for a simultaneous search, and performs a sequential search within the CAM structure on at least one database of the selected at least two databases, wherein first portions of each database of the at least two databases are searched in parallel based on only a respective portion of a complete search data, and last portions of said each database of the at least two databases are searched individually and serially based on a remaining portion of the complete search data; and an output section that outputs an accumulated search result based on the parallel and serial searches, wherein the complete search data for the parallel and serial searches is provided in a number of clock cycles equal to or less than (s−1)+m, wherein s equals a number of portions within each searched group of searched groups of the CAM structure, and m equals a total number of databases in the at least two databases.