{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:07:36Z","timestamp":1750306056864,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,6,27]],"date-time":"2017-06-27T00:00:00Z","timestamp":1498521600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100011102","name":"European Union Seventh Framework Programme","doi-asserted-by":"crossref","award":["610996 (SAVE)"],"award-info":[{"award-number":["610996 (SAVE)"]}],"id":[{"id":"10.13039\/100011102","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Maxeler program MAX-UP"},{"name":"Paderborn Center for Parallel Computing"},{"name":"German Research Foundation (DFG) within the Collaborative Research Centre \u201cOn-The-Fly Computing\u201d","award":["SFB 901"],"award-info":[{"award-number":["SFB 901"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Reconfigurable Technol. Syst."],"published-print":{"date-parts":[[2017,9,30]]},"abstract":"<jats:p>Branch and bound (B8B) 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 B8B implementation on FPGAs. First, we identify general elements of B8B 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.<\/jats:p>\n          <jats:p>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 \u00d7 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.<\/jats:p>","DOI":"10.1145\/3053687","type":"journal-article","created":{"date-parts":[[2017,6,28]],"date-time":"2017-06-28T12:27:07Z","timestamp":1498652827000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Efficient Branch and Bound on FPGAs Using Work Stealing and Instance-Specific Designs"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3811-894X","authenticated-orcid":false,"given":"Heinrich","family":"Riebler","sequence":"first","affiliation":[{"name":"Paderborn University, Paderborn, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5708-7632","authenticated-orcid":false,"given":"Michael","family":"Lass","sequence":"additional","affiliation":[{"name":"Paderborn University, Paderborn, Germany"}]},{"given":"Robert","family":"Mittendorf","sequence":"additional","affiliation":[{"name":"Paderborn University, Paderborn, Germany"}]},{"given":"Thomas","family":"L\u00f6cke","sequence":"additional","affiliation":[{"name":"Paderborn University, Paderborn, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5728-9982","authenticated-orcid":false,"given":"Christian","family":"Plessl","sequence":"additional","affiliation":[{"name":"Paderborn University, Paderborn, Germany"}]}],"member":"320","published-online":{"date-parts":[[2017,6,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.1631"},{"volume-title":"Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA\u201915)","author":"Beri A. Tarun","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324234"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/646692.759487"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391469.1391669"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07518-1_9"},{"volume-title":"Proceedings of the International Symposium on Parallel and Distributed Processing (IPDPS\u201910)","author":"Guo Y.","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1506409.1506429"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0017441"},{"volume-title":"RAM Is Key: Extracting Disk Encryption Keys from Volatile Memory. Master\u2019s thesis","author":"Kaplan Brian","key":"e_1_2_1_10_1"},{"volume-title":"Proceedings of the International Conference on Applied Electronics (AE\u201910)","year":"2010","author":"Ka\u0161\u00edk Vladimir","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FCCM.2012.12"},{"volume-title":"Proceedings of the High Performance Extreme Computing Conference (HPEC\u201915)","author":"Kumar V.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.2307\/1910129"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/SBAC-PAD.2012.28"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2015.03.001"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPL.2011.53"},{"volume-title":"Proceedings of the International Conference on High Performance Computing 8 Simulation (HPCS\u201915)","author":"Melab N.","key":"e_1_2_1_18_1"},{"volume-title":"Proceedings of the Conference on Partitioned Global Address Space Programming Models (PGAS\u201911)","year":"2011","author":"Min Seung-Jai","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-014-1200-3"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2012.78"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1024443416592"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2847263.2847343"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/2650280.2650322"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPT.2013.6718394"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2004.825859"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-05445-7_14"},{"volume-title":"Localization and Extraction of Cryptographic Keys from Memory Images and Data Streams. Master\u2019s thesis","author":"Wang Qichao","key":"e_1_2_1_28_1"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-61551-2_96"},{"volume-title":"Proceedings of the Logic Synthesis Workshop. Citeseer.","year":"1997","author":"Zhong Peixin","key":"e_1_2_1_30_1"}],"container-title":["ACM Transactions on Reconfigurable Technology and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3053687","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3053687","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:03:36Z","timestamp":1750215816000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3053687"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,27]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,9,30]]}},"alternative-id":["10.1145\/3053687"],"URL":"https:\/\/doi.org\/10.1145\/3053687","relation":{},"ISSN":["1936-7406","1936-7414"],"issn-type":[{"type":"print","value":"1936-7406"},{"type":"electronic","value":"1936-7414"}],"subject":[],"published":{"date-parts":[[2017,6,27]]},"assertion":[{"value":"2016-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-06-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}