La minimización de la Lógica en un Spartan-6 para un Juego de la Vida de la Célula

Question

Mientras tratando de aprender programación FPGA, me he decidido a implementar un paralelo masivo juego de la vida. Aquí está mi primer intento:

entity LifeCell is
    Port ( neighbours : in      std_logic_vector(7 downto 0);
           state        : inout std_logic;
           clk       : in   std_logic);
end LifeCell;

architecture Behavioral of LifeCell is

begin
    compute: process(clk)
    variable temp : integer range 0 to 8;
    begin
        if rising_edge(clk) then
            temp := 0;
            for i in neighbours'range loop
                if neighbours(i) = '1' then temp := temp + 1; 
                end if;
            end loop;

            if (temp = 3 or (temp = 2 and state = '1')) then
                state <= '1';
            else
                state <= '0';
            end if;

        end if;
    end process;
end Behavioral;

Entonces me di cuenta de que la Tecnología Diagrama fue el uso de 13 de LUTs. Hmmm... tal vez lo puedo hacer mejor? ¿Por qué no especifican de antemano las posibles combinaciones?

function count3bits(v : std_logic_vector(7 downto 0)) return boolean is
begin
    case v is
        when "00000111" => return true;
        when "00001011" => return true;
        when "00001101" => return true;
        when "00001110" => return true;
        when "00010011" => return true;
        when "00010101" => return true;
        when "00010110" => return true;
        when "00011001" => return true;
        when "00011010" => return true;
        when "00011100" => return true;
        when "00100011" => return true;
        when "00100101" => return true;
        when "00100110" => return true;
        when "00101001" => return true;
        when "00101010" => return true;
        when "00101100" => return true;
        when "00110001" => return true;
        when "00110010" => return true;
        when "00110100" => return true;
        when "00111000" => return true;
        when "01000011" => return true;
        when "01000101" => return true;
        when "01000110" => return true;
        when "01001001" => return true;
        when "01001010" => return true;
        when "01001100" => return true;
        when "01010001" => return true;
        when "01010010" => return true;
        when "01010100" => return true;
        when "01011000" => return true;
        when "01100001" => return true;
        when "01100010" => return true;
        when "01100100" => return true;
        when "01101000" => return true;
        when "01110000" => return true;
        when "10000011" => return true;
        when "10000101" => return true;
        when "10000110" => return true;
        when "10001001" => return true;
        when "10001010" => return true;
        when "10001100" => return true;
        when "10010001" => return true;
        when "10010010" => return true;
        when "10010100" => return true;
        when "10011000" => return true;
        when "10100001" => return true;
        when "10100010" => return true;
        when "10100100" => return true;
        when "10101000" => return true;
        when "10110000" => return true;
        when "11000001" => return true;
        when "11000010" => return true;
        when "11000100" => return true;
        when "11001000" => return true;
        when "11010000" => return true;
        when "11100000" => return true;
        when others => return false;
    end case;
end count3bits;

function count2bits(v : std_logic_vector(7 downto 0)) return boolean is
begin
    case v is
        when "00000011" => return true;
        when "00000101" => return true;
        when "00000110" => return true;
        when "00001001" => return true;
        when "00001010" => return true;
        when "00001100" => return true;
        when "00010001" => return true;
        when "00010010" => return true;
        when "00010100" => return true;
        when "00011000" => return true;
        when "00100001" => return true;
        when "00100010" => return true;
        when "00100100" => return true;
        when "00101000" => return true;
        when "00110000" => return true;
        when "01000001" => return true;
        when "01000010" => return true;
        when "01000100" => return true;
        when "01001000" => return true;
        when "01010000" => return true;
        when "01100000" => return true;
        when "10000001" => return true;
        when "10000010" => return true;
        when "10000100" => return true;
        when "10001000" => return true;
        when "10010000" => return true;
        when "10100000" => return true;
        when "11000000" => return true;
        when others => return false;
    end case;
end count2bits;

begin
    compute: process(clk)
    begin
        if rising_edge(clk) then
            if (count3bits(neighbours) or (state = '1' and count2bits(neighbours))) then
                state <= '1';
            else
                state <= '0';
            end if;
        end if;
    end process;
end Behavioral;

La aplicación es ahora hasta el 9 de LUTs.

Ahora, aquí está la pregunta. Es posible hacer mejor? (Spartan-6 sólo dispone de 6-bit Lut).

Answer 1

Yo creo que usted debería ser capaz de hacer esto con 6 LUTs por celda. El enfoque básico es dividir a los 8 entradas en dos grupos, 3 entradas en un grupo y 5 entradas en el otro. Usted puede contar con los del primer grupo con 2 LUTs, y contar los que están en el segundo grupo de 3 con LUTs, para un total de 5 resultado intermedio bits. Uno de los más LUT puede combinar los bits que con el estado actual para dar el siguiente estado.

También, desde los primeros 5 LUTs operan en paralelo, la latencia total es de sólo dos LUTs, así que usted debe ser capaz de operar a una muy alta velocidad de reloj.

El código siguiente da una idea general. Algunos de los detalles de la sintaxis podría ser un poco — mi VHDL es un poco oxidado.

-- This function uses 2 LUTs
function count3bits(v : std_logic_vector(2 downto 0)) return std_logic_vector(1 downto 0) is
begin
    case v is
        when "000" => return "00";
        when "001" => return "01";
        when "010" => return "01";
        when "011" => return "10";
        when "100" => return "01";
        when "101" => return "10";
        when "110" => return "10";
        when "111" => return "11";
        when others => return "00";
    end case;
end count3bits;

-- This function uses 3 LUTs
function count5bits(v : std_logic_vector(4 downto 0)) return std_logic_vector(2 downto 0) is
begin
    case v is
        when "00000" => return "000";
        when "00001" => return "001";
        when "00010" => return "001";
        when "00011" => return "010";
        when "00100" => return "001";
        when "00101" => return "010";
        when "00110" => return "010";
        when "00111" => return "011";
        when "01000" => return "001";
        when "01001" => return "010";
        when "01010" => return "010";
        when "01011" => return "011";
        when "01100" => return "010";
        when "01101" => return "011";
        when "01110" => return "011";
        when "01111" => return "100";
        when "10000" => return "001";
        when "10001" => return "010";
        when "10010" => return "010";
        when "10011" => return "011";
        when "10100" => return "010";
        when "10101" => return "011";
        when "10110" => return "011";
        when "10111" => return "100";
        when "11000" => return "010";
        when "11001" => return "011";
        when "11010" => return "011";
        when "11011" => return "100";
        when "11100" => return "011";
        when "11101" => return "100";
        when "11110" => return "100";
        when "11111" => return "101";
        when others  => return "000";
    end case;
end count5bits;

-- This function uses 1 LUT
function evaluate(a : std_logic_vector(1 downto 0),
                  b : std_logic_vector(2 downto 0),
                  s : std_logic) return std_logic is
    variable temp : std_logic_vector (5 downto 0);
begin
    temp := (a & b & s);
    case temp is
        -- cases where the state is true and the sum is 2
        when "10_000_1" => return '1';
        when "01_001_1" => return '1';
        when "00_010_1" => return '1';

        -- cases where the state is true and the sum is 3
        when "11_000_1" => return '1';
        when "10_001_1" => return '1';
        when "01_010_1" => return '1';
        when "00_011_1" => return '1';

        -- cases where the state is false and the sum is 3
        when "11_000_0" => return '1';
        when "10_001_0" => return '1';
        when "01_010_0" => return '1';
        when "00_011_0" => return '1';

        when others => return '0';
    end case;
end evaluate;

begin
    compute: process(clk)
    begin
        if rising_edge(clk) then
            state <= (evaluate(count3bits(neighbours(7 downto 5)),
                               count5bits(neighbours(4 downto 0)),
                               state);
        end if;
    end process;
end Behavioral;

La mayor Spartan-6 ha 23038 sectores, cada uno de los cuales contiene cuatro de 64-bit Lut. Tenga en cuenta que cada una de esas tablas de búsqueda también se puede dividir en dos 32-bit Lut siempre que compartan los mismos insumos. Esto significa que una célula de la Vida sólo se requiere una rebanada de implementar. Usted podría hacer un 150×150 juego de la Vida que se ejecuta en cientos de millones de generaciones/segundo. O usted podría utilizar la influencia de Brahms búfer doble en un juego de la Vida el tamaño de un televisor de alta definición de pantalla (1920×1080) y ejecutarlo en alrededor de un millón de generaciones/segundo.

Answer 2

Creo que puede encajar en 3 LUTs pero no va a ser tan elegante como la de David solución. Pero la reducción de la LUT es una meta, entonces esto puede funcionar. También, no he trabajado con Spartan-6 Fpga. Me estoy basando el análisis en:

http://www.xilinx.com/support/documentation/user_guides/ug384.pdf específicamente la figura 6 en la página 13.

Aquí va:

1. LUT 0 se utiliza como doble 5 entradas. Sus entradas son bits [4:0] "los vecinos".
2. LUT 1 se utiliza como 6 entradas. Sus entradas son {Estado, vecinos[4:0]}

Ambos trabajan juntos para generar 3 bits de salida codificado como en esta tabla:

Aquí es cómo leer la tabla. Fila 1 dice: "si el estado es 0 y no son cero 1s en bits[4:0], entonces para la Próxima Estado 1, debe haber tres 1s en el resto de los 3 bits." Como usted puede ver, hay 12 únicas combinaciones de entrada que deben ser codificados. Pero hay oportunidades para combinar pocos. En primer lugar, si hay 4 o 5 1s ya entonces el Estado no se 1 entonces filas 5,6,11 y 12 pueden ser codificados como único punto de código. Curiosamente, las líneas 4 y 10 también puede ser representado como único punto de código. Si hay tres 1s ya, a continuación, "Estado" es, esencialmente, no me importa.

Si se fusionan las filas de esta manera, hay 8 código único punto que contienen suficiente información para procesamiento restante 3 bits. Por favor, tenga en cuenta que el Estado ya está codificado aquí y no es más necesario.

Puntos de código son seleccionados de tal manera que LUT0 genera consistente salidas y no necesita saber sobre el Estado de la entrada.

LUT2 será de 6 entradas. Tendrá 3 bits de {LUT1, LUT0} y los 3 restantes bits vecinos[7:5]. Interpreta los bits como por la Acción de la columna de la tabla para generar siguiente estado.

Creo que cumple con el requisito establecido. Me gustaría saber si usted ve cualquier problema.