A Study on Efficient Problem Solving for Combinatorial Problems Using Programmable Logic Devices

利用现场可编程门阵列（fpga）进行可重构计算作为一种解决组合问题的新方法已经得到了广泛的应用。特别是，通过实例特定的加速器来解决问题已经得到了广泛的关注，如布尔可满足性问题、最小覆盖问题等。在本研究中，我们提出了一种基于可重构计算的新方法来解决图上的几个np困难问题，如最大团问题、最小顶点覆盖问题和最小支配集问题。在提出的方法中，对于每个问题的给定实例，生成实例特定加速器的HDL描述，以产生问题的最佳解决方案。生成的特定于实例的加速器是基于分支和界搜索与各种修剪技术。此外，还引入了流水线和并行处理，加快了计算速度。我们还开发了一个系统，该系统可以针对给定的问题实例自动生成加速器的Verilog HDL描述。生成的Verilog描述被编译并下载到FPGA中作为配置数据，通过硬件解决问题。实验结果表明，与软件求解器相比，即使考虑电路合成和FPGA配置的时间，所提算法也能在非常短的运行时间内得到问题的最优解。

Reconfigurable computing with Field Programmable Gate Arrays (FPGAs) has become popular as a new approach to combinatorial problems. In particular, problem solving by instance-specific accelerators has been widely noticed such as the Boolean satisfiability problem, the minimum cover problem, etc. In this study, we present a novel approach to solving several NP-hard problems on graphs such as the maximum clique problem, the minimum vertex cover problem, and the minimum dominating set problem, based on reconfigurable computing. In the proposed approach, for a given instance of each problem, an HDL description of an instance-specific accelerator is generated to produce an optimum solution of the problem. The generated instance-specific accelerator is based on branch & bound search with various pruning techniques. Furthermore, pipeline and parallel processing are introduced to speed up the computation time. We also developed a system, which generates the Verilog HDL description of the accelerator automatically for a given problem instance. The generated Verilog description is compiled and downloaded to an FPGA as configuration data to solve the problem by hardware. Experimental results showed that, compared with the software solver, the proposed algorithm produced an optimum solution of the problem in a 'very shorter running time even if the time for circuit synthesis and configuration of FPGA was taken into account.