Synthesizable heap-sorter for FPGA - BSD licensed sources

[wzab]

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: http://groups.google.com/group/alt.sources/msg/ab4bda56ca52cc59?dmode=source
(copy the body of the message to the file, then run "uudecode" on this
file, and you'll get sorter.tar.bz2 archive).

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
http://www.ise.pw.edu.pl/~wzab/fpga_heapsort
--
HTH & Best regards,
Wojtek Zabolotny

 

[wzab]

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

 

[wzab]

I have finally managed to post uncorrupted shar archive with sources
of my sorter to alt.sources.
Additionally I have provided sources at http://www.ise.pw.edu.pl/~wzab/fpga_heapsort/sorter.tar.bz2
with short description at http://www.ise.pw.edu.pl/~wzab/fpga_heapsort
--
Regards, Wojtek

 

[Weng Tianxiang]

On Jul 11, 11:46 am, wzab <wza...@gmail.com> wrote:

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:http://groups.google.com/group/alt.sources/msg/ab4bda56ca52cc59?dmode...
(copy the body of the message to the file, then run "uudecode" on this
file, and you'll get sorter.tar.bz2 archive).

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) athttp://www.ise.pw.edu.pl/~wzab/fpga_heapsort
--
HTH & Best regards,
Wojtek Zabolotny

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

 

[wzab]

On Aug 11, 2:26 am, Weng Tianxiang <wtx...@gmail.com> wrote:

On Jul 11, 11:46 am, wzab <wza...@gmail.com> wrote:

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.
[...]

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

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

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.

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=2^(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=${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.

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

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

Wojtek