公开(公告)号：US07424474B2

公开(公告)日：2008-09-09

申请号：US11206422

申请日：2005-08-17

申请人： Paul Nadj ,  David W. Carr ,  Edward D. Funnekotter

发明人： Paul Nadj ,  David W. Carr ,  Edward D. Funnekotter

IPC分类号： G06F17/30

CPC分类号： G06F7/22 ,  Y10S707/99938 ,  Y10S707/99945

摘要： An improved data structure is provided by modifying a public-domain data structure known as a “heap”. When these improvements are applied, the resultant data structure is known as a “pile.” This invention further described a pipelined hardware implementation of a pile. Piles offer many advantages over heaps: they allow for fast, pipelined hardware implementations with increased throughput, making piles practical for a wide variety of new applications; they remove the requirement to track and update the last position in the heap; they reduce the number of memory reads accesses required during a delete operation; they require only ordinary, inexpensive RAM for storage in a fast, pipelined implementation; and they allow a random mixture of back-to-back insert, remove, and swap operations to be performed without stalling the pipeline.

摘要翻译： 通过修改被称为“堆”的公共域数据结构来提供改进的数据结构。 当应用这些改进时，所得到的数据结构被称为“堆”。 本发明进一步描述了桩的流水线硬件实现。 桩比堆叠提供许多优点：它们允许快速，流水线的硬件实现，增加吞吐量，使堆桩适用于各种新应用程序; 它们删除跟踪和更新堆中最后一个位置的要求; 它们减少了在删除操作期间所需的存储器读取访问次数; 它们只需要普通的便宜的RAM，用于以快速，流水线的方式存储; 并且它们允许随机混合背靠背插入，移除和交换操作，而不会使管道停顿。

公开(公告)号：US06952696B1

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

申请号：US09728147

申请日：2000-11-28

申请人： Paul Nadj ,  David W. Carr ,  Edward D. Funnekotter

发明人： Paul Nadj ,  David W. Carr ,  Edward D. Funnekotter

IPC分类号： G06F7/22 ,  G06F17/30

CPC分类号： G06F7/22 ,  Y10S707/99938 ,  Y10S707/99945

摘要： An improved data structure is provided by modifying a public-domain data structure known as a “heap”. When these improvements are applied, the resultant data structure is known as a “pile.” This invention further described a pipelined hardware implementation of a pile. Piles offer many advantages over heaps: they allow for fast, pipelined hardware implementations with increased throughput, making piles practical for a wide variety of new applications; they remove the requirement to track and update the last position in the heap; they reduce the number of memory reads accesses required during a delete operation; they require only ordinary, inexpensive RAM for storage in a fast, pipelined implementation; and they allow a random mixture of back-to-back insert, remove, and swap operations to be performed without stalling the pipeline.

摘要翻译： 通过修改被称为“堆”的公共域数据结构来提供改进的数据结构。 当应用这些改进时，所得到的数据结构被称为“堆”。 本发明进一步描述了桩的流水线硬件实现。 桩比堆叠提供许多优点：它们允许快速，流水线的硬件实现，增加吞吐量，使堆桩适用于各种新应用程序; 它们删除跟踪和更新堆中最后一个位置的要求; 它们减少了在删除操作期间所需的存储器读取访问次数; 它们只需要普通的便宜的RAM，用于以快速，流水线的方式存储; 并且它们允许随机混合背靠背插入，移除和交换操作，而不会使管道停顿。

公开(公告)号：US07657525B2

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

申请号：US11254156

申请日：2005-10-18

申请人： Paul Nadj ,  David W. Carr ,  Edward D. Funnekotter

发明人： Paul Nadj ,  David W. Carr ,  Edward D. Funnekotter

IPC分类号： G06F17/30

CPC分类号： G06F7/22 ,  G06F2207/222 ,  Y10S707/99937 ,  Y10S707/99945 ,  Y10S707/99952

摘要： An improved data structure is provided by modifying a public-domain data structure known as a “heap”. When these improvements are applied, the resultant data structure is known as a “pile.” This invention further describes a pipelined hardware implementation of a pile. Piles offer many advantages over heaps: they allow for fast, pipelined hardware implementations with increased throughput, making piles practical for a wide variety of new applications; they remove the requirement to track and update the last position in the heap; they reduce the number of memory reads accesses required during a delete operation; they require only ordinary, inexpensive RAM for storage in a fast, pipelined implementation; and they allow a random mixture of back-to-back insert, remove, and swap operations to be performed without stalling the pipeline.

摘要翻译： 通过修改被称为“堆”的公共域数据结构来提供改进的数据结构。 当应用这些改进时，所得到的数据结构被称为“堆”。 本发明进一步描述了桩的流水线硬件实现。 桩比堆叠提供许多优点：它们允许快速，流水线的硬件实现，增加吞吐量，使堆桩适用于各种新应用程序; 它们删除跟踪和更新堆中最后一个位置的要求; 它们减少了在删除操作期间所需的存储器读取访问次数; 它们只需要普通的便宜的RAM，用于以快速，流水线的方式存储; 并且它们允许随机混合背靠背插入，移除和交换操作，而不会使管道停顿。

公开(公告)号：US07007021B1

公开(公告)日：2006-02-28

申请号：US09727534

申请日：2000-11-28

申请人： Paul Nadj ,  David W. Carr ,  Edward D. Funnekotter

发明人： Paul Nadj ,  David W. Carr ,  Edward D. Funnekotter

IPC分类号： G06F17/30

CPC分类号： G06F7/22 ,  G06F2207/222 ,  Y10S707/99937 ,  Y10S707/99945 ,  Y10S707/99952

摘要： An improved data structure is provided by modifying a public-domain data structure known as a “heap”. When these improvements are applied, the resultant data structure is known as a “pile.” This invention further describes a pipelined hardware implementation of a pile. Piles offer many advantages over heaps: they allow for fast, pipelined hardware implementations with increased throughput, making piles practical for a wide variety of new applications; they remove the requirement to track and update the last position in the heap; they reduce the number of memory reads accesses required during a delete operation; they require only ordinary, inexpensive RAM for storage in a fast, pipelined implementation; and they allow a random mixture of back-to-back insert, remove, and swap operations to be performed without stalling the pipeline.

摘要翻译： 通过修改被称为“堆”的公共域数据结构来提供改进的数据结构。 当应用这些改进时，所得到的数据结构被称为“堆”。 本发明进一步描述了桩的流水线硬件实现。 桩比堆叠提供许多优点：它们允许快速，流水线的硬件实现，增加吞吐量，使堆桩适用于各种新应用程序; 它们删除跟踪和更新堆中最后一个位置的要求; 它们减少了在删除操作期间所需的存储器读取访问次数; 它们只需要普通的便宜的RAM，用于以快速，流水线的方式存储; 并且它们允许随机混合背靠背插入，移除和交换操作，而不会使管道停顿。

公开(公告)号：US06449214B1

公开(公告)日：2002-09-10

申请号：US09727533

申请日：2000-11-28

申请人： David W. Carr ,  Edward D. Funnekotter

发明人： David W. Carr ,  Edward D. Funnekotter

IPC分类号： G11C800

CPC分类号： G11C15/00

摘要： A method and means to reduce memory requirements for storing statistics by recording, in a separate overflow memory, the most significant bits of counters requiring more bits than provided in the main statistics memory. A binary CAM provides the linking mechanism between the main and overflow memories.

摘要翻译： 通过在单独的溢出存储器中记录需要比主统计存储器中提供的更多位的计数器的最高有效位来减少存储统计信息的存储器要求的方法和装置。 二进制CAM提供主存储器和溢出存储器之间的链接机制。

公开(公告)号：US06600744B1

公开(公告)日：2003-07-29

申请号：US09274720

申请日：1999-03-23

申请人： David W. Carr ,  Paul Nadj

发明人： David W. Carr ,  Paul Nadj

IPC分类号： H04L1228

CPC分类号： H04L47/10 ,  H04L45/742 ,  H04L47/2441 ,  H04L49/205 ,  H04L49/25 ,  H04L49/351

摘要： A method and apparatus for packet classification stores rules or parameters for classifying the packets in a memory structure. The memory structure receives a set of rule selection signals, where the memory provides a selected set of rules in response to the rule selection signals. A comparison block operably coupled to the memory receives a key, which is also preferably derived from the header information for the packet. The key includes the relevant information for classifying the packet according to the rules stored in the memory. The comparison block compares the key with each of the rules in the selected set of rules, and when a favorable comparison is determined, the comparison block provides an indication of the favorable comparison. A prioritization block operably coupled to the comparison block prioritizes the rules that resulted in a favorable comparison to determine a preferred rule, where the preferred rule includes the resulting classification information for the packet.

摘要翻译： 用于分组分类的方法和装置存储用于对存储器结构中的分组进行分类的规则或参数。 存储器结构接收一组规则选择信号，其中存储器响应于规则选择信号提供所选择的一组规则。 可操作地耦合到存储器的比较块接收密钥，其也优选地从用于分组的报头信息导出。 密钥包括根据存储在存储器中的规则对分组进行分类的相关信息。 比较块将密钥与所选规则集中的每个规则进行比较，并且当确定有利的比较时，比较块提供有利的比较的指示。 可操作地耦合到比较块的优先级块将导致有利的比较的规则优先于确定优选规则，其中优选规则包括所得到的分组的分类信息。

公开(公告)号：US07725450B1

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

申请号：US11685982

申请日：2007-03-14

申请人： Gary Depelteau ,  David W. Carr

发明人： Gary Depelteau ,  David W. Carr

IPC分类号： G06F7/00 ,  G06F17/30

CPC分类号： G06F17/30958

摘要： 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.

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

公开(公告)号：US07603346B1

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

申请号：US11674474

申请日：2007-02-13

申请人： Gary Depelteau ,  David W. Carr

发明人： Gary Depelteau ,  David W. Carr

IPC分类号： G06F17/30

CPC分类号： G06F17/30961 ,  Y10S707/99932 ,  Y10S707/99933 ,  Y10S707/99937 ,  Y10S707/99942 ,  Y10S707/99943 ,  Y10S707/99952 ,  Y10S707/99953

摘要： 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.

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

公开(公告)号：USD393333S

公开(公告)日：1998-04-07

申请号：US62632

申请日：1996-11-20

申请人： Lawrence R. Kibler ,  David W. Carr ,  Kenneth Todd Shelley

设计人： Lawrence R. Kibler ,  David W. Carr ,  Kenneth Todd Shelley

公开(公告)号：US09347166B2

公开(公告)日：2016-05-24

申请号：US13494340

申请日：2012-06-12

申请人： David W. Carr ,  Dale E. Mueller ,  Basak Oguz ,  Jon D. Strait

发明人： David W. Carr ,  Dale E. Mueller ,  Basak Oguz ,  Jon D. Strait

IPC分类号： D06F37/14 ,  D06F17/10 ,  D06F37/06

CPC分类号： D06F37/14 ,  D06F17/10 ,  D06F37/06

摘要： A washing machine for treating laundry comprising a basket rotatable about a first rotational axis, having a peripheral side wall extending upwardly from a bottom wall to at least partially define a treating chamber; a clothes mover proximate the bottom wall, having a base with a centrally located hub concentric with a second rotational axis about which the clothes mover reciprocally rotates; and at least one vane having an elongated body extending away from the hub and projecting upwardly from the clothes mover to terminate in a tip.

摘要翻译： 一种用于处理衣物的洗衣机，包括可围绕第一旋转轴线旋转的篮，其具有从底壁向上延伸的至少部分地限定处理室的周边侧壁; 靠近底壁的衣物移动器，具有基座，其具有与第二旋转轴线同心的中心定位的轮毂，衣物推动器绕该第二旋转轴线往复旋转; 以及至少一个叶片，其具有远离轮毂延伸的细长体，并从衣物推动器向上突出以终止于尖端。