Subversion Repositories heap_sorter

-------------------------------------------------------------------------------
-- Title      : Top entity of heap-sorter
-- Project    : heap-sorter
-------------------------------------------------------------------------------
-- File       : sorter_sys.vhd
-- Author     : Wojciech M. Zabolotny <wzab@ise.pw.edu.pl>
-- Company    : 
-- Created    : 2010-05-14
-- Last update: 2018-03-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
-- 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
-- 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.sorter_pkg.all;
use work.sys_config.all;
 
entity sorter_sys is
  generic (
    NLEVELS : integer := SYS_NLEVELS     -- number of levels in the sorter heap
    );
 
  port (
    din   : in  T_DATA_REC;
    we    : in  std_logic;
    dout  : out T_DATA_REC;
    dav   : out std_logic;
    clk   : in  std_logic;
    rst_n : in  std_logic;
    ready : out std_logic);
end sorter_sys;
 
architecture sorter_sys_arch1 of sorter_sys is
 
  component sort_dp_ram
    generic (
      ADDR_WIDTH : natural;
      NLEVELS    : natural;
      NAME       : string;
      RAM_STYLE_G : string := "block");
    port (
      clk    : in  std_logic;
      addr_a : in  std_logic_vector(NLEVELS-1 downto 0);
      addr_b : in  std_logic_vector(NLEVELS-1 downto 0);
      data_a : in  T_DATA_REC;
      data_b : in  T_DATA_REC;
      we_a   : in  std_logic;
      we_b   : in  std_logic;
      q_a    : out T_DATA_REC;
      q_b    : out T_DATA_REC);
  end component;
 
  component sorter_ctrl
    generic (
      NLEVELS   : integer;
      NADDRBITS : integer);
    port (
      tm_din       : in  T_DATA_REC;
      tm_dout      : out T_DATA_REC;
      tm_addr      : out std_logic_vector(NLEVELS-1 downto 0);
      tm_we        : out std_logic;
      lm_din       : in  T_DATA_REC;
      lm_dout      : out T_DATA_REC;
      lm_addr      : out std_logic_vector(NLEVELS-1 downto 0);
      lm_we        : out std_logic;
      rm_din       : in  T_DATA_REC;
      rm_dout      : out T_DATA_REC;
      rm_addr      : out std_logic_vector(NLEVELS-1 downto 0);
      rm_we        : out std_logic;
      up_in        : in  std_logic;
      up_in_val    : in  T_DATA_REC;
      up_in_addr   : in  std_logic_vector(NLEVELS-1 downto 0);
      up_out       : out std_logic;
      up_out_val   : out T_DATA_REC;
      up_out_addr  : out std_logic_vector(NLEVELS-1 downto 0);
      low_out      : out std_logic;
      low_out_val  : out T_DATA_REC;
      low_out_addr : out std_logic_vector(NLEVELS-1 downto 0);
      low_in       : in  std_logic;
      low_in_val   : in  T_DATA_REC;
      low_in_addr  : in  std_logic_vector(NLEVELS-1 downto 0);
      clk          : in  std_logic;
      clk_en       : in  std_logic;
      ready_in     : in  std_logic;
      ready_out    : out std_logic;
      rst_n        : in  std_logic);
  end component;
 
  -- Create signals for address buses
  -- Some of them will remain unused.
  subtype T_SORT_BUS_ADDR is std_logic_vector(NLEVELS-1 downto 0);
  type T_SORT_ADDR_BUSES is array (NLEVELS downto 0) of T_SORT_BUS_ADDR;
  signal low_addr, up_addr, addr_dr, addr_dl, addr_u                       : T_SORT_ADDR_BUSES                  := (others => (others => '0'));
  type T_SORT_DATA_BUSES is array (NLEVELS downto 0) of T_DATA_REC;
  signal up_update_path, low_update_path, data_d, data_dl, data_dr, data_u : T_SORT_DATA_BUSES                  := (others => DATA_REC_INIT_DATA);
  signal q_dr, q_dl, q_u, q_ul, q_ur                                       : T_SORT_DATA_BUSES                  := (others => DATA_REC_INIT_DATA);
  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');
  signal addr_switch, addr_switch_del                                      : std_logic_vector(NLEVELS downto 0);
  signal l0_reg                                                            : T_DATA_REC;
  signal clk_en                                                            : std_logic                          := '1';
 
  function f_sel_bram_style (
    addrwidth   : natural )
    return string is
  begin
    if addrwidth >= 4 then
      return "block";
    else
      return "distributed";
    end if;
  end function f_sel_bram_style;
 
begin  -- sorter_sys_arch1
 
-- Build the sorting tree
 
  g1 : for i in 0 to NLEVELS-1 generate
 
    -- Two RAMs from the upper level are seen as a single RAM
    -- We use the most significant bit (i-th bit) to distinguish RAM
    -- In all RAMs the A-ports are used for upstream connections
    -- and the B-ports are used for downstream connections
 
    -- Below are processes used to combine two upstream RAMs in a single one
    i0a : if i >= 1 generate
      addr_switch(i) <= addr_u(i)(i-1);
    end generate i0a;
    i0b : if i = 0 generate
      addr_switch(i) <= '0';
    end generate i0b;
 
    -- There is a problem with reading of data provided by two upstream RAMs
    -- we need to multiplex the data...
    -- Delay for read data multiplexer
    s1 : process (clk, rst_n)
    begin  -- process s1
      if rst_n = '0' then                 -- asynchronous reset (active low)
        addr_switch_del(i) <= '0';
      elsif clk'event and clk = '1' then  -- rising clock edge
        addr_switch_del(i) <= addr_switch(i);
      end if;
    end process s1;
 
    -- Upper RAM signals' multiplexer
    c1 : process (addr_switch, addr_switch_del, q_ul, q_ur, we_u)
    begin  -- process c1
      we_ul(i) <= '0';
      we_ur(i) <= '0';
      if addr_switch(i) = '1' then
        we_ul(i) <= we_u(i);
      else
        we_ur(i) <= we_u(i);
      end if;
      if addr_switch_del(i) = '1' then
        q_u(i) <= q_ul(i);
      else
        q_u(i) <= q_ur(i);
      end if;
    end process c1;
 
    dp_ram_l : sort_dp_ram
      generic map (
        NLEVELS    => NLEVELS,
        ADDR_WIDTH => i,
        NAME       => "L",
        RAM_STYLE_G => f_sel_bram_style(i))
      port map (
        clk    => clk,
        addr_a => addr_dl(i),
        addr_b => addr_u(i+1),
        data_a => data_dl(i),
        data_b => data_u(i+1),
        we_a   => we_dl(i),
        we_b   => we_ul(i+1),
        q_a    => q_dl(i),
        q_b    => q_ul(i+1));
 
    dp_ram_r : sort_dp_ram
      generic map (
        NLEVELS    => NLEVELS,
        ADDR_WIDTH => i,
        NAME       => "R",
        RAM_STYLE_G => f_sel_bram_style(i))
      port map (
        clk    => clk,
        addr_a => addr_dr(i),
        addr_b => addr_u(i+1),
        data_a => data_dr(i),
        data_b => data_u(i+1),
        we_a   => we_dr(i),
        we_b   => we_ur(i+1),
        q_a    => q_dr(i),
        q_b    => q_ur(i+1));
 
    sorter_ctrl_1 : sorter_ctrl
      generic map (
        NLEVELS   => NLEVELS,
        NADDRBITS => i)
      port map (
        tm_din       => q_u(i),
        tm_dout      => data_u(i),
        tm_addr      => addr_u(i),
        tm_we        => we_u(i),
        lm_din       => q_dl(i),
        lm_dout      => data_dl(i),
        lm_addr      => addr_dl(i),
        lm_we        => we_dl(i),
        rm_din       => q_dr(i),
        rm_dout      => data_dr(i),
        rm_addr      => addr_dr(i),
        rm_we        => we_dr(i),
        up_in        => up_update(i),
        up_in_val    => up_update_path(i),
        up_in_addr   => up_addr(i),
        up_out       => low_update(i),
        up_out_val   => low_update_path(i),
        up_out_addr  => low_addr(i),
        low_in       => low_update(i+1),
        low_in_val   => low_update_path(i+1),
        low_in_addr  => low_addr(i+1),
        low_out      => up_update(i+1),  -- connections to the next level
        low_out_val  => up_update_path(i+1),
        low_out_addr => up_addr(i+1),
        clk          => clk,
        clk_en       => clk_en,
        ready_in     => s_ready(i+1),
        ready_out    => s_ready(i),
        rst_n        => rst_n);
 
  end generate g1;
  -- top level
 
  -- On the top level we have only a single register
  process (clk, rst_n)
    variable rline : line;
  begin  -- process
    if rst_n = '0' then                 -- asynchronous reset (active low)
      l0_reg <= DATA_REC_INIT_DATA;
      dav <= '0';
    elsif clk'event and clk = '1' then  -- rising clock edge
      dav <= '0';
      if we_u(0) = '1' then
        l0_reg <= data_u(0);
        dout   <= data_u(0);
        dav    <= '1';
        --if SORT_DEBUG then
        --  write(rline, string'("OUT: "));
        --  write(rline, tdrec2stlv(data_u(0)));
        --  writeline(reports, rline);
        --end if;
      elsif we = '1' then
        --if SORT_DEBUG then
        --  write(rline, string'("IN: "));
        --  write(rline, tdrec2stlv(din));
        --  writeline(reports, rline);
        --end if;
        l0_reg <= din;
        -- dout   <= din;
      -- else
      --   dout <= l0_reg;
      end if;
    end if;
  end process;
  ready             <= s_ready(0);
  q_ur(0)           <= l0_reg;
  q_ul(0)           <= l0_reg;
  up_update(0)      <= we;
  up_update_path(0) <= din;
  up_addr(0)        <= (others => '0');
 
  -- signals for the last level
 
  s_ready(NLEVELS) <= '1';
  --addr(NLEVELS)    <= (others => '0');
  data_dr(NLEVELS) <= DATA_REC_INIT_DATA;
  data_dl(NLEVELS) <= DATA_REC_INIT_DATA;
  we_dl(NLEVELS)   <= '0';
  we_dr(NLEVELS)   <= '0';
 
  low_update(NLEVELS)      <= '0';
  low_update_path(NLEVELS) <= DATA_REC_INIT_DATA;
  low_addr(0)              <= (others => '0');
 
end sorter_sys_arch1;