２次割当問題に対するタブー探索法に基づく FPGA を用いたハードウェア解法

• Item type: SIG Technical Reports(1)
• 公開日: 2007-01-17
• タイトル: ２次割当問題に対するタブー探索法に基づく FPGA を用いたハードウェア解法
• タイトル / 言語: en
• タイトル: A Hardware Algorithm for the Quadratic Assignment Problem Based on Tabu Search Using FPGAs
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 広島市立大学情報科学部
• 著者所属: 広島市立大学情報科学部
• 著者所属: 広島市立大学情報科学部
• 著者所属(英): en
• 著者所属(英): Faculty of Information Sciences, Hiroshima City University
• 著者所属(英): en
• 著者所属(英): Faculty of Information Sciences, Hiroshima City University
• 著者所属(英): en
• 著者所属(英): Faculty of Information Sciences, Hiroshima City University
• 著者名: 木村, 義洋; 若林, 真一; 永山, 忍
• 著者名(英): Yoshihiro, KIMURA; Shin'ichi, WAKABAYASHI; Shinobu, NAGAYAMA
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本研究では、２次割当問題（QAP）に対し、タブー探索法に基づくハードウェア解法を提案する。提案アルゴリズムは FPGA の大規模内部メモリを効率よく利用することで複数の近傍解を並列処理により同時に評価し、かつ、各解に対する目的関数の評価をパイプライン処理で実行することで近傍解の評価時間を大幅に短縮している。この結果、従来のソフトウェア解法と比較して非常に短い実行時間でタブー探索法に基づく近似解を得ることを可能とした。また、FPGA のプログラム可能性を利用することで、問題サイズと FPGA チップの規模を考慮した最適なハードウェア構成が実現可能になる。提案手法を Verilog-HDL ハードウェア記述言語を用いて設計し、FPGA 上に実現して性能を評価した。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11451459
• 書誌情報: 情報処理学会研究報告システムLSI設計技術（SLDM）; 巻 2007, 号 2(2007-SLDM-128), p. 37-42, 発行日 2007-01-17
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会