| 講演名 | 2012-11-28 大規模グラフの最大クリーク問題に対する部分再構成可能FPGAを用いたハードウェア解法(リコンフィギャラブル応用,デザインガイア2012-VLSI設計の新しい大地-) 三浦 智香子, 永山 忍, 若林 真一, 稲木 雅人, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本稿では,大規模グラフに対する最大クリークを求めるハードウェア解法を提案し,提案解法を部分再構成可能FPGA上に実装した結果を報告する.提案解法は,従来手法では1つのFPGAで解くことができない大規模グラフに対しても,部分グラフを複数生成し,FPGAの部分再構成機能を用いることにより,1つのFPGAで解を得ることができる.提案するハードウェアアルゴリズムは分枝限定法に基づいているため,解空間を効率良く探索できるだけでなく,FPGAの部分再構成回数も削減することができる.提案手法を部分再構成機能を用いてFPGA上に実装し,既存手法では得られなかった大規模グラフに対する解か高速に得られることを確認した. |
| 抄録(英) | In this paper, we propose a hardware algorithm to solve the maximum clique problem of large graphs, and show its implementation results using a dynamically partially reconfigurable FPGA. Although existing hardware algorithms cannot solve the problem for graphs with many nodes due to the resource limitation on an FPGA, the proposed algorithm can solve the problem for such large graphs using only one FPGA by generating subgraphs from a given graph, and implementing them using dynamically partial reconfiguration of an FPGA. Since the proposed hardware algorithm is based on a branch-and-bound method, it can explore solution space efficiently, and reduce the number of partial reconfigurations of FPGA. Our experimental results using a dynamically partially reconfigurable FPGA show that the proposed algorithm can efficiently solve the problem that an existing algorithm cannot solve. |
| キーワード(和) | 最大クリーク問題 / 分枝限定法 / FPGA / 部分再構成 |
| キーワード(英) | maximum clique problem / branch-and-bound method / FPGA / partial reconfiguration |
| 資料番号 | RECONF2012-53 |
| 発行日 |
| 研究会情報 | |
| 研究会 | RECONF |
|---|---|
| 開催期間 | 2012/11/20(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Reconfigurable Systems (RECONF) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 大規模グラフの最大クリーク問題に対する部分再構成可能FPGAを用いたハードウェア解法(リコンフィギャラブル応用,デザインガイア2012-VLSI設計の新しい大地-) |
| サブタイトル（和） | |
| タイトル（英） | A Hardware Algorithm Using Dynamically Partially Reconfigurable FPGA for Solving the Maximum Clique Problem of Large Graphs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 最大クリーク問題 / maximum clique problem |
| キーワード(2)（和/英） | 分枝限定法 / branch-and-bound method |
| キーワード(3)（和/英） | FPGA / FPGA |
| キーワード(4)（和/英） | 部分再構成 / partial reconfiguration |
| 第 1 著者 氏名（和/英） | 三浦 智香子 / Chikako MIURA |
| 第 1 著者 所属（和/英） | 広島市立大学大学院情報科学研究科 Graduate School of Information Sciences, Hiroshima City University |
| 第 2 著者 氏名（和/英） | 永山 忍 / Shinobu NAGAYAMA |
| 第 2 著者 所属（和/英） | 広島市立大学大学院情報科学研究科 Graduate School of Information Sciences, Hiroshima City University |
| 第 3 著者 氏名（和/英） | 若林 真一 / Shin'ichi WAKABAYASHI |
| 第 3 著者 所属（和/英） | 広島市立大学大学院情報科学研究科 Graduate School of Information Sciences, Hiroshima City University |
| 第 4 著者 氏名（和/英） | 稲木 雅人 / Masato INAGI |
| 第 4 著者 所属（和/英） | 広島市立大学大学院情報科学研究科 Graduate School of Information Sciences, Hiroshima City University |
| 発表年月日 | 2012-11-28 |
| 資料番号 | RECONF2012-53 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | 325 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |