A Study on Reconfigurable Engine for Efficient Problem Solving for Combinatorial Optimization Problems

高效求解组合优化问题的可重构引擎研究

基本信息

批准号：
18500042
负责人：
WAKABAYASHI Shinichi
金额：
$ 2.48万
依托单位：
Hiroshima City University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2006
资助国家：
日本
起止时间：
2006 至 2007
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18500042/
关键词：
Quadratic assignment problem Tabu search FPGA Systolic algorithm Parallel algorithm Pipeline processing 並列処理

项目摘要

The quadratic assignment problem (QAP), which is one of NP-hard combinatorial optimization problems, is known to be difficult to be solved optimally with ordinary optimization methods. In this research, we investigated parallel algorithms to solve the quadratic assignment problem in a short execution time, and proposed a hardware algorithm to efficiently solve the QAP. The proposed algorithm is based on tabu search, and its main body is a systolic algorithm, which runs on a one-dimensional array of simple processing units. During the algorithm execution, multiple neighborhood solutions are evaluated in parallel and each solution is evaluated in a pipeline fashion. The proposed algorithm effectively utilizes internal block RAMs of recent large scale FPGAs. The proposed hardware QAP solver was designed with Verilog-HDL, and implemented on a FPGA board. Experimental results showed the efficiency and effectiveness of the proposed algorithm. Results obtained by this research have been presented in several domestic and international conferences.

二次分配问题（QAP）是NP-HARD组合优化问题之一，已知难以通过普通优化方法最佳地解决。在这项研究中，我们研究了并行算法在短执行时间内解决二次分配问题，并提出了一种硬件算法来有效地求解QAP。所提出的算法基于禁忌搜索，其主体是一种收缩期算法，该算法在一维简单处理单元上运行。在执行算法期间，并行评估了多个邻域解决方案，并以管道方式评估每个溶液。所提出的算法有效地利用了最近大规模FPGA的内部块RAM。拟议的硬件QAP求解器是使用Verilog-HDL设计的，并在FPGA板上实施。实验结果表明了所提出的算法的效率和有效性。这项研究获得的结果已在几个国内和国际会议上提出。

项目成果

期刊论文数量（0）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

2次割当問題に対するタブー探索法に基づくシストリックアルゴリズム

基于禁忌搜索法的二次分配问题收缩算法

DOI：
发表时间：
2007
期刊：
影响因子：
0
作者：
Yoshihiro;Kimura;木村義洋
通讯作者：
木村義洋

FPGA Implementation of Tabu Search for the Quadratic Assignment Problem

二次分配问题禁忌搜索的 FPGA 实现

DOI：
发表时间：
2006
期刊：
Proc.International Conference on Field Programmable Technology
影响因子：
0
作者：
Yoshihiro;Kimura;木村義洋;若林真一;Shin'ichi Wakabayashi
通讯作者：
Shin'ichi Wakabayashi

A Systolic Algorithm for the Quadratic Assignment Problem and its FPGA Implementation

二次分配问题的脉动算法及其FPGA实现

DOI：
发表时间：
2007
期刊：
Proc.International Conference on Field Programmable Technology
影响因子：
0
作者：
東條充;一宮正博;四柳浩之;橋爪正樹;松尾英治;H. Tomimori;K. Terashima;E. Matsuo;富森英生;藤崎友樹;Y. Fujisaki;藤崎友樹;後藤隼弐;植田裕規;鮫島清豪;富森英生;高木敬介;金丸達雄;陶山優一;横田裕介;村上貴彦;T. Kanamaru;Y. Suyama;Y. Yokota;T. Murakami;金丸達雄;後藤隼弐;植田裕規;鮫島清豪;富森英生;高木敬介;H. Goto;Y. Ueda;K. Sameshima;H. Tomimori;K. Takagi;Yoshihiro Kimura
通讯作者：
Yoshihiro Kimura

FPGAを用いたタブー探索法に基づく2次割当問題の高速解法

基于禁忌搜索法的FPGA快速求解二次分配问题