VHDL modules: Sorting algorithm FPGA implementations
This demo project contains five VHDL implementations of two hardware-friendly sorting algorithms: (Odd-even) Brick sort and Selection sort.
Description
FPGAs can sort arrays with combinational logic or as pipelined parallelized sorter circuits. Or you can use state machines, and the sorting can happen in-place in block RAM.
This demo project contains five implementations of two hardware-friendly sorting algorithms:
There’s a video where I explain how the algorithm works and how to use the files. We’ll go through the five modules and run the testbenches together.
The full duration of the video is 34 minutes. Here’s a preview. 👇
This project is only available in the VHDLwhiz Membership.
The membership subscription gives you access to this and many other VHDL resources and courses.
You pay monthly to access the membership and can cancel the automatic renewal anytime. There is no lock-in period or hidden fees.
Zip content
Here’s the list of files included in the project:
sorting/ ├── LICENSE.txt ├── README.txt ├── brick_sort_generate │ ├── brick_sort_generate.vhd │ ├── brick_sort_generate_tb.vhd │ ├── run.do │ └── wave.do ├── brick_sort_pipelined │ ├── brick_sort_pipelined.vhd │ ├── brick_sort_pipelined_tb.vhd │ ├── run.do │ └── wave.do ├── brick_sort_variable │ ├── brick_sort_variable.vhd │ ├── brick_sort_variable_tb.vhd │ ├── run.do │ └── wave.do ├── questa_proj │ └── sorting.mpf ├── selection_sort │ ├── run.do │ ├── selection_sort.vhd │ ├── selection_sort_tb.vhd │ └── wave.do ├── selection_sort_bram │ ├── dual_port_ram.vhd │ ├── run.do │ ├── selection_sort_bram.vhd │ ├── selection_sort_bram_tb.vhd │ ├── top_wrapper.vhd │ └── wave.do └── sorting_pkg.vhd
VHDL module entities
Brick sort implementation using a variable to store the intermediate values:
entity brick_sort_variable is
generic (
array_length : positive
);
port (
unsorted : in data_array_t(0 to array_length - 1);
sorted : out data_array_t(0 to array_length - 1)
);
end brick_sort_variable;
Brick sort implementation with generate statements using a signal array to store intermediate values:
entity brick_sort_generate is
generic (
array_length : positive
);
port (
unsorted : in data_array_t(0 to array_length - 1);
sorted : out data_array_t(0 to array_length - 1)
);
end brick_sort_generate;
Pipelined Brick sort implementation constructed using a generate statements:
entity brick_sort_pipelined is
generic (
array_length : positive
);
port (
clk : in std_logic;
rst : in std_logic;
unsorted : in data_array_t(0 to array_length - 1);
sorted : out data_array_t(0 to array_length - 1);
in_valid : in std_logic;
out_valid : out std_logic
);
end brick_sort_pipelined;
Selection sort implementation using registers to store intermediate values:
entity selection_sort is
generic (
array_length : positive
);
port (
clk : in std_logic;
rst : in std_logic;
unsorted : in data_array_t(0 to array_length - 1);
sorted : out data_array_t(0 to array_length - 1);
in_valid : in std_logic;
in_ready : out std_logic;
out_valid : out std_logic
);
end selection_sort;
Selection sort implementation that sorts elements stored in block RAM in-place:
entity selection_sort_bram is
generic (
array_length : positive -- RAM depth
);
port (
clk : in std_logic;
rst : in std_logic;
-- Control interface
start : in std_logic;
ready : out std_logic;
done : out std_logic;
-- Block RAM interface
ram_wr_en : out std_logic;
ram_addr : out integer range 0 to array_length - 1;
ram_din : out data_t;
ram_dout : in data_t
);
end selection_sort_bram;
This project is only available in the VHDLwhiz Membership.
The membership subscription gives you access to this and many other VHDL resources and courses.
You pay monthly to access the membership and can cancel the automatic renewal anytime. There is no lock-in period or hidden fees.
License agreement
MIT License
Copyright (c) 2024 Jonas Julian Jensen
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
Reviews
There are no reviews yet.