Synthesizable heap-sorter for FPGA - BSD licensed sources

Hi,

I have prepared a heap-sorter implementation for FPGA. The sources are licensed under the BSD license and are available at alt.sources group. Due to the fact, that I'm on my holidays, I was not able to post the standard shar archive, and instead I have finally to send the uuencoded tar.bz archive. You can find it at:

The sorter is able to sort one data record every 2 clock pulses. I was able to compile into Virtex-6 XC6VLX75T-3FF484 a sorter with capacity of 65535 records (able to sort the data stream with maximum distance between unsorted records equal to 65535) with each record containing 18 bits of time-stamp and 20 bits of payload.

More information is available at the beginning of my alt.sources post. The current sources will be available (a little later) at

-- HTH & Best regards, Wojtek Zabolotny

Ooops, sorry for repeated post. I have now only GPRS access to the network, and all my network related programs started to work in a crazy way :-(.

-- Regards, Wojtek

I have finally managed to post uncorrupted shar archive with sources of my sorter to alt.sources. Additionally I have provided sources at

-- Regards, Wojtek

Hi Wojtek, Your work is impressive. It may be used in 16-bit integer environment.

I want to know what delay time is: from the last input data to the first output sorted data in addition to the one sorted data out for every clock cycle.

Your Heapsort's big problem is it can apply to 16-bit integer and the sort is not stable.

Weng

The size of the "payload" and "sort_key" ("time-stamp") part of the data record may be defined in the sorter_pkg.vhd file, so of course it may be used for 16-bit integers as well, but you may use it also for much longer

The sorter is dedicated for sorting of stream of data. Therefore you obtain the first data before the last data enters the sorter. The first sorted data appear on the output as soon, as the sorter is filled with the data. The sorter containing N levels has the capacity of M=3D2^(N+1)-1 data records. So the first sorted record is available on the output 2*M clock pulses, after the first record enters the sorter. Of course sorter may sort only the records fitting into its storage. Therefore the maximum distance between unsorted records in the input stream must be not greater than M.

You may investigate the internal operation of the sorter by changing in the Makefile the line: ./${ENTITY} ${RUN_OPTIONS} 2>&1 > res.txt into: ./${ENTITY} --wave=3D${ENTITY}.ghw ${RUN_OPTIONS} 2>&1 >

res.txt Then you can open the resulting sorter_sys_tb.ghw file in the gtkwave and check how all signals change in time.

More detailed description will be available in my paper prepared for Proceedings of SPIE, however according to SPIE policy I can not publish it yet.

Yes, the Heapsort is not a stable sort algorithm. However for many applications this is not a problem.

Wojtek

Hi,

The article describing my "Synthesizable heap-sorter for FPGA" (available at