| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2008-01-16 17:25 並列リコンフィギャラブルプロセッサDAPDNA-2を用いた集合被覆問題の高速解法 ○石川浩行・清水 翔・荒川 豊・山中直明（慶大）・斯波康祐（アイピーフレックス）  VLD2007-116 CPSY2007-59 RECONF2007-62 |
|
| 抄録 | （和） | 高速広帯域ネットワークの発展を背景に普及した，大容量の映像を配信するためのサービスにおいては，ユーザがオリジナルサーバからのみコンテンツをダウンロードした場合，オリジナルサーバの負荷が大きくなる．一方，オリジナルサーバ以外にもコンテンツを分散させる手法が提案されているが，コンテンツレプリカの最適配置計算は集合被覆問題に帰着され，NP困難である．そのためネットワーク規模が膨大になると，ソフトウェアで処理することは難しい．本研究では，レプリカ配置の全組合せを複数グループに最適分割してパイプライン処理を行う集合被覆問題の高速解法を提案する．IPFlex社が開発した並列リコンフィギャラブルプロセッサDAPDNA-2の評価ボードに実装し，特性評価の結果，動作クロック数が17倍のIntel Pentium 4と比較して実行時間が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 4 2.8GHz. |
|
| キーワード | （和） | リコンフィギャラブルプロセッサ / DAPDNA-2 / 集合被覆問題 / レプリカ配置問題 / NP困難 / / / |
| （英） | Reconfigurable processor / DAPDNA-2 / Set Cover Problem / Replica placement / NP-hard / / / | |
| 文献情報 | 信学技報, vol. 107, no. 418, RECONF2007-62, pp. 67-72, 2008年1月. | |
| 資料番号 | RECONF2007-62 | |
| 発行日 | 2008-01-09 (VLD, CPSY, RECONF) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | VLD2007-116 CPSY2007-59 RECONF2007-62 |
|
| 研究会情報 | |
| 研究会 | RECONF CPSY VLD IPSJ-SLDM |
| 開催期間 | 2008-01-16 - 2008-01-17 |
| 開催地（和） | 慶應義塾大学日吉キャンパス |
| 開催地（英） | Hiyoshi Campus, Keio University |
| テーマ（和） | FPGA応用および一般 |
| テーマ（英） | FPGA Applications, etc |
| 講演論文情報の詳細 | |
| 申込み研究会 | RECONF |
| 会議コード | 2008-01-RECONF-CPSY-VLD-IPSJ-SLDM |
| 本文の言語 | 日本語 |
| タイトル（和） | 並列リコンフィギャラブルプロセッサDAPDNA-2を用いた集合被覆問題の高速解法 |
| サブタイトル（和） | |
| タイトル（英） | Fast solution 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 |
| キーワード(5)（和/英） | NP困難 / NP-hard |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 石川 浩行 / Hiroyuki Ishikawa / イシカワ ヒロユキ |
| 第1著者 所属（和/英） | 慶応義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 清水 翔 / Sho Shimizu / シミズ ショウ |
| 第2著者 所属（和/英） | 慶応義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 荒川 豊 / Yutaka Arakawa / アラカワ ユタカ |
| 第3著者 所属（和/英） | 慶応義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 第4著者 氏名（和/英/ヨミ） | 山中 直明 / Naoaki Yamanaka / ヤマナカ ナオアキ |
| 第4著者 所属（和/英） | 慶応義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 第5著者 氏名（和/英/ヨミ） | 斯波 康祐 / Kosuke Shiba / |
| 第5著者 所属（和/英） | アイピーフレックス株式会社 (略称： アイピーフレックス) IPFlex Inc. (略称： IPFlex) |
| 講演者 | 第1著者 |
| 発表日時 | 2008-01-16 17:25:00 |
| 発表時間 | 25分 |
| 申込先研究会 | RECONF |
| 資料番号 | VLD2007-116, CPSY2007-59, RECONF2007-62 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | no.414(VLD), no.416(CPSY), no.418(RECONF) |
| ページ範囲 | pp.67-72 |
| ページ数 | 6 |
| 発行日 | 2008-01-09 (VLD, CPSY, RECONF) |
[研究会発表申込システムのトップページに戻る]