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

在本研究中，我们提出了几种硬件算法来解决组合优化问题。首先，我们提出了一种通过生成一组小子图来解决大图最大团问题的硬件算法，并使用动态部分可重构的FPGA展示了其实现结果。其次，我们提出了一种新的硬件满意度求解器，它是在我们之前的研究中提出的自下而上求解器的基础上提出的。它可以得到问题的一个大实例的解。第三，提出了正则表达式匹配（REM）硬件引擎。在该方法中，减小了电路尺寸，保持了任何正则都可以处理和模式可以立即更新的优点。

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.