Heap Sorter Algorithm for FPGA

Heap Sorter Algorithm for FPGA

Details

Category: Arithmetic Core

Created: October 13, 2012

Updated: January 27, 2020

Language: VHDL

Other project properties

Development Status: Beta

WishBone compliant: No

WishBone version: n/a

License: BSD

Description

This project implements a sorter able to sort a continuous stream of data, consisting of records labeled with "sort keys".
Sorter sorts one record every two clock cycles.
Sorter is based on the heap sort algorithm. Efficient implementation is assured thanks to the use of internal dual port
RAM in FPGA.
The required size of heap is equal to the expected maximum distance between unsorted records in the data stream.

Detailed description

The sorter implemented in this project is designed for sorting of stream of constant length records.
The main supposed application area are the multichannel data acquisition systems, where data records labelled with time stamps are transmitted through multiple channels with different latencies to the data concentrator, which should sort data according to their time stamps and source identifiers before sending them to further processing.

Each record contains the "sort key" and the payload. In the simplest case, the sort key may be a N-bit bit vector, treated as unsigned integer number.
Of course in case of lengthy data stream, the sort key will reach its maximum value of 2^N-1 and then wrap to 0. For the sorter it is fully acceptable, as long, as the capacity of the sorter (maximum number of data records stored in the sorter) summed with the maximum distance between unsorted records in the input data stream is less than half of the maximum value of the sort-key.
In this case we may compare sort keys of the newly received data record and data records stored in the sorter using simple operation:

signal unsigned sort_key1(N-1 downto 0);
signal unsigned sort_key2(N-1 downto 0);
signal signed sort_key_diff(N-1 downto 0);
[...]

sort_key_diff

  • init=1, valid=0 - "initial record"
    The sorter is filled with initial records on the beginning of operation. The "initial record" is "smaller" than any data record. On the output of the sorter initial records may be discarded.
  • init=1, valid=1 - "end record"
    When all data are transferred to the sorter, you should feed the sorter with "end records" to keep the data flowing through the sorter, and to "flush" last sorted data out of the sorter. The "end record" is "bigger" than any data record. When first "end record" appears on the output, all data are sorted.
  • init=0, valid=1 - "standard data record"
    This record contains the useful data. The time-stamp is stored in the "sort-key" and user data in the "payload".
  • init=0, valid=0 - "empty data record"
    When in the particular sorting cycle there are no valid data on the input of the sorter, the last data records remain in the sorter. Therefore you may feed the sorter with "empty data records" with sort key equal to to the highest recent sort key, to keep data flowing through the sorter. On the output the "empty data records" may get discarded.


,

entity sorter_sys is
generic (
NLEVELS : integer := SYS_NLEVELS -- number of levels in the sorter heap
);

port (
din : in T_DATA_REC;
we : in std_logic;
dout : out T_DATA_REC;
dav : out std_logic;
clk : in std_logic;
rst_n : in std_logic;
ready : out std_logic);
end sorter_sys;

T_DATA_REC,sorter_pkg.vhd,tdrec2stlv,stlv2tdrec,
,T_SORT_KEY type,sort_cmp_lt,
,
,
,
,
,ghdl,
,
,dpram4.vhd,http://danstrother.com/2010/09/11/inferring-rams-in-fpgas/,dpram_inf.vhd,
,
,
,
,doi:10.1117/12.905281,
,
,
,
,
,http://wzab.cba.pl/STARE/fpga_heapsort/,.

HLS implementation for Xilinx FPGAs
I have prepared different implementations of my heap sorter in C using the Xilinx HLS compiler. The detailed description of those implementations and their properties may be found in my paper:
Wojciech M. Zabołotny, "Implementation of heapsort in programmable logic with high-level synthesis", Proc. SPIE 10808 (2018); ,doi:10.1117/12.2502093,