Efficient Branch and Bound on FPGAs Using Work Stealing and Instance-Specific Designs

H. Riebler, M. Lass, R. Mittendorf, T. Löcke, C. Plessl, ACM Transactions on Reconfigurable Technology and Systems (TRETS) 10 (2017) 24:1-24:23.

Download
Restricted a24-riebler.pdf 2.13 MB
Journal Article | Published | English
Author
Abstract
Branch and bound (B&B) algorithms structure the search space as a tree and eliminate infeasible solutions early by pruning subtrees that cannot lead to a valid or optimal solution. Custom hardware designs significantly accelerate the execution of these algorithms. In this article, we demonstrate a high-performance B&B implementation on FPGAs. First, we identify general elements of B&B algorithms and describe their implementation as a finite state machine. Then, we introduce workers that autonomously cooperate using work stealing to allow parallel execution and full utilization of the target FPGA. Finally, we explore advantages of instance-specific designs that target a specific problem instance to improve performance. We evaluate our concepts by applying them to a branch and bound problem, the reconstruction of corrupted AES keys obtained from cold-boot attacks. The evaluation shows that our work stealing approach is scalable with the available resources and provides speedups proportional to the number of workers. Instance-specific designs allow us to achieve an overall speedup of 47 × compared to the fastest implementation of AES key reconstruction so far. Finally, we demonstrate how instance-specific designs can be generated just-in-time such that the provided speedups outweigh the additional time required for design synthesis.
Keywords
Publishing Year
Journal Title
ACM Transactions on Reconfigurable Technology and Systems (TRETS)
Volume
10
Issue
3
Page
24:1-24:23
ISSN
LibreCat-ID
18

Cite this

Riebler H, Lass M, Mittendorf R, Löcke T, Plessl C. Efficient Branch and Bound on FPGAs Using Work Stealing and Instance-Specific Designs. ACM Transactions on Reconfigurable Technology and Systems (TRETS). 2017;10(3):24:1-24:23. doi:10.1145/3053687
Riebler, H., Lass, M., Mittendorf, R., Löcke, T., & Plessl, C. (2017). Efficient Branch and Bound on FPGAs Using Work Stealing and Instance-Specific Designs. ACM Transactions on Reconfigurable Technology and Systems (TRETS), 10(3), 24:1-24:23. https://doi.org/10.1145/3053687
@article{Riebler_Lass_Mittendorf_Löcke_Plessl_2017, title={Efficient Branch and Bound on FPGAs Using Work Stealing and Instance-Specific Designs}, volume={10}, DOI={10.1145/3053687}, number={3}, journal={ACM Transactions on Reconfigurable Technology and Systems (TRETS)}, publisher={Association for Computing Machinery (ACM)}, author={Riebler, Heinrich and Lass, Michael and Mittendorf, Robert and Löcke, Thomas and Plessl, Christian}, year={2017}, pages={24:1-24:23} }
Riebler, Heinrich, Michael Lass, Robert Mittendorf, Thomas Löcke, and Christian Plessl. “Efficient Branch and Bound on FPGAs Using Work Stealing and Instance-Specific Designs.” ACM Transactions on Reconfigurable Technology and Systems (TRETS) 10, no. 3 (2017): 24:1-24:23. https://doi.org/10.1145/3053687.
H. Riebler, M. Lass, R. Mittendorf, T. Löcke, and C. Plessl, “Efficient Branch and Bound on FPGAs Using Work Stealing and Instance-Specific Designs,” ACM Transactions on Reconfigurable Technology and Systems (TRETS), vol. 10, no. 3, p. 24:1-24:23, 2017, doi: 10.1145/3053687.
Riebler, Heinrich, et al. “Efficient Branch and Bound on FPGAs Using Work Stealing and Instance-Specific Designs.” ACM Transactions on Reconfigurable Technology and Systems (TRETS), vol. 10, no. 3, Association for Computing Machinery (ACM), 2017, p. 24:1-24:23, doi:10.1145/3053687.
Main File(s)
File Name
a24-riebler.pdf 2.13 MB
Access Level
Restricted Closed Access
Last Uploaded
2018-11-02T16:04:14Z


Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar