Suurima ühisteguri leidmine (GCD)

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

SystemVerilog

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äitumuslik mudel - ei ole sünteesitav, sisemised signaalid puuduvad.
Sobib ainult esialgse idee kiireks kontrolliks.

`timescale 1 ns / 1 ns

module gcd (
  input logic unsigned [15:0] xi, yi,
  input logic rst,
  output logic unsigned [15:0] xo,
  output logic rdy,
  input logic clk );

  logic unsigned [15:0] x, y;

  initial rdy = 1;

  always begin
    // Wait for the new input data
    while ( rst == 1 ) @(posedge clk);

    x = xi;    y = yi;    rdy = 0;
    @(posedge clk);

    // Calculate
    while ( x != y )
      if ( x < y )  y = y - x;
      else          x = x - y;

    // Ready
    xo = x;    rdy = 1;
    @(posedge clk);
  end

endmodule

Käitumusliku simulatsiooni tulemus (testpink on allpool):

Testpink

VHDL

SystemVerilog

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;

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

`timescale 1 ns / 1 ns

module  testbench;
  logic clk, rst, rdy;
  logic unsigned [15:0] x, y, res;

  // expected results (GCD)
  //   9,   1,   5,  11,   4,   1, 125,   2
  parameter logic unsigned [15:0] a [8] =
    { 27,  33, 245, 121,  52, 333, 125, 422 };
  parameter logic unsigned [15:0] b [8] = 
    { 18, 256,  45,  11, 452, 121, 625, 312 };

  initial clk = 1;  always #10 clk = !clk;

  gcd u1 (x, y, rst, res, rdy, clk);

  initial begin
    rst = 1;
    @(negedge clk);
    for ( int i=0; i<8; i++ ) begin
      x = a[i];  y = b[i];  rst = 0;
      @(negedge clk)  rst = 1;
      // @(negedge clk);
      while ( rdy == 0 )  @(negedge clk);
      @(negedge clk);
    end
    @(negedge clk) $stop;
  end

endmodule

Takteeritud käitumuslik mudel

VHDL

SystemVerilog

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;

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.

`timescale 1 ns / 1 ns

module gcd (
  input logic unsigned [15:0] xi, yi,
  input logic rst,
  output logic unsigned [15:0] xo,
  output logic rdy,
  input logic clk );

  logic unsigned [15:0] x, y;

  always begin
    // Wait for the new input data
    while ( rst == 1 ) @(posedge clk);

    x = xi;    y = yi;    rdy = 0;
    @(posedge clk);

    // Calculate
    while ( x != y ) begin
      if ( x < y )  y = y - x;
      else          x = x - y;
      @(posedge clk);
    end

    // Ready
    xo = x;    rdy = 1;
    @(posedge clk);
  end

endmodule

Takteeritud käitumusliku mudeli simulatsiooni tulemus:

Käitumuslik automaat

VHDL

SystemVerilog

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;

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).

`timescale 1 ns / 1 ns

module gcd (
  input logic unsigned [15:0] xi, yi,
  input logic rst,
  output logic unsigned [15:0] xo,
  output logic rdy,
  input logic clk );

  // State - type & signals
  // Will be interpreted as 32-bit integer in syhtesis and 'default'
  // must be used in case statements to avoid latches. Synthesizer
  // will remove extra 30 bits.
  enum {S_wait, S_start, S_comp, S_ready} state, next_state;

  logic unsigned [15:0] x, y;

  always @(posedge clk)
    case (state)
      // Wait for the new input data
      S_wait :
        if (rst==0) begin
          x <= xi;    y <= yi;    rdy <= 0;    state <= S_start;
        end
      // Calculate
      S_start :
        if ( x != y ) begin
          if ( x < y )  y <= y - x;
          else          x <= x - y;
          state <= S_start;
        end
        else begin
          xo <= x;    rdy <= 1;    state <= S_ready;
        end
      // Ready
      default : state <= S_wait;
    endcase

endmodule

Käitumusliku automaadi mudeli simulatsiooni tulemus:

Sama simulatsiooni algus - olekute muutumine on näha:

Ülejäänud HDL-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 (VHDL/SystemVerilog) - üks ALU, 3 takti iteratsiooni kohta (vt. struktuuri).

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

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

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

Erinevate variantide sünteeside tulemused ja struktuurskeemid (VHDL/SystemVerilog).

Slaidid algoritmi kirjelduse ja realisatsioonide variantidest (VHDL).

Komponentide võrdlemiseks kasutatud HDL failid - lahutaja ja kaks võrdlejat (VHDL/SystemVerilog), univeraalne ALU (VHDL/SystemVerilog) ning testpink kontrolliks (VHDL/SystemVerilog).

Tühi komponent

VHDL

SystemVerilog

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;

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

`timescale 1 ns / 1 ns

module gcd (
  input logic unsigned [15:0] xi, yi,
  input logic rst,
  output logic unsigned [15:0] xo,
  output logic rdy,
  input logic clk );

  logic unsigned [15:0] x, y;

  initial rdy = 1;

  always begin
    // Wait for the new input data
    while ( rst == 1 ) @(posedge clk);

    x = xi;    y = yi;    rdy = 0;
    @(posedge clk);

    // Calculate
    //
    // Insert your algorithm here.
    // Use '@' command and additional signal
    // to see them in the waveform...
    // @(posedge clk);

    // Calculate
    while ( x != y )
      if ( x < y )  y = y - x;
      else          x = x - y;

    // Ready
    xo = x;    rdy = 1;
    @(posedge clk);
  end

endmodule