Minimierung der Logik in einem Spartan-6 für ein Spiel der Lebenszelle

Denken Sie daran, dass Spartan-6-LUTs als einzelne LUT mit 6 Eingängen oder als duale LUTs mit 5 Eingängen konfiguriert werden können. Ich schaue mir speziell die SLICEX-Variante an, die eine Teilmenge und die am wenigsten fähige aller Spartan-6-Slices ist.

Ich denke, dies kann in 4 LUTs mit sechs Eingängen erfolgen.

Die ersten drei LUTs geben den Zustand von 6 der umgebenden Zellen ein, out gibt eine 3-Bit-Zahl aus, die die Zählung von Einsen in diesen sechs Zellen ist.

Die vierte LUT mit sechs Eingängen nimmt diese 3-Bit-Zählung plus die verbleibenden 2 umgebenden Zellen und den aktuellen Zustand der mittleren Zelle und gibt den neuen Zustand der Zelle aus.

Diese gesamte Logik kann in einen einzelnen SliceX-Block passen (passt aber auch in alle anderen Slice-Typen). Im kleinsten Spartan-6 könnten Sie 300 Zellen machen. Im größten können Sie etwas mehr als 23.000 tun.

Nichts davon spielt bei der Kommunikation eine Rolle, die zum Auslesen oder Setzen des Status der gesamten Matrix erforderlich ist. Das Auslesen könnte eine LUT + FF mit 5 Eingängen pro Zelle hinzufügen, und das Initialisieren der Matrix könnte weitere LUT + FF mit 5 Eingängen pro Zelle hinzufügen. Dies entspricht weiteren 6 Eingabe-LUTs (mit 2 FFs) pro Zelle – und einer 25%igen Steigerung der Logik, die für ein nützliches Game of Life erforderlich ist.

Ich glaube, Sie sollten dies mit 6 LUTs pro Zelle tun können. Der grundlegende Ansatz besteht darin, die 8 Eingänge in zwei Gruppen zu unterteilen, 3 Eingänge in einer Gruppe und 5 Eingänge in der anderen. Sie können die Einsen in der ersten Gruppe mit 2 LUTs zählen und die Einsen in der zweiten Gruppe mit 3 LUTs zählen, für insgesamt 5 Zwischenergebnisbits. Eine weitere LUT kann diese Bits mit dem aktuellen Zustand kombinieren, um den nächsten Zustand zu ergeben.

Da die ersten 5 LUTs parallel arbeiten, beträgt die Gesamtlatenz außerdem nur zwei LUTs, sodass Sie diese mit einer sehr hohen Taktrate betreiben können sollten.

Der folgende Code gibt die allgemeine Idee wieder. Einige der Syntaxdetails könnten etwas abweichen – mein VHDL ist ein wenig eingerostet.

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

Der größte Spartan-6 hat 23038 Slices, von denen jedes vier 64-Bit-LUTs enthält. Beachten Sie, dass jede dieser LUTs auch in zwei 32-Bit-LUTs aufgeteilt werden kann, solange sie dieselben Eingänge teilen. Dies bedeutet, dass eine Lebenszelle nur einen Slice zur Implementierung benötigt. Sie könnten ein 150×150-Spiel des Lebens machen, das mit Hunderten von Millionen Generationen/Sekunde läuft. Oder Sie könnten die BRAMs verwenden, um ein Spiel des Lebens in der Größe eines HDTV-Bildschirms (1920 × 1080) doppelt zu puffern und es mit etwa einer Million Generationen/Sekunde laufen zu lassen.

Ich denke, es kann in 3 LUTs passen, aber es wird nicht so elegant sein wie Davids Lösung. Aber die LUT zu reduzieren ist ein Ziel, dann kann das funktionieren. Außerdem habe ich nicht mit Spartan-6-FPGAs gearbeitet. Ich stütze diese Analyse auf:

http://www.xilinx.com/support/documentation/user_guides/ug384.pdf insbesondere Abbildung 6 auf Seite 13.

Hier kommt's:

1. LUT 0 wird als Dual-LUT mit 5 Eingängen verwendet. Seine Eingänge sind Bits [4:0] von "Nachbarn".
2. LUT 1 wird als LUT mit 6 Eingängen verwendet. Seine Eingaben sind {Zustand, Nachbarn[4:0]}

Beide arbeiten zusammen, um eine 3-Bit-codierte Ausgabe wie in dieser Tabelle zu erzeugen:

So lesen Sie die Tabelle. Zeile 1 sagt: "Wenn der Zustand 0 ist und es null Einsen in Bits [4:0] gibt, müssen drei Einsen in den verbleibenden 3 Bits vorhanden sein, damit der nächste Zustand 1 ist." Wie Sie sehen können, gibt es 12 eindeutige Eingabekombinationen, die codiert werden müssen. Aber es gibt nur wenige Möglichkeiten, zusammenzuführen. Erstens, wenn bereits 4 oder 5 Einsen vorhanden sind, ist State nicht 1, sodass die Zeilen 5, 6, 11 und 12 als einzelner Codepunkt codiert werden können. Interessanterweise können die Zeilen 4 und 10 auch als einzelner Codepunkt dargestellt werden. Wenn es bereits drei Einsen gibt, ist "State" im Wesentlichen egal.

Wenn wir Zeilen auf diese Weise zusammenführen, gibt es 8 eindeutige Codepunkte, die genügend Informationen für die Verarbeitung der verbleibenden 3 Bits enthalten. Bitte beachten Sie, dass State hier bereits kodiert ist und nicht weiter benötigt wird.

Codepunkte werden so ausgewählt, dass LUT0 konsistente Ausgaben generiert und nichts über die Statuseingabe wissen muss.

LUT2 wird eine LUT mit 6 Eingängen sein. Es wird 3 Bits von {LUT1, LUT0} und 3 verbleibende Bits von Nachbarn [7:5] haben. Es interpretiert diese Bits gemäß der Aktionsspalte der Tabelle, um den nächsten Zustand zu erzeugen.

Ich denke, es erfüllt die von Ihnen gestellten Anforderungen. Ich würde gerne hören, ob Sie ein Problem sehen.