公开(公告)号：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）执行下一个密钥获取操作 在流水线数据库中，从至少一个密钥识别下一个密钥。 然后从搜索引擎设备检索下一个密钥和与下一个密钥相关联的句柄（例如，传送到命令主机）。

公开(公告)号：US20140181126A1

公开(公告)日：2014-06-26

申请号：US13230732

申请日：2011-09-12

Applicant: Paul Nadj ,  David Walter Carr ,  Edward D. Funnekotter

Inventor： Paul Nadj ,  David Walter Carr ,  Edward D. Funnekotter

IPC: G06F17/30 ,  G06F7/24

CPC classification number: G06F17/30336 ,  G06F7/22 ,  G06F7/24 ,  G06F17/30327 ,  G06F2207/222 ,  Y10S707/99942

Abstract: A method for high-speed scheduling and arbitration of events for computing and networking is disclosed. The method includes the software and hardware implementation of a unique data structure, known as a pile, for scheduling and arbitration of events. According to the method, events are stored in loosely sorted order in piles, with the next event to be processed residing in the root node of the pile. The pipelining of the insertion and removal of events from the piles allows for simultaneous event removal and next event calculation. The method's inherent parallelisms thus allow for the automatic rescheduling of removed events for re-execution at a future time, also known as event swapping. The method executes in O(1) time.

Abstract translation: 公开了用于计算和联网的事件的高速调度和仲裁的方法。 该方法包括用于调度和仲裁事件的独特数据结构（称为堆栈）的软件和硬件实现。 根据该方法，事件以松散排列的顺序存储在桩中，下一个要处理的事件驻留在桩的根节点中。 从桩中插入和移除事件的流水线允许同时进行事件移除和下一个事件计算。 因此，该方法的固有并行性允许自动重新安排已移除的事件，以便将来再次执行，也称为事件交换。 该方法在O（1）时间内执行。

公开(公告)号：US07825777B1

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

申请号：US11393489

申请日：2006-03-30

Applicant: Tingjun Wen ,  David Walter Carr ,  Tadeusz Kwasniewski

Inventor： Tingjun Wen ,  David Walter Carr ,  Tadeusz Kwasniewski

IPC: G05B1/00 ,  H03K19/20 ,  H03K19/094 ,  G06F7/00

CPC classification number: G06F7/026

Abstract: An integrated circuit comparator is provided that determines non-strict inequalities between operands applied thereto. Each comparator includes at least one n-bit comparator cell. This comparator cell is configured to determine a non-strict inequality between a first n-bit operand (e.g., A[n−1, . . . , 0]) and a second n-bit operand (e.g., B[n−1, . . . , 0]). The comparator cell determines the non-strict inequality by computing a control output signal Co (or its complement), where: C o = ( … ⁡ ( ( C i ⁡ ( A 0 + B 0 _ ) + A 0 ⁢ B 0 _ ) ⁢ ( A 1 + B 1 _ ) + A 1 ⁢ B 1 _ ) ⁢ … ⁡ ( A n - 2 + B n - 2 _ ) + A n - 2 ⁢ B n - 2 _ ) ⁢ ( A n - 1 + B n - 1 _ ) + A n - 1 ⁢ B n - 1 _ , “n” is a positive integer greater than one and Ci is a control input signal that specifies an interpretation to be given to the control output signal Co.

Abstract translation: 提供集成电路比较器，其确定施加到其上的操作数之间的非严格不等式。 每个比较器包括至少一个n位比较器单元。 该比较器单元被配置为确定第一n位操作数（例如，A [n-1，...，0]）和第二n位操作数之间的非严格不等式（例如，B [n-1 ，...，0]）。 比较器单元通过计算控制输出信号Co（或其补码）来确定非严格不等式，其中：C o =（...⁡（（C 0⁡（A 0 + B 0 _）+ A 0 B 0 _ ）（A 1 + B 1 _）+ A 1 B 1 _）...⁡（A n-2 + B n-2 _）+ A n-2 B n-2 _）（A n- 1 + B n - 1 _）+ A n - 1 B n - 1 _，“n”是大于1的正整数，Ci是指定给予控制输出信号Co的解释的控制输入信号 。

公开(公告)号：US09418093B2

公开(公告)日：2016-08-16

申请号：US13230732

申请日：2011-09-12

Applicant: Paul Nadj ,  David Walter Carr ,  Edward D. Funnekotter

Inventor： Paul Nadj ,  David Walter Carr ,  Edward D. Funnekotter

IPC: G06F17/00 ,  G06F17/30 ,  G06F7/22 ,  G06F7/24

CPC classification number: G06F17/30336 ,  G06F7/22 ,  G06F7/24 ,  G06F17/30327 ,  G06F2207/222 ,  Y10S707/99942

Abstract: A method for high-speed scheduling and arbitration of events for computing and networking is disclosed. The method includes the software and hardware implementation of a unique data structure, known as a pile, for scheduling and arbitration of events. According to the method, events are stored in loosely sorted order in piles, with the next event to be processed residing in the root node of the pile. The pipelining of the insertion and removal of events from the piles allows for simultaneous event removal and next event calculation. The method's inherent parallelisms thus allow for the automatic rescheduling of removed events for re-execution at a future time, also known as event swapping. The method executes in O(1) time.

Abstract translation: 公开了用于计算和联网的事件的高速调度和仲裁的方法。 该方法包括用于调度和仲裁事件的独特数据结构（称为堆栈）的软件和硬件实现。 根据该方法，事件以松散排列的顺序存储在桩中，下一个要处理的事件驻留在桩的根节点中。 从桩中插入和移除事件的流水线允许同时进行事件移除和下一个事件计算。 因此，该方法的固有并行性允许自动重新安排已移除的事件，以便将来再次执行，也称为事件交换。 该方法在O（1）时间内执行。

公开(公告)号：US08086641B1

公开(公告)日：2011-12-27

申请号：US12336565

申请日：2008-12-17

Applicant: David Walter Carr

Inventor： David Walter Carr

IPC: G06F7/00 ,  G06F17/30

CPC classification number: G06F17/30327

Abstract: An integrated search engine device evaluates span prefix masks for keys residing at leaf parent levels of a search tree to identify a longest prefix match to an applied search key. This longest prefix match resides at a leaf node of the search tree that is outside a search path of the search tree for the applied search key. The search engine device is also configured to read a bitmap associated with the leaf node to identify a pointer to associated data for the longest prefix match. The pointer has a value that is based on a position of a set bit within the bitmap that corresponds to a set bit within the span prefix mask that signifies the longest prefix match.

Abstract translation: 集成搜索引擎设备评估驻留在搜索树的叶父级别的密钥的跨度前缀掩码，以标识与应用的搜索关键字的最长前缀匹配。 该最长的前缀匹配位于搜索树的叶节点处，该搜索树位于搜索树的搜索路径之外，用于所应用的搜索关键字。 搜索引擎设备还被配置为读取与叶节点相关联的位图，以识别用于最长前缀匹配的关联数据的指针。 该指针具有基于位图内的设置位的位置的值，其对应于跨度前缀掩码内的表示最长前缀匹配的集合位。

公开(公告)号：US6163542A

公开(公告)日：2000-12-19

申请号：US924657

申请日：1997-09-05

Applicant: David Walter Carr ,  Denny L. S. Lee

Inventor： David Walter Carr ,  Denny L. S. Lee

IPC: H04L12/56 ,  H04Q11/04 ,  H04L12/28

CPC classification number: H04L12/5602 ,  H04L2012/5624 ,  H04L2012/5631 ,  H04L2012/5651 ,  H04L2012/5679 ,  H04L2012/568 ,  H04Q11/0478

Abstract: An apparatus and a method for shaping ATM cell traffic emitted onto a virtual path connection in an ATM network are described. Component virtual channel connections are arbitrated at an aggregation point utilizing a hierarchical, multi-level arbitration technique. The technique provides both virtual path shaping and controllability of underlying virtual channel connections with an improved fairness performance amongst all the aggregating virtual channel connections.

Abstract translation: 描述了在ATM网络中发送到虚拟路径连接上的ATM信元业务整形的装置和方法。 使用分级多级仲裁技术，在聚合点对组件虚拟信道连接进行仲裁。 该技术提供了虚拟通道整形和底层虚拟通道连接的可控性，并提高了所有聚合虚拟通道连接之间的公平性。

公开(公告)号：US08032561B1

公开(公告)日：2011-10-04

申请号：US09931841

申请日：2001-08-16

Applicant: Paul Nadj ,  David Walter Carr ,  Edward D. Funnekotter

Inventor： Paul Nadj ,  David Walter Carr ,  Edward D. Funnekotter

IPC: G06F17/30

CPC classification number: G06F17/30336 ,  G06F7/22 ,  G06F7/24 ,  G06F17/30327 ,  G06F2207/222 ,  Y10S707/99942

Abstract: A method for high-speed scheduling and arbitration of events for computing and networking is disclosed. The method includes the software and hardware implementation of a unique data structure, known as a pile, for scheduling and arbitration of events. According to the method, events are stored in loosely sorted order in piles, with the next event to be processed residing in the root node of the pile. The pipelining of the insertion and removal of events from the piles allows for simultaneous event removal and next event calculation. The method's inherent parallelisms thus allow for the automatic rescheduling of removed events for re-execution at a future time, also known as event swapping. The method executes in O(1) time.

Abstract translation: 公开了用于计算和联网的事件的高速调度和仲裁的方法。 该方法包括用于调度和仲裁事件的独特数据结构（称为堆栈）的软件和硬件实现。 根据该方法，事件以松散排列的顺序存储在桩中，下一个要处理的事件驻留在桩的根节点中。 从桩中插入和移除事件的流水线允许同时进行事件移除和下一个事件计算。 因此，该方法的固有并行性允许自动重新安排已移除的事件，以便将来的时间重新执行，也称为事件交换。 该方法在O（1）时间内执行。

公开(公告)号：US07792812B1

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

申请号：US11395097

申请日：2006-03-31

Applicant: David Walter Carr

Inventor： David Walter Carr

IPC: G06F7/00 ,  G06F17/30

CPC classification number: G06F17/30327

Abstract: A search engine device that supports a Patricia trie arrangement of search keys includes an array of comparator cells that supports parallel decoding of the Patricia trie. This array of comparator cells processes a plurality of distinguishing bit identifiers for nodes in the Patricia trie in parallel with a corresponding plurality of bits of an applied search key during a search operation. In response to this processing, the array generates a match signal that identifies a location of a matching search key candidate within the Patricia trie.

Abstract translation: 支持搜索关键词的Patricia trie排列的搜索引擎设备包括支持Patricia特里的并行解码的比较单元阵列。 该比较单元阵列在搜索操作期间与Patricia trie中的节点并行地处理应用搜索关键字的相应多个位的多个区分位标识符。 响应于该处理，阵列产生一个匹配信号，该匹配信号标识Patricia特里内匹配的搜索关键候选者的位置。

公开(公告)号：US07747599B1

公开(公告)日：2010-06-29

申请号：US11184243

申请日：2005-07-19

Applicant: Gary Michael Depelteau ,  David Walter Carr

Inventor： Gary Michael Depelteau ,  David Walter Carr

IPC: G06F7/00 ,  G06F17/30 ,  G06F13/00

CPC classification number: G06F17/30327

Abstract: A search engine device includes a hierarchical memory that is configured to store a b-tree of search prefixes and span prefix masks (SPMs). These SPMs are evaluated during each search operation to identify search prefixes that match an applied search key yet reside at nodes of the b-tree that are not traversed during the search operation. The search engine device also includes handle memory. This handle memory is configured to support a respective handle memory block for each search prefix within each of a plurality of nodes of the b-tree that reside at a leaf parent level within the b-tree. Each of these handle memory blocks may have sufficient capacity to support one result handle per bit within a span prefix mask associated with a corresponding search prefix. In other cases, each of these handle memory blocks may have sufficient capacity to support only M+1 handles, where M is a positive integer corresponding to a quantity of search prefixes supported by each of a plurality of leaf nodes within the b-tree.

Abstract translation: 搜索引擎设备包括被配置为存储搜索前缀和跨度前缀掩码（SPM）的b树的分层存储器。 在每个搜索操作期间评估这些SPM以识别与在搜索操作期间未被遍历的b-tree的节点匹配的应用搜索关键字的搜索前缀。 搜索引擎设备还包括句柄存储器。 该处理存储器被配置为支持驻留在b-tree内的叶父级别的b-tree的多个节点的每个中的每个搜索前缀的相应句柄存储块。 这些处理存储器块中的每一个可以具有足够的容量以在与相应的搜索前缀相关联的范围前缀掩码内每位支持一个结果句柄。 在其他情况下，这些处理存储器块中的每一个可以具有足够的容量来仅支持M + 1句柄，其中M是对应于b树内的多个叶节点中的每一个支持的搜索前缀的数量的正整数。

公开(公告)号：US07739460B1

公开(公告)日：2010-06-15

申请号：US11861399

申请日：2007-09-26

Applicant: David Walter Carr

Inventor： David Walter Carr

IPC: G06F12/00

CPC classification number: G06F12/0804 ,  G06F2212/1016

Abstract: An integrated circuit memory system includes a write-back buffer and a control circuit that support read-write-modify (RWM) operations within a high capacity memory device. A RWM operation may include reading from the integrated circuit memory device and the write-back buffer to identify whether the memory device or the write-back buffer has the data requested by a read instruction issued to the memory system. The data read from the write-back buffer is then written into the memory device and a modified version of the requested data is written to the write-back buffer in anticipation of subsequent transfer to the memory device.

Abstract translation: 一种集成电路存储器系统包括一个回写缓冲器和一个支持高容量存储器件内的读写修改（RWM）操作的控制电路。 RWM操作可以包括从集成电路存储器件和回写缓冲器读取以识别存储器件或回写缓冲器是否具有由发出到存储器系统的读指令请求的数据。 然后从写回缓冲器读取的数据被写入存储器件，并且所需数据的修改版本被写入到写回缓冲器中，以期随后传送到存储器件。