2次割当問題に対するシストリックアルゴリズムに基づくハードウェア解法

• Item type: SIG Technical Reports(1)
• 公開日: 2008-01-16
• タイトル: 2次割当問題に対するシストリックアルゴリズムに基づくハードウェア解法
• タイトル / 言語: en
• タイトル: Solving the Quadratic Assignment Problem by Hardware Based on a Systolic Algorithm
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 広島市立大学大学院情報科学研究科
• 著者所属: 広島市立大学大学院情報科学研究科
• 著者所属: 広島市立大学大学院情報科学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Hiroshima City University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Hiroshima City University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Hiroshima City University
• 著者名: 木村, 義洋; 若林, 真一; 永山, 忍
• 著者名(英): Yoshihiro, KIMURA; Shin'ichi, WAKABAYASHI; Shinobu, NAGAYAMA
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 2次割当問題(Quadratic Assignment Problem，QAP)に対し，タブー探索法に基づくヒューリスティック解法をハードウェアとして実現し，FPGA上に実装することで問題を高速に解くことを提案する．提案するハードウェア解法はタブー探索法をシストリックアルゴリズムとして実現することにより，複数の近傍解を並列処理により同時に評価し，かつ各近傍解に対する目的関数の評価をパイプライン処理することで計算時間を短縮する．提案手法をFPGA上に実現し，ソフトウェア解法と比較することにより提案手法の有効性を示した。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11451459
• 書誌情報: 情報処理学会研究報告システムLSI設計技術（SLDM）; 巻 2008, 号 2(2008-SLDM-133), p. 55-60, 発行日 2008-01-16
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会