------------------------------------------------------------------------------- -- Title : Shifting Sorter with parameterizable Depth -- Project : Prototype implementation of the GTU of the Alice TRD Experiment ------------------------------------------------------------------------------- -- File : sorter.vhd -- Author : Jan de Cuveland -- Company : -- Last update: 2004/04/28 -- Platform : ------------------------------------------------------------------------------- -- This is a prototype implementation of the Global Tracking Unit (GTU) -- of the Alice TRD detector. ------------------------------------------------------------------------------- -- Description: Input data is sorted using a bubble-sort-like algorithm ------------------------------------------------------------------------------- -- Revisions : -- Date Version Author Description -- 2003/01/19 1.0 cuveland Created -- 2006/06/22 1.1 angelov replaced if-then-else chain with case in reg:process ------------------------------------------------------------------------------- library ieee; use ieee.std_logic_1164.all; use ieee.std_logic_arith.all; use work.gtu_types.all; ------------------------------------------------------------------------------- entity sorter is generic ( depth : integer); port ( clk : in std_logic; -- clock rst_n : in std_logic; -- asynchronous reset valid_in : in std_logic; y_in : in signed(PROJ_YPOS_WIDTH-1 downto 0); idx_in : in unsigned(IDX_WIDTH-1 downto 0); addr_in : in unsigned(ADDR_WIDTH-1 downto 0); valid_out : out std_logic; y_out : out signed(PROJ_YPOS_WIDTH-1 downto 0); idx_out : out unsigned(IDX_WIDTH-1 downto 0); addr_out : out unsigned(ADDR_WIDTH-1 downto 0)); end sorter; ------------------------------------------------------------------------------- architecture default of sorter is type y_tn is array (depth+1 downto 0) of signed(PROJ_YPOS_WIDTH-1 downto 0); type idx_tn is array (depth+1 downto 0) of unsigned(IDX_WIDTH-1 downto 0); type addr_tn is array (depth+1 downto 0) of unsigned(ADDR_WIDTH-1 downto 0); signal y : y_tn; signal idx : idx_tn; signal addr : addr_tn; type action_t is (INSERT_NEW, KEEP, FROM_LEFT, FROM_RIGHT); type action_tn is array (depth-1 downto 0) of action_t; signal action : action_tn; signal idx_in_i : unsigned(IDX_WIDTH-1 downto 0); signal last_idx_in : unsigned(IDX_WIDTH-1 downto 0); signal valid_out_i : std_logic; type lower_as_tn is array (depth+1 downto 0) of std_logic; signal lower_as : lower_as_tn; begin -- default -- set idx_in to "111" for end marker idx_in_i <= idx_in when y_in /= proj_ypos_end else (idx_in_i'range => '1'); -- save last input index for valid_out generation process (clk, rst_n) begin if rst_n = '0' then last_idx_in <= (last_idx_in'range => '0'); elsif clk'event and clk = '1' then if valid_in = '1' then last_idx_in <= idx_in_i; end if; end if; end process; -- generate valid_out process (addr, idx, valid_in, idx_in_i, last_idx_in) begin -- process valid_out_gen if addr(0+1) = unsigned(conv_signed(-1, ADDR_WIDTH)) then -- buffer empty valid_out_i <= '0'; elsif idx(depth-1) /= unsigned(conv_signed(-1, IDX_WIDTH)) then -- buffer full valid_out_i <= '1'; elsif valid_in = '1' then -- input data is valid if idx_in_i /= idx(0) then valid_out_i <= '1'; else valid_out_i <= '0'; end if; else -- input data is not valid if last_idx_in /= idx(0) or idx(0) = unsigned(conv_signed(-1, IDX_WIDTH)) then valid_out_i <= '1'; else valid_out_i <= '0'; end if; end if; end process; -- border values y(-1+1) <= (y(-1+1)'range => '0'); idx(-1+1) <= (idx(-1+1)'range => '0'); addr(-1+1) <= (addr(-1+1)'range => '0'); lower_as(-1+1) <= '0'; y(depth+1) <= "0111111111"; idx(depth+1) <= "111"; addr(depth+1) <= "111111"; lower_as(depth+1) <= '1'; -- generate sorter registers gen : for i in depth-1 downto 0 generate lower_as(i+1) <= '1' when (signed(y_in) <= y(i+1) and idx_in_i = idx(i+1)) or idx(i+1) = unsigned(conv_signed(-1, 3)) else '0'; act : process (valid_in, valid_out_i, lower_as, idx_in_i) begin -- process act if valid_in = '1' and idx_in_i /= conv_unsigned(0, 3) then if valid_out_i = '1' then if lower_as(i+1) = '1' then action(i) <= KEEP; else if lower_as(i+1+1) = '1' then action(i) <= INSERT_NEW; else action(i) <= FROM_RIGHT; end if; end if; else if lower_as(i+1) = '1' then if lower_as(i-1+1) = '0' then action(i) <= INSERT_NEW; else action(i) <= FROM_LEFT; end if; else action(i) <= KEEP; end if; end if; else if valid_out_i = '1' then action(i) <= FROM_RIGHT; else action(i) <= KEEP; end if; end if; end process act; reg : process (clk, rst_n) begin -- process reg if rst_n = '0' then y(i+1) <= "0111111111"; idx(i+1) <= "111"; addr(i+1) <= "111111"; elsif clk'event and clk = '1' then case action(i) is when FROM_LEFT => y(i+1) <= y(i-1+1); idx(i+1) <= idx(i-1+1); addr(i+1) <= addr(i-1+1); when FROM_RIGHT => y(i+1) <= y(i+1+1); idx(i+1) <= idx(i+1+1); addr(i+1) <= addr(i+1+1); when INSERT_NEW => y(i+1) <= signed(y_in); idx(i+1) <= idx_in_i; addr(i+1) <= addr_in; when others => NULL; end case; -- if action(i) = FROM_LEFT then -- y(i+1) <= y(i-1+1); -- idx(i+1) <= idx(i-1+1); -- addr(i+1) <= addr(i-1+1); -- elsif action(i) = FROM_RIGHT then -- y(i+1) <= y(i+1+1); -- idx(i+1) <= idx(i+1+1); -- addr(i+1) <= addr(i+1+1); -- elsif action(i) = INSERT_NEW then -- y(i+1) <= signed(y_in); -- idx(i+1) <= idx_in_i; -- addr(i+1) <= addr_in; -- end if; end if; end process reg; end generate gen; -- connect outputs valid_out <= valid_out_i; y_out <= y(0+1); idx_out <= idx(0+1); addr_out <= addr(0+1); end default; --| --| the meaning of idx: --|--------------------- --| "000" (0) -> drop this word (idx_in only: can also be end marker) --| "001" (1) -> accept as index 1 --| "010" (2) -> accept as index 2 --| "011" (3) -> accept as index 3 --| "100" (4) -> accept as index 4 --| "101" (5) -> accept as index 5 (idx_in only: can also be end marker) --| "110" (6) -> accept as index 6 (idx_in only: can also be end marker) --| "111" (7) -> end marker (only idx_in_i, idx_out and buffer) --| or empty space in buffer --| --| the meaning of y: --|------------------- --| "0111111111" (511) -> end marker (both y_in and y_out) --| or empty space in buffer --| everything else -> signed y value --| --| the meaning of addr: --|---------------------- --| "111111" (63) -> empty space in buffer --| everything else -> valid address or end marker --| --| special entries in buffer: --|---------------------------- --| | y | idx | addr | meaning | --| |-----------------------------------------|-------------| --| | "0111111111" | "111" | (nicht "111111") | end marker | --| | "0111111111" | "111" | "111111" | empty space | --|