I have a fixed set of 9 values that needs to be sorted in an FPGA.
What would be an optimal sorting algorithm to implement?
\$\begingroup\$\$\endgroup\$
9
- 1\$\begingroup\$Would requiring 9! comparators be an issue?\$\endgroup\$– Spehro 'speff' PefhanyCommentedApr 12, 2014 at 20:33
- 4\$\begingroup\$Please define "optimal". Fastest? Smallest? Least power? Easiest to code?\$\endgroup\$– Joe HassCommentedApr 12, 2014 at 20:39
- \$\begingroup\$Optimal = Least number of logical blocks needed.\$\endgroup\$– ErikAndrenCommentedApr 12, 2014 at 20:46
- \$\begingroup\$How many clock cycles can we use?\$\endgroup\$– Dave TweedCommentedApr 12, 2014 at 21:48
- 1\$\begingroup\$Before we can even start to consider making this "optimal", too much depends on how a "value" is represented (integer? how many bits?) and what the handshake protocol with the outside world is. Please specify. Since you want to minimize the physical size, we will assume that computation time is not an issue at all.\$\endgroup\$– PhilippeCommentedApr 13, 2014 at 13:24
| Show 4 more comments
1 Answer
\$\begingroup\$
Sorting in an FPGA is typically done using a Sorting network. One good example of a sorting network is Bitonic Sort. A sorting network is a fixed network of comparators where the order of operations does not depend on the data. Bitonic sort has a complexity of O(n*log(n)^2), although it is not O(n*log(n)) like sorting algorithms popularly used in software implementations it is still often more efficient to implement in an FPGA due to its fixed structure.
For small arrays such as your 9-values you can just have a fixed sorting network with a throughput of 9 sorted values per clock cycle. If you have larger arrays or lower throughput requirements the sorting operation can be computed in different passes kind of like an FFT where a fixed k-input bitonic sort network is applied to the data several times. Typically k is chosen large enough to minimize the number of passes while keeping the data-path size feasible. The smallest bitonic sort network is a 2-input network where one output is the minimum value and the other is the maximum value.
\$\endgroup\$
