Presentation | 2008-01-16 Fast calculation method of Set Cover Problem on parallel reconfigurable processor DAPDNA-2 Hiroyuki ISHIKAWA, Sho SHIMIZU, Yutaka ARAKAWA, Naoaki YAMANAKA, Kosuke SHIBA, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | This paper proposes a fast calculation method of the set cover problem, which is implemented on reconfigurable processor DAPDNA-2 of IPFlex Inc. Content replication is a widely employed technique to improve the performance of large-scale content distribution systems. Replica placement method is derived from the set cover problem which is known to be NP-hard. It is difficult to caluculate the large-scale set cover problem on a program counter-based processor. Our proposed algorithm divides the combination optimally and performs pipeline operation. Experimental results show that the proposed algorithm reduces the execution time by 40 times compared to Intel Pentium 42.8GHz. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Reconfigurable processor / DAPDNA-2 / Set cover problem / Replica placement problem / NP-hard |
Paper # | VLD2007-116,CPSY2007-59,RECONF2007-62 |
Date of Issue |
Conference Information | |
Committee | RECONF |
---|---|
Conference Date | 2008/1/9(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) | Fast calculation method of Set Cover Problem on parallel reconfigurable processor DAPDNA-2 |
Sub Title (in English) | |
Keyword(1) | Reconfigurable processor |
Keyword(2) | DAPDNA-2 |
Keyword(3) | Set cover problem |
Keyword(4) | Replica placement problem |
Keyword(5) | NP-hard |
1st Author's Name | Hiroyuki ISHIKAWA |
1st Author's Affiliation | Dept. of Information and Computer Science, Faculty of Science and Technology, Keio University() |
2nd Author's Name | Sho SHIMIZU |
2nd Author's Affiliation | Dept. of Information and Computer Science, Faculty of Science and Technology, Keio University |
3rd Author's Name | Yutaka ARAKAWA |
3rd Author's Affiliation | Dept. of Information and Computer Science, Faculty of Science and Technology, Keio University |
4th Author's Name | Naoaki YAMANAKA |
4th Author's Affiliation | Dept. of Information and Computer Science, Faculty of Science and Technology, Keio University |
5th Author's Name | Kosuke SHIBA |
5th Author's Affiliation | IPFlex Inc. |
Date | 2008-01-16 |
Paper # | VLD2007-116,CPSY2007-59,RECONF2007-62 |
Volume (vol) | vol.107 |
Number (no) | 418 |
Page | pp.pp.- |
#Pages | 6 |
Date of Issue |