公开(公告)号：US07953721B1

公开(公告)日：2011-05-31

申请号：US11963041

申请日：2007-12-21

Applicant: Gary Depelteau ,  David Walter Carr

Inventor： Gary Depelteau ,  David Walter Carr

IPC: G06F17/30

CPC classification number: G06F17/30327

Abstract: Methods of operating a search engine device include repeatedly reading next keys (and associated handles) from a database within the search engine device in order to identify and transfer some or possibly all of the contents of the database to another device (e.g., command host) requesting the database contents. An operation to read a next key includes: (i) searching a pipelined database within the search engine device with a first key to identify at least one key therein that is greater than the first key and then (ii) executing a next key fetch operation in the pipelined database to identify the next key from the at least one key. The next key and a handle associated with the next key are then retrieved from the search engine device (e.g., transferred to a command host).

Abstract translation: 操作搜索引擎设备的方法包括从搜索引擎设备内的数据库重复读取下一个密钥（和相关联的句柄），以便将数据库的一些或可能全部的内容识别并传送到另一设备（例如，命令主机） 请求数据库内容。 读取下一个密钥的操作包括：（i）用第一密钥搜索搜索引擎设备内的流水线数据库，以识别大于第一密钥的至少一个密钥，然后（ii）执行下一个密钥获取操作 在流水线数据库中，从至少一个密钥识别下一个密钥。 然后从搜索引擎设备检索下一个密钥和与下一个密钥相关联的句柄（例如，传送到命令主机）。

公开(公告)号：US07831626B1

公开(公告)日：2010-11-09

申请号：US11858441

申请日：2007-09-20

Applicant: Gary Depelteau

Inventor： Gary Depelteau

IPC: G06F7/00 ,  G06F17/30

CPC classification number: G06F17/30327

Abstract: An integrated search engine includes a hierarchical memory configured to support a plurality of multi-way trees of search keys. These multi-way trees, which share a common root node, support respective databases of search keys. The child pointers associated with search keys within the common root node may be allocated at a single key level of granularity, which means that each search key within the common root node may be associated with a pair of child pointers when each search key within the common root node is associated with a different multi-way tree of search keys.

Abstract translation: 集成搜索引擎包括被配置为支持搜索关键字的多个多路树的分层存储器。 共享一个共同根节点的多路树支持相关的搜索关键数据库。 与公共根节点内的搜索关键字相关联的子指针可以以粒度的单个关键级别分配，这意味着当共同根节点内的每个搜索关键字在共同根目录内的每个搜索关键字时，共同根节点内的每个搜索关键字可以与一对子指针相关联 根节点与搜索关键字的不同多路树关联。

公开(公告)号：US08886677B1

公开(公告)日：2014-11-11

申请号：US11768646

申请日：2007-06-26

Applicant: Gary Depelteau ,  David W. Carr

Inventor： Gary Depelteau ,  David W. Carr

IPC: G06F17/30

CPC classification number: G06F17/30327

Abstract: A pipelined search engine supports a tree of search keys therein that utilizes span prefix masks to assist in longest prefix match (LPM) detection when the tree is searched. Each of a plurality of the span prefix masks encodes a prefix length of a search key to which the span prefix mask is associated and a value of another search key in the tree that is a prefix match to the search key to which the span prefix mask is associated.

Abstract translation: 流水线搜索引擎支持其中的搜索关键字树，其利用跨越前缀掩码以在搜索树时辅助最长前缀匹配（LPM）检测。 多个跨度前缀掩码中的每一个编码与跨度前缀掩码相关联的搜索关键字的前缀长度，并且作为前缀的树中的另一个搜索关键字的值与搜索关键字匹配，跨度前缀掩码 已关联的。

公开(公告)号：US07801877B1

公开(公告)日：2010-09-21

申请号：US12102282

申请日：2008-04-14

Applicant: Gary Depelteau ,  Pascal de Wit

Inventor： Gary Depelteau ,  Pascal de Wit

IPC: G06F7/00

CPC classification number: G06F17/30982

Abstract: Integrated circuit search engine devices include serially connected stages, a handle memory and a handle memory access manager. The stages store search keys in a multilevel tree of search keys. A first level stage is responsive to an input search key and a last level stage identifies a best match key for the input search key. The handle memory includes handle memory locations that store search result handles. The handle memory access manager searches the handle memory to retrieve a search result handle that corresponds to a best match key. The handle memory access manager refrains from modifying the handle memory in response to modify instructions during active periods of the handle memory when the handle memory is being searched. The handle memory access manager modifies the handle memory in response to the modify instructions during idle periods of the handle memory when the handle memory is not being searched. Related methods are also disclosed.

Abstract translation: 集成电路搜索引擎设备包括串行连接的级，句柄存储器和句柄存储器访问管理器。 阶段将搜索键存储在多级搜索键树中。 第一级响应于输入搜索关键字，最后一级标识输入搜索关键字的最佳匹配键。 句柄存储器包括存储搜索结果句柄的句柄存储器位置。 句柄存储器访问管理器搜索句柄存储器以检索对应于最佳匹配键的搜索结果句柄。 当正在搜索句柄存储器时，句柄存储器访问管理器避免修改句柄存储器以响应于句柄存储器的活动期间的修改指令。 当句柄存储器未被搜索时，句柄存储器访问管理器响应于句柄存储器的空闲周期期间的修改指令来修改句柄存储器。 还公开了相关方法。

公开(公告)号：US07725450B1

公开(公告)日：2010-05-25

申请号：US11685982

申请日：2007-03-14

Applicant: Gary Depelteau ,  David W. Carr

Inventor： Gary Depelteau ,  David W. Carr

IPC: G06F7/00 ,  G06F17/30

CPC classification number: G06F17/30958

Abstract: A search engine includes a pipelined arrangement of a plurality of search and tree maintenance sub-engines therein, which are configured to support the performance of search operations on exclusively valid multi-way trees of search prefixes concurrently with the performance of update operations on the multi-way trees as they are being searched.

Abstract translation: 搜索引擎包括其中的多个搜索和树维护子引擎的流水线布置，其被配置为与多个搜索和树维护子引擎上的更新操作的执行同时支持对专有有效的搜索前缀多路树的搜索操作的执行 - 正在搜索的树木。

公开(公告)号：US07603346B1

公开(公告)日：2009-10-13

申请号：US11674474

申请日：2007-02-13

Applicant: Gary Depelteau ,  David W. Carr

Inventor： Gary Depelteau ,  David W. Carr

IPC: G06F17/30

CPC classification number: G06F17/30961 ,  Y10S707/99932 ,  Y10S707/99933 ,  Y10S707/99937 ,  Y10S707/99942 ,  Y10S707/99943 ,  Y10S707/99952 ,  Y10S707/99953

Abstract: A pipelined search engine device, such as a longest prefix match (LPM) search engine device, includes a hierarchical memory and a pipelined tree maintenance engine therein. The hierarchical memory is configured to store a b−tree of search prefixes (and possibly span prefix masks) at multiple levels therein. The pipelined tree maintenance engine, which is embedded within the search engine device, includes a plurality of node maintenance sub-engines that are distributed with the multiple levels of the hierarchical memory. The search engine device may also include pipeline control and search logic that is distributed with the multiple levels of the hierarchical memory.

Abstract translation: 诸如最长前缀匹配（LPM）搜索引擎设备的流水线搜索引擎设备在其中包括分层存储器和流水线树维护引擎。 分层存储器被配置为在其中的多个级别存储搜索前缀的b树（并且可能跨越前缀掩码）。 嵌入在搜索引擎设备内的流水线树维护引擎包括与分级存储器的多个级别分布的多个节点维护子引擎。 搜索引擎设备还可以包括与分层存储器的多个级别分布的流水线控制和搜索逻辑。

公开(公告)号：US07987205B1

公开(公告)日：2011-07-26

申请号：US11963142

申请日：2007-12-21

Applicant: Gary Depelteau

Inventor： Gary Depelteau

IPC: G06F7/00 ,  G06F17/30

CPC classification number: G06F17/30327

Abstract: An integrated search engine device contains a pipelined arrangement of a plurality of search and tree maintenance sub-engines therein. This pipelined arrangement of sub-engines includes a hierarchical memory, which is configured to store a plurality of databases of search prefixes. These databases are arranged as a corresponding plurality of multi-way trees that span multiple levels of the hierarchical memory. The plurality of search and tree maintenance sub-engines are configured to respond to a database flush command by redesignating active nodes of a selected database within the hierarchical memory as free nodes using downstream and upstream communications between the plurality of search and tree maintenance sub-engines.

Abstract translation: 集成的搜索引擎设备包含其中的多个搜索和树维护子引擎的流水线布置。 子引擎的流水线布置包括分层存储器，其被配置为存储多个搜索前缀数据库。 这些数据库被布置为跨越分级存储器的多个级别的对应的多个多路树。 多个搜索和树维护子引擎被配置为通过在分层存储器内重新指定所选择的数据库的活动节点来响应数据库刷新命令，作为使用多个搜索和树维护子引擎之间的下游和上游通信的空闲节点 。

公开(公告)号：US07844867B1

公开(公告)日：2010-11-30

申请号：US11959705

申请日：2007-12-19

Applicant: Sudhakar Reddy ,  Gary Depelteau

Inventor： Sudhakar Reddy ,  Gary Depelteau

IPC: G11C29/26 ,  G11C29/50

CPC classification number: G11C29/16 ,  G11C29/26

Abstract: A hierarchical memory includes a plurality of memory blocks, a common access bus coupled to the plurality of memory blocks, and a host bus interface coupled to the common access bus and configured to provide communication between an external host and the plurality of memory blocks over the common access bus. The memory further includes a Built-In Self Test (BIST) module coupled to the common access bus and configured to communicate with the plurality of memory blocks over the common access bus, and a test access interface coupled to the BIST main module and configured to receive test instructions and test data, to provide the test data to the BIST main module, and to configure the BIST main module in response to the test instructions. BIST operations are carried out in the memory blocks in response to BIST control signals and test data transmitted by the BIST module over the common access bus.

Abstract translation: 分层存储器包括多个存储器块，耦合到所述多个存储器块的公共存取总线，以及耦合到所述公共存取总线的主机总线接口，并且被配置为通过所述存储块提供外部主机与所述多个存储块之间的通信 公共接入总线。 所述存储器还包括耦合到所述公共访问总线并被配置为通过所述公共访问总线与所述多个存储器块通信的内置自测（BIST）模块以及耦合到所述BIST主模块并被配置为 接收测试指令和测试数据，将测试数据提供给BIST主模块，并根据测试指令配置BIST主模块。 响应BIST控制信号和BIST模块通过公共接入总线发送的测试数据，在存储器块中执行BIST操作。

公开(公告)号：US07805427B1

公开(公告)日：2010-09-28

申请号：US11864290

申请日：2007-09-28

Applicant: Gary Depelteau

Inventor： Gary Depelteau

IPC: G06F17/30

CPC classification number: G06F17/30327

Abstract: An integrated circuit search engine device supports a multi-way tree of search keys therein. The search engine device includes at least one multi-node sub-engine. The multi-node sub-engine includes a node processor and a plurality of columns of sub-nodes containing search keys. The node processor is configured to distribute an applied search key in parallel to each of the plurality of columns of sub-nodes in response to a search request. The node processor is also configured to receive and resolve corresponding sub-node search results from the plurality of columns of sub-nodes.

Abstract translation: 集成电路搜索引擎装置支持其中的搜索键的多路树。 搜索引擎设备包括至少一个多节点子引擎。 多节点子引擎包括节点处理器和包含搜索关键字的多列子节点。 节点处理器被配置为响应于搜索请求而将应用的搜索密钥并行地分布到多个子节点列中的每一个。 节点处理器还被配置为从多个子节点列接收和解析相应的子节点搜索结果。

公开(公告)号：US07716204B1

公开(公告)日：2010-05-11

申请号：US11962716

申请日：2007-12-21

Applicant: Gary Depelteau ,  Pascal de Wit

Inventor： Gary Depelteau ,  Pascal de Wit

IPC: G06F7/00 ,  G06F13/00 ,  G06F13/28 ,  G06F15/16 ,  G06F17/30 ,  H04L12/28 ,  H04L12/56

CPC classification number: H04L45/7457 ,  G06F17/30955

Abstract: A handle allocation manager is provided for an integrated circuit search engine device that includes multiple stages of a multilevel tree of search keys and a handle memory. The handle allocation manager includes a handle availability memory that stores handle availability indicators to provide an indication of whether a handle is available for association with a key. A handle availability summary memory stores indicators for groups of handles and a block availability summary memory stores indicators for multiple groups of handle availability summary memories. The handle allocation manager can use these memories to search for a next available handle. Related methods are also provided.

Abstract translation: 提供了一种用于集成电路搜索引擎设备的句柄分配管理器，其包括多级搜索键的多级树和句柄存储器。 句柄分配管理器包括句柄可用性存储器，其存储句柄可用性指示符以提供句柄是否可用于与键相关联的指示。 句柄可用性摘要存储器存储用于组句柄的指示符，并且块可用性总结存储器存储用于多组句柄可用性总结存储器的指示符。 句柄分配管理器可以使用这些存储器来搜索下一个可用句柄。 还提供了相关方法。