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

利用可编程逻辑器件高效解决组合问题的研究

基本信息

批准号：
15500040
负责人：
WAKABAYASHI Shinichi
金额：
$ 2.37万
依托单位：
Hiroshima City University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2003
资助国家：
日本
起止时间：
2003 至 2004
项目状态：
已结题

项目摘要

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.

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