Efficient Hardware Algorithms for Solving Combinatorial Optimization Problems by Using FPGAs with Dynamic Partial Reconfiguration

在本研究中，我们提出了几种解决组合优化问题的硬件算法。首先，我们提出了一种通过产生一组小的子图来解决大图的最大团问题的硬件算法，并用动态部分可重构的现场可编程门阵列展示了它的实现结果。其次，在前面研究中提出的自底向上求解器的基础上，提出了一种新的硬件可满足性求解器。它可以为问题的一个大实例获得解决方案。第三，提出了正则表达式匹配(REM)硬件引擎。在所提出的方法中，减小了电路尺寸，保持了可以处理任何RE并且可以立即更新图案的优点。

In this research, we proposed several hardware algorithms to solve combinatorial optimization problems. First, we proposed a hardware algorithm to solve the maximum clique problem of large graphs by producing a set of small subgraphs, and show its implementation results using a dynamically partially reconfigurable FPGA. Second, we proposed a new hardware satisfiability solver, which is based on the bottom-up solver proposed in our previous study. It can obtain a solution for a large instance of the problem. Third, we proposed a regular expression matching (REM) hardware engine. In the proposed method, the circuit size is reduced keeping the advantages that any RE can be handled and a pattern can be updated immediately.