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 |