公开(公告)号：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）时间内执行。

公开(公告)号：US07925971B2

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

申请号：US11552849

申请日：2006-10-25

Applicant: Edward D. Funnekotter ,  Jason Whelan ,  Jonathan Bosloy ,  Patrick Brodeur ,  Stephen Cadieux ,  Philippe-Andre Babkine ,  David W. Horton ,  Paul Kondrat

Inventor： Edward D. Funnekotter ,  Jason Whelan ,  Jonathan Bosloy ,  Patrick Brodeur ,  Stephen Cadieux ,  Philippe-Andre Babkine ,  David W. Horton ,  Paul Kondrat

IPC: G06F9/44

CPC classification number: G06F17/227 ,  G06F17/2247 ,  G06F17/2258 ,  G06F17/2264 ,  G06F17/272 ,  H04L67/02 ,  H04L67/327 ,  H04L69/22

Abstract: A method and apparatus for converting documents from one format to another in a speed efficient way involves a hardware module which implements several operating pipeline stages which work in parallel. The transformations are supplied and decomposed into sequences of control units. The transformation of documents consists of applying control unit sequences to input documents. The control units are themselves executed by a set of dedicated hardware resources. Furthermore the pipeline is capable of operating on more than one document at a time. Fast document transformation is a key capability of document processing systems. The use of parallel processing techniques and hardware that implements highly specialized transformation resources make this invention particularly scalable for its use in large, high speed content networks.

Abstract translation: 用于以高速方式将文档从一种格式转换到另一种格式的方法和装置涉及一种实现并行工作的多个操作流水线级的硬件模块。 转换被提供并分解成控制单元的序列。 文件的转换包括将控制单元序列应用于输入文档。 控制单元本身由一组专用硬件资源执行。 此外，管道一次可以在多个文档上操作。 快速文档转换是文档处理系统的关键功能。 使用并行处理技术和实现高度专业化的转换资源的硬件使本发明特别可扩展，可用于大型高速内容网络。

公开(公告)号：US06449214B1

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

申请号：US09727533

申请日：2000-11-28

Applicant: David W. Carr ,  Edward D. Funnekotter

Inventor： David W. Carr ,  Edward D. Funnekotter

IPC: G11C800

CPC classification number: G11C15/00

Abstract: 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.

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

公开(公告)号：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）时间内执行。

公开(公告)号：US07424474B2

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

申请号：US11206422

申请日：2005-08-17

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

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

IPC: G06F17/30

CPC classification number: G06F7/22 ,  Y10S707/99938 ,  Y10S707/99945

Abstract: 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.

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

公开(公告)号：US06952696B1

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

申请号：US09728147

申请日：2000-11-28

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

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

IPC: G06F7/22 ,  G06F17/30

CPC classification number: G06F7/22 ,  Y10S707/99938 ,  Y10S707/99945

Abstract: 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.

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

公开(公告)号：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）时间内执行。

公开(公告)号：US07657525B2

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

申请号：US11254156

申请日：2005-10-18

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

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

IPC: G06F17/30

CPC classification number: G06F7/22 ,  G06F2207/222 ,  Y10S707/99937 ,  Y10S707/99945 ,  Y10S707/99952

Abstract: 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.

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

公开(公告)号：US07007021B1

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

申请号：US09727534

申请日：2000-11-28

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

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

IPC: G06F17/30

CPC classification number: G06F7/22 ,  G06F2207/222 ,  Y10S707/99937 ,  Y10S707/99945 ,  Y10S707/99952

Abstract: 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.

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