TY  - THES
AB  - Eine der verbreitetsten Methoden um große Suchräume effizient zu verarbeiten ist Branch-and-Bound (BaB). Bei BaB wird der Suchraum als Baumstruktur organisiert. Das Verfahren grenzt durch schrittweises Verzweigen und Begrenzen systematisch Teilbereiche des Suchraums aus, die nicht zu einer optimalen Lösung führen. In dieser Arbeit konzentrieren wir uns auf die Implementierung von BaB auf Field Programmable Gate Arrays (FPGAs). BaB gehört nicht zu den klassischen Problemen, die auf FPGAs untersucht werden, da die Berechnungen kontroll- und nicht datengesteuert sind. Wir zeigen dennoch, wie hochspezialisierte FPGA-Implementierungen die Ausführung erheblich beschleunigen können. Dazu beschreiben wir systematisch Möglichkeiten einer effizienten Implementierung durch Zustandsautomaten. Bei der Auswahl der Architektur untersuchen wir die Kompromisse zwischen hochoptimierten Datenpfaden für die leistungskritischen Teile des Suchraums und ressourceneffizienteren Datenpfaden für die seltener explorierten Teile. Dann erweitern wir unser Design um zwei Optimierungen. Die erste ist die Parallelisierung von BaB auf FPGAs mittels Work Stealing. Mehrere Instanzen bemühen sich autonom um Arbeitspakete, indem sie aktiv voneinander stehlen. Unser Design zeigt nahezu lineare Skalierungseigenschaften. Bei der zweiten Optimierung untersuchen wir instanzspezifische FPGA-Designs, angewandt auf besonders schwierige BaB-Probleme. Wir beschreiben eine vollautomatische Generierung von Designs und kombinieren diese mit Work Stealing. Zudem untersuchen wir eine On-the-Fly-Generierung der Designs, bei der die erzielte Beschleunigung die Dauer der notwendigen Synthesen überwiegt. Wir evaluieren unsere Methoden auf FPGAs und CPUs. Unsere Ergebnisse zeigen, dass unsere FPGA-Implementierung die Verarbeitungsleistung von CPUs übertreffen kann und gleichzeitig energieeffizienter ist.
AU  - Riebler, Heinrich
CY  - Paderborn
DA  - 2019
DO  - 10.17619/UNIPB/1-830
DP  - Universität Paderborn
LA  - eng
N1  - Tag der Verteidigung: 12.11.2019
N1  - Universität Paderborn, Dissertation, 2019
PB  - Veröffentlichungen der Universität
PY  - 2019
SP  - 1 Online-Ressource (xiii, 139 Seiten)
T2  - Institut für Informatik
TI  - Efficient parallel branch-and-bound search on FPGAs using work stealing and instance-specific designs
UR  - https://nbn-resolving.org/urn:nbn:de:hbz:466:2-35885
Y2  - 2026-02-06T09:22:27
ER  -