发明授权
- 专利标题: Data structure and method for pipeline heap-sorting
- 专利标题(中): 管道堆排序的数据结构和方法
-
申请号: US11254156申请日: 2005-10-18
-
公开(公告)号: US07657525B2公开(公告)日: 2010-02-02
- 发明人: Paul Nadj , David W. Carr , Edward D. Funnekotter
- 申请人: Paul Nadj , David W. Carr , Edward D. Funnekotter
- 申请人地址: US CA San Jose
- 专利权人: Altera Corporation
- 当前专利权人: Altera Corporation
- 当前专利权人地址: US CA San Jose
- 代理机构: Martine Penilla & Gencarella, LLP
- 主分类号: G06F17/30
- IPC分类号: G06F17/30
摘要:
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.
公开/授权文献
- US20060095444A1 Data structure and method for pipeline heap-sorting 公开/授权日:2006-05-04
信息查询