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?
Take the 2-minute tour
×
Electrical Engineering Stack Exchange is a question and answer site for electronics and electrical engineering professionals, students, and enthusiasts. It's 100% free, no registration required.
|
|
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. |
||||
|
|
