Dual port memory based heapsort implementation for FPGA



Here you can find sources of my synthesizable heap-sorter for FPGA, described in the paper "Dual port memory based heapsort implementation for FPGA" which was presented during the "XXVIII-th IEEE-SPIE Joint Symposium on Photonics, Web Engineering, Electronics for Astronomy and High Energy Physics Experiments,Wilga 2011" and was submitted to Proceedings of SPIE.
This paper should be cited as:

Wojciech M. Zabołotny, "Dual port memory based Heapsort implementation for FPGA", Proc. SPIE 8008, 80080E (2011); doi:10.1117/12.905281
and is available at http://dx.doi.org/10.1117/12.905281

In fact, after I've finished my implementation, and submitted the first version of the paper, I've found the very similar solution in the:
@INPROCEEDINGS{786822, author={Tuan Ha-duong and Moreira, S.S.}, booktitle={ATM, 1999. ICATM '99. 1999 2nd International Conference on}, title={T he heap-sort based ATM cells spacer}, year={1999}, month={}, volume={}, number={}, pages={346 -350}, doi={10.1109/ICATM.1999.786822}, ISSN={},} So before my paper is available, you may find some explanations of the basic ideas in the above publication.

Comparing to the version described in my paper, sources contained in this archive provide the following improvements:

Instead of using the minimum value of "time-stamp" for "initial records" and maximum value for "end records", I've added two additional bit fields "init" and "valid". The "time-stamp" supplemented with those bits creates a "sort-key". The additional bits are used in the following way:

  1. 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.
  2. 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.
  3. 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".
  4. 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 time-stamp equal to to the highest recent time-stamp, to keep data flowing through the sorter. On the output the "empty data records" may get discarded.
The second improvement is that my sorter may work with wrapping around time-stamps. The only requirement is that the capacity of the sorter summed with the maximum distance between unsorted records in the input data stream should be less than half of the maximum value of the time-stamp (sort-key).

The sources provide also complete testbench for my sorter. To check it, you should simply adjust parameters given in the "sort_test_gen.py" file and run "make".
The Python script will generate the sorter configuration and input records. Then the makefile will compile the testbench and run the simulation.
Finally the records on the output will be analyzed. If everything works fine, the "Test passed!" message will be displayed.

If you want to synthesize the sorter for use in real FPGA, you should replace the implementation found in dpram4.vhd with implementation based on:
http://danstrother.com/2010/09/11/inferring-rams-in-fpgas/ The source is available in dpram_inf.vhd

If you want to customize and use my sorter, you should look at sorter_pkg.vhd file. It provides the essential comparison function sort_cmp_lt, and also the functions for converting data records into the std_logic_vector and from std_logic_vector.

All my sources in this archive are published under the BSD license. You can use them and modify them, however you should keep the information about the original author.
Additionally I'll be glad if you cite my paper, when you publish something based on my sources (I'll send follow-up message with detailed bibliographic information as soon as the paper is published).

The archive contains also some sources (dpram4.vhd, dpram_inf.vhd) which were obtained either from sources with unclear licensing conditions - so I simply provide them for completeness, but I'm not able to set any specific licensing for them.

I don't know whether my sorter infringes any patents. If you want to use it for commercial purposes, you should check it yourself. I also don't know if my sorter works correctly in all possible conditions. I provide it "AS IS" without any warranty. You use it on your own risk!

Wojciech Zabolotny