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
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.