Method and apparatus for latency and power efficient database searches

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.

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.

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.

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.