Invention Grant
- Patent Title: Data structure and method for sorting using heap-supernodes
- Patent Title (中): 使用堆超节点进行排序的数据结构和方法
-
Application No.: US11206422Application Date: 2005-08-17
-
Publication No.: US07424474B2Publication Date: 2008-09-09
- Inventor: Paul Nadj , David W. Carr , Edward D. Funnekotter
- Applicant: Paul Nadj , David W. Carr , Edward D. Funnekotter
- Applicant Address: US CA San Jose
- Assignee: Altera Corporation
- Current Assignee: Altera Corporation
- Current Assignee Address: US CA San Jose
- Agency: Martine Penilla & Gencarella, LLP
- Main IPC: G06F17/30
- IPC: G06F17/30

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.
Public/Granted literature
- US20060004897A1 Data structure and method for sorting using heap-supernodes Public/Granted day:2006-01-05
Information query