| 講演名 | 2009-05-14 高いスループットを実現する組み合わせ生成アルゴリズムの提案と実装(リコンフィギャラブル応用) 辻 聡, 山垣 則夫, 神谷 聡史, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 組み合わせ最適化問題と呼ばれる問題は世の中に広く存在している.組み合わせ最適化問題はNP困難な問題であるため,一般的にはgreedy法のような近似解法を用いて解かれている.しかし,近似解法では,問題によっては局所解に陥り,最適解との差が大きくなってしまう場合や,解を算出できない場合がある.一方,ハードウェアの性能向上などの要因により,組み合わせを総当たりで調べる列挙法を用いた場合でも,最適解を現実的な時間で得ることができる可能性が出てきている.列挙法の高速化のためには,組み合わせを高速に生成する必要がある.そこで,本稿では列挙法の高速化を目的とし,既存の組み合わせ生成アルゴリズムの性能評価を行い,高速化のための課題を明らかにする.さらに,従来よりも高速に組み合わせの生成を行うことが可能なアルゴリズムを提案する.FPGAを対象デバイスとして提案アルゴリズムをハードウェア化し,性能評価を行った結果,既存の組み合わせ生成アルゴリズムを汎用CPUを用いて実行した場合に比べて500倍以上,専用ハードウェアで生成した場合に比べて10倍以上の速度で組み合わせを生成可能であることが示された. |
| 抄録(英) | Combinatorial optimization problems are widely exist. Generally they are solved by approximate means like greedy method because they are categorized as NP-hard. However, in several cases, the solution is likely to be local optimized. In the worst case, no solutions can be obtained. Meanwhile, even if brute force method like enumeration method is used, there is a possibility that optimized solutions can be obtained within realistic time because of resent performance improvement of processors and other reasons. For speeding up the enumeration method, a method of fast combination generation is required. In this paper, we clarify the problems for speeding up of enumeration method through performance evaluations of existing combination generation algorithms. Moreover, we propose a faster combination generation algorithm than existings. In the results of the performance evaluations, the dedicated hardware of the proposed algorithm achieves about 500 times faster than software of the existing algorithm and about 10 times than the dedicated hardware of that. |
| キーワード(和) | 組み合わせ最適化問題 / 列挙法 / 組み合わせ生成 / FPGA |
| キーワード(英) | combinatorial optimization problem / enumeration method / combination generation / FPGA |
| 資料番号 | RECONF2009-5 |
| 発行日 |
| 研究会情報 | |
| 研究会 | RECONF |
|---|---|
| 開催期間 | 2009/5/7(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Reconfigurable Systems (RECONF) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 高いスループットを実現する組み合わせ生成アルゴリズムの提案と実装(リコンフィギャラブル応用) |
| サブタイトル（和） | |
| タイトル（英） | Proposal and Implementation of High Throughput Algorithm for Combination Generation |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 組み合わせ最適化問題 / combinatorial optimization problem |
| キーワード(2)（和/英） | 列挙法 / enumeration method |
| キーワード(3)（和/英） | 組み合わせ生成 / combination generation |
| キーワード(4)（和/英） | FPGA / FPGA |
| 第 1 著者 氏名（和/英） | 辻 聡 / Akira TSUJI |
| 第 1 著者 所属（和/英） | NECシステムIPコア研究所 System IP Core Research Laboratories, NEC Corporation |
| 第 2 著者 氏名（和/英） | 山垣 則夫 / Norio YAMAGAKI |
| 第 2 著者 所属（和/英） | NECシステムIPコア研究所 System IP Core Research Laboratories, NEC Corporation |
| 第 3 著者 氏名（和/英） | 神谷 聡史 / Satoshi KAMIYA |
| 第 3 著者 所属（和/英） | NECシステムIPコア研究所 System IP Core Research Laboratories, NEC Corporation |
| 発表年月日 | 2009-05-14 |
| 資料番号 | RECONF2009-5 |
| 巻番号（vol） | vol.109 |
| 号番号（no） | 26 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |