Acceleration of Solving Quadratic Assignment Problems on Programmable SoC using High Level Synthesis

Conference: FSP 2017 - Fourth International Workshop on FPGAs for Software Programmers
09/07/2017 at Ghent, Belgium

Proceedings: FSP 2017

Pages: 8Language: englishTyp: PDF

Personal VDE Members are entitled to a 10% discount on this title

Authors:
Kanazawa, Kenji (Faculty of Engineering, Information and Systems, University of Tsukuba, 1-1-1 Ten-ou-dai Tsukuba Ibaraki, Japan)

Abstract:
The quadratic assignment problem (QAP) is an NP-hard combinatorial optimization problem with various real-world applications. Breakout local search (BLS) is among the best performing heuristic algorithms to solve QAPs. BLS uses an adaptive perturbation mechanism to escape from local minima that complicates the control structure of BLS while BLS involves an abundance of data-level parallelism. In this paper, we propose a hardware solver for QAP on Xilinx Zynq-MPSoC. Zynq is a programmable SoC that consists of an ARM microprocessor and a programmable logic fabric that are tightly coupled on the same chip, and developed based on a software design by using High-level synthesis. Our proposed approach leverages inherent parallelism in BLS while maintaining the algorithmic behavior and control structure in the original software design, and outperforms software execution of BLS, parallel execution of BLS on a multicore CPU, and previous accelerators on GPU.