Details

Autor(en) / Beteiligte

• Riebler, Heinrich
• Plessl, Christian[Akademischer Betreuer]
• Platzner, Marco[Akademischer Betreuer]
• Meyer auf der Heide, Friedhelm[Akademischer Betreuer]
• Tierney, Kevin[Akademischer Betreuer]
• Lettmann, Theodor[Akademischer Betreuer]

Titel

Efficient parallel branch-and-bound search on FPGAs using work stealing and instance-specific designs

Ort / Verlag

Paderborn

Erscheinungsjahr

2019

Verknüpfte Titel

Beschreibungen/Notizen

• Tag der Verteidigung: 12.11.2019
• ger: 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.
• eng: One of the most common methods for processing large search spaces is using branch-and-bound (BaB) algorithms. The search space in BaB is organized in a tree data structure and the algorithm tries to eliminate infeasible solutions as early as possible by pruning unpromising subtrees through a bounding function. In this thesis, we study the insufficiently understood realization of BaB for field programmable gate arrays (FPGAs). BaB problems are not the typical class of problems that have been tackled using FPGAs, because they are control-driven and not data-driven. In this thesis, we show that custom hardware designs can significantly accelerate the execution of BaB algorithms. We develop and demonstrate their efficient implementation as finite state machines. Our architecture shows trade-offs between highly optimized combinational datapaths for the performance-critical parts of the search tree and more resource-efficient pipelined ones for the less frequent and more complex parts. Then we extend our design with two optimization techniques to further improve efficiency. We introduce the concept of work stealing to allow parallel execution of BaB on FPGAs. Hardware workers dynamically share and balance their work and show near linear speedups. Then we explore the advantages of instance-specific designs that target a specific problem instance and combine them with the design using work stealing. We present a fully automated generation of custom-tailored designs that existing tools do not deliver. We demonstrate how instance-specific designs can be generated on-the-fly such that the provided speedups outweigh the additional time required for design synthesis. Finally, we evaluate all of our approaches and compare each result to those obtained using similar techniques in software. ...