Optimierung dynamischer Hardware-Rekonfiguration

Inzwischen läuft ein Projekt zur weiteren Anwendung unserer Packalgorithmen in der Praxis. Gemeinsam mit Prof. Jürgen Teich vom Fachbereich Elektrotechnik der Universität-Gesamthochschule Paderborn arbeiten wir am Einsatz unserer Packverfahren zur optimalen Belegungsplanung besonderer Computerchips, sogenannter ,,Field Programmable Gate Arrays`` (FPGAs). Diese Bauteile ermöglichen es, zahlreiche Berechnungen parallel laufen zu lassen. Nach Abschluß eines einzelnen Jobs läßt sich der dadurch freiwerdende Teilbereich des Chips softwaregesteuert für weitere Berechnungen neu konfigurieren, ohne daß andere laufende Berechnungen gestoppt werden müssen. Probleme dieser Art lassen sich als dreidimensionale Packungsprobleme mit Nebenbedingungen formulieren, wobei zwei Dimensionen die Geometrie des Chips repräsentieren (ein einzelner Job nimmt also einen rechteckigen Teilbereich ein), während die dritte Dimension für die Zeit steht.

  

Abbildung: Restriktionsgraph und optimaler Belegungsplan für die Berechnungen eines elliptischen Wellenfilters

Aufgrund unserer graphentheoretischen Charakterisierung sind die aus Reihenfolgerestriktionen für einzelne Berechnungen resultierenden Nebenbedingungen mit unserem Verfahren relativ gut zu verarbeiten, da sie auf natürliche Weise den Suchbaum einschränken. Statt eines dreidimensionalen Problemes mit schwer zu erfüllenden Zusatzbedingungen können wir das Problem in gewissen Szenarien auf ein zweidimensionales Problem reduzieren. Erste Versuche mit etablierten Benchmarkproblemen ergaben ermutigende Resultate.