Minimizar la lógica en un Spartan-6 para una célula de Game of Life

Recuerde que las Spartan-6 LUT pueden configurarse como una sola LUT de 6 entradas o como una LUT doble de 5 entradas. Estoy considerando específicamente la variación SLICEX, que es un subconjunto y el menos capaz de todas las rebanadas de Spartan-6.

Creo que esto se puede hacer en 4 LUT de seis entradas.

Los tres primeros LUT ingresan el estado de 6 de las celdas circundantes, y salen un número de 3 bits que es el conteo de 1 en esas seis celdas.

La cuarta LUT de seis entradas toma ese conteo de 3 bits, más las 2 celdas circundantes restantes y el estado actual de la celda central y genera el nuevo estado de la celda.

Toda esta lógica puede caber dentro de un solo bloque SliceX (pero también encajará dentro de todos los demás tipos de rebanadas). En el Spartan-6 más pequeño, podrías hacer 300 celdas. En la más grande, puedes hacer algo más de 23,000.

Ninguno de estos factores en la comunicación requerida para leer o establecer el estado de toda la matriz. Al leerlo se podría agregar una LUT + FF de 5 entradas por celda, y la inicialización de la matriz podría agregar otra LUT + FF de 5 entradas por celda. Esto equivale a otra LUT de 6 entradas (que tiene 2 FF con ella) por celda, y un aumento del 25% en la lógica requerida para hacer un Juego de la Vida útil.

Creo que debería poder hacer esto con 6 LUT por celda. El enfoque básico es dividir las 8 entradas en dos grupos, 3 entradas en un grupo y 5 entradas en el otro. Puede contar las que están en el primer grupo con 2 LUT y las que están en el segundo grupo con 3 LUT, para un total de 5 bits de resultados intermedios. Una LUT más puede combinar esos bits con el estado actual para dar el siguiente estado.

Además, dado que las primeras 5 LUT funcionan en paralelo, la latencia total es de solo dos LUT, por lo que debería poder operar esto a una velocidad de reloj muy alta.

El siguiente código da la idea general. Algunos de los detalles de la sintaxis pueden estar un poco apagados, mi VHDL está un poco oxidada.

-- 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;

El Spartan-6 más grande tiene 23038 cortes, cada uno de los cuales contiene cuatro LUT de 64 bits. Tenga en cuenta que cada una de esas LUT también se puede dividir en dos LUT de 32 bits siempre que compartan las mismas entradas. Esto significa que una célula de vida solo requiere una porción para implementar. Podrías hacer un juego de Vida 150 × 150 que se ejecuta en cientos de millones de generaciones / segundo. O puede usar los BRAM para duplicar un juego de Life del tamaño de una pantalla HDTV (1920 × 1080) y ejecutarlo en aproximadamente un millón de generaciones / segundo.

Creo que puede caber en 3 LUT, pero no será tan elegante como la solución de David. Pero reducir la LUT es una meta, entonces esto puede funcionar. Además, no he trabajado con Spartan-6 FPGAs. Estoy basando este análisis en:

enlace específicamente la figura 6 en la página 13.

Aquí va:

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

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

Aquíescómoleerlatabla.Lafila1dice"si el estado es 0 y hay 1 cero en los bits [4: 0], para que el estado siguiente sea 1, debe haber tres 1 en los 3 bits restantes". Como puede ver, hay 12 combinaciones de entrada únicas que deben codificarse. Pero hay oportunidades para fusionar algunos. Primero, si ya hay 4 o 5 1, entonces el estado no será 1, por lo que las filas 5,6,11 y 12 pueden codificarse como un punto de código único. Curiosamente, las filas 4 y 10 también se pueden representar como un punto de código único. Si ya hay tres 1s, entonces "Estado" es esencialmente no importa.

Si combinamos filas de esta manera, hay 8 puntos de código únicos que contienen suficiente información para procesar los 3 bits restantes. Tenga en cuenta que el estado ya está codificado aquí y no se requiere más.

Los puntos de código se seleccionan de tal manera que LUT0 genera resultados consistentes y no necesita saber acerca de la entrada del estado.

LUT2 será LUT de 6 entradas. Tendrá 3 bits de {LUT1, LUT0} y 3 bits restantes vecinos [7: 5]. Interpretará esos bits según la columna Acción de la tabla para generar el siguiente estado.

Creo que cumple con el requisito establecido. Me gustaría escuchar si ve algún problema.