Rechnen - 1

Immer wieder braucht man trotz aller Tricks einen Divisionsalgorithmus in VHDL. Leider geht das nicht so einfach wie eine Addition oder eine Multiplikation. Mit irgendwelchen Tools erzeugte Algorithmen sind u.U. nicht so ohne weiteres nicht portierbar, oder man möchte einfach nur mal sehen, wie sowas geht.

Hier habe ich eine Integer Division, die unter dem Namen Radix-2 Division bekannt ist, implementiert. Dieser Algorithmus benötigt einen Rechenschritt pro Bit. Siehe dazu auch hier bei der Uni Ulm.

Eine Division ist an sich nur eine wiederholte Subtraktion. Ähnlich wie in der schriftlichen Division, die wir aus der Schule kennen, beginnt auch die binäre Division bei den höchstwertigen Stellen und gibt pro Rechenschritt eine weitere Quotientenstelle aus. Der Divisionsweg teilt sich in in zwei Abschnitte auf:
1) Scheibe die oberen Bits des Dividenden in den Rest
2) Ziehe den Divisor von dem Wert im Rest ab.
    Das MSB dieser Subtraktion wird ein Bit im Quotienten.

 Dividend
---------- = Quotient und Rest
 Divisor

Gestartet wird die Division, nachdem der Dividend und der Divisor zugewiesen wurden, mit dem Signal start='1'. Es reicht aus, wenn start für einen Taktzyklus aktiv ist. Während der Division ist busy='1', zum Abschluss der Division wird start kontrolliert und ggf. gewartet, bis start wieder auf '0' gegangen ist.

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;

entity Divider is
    Generic ( b  : natural range 4 to 32 := 32 ); -- Breite 
    Port ( start     : in   STD_LOGIC;
           divisor   : in   STD_LOGIC_VECTOR (b-1 downto 0);
           dividend  : in   STD_LOGIC_VECTOR (b-1 downto 0);
           quotient  : out  STD_LOGIC_VECTOR (b-1 downto 0);
           remainder : out  STD_LOGIC_VECTOR (b-1 downto 0);
           busy      : out  STD_LOGIC;
           clk       : in   STD_LOGIC);
end Divider;

architecture Behave_Unsigned of Divider is
signal dd : unsigned(b-1 downto 0); -- dividend
signal dr : unsigned(b-1 downto 0); -- divisor
signal q  : unsigned(b-1 downto 0); -- qoutient
signal r  : unsigned(b-1 downto 0); -- remainder
signal bits : integer range b downto 0;
type zustaende is (idle, prepare, shift, sub, done);
signal z : zustaende;

begin

   process 
   variable diff : unsigned(b-1 downto 0);
   begin
      wait until rising_edge(clk);
      case z is 
         when idle => 
            if (start='1') then 
               z <= prepare; 
               busy <= '1';
            end if;
            dd <= unsigned(dividend);
            dr <= unsigned(divisor);

         when prepare =>
            q    <= (others=>'0');
            r    <= (others=>'0');
            z    <= shift;            
            bits <= b;
            -- Sonderfall: Division durch Null
            if (dr=0) then  
               q <= (others=>'1');
               r <= (others=>'1');
               z <= done;
            -- Sonderfall: Divisor größer als Dividend
            elsif (dr>dd) then 
               r <= dd;
               z <= done;
            -- Sonderfall: Divisor gleich Dividend
            elsif (dr=dd) then
               q <= to_unsigned(1,b);
               z <= done;
            end if;

         when shift =>
            -- erst mal die beiden Operanden 
            -- für die Subtraktion zurechtrücken
            if ( (r(b-2 downto 0)&dd(b-1)) < dr ) then
               bits <= bits-1;
               r    <= r(b-2 downto 0)&dd(b-1);
               dd   <= dd(b-2 downto 0)&'0';
            else
               z    <= sub;
            end if;

         when sub =>
            if (bits>0) then
               r    <= r(b-2 downto 0)&dd(b-1);
               dd   <= dd(b-2 downto 0)&'0';
               -- Rest minus Divisor
               diff := (r(b-2 downto 0)&dd(b-1)) - dr;  
               if (diff(b-1)='0') then                 
                  -- wenn kein Unterlauf 
                  --> Divisor passt noch rein 
                  --> MSB=0 --> 1 in Ergebnis einschieben
                  q <= q(b-2 downto 0) & '1';
                  r <= diff;
               else
                  -- wenn Unterlauf 
                  --> 0 einschieben, mit altem Wert weiterrechnen
                  q <= q(b-2 downto 0) & '0';
               end if;
               bits <= bits-1;
            else
               z    <= done;
            end if;
            
         when done =>
            busy <= '0';
            -- Handshake: wenn nötig warten, bis start='0'
            if (start='0') then 
               z <= idle; 
            end if;
      end case;
   end process;
   
   quotient  <= std_logic_vector(q);
   remainder <= std_logic_vector(r);
   
end;

Die 32 Bit Implementation der Division benötigt laut Syntheseergebnis folgende Ressourcen:
Number of Slices 189
Number of Slice Flip Flops 138
Number of 4 input LUTs 358

Hier noch ein Auszug der Testbench mit den Sonderfällen am Anfang und einigen Divisionen danach.

  clk <= not clk after 3 ns;
   
  tb : PROCESS
  BEGIN
    dividend <= std_logic_vector(to_unsigned(127,32));
    divisor  <= std_logic_vector(to_unsigned(127,32));
    wait for 5 ns;
    start <= '1';
    wait for 25 ns;
    start <= '0';
    wait for 50 ns;
      
    dividend <= std_logic_vector(to_unsigned(127,32));
    divisor  <= std_logic_vector(to_unsigned(0,32));
    wait for 5 ns;
    start <= '1';
    wait for 25 ns;
    start <= '0';
    wait for 50 ns;
      
    dividend <= std_logic_vector(to_unsigned(127,32));
    divisor  <= std_logic_vector(to_unsigned(255,32));
    wait for 5 ns;
    start <= '1';
    wait for 25 ns;
    start <= '0';
    wait for 50 ns;
      
      
    dividend <= std_logic_vector(to_unsigned(1023,32));
    divisor  <= std_logic_vector(to_unsigned( 128,32));
    wait for 5 ns;
    start <= '1';
    wait for 25 ns;
    start <= '0';
    wait for 222 ns;
    assert (to_integer(unsigned(quotient)) =7)   report "Division fehlerhaft" severity failure;      
    assert (to_integer(unsigned(remainder))=127) report "Division fehlerhaft" severity failure;      
      
    dividend <= std_logic_vector(to_unsigned(1024,32));
    divisor  <= std_logic_vector(to_unsigned( 128,32));
    wait for 5 ns;
    start <= '1';
    wait for 25 ns;
    start <= '0';
    wait for 222 ns;
    assert (to_integer(unsigned(quotient)) =8) report "Division fehlerhaft" severity failure;      
    assert (to_integer(unsigned(remainder))=0) report "Division fehlerhaft" severity failure;

Das ganze sieht in der Wavedarstellung so aus:

Waveform der 32-bit Division

Manchmal wäre es doch interessant, die Anzahl der gesetzen Bits in einem Vektor zu kennen. Die erste Schritt wäre, einen Stall Addierer zu nehmen, und die alle hintereinanderzuhängen. Das macht ein Design natürlich nicht unbedingt schneller, denn wenn da ein Carry langsam durchtrudeln muss.

Fangen wir einfach mal vorn an und zählen die Bits einfach in einer Schleife:

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;

entity CountOnes is
    Port ( i : in  STD_LOGIC_VECTOR (15 downto 0);
           o : out  STD_LOGIC_VECTOR (4 downto 0));
end CountOnes;

architecture Behavioral of CountOnes is

begin
  -- Spartan 3
  -- Number of Slices       42
  -- Number of 4 input LUTs 73
  process (i) 
  variable cnt : integer range 0 to 16 := 0;
  begin
     cnt := 0;
     for c in 0 to 15 loop
       if i(c)='1' then 
         cnt:=cnt+1; 
       end if;
     end loop;
     o <= std_logic_vector(to_unsigned(cnt,5));
  end process;

  -- Spartan 3
  -- Number of Slices       16
  -- Number of 4 input LUTs 28
  process (i) 
  variable cnt : unsigned (4 downto 0);
  begin
     cnt := "00000";
     for c in 0 to 15 loop
       cnt:=cnt+unsigned'("0000"&i(c)); 
     end loop;
     o <= std_logic_vector(cnt);
  end process;

end Behavioral;

Die erste Variante gibt einen recht aufwendigen Multiplexer und braucht 27ns, die zweite Variante die gewünschten Addierer mit 19ns Durchlaufzeit (incl. IO-Pads Treiber!).

Aber es geht noch schneller (16ns), wenn nämlich nicht eine Addiererkette gebildet wird, sondern erst ein paar kleine Teilsummen gebildet und die dann aufsummiert werden:

  process (i) 
  variable c0  : unsigned (2 downto 0);
  variable c1  : unsigned (2 downto 0);
  variable c2  : unsigned (2 downto 0);
  variable c3  : unsigned (2 downto 0);
  variable cnt : unsigned (4 downto 0);
  begin
     cnt := "00000";
     c0  := "000";
     c1  := "000";
     c2  := "000";
     c3  := "000";
     for c in 0 to 3 loop
       c0 := c0+unsigned'("00"&i(c)); 
       c1 := c1+unsigned'("00"&i(c+4)); 
       c2 := c2+unsigned'("00"&i(c+8)); 
       c3 := c3+unsigned'("00"&i(c+12)); 
     end loop;
     cnt:= unsigned'("00"&c0)+unsigned'("00"&c1)+unsigned'("00"&c2)+unsigned'("00"&c3);
     o <= std_logic_vector(cnt);
  end process;

Auf dem uC.net findet sich der entsprechende Thread: Bits in Wort zählen

Hier jetzt mal eine Umsetzung des allseits bekannten Bubblesort-Algorithmus in VHDL.
Zuerst die rein kombinatorische Variante:

library IEEE;
use IEEE.STD_LOGIC_1164.all;

package BSTypes is
  type BSData_Typ is array (0 to 9) of integer range 0 to 127;
end BSTypes;

package body BSTypes is
end BSTypes;




library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;
use work.bstypes.all;

entity Bubblesort is
    Port ( di  : in  BSData_Typ;
           do  : out BSData_Typ );
end Bubblesort;

architecture Behavioral of Bubblesort is
begin

   process (di) 
   variable din  : BSData_Typ;
   variable temp : integer;
   variable n    : integer;
   variable oncemore : boolean;
   begin
      din      := di;
      n        := din'length;
      oncemore := TRUE;
      while oncemore = TRUE and n > 1 loop
         oncemore := FALSE;
         for i in 0 to din'length-2 loop
            if din(i) > din(i+1) then 
               temp     := din(i);   -- Dreieckstausch
               din(i)   := din(i+1);
               din(i+1) := temp;
               oncemore := TRUE;
            end if;
         end loop;
         n := n-1;
      end loop;
      do <= din;
   end process;
   
end Behavioral;

In einem Spartan 3 FPGA braucht diese Lösung abhängig vom Abbruch (über die Variable oncemore) unterschiedlich viele Ressourcen:
Mit Abbruch:      Number of Slices  1293         Number of 4 input LUTs 2272
Ohne Abbruch:   Number of Slices  976           Number of 4 input LUTs 1701

Der offensichtlichste Unterschied ist, dass der in der Software effizientere Abbruch (wenn das Array schon vor Ablauf aller Kombinationen schon komplett sortiert ist) in der Hardware nur Nachteile mit sich bringt.

Nachfolgend eine getaktete Lösung, die auf Kosten der Rechenzeit deutlich weniger Ressourcen braucht. Bubblesort.zip
Insbesondere fällt hier der Unterschied zwischen der Variante mit und der ohneAbbruch wesentlich geringer aus:
Mit Abbruch:      Number of Slices  168           Number of 4 input LUTs 250
Ohne Abbruch:   Number of Slices  167           Number of 4 input LUTs 245

-- Typdefinition BSData_Typ s.o.

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;
use work.bstypes.all;

entity Bubblesort is
    Port ( di    : in  BSData_Typ;
           do    : out BSData_Typ;
           start : in  std_logic;
           done  : out std_logic;
           clk   : in  std_logic);
end Bubblesort;

architecture Behavioral of Bubblesort is
signal busy     : boolean := FALSE;
signal din      : BSData_Typ;
signal n,i      : integer range 0 to din'length;
begin

   process 
   variable temp : integer;
   begin
      wait until rising_edge(clk);
      if (busy=FALSE) then
         if (start='1') then
            din  <= di;
            busy <= TRUE;
            n    <= 0;
            i    <= 0;
         end if;
      else
         if (n < din'length) then
            if (i<din'length-1) then
               if din(i) > din(i+1) then
                  temp     := din(i);   -- Dreieckstausch
                  din(i)   <= din(i+1);
                  din(i+1) <= temp;
               end if;
               i <= i+1;
            else
               i <= 0;
               n <= n+1;
            end if;
         else
            busy <= FALSE;       
            do   <= din;
         end if;
      end if;
   end process;
   
   done <= '1' when start='0' and busy=FALSE else '0';

end Behavioral;

Das ist die Testbench für die kombinatorische Variante:

LIBRARY ieee;
USE ieee.std_logic_1164.ALL;
USE ieee.numeric_std.ALL;
use ieee.math_real.all;
use work.bstypes.all;
 
ENTITY tb_BubbleSort IS
END tb_BubbleSort;
 
ARCHITECTURE behavior OF tb_BubbleSort IS 
    COMPONENT Bubblesort
    Port ( di  : in  BSData_Typ;
           do  : out BSData_Typ );
    END COMPONENT;

   --Inputs
   signal di : BSData_Typ := (3,6,1,8,7,2,4,5,9,0);
   --Outputs
   signal do : BSData_Typ;
   
BEGIN
  -- Instantiate the Unit Under Test (UUT)
   uut: Bubblesort PORT MAP (
          di => di,
          do => do
        );

   -- Stimulus process
   stim_proc: process
    variable rand  : real;
    variable seed1 : positive := 234;
    variable seed2 : positive := 567;
   begin    
      wait for 100 ns;  
      loop
         for i in 0 to 9 loop
            UNIFORM(seed1, seed2, rand);
            di(i) <= integer(TRUNC(rand*127.999));
         end loop;
         wait for 10 ns;
         for i in 0 to 8 loop
            assert do(i)<=do(i+1) report "Falsche Reihenfolge!" severity failure;
         end loop;
       end loop;
   end process;

END;

Und das kommt dabei heraus:

Waveform der Testbench für den kombinatorischen Sortierer

Und hier können die Dateien gezippt heruntergeladen werden: Bubblesort.zip

Eine Wurzel zu ziehen kann recht aufwendig sein. Erschwert wird das Ganze, wenn es in VHDL geschehen soll. Hier eine Gegenüberstellung des Ressourcenverbrauchs einer rein kombinatorischen Lösung verglichen mit einer sequentiellen getakteten Variante in einem Xilinx Spartan3 XC3S200 FPGA.

Hier als Bezugspunkt die parallel implementierte kombinatorische Lösung:

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;

entity SQRT is
    Generic ( b  : natural range 4 to 32 := 16 ); -- Breite 
    Port ( value  : in   STD_LOGIC_VECTOR (15 downto 0);
           result : out  STD_LOGIC_VECTOR (7 downto 0));
end SQRT;

architecture Behave of SQRT is
begin
   process (value)
   variable vop  : unsigned(b-1 downto 0);  
   variable vres : unsigned(b-1 downto 0);  
   variable vone : unsigned(b-1 downto 0);  
   begin
      vone := to_unsigned(2**(b-2),b);
      vop  := unsigned(value);
      vres := (others=>'0'); 
      while (vone /= 0) loop
         if (vop >= vres+vone) then
            vop   := vop - (vres+vone);
            vres  := vres/2 + vone;
         else
            vres  := vres/2;
         end if;
         vone := vone/4;
      end loop;
      result <= std_logic_vector(vres(result'range));
   end process;
end;

Mit diesem Ansatz ergibt sich folgender Ressourcenbedarf:

So eine Wurzel braucht schon Platz...

Und jetzt zum Vergleich die Variante mit der getakteten Berechnung der Wurzel:

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;

entity SQRT is
    Generic ( b  : natural range 4 to 32 := 16 ); -- Breite 
    Port ( clk    : in   STD_LOGIC;
           start  : in   STD_LOGIC;
           value  : in   STD_LOGIC_VECTOR (15 downto 0);
           result : out  STD_LOGIC_VECTOR (7 downto 0);
           busy   : out  STD_LOGIC);
end SQRT;

architecture Behave of SQRT is
signal op  : unsigned(b-1 downto 0); -- 
signal res : unsigned(b-1 downto 0); -- 
signal one : unsigned(b-1 downto 0); -- 

signal bits : integer range b downto 0;
type zustaende is (idle, shift, calc, done);
signal z : zustaende;

begin
   process begin
      wait until rising_edge(clk);
      case z is 
         when idle => 
            if (start='1') then 
               z <= shift; 
               busy <= '1';
            end if;
            one <= to_unsigned(2**(b-2),b);
            op  <= unsigned(value);
            res <= (others=>'0');

         when shift =>
            if (one > op) then
               one <= one/4;
            else
               z   <= calc;
            end if;

         when calc =>
            if (one /= 0) then
               if (op >= res+one) then
                  op   <= op - (res+one);
                  res  <= res/2 + one;
               else
                  res  <= res/2;
               end if;
               one <= one/4;
            else
               z    <= done;
            end if;
            
         when done =>
            busy <= '0';
            -- Handshake: wenn nötig warten, bis start='0'
            if (start='0') then 
               z <= idle; 
            end if;
      end case;
   end process;
   
   result <= std_logic_vector(res(result'range));
end;

Das Design Summary zeigt jetzt einen deutlich kleineren Ressourcenverbrauch an, wobei der Verbrauch an Slices insgesamt nicht mal so sehr viel höher ist:

... aber es geht auch wesentlich kompakter

Die Wurzelberechnung basiert auf diesem C Code von Jack W. Crenshaw:

int sqrt(int num) {
    int op = num;
    int res = 0;
    int one = 1 << 30; // The second-to-top bit is set: 1L<<30 for long

    // "one" starts at the highest power of four <= the argument.
    while (one > op)
        one >>= 2;
   
    while (one != 0) {
        if (op >= res + one) {
            op -= res + one;
            res += 2 * one;
        }
        res >>= 1;
        one >>= 2;
    }
    return res;
}

Manchmal möchte man, dass sich die Wortbreite von Vektoren eines VHDL-Moduls z.B. über ein Generic einstellen lassen. Natürlich kann man das Ganze händisch machen:

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;

entity CalcBW is
    Generic ( COUNT_MAX : natural  := 100;
              COUNT_WIDTH : natural := 7     -- 7 Bits sind nötig.
             );
    Port ( clk   : in  STD_LOGIC;
           count : out STD_LOGIC_VECTOR (31 downto 0) := (others=>'0')
          );
end CalcBW;

architecture Behavioral of CalcBW is
signal   cnt  : unsigned (COUNT_WIDTH-1 downto 0) := (others=>'0');
begin
  process begin
     wait until rising_edge(clk);
     if (cnt < COUNT_MAX) then  cnt <= cnt+1;
     else                       cnt <= (others=>'0'); 
     end if;
  end process;
  count(cnt'range) <= std_logic_vector(cnt);
end Behavioral;

Wesentlich eleganter ist aber, wenn hier z.B. nur der Zählerendwert übergeben und daraus in dem VHDL-Modul die nötige Vektorbreite berechnet wird. Das kann z.B. so gemacht werden:

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;
USE ieee.math_real.log2;
USE ieee.math_real.ceil;

entity CalcBW is
    Generic ( COUNT_MAX : natural := 100
             );
    Port ( clk   : in  STD_LOGIC;
           clear : in  STD_LOGIC;
           count : out STD_LOGIC_VECTOR (31 downto 0) := (others=>'0')
          );
end CalcBW;

architecture Behavioral of CalcBW is
constant COUNT_WIDTH : integer := INTEGER(CEIL(LOG2(REAL(COUNT_MAX+1))));
signal   cnt  : unsigned (COUNT_WIDTH-1 downto 0) := (others=>'0');
begin
  process begin
     wait until rising_edge(clk);
     if (cnt < COUNT_MAX) then  cnt <= cnt+1;
     else                       cnt <= (others=>'0'); 
     end if;
  end process;
  count(cnt'range) <= std_logic_vector(cnt);
end Behavioral;

Mit den in der MATH_REAL Bibliothek enthaltenen Funktionen LOG2 wird zuerst die tatsächliche Bitzahl ausgerechnet und mit CEIL auf das nächste Bit aufgerundet. So erhält man z.B. für die Werte 100 und 126 die nötigen 7 Bits, für einen Wert von 129 dann 8 Bits.