SOLSORT 22.9.2006

SOLSORT is a chip, which sorts 128 32-bit integers with a parallel bubblesort algorithm in 64 cycles. Every cycle only consists of two comparisons. If you want to display 3D-graphics on a computer, you can use linear equalities (Astro Solutions 3DVideoCreator) or sort polygons (Astro Solutions Cubewar2003, Planetris, Space Bomber). Using linear equalities is preferred, because they can be processed parallel, but sorting can be accelerated with chips, too. Cubewar2003 sorts 80% of the time, but also other applications sort a lot of time. The most-used algorithm for sorting is quicksort, but with special hardware parallel bubblesort is faster. First it was developed for parallel computers. If you sort n elements, Quicksort takes n*log(n) cycles and parallel bubblesort only n. But you are bound to fix numbers of elements. The following algorithm is a mixture and accelerates sorting:
You apply quicksort to the array, which has to be sorted and divide the arrays while there is a part with more than 128 elements. The rest is sorted by the SOLSORT chip. The result is that the costs of the last six recursions sink from 128*7 per array to 128 per array. For example you spare 25% for arrays with one million elements if the last divided arrays have a size between 63 and 128 elements, which is a normal distribution. If the application sorts 30% of its working time, the acceleration still is more than 5%.
SOLSORT is OpenSource and testing and changing is allowed. Commercial use requires a license from Astro Solutions. Demand is not expected, because SOLSORT was written and tested in AstroChip and not in VHDL.