Minimizando la Lógica en un Spartan-6 para un Game of Life Cell

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

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

Las primeras tres LUT ingresan el estado de 6 de las celdas circundantes, y emiten 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 cabe dentro de todos los demás tipos de rebanadas). En el Spartan-6 más pequeño, podrías hacer 300 celdas. En el más grande, puedes hacer poco más de 23.000.

Ninguno de estos factores en la comunicación requerida para leer o establecer el estado de toda la matriz. Leerlo podría agregar una LUT + FF de 5 entradas por celda, e inicializar la matriz podría agregar otras 5 LUT + FF de entrada por celda. Esto equivale a otros 6 LUT de entrada (que tiene 2 FF) por celda, y se requiere un aumento del 25% en la lógica para hacer un Game of Life ú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 los del primer grupo con 2 LUT y los del segundo grupo con 3 LUT, para un total de 5 bits de resultado intermedio. 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 fuera de lugar: mi VHDL está 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;

El Spartan-6 más grande tiene 23038 segmentos, 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 celda de vida solo requiere una porción para implementarse. Podrías hacer un juego de Life de 150×150 que se ejecuta a cientos de millones de generaciones/segundo. O puede usar las BRAM para duplicar el búfer de un juego de Life del tamaño de una pantalla de HDTV (1920 × 1080) y ejecutarlo alrededor de un millón de generaciones por segundo.

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

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

Aquí va:

1. LUT 0 se utiliza como LUT dual 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í se explica cómo leer la tabla. La fila 1 dice "si el estado es 0 y hay cero 1 en los bits [4:0], entonces para que el siguiente estado 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 pocos. Primero, si ya hay 4 o 5 1, el estado no será 1, por lo que las filas 5, 6, 11 y 12 se pueden codificar como punto de código único. Curiosamente, las filas 4 y 10 también se pueden representar como un único punto de código. Si ya hay tres 1, entonces "Estado" es esencialmente no importa.

Si fusionamos 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 salidas consistentes y no necesita conocer la entrada de estado.

LUT2 será LUT de 6 entradas. Tendrá 3 bits de {LUT1, LUT0} y 3 bits vecinos restantes [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 que estableciste. Me gustaría saber si ve algún problema.