A Study on Reconfigurable Engine for Efficient Problem Solving for Combinatorial Optimization Problems

点击翻译按钮获取中文摘要

The quadratic assignment problem (QAP), which is one of NP-hard combinatorial optimization problems, is known to be difficult to be solved optimally with ordinary optimization methods. In this research, we investigated parallel algorithms to solve the quadratic assignment problem in a short execution time, and proposed a hardware algorithm to efficiently solve the QAP. The proposed algorithm is based on tabu search, and its main body is a systolic algorithm, which runs on a one-dimensional array of simple processing units. During the algorithm execution, multiple neighborhood solutions are evaluated in parallel and each solution is evaluated in a pipeline fashion. The proposed algorithm effectively utilizes internal block RAMs of recent large scale FPGAs. The proposed hardware QAP solver was designed with Verilog-HDL, and implemented on a FPGA board. Experimental results showed the efficiency and effectiveness of the proposed algorithm. Results obtained by this research have been presented in several domestic and international conferences.