講演抄録/キーワード |
講演名 |
2008-01-16 16:35
2次割当問題に対するシストリックアルゴリズムに基づくハードウェア解法 ○木村義洋・若林真一・永山 忍(広島市大) VLD2007-114 CPSY2007-57 RECONF2007-60 |
抄録 |
(和) |
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 algoirthm / FPGA / / / / |
文献情報 |
信学技報, vol. 107, no. 418, RECONF2007-60, pp. 55-60, 2008年1月. |
資料番号 |
RECONF2007-60 |
発行日 |
2008-01-09 (VLD, CPSY, RECONF) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
VLD2007-114 CPSY2007-57 RECONF2007-60 |
|