Diseño e implementación de un procesador RISC desde cero (II) 
En esta segunda entrega de la serie se profundiza en el diseño de la unidad de control, en la implementación en VHDL de los diferentes elementos y en la realización de una prueba de concepto sobre un simulador.

>>> Enlace a la primera entrega de la serie.

Lógica combinatoria: los multiplexores

Un multiplexor es un circuito combinacional con varias entradas y una salida que permite, mediante una entrada adicional de selección, decidir qué entrada se enruta a la salida.

El código VHDL para un multiplexor de, por ejemplo, 3 entradas sería el siguiente:

library ieee;
use ieee.std_logic_1164.all;

entity Mux3Inputs is
    generic (
        NBits : integer := 16
    );
    port (
        Sel     : in std_logic_vector(1 downto 0);
        DataIn0 : in std_logic_vector((NBits - 1) downto 0);
        DataIn1 : in std_logic_vector((NBits - 1) downto 0);
        DataIn2 : in std_logic_vector((NBits - 1) downto 0);
        DataOut : out std_logic_vector((NBits - 1) downto 0)
    );
end entity;

architecture Architecture1 of Mux3Inputs is
begin
    DataOut <= DataIn0 when (Sel = "00") else
               DataIn1 when (Sel = "01") else
               DataIn2;
end architecture;


Lógica combinatoria: el expansor del signo

El expansor del signo (EXP) es un bloque combinacional que expande el signo de un valor de M bits a N bits siendo M < N.

En nuestro caso, el expansor del signo incluye una entrada de selección de un bit para elegir entre M=12 (instrucciones de salto relativo) y M=15 (sólo para la instrucción LOADI).

library ieee;
use ieee.std_logic_1164.all;

entity SignExp is
    generic (
        NBitsToExpand0 : integer := 15;
        NBitsToExpand1 : integer := 12;
        NBits : integer := 16
    );
    port (
        SelIn   : in std_logic;
        DataIn  : in std_logic_vector((NBits - 1) downto 0);
        DataOut : out std_logic_vector((NBits - 1) downto 0)
    );
end SignExp;

architecture Architecture1 of SignExp is
signal Expansion0 : std_logic_vector((NBits - NBitsToExpand0 - 1) downto 0);
signal Expansion1 : std_logic_vector((NBits - NBitsToExpand1 - 1) downto 0);
begin
    Expansion0 <= (others => DataIn(NBitsToExpand0 - 1));
    Expansion1 <= (others => DataIn(NBitsToExpand1 - 1));
    DataOut <= Expansion0 & DataIn((NBitsToExpand0 - 1) downto 0) when (SelIn = '0') else
               Expansion1 & DataIn((NBitsToExpand1 - 1) downto 0);
end Architecture1;


Lógica combinatoria: ALU

La ALU es en este caso incluye dentro dos multiplexores, un sumador y un negador.

Partiendo de este diseño, la implementación en VHDL es directa.

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity Alu is
    generic (
        NBits : integer := 16
    );
    port (
        DIn   : in std_logic_vector((NBits - 1) downto 0);
        SIn   : in std_logic_vector((NBits - 1) downto 0);
        RAIn  : in std_logic_vector((NBits - 1) downto 0);
        DOut  : out std_logic_vector((NBits - 1) downto 0);
        SelIn : in std_logic_vector(3 downto 0)
    );
end entity;

architecture Architecture1 of Alu is
    component Adder is
        generic (
            NBits : integer := 16
        );
        port (
            A : in std_logic_vector((NBits - 1) downto 0);
            B : in std_logic_vector((NBits - 1) downto 0);
            Y : out std_logic_vector((NBits - 1) downto 0)
        );
    end component;
    component Neg is
        generic (
            NBits : integer := 16
        );
        port(
            DataIn  : in std_logic_vector((NBits - 1) downto 0);
            DataOut : out std_logic_vector((NBits - 1) downto 0)
        );
    end component;
    signal AddOut : std_logic_vector((NBits - 1) downto 0);
    signal SInNeg : std_logic_vector((NBits - 1) downto 0);
    signal FirstOperand : std_logic_vector((NBits - 1) downto 0);
    signal SMuxOut : std_logic_vector((NBits - 1) downto 0);
begin
    -- mux for the first operand of the adder
    FirstOperand <= std_logic_vector(to_signed(1, NBits)) when (SelIn = "0111") else                              -- inc
                    std_logic_vector(to_signed(-1, NBits)) when (SelIn = "1000") else                             -- dec
                    DIn when ((SelIn = "0001") or (SelIn = "0010") or (SelIn = "1100") or (SelIn = "1101")) else  -- add, sub, jz, jn
                    (others => '0');                                                                              -- assign
    -- neg Y
    Negate : Neg generic map (
        NBits => NBits
    )
    port map (
        DataIn => SIn,
        DataOut => SInNeg
    );
    -- src mux
    SMuxOut <= SInNeg when (SelIn = "0010") else  -- sub
               (others => '0') when ((SelIn = "1100") and (RAIn /= std_logic_vector(to_unsigned(0, NBits)))) or ((SelIn = "1101") and (RaIn(NBits - 1) = '0')) else  -- jz, jn
               SIn;
    -- adder
    Add : Adder generic map (
        NBits => NBits
    )
    port map (
        A => FirstOperand,
        B => SMuxOut,
        Y => AddOut
    );
    -- final mux
    DOut <= AddOut when ((SelIn = "0000") or (SelIn = "0001") or (SelIn = "0010") or (SelIn = "0111") or (SelIn = "1000") or (SelIn = "1100") or (SelIn = "1101")) else
            (DIn and SIn) when (SelIn = "0011") else
            (DIn or SIn) when (SelIn = "0100") else
            (DIn xor SIn) when (SelIn = "0101") else
            (not(SIn)) when (SelIn = "0110") else
            ('0' & SIn(15 downto 1)) when (SelIn = "1001") else         -- slr
            (SIn(15) & SIn(15 downto 1)) when (SelIn = "1010") else     -- sar
            (SIn(14 downto 0) & '0') when (SelIn = "1011") else         -- sll
            (others => '0');
end architecture;

Nótese que el componente “Neg” es el negador y calcula el complemento a dos (también se trata, a su vez, de un circuito combinacional)

Lógica secuencial: los registros

Un registro no es más que una colección de biestables D en paralelo, uno por cada bit.

La forma más portable de implementar una entrada “enable” es poniendo un multiplexor en la entrada D que seleccione entre la entrada exterior y realimentar la propia Q. De esta forma simulamos un “enable” con lógica “estándar”.

La implementación en VHDL de biestables D es directa:

library ieee;
use ieee.std_logic_1164.all;

entity Reg is
    generic (
        NBits : integer := 16
    );
    port (
        Enable  : in std_logic;
        Clk     : in std_logic;
        DataIn  : in std_logic_vector((NBits - 1) downto 0);
        DataOut : out std_logic_vector((NBits - 1) downto 0)
    );
end Reg;

architecture Architecture1 of Reg is
signal QBus : std_logic_vector((NBits - 1) downto 0);
signal DBus : std_logic_vector((NBits - 1) downto 0);
signal PreDBus : std_logic_vector((NBits - 1) downto 0);
begin
    process (Clk)
    begin
        if (Clk'event and (Clk = '1')) then
            QBus <= DBus;
        end if;
    end process;

    DBus <= PreDBus when (Enable = '1') else QBus;
    PreDBus <= DataIn;
    DataOut <= QBus;
end Architecture1;


Lógica secuencial: la memoria

La unidad de memoria viene con una RAM y una ROM. Una memoria ROM no requiere secuencialidad y puede ser implementada como una LUT de forma combinatoria:

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity Rom is
    port (
        AddressIn : in std_logic_vector(12 downto 0);
        DataOut   : out std_logic_vector(15 downto 0)
    );
end entity;

architecture Architecture1 of Rom is
type RomType is array (0 to 8191) of std_logic_vector(15 downto 0);
constant Data : RomType := (
    "0001000000000000",      --     load
    "0010000000001000",      --     op ra, ra, dec
    "0011000000000000",      --     store
    others => "0000000000000000"
);
begin
    DataOut <= Data(to_integer(unsigned(AddressIn)));
end architecture;

La memoria RAM sí requiere de la señal de reloj ya que es un circuito secuencial. La implementación VHDL usada es la recomendada por la mayoría de los fabricantes (usando un array de std_logic_vector):

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity Ram is
    generic (
        GPOutAddress : integer := 4096
    );
    port (
        AddressIn   : in std_logic_vector(12 downto 0);
        DataOut     : out std_logic_vector(15 downto 0);
        DataIn      : in std_logic_vector(15 downto 0);
        WriteEnable : in std_logic;
        GPOut       : out std_logic_vector(15 downto 0);
        Clk         : in std_logic
    );
end entity;

architecture Architecture1 of Ram is
type RamType is array(0 to 8191) of std_logic_vector(15 downto 0);
signal Data : RamType;
begin
    process (Clk)
    begin
        if ((Clk'event) and (Clk = '1')) then
            if (WriteEnable = '1') then
                Data(to_integer(unsigned(AddressIn))) <= DataIn;
            end if;
        end if;
    end process;

    DataOut <= Data(to_integer(unsigned(AddressIn)));
    GPOut <= Data(GPOutAddress);
end architecture;


La RAM incluye un puerto “GPOut” que mapea la dirección de memoria 4096 de la RAM en un puerto de salida de 16 bits. Este añadido se usará más adelante, en la prueba de concepto, para facilitar la depuración del procesador.

La unidad de control

Como se vio en la primera entrega, la unidad de control es realmente una FSM (máquina de estados finita) cuyas salidas gobiernan las entradas “enable” de los registros, las entradas de selección de los multiplexores y el resto de la lógica del procesador.

La FSM de la unidad de control va avanzando el contador de programa, carga las instrucciones en el IR y ejecuta el microcódigo de cada instrucción. Los estados de la FSM comunes a cualquier instrucción que se ejecute son los siguientes (extraído del anterior post):

0. MUX6 := "0", Habilitar PC

1. MUX1 = PC, Habilitar ADDR

2. Habilitar DATAin

3. Habilitar IR

4. MUX5 := FSM, ALU := inc, MUX4 := PC, Habilitar PC

5. EJECUTAR EL MICROCÓDIGO DE LA INSTRUCCIÓN ALMACENADA EN IR

6. Ir al estado 1

A continuación puede verse el grafo completo de la FSM.

El estado 0 es al estado que se va en el reset. A continuación pueden verse también las señales que unen la unidad de control con el resto de la lógica del procesador:

Se ha optado por implementar la FSM como una máquina de tipo Moore (la salida depende sólo del estado actual y el estado siguiente depende de las entradas y del estado actual)

library ieee;
use ieee.std_logic_1164.all;

entity FSM is
    port (
        DataOutEnable  : out std_logic;
        DataInEnable   : out std_logic;
        RAEnable       : out std_logic;
        RBEnable       : out std_logic;
        RCEnable       : out std_logic;
        SPEnable       : out std_logic;
        PCEnable       : out std_logic;
        AddrEnable     : out std_logic;
        IREnable       : out std_logic;
        Mux1Sel        : out std_logic_vector(1 downto 0);
        Mux2Sel        : out std_logic_vector(1 downto 0);
        Mux3Sel        : out std_logic_vector(2 downto 0);
        Mux4Sel        : out std_logic_vector(2 downto 0);
        Mux5Sel        : out std_logic;
        Mux6Sel        : out std_logic;
        AluOpSel       : out std_logic_vector(3 downto 0);
        MemWriteEnable : out std_logic;
        SignExpSel     : out std_logic;
        IRValue        : in std_logic_vector(15 downto 0);
        Clk            : in std_logic;
        Reset          : in std_logic
    );
end entity;

architecture Architecture1 of FSM is
    signal QBus : std_logic_vector(4 downto 0);
    signal DBus : std_logic_vector(4 downto 0);
begin

    process (Clk, Reset)
    begin
        if (Clk'event and (Clk = '1')) then
            if (Reset = '1') then
                QBus <= (others => '0');
            else
                QBus <= DBus;
            end if;
        end if;
    end process;

    -- next state logic
    -- for state "00000"   MUX6 := "0", Enable PC
    DBus <= "00001" when ((QBus = "00000") or (QBus = "00101") or (QBus = "01000") or (QBus = "01001") or (QBus = "01011") or (QBus = "01110") or (QBus = "10010") or (QBus = "10011") or (QBus = "10100") or (QBus = "10101")) else                -- MUX1 := PC, Enable ADDR
            "00010" when (QBus = "00001") else        -- Enable DATAIN
            "00011" when (QBus = "00010") else        -- Enable IR
            "00100" when (QBus = "00011") else        -- MUX5 := FSM, ALU := inc, MUX4 := PC, Enable PC
            -- LOADI states
            "00101" when ((QBus = "00100") and (IRValue(15) = '1')) else                  -- MUX2 := EXP, SignSel := 15 bits, Enable RA
            -- LOAD states
            "00110" when ((QBus = "00100") and (IRValue(15 downto 12) = "0001")) else     -- MUX1 := RB, Enable ADDR
            "00111" when (QBus = "00110") else                                            -- Enable DATAIN
            "01000" when (QBus = "00111") else                                            -- MUX2 := DATAIN, Enable RA
            -- OP states
            "01001" when ((QBus = "00100") and (IRValue(15 downto 12) = "0010")) else     -- MUX2 := ALU, MUX3 := dst, MUX4 := src, MUX5 := IR(3..0), Enable dst
            -- STORE states
            "01010" when ((QBus = "00100") and (IRValue(15 downto 12) = "0011")) else     -- MUX1 := RB, Enable ADDR, Enable DATAOUT
            "01011" when (QBus = "01010") else                                            -- WE := 1
            -- PUSH states
            "01100" when ((QBus = "00100") and (IRValue(15 downto 12) = "0100")) else     -- MUX4 := SP, MUX5 := FSM, ALU := inc, Enable SP
            "01101" when (QBus = "01100") else                                            -- MUX1 := SP, Enable ADDR, Enable DATAOUT
            "01110" when (QBus = "01101") else                                            -- WE := 1
            -- POP states
            "01111" when ((QBus = "00100") and (IRValue(15 downto 12) = "0101")) else     -- MUX1 := SP, Enable ADDR
            "10000" when (QBus = "01111") else                                            -- Enable DATAIN
            "10001" when (QBus = "10000") else                                            -- Enable RA, MUX2 := DATAIN
            "10010" when (QBus = "10001") else                                            -- MUX4 := SP, MUX5 := FSM, ALU := dec, Enable SP
            -- J states
            "10011" when ((QBus = "00100") and (IRValue(15 downto 12) = "0110")) else     -- MUX4 := EXP, SignSel := 12 bits, MUX3 := PC, MUX5 := FSM, ALU := add, Enable PC
            -- JZ states
            "10100" when ((QBus = "00100") and (IRValue(15 downto 12) = "0111")) else     -- MUX4 := EXP, SignSel := 12 bits, MUX3 := PC, MUX5 := FSM, ALU := add if RA=0, Enable PC
            -- JN states
            "10101" when ((QBus = "00100") and (IRValue(15 downto 12) = "0000")) else     -- MUX4 := EXP, SignSel := 12 bits, MUX3 := PC, MUX5 := FSM, ALU := add if RA<0, Enable PC
            "00000";

    -- output logic
    DataOutEnable <= '1' when (QBus = "01010") or (QBus = "01101") else
                     '0';
    DataInEnable <= '1' when (QBus = "00010") or (QBus = "00111") or (QBus = "10000") else
                    '0';
    RAEnable <= '1' when (QBus = "00101") or (QBus = "01000") or (QBus = "10001") or ((QBus = "01001") and (IRValue(10 downto 8) = "000")) else
                '0';
    RBEnable <= '1' when (QBus = "01001") and (IRValue(10 downto 8) = "001") else
                '0';
    RCEnable <= '1' when (QBus = "01001") and (IRValue(10 downto 8) = "010") else
                '0';
    SPEnable <= '1' when (QBus = "01100") or (QBus = "10010") or ((QBus = "01001") and (IRValue(10 downto 8) = "011")) else
                '0';
    PCEnable <= '1' when (QBus = "00000") or (QBus = "00100") or (QBus = "10011") or (QBus = "10100") or (QBus = "10101") or ((QBus = "01001") and (IRValue(10 downto 8) = "100")) else
                '0';
    AddrEnable <= '1' when (QBus = "00001") or (QBus = "00110") or (QBus = "01010") or (QBus = "01101") or (QBus = "01111") else
                  '0';
    IREnable <= '1' when (QBus = "00011") else
                '0';
    Mux1Sel <= "00" when (QBus = "00110") or (QBus = "01010") else
               "01" when (QBus = "01101") or (QBus = "01111") else
               "10";
    Mux2Sel <= "00" when (QBus = "01000") or (QBus = "10001") else
               "01" when (QBus = "01001") else
               "10";
    Mux3Sel <= "100" when (QBus = "10011") or (QBus = "10100") or (QBus = "10101") else
               IRValue(10 downto 8);
    Mux4Sel <= "011" when (QBus = "01100") or (QBus = "10010") else
               "100" when (QBus = "00100") else
               "101" when (QBus = "10011") or (QBus = "10100") or (QBus = "10101") else
               IRValue(6 downto 4);
    Mux5Sel <= '0' when (QBus = "01001") else
               '1';
    Mux6Sel <= '0' when (QBus = "00000") else
               '1';
    AluOpSel <= "0111" when (QBus = "00100") or (QBus = "01100") else
                "1000" when (QBus = "10010") else
                "0001" when (QBus = "10011") else
                "1100" when (QBus = "10100") else
                "1101" when (QBus = "10101") else
                "0000";
    MemWriteEnable <= '1' when (QBus = "01011") or (QBus = "01110") else
                      '0';
    SignExpSel <= '0' when (QBus = "00101") else
                  '1';
end architecture;

Al igual que en otras ocasiones, una vez tenemos el grafo de la FSM, su implementación en VHDL es totalmente mecánica.

Prueba de concepto

Como primera aproximación se ha creado un fichero Rom.vhd que contiene, escrito a mano, el código máquina del siguiente código ensamblador:

    # GPOut := 10
    loadi 12288
    op rb, ra, assign
    loadi 10
    store
loop:
    # if (GPOut == 0) then goto loopEnd
    loadi 12288
    op rb, ra, assign
    load
    jz loopEnd
    # decrementar GPOut
    loadi 12288
    op rb, ra, assign
    load
    op ra, ra, dec
    store
    # bucle
    j loop
loopEnd:
    j loopEnd


Para este programa el código VHDL de la ROM quedaría como sigue:

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity Rom is
    port (
        AddressIn : in std_logic_vector(12 downto 0);
        DataOut   : out std_logic_vector(15 downto 0)
    );
end entity;

architecture Architecture1 of Rom is
type RomType is array (0 to 8191) of std_logic_vector(15 downto 0);
constant Data : RomType := (
    -- simple counter
    "1011000000000000",      --     loadi 12288
    "0010000100000000",      --     op rb, ra, assign
    "1000000000001010",      --     loadi 10
    "0011000000000000",      --     store
                             -- loop:
    "1011000000000000",      --     loadi 12288
    "0010000100000000",      --     op rb, ra, assign
    "0001000000000000",      --     load
    "0111000000000110",      --     jz loopEnd          (+6)
    "1011000000000000",      --     loadi 12288
    "0010000100000000",      --     op rb, ra, assign
    "0001000000000000",      --     load
    "0010000000001000",      --     op ra, ra, dec
    "0011000000000000",      --     store
    "0110111111110110",      --     j loop              (-10)
                             -- loopEnd:
    "0110111111111111",      --     j loopEnd           (-1)
    others => "0000000000000000"
);
begin
    DataOut <= Data(to_integer(unsigned(AddressIn)));
end architecture;

El puerto de salida está en la dirección 4096 de nuestra RAM pero como la RAM está situada después de la ROM, la dirección de memoria de este puerto de salida será realmente 8192 + 4096 = 12288.

Ejecutando la simulación

El paquete de software usado para realizar la simulación es el GHDL, un compilador y simulador VHDL open source que genera ficheros VCD de eventos. Estos ficheros VCD contienen las señales digitales de todo el circuito simulado y son visualizables con herramientas como el GtkWave.

El testbench utilizado se encarga simplemente de generar el tren de pulsos del reloj y de realizar un reset al principio.

Reset <= '0' after 3 ns;
Finished <= '1' after 2 us;
Clk <= not Clk after 1 ns when Finished /= '1' else
       '0';


A continuación pueden verse las señales de nuestra CPU al ejecutar una instrucción LOADI justo después del reset:

Si observamos el puerto de salida GPOut y alejamos el zoom se puede ver cómo el procesador ha ejecutado el programa correctamente (cuenta descendente desde 10 hasta 0 y se detiene).



Ya hemos conseguido que nuestro provesador V1 funcione en un simulador, ahora sólo nos queda implementarlo en una FPGA, pero eso será en la próxima entrega :-).

En la sección soft puede descargarse todo el código VHDL del proyecto.

>>> Enlace a la tercera entrega de la serie.

[ añadir comentario ] ( 1622 visualizaciones )   |  [ 0 trackbacks ]   |  enlace permanente
  |    |    |    |   ( 3 / 1650 )
Diseño e implementación de un procesador RISC desde cero (I) 
Mediante este post empiezo a realizar una serie de entradas en las que iré abordando el diseño y la implementación en VHDL de un procesador RISC sencillo al que he llamado V1. La complejidad y lo extenso del tema obligan a dividir el proyecto en varios posts que iré publicando a medida que vaya alcanzando los diferentes hitos.

El objetivo final es conseguir un procesador funcional dentro de una FPGA (en mi caso, dentro de una Sparten-3E de Xilinx) y de desarrollar como mínimo un ensamblador y, si se tercia, un pequeño compilador.

Procesador RISC

Se plantea un procesador de tipo RISC de 16 bits con 5 registros (RA, RB, RC, SP y PC) y 9 instrucciones. Las características generales del procesador son las siguientes:

- 5 registros de 16 bits con signo (RA, RB, RC, SP y PC) entre los que se incluyen el puntero de pila (SP) y el contador de programa (PC).

- Memoria interna incorporada: 8192 palabras de 16 bits (16Kb) de ROM y 8192 palabras de 16 bits (16Kb) de RAM. La memoria no es accesible por bytes sino por palabras de 16 bits.

- 9 instrucciones tipo RISC (instrucciones de acceso a los datos separadas de las instrucciones de manipulación de los datos): LOADI, LOAD, STORE, OP, PUSH, POP, J, JZ y JN.

Repertorio de instrucciones

LOADI value
Carga en el registro RA el valor indicado como operando de 15 bits.
1vvv vvvv vvvv vvvv
RA := value (15 bits con expansión del signo)

LOAD
Carga en el registro RA el valor almacenado en la posición de memoria apuntada por el registro RB.
0001 xxxx xxxx xxxx
RA := [RB]

OP dst, src, ope
Realiza una operación entre registros.
0010 0ddd 0sss oooo
ddd, sss:
000 RA
001 RB
010 RC
011 SP (puntero de pila)
100 PC (contador de programa)
oooo:
0000 assign (dst := src)
0001 add (dst := dst + src)
0010 sub (dst := dst - src)
0011 and (dst := dst & src)
0100 or (dst := dst | src)
0101 xor (dst := dst ^ src)
0110 not (dst := !src)
0111 inc (dst := src + 1)
1000 dec (dst := src - 1)
1001 slr (dst := src slr 1)
1010 sar (dst := src sar 1)
1011 sll (dst := src sll 1)
1100 add if RA = 0 (dst := dst + src if RA = 0, else dst := dst) (jz)
1101 add if RA < 0 (dst := dst + src if RA < 0, else dst := dst) (jn)

STORE
Almacena en la posición de memoria apuntada por RB el valor que hay en RA.
0011 xxxx xxxx xxxx
[RB] := RA

PUSH
Empuja en la pila el valor que hay en RA.
0100 xxxx xxxx xxxx
SP := SP + 1, [SP] := RA

POP
Extrae un valor de la pila y lo pone en RA.
0101 xxxx xxxx xxxx
RA := [SP], SP := SP - 1

J value
Salto relativo incondicional a otra posición de memoria.
0110 vvvv vvvv vvvv
PC := PC + value (12 bits con expansión de signo)

JZ value
Salto relativo condicional (si RA = 0) a otra posición de memoria.
0111 vvvv vvvv vvvv
Si RA = 0 entonces PC := PC + value (12 bits con expansión de signo)

JN value
Salto relativo condicional (si RA < 0) a otra posición de memoria.
0000 vvvv vvvv vvvv
Si RA < 0 entonces PC := PC + value (12 bits con expansión de signo)

Como se puede comprobar se trata de un repertorio de instrucciones muy sencillo. En el que se ha optado por hacer una instrucción “OP” que abarque todas las posibles operaciones de la ALU: No es casualidad que las dos últimas operaciones de la instrucción “OP” sean las utilizadas internamente por las instrucciones JZ y JN. Esta simplificación facilita mucho el diseño de la unidad de control.

Se ha optado, además, por utilizar 5 registros en lugar de 4 ya que, aunque un juego de registros (RA, RB, SP, PC) de 4 es más que suficiente para obtener un procesador funcional, lo cierto es que de cara a la implementación de un compilador y el uso de marcos de pila (stack frames) se agradece poder disponer de un registro que permita localizar cómodamente los parámetros y las variables locales sin estar haciendo muchas filigranas (la función que realiza el registro BP en la arquitectura x86).

Un compilador podrá utilizar los registros RA y RB para los cálculos de propósito general y RC como puntero base para acceder a los parámetros actuales y las variables locales, sin necesidad de hacer malabarismos con el puntero de pila (SP).

Ejemplos de código

Un bucle sencillo:
    # x = 10
    loadi x
    op rb, ra, assign
    loadi 10
    store
loop:
    # if x = 0 goto loopEnd
    loadi x
    op rb, ra, assign
    load
    jz loopEnd
    # x--
    loadi x
    op rb, ra, assign
    load
    op ra, ra, dec
    store
    # goto loop
    j loop
loopEnd:


Una indirección:
    # x[ i ] = 10
    loadi i
    op rb, ra, assign
    load
    op rc, ra, assign
    loadi x
    op rb, ra, assign
    op rb, rc, add
    loadi 10
    store


Restricciones de diseño

De cara a realizar el diseño del procesador se han seguido las siguientes directrices:

- Que el código VHDL sea totalmente síncrono y sintetizable. Utilizando siempre una arquitectura de tipo RTL para que pueda implementarse en cualquier FPGA de cualquier fabricante.

- Sin pipeline ni ningún otro tipo de paralelización u optimización hardware.

- Sin caché: Sólo RAM, ROM y registros.

Ruta de datos

La ruta de datos que se ha usado partiendo del repertorio de instrucciones es la siguiente:



ALU

La unidad aritmético-lógica (ALU) se encarga de realizar los cálculos mediante lógica combinatoria: sumas, restas, operaciones de bit, etc.



Módulo de memoria

La memoria está compuesta por 32 Kbytes repartidos en 16 KBytes para ROM y 16 KBytes para RAM. La memoria es solo accesible a nivel de palabra de 16 bits por lo que realmente tenemos un espacio de 16384 palabras con 16 bits por palabra: 8192 palabras de ROM y 8192 palabras de RAM.



Microcódigo

Cada una de las instrucciones descritas anteriormente tendrá un microcódigo asociado que serán las órdenes de carga de los latches, las entradas de selección de los multiplexores, etc. necesarias para que cada instrucción de ejecute. A continuación se puede ver cómo es el microcódigo de cada una de las instrucciones:

LOADI value
MUX2 := EXP, EXP := 15 bits, Habilitar RA

LOAD
MUX1 := RB, Habilitar ADDR
Habilitar DATAin
MUX2 := DATAin, Habilitar RA

OP dst, src, ope
MUX2 := Alu, MUX3 := dst, MUX4 := src, MUX5 := IR[3...0], Habilitar dst

STORE
MUX1 := RB, Habilitar ADDR, Habilitar DATAout
WE := 1

PUSH
MUX4 := SP, MUX5 := FSM, ALU := inc, Habilitar SP
MUX1 := SP, Habilitar ADDR, Habilitar DATAout
WE := 1

POP
MUX1 := SP, Habilitar ADDR
Habilitar DATAin
Habilitar RA, MUX2 := DATAin
MUX4 := SP, MUX5 := FSM, ALU := dec, Habilitar SP

J value
MUX4 := EXP, EXP := 12 bits, MUX3 := PC, MUX5 := FSM, ALU := add, Habilitar PC

JZ value
MUX4 := EXP, EXP := 12 bits, MUX3 := PC, MUX5 := FSM, ALU := add if RA = 0, Habilitar PC

JN value
MUX4 := EXP, EXP := 12 bits, MUX3 := PC, MUX5 := FSM, ALU := add if RA < 0, Habilitar PC

Cada línea de microcódigo corresponde con un ciclo de reloj: LOADI requiere de un único ciclo de reloj mientras que POP requiere de cuatro ciclos de reloj. Las instrucciones PUSH y POP son las más intensivas en cuanto a ciclos de microcódigo.

Por ejemplo:
MUX4 := SP, MUX5 := FSM, ALU := inc, Habilitar SP
Significa: seleccionar la entrada correspondiente a SP en el MUX4, seleccionar la entrada correspondiente a la FSM en el MUX5 y hacer que la FSM mande la instrucción "inc" a la ALU y habilitar (poner el enable a 1) el registro SP para que sea cargado en el siguiente ciclo de reloj. Como todo está en una misma línea significa que se hace todo esto de golpe.

Hay que recordar que como estamos haciendo un modelo RTL el reloj es global a todos los bloques del procesador y la única forma que hay de controlar la carga de registros es mediante “enables” (Habilitar XX). Cuando se habilita un registro, es en el siguiente pulso de reloj cuando dicho registro se carga. Por ejemplo, veamos el caso de la instrucción POP:

POP
MUX1 := SP, Habilitar ADDR
Habilitar DATAin --> AQUÍ SE CARGA ADDR
Habilitar RA, MUX2 := DATAin --> AQUÍ SE CARGA DATAin”
MUX4 := SP, MUX5 := FSM, ALU := dec, Habilitar SP --> AQUÍ SE CARGA RA

Veamos este microcódigo de forma más detallada y explicada:

1. En el primer ciclo de reloj se selecciona la entrada SP del MUX1 y se pone a 1 la entrada "enable" del registro ADDR.

2. En el segundo ciclo de reloj se cargará el registro ADDR con lo que estaba en la salida del MUX1 (el valor del registro SP) y se pondrá a 1 la entrada "enable" del registro DATAIN.

3. Como el registro ADDR direcciona la memoria, en la entrada del registro DATAIN estará el dato alojado en la dirección de memoria apuntada por el valor de ADDR (el valor de SP), por lo que en este ciclo de reloj en DATAIN se cargará este dato (es decir, lo que está en el tope de la pila). Se pone a 1 la entrada "enable" del registro RA y se selecciona la entrada DATAIN en el MUX2.

4. En el cuarto ciclo de reloj se carga el registro RA con el valor que sale del MUX2, que es el valor del registro DATAIN. Ya tenemos en RA el valor del tope de la pila (hemos hecho RA := [SP]). En este mismo ciclo de reloj nos preparamos para decrementar SP: Indicamos al MUX4 que seleccione la entrada SP para que la entrada S de la ALU sea el valor de SP, seleccionamos en el MUX5 la entrada de selección que llega desde la FSM, desde la FSM indicamos que queremos una operación de decremento ("dec") y ponemos a 1 la entrada "enable" del registro SP.

5. En el quinto ciclo de reloj el registro SP se carga con el valor de salida de la ALU (SP := SP - 1).

Unidad de control

La unidad de control es la parte del procesador que se encarga de la secuenciación del resto de elementos y normalmente (como este caso) se implementa en forma de FSM (máquina de estados finita). La unidad de control se encarga en nuestro caso de:

- Inicialización en el arranque del PC con el vector de reset.

- Carga de la instrucción apuntada por el PC en el IR.

- Ejecución del microcódigo de la instrucción almacenada en el IR.

- Actualización automática del PC.

Los estados que tendrá la FSM serán los siguientes (el estado 0 es el estado en el que empieza el procesador tras un reset):

0. MUX6 := "0", Habilitar PC (El vector de reset es el 0)

1. MUX1 = PC, Habilitar ADDR (Se carga IR con la instrucción apuntada por PC)

2. Habilitar DATAin

3. Habilitar IR

4. MUX5 := FSM, ALU := inc, MUX4 := PC, Habilitar PC (Se hace PC := PC + 1)

5. EJECUTAR EL MICROCÓDIGO DE LA INSTRUCCIÓN ALMACENADA EN IR

6. Ir al estado 1

En el peor caso (instrucción POP), el paso 5 necesita 4 ciclos de reloj para ejecutarse. Por tanto en el peor caso, cada instrucción necesita un total de 11 ciclos mientras que en el mejor caso (instrucciones de 1 ciclo) cada instrucción necesita un total de 7 ciclos. A 32 MHz tendremos una velocidad mínima de 2.9 MIPS y máxima de 4.6 MIPS (millones de instrucciones por segundo).

Siguiente entrega

El la siguiente entrega se abordará el diseño de la máquina de estados y se empezará a plantear la implementación de los multiplexores, la ALU y los registros en VHDL.

En la sección soft puede descargarse un simulador y un ensamblador para este procesador, desarrollados en C++.

>>> Enlace a la segunda entrega de la serie.

[ 2 comentarios ] ( 37066 visualizaciones )   |  [ 0 trackbacks ]   |  enlace permanente
  |    |    |    |   ( 3 / 1511 )
Luces de Navidad controladas por FPGA 
Como cada año por estas fechas hago una revisita al concepto de las luces para el belén usando diferentes tecnologías. En este caso y como no podía ser de otro modo, intentaremos usar una FPGA para implementar este efecto.

Aspectos funcionales

Partimos de 5 leds de alta luminosidad (los mismos de años anteriores) y necesitamos que parpadeen de forma aleatoria, como si simularan el aspecto de una porción del cielo nocturno. La secuencia de parpadeo debería ser lo más aleatoria posible y lo ideal es que la probabilidad de parpadeo sea controlable para simular un ciclo día-noche.

Diseño

Para generar una secuencia de números pseudoaleatorios la forma más sencilla es utilizar un LFSR con la cantidad suficiente de bits como para dar la percepción de que se trata de un generador de números realmente aleatorios. Si partimos de un LFSR de 10 bits, para que sea maximal (que su secuencia numérica sea lo más larga posible antes de “dar la vuelta”) debemos implementar el siguiente polinomio de realimentación:
$$x^{10} + x^7 + 1$$
Este polinomio de realimentación garantiza una secuencia maximal de $2^{n} - 1$ valores, siendo en este caso $n=10$. La secuencia no es de $2^{n}$ valores debido a que el valor 0 (todos los bits a cero) no está incluido en la secuencia.

("=1" denota la operación XOR en notación IEC) La ruta de datos que se va a usar es la siguiente:

El funcionamiento interno sería el siguiente.

1. Se inicializa el LFSR (se le mete un valor que incluya, al menos un bit a 1).
2. Hacer 5 veces (una vez por cada uno de los 5 leds).
2.1. Se itera el LFSR para que genere el siguiente numero pseudoaleatorio.
2.2. Se empuja el bit resultante de la comparación entre el valor del LFSR (valor A) y una constante (valor B) en el registro de desplazamiento.
3. Se carga en el latch de salida el valor que hay en el registro de desplazamiento.
4. Se espera 1 segundo.
5. Saltar al paso 2.

Tanto para el conteo de la carga de los 5 bits en el registro de desplazamiento como para el conteo del tiempo de espera de 1 segundo se utiliza un contador de 32 bits de dos límites: uno de los límites se fija a 5 (para contar los bits) y otro de los límites se fija en 32000000 para contar 1 segundo (el reloj de la FPGA va a 32MHz).

A partir de este algoritmo se puede diseñar la siguiente máquina de estados:



Salidas de la FSM:
LFSR.RST = Reset del LFSR.
LFSR.ENA = Enable del LFSR.
SR.ENA = Enable del registro de desplazamiento.
LATCH.ENA = Enable del latch de salida.
CNT.RST = Reset del contador.
CNT.ENA = Enable del contador.

Entradas de la FSM:
CNT.T1 = a 1 cuando el contador llega a 5.
CNT.T2 = a 1 cuando el contador llega a 32000000.

Como se puede ver, se trata de un diseño totalmente síncrono, basado en enables y en el que se evita el uso de “gated clocks”, por lo tanto, perfectamente sintetizable en cualquier FPGA.

Por ahora la probabilidad de parpadeo está fijada por hardware como una constante (el valor de B en el diagrama, que no es modificable), sin embargo el diseño queda preparado para que en una siguiente versión se pueda obtener dicha constante de algún parámetro físico (ADC, reloj de tiempo real, etc.)

Implementación

La implementacion de todos los módulos se ha realizado siguiendo siempre un modelo RTL. A continuación se lista el codigo fuente de la unidad de más alto nivel (que se ha denominado “ChristmasLights”) y que engloba todos los submódulos (LFSR, comparador, registro de desplazamiento, latch, contador y FSM).

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity ChristmasLights is
	generic (
		NLeds : integer := 8;
		NWaitClocks : integer := 20;    -- for the simulation 20 clocks between lights change, but in real hardware change this value according FPGA clock
		Probability : integer := 512    -- 0 = all lights on, 1023 = all lights off
	);
	port (
		Clk   : in std_logic;
		Reset : in std_logic;
		Led   : out std_logic_vector((NLeds - 1) downto 0)
	);
end ChristmasLights;

architecture Architecture1 of ChristmasLights is
	component LFSR10 is
		port (
			Reset  : in std_logic;
			Enable : in std_logic;
			Clk    : in std_logic;
			Data   : out std_logic_vector(9 downto 0)
		);
	end component;
	component Comparator is
		generic (
			NBits : integer := 4
		);
		port (
			A           : in std_logic_vector((NBits - 1) downto 0);
			B           : in std_logic_vector((NBits - 1) downto 0);
			AGreatThanB : out std_logic;
			ALessThanB  : out std_logic;
			AEqualB     : out std_logic
		);
	end component;
	component ShiftRegister is
		generic (
			NBits : integer := 8
		);
		port (
			Enable         : in std_logic;
			Clk            : in std_logic;
			SerialInput    : in std_logic;
			ParallelOutput : out std_logic_vector((NBits - 1) downto 0)
		);
	end component;
	component Latch is
		generic (
			NBits : integer := 8
		);
		port (
			Enable  : in std_logic;
			Clk     : in std_logic;
			DataIn  : in std_logic_vector((NBits - 1) downto 0);
			DataOut : out std_logic_vector((NBits - 1) downto 0)
		);
	end component;
	component TwoLimitCounter is
		generic (
			NBits : integer := 4;
			Limit1 : integer := 3;
			Limit2 : integer := 2
		);
		port (
			Reset       : in std_logic;
			Enable      : in std_logic;
			Clock       : in std_logic;
			Terminated1 : out std_logic;
			Terminated2 : out std_logic
		);
	end component;
	signal LfsrEnable : std_logic;
	signal LfsrReset : std_logic;
	signal LfsrData : std_logic_vector(9 downto 0);
	signal CompOutput : std_logic;
	signal SREnable : std_logic;
	signal SRData : std_logic_vector((NLeds - 1) downto 0);
	signal LatEnable : std_logic;
	signal CntReset : std_logic;
	signal CntEnable : std_logic;
	signal CntBitsOut : std_logic;
	signal CntTimeOut : std_logic;
	signal FSMDBus : std_logic_vector(2 downto 0);
	signal FSMQBus : std_logic_vector(2 downto 0);
begin
	-- LFSR
	Lfsr : LFSR10 port map (
		Clk => Clk,
		Enable => LfsrEnable,
		Reset => LfsrReset,
		Data => LfsrData
	);
	-- comparator
	Comp : Comparator generic map (
		NBits => 10
	)
	port map (
		A => LfsrData,
		B => std_logic_vector(to_unsigned(Probability, 10)),
		AGreatThanB => CompOutput
	);
	-- shift register
	SR : ShiftRegister generic map (
		NBits => NLeds
	)
	port map (
		Enable => SREnable,
		Clk => Clk,
		SerialInput => CompOutput,
		ParallelOutput => SRData
	);
	-- output latch
	Lat : Latch generic map (
		NBits => NLeds
	)
	port map (
		Enable => LatEnable,
		Clk => Clk,
		DataIn => SRData,
		DataOut => Led
	);
	-- two limit counter
	Cnt : TwoLimitCounter generic map (
		NBits => 32,
		Limit1 => NLeds,
		Limit2 => NWaitClocks
	)
	port map (
		Reset => CntReset,
		Enable => CntEnable,
		Clock => Clk,
		Terminated1 => CntBitsOut,
		Terminated2 => CntTimeOut
	);

	-- FSM D FFs
	process (Clk, Reset)
	begin
		if (Clk'event and (Clk = '1')) then
			if (Reset = '1') then
				FSMQBus <= (others => '0');
			else
				FSMQBus <= FSMDBus;
			end if;
		end if;
	end process;
	-- FSM next state logic
	FSMDBus <= "000" when (Reset = '1') else
	           "001" when (FSMQBus = "000") else
	           "010" when (FSMQBus = "001") or (FSMQBus = "011") else
	           "011" when (FSMQBus = "010") and (CntBitsOut = '0') else
	           "100" when (FSMQBus = "010") and (CntBitsOut = '1') else
	           "101" when (FSMQBus = "100") or ((FSMQBus = "101") and (CntTimeOut = '0')) else
	           "001" when (FSMQBus = "101") and (CntTimeOut = '1') else
	           "000";
	-- FSM output logic
	LfsrReset <= '1' when (FSMQBus = "000") else
	             '0';
	CntReset <= '1' when (FSMQBus = "001") or (FSMQBus = "100") else
	            '0';
	CntEnable <= '1' when (FSMQBus = "010") or (FSMQBus = "101") else
	             '0';
	LfsrEnable <= '1' when (FSMQBus = "010") else
	              '0';
	SREnable <= '1' when (FSMQBus = "011") else
	            '0';
	LatEnable <= '1' when (FSMQBus = "100") else
	             '0';
end Architecture1;

Vídeo con el código VHDL implementado sobre la FPGA Spartan3E de Xilinx.



Todo el codigo puede descargarse de la sección soft. Feliz programación y feliz Navidad :-).

[ añadir comentario ] ( 1555 visualizaciones )   |  [ 0 trackbacks ]   |  enlace permanente
  |    |    |    |   ( 3 / 2354 )
Implementación de un receptor serie asíncrono sobre FPGA 
Un receptor serie asíncrono es un módulo de hardware que recibe datos serie de forma asíncrona: es el elemento receptor de una UART. A lo largo de este post se aborda paso a paso el diseño digital y la implementación de un módulo receptor serie asíncrono muy sencillo en VHDL, con un bit de start, un bit de stop y 8 bits de datos, así como su posterior implementación en una FPGA.

Especificaciones del receptor

La idea es crear un módulo muy sencillo que sea capaz de recibir datos en formato 8N1, es decir, 1 bit de start, 8 bits de datos, sin paridad y 1 bit de stop. Se asume el orden de envío estándar LSB --> MSB (primero el bit 0 y por último el bit 7) y una velocidad de 9600 bits por segundo (bps). Además de estas especificaciones "funcionales" se va a intentar que el circuito resultante sea totalmente síncrono (sin gated clocks, que el reloj sea el mismo para todos los sub módulos secuenciales del receptor). Este último requisito facilitará la implementación del módulo sobre cualquier FPGA sin limitación en la cantidad de líneas de reloj y de paso servirá para entender las alternativas al uso de gated clocks en el diseño de circuitos digitales.

Bloques del receptor

Los diferentes bloques que componen el receptor asíncrono son los siguientes:
- Un registro de desplazamiento: donde se irán empujando los bits a medida que lleguen.
- Un latch o registro de salida: donde se realizará una carga paralela desde el registro de desplazamiento del dato recibido una vez se compruebe que la recepción ha sido correcta.
- Dos contadores independientes para realizar la división de frecuencia y el conteo de los bits que van llegando, respectivamente.
- Una máquina de estados (FSM, Finite-State Machine) encargada del control de los contadores, del registro de desplazamiento y del registro de salida.



Algoritmo

De forma resumida el funcionamiento es el siguiente:

1. En el estado inicial, la FSM espera a que el pin RX valga 0.

2. En el instante en que RX pase a valor 0 la FSM inicializa un contador que tarda el equivalente en tiempo a 1.5 bits a 9600 bps en alcanzar el límite de cuenta, en el momento que este contador alcanza su límite se pasa al siguiente estado.

3. Se inicializa un contador que va a contar la cantidad de bits (8 + 1 bit de stop = 9).

4. Se empuja el valor de RX en el registro de desplazamiento, se reinicia otro contador que tiene como límite el equivalente en tiempo a 1 bit a 9600 bps y se incrementa el contador del número de bits

5. Si el contador de bits vale 9, saltamos al paso 8.

6. Esperamos a que el contador de tiempo para 1 bit llegue al límite

7. Saltamos al paso 4.

8. Si el bit de stop vale 1 cargamos el buffer de salida y hacemos DATAOUT = 1 para indicar que en el buffer de salida hay datos válidos, en caso contrario no se carga de buffer de salida.

9. Saltamos al paso 1.



Evitar el uso de “gated clocks”

En el anterior proyecto en el que se implementó un multiplicador en VHDL usando el algoritmo de Booth, el entorno de desarrollo ISE Design Suite de Xilinx mostraba un warning en el que se indicaba que había que evitar el uso de “gated clocks”.

Un “gated clock” es una línea de reloj que no se corresponde con la salida de un oscilador o un PLL sino que es la salida de una función combinacional o secuencial en un circuito. En el caso del multiplicador implementado en el anterior post, sí se utilizan gated clocks: Por ejemplo, cuando se quiere cargar un registro, la salida del FSM ataca directamente a la entrada de reloj de los biestables de ese registro. Esta forma de trabajar, a priori inocua, tiene varias implicaciones que en aquel proyecto no se tuvieron en cuenta:

1. Como bien me comentó mi colega Armando Sánchez Peña, las líneas de reloj son bienes muy preciados dentro de las FPGAs: su enrutamiento está muy cuidado para garantizar retardos equivalentes independientemente de la parte del chip donde lleguen y debido a ello no podemos disponer de todas las que queramos (aunque tengamos una FPGA con miles de unidades lógicas igual sólo disponemos de unas pocas decenas de líneas de reloj).

2. Los cambios de estado en los biestables de un FSM a veces no son todo lo limpios que uno desearía: Imaginemos que tenemos un FSM con tres estados (“00”, “01” y “11”), para el estado “01” tenemos una lógica de salida que genera un “1” en una entrada de reloj de un registro A y para el estado “11” tenemos una lógica de salida que genera un “1” en una entrada de reloj de otro registro B. Si el FSM está en el estado “00” y tiene que cambiar al estado “11”, es posible que los biestables basculen a velocidades ligeramente diferentes por lo que durante un breve intervalo de tiempo (picosegundos) se podría producir el estado “01” (si el biestable menos significativo es más rápido basculando que el más significativo) ¿Que sucederá durante este picosegundo? Pues que probablemente se produzca una carga espúrea y no deseada del registro A. Estos problemas pueden minimizarse utilizando codificación gray (estados adyacentes se codifican de tal manera que solo cambia de valor un bit) o codificación one-hot (un biestable por estado: gastamos más biestables pero la lógica de salida y de estado siguiente se simplifica por lo que a veces compensa). En posts futuros trataré de profundizará más en estos temas.

En multitud de foros sobre FPGAs y ASICs se comenta lo malo que es el uso de “gated clocks” sin embargo este post y otros ayudan mucho a aclarar este asunto. No todo es blanco o negro:

1. Para FPGAs hay que evitar el uso de gated clocks debido a la cantidad limitada de líneas de reloj de las que disponemos dentro del chip.

2. Para ASICs el uso de gated clocks mientras sea con cabeza (código gray, one-hot, etc.) no sólo es perfectamente válido, sino hasta aconsejable. Hay que tener en cuenta que una señal de reloj es una enorme fuente de consumo de corriente ya que cada vez que bascula la señal de reloj se producen micropicos de corriente debidos a las capacidades presentes en las entradas de reloj de los biestables a los que ataca. Un circuito con gated clocks consumirá menos corriente que su equivalente sin gated clocks.

Como obviamente, salvo casos excepcionales, lo normal es que dispongamos de una FPGA, no de un ASIC, lo lógico es intentar evitar el uso de gated clocks en nuestros diseños digitales. En este caso, como se puede ver en el diagrama de bloques anterior, esa ha sido la consigna que se ha seguido:

1. La misma señal de reloj para todos los módulos.

2. Sustituir los antiguos “gated clocks” por “enables” que permitan habilitar o deshabilitar módulos en un instante dado sin necesidad de enmascarar o tocar la señal de reloj.



Los enables en circuitos secuenciales se pueden implementar mediante lógica combinacional en los biestables o mediante señales CE (“Chip Enable”) que implementan muchos de los biestables presentes en las FPGAs que hay en el mercado. Para garantizar portabilidad en el código VHDL no se puede presuponer que los biestables de la FPGA vayan a tener entradas CE y dado que en este caso siempre se están usando biestables de tipo D, la opcion más lógica es la indicada en el documento FPGA Design Tips de Xilinx:



Esta es una forma sencilla de implementar un CE (“Chip Enable”) “a mano”. Cuando el multiplexor selecciona la entrada conectada a la salida Q, el biestable no cambia de estado por muchos ciclos de reloj que le lleguen. Además implementando un CE “a mano” de esta manera, nos aseguramos que el circuito resultante es sintetizable en cualquier FPGA independientemente de si ésta implementa entradas CE en sus biestables o no.

Máquina de estados

La máquina de estados resultante para nuestro módulo de recepción de la UART quedaría, utilizando la técnica de los “enables”, como sigue:



La máquina de estados es una versión “formal” del algoritmo descrito en párrafos anteriores. Como se puede apreciar el contador 1 se utiliza para controlar los tiempos entre los principales cambios de estado (cuando se detecta el bit de start y entre bit y bit de datos).

Contadores

El módulo receptor utiliza dos contadores, uno (contador 1) para contar el tiempo equivalente a 1.5 bits a 9600 bps y el tiempo equivalente a 1 bit a 9600 bps y otro contador (contador 2) para contar los bits que se van empujando en el registro de desplazamiento (9, los 8 de datos más el bit de stop). El segundo contador (contador 2) es trivial ya que cuenta hasta 9 mientras que para el contador 1 sí que es necesario realizar algunos cálculos previos. Consideremos una velocidad de 9600 bps:

$$9600\ \ bits/segundo = {1 \over 9600}\ \ segundos/bit$$

Teniendo en cuenta que, en el caso particular de la placa FPGA Papilio One, el reloj del sistema va a 32MHz tenemos que:

$$(32000000\ \ pulsos/segundo) \times \left({1 \over 9600}\ \ segundos/bit\right) = 3333.33\ \ pulsos/bit$$

Que, redondeando, nos da: 3333 pulsos a 32MHz por bit a 9600 bps. Multiplicando por 1.5 nos dará la cantidad de pulsos a 32MHz necesarios para contar 1.5 bits de tiempo:

$$3333.33 \times 1.5 = 5000\ pulsos\ a\ 32MHz\ por\ 1.5\ bit\ a\ 9600 bps$$

El Contador 1 tendrá, por tanto como límite de cuenta 1 el valor 3333 y como límite de cuenta 2 el valor 5000. En otras palabras, tras un reset en el contador 1, la salida TERM1 de dicho contador 1 se pondrá a “1” cuando pasen 3333 pulsos de reloj del sistema mientras que la salida TERM2 de ese mismo contador 1 se pondrá a “1” cuando pasen 5000 pulsos de reloj del sistema.

VHDL

Ambos contadores (1 y 2) son instancias separadas de un mismo módulo contador (en el caso del contador 2 se ignora la salida TERM2). Al ser tanto el registro de desplazamiento como el registro de salida simplemente arrays de biestables, se ha optado por implementar ambos submódulos dentro de la misma FSM.

library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.numeric_std.all;

entity UartReceiver is
    port (
        Rx        : in std_logic;
        Clock     : in std_logic;
        DataOut   : out std_logic_vector(7 downto 0);
        DataOutOk : out std_logic
    );
end UartReceiver;

architecture Architecture1 of UartReceiver is
    component TwoLimitCounter is
        generic (
            NBits : integer := 4;
            Limit1 : integer := 3;
            Limit2 : integer := 11
        );
        port (
            Reset       : in std_logic;
            Clock       : in std_logic;
            Enable      : in std_logic;
            Terminated1 : out std_logic;
            Terminated2 : out std_logic
        );
    end component;
    signal ShiftRegisterDBus : std_logic_vector(8 downto 0);  -- 8 bits + 1 bit de stop
    signal ShiftRegisterQBus : std_logic_vector(8 downto 0);
    signal ShiftRegisterEnable : std_logic;
    signal BufferDBus : std_logic_vector(7 downto 0);
    signal BufferQBus : std_logic_vector(7 downto 0);
    signal BufferEnable : std_logic;
    signal Counter1Reset : std_logic;
    signal Counter1Terminated1 : std_logic;
    signal Counter1Terminated2 : std_logic;
    signal Counter2Reset : std_logic;
    signal Counter2Enable : std_logic;
    signal Counter2Terminated : std_logic;
    signal FSMQBus : std_logic_vector(3 downto 0);
    signal FSMDBus : std_logic_vector(3 downto 0);
begin
    -- registro de desplazamiento
    process (Clock)
    begin
        if (Clock'event and (Clock = '1')) then
            ShiftRegisterQBus <= ShiftRegisterDBus;
        end if;
    end process;
    -- MSB first (apenas usado)
    -- ShiftRegisterDBus <= (ShiftRegisterQBus(7 downto 0) & Rx) when (ShiftRegisterEnable = '1') else ShiftRegisterQBus;
    -- LSB first: los valores se van metiendo por el bit más significativo
    ShiftRegisterDBus <= (Rx & ShiftRegisterQBus(8 downto 1)) when (ShiftRegisterEnable = '1') else ShiftRegisterQBus;
    
    -- buffer de salida
    process (Clock)
    begin
        if (Clock'event and (Clock = '1')) then
            BufferQBus <= BufferDBus;
        end if;
    end process;
    -- MSB first (apenas usado)
    -- BufferDBus <= ShiftRegisterQBus(8 downto 1) when (BufferEnable = '1') else BufferQBus;
    -- LSB first: El bit de stop está en el bit más significativo, el dato en el resto de bits
    BufferDBus <= ShiftRegisterQBus(7 downto 0) when (BufferEnable = '1') else BufferQBus;

    -- contador fino para medir 1 y 1,5 bits a 32MHz
    Counter1: TwoLimitcounter generic map (
        NBits => 13,
        --Limit1 => 50,   -- 1 bit a 1MHz
        --Limit2 => 75    -- 1.5 bits a 1MHz
        Limit1 => 3333,   -- 1 bit a 32MHz
        Limit2 => 5000    -- 1.5 bits a 32MHz
    )
    port map (
        Reset => Counter1Reset,
        Clock => Clock,
        Enable => '1',
        Terminated1 => Counter1Terminated1,
        Terminated2 => Counter1Terminated2
    );
    
    -- contador grueso de bits
    Counter2: TwoLimitcounter generic map (
        NBits => 4,
        Limit1 => 8,  -- poniendo el límite a 8 metemos 9 valores en el registro de desplaz.
        Limit2 => 0
    )
    port map (
        Reset => Counter2Reset,
        Clock => Clock,
        Enable => Counter2Enable,
        Terminated1 => Counter2Terminated
    );
   
    -- FSM: Biestables
    process (Clock)
    begin
        if (Clock'event and (Clock = '1')) then
            FSMQBus <= FSMDBus;
        end if;
    end process;
    
    -- FSM: Lógica del estado siguiente
    FSMDBus <= "0001" when (FSMQBus = "0000") and (Rx = '0') else
               "0010" when (FSMQBus = "0001") or ((FSMQBus = "0010") and (Counter1Terminated2 = '0')) else
               "0011" when (FSMQBus = "0010") and (Counter1Terminated2 = '1') else
               "0100" when (FSMQBus = "0011") or ((FSMQBus = "0101") and (Counter2Terminated = '0')) or ((FSMQBus = "0100") and (Counter1Terminated1 = '0')) else
               "0101" when (FSMQBus = "0100") and (Counter1Terminated1 = '1') else
               "0110" when (FSMQBus = "0101") and (Counter2Terminated = '1') else
               "0111" when (FSMQBus = "0110") and (ShiftRegisterQBus(8) = '1') else  -- bit de stop ok
               "1000" when (FSMQBus = "0111") else
               "1001" when (FSMQBus = "1000") else
               "1010" when (FSMQBus = "0110") and (ShiftRegisterQBus(8) = '0') else  -- bit de stop mal
               "0000";
    -- FSM: Lógica de salida
    ShiftRegisterEnable <= '1' when (FSMQBus = "0011") or (FSMQBus = "0101") else
                           '0';
    BufferEnable <= '1' when (FSMQBus = "0111") else
                    '0';
    Counter1Reset <= '1' when (FSMQBus = "0001") or (FSMQBus = "0011") or (FSMQBus = "0101") else
                     '0';
    Counter2Reset <= '1' when (FSMQBus = "0001") else
                     '0';
    Counter2Enable <= '1' when (FSMQBus = "0011") or (FSMQBus = "0101") else
                      '0';
    DataOutOk <= '1' when (FSMQBus = "1001") else
                 '0';

    -- salida paralelo
    DataOut <= BufferQBus;
end Architecture1;


Se trata de un diseño RTL, por lo que la implementación en VHDL es trivial, directa y siempre sintetizable.

A continuación puede verse una simulación en la que se recibe el valor serie 0x53:



La señal COUNTER1TERMINATED2 indica que han pasado 1.5 bits de datos desde el reset del contador 1 mientras que la señal COUNTER1TERMINATED1 indica que ha pasado 1 bit de datos desde el reset del contador 1.

Implementación física

A la placa Papilio One (Xilinx Spartan3E) se le conectó por un lado un array de 8 leds (conectado internamente al registro de salida del módulo receptor de la UART) y, por otro lado un módulo USBSerial basado en el chip FT232R, dicho módulo permite mediante un jumper seleccionar una operación a 3.3V (la FPGA incluida en la placa Papilio One no es tolerante a 5V): Se conectó la salida TX del módulo a un pin de la FPGA conectado internamente a la señal RX del módulo receptor.





En la foto se puede ver al receptor cargando un carácter 'i' (hexadecimal 69) enviado por el puerto serie desde el ordenador.

Todo el código fuente puede descargarse de la sección soft.

[ añadir comentario ] ( 1373 visualizaciones )   |  [ 0 trackbacks ]   |  enlace permanente
  |    |    |    |   ( 3 / 2271 )
Implementación del algoritmo de multiplicación de Booth en VHDL sobre una FPGA 
El algoritmo de multiplicación de Booth permite multiplicar enteros con signo en complemento a dos utilizando una técnica muy sencilla basada en desplazamientos y sumas. A lo largo de este post se abordará el diseño y la codificación en VHDL de dicho algoritmo así como su implementación final en una FPGA.

El algoritmo

En la Wikipedia hay una explicación muy clara y detallada del algoritmo de Booth (https://es.wikipedia.org/wiki/Algoritmo_de_Booth). En este caso se ha asumido, por simplicidad, que ambos términos (multiplicando y multiplicador) tienen la misma cantidad de bits.

Partimos de dos números enteros X e Y, ambos de N bits:

1. Construimos una matriz de 3 filas y N+N+1 columnas. La primera fila la llamaremos A, la segunda S y la tercera P.

  1.1. En los N bits más significativos de A metemos X, el resto de bits de A los ponemos a 0.

  1.2. En los N bits más significativos de S metemos -X (complemento a 2 de X), el resto de bits de S los ponemos a 0.

  1.3. En los N bits más significativos de P metemos 0s, a continuación metemos los N bits de Y y en el bit que queda (el menos significativo) metemos un 0.

2. Hacer N veces:

  2.1. Si los dos bits menos significativos de P son 01, hacer P <- P + A, en caso de que sean 10, hacer P <- P + S, en caso de que sean 00 o 11, no hacer nada

  2.2. Hacer un desplazamiento aritmético (incluyendo el signo) de P hacia la derecha.

3. El resultado de la multiplicación serán los bits N a 1 de P (ojo, el bit 0 de P no forma parte de la solución).

Se trata de un algoritmo muy sencillo y que debe ser implementado de forma secuencial.

El flujo de datos

A continuación puede verse de forma esquemática cómo sería el flujo de datos en el multiplicador.



El multiplexor MUXa permite seleccionar entre la operación “P + A” o “P + S”, mientras que el multiplexor MUXp permite seleccionar entre al desplazamiento aritmético hacia la derecha de P, la entrada (para cargar el valor inicial de P a partir del operando Y) y la salida del sumador.

La unidad de control del multiplicador

Para gobernar las señales de carga de los registros y las señales de selección de los multiplexores es necesario implementar una unidad de control. La unidad de control se implementará mediante una máquina de estados finita (FSM) formada por biestables D, lógica de estado siguiente y lógica de salida de tipo Moore.



En este caso la máquina de estados que implementaría el algoritmo de Booth sería la siguiente:



Supongamos que se quiere multiplicar -3 por 2 utilizando una mantisa de 5 bits. En este caso:

-3 dec = 11101 bin
2 dec = 00010 bin

- Estado 0.
- Estado 1: MUXp=Y, Resetear el contador.
- Estado 2: Cargar A, Cargar S, Cargar P (se carga Y), Avanzar el contador.
- Estado 3.
Estando en el estado 3 los dos bits menos significativos de P valen en este momento “00” (P1=P0)y el contador no ha terminado (Ct=0), por lo que se va a estado 8.
- Estado 8: MUXp = SRA(P) (desplazamiento aritmético a la derecha de P un bit).
- Estado 9: MUXp = SRA(P), Cargar P (P <- SRA(P)).
- Estado 10: Avanzar el contador.
- Estado 3.
Estando en el estado 3 los dos bits menos significativos de P valen en este momento “10” (P1=1 y P0=0) y el contador no ha terminado (Ct=0), por lo que se va de nuevo al estado 6.
- Estado 6: MUXp = Sumador, MUXa = A.
- Estado 7: MUXp = Sumador, MUXa = A, Cargar P (P <- P + A)
- ...

Y así sucesivamente. Como se puede ver en el grafo de la FSM la multiplicación termina cuando, estando en el estado 3, el contador llega al final:

- ...
- Estado 3: Si el contador ha terminado pasamos al estado 11.
- Estado 11: Cargar Out (Out <- P).
- Estado 0 (se vuelve a empezar).
- ...

El el siguiente diagrama puede verse cómo quedaría todo el conjunto (registros, multiplexores, sumador y unidad de control) con lo que serían las entradas y salidas finales del multiplicador.



Implementación en VHDL

Para implementar en VHDL el FSM de la unidad de control basta con traducir el FSM a un modelo RTL: se traducen los arcos del grafo a lógica de estado siguiente y las salidas indicadas en los nodos del grafo a lógica de salida.

library ieee;
use ieee.std_logic_1164.all;

entity MultiplierControlUnit is
    generic (
        NBits : integer := 4
    );
    port (
        Clock             : in std_logic;
        Reset             : in std_logic;
        P1                : in std_logic;
        P0                : in std_logic;
        LoadA             : out std_logic;
        LoadS             : out std_logic;
        LoadP             : out std_logic;
        LoadOut           : out std_logic;
        AdderMuxSel       : out std_logic;
        PMuxSel           : out std_logic_vector(1 downto 0)
    );
end MultiplierControlUnit;

architecture Architecture1 of MultiplierControlUnit is
    component Counter
        generic (
            NBits : integer := 4;
            Limit : integer := 3
        );
        port (
            Reset      : in std_logic;
       	    Clock      : in std_logic;
            Terminated : out std_logic
        );
    end component;
    signal DBus : std_logic_vector(3 downto 0);
    signal QBus : std_logic_vector(3 downto 0);
    signal CounterReset : std_logic;
    signal CounterClock : std_logic;
    signal CounterTerminated : std_logic;
begin
    -- counter for shift loop
    C : Counter generic map (
    	NBits => 8,
        Limit => NBits
    )
    port map (
    	Reset => CounterReset,
        Clock => CounterClock,
        Terminated => CounterTerminated
    );
    
    -- D flip-flop with synchronous reset for FSM
    process (Clock, Reset)
    begin
        if (Clock'event and (Clock = '1')) then
	    if (Reset = '1') then
                QBus <= (others => '0');
            else
            	QBus <= DBus;
            end if;
        end if;
    end process;
    
    -- next state logic
    DBus <= "0001" when (QBus = "0000") else
            "0010" when (QBus = "0001") else
            "0011" when ((QBus = "0010") or (QBus = "1010")) else
            "0100" when ((QBus = "0011") and (P1 = '1') and (P0 = '0') and (CounterTerminated = '0')) else
            "0101" when (QBus = "0100") else
            "0110" when ((QBus = "0011") and (P1 = '0') and (P0 = '1') and (CounterTerminated = '0')) else
            "0111" when (QBus = "0110") else
            "1000" when ((QBus = "0101") or (QBus = "0111") or ((QBus = "0011") and (P1 = P0) and (CounterTerminated = '0'))) else
            "1001" when (QBus = "1000") else
            "1010" when (QBus = "1001") else
            "1011" when ((QBus = "0011") and (CounterTerminated = '1')) else
            "0000";

    -- output logic
    LoadA <= '1' when (QBus = "0010") else
             '0';
    LoadS <= '1' when (QBus = "0010") else
             '0';
    LoadP <= '1' when ((QBus = "0010") or (QBus = "0101") or (QBus = "0111") or (QBus = "1001")) else
             '0';
    LoadOut <= '1' when (QBus = "1011") else
               '0';
    PMuxSel <= "01" when ((QBus = "0001") or (QBus = "0010")) else  -- Y
               "10" when ((QBus = "0100") or (QBus = "0101") or (QBus = "0110") or (QBus = "0111")) else  -- +
               "00" when ((QBus = "1000") or (QBus = "1001")) else
               "11";
    AdderMuxSel <= '0' when ((QBus = "0110") or (QBus = "0111")) else  -- A
                   '1' when ((QBus = "0100") or (QBus = "0101")) else  -- S
                   '0';
    CounterReset <= '1' when ((QBus = "0001") or (QBus = "0010")) else
                    '0';
    CounterClock <= '1' when ((QBus = "0010") or (QBus = "1010")) else
                    '0';
end Architecture1;

La unidad de control incluye un contador interno (el componente instanciado como C) encargado de controlar la cantidad de veces que itera el bucle del algoritmo. En el caso del algoritmo de Booth el bucle itera tantas veces como bits tiene la mantisa (al instanciar el contador C hacemos Limit => NBits).

Como puede apreciarse, se trata de un diseño totalmente basado en modelos RTL (https://en.wikipedia.org/wiki/Register-transfer_level) por lo que su implementación es relativamente sencilla y el código generado siempre es sintetizable.

Todo el código fuente se puede descargar de la sección soft.



[ añadir comentario ] ( 1450 visualizaciones )   |  [ 0 trackbacks ]   |  enlace permanente
  |    |    |    |   ( 3 / 2489 )

<< <Anterior | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | Siguiente> >>