Supervisor: Christoph Flothow
Earliest start: sofort
Type: Master Theses

Das Technology Mapping ist ein wichtiger Schritt in der Logiksynthese, in der die gewünschte Funktionalität der Schaltung - als Boolesche Funktionen beschrieben - auf Elemente der Zieltechnologie abgebildet wird. Bei FPGAs handelt es sich hierbei um Lookup Tables (LUTs). Die Güte dieser Abbildung kann sowohl Auswirkungen auf die erreichbare Taktfrequenz, als auch auf die Anzahl der LUTs und somit auf die Größe des benötigten FPGAs haben.

Ein gängiges Verfahren in diesem Bereich ist der sogenannte Priority Cuts Algorithmus, der in dem open source Tool ABC implementiert ist. Hier werden Cuts in einem And-Inverter Graph (AIG) so gesetzt, dass die gesamte Logik, die in einem Cut enthalten ist, direkt auf eine einzelne LUT abgebildet werden kann. Eine mögliche Optimierung dieses Verfahrens ist es, den AIG um sogenannte Structural Choices zu erweitern. Hier werden Choice Nodes dem AIG hinzugefügt, wo an jedem Eingang prinzipell identische, strukturel jedoch unterschiedliche Subgraphen angeschlossen sind. Da alle Eingänge funktional identisch sind, muss allerdings nur eine dieser Varianten tatsächlich implementiert werden, und während des Mappings kann der Algorithmus die Variante wählen, die das aktuelle Optimierungsziel am besten erreicht.

Die Erweiterung des AIG um solche Choice Nodes wird aktuell von ABC nur vor dem eigentlichen Mapping durchgeführt. Im Gegensatz dazu ist das Ziel dieser Arbeit, den Priority Cuts Algorithmus so zu erweitern, dass dynamisch während des Mappings neue Choice Nodes dem Graphen hinzugefügt werden nach gewissen Kriterien. Insbesondere wird erwartet, dass so die Tiefe des finalen Mappings verbessert werden kann.