| 講演名 | 2007-01-17 2次割当問題に対するタブー探索法に基づくFPGAを用いたハードウェア解法(FPGAとその応用及び一般) 木村 義洋, 若林 真一, 永山 忍, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本研究では,2次割当問題(QAP)に対し,タブー探索法に基づくハードウェア解法を提案する.提案アルゴリズムはFPGAの大規模内部メモリを効率よく利用することで複数の近傍解を並列処理により同時に評価し,かつ,各解に対する目的関数の評価をパイプライン処理で実行することで近傍解の評価時間を大幅に短縮している.この結果,従来のソフトウェア解法と比較して非常に短い実行時間でタブー探索法に基づく近似解を得ることを可能とした.また,FPGAのプログラム可能性を利用することで,問題サイズとFPGAチップの規模を考慮した最適なハードウェア構成が実現可能になる.提案手法をVerilog-HDLハードウェア記述言語を用いて設計し,FPGA上に実現して性能を評価した. |
| 抄録(英) | In this paper, a hardware algorithm for the quadratic assignment problem (QAP) based on tabu search was proposed. The proposed algorithm effectively utilizes internal RAMs in FPGAs so that multiple neighborhood solutions are evaluated in parallel, and each neighborhood solution is evaluated in a pipeline fashion. From those features of the proposed algorithm, execution time of the tabu search for the QAP can be significantly shortened compared with its software implementation. Furthermore, utilizing the programability of FPGA devices, an optimal circuit structure of the proposed method can be easily implemented for a given instance of the problem and the size of a FPGA chip to be used. The proposed method was designed with the Verilog-HDL, and its performance was experimentally evaluated. |
| キーワード(和) | 2次割当問題 / タブー探索法 / FPGA |
| キーワード(英) | quadratic assignment problem / tabu search / FPGA |
| 資料番号 | VLD2006-91,CPSY2006-62,RECONF2006-62 |
| 発行日 |
| 研究会情報 | |
| 研究会 | RECONF |
|---|---|
| 開催期間 | 2007/1/10(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Reconfigurable Systems (RECONF) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 2次割当問題に対するタブー探索法に基づくFPGAを用いたハードウェア解法(FPGAとその応用及び一般) |
| サブタイトル（和） | |
| タイトル（英） | A Hardware Algorithm for the Quadratic Assignment Problem Based on Tabu Search Using FPGAs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 2次割当問題 / quadratic assignment problem |
| キーワード(2)（和/英） | タブー探索法 / tabu search |
| キーワード(3)（和/英） | FPGA / FPGA |
| 第 1 著者 氏名（和/英） | 木村 義洋 / Yoshihiro KIMURA |
| 第 1 著者 所属（和/英） | 広島市立大学情報科学部 Faculty of Information Sciences, Hiroshima City University |
| 第 2 著者 氏名（和/英） | 若林 真一 / Shin'ichi WAKABAYASHI |
| 第 2 著者 所属（和/英） | 広島市立大学情報科学部 Faculty of Information Sciences, Hiroshima City University |
| 第 3 著者 氏名（和/英） | 永山 忍 / Shinobu NAGAYAMA |
| 第 3 著者 所属（和/英） | 広島市立大学情報科学部 Faculty of Information Sciences, Hiroshima City University |
| 発表年月日 | 2007-01-17 |
| 資料番号 | VLD2006-91,CPSY2006-62,RECONF2006-62 |
| 巻番号（vol） | vol.106 |
| 号番号（no） | 457 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |