Method for a parallel-sort algorithm hardware implementation
Permalink
Bookmark
Share
Twitter
Digg
Reddit
Facebook
Stumbleupon
Del.icio.us| IP.com Number | IPCOM000141641D |
|
|
|---|---|---|---|
| Dated | Oct 11, 2006 UTC | ||
| Size | 3 page(s) (38.0 KB) | ||
Publication Summary
Disclosed is a method for parallel-sort algorithm hardware implementation. Benefits include improved functionality, improved performance, improved design flexibility, and improved cost effectiveness.| Country | United States |
|---|---|
| Language | English (United States) |
About this Publication
This document was submitted to IP.com's Prior Art Database and this preview is designed to provide you with information regarding the contents of this document by displaying up to the first four pages of the document as scaled page renderings and displaying a limited amount of text which was extracted from the document on the Text Preview Tab.
To find out more on how to obtain the entire document, click the Download tab. There is a charge for downloading some Prior Art Database documents; please examine carefully whether you believe this document fills your needs before purchasing.
For more information about the Prior Art Database, visit the Learn section of this website. Thank you for visiting IP.com's Prior Art Database! You may wish to check out our Global Patent Search website before you leave.
Method for a parallel-sort algorithm hardware implementation
Disclosed is a method for parallel-sort algorithm hardware implementation. Benefits include improved functionality, improved performance, improved design flexibility, and improved cost effectiveness.
Background
A conventional bubble-sort algorithm on a sequence of length n, requires n*(n-1)/2 compare-and-swap operations in n-1 iterations. Some fast sorting algorithms, such as quick sort and shell sort, are in some way derived from bubble sorting.
General description
The disclosed method is a parallel-sort algorithm hardware implementation. The method is applicable to digital signal processing (DSP) related design implementation. The algorithm maximizes the parallelism of sorting, using a minimum of hardware resources, while providing implementation flexibility.
Advantages
The disclosed method
provides advantages, including:
• Improved functionality due to
providing a parallel-sort algorithm hardware implementation
• Improved performance due to regrouping
and parallelizing all compare-and-swap operations to reduce processing time
• Improved design flexibility due to enabling the parallel-compare-and-swap operations to be grouped in any fashion to adapt to the design’s pipeline restrictions
• Improved cost effectiveness due to performing the sorting in-place without requiring additional storage
Detailed description
The disclosed method is a parallel-sort algorithm hardware implementation. The method regroups and parallelizes all compare-and-swap operations required for a bubble sort to achieve sorting in the shortest time. For a...