並列リコンフィギャラブルプロセッサDAPDNA－2を用いた集合被覆問題の高速解法

摘要

This paper proposes a fast calculation method of the set cover problem, which is implemented on re-configurable 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.%高速広帯域ネットワークの発展を背景に普及した，大容量の映像を配信するためのサービスにおいては，ユーザがオリジナルサーバからのみコンテンツをダウンロードした場合，オリジナルサーバの負荷が大きくなる．一方，オリジナルサーバ以外にもコンテンツを分散させる手法が提案されているが，コンテンツレプリカの最適配置計算は集合被覆問題に帰着され，NP困難である．そのためネットワーク規模が膨大になると，ソフトウェアで処理することは難しい．本研究では，レプリカ配置の全組合せを複数グループに最適分割してパイプライン処理を行う集合被覆問題の高速解法を提案する．IPFlex社が開発した並列リコンフィギャラブルプロセッサDAPDNA－2の評価ボードに実装し，特性評価の結果，動作クロック数が17倍のIntel Pentium 4 と比較して実行時間が40倍以上改善することから，提案方式の有効性を示す．