| 講演名 | 2004/1/16 最大クリークを求めるデータ依存ハードウェアアルゴリズムの実装と評価(FPGAとその応用及び一般) 若林 真一, 菊池 健司, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | グラフの最大クリークを求めるハードウェアアルゴリズムを提案し,FPGA上に実装して評価した結果を報告する.提案アルゴリズムは与えられたグラフのインスタンスに基づいて構成され,分枝限定法に基づく解探索により最大クリークを効率よく求めることができる.提案アルゴリズムはハードウェアによる実現を前提としており,並列処理とパイプライン処理により効率のよい分枝限定を実現している.提案手法をFPGA上に実装して実行時間を実測し,ソフトウェアによる解法と比較して提案アルゴリズムが高速に最大クリークを求めることを確認した. |
| 抄録(英) | This report presents a hardware algorithm for finding a maximum clique of a given graph, and shows experimental evaluation of implementation of the proposed algorithm on an FPGA. The proposed algorithm is constructed according to a. given instance of graph, and can find a maximum clique efficiently based on branch and bound search. The proposed algorithm is supposed to be implmented with hardware, and realizes an efficient branch and bound search with parallel and pipeline processing. The proposed algorithm was implemented on an FPGA, and its running time was measured. Compared with the solving method with software, the proposed algorithm produced a maximum clique in a shorter running time. |
| キーワード(和) | FPGA / 最大クリーク / インスタンス / 分枝限定 / 論理合成 |
| キーワード(英) | FPGA / maximum clique / instance / branch and bound / logic synthesis |
| 資料番号 | VLD2003-135,CPSY2003-44 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2004/1/16(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 最大クリークを求めるデータ依存ハードウェアアルゴリズムの実装と評価(FPGAとその応用及び一般) |
| サブタイトル（和） | |
| タイトル（英） | Implementation and Evaluation of an Instance-Specific Hardware Algorithm for Finding a Maximum Clique |
| サブタイトル（和） | |
| キーワード(1)（和/英） | FPGA / FPGA |
| キーワード(2)（和/英） | 最大クリーク / maximum clique |
| キーワード(3)（和/英） | インスタンス / instance |
| キーワード(4)（和/英） | 分枝限定 / branch and bound |
| キーワード(5)（和/英） | 論理合成 / logic synthesis |
| 第 1 著者 氏名（和/英） | 若林 真一 / Shin'ichi WAKABAYASHI |
| 第 1 著者 所属（和/英） | 広島市立大学情報科学部 Faculty of Information Sciences, Hiroshima City University |
| 第 2 著者 氏名（和/英） | 菊池 健司 / Kenji KIKUCHI |
| 第 2 著者 所属（和/英） | 広島市立大学情報科学部 Faculty of Information Sciences, Hiroshima City University |
| 発表年月日 | 2004/1/16 |
| 資料番号 | VLD2003-135,CPSY2003-44 |
| 巻番号（vol） | vol.103 |
| 号番号（no） | 579 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |