| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2009-05-14 15:10 高いスループットを実現する組み合わせ生成アルゴリズムの提案と実装 ○辻 聡・山垣則夫・神谷聡史（NEC）  RECONF2009-5 |
|
| 抄録 | （和） | 組み合わせ最適化問題と呼ばれる問題は世の中に広く存在している． 組み合わせ最適化問題は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 / / / / | |
| 文献情報 | 信学技報, vol. 109, no. 26, RECONF2009-5, pp. 25-30, 2009年5月. | |
| 資料番号 | RECONF2009-5 | |
| 発行日 | 2009-05-07 (RECONF) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | RECONF2009-5 |
|
| 研究会情報 | |
| 研究会 | RECONF |
| 開催期間 | 2009-05-14 - 2009-05-15 |
| 開催地（和） | 福井大学文京キャンパス |
| 開催地（英） | |
| テーマ（和） | リコンフィギャラブルシステム，一般 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | RECONF |
| 会議コード | 2009-05-RECONF |
| 本文の言語 | 日本語 |
| タイトル（和） | 高いスループットを実現する組み合わせ生成アルゴリズムの提案と実装 |
| サブタイトル（和） | |
| タイトル（英） | Proposal and Implementation of High Throughput Algorithm for Combination Generation |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 組み合わせ最適化問題 / combinatorial optimization problem |
| キーワード(2)（和/英） | 列挙法 / enumeration method |
| キーワード(3)（和/英） | 組み合わせ生成 / combination generation |
| キーワード(4)（和/英） | FPGA / FPGA |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 辻 聡 / Akira Tsuji / ツジ アキラ |
| 第1著者 所属（和/英） | 日本電気株式会社 (略称： NEC) NEC Corporation (略称： NEC) |
| 第2著者 氏名（和/英/ヨミ） | 山垣 則夫 / Norio Yamagaki / ヤマガキ ノリオ |
| 第2著者 所属（和/英） | 日本電気株式会社 (略称： NEC) NEC Corporation (略称： NEC) |
| 第3著者 氏名（和/英/ヨミ） | 神谷 聡史 / Satoshi Kamiya / カミヤ サトシ |
| 第3著者 所属（和/英） | 日本電気株式会社 (略称： NEC) NEC Corporation (略称： NEC) |
| 講演者 | 第1著者 |
| 発表日時 | 2009-05-14 15:10:00 |
| 発表時間 | 30分 |
| 申込先研究会 | RECONF |
| 資料番号 | RECONF2009-5 |
| 巻番号（vol） | vol.109 |
| 号番号（no） | no.26 |
| ページ範囲 | pp.25-30 |
| ページ数 | 6 |
| 発行日 | 2009-05-07 (RECONF) |
[研究会発表申込システムのトップページに戻る]