Hadoop MapReduceの計算モデルの定式化とScan計算への応用

全文

(1)情報処理学会論文誌. プログラミング. Vol.7 No.5 17 (Dec. 2014). 発表概要. Hadoop MapReduce の計算モデルの定式化と Scan 計算への応用松崎公紀1,a) 2014年7月30日発表. Google によって最初に提案された MapReduce は，大規模データ処理の重要なプログラミングモデルである．現在では，Google の MapReduce のオープンソース実装である Hadoop が，幅広いアプリケーションの開発に用いられている．このような状況から，MapReduce の計算モデルを定式化することは重要であり，計算の理解，プログラムの正しさの証明，プログラムの最適化への応用が考えられる．本発表では， MapReduce の計算モデルとして 5 つのモデルをたて，MapReduce の計算の本質をとらえる．さらに，リスト上の scan（接頭辞和）アルゴリズムを提案モデルの上で開発する．最も具体的な計算モデルを用いることで，scan の BSP アルゴリズムを定義することに成功した．. Functional Models of Hadoop MapReduce with Application to Scan Kiminori Matsuzaki1,a) Presented: July 30, 2014. MapReduce, first proposed by Google, is a remarkable programming model for processing very large amounts of data. Hadoop, an open-source Java implementation of Google’s MapReduce, is now widely used for developing a wide-range of applications. Under these situations, functional models for the MapReduce computation play important roles, because we could understand the computation rather easily, prove the correctness of programs, and even optimize them. In this paper, we develop five functional models that capture semantics of Hadoop MapReduce computation. In addition, we develop MapReduce algorithms for the scan computational pattern (prefix sums) on the proposed models. We can successfully define the BSP-based scan algorithm with a newly proposed model of the MapReduce.. 1. a). 高知工科大学情報学群 School of Information, Kochi University of Technology, Kami, Kochi 782–8502, Japan [email protected]. c 2014 Information Processing Society of Japan . 17.

(2)