权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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难的组合优化问题，通常的优化方法很难得到最优解。在本研究中，我们研究了在短执行时间内解决二次分配问题的并行算法，并提出了一种硬件算法来有效地解决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快速求解二次分配问题