Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Heap-sorter implementation in behavioral but synthesizable VHDL code

58 views
Skip to first unread message

wzab

unread,
Jul 11, 2011, 11:50:26 AM7/11/11
to
Archive-name: fpga-heasort
Submitted-by: Wojciech M. Zabolotny wzab<at>ise.pw.edu.pl

This archive contains the source code of the heap-sorter
able to sort one data record every two clock pulses.

The detailed description of the implementation is provided 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.

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.

The current version of my sources will be available at
http://www.ise.pw.edu.pl/~wzab/fpga_heapsort

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 M. Zabolotny
wzab<at>ise.pw.edu.pl

#!/bin/sh
# This is a shell archive (produced by GNU sharutils 4.11).
# To extract the files from this archive, save it to some FILE, remove
# everything before the `#!/bin/sh' line above, then type `sh FILE'.
#
lock_dir=_sh10184
# Made on 2011-07-11 17:16 CEST by <wzab@wzlaphp>.
# Source directory was `/tmp/sort'.
#
# Existing files will *not* be overwritten, unless `-c' is specified.
#
# This shar contains:
# length mode name
# ------ ---------- ------------------------------------------
# 12022 -rw-r--r-- src/sorter_ctrl.vhd
# 2756 -rw-r--r-- src/dpram4.vhd
# 299 -rw-r--r-- src/sys_config.vhd
# 10019 -rw-r--r-- src/sorter_sys.vhd
# 1654 -rw-r--r-- src/dpram_inf.vhd
# 5494 -rw-r--r-- src/sort_dpram.vhd
# 7572 -rw-r--r-- src/sorter_pkg.vhd
# 4887 -rw-r--r-- src/sorter_sys_tb.vhd
# 54 -rw-r--r-- comp/dummy.txt
# 823 -rw-r--r-- makefile
# 2596 -rwxr-xr-x sort_test_gen.py
# 1591 -rwxr-xr-x sort_test_check.py
#
MD5SUM=${MD5SUM-md5sum}
f=`${MD5SUM} --version | egrep '^md5sum .*(core|text)utils'`
test -n "${f}" && md5check=true || md5check=false
${md5check} || \
echo 'Note: not verifying md5sums. Consider installing GNU
coreutils.'
if test "X$1" = "X-c"
then keep_file=''
else keep_file=true
fi
echo=echo
save_IFS="${IFS}"
IFS="${IFS}:"
gettext_dir=
locale_dir=
set_echo=false

for dir in $PATH
do
if test -f $dir/gettext \
&& ($dir/gettext --version >/dev/null 2>&1)
then
case `$dir/gettext --version 2>&1 | sed 1q` in
*GNU*) gettext_dir=$dir
set_echo=true
break ;;
esac
fi
done

if ${set_echo}
then
set_echo=false
for dir in $PATH
do
if test -f $dir/shar \
&& ($dir/shar --print-text-domain-dir >/dev/null 2>&1)
then
locale_dir=`$dir/shar --print-text-domain-dir`
set_echo=true
break
fi
done

if ${set_echo}
then
TEXTDOMAINDIR=$locale_dir
export TEXTDOMAINDIR
TEXTDOMAIN=sharutils
export TEXTDOMAIN
echo="$gettext_dir/gettext -s"
fi
fi
IFS="$save_IFS"
if (echo "testing\c"; echo 1,2,3) | grep c >/dev/null
then if (echo -n test; echo 1,2,3) | grep n >/dev/null
then shar_n= shar_c='
'
else shar_n=-n shar_c= ; fi
else shar_n= shar_c='\c' ; fi
f=shar-touch.$$
st1=200112312359.59
st2=123123592001.59
st2tr=123123592001.5 # old SysV 14-char limit
st3=1231235901

if touch -am -t ${st1} ${f} >/dev/null 2>&1 && \
test ! -f ${st1} && test -f ${f}; then
shar_touch='touch -am -t $1$2$3$4$5$6.$7 "$8"'

elif touch -am ${st2} ${f} >/dev/null 2>&1 && \
test ! -f ${st2} && test ! -f ${st2tr} && test -f ${f}; then
shar_touch='touch -am $3$4$5$6$1$2.$7 "$8"'

elif touch -am ${st3} ${f} >/dev/null 2>&1 && \
test ! -f ${st3} && test -f ${f}; then
shar_touch='touch -am $3$4$5$6$2 "$8"'

else
shar_touch=:
echo
${echo} 'WARNING: not restoring timestamps. Consider getting and
installing GNU `touch'\'', distributed in GNU coreutils...'
echo
fi
rm -f ${st1} ${st2} ${st2tr} ${st3} ${f}
#
if test ! -d ${lock_dir} ; then :
else ${echo} "lock directory ${lock_dir} exists"
exit 1
fi
if mkdir ${lock_dir}
then ${echo} "x - created lock directory ${lock_dir}."
else ${echo} "x - failed to create lock directory ${lock_dir}."
exit 1
fi
# ============= src/sorter_ctrl.vhd ==============
if test ! -d 'src'; then
mkdir 'src'
if test $? -eq 0
then ${echo} "x - created directory src."
else ${echo} "x - failed to create directory src."
exit 1
fi
fi
if test -n "${keep_file}" && test -f 'src/sorter_ctrl.vhd'
then
${echo} "x - SKIPPING src/sorter_ctrl.vhd (file already exists)"
else
${echo} "x - extracting src/sorter_ctrl.vhd (text)"
sed 's/^X//' << 'SHAR_EOF' > 'src/sorter_ctrl.vhd' &&
-------------------------------------------------------------------------------
-- Title : Sorting node controller for heap-sorter
-- Project : heap-sorter
-------------------------------------------------------------------------------
-- File : sorter_ctrl.vhd
-- Author : Wojciech M. Zabolotny <wz...@ise.pw.edu.pl>
-- Company :
-- Created : 2010-05-14
-- Last update: 2011-07-11
-- Platform :
-- Standard : VHDL'93
-------------------------------------------------------------------------------
-- Description:
-------------------------------------------------------------------------------
-- Copyright (c) 2010 Wojciech M. Zabolotny
-- This file is published under the BSD license, so you can freely
adapt
-- it for your own purposes.
-- Additionally this design has been described in my article
-- "Dual port memory based heapsort implementation for FPGA"
-- submitted to Proceedings of SPIE in 2011
-- I'll provide detailed bibliographic information after this paper
-- is printed.
-- I'd be glad if you cite this article when you publish something
based
-- on my design.
-------------------------------------------------------------------------------
-- Revisions :
-- Date Version Author Description
-- 2010-05-14 1.0 wzab Created
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
-- The sorter controller is connected with three dual port memories.
-- The first dual port memory tm_... provides the "upstream data"
-- The second dual port memory lm_... provides the "left branch of
downstream data"
-- The third dual port memory rm_... provides the "right branch of
downstream data"
-- The controller is notified about availability of the new data by
the
-- "update" signal.
-- However in this architecture we need to service two upstream
memories!
-- That's because we want to save one cycle, and to be able to issue
--
-- Important feature of each controller is the ability to clear the
memory
-- after reset.
-------------------------------------------------------------------------------
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use ieee.std_logic_textio.all;
use std.textio.all;
library work;
use work.sorter_pkg.all;
use work.sys_config.all;
X
entity sorter_ctrl is
X
X generic (
X NLEVELS : integer; -- number of levels (max
number of
X -- address bits
X NADDRBITS : integer -- number of used address
bits
X );
X
X port (
X -- Top memory connections
X tm_din : in T_DATA_REC;
X tm_dout : out T_DATA_REC;
X tm_addr : out std_logic_vector(NLEVELS-1 downto 0);
X tm_we : out std_logic;
X -- Left memory connections
X lm_din : in T_DATA_REC;
X lm_dout : out T_DATA_REC;
X lm_addr : out std_logic_vector(NLEVELS-1 downto 0);
X lm_we : out std_logic;
X -- Right memory connections
X rm_din : in T_DATA_REC;
X rm_dout : out T_DATA_REC;
X rm_addr : out std_logic_vector(NLEVELS-1 downto 0);
X rm_we : out std_logic;
X -- Upper level controller connections
X up_in : in std_logic;
X up_in_val : in T_DATA_REC;
X up_in_addr : in std_logic_vector(NLEVELS-1 downto 0);
X -- Upper level update notifier
X up_out : out std_logic;
X up_out_val : out T_DATA_REC;
X up_out_addr : out std_logic_vector(NLEVELS-1 downto 0);
X -- Lower level controller connections
X low_out : out std_logic;
X low_out_val : out T_DATA_REC;
X low_out_addr : out std_logic_vector(NLEVELS-1 downto 0);
X low_in : in std_logic;
X low_in_val : in T_DATA_REC;
X low_in_addr : in std_logic_vector(NLEVELS-1 downto 0);
X -- Lower level update notifier
X -- System connections
X clk : in std_logic;
X clk_en : in std_logic;
X ready_in : in std_logic;
X ready_out : out std_logic; -- signals, when memory is
cleared
X -- after reset
X rst_n : in std_logic);
end sorter_ctrl;
X
architecture sorter_ctrl_arch1 of sorter_ctrl is
X
X type T_CTRL_STATE is (CTRL_RESET, CTRL_CLEAR, CTRL_IDLE, CTRL_S1,
CTRL_S0);
X signal ctrl_state, ctrl_state_next : T_CTRL_STATE := CTRL_IDLE;
X signal addr, addr_i : std_logic_vector(NLEVELS-1
downto 0);
X signal s_low_in_addr, s_low_in_addr_i : std_logic_vector(NLEVELS-1
downto 0);
X signal s_up_in_addr, s_up_in_addr_i : std_logic_vector(NLEVELS-1
downto 0);
X signal s_ready_out, s_ready_out_i : std_logic;
X signal s_low_in, s_low_in_i : std_logic;
X signal s_addr_out : std_logic_vector(NLEVELS-1
downto 0);
X signal s_tm_dout : T_DATA_REC;
X signal s_up_in_val_i, s_up_in_val : T_DATA_REC :=
DATA_REC_INIT_DATA;
X signal s_low_in_val_i, s_low_in_val : T_DATA_REC :=
DATA_REC_INIT_DATA;
X
X
X constant ADDR_MAX : std_logic_vector(NLEVELS-1 downto 0) :=
std_logic_vector(to_unsigned(2**NADDRBITS-1, NLEVELS));
X
begin
X
X tm_dout <= s_tm_dout;
-- We have the two-process state machine.
X p1 : process (addr, ctrl_state, lm_din, low_in, low_in_addr,
low_in_val,
X ready_in, rm_din, s_addr_out, s_low_in,
s_low_in_addr,
X s_low_in_val, s_ready_out, s_up_in_val, up_in,
up_in_addr,
X up_in_val)
X variable rline : line;
X variable l_val : T_DATA_REC;
X variable r_val : T_DATA_REC;
X
X begin -- process p1
X -- defaults
X ctrl_state_next <= ctrl_state;
X tm_we <= '0';
X rm_we <= '0';
X lm_we <= '0';
X lm_addr <= (others => '0');
X rm_addr <= (others => '0');
X tm_addr <= (others => '0');
X s_ready_out_i <= s_ready_out;
X addr_i <= addr;
X s_low_in_addr_i <= s_low_in_addr;
X s_low_in_i <= low_in;
X low_out <= '0';
X up_out <= '0';
X up_out_addr <= (others => '0');
X s_up_in_val_i <= s_up_in_val;
X s_low_in_val_i <= s_low_in_val;
X lm_dout <= DATA_REC_INIT_DATA;
X rm_dout <= DATA_REC_INIT_DATA;
X s_tm_dout <= DATA_REC_INIT_DATA;
X s_addr_out <= (others => '0');
X case ctrl_state is
X when CTRL_RESET =>
X addr_i <= (others => '0');
X s_ready_out_i <= '0';
X ctrl_state_next <= CTRL_CLEAR;
X when CTRL_CLEAR =>
X lm_addr <= addr;
X rm_addr <= addr;
X lm_dout <= DATA_REC_INIT_DATA;
X rm_dout <= DATA_REC_INIT_DATA;
X lm_we <= '1';
X rm_we <= '1';
X if addr = ADDR_MAX then
X if ready_in = '1' then
X s_ready_out_i <= '1';
X ctrl_state_next <= CTRL_IDLE;
X end if;
X else
X addr_i <= std_logic_vector(unsigned(addr)+1);
X end if;
X when CTRL_IDLE =>
X -- We read "down" memories ("upper" value is provided by the
``bypass channel'')
X if up_in = '1' then
X ctrl_state_next <= CTRL_S1;
X tm_addr <= up_in_addr;
X lm_addr <= up_in_addr;
X rm_addr <= up_in_addr;
X addr_i <= up_in_addr;
X s_up_in_val_i <= up_in_val;
X if low_in = '1' then
X s_low_in_val_i <= low_in_val;
X s_low_in_addr_i <= low_in_addr;
X end if;
X end if;
X when CTRL_S1 =>
X -- In this cycle we can compare data
X -- Debug output!
X if SORT_DEBUG then
X write(rline, string'("CMP "));
X write(rline, NADDRBITS);
X write(rline, string'(" U:"));
X wrstlv(rline, tdrec2stlv(s_up_in_val));
X end if;
X l_val := lm_din;
X r_val := rm_din;
X -- Check, if we need to take value from lower ``bypass
channel''
X if s_low_in = '1' then
X if SORT_DEBUG then
X write(rline, string'(" x! "));
X end if;
X if (addr(NADDRBITS-1 downto 0) = s_low_in_addr(NADDRBITS-1
downto 0)) then
X -- We are reading a value which was just updated, so we
need to get it
X -- from ``bypass channel'' instead of memory
X if SORT_DEBUG then
X write(rline, string'(" y! "));
X end if;
X if s_low_in_addr(NADDRBITS) = '1' then
X l_val := s_low_in_val;
X else
X r_val := s_low_in_val;
X end if;
X end if;
X end if;
X if SORT_DEBUG then
X write(rline, string'(" L:"));
X wrstlv(rline, tdrec2stlv(l_val));
X write(rline, string'(" R:"));
X wrstlv(rline, tdrec2stlv(r_val));
X write(rline, string'(" A:"));
X end if;
X if sort_cmp_lt(l_val, s_up_in_val) and sort_cmp_lt(l_val,
r_val) then
X -- The L-ram value is the smallest
X -- Output the value from the L-ram and put the new value
into the L-ram
X s_tm_dout <= l_val;
X tm_addr <= addr;
X tm_we <= '1';
X
X up_out_val <= l_val;
X up_out <= '1';
X up_out_addr <= addr;
X
X lm_addr <= addr;
X lm_dout <= s_up_in_val;
X lm_we <= '1';
X
X low_out <= '1';
X low_out_val <= s_up_in_val;
X s_addr_out(NADDRBITS) <= '1';
X
X if NADDRBITS > 0 then
X s_addr_out(NADDRBITS-1 downto 0) <= addr(NADDRBITS-1
downto 0);
X end if;
X wrstlv(rline, s_addr_out);
X ctrl_state_next <= CTRL_IDLE;
X if SORT_DEBUG then
X write(rline, string'(" T<->L"));
X end if;
X elsif sort_cmp_lt(r_val, s_up_in_val) then
X -- The R-ram value is the smallest
X -- Output the value from the R-ram and put the new value
into the R-ram
X s_tm_dout <= r_val;
X tm_addr <= addr;
X tm_we <= '1';
X
X up_out_val <= r_val;
X up_out <= '1';
X up_out_addr <= addr;
X
X rm_addr <= addr;
X rm_dout <= s_up_in_val;
X rm_we <= '1';
X
X low_out <= '1';
X low_out_val <= s_up_in_val;
X
X s_addr_out(NADDRBITS) <= '0';
X if NADDRBITS > 0 then
X s_addr_out(NADDRBITS-1 downto 0) <= addr(NADDRBITS-1
downto 0);
X end if;
X ctrl_state_next <= CTRL_IDLE;
X if SORT_DEBUG then
X wrstlv(rline, s_addr_out);
X write(rline, string'(" T<->R"));
X end if;
X else
X -- The new value is the smallest
X -- Nothing to do, no update downstream
X s_tm_dout <= s_up_in_val;
X tm_we <= '1';
X tm_addr <= addr;
X
X up_out_val <= s_up_in_val;
X up_out <= '1';
X up_out_addr <= addr;
X
X ctrl_state_next <= CTRL_IDLE;
X wrstlv(rline, up_in_addr);
X if SORT_DEBUG then
X write(rline, string'(" T===T"));
X end if;
X end if;
X if SORT_DEBUG then
X writeline(reports, rline);
X end if;
X when others => null;
X end case;
X end process p1;
X
X p2 : process (clk, rst_n) is
X begin -- process p2
X if rst_n = '0' then -- asynchronous reset (active
low)
X ctrl_state <= CTRL_RESET;
X s_ready_out <= '0';
X addr <= (others => '0');
X s_low_in_addr <= (others => '0');
X s_low_in <= '0';
X s_low_in_val <= DATA_REC_INIT_DATA;
X s_up_in_val <= DATA_REC_INIT_DATA;
X --update_out <= '0';
X --addr_out <= (others => '0');
X elsif clk'event and clk = '1' then -- rising clock edge
X s_ready_out <= s_ready_out_i;
X ctrl_state <= ctrl_state_next;
X addr <= addr_i;
X s_low_in_addr <= s_low_in_addr_i;
X s_low_in_val <= s_low_in_val_i;
X s_up_in_val <= s_up_in_val_i;
X s_low_in <= s_low_in_i;
X end if;
X end process p2;
X ready_out <= s_ready_out;
X low_out_addr <= s_addr_out;
end sorter_ctrl_arch1;
SHAR_EOF
(set 20 11 07 11 16 51 35 'src/sorter_ctrl.vhd'
eval "${shar_touch}") && \
chmod 0644 'src/sorter_ctrl.vhd'
if test $? -ne 0
then ${echo} "restore of src/sorter_ctrl.vhd failed"
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'src/sorter_ctrl.vhd':
'MD5 check failed'
) << \SHAR_EOF
23abe16f2a24b0e0dc666000da22ed70 src/sorter_ctrl.vhd
SHAR_EOF
else
test `LC_ALL=C wc -c < 'src/sorter_ctrl.vhd'` -ne 12022 && \
${echo} "restoration warning: size of 'src/sorter_ctrl.vhd' is not
12022"
fi
fi
# ============= src/dpram4.vhd ==============
if test ! -d 'src'; then
mkdir 'src'
if test $? -eq 0
then ${echo} "x - created directory src."
else ${echo} "x - failed to create directory src."
exit 1
fi
fi
if test -n "${keep_file}" && test -f 'src/dpram4.vhd'
then
${echo} "x - SKIPPING src/dpram4.vhd (file already exists)"
else
${echo} "x - extracting src/dpram4.vhd (text)"
sed 's/^X//' << 'SHAR_EOF' > 'src/dpram4.vhd' &&
-- Simulation model of the dual port RAM (DP RAM) with single clock
-- and with "read-after-write" operation.
-- This file was combined from multiple descriptions and models of
dual port RAMs
-- which I was able to find in the Internet and in the documentation
provided
-- by vendors like Xilinx or Altera.
-- Therefore the only thing I can do is to publish it as PUBLIC DOMAIN
--
-- Please note, that for synthesis you should replace this file with
-- another DP RAM wrapper inferring the real DP RAM
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
X
entity dp_ram_scl is
X
X generic
X (
X DATA_WIDTH : natural;
X ADDR_WIDTH : natural
X );
X
X port
X (
X clk : in std_logic;
X addr_a : in std_logic_vector(ADDR_WIDTH-1 downto 0);
X addr_b : in std_logic_vector(ADDR_WIDTH-1 downto 0);
X data_a : in std_logic_vector((DATA_WIDTH-1) downto 0);
X data_b : in std_logic_vector((DATA_WIDTH-1) downto 0);
X we_a : in std_logic := '1';
X we_b : in std_logic := '1';
X q_a : out std_logic_vector((DATA_WIDTH -1) downto 0);
X q_b : out std_logic_vector((DATA_WIDTH -1) downto 0)
X );
X
end dp_ram_scl;
X
architecture rtl of dp_ram_scl is
X
X signal v_addr_a : natural range 0 to 2**ADDR_WIDTH - 1;
X signal v_addr_b : natural range 0 to 2**ADDR_WIDTH - 1;
X subtype word_t is std_logic_vector((DATA_WIDTH-1) downto 0);
X type memory_t is array((2**ADDR_WIDTH-1) downto 0) of word_t;
X
X signal ram : memory_t := (others => x"33"); -- For debugging -
initialize
X -- simulated RAM with
x"33"
X
begin
X
X v_addr_a <= to_integer(unsigned(addr_a(ADDR_WIDTH-1 downto 0)));
X v_addr_b <= to_integer(unsigned(addr_b(ADDR_WIDTH-1 downto 0)));
X
X process(clk)
X begin
X
X if(rising_edge(clk)) then
X -- Port A
X if(we_a = '1') then
X ram(v_addr_a) <= data_a;
X -- read-after-write behavior
X q_a <= data_a;
X else
X -- simulate "unknown" value when the same address is written
via one port
X -- and immediately read via another port
X if we_b='1' and v_addr_a=v_addr_b then
X q_a <= (others => 'X');
X else
X q_a <= ram(v_addr_a);
X end if;
X end if;
X -- Port B
X if(we_b = '1') then
X ram(v_addr_b) <= data_b;
X -- read-after-write behavior
X q_b <= data_b;
X else
X -- simulate "unknown" value when the same address is written
via one port
X -- and immediately read via another port
X if we_a='1' and v_addr_a=v_addr_b then
X q_b <= (others => 'X');
X else
X q_b <= ram(v_addr_b);
X end if;
X end if;
X end if;
X end process;
X
end rtl;
SHAR_EOF
(set 20 11 07 11 15 09 54 'src/dpram4.vhd'
eval "${shar_touch}") && \
chmod 0644 'src/dpram4.vhd'
if test $? -ne 0
then ${echo} "restore of src/dpram4.vhd failed"
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'src/dpram4.vhd': 'MD5
check failed'
) << \SHAR_EOF
bd39e4a2778d63d514531d897aec1ab7 src/dpram4.vhd
SHAR_EOF
else
test `LC_ALL=C wc -c < 'src/dpram4.vhd'` -ne 2756 && \
${echo} "restoration warning: size of 'src/dpram4.vhd' is not 2756"
fi
fi
# ============= src/sys_config.vhd ==============
if test -n "${keep_file}" && test -f 'src/sys_config.vhd'
then
${echo} "x - SKIPPING src/sys_config.vhd (file already exists)"
else
${echo} "x - extracting src/sys_config.vhd (text)"
sed 's/^X//' << 'SHAR_EOF' > 'src/sys_config.vhd' &&
library ieee;
use ieee.std_logic_1164.all;
library work;
package sys_config is
X constant SORT_DEBUG : boolean :=false;
X constant SYS_NLEVELS : integer :=5;
X constant DATA_REC_SORT_KEY_WIDTH : integer :=8;
X constant DATA_REC_PAYLOAD_WIDTH : integer :=4;
end sys_config;
SHAR_EOF
(set 20 11 07 11 16 48 06 'src/sys_config.vhd'
eval "${shar_touch}") && \
chmod 0644 'src/sys_config.vhd'
if test $? -ne 0
then ${echo} "restore of src/sys_config.vhd failed"
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'src/sys_config.vhd':
'MD5 check failed'
) << \SHAR_EOF
9f0d63702682ff9afa28a73e295973a5 src/sys_config.vhd
SHAR_EOF
else
test `LC_ALL=C wc -c < 'src/sys_config.vhd'` -ne 299 && \
${echo} "restoration warning: size of 'src/sys_config.vhd' is not
299"
fi
fi
# ============= src/sorter_sys.vhd ==============
if test -n "${keep_file}" && test -f 'src/sorter_sys.vhd'
then
${echo} "x - SKIPPING src/sorter_sys.vhd (file already exists)"
else
${echo} "x - extracting src/sorter_sys.vhd (text)"
sed 's/^X//' << 'SHAR_EOF' > 'src/sorter_sys.vhd' &&
-------------------------------------------------------------------------------
-- Title : Top entity of heap-sorter
-- Project : heap-sorter
-------------------------------------------------------------------------------
-- File : sorter_sys.vhd
-- Author : Wojciech M. Zabolotny <wz...@ise.pw.edu.pl>
-- Company :
-- Created : 2010-05-14
-- Last update: 2011-07-11
-- Platform :
-- Standard : VHDL'93
-------------------------------------------------------------------------------
-- Description:
-------------------------------------------------------------------------------
-- Copyright (c) 2010 Wojciech M. Zabolotny
-- This file is published under the BSD license, so you can freely
adapt
-- it for your own purposes.
-- Additionally this design has been described in my article
-- "Dual port memory based heapsort implementation for FPGA"
-- submitted to Proceedings of SPIE in 2011
-- I'll provide detailed bibliographic information after this paper
-- is printed.
-- I'd be glad if you cite this article when you publish something
based
-- on my design.
-------------------------------------------------------------------------------
-- Revisions :
-- Date Version Author Description
-- 2010-05-14 1.0 wzab Created
-------------------------------------------------------------------------------
X
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use ieee.std_logic_textio.all;
use std.textio.all;
library work;
use work.sorter_pkg.all;
use work.sys_config.all;
X
entity sorter_sys is
X generic (
X NLEVELS : integer := SYS_NLEVELS -- number of levels in the
sorter heap
X );
X
X port (
X din : in T_DATA_REC;
X we : in std_logic;
X dout : out T_DATA_REC;
X dav : out std_logic;
X clk : in std_logic;
X rst_n : in std_logic;
X ready : out std_logic);
end sorter_sys;
X
architecture sorter_sys_arch1 of sorter_sys is
X
X component sort_dp_ram
X generic (
X ADDR_WIDTH : natural;
X NLEVELS : natural;
X NAME : string);
X port (
X clk : in std_logic;
X addr_a : in std_logic_vector(NLEVELS-1 downto 0);
X addr_b : in std_logic_vector(NLEVELS-1 downto 0);
X data_a : in T_DATA_REC;
X data_b : in T_DATA_REC;
X we_a : in std_logic;
X we_b : in std_logic;
X q_a : out T_DATA_REC;
X q_b : out T_DATA_REC);
X end component;
X
X component sorter_ctrl
X generic (
X NLEVELS : integer;
X NADDRBITS : integer);
X port (
X tm_din : in T_DATA_REC;
X tm_dout : out T_DATA_REC;
X tm_addr : out std_logic_vector(NLEVELS-1 downto 0);
X tm_we : out std_logic;
X lm_din : in T_DATA_REC;
X lm_dout : out T_DATA_REC;
X lm_addr : out std_logic_vector(NLEVELS-1 downto 0);
X lm_we : out std_logic;
X rm_din : in T_DATA_REC;
X rm_dout : out T_DATA_REC;
X rm_addr : out std_logic_vector(NLEVELS-1 downto 0);
X rm_we : out std_logic;
X up_in : in std_logic;
X up_in_val : in T_DATA_REC;
X up_in_addr : in std_logic_vector(NLEVELS-1 downto 0);
X up_out : out std_logic;
X up_out_val : out T_DATA_REC;
X up_out_addr : out std_logic_vector(NLEVELS-1 downto 0);
X low_out : out std_logic;
X low_out_val : out T_DATA_REC;
X low_out_addr : out std_logic_vector(NLEVELS-1 downto 0);
X low_in : in std_logic;
X low_in_val : in T_DATA_REC;
X low_in_addr : in std_logic_vector(NLEVELS-1 downto 0);
X clk : in std_logic;
X clk_en : in std_logic;
X ready_in : in std_logic;
X ready_out : out std_logic;
X rst_n : in std_logic);
X end component;
X
X -- Create signals for address buses
X -- Some of them will remain unused.
X subtype T_SORT_BUS_ADDR is std_logic_vector(NLEVELS-1 downto 0);
X type T_SORT_ADDR_BUSES is array (NLEVELS downto 0) of
T_SORT_BUS_ADDR;
X signal low_addr, up_addr, addr_dr, addr_dl,
addr_u : T_SORT_ADDR_BUSES :=
(others => (others => '0'));
X type T_SORT_DATA_BUSES is array (NLEVELS downto 0) of T_DATA_REC;
X signal up_update_path, low_update_path, data_d, data_dl, data_dr,
data_u : T_SORT_DATA_BUSES := (others =>
DATA_REC_INIT_DATA);
X signal q_dr, q_dl, q_u, q_ul,
q_ur :
T_SORT_DATA_BUSES := (others => DATA_REC_INIT_DATA);
X signal we_ul, we_ur, we_u, we_dl, we_dr, low_update, up_update,
s_ready : std_logic_vector(NLEVELS downto 0) := (others => '0');
X signal addr_switch,
addr_switch_del :
std_logic_vector(NLEVELS downto 0);
X signal
l0_reg :
T_DATA_REC;
X signal
clk_en :
std_logic := '1';
X
begin -- sorter_sys_arch1
X
-- Build the sorting tree
X
X g1 : for i in 0 to NLEVELS-1 generate
X
X -- Two RAMs from the upper level are seen as a single RAM
X -- We use the most significant bit (i-th bit) to distinguish RAM
X -- In all RAMs the A-ports are used for upstream connections
X -- and the B-ports are used for downstream connections
X
X -- Below are processes used to combine two upstream RAMs in a
single one
X i0a : if i >= 1 generate
X addr_switch(i) <= addr_u(i)(i-1);
X end generate i0a;
X i0b : if i = 0 generate
X addr_switch(i) <= '0';
X end generate i0b;
X
X -- There is a problem with reading of data provided by two
upstream RAMs
X -- we need to multiplex the data...
X -- Delay for read data multiplexer
X s1 : process (clk, rst_n)
X begin -- process s1
X if rst_n = '0' then -- asynchronous reset
(active low)
X addr_switch_del(i) <= '0';
X elsif clk'event and clk = '1' then -- rising clock edge
X addr_switch_del(i) <= addr_switch(i);
X end if;
X end process s1;
X
X -- Upper RAM signals' multiplexer
X c1 : process (addr_switch, addr_switch_del, q_ul, q_ur, we_u)
X begin -- process c1
X we_ul(i) <= '0';
X we_ur(i) <= '0';
X if addr_switch(i) = '1' then
X we_ul(i) <= we_u(i);
X else
X we_ur(i) <= we_u(i);
X end if;
X if addr_switch_del(i) = '1' then
X q_u(i) <= q_ul(i);
X else
X q_u(i) <= q_ur(i);
X end if;
X end process c1;
X
X dp_ram_l : sort_dp_ram
X generic map (
X NLEVELS => NLEVELS,
X ADDR_WIDTH => i,
X NAME => "L")
X port map (
X clk => clk,
X addr_a => addr_dl(i),
X addr_b => addr_u(i+1),
X data_a => data_dl(i),
X data_b => data_u(i+1),
X we_a => we_dl(i),
X we_b => we_ul(i+1),
X q_a => q_dl(i),
X q_b => q_ul(i+1));
X
X dp_ram_r : sort_dp_ram
X generic map (
X NLEVELS => NLEVELS,
X ADDR_WIDTH => i,
X NAME => "R")
X port map (
X clk => clk,
X addr_a => addr_dr(i),
X addr_b => addr_u(i+1),
X data_a => data_dr(i),
X data_b => data_u(i+1),
X we_a => we_dr(i),
X we_b => we_ur(i+1),
X q_a => q_dr(i),
X q_b => q_ur(i+1));
X
X sorter_ctrl_1 : sorter_ctrl
X generic map (
X NLEVELS => NLEVELS,
X NADDRBITS => i)
X port map (
X tm_din => q_u(i),
X tm_dout => data_u(i),
X tm_addr => addr_u(i),
X tm_we => we_u(i),
X lm_din => q_dl(i),
X lm_dout => data_dl(i),
X lm_addr => addr_dl(i),
X lm_we => we_dl(i),
X rm_din => q_dr(i),
X rm_dout => data_dr(i),
X rm_addr => addr_dr(i),
X rm_we => we_dr(i),
X up_in => up_update(i),
X up_in_val => up_update_path(i),
X up_in_addr => up_addr(i),
X up_out => low_update(i),
X up_out_val => low_update_path(i),
X up_out_addr => low_addr(i),
X low_in => low_update(i+1),
X low_in_val => low_update_path(i+1),
X low_in_addr => low_addr(i+1),
X low_out => up_update(i+1), -- connections to the next
level
X low_out_val => up_update_path(i+1),
X low_out_addr => up_addr(i+1),
X clk => clk,
X clk_en => clk_en,
X ready_in => s_ready(i+1),
X ready_out => s_ready(i),
X rst_n => rst_n);
X
X end generate g1;
X -- top level
X
X -- On the top level we have only a single register
X process (clk, rst_n)
X variable rline : line;
X begin -- process
X if rst_n = '0' then -- asynchronous reset (active
low)
X l0_reg <= DATA_REC_INIT_DATA;
X elsif clk'event and clk = '1' then -- rising clock edge
X dav <= '0';
X if we_u(0) = '1' then
X l0_reg <= data_u(0);
X dout <= data_u(0);
X dav <= '1';
X if SORT_DEBUG then
X write(rline, string'("OUT: "));
X write(rline, tdrec2stlv(data_u(0)));
X writeline(reports, rline);
X end if;
X elsif we = '1' then
X if SORT_DEBUG then
X write(rline, string'("IN: "));
X write(rline, tdrec2stlv(din));
X writeline(reports, rline);
X end if;
X l0_reg <= din;
X dout <= din;
X else
X dout <= l0_reg;
X end if;
X end if;
X end process;
X ready <= s_ready(0);
X q_ur(0) <= l0_reg;
X q_ul(0) <= l0_reg;
X up_update(0) <= we;
X up_update_path(0) <= din;
X up_addr(0) <= (others => '0');
X
X -- signals for the last level
X
X s_ready(NLEVELS) <= '1';
X --addr(NLEVELS) <= (others => '0');
X data_dr(NLEVELS) <= DATA_REC_INIT_DATA;
X data_dl(NLEVELS) <= DATA_REC_INIT_DATA;
X we_dl(NLEVELS) <= '0';
X we_dr(NLEVELS) <= '0';
X
X low_update(NLEVELS) <= '0';
X low_update_path(NLEVELS) <= DATA_REC_INIT_DATA;
X low_addr(0) <= (others => '0');
X
end sorter_sys_arch1;
SHAR_EOF
(set 20 11 07 11 16 31 04 'src/sorter_sys.vhd'
eval "${shar_touch}") && \
chmod 0644 'src/sorter_sys.vhd'
if test $? -ne 0
then ${echo} "restore of src/sorter_sys.vhd failed"
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'src/sorter_sys.vhd':
'MD5 check failed'
) << \SHAR_EOF
433e4f8f534e7dac54bb53beb7ec1d21 src/sorter_sys.vhd
SHAR_EOF
else
test `LC_ALL=C wc -c < 'src/sorter_sys.vhd'` -ne 10019 && \
${echo} "restoration warning: size of 'src/sorter_sys.vhd' is not
10019"
fi
fi
# ============= src/dpram_inf.vhd ==============
if test -n "${keep_file}" && test -f 'src/dpram_inf.vhd'
then
${echo} "x - SKIPPING src/dpram_inf.vhd (file already exists)"
else
${echo} "x - extracting src/dpram_inf.vhd (text)"
sed 's/^X//' << 'SHAR_EOF' > 'src/dpram_inf.vhd' &&
-- A parameterized, inferable, true dual-port, common-clock block RAM
in VHDL.
-- Original file was taken from: http://danstrother.com/2010/09/11/inferring-rams-in-fpgas/
-- No license information were provided by the original author.
-- Minimal modifications were introduced by me to make it suitable for
my sorter.
X
library ieee;
use ieee.std_logic_1164.all;
use ieee.std_logic_unsigned.all;
X
entity dp_ram_scl is
X generic (
X DATA_WIDTH : integer := 72;
X ADDR_WIDTH : integer := 10
X );
X port (
-- common clock
X clk : in std_logic;
X -- Port A
X we_a : in std_logic;
X addr_a : in std_logic_vector(ADDR_WIDTH-1 downto 0);
X data_a : in std_logic_vector(DATA_WIDTH-1 downto 0);
X q_a : out std_logic_vector(DATA_WIDTH-1 downto 0);
X
X -- Port B
X we_b : in std_logic;
X addr_b : in std_logic_vector(ADDR_WIDTH-1 downto 0);
X data_b : in std_logic_vector(DATA_WIDTH-1 downto 0);
X q_b : out std_logic_vector(DATA_WIDTH-1 downto 0)
X );
end dp_ram_scl;
X
architecture rtl of dp_ram_scl is
X -- Shared memory
X type mem_type is array ((2**ADDR_WIDTH)-1 downto 0) of
std_logic_vector(DATA_WIDTH-1 downto 0);
X shared variable mem : mem_type;
begin
X
-- Port A
X process(clk)
X begin
X if(clk'event and clk = '1') then
X if(we_a = '1') then
X mem(conv_integer(addr_a)) := data_a;
X end if;
X q_a <= mem(conv_integer(addr_a));
X end if;
X end process;
X
-- Port B
X process(clk)
X begin
X if(clk'event and clk = '1') then
X if(we_b = '1') then
X mem(conv_integer(addr_b)) := data_b;
X end if;
X q_b <= mem(conv_integer(addr_b));
X end if;
X end process;
X
end rtl;
SHAR_EOF
(set 20 11 07 11 16 41 27 'src/dpram_inf.vhd'
eval "${shar_touch}") && \
chmod 0644 'src/dpram_inf.vhd'
if test $? -ne 0
then ${echo} "restore of src/dpram_inf.vhd failed"
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'src/dpram_inf.vhd':
'MD5 check failed'
) << \SHAR_EOF
245e6cb633a8335f0b70149795af4997 src/dpram_inf.vhd
SHAR_EOF
else
test `LC_ALL=C wc -c < 'src/dpram_inf.vhd'` -ne 1654 && \
${echo} "restoration warning: size of 'src/dpram_inf.vhd' is not
1654"
fi
fi
# ============= src/sort_dpram.vhd ==============
if test -n "${keep_file}" && test -f 'src/sort_dpram.vhd'
then
${echo} "x - SKIPPING src/sort_dpram.vhd (file already exists)"
else
${echo} "x - extracting src/sort_dpram.vhd (text)"
sed 's/^X//' << 'SHAR_EOF' > 'src/sort_dpram.vhd' &&
-------------------------------------------------------------------------------
-- Title : Parametrized DP RAM for heap-sorter
-- Project : heap-sorter
-------------------------------------------------------------------------------
-- File : sort_dpram.vhd
-- Author : Wojciech M. Zabolotny <wz...@ise.pw.edu.pl>
-- Company :
-- Created : 2010-05-14
-- Last update: 2011-07-06
-- Platform :
-- Standard : VHDL'93
-------------------------------------------------------------------------------
-- Description:
-------------------------------------------------------------------------------
-- Copyright (c) 2010 Wojciech M. Zabolotny
-- This file is published under the BSD license, so you can freely
adapt
-- it for your own purposes.
-- Additionally this design has been described in my article
-- "Dual port memory based heapsort implementation for FPGA"
-- submitted to Proceedings of SPIE in 2011
-- I'll provide detailed bibliographic information after this paper
-- is printed.
-- I'd be glad if you cite this article when you publish something
based
-- on my design.
-------------------------------------------------------------------------------
-- Revisions :
-- Date Version Author Description
-- 2010-05-14 1.0 wzab Created
-------------------------------------------------------------------------------
X
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use ieee.std_logic_textio.all;
use std.textio.all;
library work;
use work.sorter_pkg.all;
use work.sys_config.all;
X
entity sort_dp_ram is
X
X generic
X (
X ADDR_WIDTH : natural;
X NLEVELS : natural;
X NAME : string := "X"
X );
X
X port
X (
X clk : in std_logic;
X addr_a : in std_logic_vector(NLEVELS-1 downto 0);
X addr_b : in std_logic_vector(NLEVELS-1 downto 0);
X data_a : in T_DATA_REC;
X data_b : in T_DATA_REC;
X we_a : in std_logic;
X we_b : in std_logic;
X q_a : out T_DATA_REC;
X q_b : out T_DATA_REC
X );
X
end sort_dp_ram;
X
architecture rtl of sort_dp_ram is
X
X signal vq_a, vq_b, tdata_a, tdata_b :
std_logic_vector(DATA_REC_WIDTH-1 downto 0);
X signal reg : T_DATA_REC :=
DATA_REC_INIT_DATA;
X
X component dp_ram_scl
X generic (
X DATA_WIDTH : natural;
X ADDR_WIDTH : natural);
X port (
X clk : in std_logic;
X addr_a : in std_logic_vector(ADDR_WIDTH-1 downto 0);
X addr_b : in std_logic_vector(ADDR_WIDTH-1 downto 0);
X data_a : in std_logic_vector((DATA_WIDTH-1) downto 0);
X data_b : in std_logic_vector((DATA_WIDTH-1) downto 0);
X we_a : in std_logic := '1';
X we_b : in std_logic := '1';
X q_a : out std_logic_vector((DATA_WIDTH -1) downto 0);
X q_b : out std_logic_vector((DATA_WIDTH -1) downto 0));
X end component;
X
begin
X
X -- Convert our data records int std_logic_vector, so that
X -- standard DP RAM may handle it
X tdata_a <= tdrec2stlv(data_a);
X tdata_b <= tdrec2stlv(data_b);
X
X
X i1 : if ADDR_WIDTH > 0 generate
X -- When ADDR_WIDTH is above 0 embed the real DP RAM
X -- (even though synthesis tool may still replace it with
X -- registers during optimization for low ADDR_WIDTH)
X
X q_a <= stlv2tdrec(vq_a);
X q_b <= stlv2tdrec(vq_b);
X
X dp_ram_1 : dp_ram_scl
X generic map (
X DATA_WIDTH => DATA_REC_WIDTH,
X ADDR_WIDTH => ADDR_WIDTH)
X port map (
X clk => clk,
X addr_a => addr_a(ADDR_WIDTH-1 downto 0),
X addr_b => addr_b(ADDR_WIDTH-1 downto 0),
X data_a => tdata_a,
X data_b => tdata_b,
X we_a => we_a,
X we_b => we_b,
X q_a => vq_a,
X q_b => vq_b);
X
X end generate i1;
X
X i2 : if ADDR_WIDTH = 0 generate
X -- When ADDR_WIDTH is 0, DP RAM should be simply replaced
X -- with a register implemented below
X
X p1 : process (clk)
X begin -- process p1
X if clk'event and clk = '1' then -- rising clock edge
X if we_a = '1' then
X reg <= data_a;
X q_a <= data_a;
X q_b <= data_a;
X elsif we_b = '1' then
X reg <= data_b;
X q_a <= data_b;
X q_b <= data_b;
X else
X q_a <= reg;
X q_b <= reg;
X end if;
X end if;
X end process p1;
X
X end generate i2;
X
X dbg1 : if SORT_DEBUG generate
X
X -- Process monitoring read/write accesses to the memory (only for
debugging)
X p3 : process (clk)
X variable rline : line;
X begin -- process p1
X if clk'event and clk = '1' then -- rising clock edge
X if(we_a = '1' and we_b = '1') then
X write(rline, NAME);
X write(rline, ADDR_WIDTH);
X write(rline, string'(" Possible write collision!"));
X writeline(reports, rline);
X end if;
X
X if we_a = '1' then
X write(rline, NAME);
X write(rline, ADDR_WIDTH);
X write(rline, string'(" WR_A:"));
X wrstlv(rline, addr_a(ADDR_WIDTH-1 downto 0));
X write(rline, string'(" VAL:"));
X wrstlv(rline, tdata_a);
X writeline(reports, rline);
X end if;
X if we_b = '1' then
X write(rline, NAME);
X write(rline, ADDR_WIDTH);
X write(rline, string'(" WR_B:"));
X wrstlv(rline, addr_b(ADDR_WIDTH-1 downto 0));
X write(rline, string'(" VAL:"));
X wrstlv(rline, tdata_b);
X writeline(reports, rline);
X end if;
X end if;
X end process p3;
X end generate dbg1;
end rtl;
SHAR_EOF
(set 20 11 07 11 15 09 54 'src/sort_dpram.vhd'
eval "${shar_touch}") && \
chmod 0644 'src/sort_dpram.vhd'
if test $? -ne 0
then ${echo} "restore of src/sort_dpram.vhd failed"
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'src/sort_dpram.vhd':
'MD5 check failed'
) << \SHAR_EOF
c41b3c40342c871ebed4a25a9fb78f33 src/sort_dpram.vhd
SHAR_EOF
else
test `LC_ALL=C wc -c < 'src/sort_dpram.vhd'` -ne 5494 && \
${echo} "restoration warning: size of 'src/sort_dpram.vhd' is not
5494"
fi
fi
# ============= src/sorter_pkg.vhd ==============
if test -n "${keep_file}" && test -f 'src/sorter_pkg.vhd'
then
${echo} "x - SKIPPING src/sorter_pkg.vhd (file already exists)"
else
${echo} "x - extracting src/sorter_pkg.vhd (text)"
sed 's/^X//' << 'SHAR_EOF' > 'src/sorter_pkg.vhd' &&
-------------------------------------------------------------------------------
-- Title : Definitions for heap-sorter
-- Project : heap-sorter
-------------------------------------------------------------------------------
-- File : sorter_pkg.vhd
-- Author : Wojciech M. Zabolotny <wz...@ise.pw.edu.pl>
-- Company :
-- Created : 2010-05-14
-- Last update: 2011-07-11
-- Platform :
-- Standard : VHDL'93
-------------------------------------------------------------------------------
-- Description:
-------------------------------------------------------------------------------
-- Copyright (c) 2010 Wojciech M. Zabolotny
-- This file is published under the BSD license, so you can freely
adapt
-- it for your own purposes.
-- Additionally this design has been described in my article
-- "Dual port memory based heapsort implementation for FPGA"
-- submitted to Proceedings of SPIE in 2011
-- I'll provide detailed bibliographic information after this paper
-- is printed.
-- I'd be glad if you cite this article when you publish something
based
-- on my design.
-------------------------------------------------------------------------------
-- Revisions :
-- Date Version Author Description
-- 2010-05-14 1.0 wzab Created
-------------------------------------------------------------------------------
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use ieee.std_logic_textio.all;
use std.textio.all;
library work;
use work.sys_config.all;
X
package sorter_pkg is
X constant DATA_REC_WIDTH : integer := DATA_REC_SORT_KEY_WIDTH +
X DATA_REC_PAYLOAD_WIDTH + 2;
X
X
X subtype T_SORT_KEY is unsigned (DATA_REC_SORT_KEY_WIDTH - 1 downto
0);
X subtype T_PAYLOAD is std_logic_vector(DATA_REC_PAYLOAD_WIDTH - 1
downto 0);
X
X --alias T_SORT_KEY is unsigned (12 downto 0);
X type T_DATA_REC is record
X d_key : T_SORT_KEY;
X init : std_logic;
X valid : std_logic;
X d_payload : T_PAYLOAD;
X end record;
X
X -- Special constant used to initially fill the sorter
X -- Must be sorted so, that is smaller, than any other data
X constant DATA_REC_INIT_DATA : T_DATA_REC := (
X d_key => to_unsigned(0, DATA_REC_SORT_KEY_WIDTH),
X init => '1',
X valid => '0',
X d_payload => (others => '0')
X );
X
X -- Special constant used to ``flush'' the sorter at the end
X constant DATA_REC_END_DATA : T_DATA_REC := (
X d_key => to_unsigned(0, DATA_REC_SORT_KEY_WIDTH),
X init => '1',
X valid => '1',
X d_payload => (others => '0')
X );
X
X
X function sort_cmp_lt (
X constant v1 : T_DATA_REC;
X constant v2 : T_DATA_REC)
X return boolean;
X
X function tdrec2stlv (
X constant drec : T_DATA_REC)
X return std_logic_vector;
X
X function stlv2tdrec (
X constant dstlv : std_logic_vector)
X return T_DATA_REC;
X
X procedure wrstlv (
X rline : inout line;
X constant vect : std_logic_vector);
X
X file reports : text open write_mode is "STD_OUTPUT";
X
end sorter_pkg;
X
package body sorter_pkg is
X
X function stlv2tdrec (
X constant dstlv : std_logic_vector)
X return T_DATA_REC is
X variable result : T_DATA_REC;
X variable j : integer := 0;
X begin -- stlv2drec
X j := 0;
X result.d_key := unsigned(dstlv(j-1+DATA_REC_SORT_KEY_WIDTH
downto j));
X j := j+DATA_REC_SORT_KEY_WIDTH;
X result.valid := dstlv(j);
X j := j+1;
X result.init := dstlv(j);
X j := j+1;
X result.d_payload := dstlv(j-1+DATA_REC_PAYLOAD_WIDTH downto j);
X j := j+DATA_REC_PAYLOAD_WIDTH;
X return result;
X end stlv2tdrec;
X
X function tdrec2stlv (
X constant drec : T_DATA_REC)
X return std_logic_vector is
X variable result : std_logic_vector(DATA_REC_WIDTH-1 downto 0);
X variable j : integer := 0;
X begin -- tdrec2stlv
X j := 0;
X result(j-1+DATA_REC_SORT_KEY_WIDTH downto j) :=
std_logic_vector(drec.d_key);
X j := j
+DATA_REC_SORT_KEY_WIDTH;
X result(j) := drec.valid;
X j := j+1;
X result(j) := drec.init;
X j := j+1;
X result(j-1+DATA_REC_PAYLOAD_WIDTH downto j) :=
std_logic_vector(drec.d_payload);
X j := j
+DATA_REC_PAYLOAD_WIDTH;
X return result;
X end tdrec2stlv;
X
X
X -- Function sort_cmp_lt returns TRUE when the first opperand is
``less'' than
X -- the second one
X function sort_cmp_lt (
X constant v1 : T_DATA_REC;
X constant v2 : T_DATA_REC)
X return boolean is
X variable rline : line;
X variable dcomp : unsigned(DATA_REC_SORT_KEY_WIDTH-1 downto 0) :=
(others => '0');
X begin -- sort_cmp_lt
X -- Check the special cases
X if (v1.init = '1') and (v2.init = '0') then
X -- v1 is the special record, v2 is the standard one
X if v1.valid = '0' then
X -- initialization record - ``smaller'' than all standard
records
X return true;
X else
X -- end record - ``bigger'' than all standard records
X return false;
X end if;
X elsif (v1.init = '0') and (v2.init = '1') then
X -- v2 is the special record, v1 is the standard one
X if (v2.valid = '0') then
X -- v2 is the initialization record - it is ``smaller'' than
standard record v1
X return false;
X else
X -- v2 is the end record - it is ``bigger'' than standard
record v1
X return true;
X end if;
X elsif (v1.init = '1') and (v2.init = '1') then
X -- both v1 and v2 are special records
X if (v1.valid = '0') and (v2.valid = '1') then
X -- v1 - initial record, v2 - end record
X return true;
X else
X -- v1 is end record, so it is ``bigger'' or ``equal'' to
other records
X return false;
X end if;
X elsif (v1.init = '0') and (v2.init = '0') then
X -- We compare standard words
X -- We must consider the fact, that in longer sequences of data
records
X -- the sort keys may wrap around
X -- therefore we perform subtraction modulo
X -- 2**DATA_REC_SORT_KEY_WIDTH and check the MSB
X dcomp := v1.d_key-v2.d_key;
X if dcomp(DATA_REC_SORT_KEY_WIDTH-1) = '1' then
X --if signed(v1.d_key - v2.d_key)<0 then -- old implementation
X return true;
X elsif v2.d_key = v1.d_key then
X if v2.valid = '1' then
X return true;
X else
X -- Empty data records should wait
X return false;
X end if;
X else
X return false;
X end if;
X else
X assert false report "Wrong records in sort_cmp_lt" severity
error;
X return false;
X end if;
X return false; -- should never happen
X end sort_cmp_lt;
X
X
X procedure wrstlv (
X rline : inout line;
X constant vect : std_logic_vector) is
X begin -- stlv2str
X for i in vect'left downto vect'right loop
X case vect(i) is
X when 'U' => write(rline, string'("u"));
X when 'Z' => write(rline, string'("z"));
X when 'X' => write(rline, string'("x"));
X when 'L' => write(rline, string'("L"));
X when 'H' => write(rline, string'("H"));
X when '1' => write(rline, string'("1"));
X when '0' => write(rline, string'("0"));
X when others => write(rline, string'("?"));
X end case;
X end loop; -- i
X end wrstlv;
X
end sorter_pkg;
X
SHAR_EOF
(set 20 11 07 11 17 02 09 'src/sorter_pkg.vhd'
eval "${shar_touch}") && \
chmod 0644 'src/sorter_pkg.vhd'
if test $? -ne 0
then ${echo} "restore of src/sorter_pkg.vhd failed"
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'src/sorter_pkg.vhd':
'MD5 check failed'
) << \SHAR_EOF
3a1798b1a9cf896c1e8e61dd97317819 src/sorter_pkg.vhd
SHAR_EOF
else
test `LC_ALL=C wc -c < 'src/sorter_pkg.vhd'` -ne 7572 && \
${echo} "restoration warning: size of 'src/sorter_pkg.vhd' is not
7572"
fi
fi
# ============= src/sorter_sys_tb.vhd ==============
if test -n "${keep_file}" && test -f 'src/sorter_sys_tb.vhd'
then
${echo} "x - SKIPPING src/sorter_sys_tb.vhd (file already exists)"
else
${echo} "x - extracting src/sorter_sys_tb.vhd (text)"
sed 's/^X//' << 'SHAR_EOF' > 'src/sorter_sys_tb.vhd' &&
-------------------------------------------------------------------------------
-- Title : Testbench for design "heap-sorter"
-- Project : heap-sorter
-------------------------------------------------------------------------------
-- File : sorter_sys_tb.vhd
-- Author : Wojciech M. Zabolotny <wz...@ise.pw.edu.pl>
-- Company :
-- Created : 2010-05-14
-- Last update: 2011-07-06
-- Platform :
-- Standard : VHDL'93
-------------------------------------------------------------------------------
-- Description:
-------------------------------------------------------------------------------
-- Copyright (c) 2010 Wojciech M. Zabolotny
-- This file is published under the BSD license, so you can freely
adapt
-- it for your own purposes.
-- Additionally this design has been described in my article
-- "Dual port memory based heapsort implementation for FPGA"
-- submitted to Proceedings of SPIE in 2011
-- I'll provide detailed bibliographic information after this paper
-- is printed.
-- I'd be glad if you cite this article when you publish something
based
-- on my design.
-------------------------------------------------------------------------------
-- Revisions :
-- Date Version Author Description
-- 2010-05-14 1.0 wzab Created
-------------------------------------------------------------------------------
X
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use ieee.std_logic_textio.all;
use std.textio.all;
library work;
use work.sys_config.all;
use work.sorter_pkg.all;
X
X
-------------------------------------------------------------------------------
X
entity sorter_sys_tb is
X
end entity sorter_sys_tb;
X
-------------------------------------------------------------------------------
X
architecture sort_tb_beh of sorter_sys_tb is
X
X constant NLEVELS : integer := SYS_NLEVELS;
X -- component ports
X signal din : T_DATA_REC := DATA_REC_INIT_DATA;
X signal dout : T_DATA_REC;
X signal we : std_logic := '0';
X signal dav : std_logic := '0';
X signal rst_n : std_logic := '0';
X signal ready : std_logic := '0';
X
X component sorter_sys
X generic (
X NADDRBITS : integer);
X port (
X din : in T_DATA_REC;
X we : in std_logic;
X dout : out T_DATA_REC;
X dav : out std_logic;
X clk : in std_logic;
X rst_n : in std_logic;
X ready : out std_logic);
X end component;
X -- clock
X signal Clk : std_logic := '1';
X
X signal end_sim : boolean := false;
X signal div : integer range 0 to 8 := 0;
X
begin -- architecture sort_tb_beh
X
X -- component instantiation
X DUT : entity work.sorter_sys
X generic map (
X NLEVELS => NLEVELS)
X port map (
X din => din,
X we => we,
X dout => dout,
X dav => dav,
X clk => clk,
X rst_n => rst_n,
X ready => ready);
X
X -- clock generation
X Clk <= not Clk after 10 ns when end_sim = false else '0';
X
X -- waveform generation
X WaveGen_Proc : process
X file events_in : text open read_mode is "events.in";
X variable input_line : line;
X file events_out : text open write_mode is "events.out";
X variable output_line : line;
X variable rec : T_DATA_REC;
X variable skey : std_logic_vector(DATA_REC_SORT_KEY_WIDTH-1
downto 0);
X variable spayload : std_logic_vector(DATA_REC_PAYLOAD_WIDTH-1
downto 0);
X begin
X -- insert signal assignments here
X
X wait until Clk = '1';
X wait for 31 ns;
X rst_n <= '1';
X wait until ready = '1';
X loop
X wait until Clk = '0';
X wait until Clk = '1';
X we <= '0';
X if div = 3 then
X div <= 0;
X exit when endfile(events_in);
X readline(events_in, input_line);
X read(input_line, rec.init);
X read(input_line, rec.valid);
X read(input_line, skey);
X read(input_line, spayload);
X rec.d_key := unsigned(skey);
X rec.d_payload := spayload;
X din <= rec;
X we <= '1';
X else
X div <= div+1;
X end if;
X if dav = '1' then
X -- Process read event
X rec := dout;
X write(output_line, rec.init);
X write(output_line, rec.valid);
X write(output_line,string'(" "));
X write(output_line, std_logic_vector(rec.d_key));
X write(output_line,string'(" "));
X write(output_line, std_logic_vector(rec.d_payload));
X writeline(events_out, output_line);
X end if;
X end loop;
X end_sim <= true;
X rec.valid := '0';
X din <= rec;
X wait;
X end process WaveGen_Proc;
X
X
X
end architecture sort_tb_beh;
X
-------------------------------------------------------------------------------
X
configuration sorter_sys_tb_sort_tb_beh_cfg of sorter_sys_tb is
X for sort_tb_beh
X end for;
end sorter_sys_tb_sort_tb_beh_cfg;
X
-------------------------------------------------------------------------------
SHAR_EOF
(set 20 11 07 11 15 09 54 'src/sorter_sys_tb.vhd'
eval "${shar_touch}") && \
chmod 0644 'src/sorter_sys_tb.vhd'
if test $? -ne 0
then ${echo} "restore of src/sorter_sys_tb.vhd failed"
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'src/
sorter_sys_tb.vhd': 'MD5 check failed'
) << \SHAR_EOF
16c8f8da7c07245ebe34bacff481940d src/sorter_sys_tb.vhd
SHAR_EOF
else
test `LC_ALL=C wc -c < 'src/sorter_sys_tb.vhd'` -ne 4887 && \
${echo} "restoration warning: size of 'src/sorter_sys_tb.vhd' is
not 4887"
fi
fi
# ============= comp/dummy.txt ==============
if test ! -d 'comp'; then
mkdir 'comp'
if test $? -eq 0
then ${echo} "x - created directory comp."
else ${echo} "x - failed to create directory comp."
exit 1
fi
fi
if test -n "${keep_file}" && test -f 'comp/dummy.txt'
then
${echo} "x - SKIPPING comp/dummy.txt (file already exists)"
else
${echo} "x - extracting comp/dummy.txt (text)"
sed 's/^X//' << 'SHAR_EOF' > 'comp/dummy.txt' &&
This file is here to ensure creation of comp directory
SHAR_EOF
(set 20 11 07 11 17 15 28 'comp/dummy.txt'
eval "${shar_touch}") && \
chmod 0644 'comp/dummy.txt'
if test $? -ne 0
then ${echo} "restore of comp/dummy.txt failed"
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'comp/dummy.txt': 'MD5
check failed'
) << \SHAR_EOF
3c6900b22b89496186124fa561a062db comp/dummy.txt
SHAR_EOF
else
test `LC_ALL=C wc -c < 'comp/dummy.txt'` -ne 54 && \
${echo} "restoration warning: size of 'comp/dummy.txt' is not 54"
fi
fi
# ============= makefile ==============
if test -n "${keep_file}" && test -f 'makefile'
then
${echo} "x - SKIPPING makefile (file already exists)"
else
${echo} "x - extracting makefile (text)"
sed 's/^X//' << 'SHAR_EOF' > 'makefile' &&
VHDLS = \
X src/sys_config.vhd \
X src/sorter_pkg.vhd \
X src/dpram4.vhd \
X src/sort_dpram.vhd \
X src/sorter_ctrl.vhd \
X src/sorter_sys.vhd \
X src/sorter_sys_tb.vhd \
X
#STD=standard
STD=synopsys
VSTD=93c
ENTITY=sorter_sys_tb
RUN_OPTIONS=
all: events.in events.out test
events.in: sort_test_gen.py
X ./sort_test_gen.py
reader: ${ENTITY} ${ENTITY}.ghw
X gtkwave ${ENTITY}.ghw ${ENTITY}.sav
${ENTITY}: ${VHDLS}
# vhdlp -work fmf fmf/*.vhd
X ghdl -a --workdir=comp --std=${VSTD} --ieee=${STD} ${VHDLS}
X ghdl -e --workdir=comp --std=${VSTD} -fexplicit --ieee=${STD} $
{ENTITY}
events.out: ${ENTITY} events.in
# ./${ENTITY} --wave=${ENTITY}.ghw ${RUN_OPTIONS} --stop-time=50000ns
2>&1 > res.txt
X ./${ENTITY} ${RUN_OPTIONS} 2>&1 > res.txt
test:
X ./sort_test_check.py
clean:
X rm -f comp/* *.o *.vcd *.ghw events* ${ENTITY}
X
SHAR_EOF
(set 20 11 07 11 15 09 55 'makefile'
eval "${shar_touch}") && \
chmod 0644 'makefile'
if test $? -ne 0
then ${echo} "restore of makefile failed"
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'makefile': 'MD5 check
failed'
) << \SHAR_EOF
04025b13dfe83b0f4b58e9c1112cdf76 makefile
SHAR_EOF
else
test `LC_ALL=C wc -c < 'makefile'` -ne 823 && \
${echo} "restoration warning: size of 'makefile' is not 823"
fi
fi
# ============= sort_test_gen.py ==============
if test -n "${keep_file}" && test -f 'sort_test_gen.py'
then
${echo} "x - SKIPPING sort_test_gen.py (file already exists)"
else
${echo} "x - extracting sort_test_gen.py (text)"
sed 's/^X//' << 'SHAR_EOF' > 'sort_test_gen.py' &&
#!/usr/bin/python
#
# This Python script generates the input patterns for the sorter
# It also generates the sys_config.vhd file with constants
# describing structure of data records
#
# You can customize constants below
key_width = 8 # Width of the key part of the record
pay_width = 4 # Width of the payload part of the record
max_dist = 63 # Maximum distance between unsorted records
seq_len = 2000 # Length of the generated sequence
sort_debug = "true" #uncomment this, or the next line
sort_debug = "false" #alwayse set sort_debug to false for synthesis!
#
# The algorithm is very simple - we just generate the sequence
# of records with continuously increasing key numbers
# Then we increase the key number in each record by the random
# number, taken from the range: [0,max_dist]
import math
import sys
# calculate necessary amount of levels in the sorter
sys_nlevels=1
nrec=4
while nrec<max_dist+1:
X sys_nlevels+=1
X nrec*=2
# Sorter capacity and sorter latency is equal to nrec-1
latency=nrec-1
# When checking if the sorter key width is sufficient, we must
# consider, that in the worst key we may need to compare
# samples with keys differing by latency+max_dist
#
# Check if the settings are correct
if max_dist+latency > ((1<<(key_width-1))-1):
X print "Too high maximum distance between unsorted records"
X print "for defined width of the sort key. Please increase"
X print "the key_width value in the sort_test_gen.py file!"
X sys.exit(1)
# Then we prepare the VHDL file with system configuration
sc=open('src/sys_config.vhd','w')
l="library ieee;\n"
l+="use ieee.std_logic_1164.all;\n"
l+="library work;\n"
l+="package sys_config is\n"
l+=" constant SORT_DEBUG : boolean :="+sort_debug+";\n"
l+=" constant SYS_NLEVELS : integer :="+str(sys_nlevels)
+";\n"
l+=" constant DATA_REC_SORT_KEY_WIDTH : integer :="+str(key_width)+";
\n"
l+=" constant DATA_REC_PAYLOAD_WIDTH : integer :="+str(pay_width)+";
\n"
l+="end sys_config;\n"
sc.write(l)
sc.close()
# Generate the input patterns
fo=open('events.in','w')
t=range(1,seq_len+1)
import random
r=random.Random()
r.seed()
t2=[i+r.randint(0,max_dist) for i in t]
# Now let's prepare the input events:
key_format="{0:0"+str(key_width)+"b}"
pay_format="{0:0"+str(pay_width)+"b}"
for i in t2:
X j = i & ((1<<key_width)-1) #Truncate the key to the set width
X l = "01 " + key_format.format(j) + " " + pay_format.format(0)
X fo.write(l+"\n")
# Now let's print necessary number of end records
for i in range(0,nrec):
X l = "11 " + key_format.format(0) + " " + pay_format.format(0)
X fo.write(l+"\n")
fo.close()
SHAR_EOF
(set 20 11 07 11 16 40 39 'sort_test_gen.py'
eval "${shar_touch}") && \
chmod 0755 'sort_test_gen.py'
if test $? -ne 0
then ${echo} "restore of sort_test_gen.py failed"
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'sort_test_gen.py':
'MD5 check failed'
) << \SHAR_EOF
eaa2d03ceb6d56c8c04024e2af86db2c sort_test_gen.py
SHAR_EOF
else
test `LC_ALL=C wc -c < 'sort_test_gen.py'` -ne 2596 && \
${echo} "restoration warning: size of 'sort_test_gen.py' is not
2596"
fi
fi
# ============= sort_test_check.py ==============
if test -n "${keep_file}" && test -f 'sort_test_check.py'
then
${echo} "x - SKIPPING sort_test_check.py (file already exists)"
else
${echo} "x - extracting sort_test_check.py (text)"
sed 's/^X//' << 'SHAR_EOF' > 'sort_test_check.py' &&
#!/usr/bin/python
# This Python script checks if the records were sorted
# correctly...
import sys
# We read the input records and store them in one vector
fi=open("events.in","r")
ri=fi.read().split("\n")
ri=[i.split(" ") for i in ri]
# Leave only valid records
ri=[i for i in ri if len(i)==3 and i[0]=="01"]
# We read the output vectors and store them in a second vector
fo=open("events.out","r")
ro=fo.read().split("\n")
ro=[i.split(" ") for i in ro ]
# Leave only valid records
ro=[i for i in ro if len(i)==3 and i[0]=="01"]
# We check if the output vectors are correctly sorted
for i in range(1,len(ro)):
X # Theoretically we could simply check the condition:
X # int(ro[i-1][1],2) <= int(ro[i][1],2)
X # However for longer sequences we may need to
X # consider the fact that sort keys (time stamps)
X # will wrap around.
X # Therefore we need to perform slightly more
X # complicated test - if we use N bits to store
X # the sort key, then we need to subtract keys modulo
X # 2**N and if the difference is in range (0,2**(N-1)]
X # we consider the difference positive, while in range
X # (2**(N-1),(2**N)-1) we consider it negative.
X k1 = ro[i-1][1]
X k2 = ro[i][1]
X dlim = 1<<len(k1)
X diff=(int(k2,2)-int(k1,2)) % dlim
X if diff > dlim/2:
X print "Records unsorted!\n"
X print str(i-1)+": "+str(ro[i-1])
X print str(i)+": "+str(ro[i])
X sys.exit(1)
# We check if all input vectors were transferred to the output
# Now we only check size of vectors
if len(ro) != len(ri):
X print "Not all records transferred!\n"
X sys.exit(1)
print "Test passed!\n"
sys.exit(0)
X
SHAR_EOF
(set 20 11 07 11 15 09 55 'sort_test_check.py'
eval "${shar_touch}") && \
chmod 0755 'sort_test_check.py'
if test $? -ne 0
then ${echo} "restore of sort_test_check.py failed"
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'sort_test_check.py':
'MD5 check failed'
) << \SHAR_EOF
5e6c080fdedc07d97b2db57d25d40755 sort_test_check.py
SHAR_EOF
else
test `LC_ALL=C wc -c < 'sort_test_check.py'` -ne 1591 && \
${echo} "restoration warning: size of 'sort_test_check.py' is not
1591"
fi
fi
if rm -fr ${lock_dir}
then ${echo} "x - removed lock directory ${lock_dir}."
else ${echo} "x - failed to remove lock directory ${lock_dir}."
exit 1
fi
exit 0

wzab

unread,
Jul 11, 2011, 2:18:49 PM7/11/11
to
Archive-name: fpga-heasort
Submitted-by: Wojciech M. Zabolotny wzab<at>ise.pw.edu.pl

Unfortunately the previous post was corrupted by line wraps.
I have no possibility to send it via NNTP server allowing to send
posts
with long lines. Therefore I resend the archive in gzipped form.

lock_dir=_sh13429
# Made on 2011-07-11 20:12 CEST by <wzab@wzlaphp>.


# Source directory was `/tmp/sort'.
#
# Existing files will *not* be overwritten, unless `-c' is specified.
#
# This shar contains:
# length mode name
# ------ ---------- ------------------------------------------

# 54 -rw-r--r-- comp/dummy.txt
# 823 -rw-r--r-- makefile

# 1591 -rwxr-xr-x sort_test_check.py
# 2596 -rwxr-xr-x sort_test_gen.py


# 12022 -rw-r--r-- src/sorter_ctrl.vhd
# 2756 -rw-r--r-- src/dpram4.vhd
# 299 -rw-r--r-- src/sys_config.vhd
# 10019 -rw-r--r-- src/sorter_sys.vhd
# 1654 -rw-r--r-- src/dpram_inf.vhd
# 5494 -rw-r--r-- src/sort_dpram.vhd
# 7572 -rw-r--r-- src/sorter_pkg.vhd
# 4887 -rw-r--r-- src/sorter_sys_tb.vhd
#

# ============= comp/dummy.txt ==============
if test ! -d 'comp'; then
mkdir 'comp'
if test $? -eq 0
then ${echo} "x - created directory comp."
else ${echo} "x - failed to create directory comp."
exit 1
fi
fi
if test -n "${keep_file}" && test -f 'comp/dummy.txt'
then
${echo} "x - SKIPPING comp/dummy.txt (file already exists)"
else

${echo} "x - extracting comp/dummy.txt (gzipped)"
sed 's/^X//' << 'SHAR_EOF' | uudecode &&
SHAR_EOF
${echo} "gunzipping file comp/dummy.txt" &&

gzip -d < ${lock_dir}/gzi > 'comp/dummy.txt' && \


(set 20 11 07 11 17 15 28 'comp/dummy.txt'
eval "${shar_touch}") && \
chmod 0644 'comp/dummy.txt'
if test $? -ne 0
then ${echo} "restore of comp/dummy.txt failed"
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'comp/dummy.txt': 'MD5
check failed'
) << \SHAR_EOF
3c6900b22b89496186124fa561a062db comp/dummy.txt
SHAR_EOF
else
test `LC_ALL=C wc -c < 'comp/dummy.txt'` -ne 54 && \
${echo} "restoration warning: size of 'comp/dummy.txt' is not 54"
fi
fi
# ============= makefile ==============
if test -n "${keep_file}" && test -f 'makefile'
then
${echo} "x - SKIPPING makefile (file already exists)"
else

${echo} "x - extracting makefile (gzipped)"
sed 's/^X//' << 'SHAR_EOF' | uudecode &&
SHAR_EOF
${echo} "gunzipping file makefile" &&

gzip -d < ${lock_dir}/gzi > 'makefile' && \


(set 20 11 07 11 15 09 55 'makefile'
eval "${shar_touch}") && \
chmod 0644 'makefile'
if test $? -ne 0
then ${echo} "restore of makefile failed"
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'makefile': 'MD5 check
failed'
) << \SHAR_EOF
04025b13dfe83b0f4b58e9c1112cdf76 makefile
SHAR_EOF
else
test `LC_ALL=C wc -c < 'makefile'` -ne 823 && \
${echo} "restoration warning: size of 'makefile' is not 823"
fi
fi

# ============= sort_test_check.py ==============
if test -n "${keep_file}" && test -f 'sort_test_check.py'
then
${echo} "x - SKIPPING sort_test_check.py (file already exists)"
else

${echo} "x - extracting sort_test_check.py (gzipped)"
sed 's/^X//' << 'SHAR_EOF' | uudecode &&
SHAR_EOF
${echo} "gunzipping file sort_test_check.py" &&

gzip -d < ${lock_dir}/gzi > 'sort_test_check.py' && \


(set 20 11 07 11 15 09 55 'sort_test_check.py'
eval "${shar_touch}") && \
chmod 0755 'sort_test_check.py'
if test $? -ne 0
then ${echo} "restore of sort_test_check.py failed"
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'sort_test_check.py':
'MD5 check failed'
) << \SHAR_EOF
5e6c080fdedc07d97b2db57d25d40755 sort_test_check.py
SHAR_EOF
else
test `LC_ALL=C wc -c < 'sort_test_check.py'` -ne 1591 && \
${echo} "restoration warning: size of 'sort_test_check.py' is not
1591"
fi
fi

# ============= sort_test_gen.py ==============
if test -n "${keep_file}" && test -f 'sort_test_gen.py'
then
${echo} "x - SKIPPING sort_test_gen.py (file already exists)"
else

${echo} "x - extracting sort_test_gen.py (gzipped)"
sed 's/^X//' << 'SHAR_EOF' | uudecode &&
SHAR_EOF
${echo} "gunzipping file sort_test_gen.py" &&

gzip -d < ${lock_dir}/gzi > 'sort_test_gen.py' && \


(set 20 11 07 11 16 40 39 'sort_test_gen.py'
eval "${shar_touch}") && \
chmod 0755 'sort_test_gen.py'
if test $? -ne 0
then ${echo} "restore of sort_test_gen.py failed"
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'sort_test_gen.py':
'MD5 check failed'
) << \SHAR_EOF
eaa2d03ceb6d56c8c04024e2af86db2c sort_test_gen.py
SHAR_EOF
else
test `LC_ALL=C wc -c < 'sort_test_gen.py'` -ne 2596 && \
${echo} "restoration warning: size of 'sort_test_gen.py' is not
2596"
fi
fi

# ============= src/sorter_ctrl.vhd ==============
if test ! -d 'src'; then
mkdir 'src'
if test $? -eq 0
then ${echo} "x - created directory src."
else ${echo} "x - failed to create directory src."
exit 1
fi
fi
if test -n "${keep_file}" && test -f 'src/sorter_ctrl.vhd'
then
${echo} "x - SKIPPING src/sorter_ctrl.vhd (file already exists)"
else

${echo} "x - extracting src/sorter_ctrl.vhd (gzipped)"
sed 's/^X//' << 'SHAR_EOF' | uudecode &&
SHAR_EOF
${echo} "gunzipping file src/sorter_ctrl.vhd" &&

gzip -d < ${lock_dir}/gzi > 'src/sorter_ctrl.vhd' && \

${echo} "x - extracting src/dpram4.vhd (gzipped)"
sed 's/^X//' << 'SHAR_EOF' | uudecode &&
SHAR_EOF
${echo} "gunzipping file src/dpram4.vhd" &&

gzip -d < ${lock_dir}/gzi > 'src/dpram4.vhd' && \


(set 20 11 07 11 15 09 54 'src/dpram4.vhd'
eval "${shar_touch}") && \
chmod 0644 'src/dpram4.vhd'
if test $? -ne 0
then ${echo} "restore of src/dpram4.vhd failed"
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'src/dpram4.vhd': 'MD5
check failed'
) << \SHAR_EOF
bd39e4a2778d63d514531d897aec1ab7 src/dpram4.vhd
SHAR_EOF
else
test `LC_ALL=C wc -c < 'src/dpram4.vhd'` -ne 2756 && \
${echo} "restoration warning: size of 'src/dpram4.vhd' is not 2756"
fi
fi
# ============= src/sys_config.vhd ==============
if test -n "${keep_file}" && test -f 'src/sys_config.vhd'
then
${echo} "x - SKIPPING src/sys_config.vhd (file already exists)"
else

${echo} "x - extracting src/sys_config.vhd (gzipped)"
sed 's/^X//' << 'SHAR_EOF' | uudecode &&
SHAR_EOF
${echo} "gunzipping file src/sys_config.vhd" &&

gzip -d < ${lock_dir}/gzi > 'src/sys_config.vhd' && \


(set 20 11 07 11 16 48 06 'src/sys_config.vhd'
eval "${shar_touch}") && \
chmod 0644 'src/sys_config.vhd'
if test $? -ne 0
then ${echo} "restore of src/sys_config.vhd failed"
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'src/sys_config.vhd':
'MD5 check failed'
) << \SHAR_EOF
9f0d63702682ff9afa28a73e295973a5 src/sys_config.vhd
SHAR_EOF
else
test `LC_ALL=C wc -c < 'src/sys_config.vhd'` -ne 299 && \
${echo} "restoration warning: size of 'src/sys_config.vhd' is not
299"
fi
fi
# ============= src/sorter_sys.vhd ==============
if test -n "${keep_file}" && test -f 'src/sorter_sys.vhd'
then
${echo} "x - SKIPPING src/sorter_sys.vhd (file already exists)"
else

${echo} "x - extracting src/sorter_sys.vhd (gzipped)"
sed 's/^X//' << 'SHAR_EOF' | uudecode &&
SHAR_EOF
${echo} "gunzipping file src/sorter_sys.vhd" &&

gzip -d < ${lock_dir}/gzi > 'src/sorter_sys.vhd' && \


(set 20 11 07 11 16 31 04 'src/sorter_sys.vhd'
eval "${shar_touch}") && \
chmod 0644 'src/sorter_sys.vhd'
if test $? -ne 0
then ${echo} "restore of src/sorter_sys.vhd failed"
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'src/sorter_sys.vhd':
'MD5 check failed'
) << \SHAR_EOF
433e4f8f534e7dac54bb53beb7ec1d21 src/sorter_sys.vhd
SHAR_EOF
else
test `LC_ALL=C wc -c < 'src/sorter_sys.vhd'` -ne 10019 && \
${echo} "restoration warning: size of 'src/sorter_sys.vhd' is not
10019"
fi
fi
# ============= src/dpram_inf.vhd ==============
if test -n "${keep_file}" && test -f 'src/dpram_inf.vhd'
then
${echo} "x - SKIPPING src/dpram_inf.vhd (file already exists)"
else

${echo} "x - extracting src/dpram_inf.vhd (gzipped)"
sed 's/^X//' << 'SHAR_EOF' | uudecode &&
SHAR_EOF
${echo} "gunzipping file src/dpram_inf.vhd" &&

gzip -d < ${lock_dir}/gzi > 'src/dpram_inf.vhd' && \


(set 20 11 07 11 16 41 27 'src/dpram_inf.vhd'
eval "${shar_touch}") && \
chmod 0644 'src/dpram_inf.vhd'
if test $? -ne 0
then ${echo} "restore of src/dpram_inf.vhd failed"
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'src/dpram_inf.vhd':
'MD5 check failed'
) << \SHAR_EOF
245e6cb633a8335f0b70149795af4997 src/dpram_inf.vhd
SHAR_EOF
else
test `LC_ALL=C wc -c < 'src/dpram_inf.vhd'` -ne 1654 && \
${echo} "restoration warning: size of 'src/dpram_inf.vhd' is not
1654"
fi
fi
# ============= src/sort_dpram.vhd ==============
if test -n "${keep_file}" && test -f 'src/sort_dpram.vhd'
then
${echo} "x - SKIPPING src/sort_dpram.vhd (file already exists)"
else

${echo} "x - extracting src/sort_dpram.vhd (gzipped)"
sed 's/^X//' << 'SHAR_EOF' | uudecode &&
SHAR_EOF
${echo} "gunzipping file src/sort_dpram.vhd" &&

gzip -d < ${lock_dir}/gzi > 'src/sort_dpram.vhd' && \


(set 20 11 07 11 15 09 54 'src/sort_dpram.vhd'
eval "${shar_touch}") && \
chmod 0644 'src/sort_dpram.vhd'
if test $? -ne 0
then ${echo} "restore of src/sort_dpram.vhd failed"
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'src/sort_dpram.vhd':
'MD5 check failed'
) << \SHAR_EOF
c41b3c40342c871ebed4a25a9fb78f33 src/sort_dpram.vhd
SHAR_EOF
else
test `LC_ALL=C wc -c < 'src/sort_dpram.vhd'` -ne 5494 && \
${echo} "restoration warning: size of 'src/sort_dpram.vhd' is not
5494"
fi
fi
# ============= src/sorter_pkg.vhd ==============
if test -n "${keep_file}" && test -f 'src/sorter_pkg.vhd'
then
${echo} "x - SKIPPING src/sorter_pkg.vhd (file already exists)"
else

${echo} "x - extracting src/sorter_pkg.vhd (gzipped)"
sed 's/^X//' << 'SHAR_EOF' | uudecode &&
SHAR_EOF
${echo} "gunzipping file src/sorter_pkg.vhd" &&

gzip -d < ${lock_dir}/gzi > 'src/sorter_pkg.vhd' && \


(set 20 11 07 11 17 02 09 'src/sorter_pkg.vhd'
eval "${shar_touch}") && \
chmod 0644 'src/sorter_pkg.vhd'
if test $? -ne 0
then ${echo} "restore of src/sorter_pkg.vhd failed"
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'src/sorter_pkg.vhd':
'MD5 check failed'
) << \SHAR_EOF
3a1798b1a9cf896c1e8e61dd97317819 src/sorter_pkg.vhd
SHAR_EOF
else
test `LC_ALL=C wc -c < 'src/sorter_pkg.vhd'` -ne 7572 && \
${echo} "restoration warning: size of 'src/sorter_pkg.vhd' is not
7572"
fi
fi
# ============= src/sorter_sys_tb.vhd ==============
if test -n "${keep_file}" && test -f 'src/sorter_sys_tb.vhd'
then
${echo} "x - SKIPPING src/sorter_sys_tb.vhd (file already exists)"
else

${echo} "x - extracting src/sorter_sys_tb.vhd (gzipped)"
sed 's/^X//' << 'SHAR_EOF' | uudecode &&
SHAR_EOF
${echo} "gunzipping file src/sorter_sys_tb.vhd" &&

gzip -d < ${lock_dir}/gzi > 'src/sorter_sys_tb.vhd' && \


(set 20 11 07 11 15 09 54 'src/sorter_sys_tb.vhd'
eval "${shar_touch}") && \
chmod 0644 'src/sorter_sys_tb.vhd'
if test $? -ne 0
then ${echo} "restore of src/sorter_sys_tb.vhd failed"
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'src/
sorter_sys_tb.vhd': 'MD5 check failed'
) << \SHAR_EOF
16c8f8da7c07245ebe34bacff481940d src/sorter_sys_tb.vhd
SHAR_EOF
else
test `LC_ALL=C wc -c < 'src/sorter_sys_tb.vhd'` -ne 4887 && \
${echo} "restoration warning: size of 'src/sorter_sys_tb.vhd' is
not 4887"
fi
fi

gzi
gzi
gzi
gzi
gzi
gzi
gzi
gzi
gzi
gzi
gzi
gzi

wzab

unread,
Jul 11, 2011, 2:35:06 PM7/11/11
to
Archive-name: fpga-heasort
Submitted-by: Wojciech M. Zabolotny wzab<at>ise.pw.edu.pl

I was not able to send correctly the shar archive.
Therefore finally I send the uuencoded tar.bz2 archive:

sorter.tar.bz2

wzab

unread,
Jul 17, 2011, 5:43:16 PM7/17/11
to
Archive-name: fpga-heasort
Submitted-by: Wojciech M. Zabolotny wzab<at>ise.pw.edu.pl

I don't know why all my attempts to send the shar archive failed.
I try to send it once again, using another server, and another client program...

lock_dir=_sh15285
# Made on 2011-07-17 23:34 CEST by <wzab@wzab>.
# Source directory was `/tmp/sorter'.

${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'src/sorter_sys_tb.vhd': 'MD5 check failed'

l+=" constant SYS_NLEVELS : integer :="+str(sys_nlevels)+";\n"

Wojtek Zabołotny

unread,
Oct 14, 2011, 9:22:12 AM10/14/11
to
Hi,

The article describing my "Synthesizable heap-sorter for FPGA"
(available at http://www.ise.pw.edu.pl/~wzab/fpga_heapsort)
is just published and available at http://dx.doi.org/10.1117/12.905281
If you publish something based on my sources, please cite the above article.

--
Regards, Wojtek

Wojtek Zabołotny

unread,
Oct 14, 2011, 9:55:45 AM10/14/11
to
Archive-name: fpga-heasort
Submitted-by: Wojciech M. Zabolotny wzab<at>ise.pw.edu.pl

This archive contains the source code of the heap-sorter


able to sort one data record every two clock pulses.

The detailed description of the implementation is provided in

the paper:
Wojciech M. Zabolotny, "Dual port memory based Heapsort implementation
for FPGA", Proc. SPIE 8008, 80080E (2011); doi:10.1117/12.905281

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 above paper, when you publish
something based on my sources.

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 M. Zabolotny
wzab<at>ise.pw.edu.pl

#!/bin/sh
# This is a shell archive (produced by GNU sharutils 4.11).
# To extract the files from this archive, save it to some FILE, remove
# everything before the `#!/bin/sh' line above, then type `sh FILE'.
#

lock_dir=_sh10148
# Made on 2011-10-14 17:16 CEST by <wzab@WZLap>.
# Source directory was `/tmp/fpga'.


#
# Existing files will *not* be overwritten, unless `-c' is specified.
#
# This shar contains:
# length mode name
# ------ ---------- ------------------------------------------

# 54 -rw-r--r-- comp/dummy.txt
# 823 -rw-r--r-- makefile

# 1591 -rwxr-xr-x sort_test_check.py
# 2596 -rwxr-xr-x sort_test_gen.py
# 299 -rw-r--r-- src/sys_config.vhd
# 11983 -rw-r--r-- src/sorter_ctrl.vhd
# 10041 -rw-r--r-- src/sorter_sys.vhd
# 7533 -rw-r--r-- src/sorter_pkg.vhd
# 4848 -rw-r--r-- src/sorter_sys_tb.vhd
# 5455 -rw-r--r-- src/sort_dpram.vhd
# 1654 -rw-r--r-- src/dpram_inf.vhd
# 2756 -rw-r--r-- src/dpram4.vhd

# ============= src/sys_config.vhd ==============


if test ! -d 'src'; then
mkdir 'src'
if test $? -eq 0
then ${echo} "x - created directory src."
else ${echo} "x - failed to create directory src."
exit 1
fi
fi

-- Wojciech M. Zabolotny, "Dual port memory based Heapsort implementation
-- for FPGA", Proc. SPIE 8008, 80080E (2011); doi:10.1117/12.905281

(set 20 11 10 14 17 12 49 'src/sorter_ctrl.vhd'


eval "${shar_touch}") && \
chmod 0644 'src/sorter_ctrl.vhd'
if test $? -ne 0
then ${echo} "restore of src/sorter_ctrl.vhd failed"
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'src/sorter_ctrl.vhd': 'MD5 check failed'
) << \SHAR_EOF

69eea9fbe894706ab65eb748fcc4b818 src/sorter_ctrl.vhd
SHAR_EOF
else
test `LC_ALL=C wc -c < 'src/sorter_ctrl.vhd'` -ne 11983 && \
${echo} "restoration warning: size of 'src/sorter_ctrl.vhd' is not 11983"

-- Additionally this design has been described in my article:

-- Wojciech M. Zabolotny, "Dual port memory based Heapsort implementation
-- for FPGA", Proc. SPIE 8008, 80080E (2011); doi:10.1117/12.905281

(set 20 11 10 14 17 13 08 'src/sorter_sys.vhd'


eval "${shar_touch}") && \
chmod 0644 'src/sorter_sys.vhd'
if test $? -ne 0
then ${echo} "restore of src/sorter_sys.vhd failed"
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'src/sorter_sys.vhd': 'MD5 check failed'
) << \SHAR_EOF

023824fd6d910b29cd629f1f9b32213c src/sorter_sys.vhd
SHAR_EOF
else
test `LC_ALL=C wc -c < 'src/sorter_sys.vhd'` -ne 10041 && \
${echo} "restoration warning: size of 'src/sorter_sys.vhd' is not 10041"

-- Wojciech M. Zabolotny, "Dual port memory based Heapsort implementation
-- for FPGA", Proc. SPIE 8008, 80080E (2011); doi:10.1117/12.905281

(set 20 11 10 14 17 12 55 'src/sorter_pkg.vhd'


eval "${shar_touch}") && \
chmod 0644 'src/sorter_pkg.vhd'
if test $? -ne 0
then ${echo} "restore of src/sorter_pkg.vhd failed"
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'src/sorter_pkg.vhd': 'MD5 check failed'
) << \SHAR_EOF

245a4327b8627a138fd1e96a94a3ab6f src/sorter_pkg.vhd
SHAR_EOF
else
test `LC_ALL=C wc -c < 'src/sorter_pkg.vhd'` -ne 7533 && \
${echo} "restoration warning: size of 'src/sorter_pkg.vhd' is not 7533"

-- Wojciech M. Zabolotny, "Dual port memory based Heapsort implementation
-- for FPGA", Proc. SPIE 8008, 80080E (2011); doi:10.1117/12.905281

(set 20 11 10 14 17 13 02 'src/sorter_sys_tb.vhd'


eval "${shar_touch}") && \
chmod 0644 'src/sorter_sys_tb.vhd'
if test $? -ne 0
then ${echo} "restore of src/sorter_sys_tb.vhd failed"
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'src/sorter_sys_tb.vhd': 'MD5 check failed'
) << \SHAR_EOF

84ea0204db2352a00bb565878c4eee17 src/sorter_sys_tb.vhd
SHAR_EOF
else
test `LC_ALL=C wc -c < 'src/sorter_sys_tb.vhd'` -ne 4848 && \
${echo} "restoration warning: size of 'src/sorter_sys_tb.vhd' is not 4848"

-- Wojciech M. Zabolotny, "Dual port memory based Heapsort implementation
-- for FPGA", Proc. SPIE 8008, 80080E (2011); doi:10.1117/12.905281

(set 20 11 10 14 17 12 41 'src/sort_dpram.vhd'


eval "${shar_touch}") && \
chmod 0644 'src/sort_dpram.vhd'
if test $? -ne 0
then ${echo} "restore of src/sort_dpram.vhd failed"
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'src/sort_dpram.vhd': 'MD5 check failed'
) << \SHAR_EOF

4da0f4ed01164c10ab3aa755568781fc src/sort_dpram.vhd
SHAR_EOF
else
test `LC_ALL=C wc -c < 'src/sort_dpram.vhd'` -ne 5455 && \
${echo} "restoration warning: size of 'src/sort_dpram.vhd' is not 5455"

# ============= src/dpram4.vhd ==============

0 new messages