Suurima ühisteguri leidmine (GCD)

 english

Algoritm

  while ( x != y ) {
    if ( x < y ) y = y - x;
    else x = x - y;
  }

Liides

Sisend- (x, y) ja väljundsignaalid (xo) ning juhtsignaalid (rst - alusta, rdy - valmis). Sisend-väljundprotokolli aluseks on see, et rst=='0' puhul loetakse sisendid sisesmistesse registritesse ja rdy<='0' indikeerib, et algoritm alustas tööd. Testpink viib rst tagasi '1'-ks ja ootab, kuni rdy saab '1'-ks - algoritm lõpetas töö ja väljundis on tulemus. Loomulikult võib muuta juhtsignaalide polaarsust, kuid siis peab ka testpinki vastavalt muutma.


Graafskeem VHDL


Käitumuslik mudel - ei ole sünteesitav, sisemised signaalid puuduvad.
Sobib ainult esialgse idee kiireks kontrolliks. 

library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.std_logic_arith.all;

entity gcd is 
  port (xi, yi : in unsigned(15 downto 0);
        rst    : in bit;
        xo     : out unsigned(15 downto 0);
        rdy    : out bit := '1';
        clk    : in bit);
end gcd;

library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.std_logic_arith.all;

architecture experiments of gcd is 
begin 

  process
    variable x, y: unsigned(15 downto 0);
  begin
    -- Wait for the new input data
    wait on clk until clk='1' and rst='0';

    x := xi;    y := yi;    rdy <= '0';
    wait on clk until clk='1';

    -- Calculate
    while  x /= y  loop
      if  x < y  then y := y - x;
      else            x := x - y;    end if;
    end loop;

    -- Ready
    xo <= x;    rdy <= '1';
    wait on clk until clk='1';
  end process;

end experiments;

Käitumusliku simulatsiooni tulemus (testpink on allpool):


Testpink VHDL


Kasutatav kõikide mudelite puhul. Testpink peatub,
kui kõikide sisendandmete tulemused on arvutatud. 

library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.std_logic_arith.all;

entity test is    end test;

architecture bench of test is
  signal clk, rst, rdy, hlt: bit := '1';
  signal x, y, res: unsigned(15 downto 0);

  component gcd
    port (xi, yi : in unsigned(15 downto 0);
          rst    : in bit;
          xo     : out unsigned(15 downto 0);
          rdy    : out bit;
          clk    : in bit);
  end component;
begin
  clk <= not clk after 10 ns when hlt='1';

  U1: gcd port map (x, y, rst, res, rdy, clk);

  process
    type int_array is array (0 to 7) of integer;
    constant a: int_array := (27, 33, 245, 121, 52, 333, 125, 422);
    constant b: int_array := (18, 256, 45, 11, 452, 121, 625, 312);
    -- expected results (GCD)  9,  1,  5,  11,  4,   1,  125,   2  
  begin
    wait on clk until clk='0';
    for  i in a'range  loop
      x <= conv_unsigned(a(i),16);
      y <= conv_unsigned(b(i),16);
      rst <= '0';
      wait on clk until clk='0';
      rst <= '1';
      --wait on clk until clk='0';
      while  rdy = '0'  loop
        wait on clk until clk='0';
      end loop;
      wait on clk until clk='0';
    end loop;
    wait on clk until clk='0';
    hlt <= '0';    wait;
  end process;
end bench;

Takteeritud käitumuslik mudel VHDL


Ainult arhitektuur. Sisemiste signaalide käitumine jälgitav igal taktil,
andme- ja juhtosa pole eristatavad, osaliselt sünteesitav (vt. struktuuri).
Selline stiil sobib täielikult algoritmi töö samm-samm haaval kontrollimiseks. 

library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.std_logic_arith.all;

architecture experiments of gcd is 
  signal x, y: unsigned(15 downto 0);
begin 

  process begin
    -- Wait for the new input data
    while  rst = '1'  loop
      wait on clk until clk='1';
    end loop;

    x <= xi;    y <= yi;    rdy <= '0';
    wait on clk until clk='1';

    -- Calculate
    while  x /= y  loop
      if  x < y  then y <= y - x;
      else            x <= x - y;    end if;
      wait on clk until clk='1';
    end loop;
    
    -- Ready
    xo <= x;    rdy <= '1';
    wait on clk until clk='1';
  end process;

end experiments;

Takteeritud käitumusliku mudeli simulatsiooni tulemus:


Käitumuslik automaat VHDL


Ainult arhitektuur. Sisemiste signaalide käitumine jälgitav igal taktil,
andme- ja juhtosa pole eristatavad, kuid olekud on selgelt defineeritud.
Sünteesitav enamike sünteesivahendite poolt ja sobib ka FPGA-l
realiseerimiseks (vt. struktuuri). 

library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.std_logic_arith.all;

architecture experiments of gcd is
  type state_type is (S_wait, S_start, S_ready);
  signal state: state_type;
  signal x, y: unsigned(15 downto 0);
begin 

  process begin
    wait on clk until clk='1';
    case state  is
    -- Wait for the new input data
    when S_wait =>
      if  rst='0'  then
        x <= xi;    y <= yi;    rdy <= '0';    state <= S_start;
      end if;
    -- Calculate
    when S_start =>
      if  x /= y  then
        if  x < y  then    y <= y - x;
        else               x <= x - y;    end if;
        state <= S_start;
      else
        xo <= x;    rdy <= '1';    state <= S_ready;
      end if;
    -- Ready
    when S_ready =>    state <= S_wait;
    end case;
  end process;

end experiments;

Käitumusliku automaadi mudeli simulatsiooni tulemus:

Sama simulatsiooni algus - olekute muutumine on näha:


Salidid algoritmi kirjelduse ja realisatsioonide variantidest (2 slaidi lehel).

Ülejäänud VHDL-failid

Järgmised viis mudelit vastavad täielikult register-siirete taseme (RTL) abstraktsioonile - on selgelt eristuv juhtautomaat ja andmeosa koosned üksikutest komponentides (registrid, multipleksorid, lahutajad, jne). Samuti on olemas sisemised juht- ja kontrollsignaalid. Kõiks mudelid on sünteesitavad.

RTL #1 - üks ALU, 3 takti iteratsiooni kohta (vt. struktuuri).

RTL #2 - üks ALU, 2 takti iteratsiooni kohta (vt. struktuuri).

RTL #3 - võrdleja kontrollib lahutajat, 1 takt iteratsiooni kohta. Väike kuid aeglane andmeosa (vt. struktuuri).

RTL #4 ja RTL #5 - spekuleeriv arvutamine, st kõigepealt tehakse mõlemad lahutamised, siis toimub otsustamine. Erinevus on ostustajate/võrdlejate realiseerimises (vt. struktuuri #4 ja struktuuri #5).

Erinevate variantide sünteeside tulemused ja struktuurskeemid.

Komponentide võrdlemiseks kasutatud VHDL failid - lahutaja ja kaks võrdlejat, univeraalne ALU ning testpink kontrolliks.

Tühi komponent VHDL





Sisaldab sisend-väljund liidest, hea kasutada suvalise
algoritmi esimese mudeli loomiseks koos testpingiga eespool. 

library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.std_logic_arith.all;

entity gcd is 
  port (xi, yi : in unsigned(15 downto 0);
        rst    : in bit;
        xo     : out unsigned(15 downto 0);
        rdy    : out bit := '1';
        clk    : in bit);
end gcd;

library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.std_logic_arith.all;

architecture experiments of gcd is
  signal x, y: unsigned(15 downto 0);  
  -- The other internal signals
begin 

  process
    -- Even variables can be used
  begin
    -- Wait for the new input data
    wait on clk until clk='1' and rst='0';

    x <= xi;    y <= yi;    rdy <= '0';
    wait on clk until clk='1';

    -- Calculate
    --
    -- Insert your algorithm here.
    -- Use 'wait' statment and additional signal
    -- to see them in the waveform...
    -- wait on clk until clk='1';
 
    -- Ready
    xo <= x;    rdy <= '1';
    wait on clk until clk='1';
  end process;

end experiments;

Erinevate GCD mudelite SystemVerilog failid - käitumuslik mudel, testpink, takteeritud käitumuslik mudel, käitumuslik automaat, RTL #1, RTL #2, RTL #3, RTL #4, RTL #5 ja tühi komponent.

Komponentide võrdlemiseks kasutatud SystemVerilog failid - lahutaja ja kaks võrdlejat, universaalne ALU ning testpink kontrolliks.