SORT
A Pair of Sorting modules.
FPGA proven NO
ASIC proven NO
Description
Sorting is a recurring requirement in many algorithms. Writing code for sorting two or four numbers is not that difficult,
but efficient sorting for larger numbers gets complicated. The code here uses the odd-even sort method.
Both modules are purely combinatorial thus the sorting takes place in absence of a clock or reset.
For both the data width and the number of input ports can be set using parameters.
For these modules the number of input ports must be a power of two.
Both modules have been tested and can be synthesized. As usual they are provided with their
test benches. In this case verification was done visual checking the waveforms.
This is the RTL schematic as provided by the Xilinx Vivado tool for N=16:
(Click to enlarge)
In the archive you find the following modules:
- sort_N.v Sort N inputs each W bits wide from max to min
- maxmin_N.v Finds the maximum and minimum of N inputs each W bits wide
A trial synthesis for a Xilinx Zynq FPGA was performed. With the data width (W) set to 8 and
the number of ports (P) also set to 8 this produced the following results:
sort_N.v Uses 455 LUTS.
maxmin_N.v Uses 328 LUTS.
The code can be found here
As usual the code comes with test benches, although in this case they where rather simple as they are not self-checking