-- EMACS settings: -*- tab-width: 2; indent-tabs-mode: t -*-
-- vim: tabstop=2:shiftwidth=2:noexpandtab
-- kate: tab-width 2; replace-tabs off; indent-width 2;
-- =============================================================================
-- Authors: Jens Voss
--
-- Entity: Double-ended queue
--
-- Description:
--
-- Implements a deque (double-ended queue). This data structure allows two
-- acting entities to queue data elements for the consumption by the other while
-- still being able to unqueue untaken ones in LIFO fashion.
--
-- License:
-- =============================================================================
-- Copyright 2007-2016 Technische Universitaet Dresden - Germany
-- Chair of VLSI-Design, Diagnostics and Architecture
--
-- Licensed under the Apache License, Version 2.0 (the "License");
-- you may not use this file except in compliance with the License.
-- You may obtain a copy of the License at
--
-- http://www.apache.org/licenses/LICENSE-2.0
--
-- Unless required by applicable law or agreed to in writing, software
-- distributed under the License is distributed on an "AS IS" BASIS,
-- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-- See the License for the specific language governing permissions and
-- limitations under the License.
-- =============================================================================
library IEEE;
use IEEE.std_logic_1164.all;
entity [docs]dstruct_deque is
generic (
D_BITS : positive; -- Data Width
MIN_DEPTH : positive -- Minimum Deque Depth
);
port (
-- Shared Ports
clk, rst : in std_logic;
-- Port A
dinA : in std_logic_vector(D_BITS-1 downto 0); -- DataA Input
putA : in std_logic;
gotA : in std_logic;
doutA : out std_logic_vector(D_BITS-1 downto 0); -- DataA Output
validA : out std_logic;
fullA : out std_logic;
-- Port B
dinB : in std_logic_vector(D_BITS-1 downto 0); -- DataB Input
putB : in std_logic;
gotB : in std_logic;
doutB : out std_logic_vector(D_BITS-1 downto 0);
validB : out std_logic;
fullB : out std_logic
);
end entity dstruct_deque;
library IEEE;
use IEEE.numeric_std.all;
library PoC;
use PoC.config.all;
use PoC.utils.all;
use PoC.ocram.all;
architecture [docs]rtl of dstruct_deque is
-- Constants
constant A_BITS : natural := log2ceil(MIN_DEPTH);
-- MEMORY variable
-- type memory_t is array ((2**A_BITS)-1 downto 0) of std_logic_vector(D_BITS-1 downto 0);
-- signal memory : memory_t := (others => (others => '0'));
-- Signals
signal combined : std_logic_vector(3 downto 0) := (others => '0');
signal ctrl : std_logic_vector(1 downto 0) := (others => '1');
signal sub : unsigned(A_BITS-1 downto 0) := (others => '0');
-- last operation flag
signal last_operation : std_logic := '0'; -- save last operation 0 -> read, 1 -> write
type last_op_ctrl_t is (IDLE, SET, UNSET);
signal last_op_ctrl : last_op_ctrl_t := IDLE;
signal delayed_valid : std_logic := '0';
signal delay : std_logic := '0';
-- signal s_validA : std_logic := '0';
-- signal s_validB : std_logic := '0';
-- Stackpointer
-- A
signal stackpointerA : unsigned (A_BITS-1 downto 0) := shift_right(to_unsigned(MIN_DEPTH-1,A_BITS),1);
-- signal reA : std_logic := '0';
signal weA : std_logic := '0';
-- B
signal stackpointerB : unsigned (A_BITS-1 downto 0) := shift_right(to_unsigned(MIN_DEPTH-1,A_BITS),1) + 1;
-- signal reB : std_logic := '0';
signal weB : std_logic := '0';
-- ctrl signal for stackpointer operations
type ctrl_t is (PUSH, POP, IDLE);
signal ctrlA : ctrl_t := IDLE;
signal ctrlB : ctrl_t := IDLE;
-- RAM Signals
signal adrA : unsigned(A_BITS-1 downto 0) := (others => '0');
signal adrB : unsigned(A_BITS-1 downto 0) := (others => '0');
begin
ram : entity poc.ocram_tdp_wf
generic map(
A_BITS => A_BITS,
D_BITS => D_BITS,
FILENAME => ""
)
port map(
clk => clk,
ce => '1',
we1 => weA,
we2 => weB,
a1 => adrA,
a2 => adrB,
d1 => dinA,
d2 => dinB,
q1 => doutA,
q2 => doutB
);
sub <= stackpointerB - stackpointerA;
combined <= putA & gotA & putB & gotB;
process(combined, stackpointerA, stackpointerB, last_operation, ctrl)
begin
ctrlA <= IDLE;
ctrlB <= IDLE;
-- reA <= '1';
-- reB <= '1';
adrA <= stackpointerA + 1;
adrB <= stackpointerB - 1;
weA <= '0';
weB <= '0';
last_op_ctrl <= IDLE;
delay <= '0';
case(combined) is
when x"0" => --nothing
-- nothing happened/happens
-- don't update stackpointers
ctrlA <= IDLE;
ctrlB <= IDLE;
when x"1" => --readB
-- B read a valid value
-- update stackpointer
ctrlB <= POP;
-- reB <= '1';
adrB <= stackpointerB - 2;
last_op_ctrl <= UNSET;
if ctrl = "01" then
if(last_operation = '0') then
--> deque is empty!
-- B couldn't read a valid value => don't update SP!
ctrlB <= IDLE;
adrB <= stackpointerB - 1;
last_op_ctrl <= UNSET;
end if;
elsif ctrl = "10" then
--> only one element left
-- side B saw empty signal
-- so B couldn't read a valid value
ctrlB <= IDLE;
adrB <= stackpointerB - 1;
last_op_ctrl <= IDLE;
end if;
when x"2" => --writeB
ctrlB <= PUSH;
weB <= '1';
adrB <= stackpointerB;
last_op_ctrl <= SET;
if ctrl = "01" then
if(last_operation = '1') then
--> deque is full!
-- B cant write => don't update SP!
ctrlB <= IDLE;
weB <= '0';
adrB <= stackpointerB - 1;
else
--> deque is empty!
--> delay validA signal for one clk cycle
delay <= '1';
end if;
elsif ctrl = "00" then
--> only one spot left
-- B isn't allowed to write
-- B sees full signal atm
weB <= '0';
adrB <= stackpointerB - 1;
ctrlB <= IDLE;
end if;
when x"3" => --readB, writeB
-- B read a valid value and writes a new value at the same spot
-- don't update stackpointer
-- reB <= '1';
adrB <= stackpointerB - 1;
weB <= '1';
last_op_ctrl <= SET;
if ctrl = "01" then
if (last_operation = '1') then
--> deque is full!
-- B read a valid value but new value cant be pushed!
ctrlB <= POP;
weB <= '0';
adrB <= stackpointerB - 2;
last_op_ctrl <= UNSET;
else
--> deque is empty!
-- B couldn't read a valid value, but new value can be written!
-- delay validA signal one clk cycle
ctrlB <= PUSH;
weB <= '1';
adrB <= stackpointerB;
last_op_ctrl <= SET;
delay <= '1';
end if;
elsif ctrl = "10" then
--> only one element left
-- B couldn't read it, but can write new value
ctrlB <= PUSH;
weB <= '1';
adrB <= stackpointerB;
last_op_ctrl <= SET;
elsif ctrl = "00" then
-- only one spot left
-- B read a valid value but cant write new value
ctrlB <= POP;
weB <= '0';
adrB <= stackpointerB - 2;
last_op_ctrl <= UNSET;
end if;
when x"4" => --readA
-- A read a valid values
-- update stackpointer
ctrlA <= POP;
-- reA <= '1';
adrA <= stackpointerA + 2;
last_op_ctrl <= UNSET;
if (ctrl = "01" and last_operation = '0') then
--> deque is empty!
-- A couldn't read a valid value => don't update SP!
ctrlA <= IDLE;
adrA <= stackpointerA + 1;
end if;
when x"5" => --readA, readB
-- A and B read both valid values
-- update both stackpointers
ctrlA <= POP;
ctrlB <= POP;
-- reB <= '1';
adrB <= stackpointerB - 2;
-- reA <= '1';
adrA <= stackpointerA + 2;
last_op_ctrl <= UNSET;
if ctrl = "01" then
if (last_operation = '1') then
--> deque is full
-- A and B read a valid value!
last_op_ctrl <= UNSET;
else
--> deque is empty!
-- A and B couldn't a valid value => don't update SP!
ctrlB <= IDLE;
ctrlA <= IDLE;
adrA <= stackpointerA + 1;
adrB <= stackpointerB - 1;
end if;
elsif ctrl = "10" then
-- A and B both tried to read last value!
-- but only A was allowed to read value so only update stackpointerA
ctrlA <= POP;
ctrlB <= IDLE;
end if;
when x"6" => --readA, writeB
-- A read a valid value and B writes a new value
-- update both stackpointers
ctrlA <= POP;
ctrlB <= PUSH;
-- reA <= '1';
adrA <= stackpointerA + 2;
weB <= '1';
adrB <= stackpointerB;
last_op_ctrl <= SET;
if ctrl = "01" then
if(last_operation = '1') then
--> deque is full!
-- A read a valid value, but B cant push!
ctrlB <= IDLE;
weB <= '0';
last_op_ctrl <= UNSET;
adrB <= stackpointerB - 1;
else
--> deque is empty!
-- A couldn't read a valid value, but B can push!
-- delay validA signal one clk cycle
ctrlA <= IDLE;
adrA <= stackpointerA + 1;
last_op_ctrl <= SET;
delay <= '1';
end if;
elsif ctrl = "10" then
--> only one element in deque
--> A read valid value and B can write new value
--> But validA has to be delayed!
delay <= '1';
elsif ctrl = "00" then
--> only one spot left
-- A read valid value, but B isn't allowed to write last value
ctrlB <= IDLE;
weB <= '0';
last_op_ctrl <= UNSET;
adrB <= stackpointerB - 1;
end if;
when x"7" => --readA, readB, writeB
-- A and B read valid values and B writes a new value at the same spot
-- Update stackpointerA and don't update stackpointer B
ctrlA <= POP;
adrB <= stackpointerB - 1;
-- reB <= '1';
weB <= '1';
adrA <= stackpointerA + 2;
-- reA <= '1';
last_op_ctrl <= SET;
if ctrl = "01" then
if last_operation = '1' then
--> deque is full!
-- A and B read a valid value, but B cant push!
ctrlB <= POP;
weB <= '0';
adrB <= stackpointerB - 2;
last_op_ctrl <= UNSET;
else
--> deque is empty!
-- A and B couldn't have read a valid value, but B can push!
-- delay validA signal one clk cycle
adrA <= stackpointerA + 1;
ctrlA <= IDLE;
ctrlB <= PUSH;
weB <= '1';
adrB <= stackpointerB;
last_op_ctrl <= SET;
delay <= '1';
end if;
elsif ctrl = "00" then
--> only one spot left
-- A and B read valid values, but B isn't allowed to write new value
-- B sees full signal atm
ctrlB <= POP;
weB <= '0';
adrB <= stackpointerB - 2;
last_op_ctrl <= UNSET;
elsif ctrl = "10" then
--> only one element in deque
-- only A read a valid value, but B can write a new value
--> validA has to be delayed!
ctrlB <= PUSH;
weB <= '1';
adrB <= stackpointerB;
last_op_ctrl <= SET;
delay <= '1';
end if;
when x"8" => --writeA
-- A writes a new value
-- update stackpointer
ctrlA <= PUSH;
weA <= '1';
adrA <= stackpointerA;
last_op_ctrl <= SET;
if ctrl = "01" then
if (last_operation = '1') then
--> deque is full
-- A cant write!
ctrlA <= IDLE;
weA <= '0';
adrA <= stackpointerA + 1;
end if;
end if;
when x"9" => --writeA, readB
-- A writes new value and B reads a valid value
-- update both stackpointers
ctrlA <= PUSH;
ctrlB <= POP;
-- reB <= '1';
weA <= '1';
adrA <= stackpointerA;
adrB <= stackpointerB - 2;
last_op_ctrl <= SET;
if ctrl = "01" then
if (last_operation = '1') then
--> deque is full!
-- A cant write, but B read a valid value!
weA <= '0';
ctrlA <= IDLE;
adrA <= stackpointerA + 1;
last_op_ctrl <= SET;
else
--> deque is empty!
-- A can write, but B couldn't read a valid value!
ctrlB <= IDLE;
adrB <= stackpointerB - 1;
last_op_ctrl <= SET;
end if;
elsif ctrl = "10" then
--> only one element left
-- A can write new value, but B couldn't read a valid value
-- B sees empty signal atm
ctrlB <= IDLE;
adrB <= stackpointerB - 1;
last_op_ctrl <= SET;
end if;
when x"A" => --writeA, writeB
-- A and B write new values
-- update both Stackpointers
ctrlA <= PUSH;
ctrlB <= PUSH;
weA <= '1';
adrA <= stackpointerA;
weB <= '1';
adrB <= stackpointerB;
last_op_ctrl <= SET;
if ctrl = "01" then
if (last_operation = '1') then
--> deque is full!
-- A and B cant write!
ctrlA <= IDLE;
ctrlB <= IDLE;
weA <= '0';
weB <= '0';
adrB <= stackpointerB - 1;
adrA <= stackpointerA + 1;
last_op_ctrl <= UNSET;
else
--> deque is empty!
--> A and B can write!
last_op_ctrl <= SET;
end if;
elsif ctrl = "00" then
--> only one spot left.
-- only A is allowed to write
-- B got full signal
weB <= '0';
ctrlB <= IDLE;
adrB <= stackpointerB - 1;
end if;
when x"B" => --writeA, readB, writeB
--> A writes a value and B read a valid value and writes a new value at the same spot!
-- update stackpointerA and don't update stackpointerB
ctrlA <= PUSH;
weA <= '1';
adrA <= stackpointerA;
-- reB <= '1';
weB <= '1';
adrB <= stackpointerB - 1;
last_op_ctrl <= SET;
if ctrl = "01" then
if (last_operation = '1') then
--> deque is full!
-- A and B cant write, but B read a valid value!
ctrlB <= POP;
ctrlA <= IDLE;
weA <= '0';
weB <= '0';
adrA <= stackpointerA + 1;
adrB <= stackpointerB - 2;
last_op_ctrl <= UNSET;
else
--> deque is empty
--> A and B can write, but B couldn't read a valid value!
ctrlB <= PUSH;
adrB <= stackpointerB;
last_op_ctrl <= SET;
end if;
elsif ctrl = "00" then
--> only one spot left
-- only A can write last value
-- B only read a valid value
ctrlB <= POP;
weB <= '0';
adrB <= stackpointerB - 2;
elsif ctrl = "10" then
--> only one element left
--> B couldn't read value but A and B are allowed to write new values
ctrlB <= PUSH;
adrB <= stackpointerB;
last_op_ctrl <= SET;
end if;
when x"C" => --readA, writeA
--> A read a valid value and writes a new value at the same spot!
-- => don't update stackpointer!
ctrlA <= IDLE;
-- reA <= '1';
weA <= '1';
adrA <= stackpointerA + 1;
last_op_ctrl <= SET;
if ctrl = "01" then
if (last_operation = '1') then
--> deque is full!
-- A cant write, but read a valid value!
ctrlA <= POP;
weA <= '0';
adrA <= stackpointerA + 2;
last_op_ctrl <= UNSET;
else
--> deque is empty!
-- A can write, but couldn't read a valid value!
ctrlA <= PUSH;
adrA <= stackpointerA;
last_op_ctrl <= SET;
end if;
end if;
when x"D" => --readA, writeA, readB
-- A and B read valid values and A writes a new value at the same spot
-- don't update stackpointerA and update stackpointerB
ctrlB <= POP;
ctrlA <= IDLE;
-- reA <= '1';
weA <= '1';
adrA <= stackpointerA + 1;
-- reB <= '1';
adrB <= stackpointerB - 2;
last_op_ctrl <= SET;
if ctrl = "01" then
if (last_operation = '1') then
--> deque is full!
-- A cant write new values, but A and B could read a valid value
ctrlA <= POP;
ctrlB <= POP;
adrA <= stackpointerA + 2;
weA <= '0';
last_op_ctrl <= UNSET;
else
--> deque is empty!
-- A and B couldn't read a valid value, but A can write a new value
ctrlA <= PUSH;
adrB <= stackpointerB - 1;
ctrlB <= IDLE;
adrA <= stackpointerA;
last_op_ctrl <= SET;
end if;
elsif ctrl = "10" then
--> only one element in deque
-- only A read valid value and can write a new value
adrB <= stackpointerB - 1;
ctrlB <= IDLE;
ctrlA <= IDLE;
adrA <= stackpointerA + 1;
last_op_ctrl <= SET;
end if;
when x"E" => --readA, writeA, writeB
-- B writes a new value, A read a valid value and writes a new value at the same spot
-- update stackpiunterB and don't update stackpointerA
ctrlB <= PUSH;
ctrlA <= IDLE;
-- reA <= '1';
weA <= '1';
adrA <= stackpointerA + 1;
weB <= '1';
adrB <= stackpointerB;
last_op_ctrl <= SET;
if ctrl = "01" then
if (last_operation = '1') then
--> deque is full!
-- A and B cant write, but A could read valid value
weA <= '0';
weB <= '0';
ctrlA <= POP;
ctrlB <= IDLE;
adrB <= stackpointerB - 1;
adrA <= stackpointerA + 2;
last_op_ctrl <= UNSET;
else
--> deque is empty!
-- A couldn't read a valid value, but A and B can write new values
ctrlA <= PUSH;
ctrlB <= PUSH;
adrA <= stackpointerA;
last_op_ctrl <= SET;
end if;
elsif ctrl = "00" then
--> only one spot left
-- B cant write new value
ctrlB <= IDLE;
weB <= '0';
adrB <= stackpointerB - 1;
end if;
when x"F" => --readA, writeA,readB, writeB
-- A and B read valid values and write new values at the same stackpointers
-- don't update both stackpointers
ctrlA <= IDLE;
ctrlB <= IDLE;
-- reA <= '1';
weA <= '1';
adrA <= stackpointerA + 1;
weB <= '1';
-- reB <= '1';
adrB <= stackpointerB - 1;
last_op_ctrl <= SET;
if ctrl = "01" then
if last_operation = '1' then
--> deque is full
-- A and B could read valid values but cant write new values
ctrlA <= POP;
ctrlB <= POP;
weA <= '0';
weB <= '0';
adrA <= stackpointerA + 2;
adrB <= stackpointerB - 2;
last_op_ctrl <= UNSET;
else
--> deque is empty
-- A and B couldn't read valid values but can both write new values
ctrlA <= PUSH;
ctrlB <= PUSH;
adrA <= stackpointerA;
adrB <= stackpointerB;
last_op_ctrl <= SET;
end if;
elsif ctrl = "10" then
--> only one element left
-- only A read last value, A replaces the last element
-- B just writes new value
-- B sees empty signal atm
ctrlB <= PUSH;
adrB <= stackpointerB;
elsif ctrl = "00" then
--> only one spot left
-- B read a valid value, but isn't allowed to write
-- B sees full signal atm
ctrlB <= POP;
adrB <= stackpointerB - 2;
weB <= '0';
end if;
when others => --nothing
-- nothing happened/happens
-- don't update stackpointers
last_op_ctrl <= IDLE;
end case;
end process;
process(clk)
begin
if rising_edge(clk) then
if (rst = '1') then
last_operation <= '0';
else
case( last_op_ctrl ) is
when IDLE =>
last_operation <= last_operation;
when SET =>
last_operation <= '1';
when UNSET =>
last_operation <= '0';
when others =>
last_operation <= last_operation;
end case;
end if;
end if;
end process;
--stackpointerA operations
process(clk)
begin
if rising_edge(clk) then
if (rst = '1') then
stackpointerA <= shift_right(to_unsigned(MIN_DEPTH-1,A_BITS),1);
else
case( ctrlA ) is
when IDLE =>
stackpointerA <= stackpointerA;
when PUSH =>
stackpointerA <= stackpointerA - 1;
when POP =>
stackpointerA <= stackpointerA + 1;
when others =>
stackpointerA <= stackpointerA;
end case;
end if;
end if;
end process;
-- stackpointerB operations
process(clk)
begin
if rising_edge(clk) then
if (rst = '1') then
stackpointerB <= shift_right(to_unsigned(MIN_DEPTH-1,A_BITS),1) + 1;
else
case( ctrlB ) is
when IDLE =>
stackpointerB <= stackpointerB;
when PUSH =>
stackpointerB <= stackpointerB + 1;
when POP =>
stackpointerB <= stackpointerB - 1;
when others =>
stackpointerB <= stackpointerB;
end case;
end if;
end if;
end process;
-- delayed_valid register
process(clk)
begin
if rising_edge(clk) then
if(rst = '1') then
delayed_valid <= '0';
else
if (delay = '1') then
delayed_valid <= '1';
else
delayed_valid <= '0';
end if;
end if;
end if;
end process;
-- sub of B and A
process(sub, last_operation, delayed_valid)
begin
fullA <= '0';
fullB <= '0';
validB <= '1';
if(delayed_valid = '1') then
validA <= '0';
else
validA <= '1';
end if;
case(to_integer(sub)) is
when 0 =>
ctrl <= "00"; -- let a or b write?
-- only one spot left
-- set one side to full!
-- at the moment A has higher priority
fullB <= '1';
when 1 =>
ctrl <= "01"; -- empty or full?
if (last_operation = '1') then
fullA <= '1';
fullB <= '1';
else
validA <= '0';
validB <= '0';
end if;
when 2 =>
ctrl <= "10"; -- let a or b read?
-- only one element left
-- set one side to empty!
-- at the moment A has higher priority
validB <= '0';
when 3 =>
ctrl <= "11"; -- both can write/read
when others =>
ctrl <= "11";
end case;
end process;
end architecture;