| 講演抄録／キーワード |
| 講演名 |
2007-01-17 16:25
2次割当問題に対するタブー探索法に基づくFPGAを用いたハードウェア解法
○木村義洋・若林真一・永山 忍（広島市大） |
| 抄録 |
（和） |
本研究では，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 / / / / / |
| 文献情報 |
信学技報, vol. 106, no. 457, RECONF2006-62, pp. 37-42, 2007年1月. |
| 資料番号 |
RECONF2006-62 |
| 発行日 |
2007-01-10 (VLD, CPSY, RECONF) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|
| 研究会情報 |
| 研究会 |
VLD CPSY RECONF IPSJ-SLDM |
| 開催期間 |
2007-01-17 - 2007-01-18 |
| 開催地（和） |
慶応大学（日吉） |
| 開催地（英） |
Keio Univ. Hiyoshi Campus |
| テーマ（和） |
FPGAとその応用および一般 |
| テーマ（英） |
FPGA and its Application, etc. |
| 講演論文情報の詳細 |
| 申込み研究会 |
RECONF |
| 会議コード |
2007-01-VLD-CPSY-RECONF-IPSJ-SLDM |
| 本文の言語 |
日本語 |
| タイトル（和） |
2次割当問題に対するタブー探索法に基づく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 |
| キーワード(4)（和/英） |
/ |
| キーワード(5)（和/英） |
/ |
| キーワード(6)（和/英） |
/ |
| キーワード(7)（和/英） |
/ |
| キーワード(8)（和/英） |
/ |
| 第1著者 氏名（和/英/ヨミ） |
木村 義洋 / Yoshihiro Kimura / キムラ ヨシヒロ |
| 第1著者 所属（和/英） |
広島市立大学 (略称： 広島市大)
Hiroshima City University (略称： Hiroshima City Univ.) |
| 第2著者 氏名（和/英/ヨミ） |
若林 真一 / Shin'ichi Wakabayashi / ワカバヤシ シンイチ |
| 第2著者 所属（和/英） |
広島市立大学 (略称： 広島市大)
Hiroshima City University (略称： Hiroshima City Univ.) |
| 第3著者 氏名（和/英/ヨミ） |
永山 忍 / Shinobu Nagayama / ナガヤマ シノブ |
| 第3著者 所属（和/英） |
広島市立大学 (略称： 広島市大)
Hiroshima City University (略称： Hiroshima City Univ.) |
| 第4著者 氏名（和/英/ヨミ） |
/ / |
| 第4著者 所属（和/英） |
(略称： )
(略称： ) |
| 第5著者 氏名（和/英/ヨミ） |
/ / |
| 第5著者 所属（和/英） |
(略称： )
(略称： ) |
| 第6著者 氏名（和/英/ヨミ） |
/ / |
| 第6著者 所属（和/英） |
(略称： )
(略称： ) |
| 第7著者 氏名（和/英/ヨミ） |
/ / |
| 第7著者 所属（和/英） |
(略称： )
(略称： ) |
| 第8著者 氏名（和/英/ヨミ） |
/ / |
| 第8著者 所属（和/英） |
(略称： )
(略称： ) |
| 第9著者 氏名（和/英/ヨミ） |
/ / |
| 第9著者 所属（和/英） |
(略称： )
(略称： ) |
| 第10著者 氏名（和/英/ヨミ） |
/ / |
| 第10著者 所属（和/英） |
(略称： )
(略称： ) |
| 第11著者 氏名（和/英/ヨミ） |
/ / |
| 第11著者 所属（和/英） |
(略称： )
(略称： ) |
| 第12著者 氏名（和/英/ヨミ） |
/ / |
| 第12著者 所属（和/英） |
(略称： )
(略称： ) |
| 第13著者 氏名（和/英/ヨミ） |
/ / |
| 第13著者 所属（和/英） |
(略称： )
(略称： ) |
| 第14著者 氏名（和/英/ヨミ） |
/ / |
| 第14著者 所属（和/英） |
(略称： )
(略称： ) |
| 第15著者 氏名（和/英/ヨミ） |
/ / |
| 第15著者 所属（和/英） |
(略称： )
(略称： ) |
| 第16著者 氏名（和/英/ヨミ） |
/ / |
| 第16著者 所属（和/英） |
(略称： )
(略称： ) |
| 第17著者 氏名（和/英/ヨミ） |
/ / |
| 第17著者 所属（和/英） |
(略称： )
(略称： ) |
| 第18著者 氏名（和/英/ヨミ） |
/ / |
| 第18著者 所属（和/英） |
(略称： )
(略称： ) |
| 第19著者 氏名（和/英/ヨミ） |
/ / |
| 第19著者 所属（和/英） |
(略称： )
(略称： ) |
| 第20著者 氏名（和/英/ヨミ） |
/ / |
| 第20著者 所属（和/英） |
(略称： )
(略称： ) |
| 講演者 |
第1著者 |
| 発表日時 |
2007-01-17 16:25:00 |
| 発表時間 |
25分 |
| 申込先研究会 |
RECONF |
| 資料番号 |
VLD2006-91, CPSY2006-62, RECONF2006-62 |
| 巻番号（vol） |
vol.106 |
| 号番号（no） |
no.453(VLD), no.455(CPSY), no.457(RECONF) |
| ページ範囲 |
pp.37-42 |
| ページ数 |
6 |
| 発行日 |
2007-01-10 (VLD, CPSY, RECONF) |
|