| 講演名 | 2008-01-16 並列リコンフィギャラブルプロセッサDAPDNA-2を用いた集合被覆問題の高速解法(FPGAの応用) 石川 浩行, 清水 翔, 荒川 豊, 山中 直明, 斯波 康祐, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 高速広帯域ネットワークの発展を背景に普及した,大容量の映像を配信するためのサービスにおいては,ユーザがオリジナルサーバからのみコンテンツをダウンロードした場合,オリジナルサーバの負荷が大きくなる.一方,オリジナルサーバ以外にもコンテンツを分散させる手法が提案されているが,コンテンツレプリカの最適配置計算は集合被覆問題に帰着され,NP困難である.そのためネットワーク規模が膨大になると,ソフトウェアで処理することは難しい.本研究では,レプリカ配置の全組合せを複数グループに最適分割してパイプライン処理を行う集合被覆問題の高速解法を提案する.IPFlex社が開発した並列リコンフィギャラブルプロセッサDAPDNA-2の評価ボードに実装し,特性評価の結果,動作クロック数が17倍のIntel Pentium4と比較して実行時間が40倍以上改善することから,提案方式の有効性を示す. |
| 抄録(英) | 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. |
| キーワード(和) | リコンフィギャラブルプロセッサ / DAPDNA-2 / 集合被覆問題 / レプリカ配置問題 / NP困難 |
| キーワード(英) | Reconfigurable processor / DAPDNA-2 / Set cover problem / Replica placement problem / NP-hard |
| 資料番号 | VLD2007-116,CPSY2007-59,RECONF2007-62 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2008/1/9(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 並列リコンフィギャラブルプロセッサDAPDNA-2を用いた集合被覆問題の高速解法(FPGAの応用) |
| サブタイトル（和） | |
| タイトル（英） | Fast calculation method of Set Cover Problem on parallel reconfigurable processor DAPDNA-2 |
| サブタイトル（和） | |
| キーワード(1)（和/英） | リコンフィギャラブルプロセッサ / Reconfigurable processor |
| キーワード(2)（和/英） | DAPDNA-2 / DAPDNA-2 |
| キーワード(3)（和/英） | 集合被覆問題 / Set cover problem |
| キーワード(4)（和/英） | レプリカ配置問題 / Replica placement problem |
| キーワード(5)（和/英） | NP困難 / NP-hard |
| 第 1 著者 氏名（和/英） | 石川 浩行 / Hiroyuki ISHIKAWA |
| 第 1 著者 所属（和/英） | 慶應義塾大学理工学部情報工学科 Dept. of Information and Computer Science, Faculty of Science and Technology, Keio University |
| 第 2 著者 氏名（和/英） | 清水 翔 / Sho SHIMIZU |
| 第 2 著者 所属（和/英） | 慶應義塾大学理工学部情報工学科 Dept. of Information and Computer Science, Faculty of Science and Technology, Keio University |
| 第 3 著者 氏名（和/英） | 荒川 豊 / Yutaka ARAKAWA |
| 第 3 著者 所属（和/英） | 慶應義塾大学理工学部情報工学科 Dept. of Information and Computer Science, Faculty of Science and Technology, Keio University |
| 第 4 著者 氏名（和/英） | 山中 直明 / Naoaki YAMANAKA |
| 第 4 著者 所属（和/英） | 慶應義塾大学理工学部情報工学科 Dept. of Information and Computer Science, Faculty of Science and Technology, Keio University |
| 第 5 著者 氏名（和/英） | 斯波 康祐 / Kosuke SHIBA |
| 第 5 著者 所属（和/英） | アイピーフレックス株式会社 IPFlex Inc. |
| 発表年月日 | 2008-01-16 |
| 資料番号 | VLD2007-116,CPSY2007-59,RECONF2007-62 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | 414 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |