Warum die klaren Domänen für Soft- und Hardware verschwimmen

Anbieter zum Thema

ISH Ingenieursozietät GmbH

Syslogic GmbH

Eurocircuits GmbH

Arrow Central Europe GmbH

Entwurf einer rekursiven Hardware

Bekannt ist, dass eine dedizierte Hardwareschaltung in einem FPGA eine Rechenleistung oberhalb der eines PCs erreichen kann. Nur, wie kann eine rekursive Hardware aussehen? Soll eine Logikschaltung sich selbst enthalten, und das auch noch mehrfach?

Um eine rekursive Hardware zu entwerfen, lohnt zunächst ein Blick darauf, wie eine Rekursion in der Software umgesetzt wird. Auch dort wird der Programmcode nicht vervielfacht. Eine Funktion ruft sich selbst auf und legt dabei einen neuen Satz lokaler Daten auf einem Stack an.

Im Falle des vorliegenden Programms wird der aktuelle Kartenstapel kopiert, eine mögliche Veränderung ausgeführt, und dann die Funktion erneut aufgerufen. Dieses Procedere lässt sich auch in Hardware umsetzen – und zwar schnell!

Ein einfacher Zustandsautomat mit nur wenigen Zuständen und ein RAM können die gleiche Operation ausführen. Das RAM bildet dabei den Stack der Rekursion.

Das RAM wird mit Zählern adressiert, und es muss, je nachdem, entweder den aktuellen Kartenstapel speichern oder den zuletzt probierten Versuch wieder zurückgeben. Und so kann man sich dann mit nur wenigen Takten pro Knoten durch den Baum der möglichen Lösungen durcharbeiten.

Zustand check:

Prüfen, welche Karte an einer Position liegt, die einen Rückwärts-Swop ermöglicht. Wenn ein Swop möglich ist, dann weiter beim Zustand swop/push sonst weiter bei pop.

Zustand swop/push:

Aktuellen Kartenstapel auf dem Stack speichern und zeitgleich die oberen n Karten vertauschen, weiter mit check.

Zustand pop:

Kartenstapel vom Stack zurückholen, es sei denn, das Spiel ist zu Ende.

Optimierte Hardware

Der Vorteil einer Hardwarelösung liegt darin, dass sich in einem FPGA leicht RAMs mit mehreren Hundert Bits Breite erzeugen lassen.

Während ein Prozessor, der Software ausführt, die Karten in einer Schleife auf den Stack kopieren muss, geht das in der Hardware in einem einzigen Takt.

Selbst wenn man Programmiertricks wie structure assignment anwendet und somit den gesamten Kartenstapel in einer einzigen Anweisung kopiert: Am Ende wird im PC ein „rep movs“-Befehl daraus, den der Prozessor in mehreren Takten ausführen muss.

Auch das Rücklesen der Daten vom Stack in die Register benötigt im FPGA nur einen einzigen Takt. Und ein Swop, ein Vertauschen der oberen n Karten, lässt sich ebenfalls in einem Takt ausführen, zeitgleich mit dem Kopieren des alten Kartenstapels auf den Stack.

Dual-Port-RAMs beschleunigen den Vorgang

(ID:28152470)