MapReduce上での並列木累積計算の実装

IPSJ

Bibliographic Information

Other Title
  • Parallel Tree Accumulations on MapReduce

Search this article

Abstract

大規模分散処理のためのプログラミングモデルかつ処理系であるMapReduceについて多くの研究がある．MapReduceはクラウド環境において広く利用されており，MapReduceを用いたプログラム開発法を発展させることは非常に重要である．XMLは，半構造化データを表現するデファクトスタンダードであり，多くのアプリケーションに利用されている．本発表では，XMLのような木構造を持つデータに対する木累積計算をMapReduce上で実現することを目的とする．木累積計算は，木の形状を保持しながら各ノードの値を更新する計算であり，そのノードの値は木上のデータフローによって求められる．本発表では，筧らによって提案された並列木縮約アルゴリズムを拡張し，2種類の並列木累積計算を行うBSPアルゴリズムを設計する．また，2つのスーパーステップからなるBSPアルゴリズムに，1度のMapReduceの実行によって実現する．16台のPCクラスタを用いて行った評価実験では，10.9倍から12.7倍の速度上昇が見られた．

MapReduce is a remarkable parallel programming model as well as a parallel processing infrastructure for large-scale data processing. Since it is now widely available on cloud environments, developing methodology or patterns for MapReduce programming is important. In particular, XML is the de facto standard for representing data, and processing semi-structured data is involved in many applications. The target computational patterns in this paper are tree accumulations. Tree accumulations are shape-preserving computations over a tree in which values are updated through flows over the tree. We develop BSP algorithms for two tree accumulations as extensions of the BSP algorithm for tree reduction by Kakehi et al. (2006). We also implemented the two-superstep algorithms with a single MapReduce execution. Experimental results on a 16-node PC cluster show good speedups of a factor of 10.9-12.7.

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top