Method and system for providing a hardware sort for a large number of items
US7363304B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jun 29, 2004 |
| Grant date | Apr 22, 2008 |
| Priority date | — |
| Expiry date | Aug 4, 2025 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99937
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method and system for sorting a number of items in a computer system. The sort is based on a plurality of values of a key. Each item has a value of the plurality of values. The method and system include providing plurality of stages, providing at least one switch coupled between the plurality of stages, and providing a final switch coupled with a last stage. Each of the plurality of stages has a pair of first-in-first-out buffers (FIFOs) that store twice as many of the items as the pair of FIFOs in a previous stage. Each switch is for merging and sorting a first portion of the number of items from the pair of FIFOs in the previous stage based on the key and for providing the first portion of the number plurality of items to a first FIFO of the pair of FIFOs of the stage in order. Each switch is also for merging and sorting a second portion of the number of items the pair of FIFOs in the previous stage based on the key and providing the second portion of the number plurality of items to a second FIFO of the pair of FIFOs of the stage in order. The last switch is for merging and sorting a third portion of the number of items to provide the number of items in order.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.