2
\$\begingroup\$

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?

\$\endgroup\$
9
  • 1
    \$\begingroup\$ Would requiring 9! comparators be an issue? \$\endgroup\$ Apr 12 '14 at 20:33
  • 4
    \$\begingroup\$ Please define "optimal". Fastest? Smallest? Least power? Easiest to code? \$\endgroup\$
    – Joe Hass
    Apr 12 '14 at 20:39
  • \$\begingroup\$ Optimal = Least number of logical blocks needed. \$\endgroup\$
    – ErikAndren
    Apr 12 '14 at 20:46
  • \$\begingroup\$ How many clock cycles can we use? \$\endgroup\$
    – Dave Tweed
    Apr 12 '14 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\$
    – Philippe
    Apr 13 '14 at 13:24
4
\$\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\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.