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

使用具有动态部分重配置功能的 FPGA 解决组合优化问题的高效硬件算法

• 批准号: 23500066
• 负责人: WAKABAYASHI Shin'ichi
• 金额: $ 3.33万
• 依托单位: Hiroshima City University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2011
• 资助国家: 日本
• 起止时间: 2011 至 2013
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-23500066/
• 关键词: FPGA; 動的部分再構成; 組合せ最適化; ネットワーク侵入検知; パターンマッチング

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.

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

项目成果

An Efficient Hardware Matching Engine for Regular Expression with Nested Kleene Operators

具有嵌套 Kleene 运算符的正则表达式的高效硬件匹配引擎

• 发表时间: 2011
• 作者: M. Arai;and K. Iwasaki;Yoichi Wakaba
• 通讯作者: Yoichi Wakaba

大規模グラフの最大クリーク問題に対する部分再構成可能FPGAを用いたハードウェア解法

使用部分可重构 FPGA 解决大图中最大团问题的硬件解决方案

• 发表时间: 2012
• 作者: J. Yu;R. Miyamoto;T. Onoye;H. Sugano;and Y. Nakamura;三浦智香子
• 通讯作者: 三浦智香子

A Matching Method for Look-ahead Assertion on Pattern Independent Regular Expression Matching Engine

模式无关正则表达式匹配引擎的前瞻断言匹配方法

• 发表时间: 2012
• 作者: Shunsuke Matsuoka;Shuichi Ichikawa;近藤 大樹，中道 上，青山 幹雄;Yoichi Wakaba
• 通讯作者: Yoichi Wakaba

A Flexible and Compact Regular Expression Matching Engine Using Partial Reconfiguration for FPGA

FPGA部分重配置的灵活、紧凑的正则表达式匹配引擎

• 发表时间: 2013
• 作者: 中山裕太;佐久間俊介;新井雅之;史紅波;岩崎一彦;Yoichi Wakaba
• 通讯作者: Yoichi Wakaba

ネットワーク侵入検知のためのパターン非依存NFA とシストリックアルゴリズムを組み合わせた正規表現マッチング

正则表达式匹配结合模式无关的 NFA 和脉动算法进行网络入侵检测

• 发表时间: 2011
• 作者: 福本聡;新井雅之;原慎哉;岩崎一彦;Yoichi Wakaba;河原 芳昭，青山 幹雄，松永 昌樹;田中佑，藤枝直輝，市川周一;M. Arai and K. Iwasaki;鮎澤勇介，藤枝直輝，市川周一;永山忍
• 通讯作者: 永山忍