Arbiter

From Hamsterworks Wiki!

(Difference between revisions)
Jump to: navigation, search
(Source files)
 
Line 7: Line 7:
Here is the simulation of the outputs in the two different modes:
Here is the simulation of the outputs in the two different modes:
-
[[image:arbitor4_hold_mode.jpg|800px]]
+
[[image:arbitor4_hold_mode.jpg|950px]]
-
[[image:arbitor4_no_hold_mode.jpg|800px]]
+
[[image:arbitor4_no_hold_mode.jpg|950px]]
(the half-width pulses are due to the request inputs being updated on the falling edge.
(the half-width pulses are due to the request inputs being updated on the falling edge.

Latest revision as of 10:02, 6 October 2019

This FPGA Project was finished in October 2019

An Arbiter is logic that is used to decide who can have access to a shared resource - see https://en.wikipedia.org/wiki/Arbiter_(electronics) for more info. The need to be fast, simple and fair. For a limited number of inputs you can have it all!

This can be configured two ways - to either round-robin on each cycle, or to keep the output granted until it is released by the requester. The first might be useful for a wide bus (e.g. a write port on a FIFO). The second would be useful for transferring data packets.

Here is the simulation of the outputs in the two different modes:

Arbitor4 hold mode.jpg

Arbitor4 no hold mode.jpg

(the half-width pulses are due to the request inputs being updated on the falling edge.

To switch between modes uncommment the different set of four constants.

Source files

This code looks long, but implements into very small, fast logic. Way faster than the designs you see in papers like http://cva.stanford.edu/publications/2012/dub-thesis.pdf#page=30 when implemented in an FPGA. The logic in figure 2.2 is very hard to implement in FPGAs due to a combinatorial logic loop.

arbiter4.vhd

--------------------------------------------------------------------
-- arbiter4.vhd : a high performance 4-input arbiter for LUT6 FPGAs
--
-- Written by: Mike Field <hamster@snap.net.nz>
--
--------------------------------------------------------------------
library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;

entity arbiter4 is
    Port ( clk     : in  STD_LOGIC;
           reset   : in  STD_LOGIC;
           request : in  STD_LOGIC_VECTOR (3 downto 0);
           grant   : out STD_LOGIC_VECTOR (3 downto 0));
end arbiter4;

architecture Behavioral of arbiter4 is
   ----------------------------------------------------------------------
   -- A 4-input arbiter for a LUT6 FPGA artchitecture
   -- 
   ----------------------------------------------------------------------
   -- Bit 6    =  do we need to increment priority once nothing is granted?
   -- 
   -- Bits 5:4 - Which bit has the highest priortiy, pritorites are either
   --         Highest => Lowast
   --              0 1 2 3  (when 3 was the last granted)
   --              1 2 3 0  (when 0 was the last granted)
   --              2 3 0 1  (when 1 was the last granted)
   --              3 0 1 2  (when 2 was the last granted)
   --
   -- Bits 3:0 - The grant signals
   --
   -------------------------------------------------------------------------
   constant GRANT_NONE_PRI_0 : std_logic_vector (6 downto 0) := "0000000";
   constant GRANT_NONE_PRI_1 : std_logic_vector (6 downto 0) := "0010000";
   constant GRANT_NONE_PRI_2 : std_logic_vector (6 downto 0) := "0100000";
   constant GRANT_NONE_PRI_3 : std_logic_vector (6 downto 0) := "0110000";

---------------------------------------------------------------------
-- Use these to have a "hold the grant until no longer requested"
--
-- Timing when constrianted ot 1.8ns in Spartan-6 grade 3, with 
-- resgistered inputs and outputs
--
--     Minimum period:   1.765ns{1}   (Maximum frequency: 566.572MHz) 
-- 
-- Resource usage 10 LUT-6s, 3 flipflops
---------------------------------------------------------------------
--   constant GRANT_0          : std_logic_vector (6 downto 0) := "1000001";
--   constant GRANT_1          : std_logic_vector (6 downto 0) := "1010010";
--   constant GRANT_2          : std_logic_vector (6 downto 0) := "1100100";
--   constant GRANT_3          : std_logic_vector (6 downto 0) := "1111000";
--
--
---------------------------------------------------------------------
-- Use these to have a move to the next request after the first cycle
--
--    Minimum period:   1.730ns{1}   (Maximum frequency: 578.035MHz) 
-- 
-- Resource usage 6 LUT-6s, 2 flipflops
---------------------------------------------------------------------
   constant GRANT_0          : std_logic_vector (6 downto 0) := "0010001";
   constant GRANT_1          : std_logic_vector (6 downto 0) := "0100010";
   constant GRANT_2          : std_logic_vector (6 downto 0) := "0110100";
   constant GRANT_3          : std_logic_vector (6 downto 0) := "0001000";


   signal   highest_priority : std_logic_vector (2 downto 0) := "000";
   signal   lookup           : std_logic_vector (6 downto 0) := "0000000";

begin
   grant <= lookup(3 downto 0);
   
process(clk)
   begin
      if rising_edge(clk) then 
         if reset = '1' then
            highest_priority <= "000";
         else
            highest_priority <= lookup(6 downto 4);
         end if;
      end if;
   end process;


process(highest_priority, request) 
   begin
      case (highest_priority & request) is
--====== When nothing has been granted during the last cycle
         -- request(0) has priority 
         when "0000000" => lookup <= GRANT_NONE_PRI_0;
         when "0000001" => lookup <= GRANT_0;
         when "0000010" => lookup <= GRANT_1;
         when "0000011" => lookup <= GRANT_0;
         when "0000100" => lookup <= GRANT_2;
         when "0000101" => lookup <= GRANT_0;
         when "0000110" => lookup <= GRANT_1;
         when "0000111" => lookup <= GRANT_0;
         when "0001000" => lookup <= GRANT_3;
         when "0001001" => lookup <= GRANT_0;
         when "0001010" => lookup <= GRANT_1;
         when "0001011" => lookup <= GRANT_0;
         when "0001100" => lookup <= GRANT_2;
         when "0001101" => lookup <= GRANT_0;
         when "0001110" => lookup <= GRANT_1;
         when "0001111" => lookup <= GRANT_0;

         -- request(1) has priority 
         when "0010000" => lookup <= GRANT_NONE_PRI_1;
         when "0010001" => lookup <= GRANT_0;
         when "0010010" => lookup <= GRANT_1;
         when "0010011" => lookup <= GRANT_1;
         when "0010100" => lookup <= GRANT_2;
         when "0010101" => lookup <= GRANT_2;
         when "0010110" => lookup <= GRANT_1;
         when "0010111" => lookup <= GRANT_1;
         when "0011000" => lookup <= GRANT_3;
         when "0011001" => lookup <= GRANT_3;
         when "0011010" => lookup <= GRANT_1;
         when "0011011" => lookup <= GRANT_1;
         when "0011100" => lookup <= GRANT_2;
         when "0011101" => lookup <= GRANT_2;
         when "0011110" => lookup <= GRANT_1;
         when "0011111" => lookup <= GRANT_1;

         -- request(2) has priority 
         when "0100000" => lookup <= GRANT_NONE_PRI_2;
         when "0100001" => lookup <= GRANT_0;
         when "0100010" => lookup <= GRANT_1;
         when "0100011" => lookup <= GRANT_0;
         when "0100100" => lookup <= GRANT_2;
         when "0100101" => lookup <= GRANT_2;
         when "0100110" => lookup <= GRANT_2;
         when "0100111" => lookup <= GRANT_2;
         when "0101000" => lookup <= GRANT_3;
         when "0101001" => lookup <= GRANT_3;
         when "0101010" => lookup <= GRANT_3;
         when "0101011" => lookup <= GRANT_3;
         when "0101100" => lookup <= GRANT_2;
         when "0101101" => lookup <= GRANT_2;
         when "0101110" => lookup <= GRANT_2;
         when "0101111" => lookup <= GRANT_2;

         -- request(3) has priority 
         when "0110000" => lookup <= GRANT_NONE_PRI_3;
         when "0110001" => lookup <= GRANT_0;
         when "0110010" => lookup <= GRANT_1;
         when "0110011" => lookup <= GRANT_0;
         when "0110100" => lookup <= GRANT_2;
         when "0110101" => lookup <= GRANT_0;
         when "0110110" => lookup <= GRANT_1;
         when "0110111" => lookup <= GRANT_0;
         when "0111000" => lookup <= GRANT_3;
         when "0111001" => lookup <= GRANT_3;
         when "0111010" => lookup <= GRANT_3;
         when "0111011" => lookup <= GRANT_3;
         when "0111100" => lookup <= GRANT_3;
         when "0111101" => lookup <= GRANT_3;
         when "0111110" => lookup <= GRANT_3;
         when "0111111" => lookup <= GRANT_3;
         
--==== When something has been granted last cycle, so when release we have to inc priority
         -- request(0) has priority 
         when "1000000" => lookup <= GRANT_NONE_PRI_1;
         when "1000001" => lookup <= GRANT_0;
         when "1000010" => lookup <= GRANT_1;
         when "1000011" => lookup <= GRANT_0;
         when "1000100" => lookup <= GRANT_2;
         when "1000101" => lookup <= GRANT_0;
         when "1000110" => lookup <= GRANT_1;
         when "1000111" => lookup <= GRANT_0;
         when "1001000" => lookup <= GRANT_3;
         when "1001001" => lookup <= GRANT_0;
         when "1001010" => lookup <= GRANT_1;
         when "1001011" => lookup <= GRANT_0;
         when "1001100" => lookup <= GRANT_2;
         when "1001101" => lookup <= GRANT_0;
         when "1001110" => lookup <= GRANT_1;
         when "1001111" => lookup <= GRANT_0;

         -- request(1) has priority 
         when "1010000" => lookup <= GRANT_NONE_PRI_2;
         when "1010001" => lookup <= GRANT_0;
         when "1010010" => lookup <= GRANT_1;
         when "1010011" => lookup <= GRANT_1;
         when "1010100" => lookup <= GRANT_2;
         when "1010101" => lookup <= GRANT_2;
         when "1010110" => lookup <= GRANT_1;
         when "1010111" => lookup <= GRANT_1;
         when "1011000" => lookup <= GRANT_3;
         when "1011001" => lookup <= GRANT_3;
         when "1011010" => lookup <= GRANT_1;
         when "1011011" => lookup <= GRANT_1;
         when "1011100" => lookup <= GRANT_2;
         when "1011101" => lookup <= GRANT_2;
         when "1011110" => lookup <= GRANT_1;
         when "1011111" => lookup <= GRANT_1;

         -- request(2) has priority 
         when "1100000" => lookup <= GRANT_NONE_PRI_3;
         when "1100001" => lookup <= GRANT_0;
         when "1100010" => lookup <= GRANT_1;
         when "1100011" => lookup <= GRANT_0;
         when "1100100" => lookup <= GRANT_2;
         when "1100101" => lookup <= GRANT_2;
         when "1100110" => lookup <= GRANT_2;
         when "1100111" => lookup <= GRANT_2;
         when "1101000" => lookup <= GRANT_3;
         when "1101001" => lookup <= GRANT_3;
         when "1101010" => lookup <= GRANT_3;
         when "1101011" => lookup <= GRANT_3;
         when "1101100" => lookup <= GRANT_2;
         when "1101101" => lookup <= GRANT_2;
         when "1101110" => lookup <= GRANT_2;
         when "1101111" => lookup <= GRANT_2;

         -- request(3) has priority 
         when "1110000" => lookup <= GRANT_NONE_PRI_0;
         when "1110001" => lookup <= GRANT_0;
         when "1110010" => lookup <= GRANT_1;
         when "1110011" => lookup <= GRANT_0;
         when "1110100" => lookup <= GRANT_2;
         when "1110101" => lookup <= GRANT_0;
         when "1110110" => lookup <= GRANT_1;
         when "1110111" => lookup <= GRANT_0;
         when "1111000" => lookup <= GRANT_3;
         when "1111001" => lookup <= GRANT_3;
         when "1111010" => lookup <= GRANT_3;
         when "1111011" => lookup <= GRANT_3;
         when "1111100" => lookup <= GRANT_3;
         when "1111101" => lookup <= GRANT_3;
         when "1111110" => lookup <= GRANT_3;
         when "1111111" => lookup <= GRANT_3;

         when others    => lookup <= GRANT_NONE_PRI_0;
      end case;
   end process;
end Behavioral;


tb_arbiter.v

For some reason I've written this testbench in Verilog.

`timescale 1ns / 1ps

//------------------------------------------------------------------
// arbiter4.vhd : a high performance 4-input arbiter for LUT6 FPGAs
//
// Written by: Mike Field <hamster@snap.net.nz>
//
//--------------------------------------------------------------------
module tb_arbiter;

   reg clk;
   reg reset;
   reg [3:0] request;
   wire [3:0] grant;

   // Instantiate the Unit Under Test (UUT)
   arbiter4 uut (
      .clk(clk), 
      .reset(reset), 
      .request(request), 
      .grant(grant)
   );
   integer i;
   
   initial begin
      // Initialize Inputs
      clk = 0;
      reset = 1;
      request = 8'b0000;

      for(i =0; i < 3; i = i+1) begin
         #5
         clk = 1;
         #5
         clk = 0;
      end

      reset = 0;

      for(i =0; i < 3; i = i+1) begin
         #5
         clk = 1;
         #5
         clk = 0;
      end

      request = 8'b1111;

      for(i =0; i < 10; i = i+1) begin
         #5
         clk = 1;
         #5
         clk = 0;
      end

      request = 8'b0000;

      #5
      clk = 1;
      #5
      clk = 0;

      request = 8'b1111;

      for(i =0; i < 10; i = i+1) begin
         #5
         clk = 1;
         #5
         clk = 0;
      end

      request = 8'b0000;

      #5
      clk = 1;
      #5
      clk = 0;

      request = 8'b1111;

      for(i =0; i < 10; i = i+1) begin
         #5
         clk = 1;
         #5
         clk = 0;
      end

      request = 8'b0000;

      #5
      clk = 1;
      #5
      clk = 0;

      request = 8'b1111;

      for(i =0; i < 10; i = i+1) begin
         #5
         clk = 1;
         #5
         clk = 0;
      end

      request = 8'b0000;

      for(i =0; i < 10; i = i+1) begin
         #5
         clk = 1;
         #5
         clk = 0;
      end
      
      request = 8'b0011;

      for(i =0; i < 10; i = i+1) begin
         #5
         clk = 1;
         #5
         clk = 0;
      end

      request = 8'b0000;

      #5
      clk = 1;
      #5
      clk = 0;

      request = 8'b0011;

      for(i =0; i < 10; i = i+1) begin
         #5
         clk = 1;
         #5
         clk = 0;
      end


      request = 8'b1010;

      for(i =0; i < 10; i = i+1) begin
         #5
         clk = 1;
         #5
         clk = 0;
      end
      
      request = 8'b0010;

      for(i =0; i < 10; i = i+1) begin
         #5
         clk = 1;
         #5
         clk = 0;
      end
   end      
endmodule

Personal tools