Presentation 2007-01-17
A Hardware Algorithm for the Quadratic Assignment Problem Based on Tabu Search Using FPGAs
Yoshihiro KIMURA, Shin'ichi WAKABAYASHI, Shinobu NAGAYAMA,
PDF Download Page PDF download Page Link
Abstract(in Japanese) (See Japanese page)
Abstract(in English) 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.
Keyword(in Japanese) (See Japanese page)
Keyword(in English) quadratic assignment problem / tabu search / FPGA
Paper # VLD2006-91,CPSY2006-62,RECONF2006-62
Date of Issue

Conference Information
Committee RECONF
Conference Date 2007/1/10(1days)
Place (in Japanese) (See Japanese page)
Place (in English)
Topics (in Japanese) (See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To Reconfigurable Systems (RECONF)
Language JPN
Title (in Japanese) (See Japanese page)
Sub Title (in Japanese) (See Japanese page)
Title (in English) A Hardware Algorithm for the Quadratic Assignment Problem Based on Tabu Search Using FPGAs
Sub Title (in English)
Keyword(1) quadratic assignment problem
Keyword(2) tabu search
Keyword(3) FPGA
1st Author's Name Yoshihiro KIMURA
1st Author's Affiliation Faculty of Information Sciences, Hiroshima City University()
2nd Author's Name Shin'ichi WAKABAYASHI
2nd Author's Affiliation Faculty of Information Sciences, Hiroshima City University
3rd Author's Name Shinobu NAGAYAMA
3rd Author's Affiliation Faculty of Information Sciences, Hiroshima City University
Date 2007-01-17
Paper # VLD2006-91,CPSY2006-62,RECONF2006-62
Volume (vol) vol.106
Number (no) 457
Page pp.pp.-
#Pages 6
Date of Issue