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

现场可编程门阵列(现场可编程门阵列)可重构计算作为一种新的组合问题求解方法已经成为一种流行的计算方法。特别是，通过特定实例加速器来解决问题已经引起了广泛的关注，如布尔可满足性问题、最小覆盖问题等。在这项研究中，我们提出了一种新的方法来解决图上的几个NP-Hard问题，如最大团问题、最小顶点覆盖问题、最小支配集问题，基于可重构计算。在所提出的方法中，对于每个问题的给定实例，生成特定于实例的加速器的硬件描述以产生问题的最优解。生成的特定于实例的加速器基于分支定界搜索和各种剪枝技术。此外，还引入了流水线和并行处理，加快了计算速度。我们还开发了一个系统，它为给定的问题实例自动生成加速器的Verilog HDL语言描述。生成的Verilog描述被编译并下载到现场可编程门阵列作为配置数据，通过硬件解决该问题。实验结果表明，与软件求解器相比，即使考虑到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.