| 講演名 | 2008-01-16 2次割当問題に対するシストリックアルゴリズムに基づくハードウェア解法(FPGAの応用) 木村 義洋, 若林 真一, 永山 忍, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 2次割当問題(Quadratic Assignment Problem, QAP)に対し,タブー探索法に基づくヒューリスティック解法をハードウェアとして実現し,FPGA上に実装することで問題を高速に解くことを提案する.提案するハードウェア解法はタブー探索法をシストリックアルゴリズムとして実現することにより,複数の近傍解を並列処理により同時に評価し,かつ各近傍解に対する目的関数の評価をパイプライン処理することで計算時間を短縮する.提案手法をFPGA上に実現し,ソフトウェア解法と比較することにより提案手法の有効性を示した. |
| 抄録(英) | For the quadratic assignment problem(QAP), a heuristic algorithm based on tabu search, which is implemented as hardware on FPGAs, is proposed to solve the problem efficiently. The proposed hardware algorithm is a systolic algorithm, in which multiple neighborhood solutions are evaluated in parallel, and for each solution, the objective function is evaluated in a pipeline fashion so as to shorten the computation time. The proposed method was implemented on an FPGA chip, and its effectiveness was shown. |
| キーワード(和) | 2次割当問題 / タブー探索法 / シストリックアルゴリズム / FPGA |
| キーワード(英) | quadratic assignment problem / tabu search / systolic algorithm / FPGA |
| 資料番号 | VLD2007-114,CPSY2007-57,RECONF2007-60 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2008/1/9(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 2次割当問題に対するシストリックアルゴリズムに基づくハードウェア解法(FPGAの応用) |
| サブタイトル（和） | |
| タイトル（英） | Solving the Quadratic Assignment Problem by Hardware Based on a Systolic Algorithm |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 2次割当問題 / quadratic assignment problem |
| キーワード(2)（和/英） | タブー探索法 / tabu search |
| キーワード(3)（和/英） | シストリックアルゴリズム / systolic algorithm |
| キーワード(4)（和/英） | FPGA / FPGA |
| 第 1 著者 氏名（和/英） | 木村 義洋 / Yoshihiro KIMURA |
| 第 1 著者 所属（和/英） | 広島市立大学大学院情報科学研究科 Graduate School of Information Sciences, Hiroshima City University |
| 第 2 著者 氏名（和/英） | 若林 真一 / Shin'ichi WAKABAYASHI |
| 第 2 著者 所属（和/英） | 広島市立大学大学院情報科学研究科 Graduate School of Information Sciences, Hiroshima City University |
| 第 3 著者 氏名（和/英） | 永山 忍 / Shinobu NAGAYAMA |
| 第 3 著者 所属（和/英） | 広島市立大学大学院情報科学研究科 Graduate School of Information Sciences, Hiroshima City University |
| 発表年月日 | 2008-01-16 |
| 資料番号 | VLD2007-114,CPSY2007-57,RECONF2007-60 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | 414 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |