日本ソフトウェア科学会第 33 回大会 (2016 年度) 講演論文集

データ依存を持つ繰り返し計算アルゴリズムからのHadoop MapReduce プログラムの生成
宮崎 玲奈

松崎 公紀

スケルトン並列プログラミングは，並列処理において頻出する計算パターン (並列スケルトン) を組み合わせて並列プログラムを行う手法である．しかし，実際には，逐次に動作するアルゴリズムが与えらえたときに，そのアルゴリ
ズムから並列プログラムを生成することは，並列スケルトンの選択や組合せの観点から難しい．この問題に対して，
Hu らの研究では，ある条件に従って書かれたリスト構造に対するプログラムを，map/reduce/scan と呼ばれる並列スケルトンを組み合わせたプログラムに変換する手法を示した．本研究では，データ依存を持ち繰り返し計算を行うような逐次プログラムから，先行研究の変換手法を用いて並列スケルトンの組を生成する．さらに，Hadoop
MapReduce 上で動作する並列プログラムを生成する手法を提示する．その上で，自動生成によって得られた並列プ
ログラムの性能について評価を行う.

リスト構造に対するプログラムがある条件を満たす

1 はじめに場合，map，reduce，scan と呼ばれる 3 つの並列ス

並列プログラムは，複数の計算ノード上で並列にケルトンの組み合わせに変換できることを示した [6]．

処理が実行されるため，単一計算ノード上で動作す

本研究では，始めに，Hu らが示した変換手法を用る逐次プログラムと比較して実装が難しい．これは，いて，ある条件を満たす逐次の繰り返し計算アルゴ

並列プログラムを作成する過程で，逐次で実装可能なリズムから並列アルゴリズムを生成する．得られた処理が並列に動作できるかどうか，並列化可能な場合

並列アルゴリズムから，実際の並列処理基盤であるの処理手順，中間データの処理などを考える必要があHadoop MapReduce [1] 上で動作するプログラムをるからである．この並列プログラミングの手法の一つ

生成する．

としてスケルトン並列プログラミング [4] [10] がある．

本研究で対象とする並列処理基盤である Hadoop

スケルトン並列プログラミングでは，並列分散処理に

MapReduce には，性能に影響する多くの追加機能

おいて頻出する計算パターンを抽象化したもの（並や実行時パラメータが存在する．このため，性能の列スケルトン）を選択し組み合わせて，並列プログラ

高い並列プログラムを実装することは難しい．これムを作成する．しかし，実際のプログラミングにおいに対し先行研究 [11] では，Hu らの変換で得られる並て，最適なプログラムを構築するための並列スケルト

列アルゴリズムに対する Hadoop MapReduce 上でンの選択は難しい．Hu らはこのような問題に対し，の効率的な実装方法を示した．この結果をもとに本研究では，性能の高い実装手法をテンプレート化し，Generating MapReduce Programs from Algorithms
Including Repeated Computations and Having Data
Dependency.
Reina Miyazaki, 高知工科大学大学院工学研究科, Information Systems Engineering Course, Kochi University of Technology.
Kiminori Matsuzaki, 高知工科大学情報学群, School ofInformation, Kochi University of Technology.

Hadoop MapReduce プログラムを自動生成する．

2 並列プログラムへの変換手法：Diﬀusion
Hu らが提案したプログラミング変換手法 diﬀusion[6] は，ある条件を満たすリスト構造に対する処理に対して，BMF (Bird-Merteens formalism) [2] の重要な並列スケルトンである map，reduce，scan を組

上記のプログラムが与えられた場合，並列分散処理上み合わせたプログラムを導くものである．本章では始での計算では，はじめに後方のリストに影響する累積

めに，3 つの並列スケルトンの概要を示し，次に変換計算を行う．累積計算のリスト cs は以下の式で導か方法を示す．本節では，プログラムおよび定式の表記れる.

cs = (c⊗) ∗ (⊗ // (g2 ∗ x))法として，Haskell [3] を利用する．

cs および reduce，map，scan を用いて，前述した逐
2. 1 並列スケルトン map，reduce，scan の次プログラムは以下の形に変換される．

h x c = let cs′ ++[c′ ] = (c⊗) ∗ (⊗ // (g2 ∗ x))

処理

ac = zip x cs′

並列スケルトン map は，リストの各要素に対して任意の関数 k を適用する処理である．map の数式記
号を ∗ とすると，以下の式で示される.

k ∗ [x1 , x2 , ..., xn ] = [k x1 , k x2 , . . . , k xn ](⊕/(k ∗ ac)) ⊕ (g1 c′ )inDiﬀusion 変換では，入力プログラムが上述した条(1)

並列スケルトン reduce は，リストの全ての要素を件を満たすことが必要である．そのため，実際の変換は以下の 4 つのステップにより行われる．

結合し，単一の要素に変換する処理である．結合演算

1. 再帰呼び出しの線形化

子を ⊕，reduce の数式記号を / とすると，以下の式

2. オペレータ ⊕，⊗ の識別で示される.

3. diﬀusion 変換の適用⊕/[x1 , x2 , . . . , xn ] = x1 ⊕ x2 ⊕ · · · ⊕ xn

(2)

4. オペレータ ⊕，⊗ の最適化

並列スケルトン scan は，reduce の計算結果に関し

以下では，先行研究においても取り上げられているて累積計算を行う処理である．計算に使用する結合演

括弧マッチング問題に対する変換の過程を示す．この算子を ⊕，その単位元を ι⊕ ，scan の数式記号を // と問題では，与えられた数式に対して，括弧 ( およびすると，以下の式で示される．

) の対応が正しく記述されているかを判定する．例え⊕ //[x1 , x2 , . . . , xn ]ば， ((1+2+1)+10) は正しく，((1+2)+1+(3+2 は正= [ι⊕ , x1 , x1 ⊕ x2 , . . . , x1 ⊕ x2 ⊕ · · · ⊕ xn ] (3)
本論文で使用する scan では，単位元を第 1 要素とするため，入力リストの要素数に対してその scan の結果は 1 つ要素が増加する.

しくない．
括弧マッチング問題を解く逐次プログラム bm は，次の式で表せる [6]．

bm [ ] s=c == 0bm (a : x) s=

if a == “(′′ then bm x (s + 1)
else if a == “)′′ then

2. 2 変換方法
Hu らが示した変換は，入力として与えられる関数

s>0∧ bm x (s − 1)

定義の形に応じて 3 種類存在する．最も単純な reduceのみを使うもの，reduce と map を組み合わせるもelse bm x sの，reduce，map，scan を全て使用するものに分け

1 つ目のステップとして，上記プログラムの再帰呼られる．本研究では，reduce，map，scan を全て使

び出しを線形化する．上記プログラムでは，if 文の用するものを対象とする．以下に変換の概略を示す．

分岐に合わせて複数箇所に再帰呼び出しが存在する．

リスト構造に対する逐次処理のプログラムが以下

この再帰呼び出しの引数および if 文の条件を関数にで表される場合，reduce，map，scan を用いた並列よって導出し，プログラム内で単一の再帰呼び出しにプログラムへ変換できる．

変換する．以下に結果を示す．

h:[I ]→

A

→O

h[]c

=

g1 c

h (a : x) c=k(a, c) ⊕ h x (x ⊗ g2 a)bm [ ] s=

g1 sbm(a : x)s=k(a, s) ∧ bm x(s + g2 a)

where

g1 s
k(a, s)

g2 a

=
=

=

s == 0た場合，ss = [0, 1, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 1, 0]′′

if a == “( then T rueとなる．つまり，開き括弧が読み込まれた際に値を加else if a == “)′′ then s > 0

算して次の要素に結果を渡し，閉じ括弧が読み込ま

else T rue

れた際には値を減算して次の要素へ結果を渡す．ss′′

if a == “( then 1′′

else if a == “) then (−1)else 0

計算後の map 処理では，リストの要素が閉じ括弧の場合，対応する箇所の scan の結果が 1 以上の場合に2 つ目のステップとして，複数ノード上で同時に展

True を返す処理を行う．reduce は，この map が適開される scan や reduce の結果を結合するためのオ用されたあとのリストの各要素を論理積で結合する．

ペレータ ⊕ および ⊗ およびを識別する．今回の例と閉じ括弧が読まれた場合に，手前の残りの開き括弧

して挙げているプログラム (bm) では，入力プログラの数が 1 未満の場合，あるいは最後のリスト要素をムの条件と出力プログラムの条件を比較することで，呼んだ際に残りの開き括弧の数が 0 以外の場合には

2 つのオペレータは容易に導出される．reduce 計算

False が出力されるため，括弧のマッチングは正しくの結合オペレータ ⊕ は ∧，scan 計算の結合オペレー

ないことが導かれる．

タ ⊗ は + となる．Hu らの研究では，結合演算子 ⊗本研究では，入力として受けとる逐次のプログラが上記プログラム中の (s ⊗ g2 a) のように明示されてムとして，Diﬀusion の入力プログラムの条件を基いない場合の変換にも対応している．これは，上記のとして記法や一部条件を縮小したものを想定しておプログラムにおいて (s + g2 a) が g2 a s のようにオペり，プログラム生成の中間出力として Diﬀusion 後のレータが関数化し示されている場合である．本研究でプログラムのように scan 処理を先に行うものを得は，このようなプログラムの変換は対応せず，一般的る．この条件や処理については第 6 章で記述する．

な二項演算子での scan 計算および reduce 計算を結

そして，第 4 章および第 5 章で示す手法を用いて合するようなプログラムを変換対象としている．

Hadoop MapReduce 上で動作する並列プログラムを

3 つ目のステップは，この節の最初で示した diﬀu-

生成する．

sion の変換を適用する．上記のプログラムは diﬀusionの入力プログラム条件を満たす．このため，map，re-3 Hadoop MapReduce

duce，scan を組み合わせた並列プログラムに変換でMapReduce [5] は Google によって提案された並きる．変換後のプログラムを以下に示す．
′′

h x s = let ss ++[s ] = (s+) ∗ (+ // (g2 ∗ x))
ac = zip x ss
in′(∧/(k ∗ ac)) ∧ (g1 s′ )列分散処理のためのプログラミングモデルである.

MapReduce では，処理を Map と Reduce と呼ばれる二つのフェーズに分けて行うという特徴がある. モ
デルの概念図を図 1 に示す.

以上のステップにより，逐次プログラムから並列プ

MapReduce では，はじめにユーザから与えられログラムを算出する．Hu らの研究では，4 つ目のス

た入力ファイルを複数のスプリットに分割する. そテップとしてオペレータの最適化を行っている．本研

れぞれのスプリットに対して Map フェーズを実行す

究では，オペレータとして一般的な二項演算子を使用る. この Map フェーズおよび後に行われる Reduce

するため，今回はオペレータの最適化を自動生成のス

フェーズはユーザにより任意の処理が指定できる.

テップには組み込まない．

Map フェーズでは，スプリットに対して処理を行い，括弧のマッチング問題 (bm) のプログラムは，scan

key と value のペアからなる中間結果を出力する. 全計算の結果である ss として，各リスト要素の手前までての Map フェーズの出力に対して，key でグルーピに対応する閉じ括弧のない開き括弧の個数を累積したングおよびソートを行う. そして各 key ごとにあるものをもつ．((1+2)+3+1+(1+4)) を示すリスト x =いは各グループごとに Reduce フェーズを実行する.

[(, (, 1, +, 2, ), +, 3, +, 1, +, (, 1, +, 4, ), )] が与えられ

この Reduce フェーズの出力を最終的な結果として出力する. Map フェーズおよび Reduce フェーズで行°Šc/2yEqQcy&KŠV
c5ŠH

われる各タスクは独立しており，MPI 等と異なり各フェーズ中に他のタスクと通信を行うことはできな

map

split1

い. このためプログラムの構造は単純であるが，制約のあるモデルとなっている.

reduceresult1

reduceresult2map

split2

Hadoop MapReduce [1] は，前述した MapReduce
モデルを採用した並列分散処理のためのフレームワー

Šc/2y

map

split3クである．多くのカスタム機能や実行時パラメータがMapc5ŠH

存在するため，多様なプログラムが記述できるという特徴がある [1]．

図1Reducec5ŠH

MapReduce の概念図

カスタム機能には，入力のスプリットに対する処理を指定する FileInputFormat クラス，key のグルー研究では，先行研究で得られた効率的な実装をもとにピングやソート処理に関するセカンダリソート機能なし，自動変換によって出力する Hadoop MapReduce

どがある．また，Writable クラスを拡張したクラスプログラムをテンプレート化し実装する．

を用意することで，配列などのデータ集合を Map とReduce 間で転送することもできる．特に，先行研究
では，Map/Reduce タスク間や MapReduce のジョブ間で多くのデータセット (リスト構造など) を転送する場合，Writable クラスを拡張し，データをまとめて送ることで性能が向上するという結果が得られ4 並列プログラムの Hadoop MapReduce
での実装
本章では，2 章で示した Diﬀusion 変換の結果として得られるスケルトン並列プログラム

h x s = let ss′ ++[s′ ] = (s+) ∗ (+ // (g2 ∗ x))
ac = zip x ss′ている．
実行時パラメータには，各 Map/Reduce タスクのin(∧/(k ∗ ac)) ∧ (g1 s′ )起動数やプログラムのメモリ上限，Reduce フェーズの起動条件，仮想メモリのサイズなどがある †1 ．先を実際に Hadoop MapReduce 上で実装する方法に行研究では，Reduce タスクを実行する Reducer の起

ss は，リスト x 上の scan 計算の結果のリストであ動条件 (Map タスクがある段階まで終わった際に起る．累積計算であるため，後方のリストの要素は前動させることを指示するパラメータ) や Reducer の方のリストの要素の情報を必要とする．scan を並列

起動数の制限などで性能向上が得られている．

に計算するためのアルゴリズムとして，分散メモリ

ついて示す．

以上のように，Hadoop MapReduce では性能の高環境において広く利用されるアルゴリズム scanDist

いプログラムを記述するためには，カスタム機能を実と，BSP モデル [7] において利用される scanBSP が装し，パラメータを適切に指定することが重要となる．

ある．本研究では，先行研究でより高い性能を示しこれに対し，先行研究ではより性能の高い Hadoop

た scanBSP を用いて scan を実装する並列プログラ

MapReduce プログラムを実装する手法を示した．本

ムを生成する．このため，以降は scanBSP の実装に

†1 数百種類になる多様なパラメータの存在の要因の一
つには Hadoop MapReduce の開発の歴史にある．
Hadoop MapReduce の最新のバージョンは，2.7.xである．Hadoop MapReduce は，1.x.x 系から 2.x.x系に変わる際に，内部の一部処理やタスク起動におけるシステムの名称が大きく変更されている．特に，2.x.x 系では下位バージョンを互換するため，非常に多くのパラメータが存在しており，システムの実行や性能に与える影響が大きいものも多く存在する.

ついてのみ記述している．実装例として使用するリス
トは，[(, (, 1, +, 2, ), +, 3, +, 1, +, (, 1, +, 4, ), )] とし，
それが 3 つの部分リストに分けられたネストしたリストであるとする．

[ [( , ( , 1 , + , 2],
local
map/reduce[( , 1 , + , 4 , ) , )] ][) , + , 3 , + , 1 , + ],map ( C6 )map ( C6 )map ( C6 )[ [ 1 , 1 , 0 , 0 , 0 ] , [ -1 , 0 , 0 , 0 , 0 , 0 ] , [ 1 , 0 , 0 , 0 , -1 , -1 ] ]reduce ( E )reduce ( E )[ [2],[ -1 ] ,[ -1] ]

[ [],

[2],

[ 2 , -1 ] ]reduce ( E )reduce ( E )global scan

reduce ( E )[ 0,

reduce ( E )

2 ,

1

]

[ [ 1 , 1 , 0 , 0 , 0 ] , [ -1 , 0 , 0 , 0 , 0 , 0 ] , [ 1 , 0 , 0 , 0 , -1 , -1 ] ]scan E rscan E tscan E s[ [0,1,2,2,2,2 ],[ 2,1,1,1,1,1,1],[ 1,2,2,2,2,1,0] ]local scan

result[ 0,1,2,2,2,
図2

2,1,1,1,1,1,

1,2,2,2,2,1,0]

scanBSP のアルゴリズム

local zip/map/reduce
input[ [( , ( , 1 , + , 2],[) , + , 3 , + , 1 , + ],[( , 1 , + , 4 , ) , )] ]scan

[ [0,1,2,2,2,2 ],[ 2,1,1,1,1,1,1],[ 1,2,2,2,2,1,0] ]
zip

zip

zip

[[(, 1], [1, 2], [+, 2], [4, 2], [), 2], [), 1]]][[( , 0], [( , 1], [1 , 2], [+ , 2], [2, 2]][[ * , 0]]][[(, 2], [+, 1], [3, 1], [+, 1], [1, 1], [+, 1]]?OþŽ•[ò?"map ( G )map ( G )[ [T,T,T,T,T ],[ T,T,T,T,T,T],

reduce ( è )map ( G )[ T , T , T , T , T , T ], [ T ] ]reduce ( è )

[ T,

T ,

reduce ( è )T]reduce ( è )global reduce

[ T]
図3

map/reduce のアルゴリズム

4. 1 scan 並列アルゴリズム：scanBSP

scanBSP では，1st superstep において，各入力ス

BSP (Bulk Synchronous Parallel) モデルは，su-

プリットごとに map/reduce を行い単一の要素を計算

perstep と呼ばれるほかプロセスと独立に行う計算をし，後方の入力スプリットを処理するタスクに結果を単位として計算を進めるモデルである．BSP モデル

転送する．この値は，各スプリットごとに scan 計算

において，2 つの superstep で計算を行うアルゴリズを行った場合の末尾要素にあたる．転送後，superstep

ムが scanBSP である．括弧のマッチング問題におけ間で同期をとり，2nd superstep の処理にうつる．2nd

る処理の過程を図 2 に示す．

superstep では，前方のリストまでの scan の累積値

を用いて手前のリストまでのグローバル scan を行う．

法について示している．本研究では，より性能の高い

そして，その結果を用いて，各スプリットに対して結果を示した手法を一つ選択し，自動生成により得ローカル scan を行う．最終的に，各スプリットの結るプログラムの対象とする．選択した実装において，果を結合することで結果を得る．

各フェーズで行う処理を以下に示す.

1 段目 Map local map/reduce (図 2)
4. 2 scan 後の map，reduce(関数 h) の実装
第 4.1 節および第 4.2 節の手法によって得られる

1 段目 Reduce global scan，local scan (図 2)，
local zip/map/reduce (図 3)scan 結果 ss を得た後に，map，reduce を実行し最2 段目 Map デフォルト (処理が行われない)

終的な結果を得る．括弧のマッチング問題における2 段目 Reduce global reduce (図 3)

map，reduce の実装のアルゴリズムを図 3 に示す．

中間データ表現 新しい Writable クラスを実装し括弧のマッチング問題では第 3.2 節で示したように，

scan においてリストの各要素に対応する位置までに残る開き括弧の個数を計算し，その後の map/reduce

データセットを転送する
実行条件 Reducer の起動数を制限し，global re-duce の出力ファイル数を削減するの組合せによって，入力リストの要素と括弧の個数

この手法では，2 段目の Map フェーズでは処理を行を比較し，適正な式であるか判定する．このため，わないこと，2 段目の Reduce フェーズで行われる処

map，reduce を行う際には，入力のリスト x と括弧

理が非常に高速であることが問題にある．2 段目のの個数を示すリスト ss が必要となる．図 3 に示すよ

Reduce フェーズでは，各スプリットに対する reduce

うに，はじめに入力のリストと scan の結果を zip す処理が行われた結果を結合する処理であるため，スる．このとき，最後の分割リストの scan 計算の末尾

プリットの個数程度のデータの入力を受けとる．図 3′

要素 “0” が第 4.2 節のプログラム中の s にあたるたの場合，local zip/map/reduce の処理で得られる最め保持する．この各要素に対して map および reduce

後のデータ [T, T, T ] のみが 2 段目の Reduce フェーを行い，単一の要素を得る．例えば入力リストの値がズの入力である．つまり，reduce 処理を行うという「）」であり，その位置までの scan 計算の結果が閉じ前提のもと，global reduce の処理は逐次で行うこと

括弧が開き括弧の個数よりも 2 つ少ないことを示す

で高速な実装が可能となる．

−2 であった場合，reduce の結果は False となる．

以 上 よ り，本 研 究 で は ，scanBSP を 採 用 し た

以上の手法により，Diﬀusion 後に得られた並列プ

Hadoop MapReduce 上のプログラムを自動生成すログラムを MapReduce モデル上で実装することがるプログラムの対象とする．先行研究で得られた知見できる．

をもとに，より高速なプログラムを得るため，図 3 内にある global reduce の処理は Hadoop MapReduce

4. 3 Hadoop MapReduce 上での実装手法

上ではなく逐次プログラムとして実装する．

MapReduce モデルにおける scan，map，reduceの並列アルゴリズムを Hadoop MapReduce に実装する方法は，先行研究により示されている．手法の概略を以下に示す．

5 逐次プログラムから Hadoop MapReduce プログラムへの変換
本章では，繰り返し構造をもつ逐次プログラムから

scanBSP による scan の処理は，1 段の MapReduce

Hadoop MapReduce 上で動作する並列プログラムをにより実装する．また，scan 後の map，reduce によ

生成する手法を示す．本研究で提案する手法は，大きる計算は 1 段の MapReduce により実装する．このく分けて以下の 3 つのステップにより構成される．

ため，先行研究では，scanBSP に基づく diﬀusion 変

1. 入力プログラムの解析

換後のプログラムは 2 段の MapReduce により実装

2. Diﬀusion によるプログラム変換している．また，性能比較のために 3 種類の実装手

3. Hadoop MapReduce への適用

入力プログラムは 3 章で示した Diﬀusion が入力とし2 章で Diﬀusion の変換対象として取り上げた上記プてとるプログラム条件をもとに定める．Diﬀusion に

ログラムを，本研究の入力プログラムの条件によってよるプログラム変換では，2 章で示した手法を中心と記述した例を以下に示す．

して変換を行う．最後に，得られた並列プログラムを5 章で概略を示した Hadoop MapReduce プログラム
へと変換する．

5. 1 入力プログラムの条件
本研究で変換対象とする入力プログラムの条件を以下に示す．

1. Java 言語の構文規則に従って記述されたもの
2. リスト構造 (Java の配列で表記する) の入力に対して先頭から順に処理するもの(a) 先頭から順に読み込み処理するプログラ
ムは，main 関数内の for 文中に記述する(b) 配列の入力変数は，main 関数内に宣言する(c) 計算過程で使用する関数は，main 関数と同じ階層に記述する(d) 前方要素からの累積により得られた最後の値に対する処理がある場合，for 文の後に

0: main() {1:// 変数宣言: 条件 2-(b)2:char[] xs; // 入力配列
3:
int s = 0; // 累積値
4:boolean res = true; // 最終結果
5:
6:// 入力配列に対する処理を記述: 条件 2-(a)7:for (int i = 0; i < xs.length; i++) {8:
if (xs[i] == ’(’) {9:s = s + 1; // 条件 3，4
10:} else if (xs[i] == ’)’) {11:
if (s < 0) {12:// 条件 3，4
13:
res = res && false;
14:
}
15:
s = s - 1; // 条件 3，4
16:
}
17:
}
18:
19:
// 空配列 (または末尾要素) の処理
20:// 条件 2-(d)21:if (s != 0) {22:
res = res && false; // 条件 3，4
23:
}
24: }

記述する

3. 配列の前方要素から結果を累積させる変数や最上記プログラムでは，入力配列 xs の要素を for 文

終出力となる変数の更新には，Java 言語で一般

によって先頭から順に参照し，処理する．for 文内で的に使用できる二項演算子を使用するものに限累積される変数値は s および res である．また，累定する積された s の値によって res の値が定まる．このた

4. 配列の前方要素から結果を累積させる場合は，

め，diﬀusion の変換課程から，scan にあたるものはその累積値の更新の際に前方までの結果に対し

s の計算，reduce にあたるものは res の計算となる．

て加算や減算などの処理を行う (入力可能な例:

また，s の最終累積値に対する処理を for 文の後に記

s = s + 1，入力不可能な例：s = t)

述し，res の最終的な結果を計算している．(括弧の以下に 2 章で取り上げた括弧のマッチング問題のマッチング問題では，この計算が読み込んだ括弧の総プログラムを例にあげ，本研究で対象とする入力プロ

数が最後の要素の処理後に 0 となっていることを調グラムの例を示す．

べることと等しい)bm [ ] s=c == 0bm (a : x) s=

if a == “(′′ then bm x (s + 1)′′

else if a == “) thens>0
∧ bm x (s − 1)else bm x s

5. 2 入力プログラムの解析
5. 2. 1 AST(抽象構文木) の作成
入力プログラムに対して，プログラム変換を行う
ための前処理として AST(抽象構文木) を生成する．

AST とは，プログラムを木構造として表現したものである．例えば，a = b + 1 は図 4 のような木で表

=
a

+
b

図4

0: int a = 0;
1: int b = a + 4;

1

a = b + 1 の AST

この場合，変数 a に関して，命令文 0 で変数 b が定義され，命令文 1 で変数 a が参照される．このとき，データ依存関係は，DD(0, a, 1) となる．
本研究では，入力プログラムから制御依存関係およされる．AST に対して通りがけ順でノードを読み込

びデータ依存関係を導く．また，本研究では，データ

むことで，元のプログラムが得られる．この AST を依存関係においては，多変数間でデータ依存関係が用いて，入力プログラムの解析やプログラム変換をループするものに関しては取り扱わない．

行う．

5. 2. 2 依存関係の解析

5. 3 Diﬀusion の適用

Diﬀusion を行う為には，scan や reduce に当たる

入力プログラムの解析結果をもとに，Diﬀusion を計算を抽出することや，If 文により複数箇所にわかれ用いて並列プログラムへ変換する．6.1 節で示した入た同一変数の計算処理を関数化し単一にする必要が力プログラムに対して Diﬀusion を行った結果を以下ある．この処理には，どの変数がどの命令に依存してに示す．

いるかを抽出する必要がある．このため，入力プログ
ラム中に存在するデータ依存関係および制御依存関係を抽出する．
制御依存関係は，ある命令文 t に関して，その命令文が実行されるかどうかを定める条件文 s が存在している場合，命令文 t は条件 s の判定結果に依存するという関係である [8]．このときの制御依存関係をCD(s, t) と表記する．例えば，以下のプログラムの制
御依存関係を考える．
0: if (a == 0) {1:
b = b * 10;
2: }1 行目の命令文の実行の有無は，0 行目の条件式に依存する．このため，1 行目の命令文に関する制御依
存関係は CD(0, 1) となる．
データ依存関係では，ある変数 w が存在して，命令文 s において変数 w が定義され，変数 w を参照す
る命令文 t に到達する場合に，命令文 t は命令文 s に依存関係があるという [9]．これを，DD(s, w, t) と表記する．例えば，以下のプログラムのデータ依存関係を考える．

00: main() {01:
Char[] xs;
02:
03:// 1. scan 計算
04:s[0] = 0;05:
for (int i = 0; i < xs.length; i++) {06:
s[i + 1] = s[i] + func0(xs[i])07:- func1(xs[i]);
08:
}
09:
10:
// 2. reduce 計算
11:boolean res = true;
12:for (int i = 0; i < xs.length; i++){13:
res = res && func2(xs[i], s[i]);
14:
}
15:
16:
// 3. scan の末尾要素に対する reduce 計算
17:if (s[s.length - 1] != 0){18:
res = res && false;
19:
}
20:
21:
// 4. scan の結合に使用するオペレータ
22:
int scansOp(int val0, int val1){
23:
return val0 + val1;
24:
}
25:
26:
// 5. reduce の結合に使用するオペレータ
27:
boolean reduceresOp(boolean val0,28:
boolean val1){29:
return val0 && val1;
30: }
31:

5. 3. 1 scan/reduce にあたる変数の抽出と繰り
32: // 6. If 文による変数更新の関数化
33:
int func0(char val0){34:
if (val0 == ’(’){
35:
return 1;
36:} else if (val0 == ’)’){
37:
return 0;
38:}
39:
return 0;
40:}
41:
int func1(char val0){42:
if (val0 == ’(’){
43:
return 0;44:} else if (val0 == ’)’){
45:
return 1;
46:}
47:
return 0;
48:}
49:
int func2(char val0,int val1){50:
if (val0 == ’(’){
51:} else if (val0 == ’)’){52:
if (val1 < 0){53:
return false;
54:
}
55:
}
56:
return true;
57:
}
58: }

Diﬀusion 後に得られるプログラムでは，始めに前方リストから累積される値である s の計算を行う．このとき，配列の読み込み位置に合わせて s の値を保存する必要があるため配列に保存している．この計算
が，Diﬀusion における scan にあたる．そして，変数s の値に依存する変数 res の計算を行う．この計算
が，Diﬀusion における reduce にあたる．また，入力
プログラムでは If 文により変化していた変数 s，resの値の更新を行う命令文に関して，If 文による値の場
合分けを関数化することによって単一化する．これにより，各変数の更新命令は各 for 文内において 1 つの式によって表せる．最後に，scan の結果の末尾要素

s[s.length-1] に関して reduce の計算を行う命令を記述する．また，並列プログラムでは，scan/reduceの結果を結合する必要がある．このため，上記プログラムの導出過程において結合に使用するオペレー
タを定め関数化する (scanresOp，scansOp)．以上がDiﬀusion により得られるプログラムの構造である．
以下に，このプログラムを導出するための手順を示す．

返し構造の分割
始めに，diﬀusion における scan/reduce の計算対
象の変数を導く必要がある．入力プログラムの例では，

scan として変数 s の計算を，reduce として変数 resの計算を行う．また，その他の例では scan 対象として複数の変数が存在する場合もある．この scan/reduceの対象となる変数の導出方法および繰り返し構造の分割手法を以下に示す．

scan および reduce の対象となる変数名や，その処理順序は，入力プログラムの繰り返し構造 (for 文) 内に含まれる変数の依存関係を用いて以下のステップから導ける．

1. 繰り返し構造内で更新される変数一覧および命令文を全て取得する (繰り返し構造の条件式は除外)．

2. 各命令文に関する依存関係を抽出する．
3. 取り出した全ての命令文の集合内において，どの命令文にも依存しない命令文の組を抽出する．

4. 3. で抽出した命令文に関してプログラムスライスの手法を用いて繰り返し構造を作成する．

5. 3. で抽出した命令文を元の繰り返し構造から除去し，2. に戻る．全ての命令文が除去された場合は 6. を行う．

6. 最後に抽出された命令文の組が reduce 対象となり，他の命令文が scan 対象となる．抽出順に
命令文は実行される．

7. reduce 計算では，scan により得られる結果の末尾要素に関する計算処理を追加する．

6.1 節の入力プログラムの例を用いて，上記の導出方法を示す．まず，繰り返し構造に含まれる変数更新を行う命令文を取得する．これにより，9 行目および15 行目の変数 s の更新および 13 行目の res の更新に関する命令文が得られる．この 3 つの命令文に関して依存関係を抽出する．このとき，9 行目および 15
行目の変数 s の命令文は，抽出された 13 行目の resの命令文に依存しない．一方で，13 行目の res の命
令文は，11 行目の分岐条件より変数 s の値に依存する．これより，始めに s の値を計算する必要があることがわかる．

次に，s の値をあらかじめ計算する繰り返し構造を

5. 3. 2 繰り返し文内の変数値更新に関する命令文の単一化生成する．これは，プログラムスライスの手法を用いて，s の 9 行目および 15 行目の命令文に関する依2 章で示したように，diﬀusion ではプログラムの存関係を抽出し，必要な条件式を取り出し生成する．

再帰呼び出しを線形化し，中心となる bm 関数内かs の場合，7 行目の for 文，8 行目および 10 行目の If

ら If 文をなくし単一の再帰呼び出しを含むプログラ

文が抽出され，s を計算する新しい繰り返し構造が生ムへと変形する．本研究では，再帰構造ではなく繰り成される．また，残りの res に関する命令文におい返し構造を対象としているため，線形化の対象は，繰

て s の値は繰り返しごとに参照される．このため，sり返し構造内に含まれる変数更新の命令文となる．

の値は配列として入力配列の位置ごとに保存しておく

6.4 節で得られた変数 s の繰り返し構造のプログラ必要がある．したがって，変数 s を配列へ変換する．

ムに注目する．変数 s を更新する命令文は If 文の条

また，初期値として s の更新に使われる演算子+の単件ごとに以下の 2 つが存在する．

位元 0 を指定する．以下に s に関するプログラムス

s[i + 1] = s[i] + 1

ライスの結果を示す．

s[i + 1] = s[i] - 1
この 2 つの式を，単一の式で表現するために If 文を

00: int[] s;
01: s[0] = 0;
02: for (int i = 0; i < xs.length; i++) {03:
if (xs[i] == ’(’) {04:
s[i + 1] = s[i] + 1;
05:
} else if (xs[i] == ’)’) {06:
s[i + 1] = s[i] - 1;
07:
}
08: }

関数化し，If 文の条件によって変化する命令文の位置をその関数の返り値で表す必要がある．このために，始めに上記二つの式の形を揃えることで，If の条件
による式の値の変化を得る．揃えた式の形を以下に示す．

s[i + 1] = s[i] + 1 - 0
s[i + 1] = s[i] + 0 - 1

入力の繰り返し構造から生成の終わった s に関す

この変換は，対象となる複数の命令文の AST から，る命令文 9 行目および 13 行目を除去し，ステップ 2

自己参照位置や演算子の一致を探索することで導に戻る．残る命令文は res に関する 15 行目のもののかれる．一つ目の命令文 s[i + 1] = s[i] + 1 のみであるため，この命令文に対して繰り返し構造を組AST を初期テンプレートとして，二つ目の命令文み替える．res の初期値は s の場合と同様に res のs[i + 1] = s[i] - 1 の AST とマッチングを行う．

更新に使用される演算子&&の単位元 T rue を使用す

このときマッチングの開始位置は自己変数の参照位

る．また，手前の scan の計算により得られた結果の

置 s[i] とする．隣接する演算子のノードを比較し，末尾要素に対する reduce の処理を記述する．結果を演算子が異なる場合は，演算子の優先順位を考慮し以下に示す．

つつテンプレートの AST に追加する．この過程を全

00: boolean res = true;
01: for (int i = 0; i < xs.length; i++) {02:
if (xs[i] == ’(’) {03:} else if (xs[i] == ’)’) {04:
if (s[i] < 0) {05:
res = res && false;
06:
}
07:
}
08: }
09: if (s[s.length - 1] != 0){10:res = res && false;
11: }ての命令文がテンプレートを用いて表されるように行う．テンプレートの演算子および自己参照位置以外の値は演算子の単位元とする．これにより，テンプ
レートとして s[i + 1] = s[i] + 0 - 0 が得られる．これに対して，各命令文とマッチングさせ，単位元の位置を正しい値に書き換える．結果として，上述したような右辺の構造を揃えた式が得られる．
以上の変換により，各命令文において，If 文の条件下で変化する値の位置が分かる．命令文の中で値が異なる位置に関して，元のプログラムの If 文を含む関数を作成し，If 文の判定式ごとに変化する値を返すプに使用される二項演算子のみとしている．したがっ

ログラムへ変換する．以下にその結果を示す．

て，値更新を行う命令文を抽出し，変数更新において自身を参照する箇所に隣接する演算子を取得するこ

00: int[] s;とで導かれる．

01: s[0] = 0;

例えば，s = s + 1 の場合，右辺において自身を

02: for (int i = 0; i < xs.length; i++) {03:

s[i + 1] = s[i] + func0(xs[i])- func1(xs[i]);04: }if (xs[i] == ’(’) {

07:
08:

return 1;} else if (xs[i] == ’)’) {

09:
10:

て，scan/reduce の結果の結合に使用される演算子は+となる．また，s = s - 1 の場合においては，隣接する演算子は-であるが，scan/reduce の結果の結合

05: int func0(char val0) {06:

参照する箇所に隣接する演算子は+となる．したがっreturn 0;}に使用される演算子は+である．/および*の演算子の場合*が使用される．これは，値の累積の過程から示される．
本研究では，このオペレータを実装する関数を生成している．以下に，6.4.1 の s および res のオペレー
タに対応する関数を示す．

11: }12: int func1(char val0) {13:

if (xs[i] == ’(’) {

14:
15:

return 0;} else if (xs[i] == ’)’) {

16:
17:

return 1;
}

18: }

00:
01:
02:
03:
04:
05:
06:
07:
08:
09:
10:

// s の scan 結果の結合に// 使用するオペレータ
int scansOp(int val0, int val1){
return val0 + val1;}// res の reduce 結果の結合に// 使用するオペレータ
boolean reduceresOp(boolean val0,
boolean val1){
return val0 && val1;}

上記の関数 func0 および func1 は元のプログラム
において命令文があった位置に，各命令文で使用されこれまで行った変換であるる値に対応するものを返すものを挿入して作成して

1. scan/reduce にあたる変数の抽出と繰り返し構いる．また，関数の引数の算出は，元のプログラムにおいて If 文の条件式に使用されていた値を受け渡すために追加する．
以上の手法より，繰り返し構造内の同一変数の値更造の分割

2. 繰り返し文内の変数値更新に関する命令文の単一化

3. scan/reduce オペレータの識別

新に関する命令文を単一化することができる．これはの結果を統合し，入力プログラムに対する diﬀusion

前述した通り，diﬀusion における再帰構造の線形化

後のプログラムが得られる．

に類似した操作である．

5. 3. 3 scan/reduce オペレータの識別diﬀusion 後に得られるプログラムは，実際には複5. 4 テンプレートを使用した Hadoop MapReduce プログラムへの変換

数ノード上で並列に動作する．このため，scan や

6.3 節の変換により，入力の逐次プログラムに対す

reduce の結果を結合する演算子を抽出する必要があ

る diﬀusion 後の並列プログラムが得られた．次に，る．本研究では，scan および reduce の計算が行われ得られた並列プログラムから Hadoop MapReduce プ

る変数に関して，その値更新の方法を Java で一般的

ログラムを生成する．

4 章で概要を示したが，先行研究において diﬀusion

CustomWritable.java 入力の配列や中間出力後の並列プログラムを効率的に Hadoop MapReduceである scan の配列を転送する際に使用するカ上で実装する手法は既に示されている．このため，

スタム Writable クラス．(Hadoop MapReduce

本研究では，先行研究により得られた手法をテンプ

では，配列等の構造や，複数種類の型変数をレート化し，diﬀusion 後の並列プログラムを Hadoop

Map/Reduce タスク間および MapReduce ジョ

MapReduce プログラムへ変換する．

ブ間で転送する場合には実装する必要がある．)

5. 4. 1 MapReduce 処理の各タスク構成

GlobalReduce.java MapReduce ジョブにより4 章で示したように，diﬀusion 後の並列プログラム得られた local reduce の結果を逐次処理によっの Hadoop MapReduce 上での実装は，並列プログラて結合するプログラム．入力として MapReduce

ムで実行される scan および map/reduce の処理を以ジョブが出力したファイルが格納されるディレク

下のタスク構成で行う．

トリを受け取り，結果を全て結合する．

Map フェーズ local map/reduce(図 2)

また，上記プログラム内で使用するプログラムとして

Reduce フェーズ global scan，local scan(図 2)，

以下のものがある．

local zip/map/reduce(図 3)

CustomPartitiner.java，

逐次プログラム global reduce (図 3)

CustomGroupingComparator.java，

5. 4. 2 テンプレートへの適用

CustomSortComparator.java，

先行研究で得られた実装手法をテンプレートとし，CustomKeyWritable.java

diﬀusion 後の並列プログラムを Hadoop MapReduce

Hadoop MapReduce のセカンダリソート機能を上で動作するプログラムへ変換する．生成されるプロ実装する．入力配列は Map/Reduce タスク間でグラムは以下の 6 つである．

の配列の分割に関する順序を維持する必要があ

DataFunction.java 入力ファイルを解析し，配列構造に変換するプログラム．現在の実装では，るため，セカンダリソート機能を使用して，配列の各分割を順序を維持して転送する．

入力ファイルは 1 行ごとに配列の 1 要素に値す

SplitFileInputFormat.java，

るデータが入るとしている．

SplitFileRecordReader.java

ScanFunction.java scan および reduce で使用指定されたファイルサイズで入力データを分割する関数を定義するプログラム．このプログ

し，各分割に対して Map タスクを実行するため

ラムは，6.3 節で得られたプログラムをベースに使用する．

に，Hadoop MapReduce 上で使用される変数

全ての Hadoop MapReduce プログラムはテンプ

型 Writable に合わせて各変数型の変換を行ってレート化しているため，容易に得られる．各プログラ

いる．

ムの詳細については付録に記載する．

HadoopMainProg.java Hadoop MapReduce
で実際に実行されるメインプログラム．MapRe-

6 性能評価duce ジョブの生成や，入力ファイルのディレクト

本 研 究 で 示 し た 逐 次 プ ロ グ ラ ム か ら Hadoop

リや出力ファイルのディレクトリの制御を行う．

MapReduce プログラムを自動生成する手法では，

MRSCode.java scan，map，reduce を実現す

中心的な手法として，逐次プログラムから並列プロ

る Mapper および Reducer 関数を実装するプログラムを得る変換である Diﬀusion を採用している．

グラム．タスク構成は 5.4.1 で示したものに従う．

しかし，先行研究である Diﬀusion が対象とする入力

また，MapReduce の Job を作成する関数を実装

プログラムと比較して，本研究で受け付ける入力プ

する．HadoopMainProg.java では，この Job 生

ログラムは条件が縮小されている問題がある．2.2 節

成関数によって作られた Job を実行する．

で取り上げたように Diﬀusion では 4 つのステップにより変換を行う．このうちの 2 つ目および 4 つ目に示していた．本研究では，その変換を自動化するこあたるオペレータの識別と最適化に関して，本研究とを目的として行った．結果として，Diﬀusion が対ではオペレータを一般的な二項演算子に制限してい象とするプログラムの条件よりも条件が縮小された

る．このため，例えば二項演算子の処理 a ⊕ b としが，ある一部分においては自動化を示すことができて，a を二乗したものに b を加えたものを返す演算

た．また，並列プログラムから Hadoop MapReduce2f (a, b) = a + b として定義することはできない．こプログラムの変換では，先行研究で得られた実装手法

れは，今後実装するべき課題となる．

をもとにテンプレート化を行いそれにしたがってプ

本研究で行ったプログラム自動変換では，入力とな

ログラムを生成した．パラメータの指定や，得られるる配列の要素を先頭から順に処理するプログラムであHadoop MapReduce プログラムの最適化等に関してり，かつ，その処理結果を保持する変数は，自分自身は今後実装していく必要がある．

を参照し (a = a + 1) 入力要素の後方に結果を伝達す
るような逐次プログラムを対象としている．この条件

参 考 文 献を満たす場合，Hadoop MapReduce プログラムへの[1] Apache Software Foundation: Hadoop. http://
hadoop.apache.org/ (April 2015)[2] Bird, R.S.: An introduction to the theory of lists,
Proceedings of the NATO Advanced Study Instituteon Logic of Programming and Calculi of Discrete
Design, pp. 5–42, 1987.
[3] Bird, R.: Introduction to Functional Programming using Haskell, Prentice-Hall, 1998.
[4] Cole, M.: Algorithmic Skeletons: Structural Management of Parallel Computation. Research Monographs in Parallel and Distributed Computing, MIT
Press, 1989.
[5] Dean, J., Ghemawat, S.: MapReduce: Simplified
data processing on large clusters, 6th Symposium
on Operating System Design and Implementation(OSDI2004), pp. 137–150, 2004.
[6] Hu, Z., Takeichi, M. and Iwasaki, H.: Diﬀusion: Calculating Eﬃcient Parallel Programs, ACM
SIGPLAN Workshop on Partial Evaluation andsemantics-based Program Manipulation (PEPM’99), pp. 85–94, 1999.
[7] Valiant, L.G.: A bridging model for parallel computation, Communications of the ACM, Vol. 33,
No. 8, pp. 103–111, 1990.
[8] 伊藤 宗平, 萩原 茂樹, 米崎 直樹: プログラム依存グ
ラフの操作的意味, コンピュータソフトウェア, Vol. 26,
No. 3, pp. 109–135, 2009.
[9] 伊藤 宗平, 萩原 茂樹, 米崎 直樹: 中間コードを表す
プログラム依存グラフの操作的意味, 日本ソフトウェ
ア科学会第 23 回大会 (2006 年度) 論文集, pp. 1–12,
2006.
[10] 胡 振江, 岩崎 英哉: スケルトン並列プログラミング,
情報処理, Vol. 46, No. 10, pp. 1158–1162, 2005.
[11] 宮崎 玲奈, 松崎 公紀: Hadoop におけるリスト上の累積計算の実装手法が性能に与える影響についての考察,
情報処理学会論文誌プログラミング (PRO) , Vol. 9,
No. 3, p. 25, 2016.

変換が可能となる．一方で，例えば前方までの累積値をある条件で初期化させたい場合などは a = 0 および a = a + 1 といった処理を分岐内に記述すると考えられる．このとき，a = 0 は自分自身を参照しない．
このような処理が記述されると，scan や reduce の結果を結合するときに，単純に全ての local scan の結果を演算子 ⊕，⊗ で結合する処理だけでは正常な結果が得られない．値が a = 0 などで直接書き換えられた場合には，その入力以前の scan や reduce の結果は不要になるためである．この処理は，対象となる条件分岐を見ることによって対応が可能となるが，本研究ではまだ実装できておらず，今後の課題である．
本研究で得られる Hadoop MapReduce プログラ
ムは，事前に用意したテンプレートに従うため，実行
時パラメータの指定や，Hadoop MapReduce 上でのコード最適化などは行っていない．このため，今後，
パラメータを指定する処理やコードの最適化を行う必要がある．

7 まとめ
本研究では，データ依存を持つ繰り返し計算アルゴ
リズムから Hadoop MapReduce プログラムを生成する手法について検討した．入力プログラムの条件および入力プログラムとなる逐次プログラムから並列プ
ログラムへの変換手法は，先行研究である Diﬀusionの手法を用いた．先行研究では，入力プログラムの変換は自動化されておらずその変換のアイデアを提以下に変換結果を示す．

A Hadoop MapReduce プログラムのテン
プレート

class ScanFunction {ScanFunction(){}A. 1 ScanFunction.java
Diﬀusion 後に得られる並列プログラムを Hadoop
MapReduce 上の map 関数および reduce 関数で使用するために，型変換の命令や関数の属性を追記する．

Diﬀusion 後の並列プログラムは，5.3 節の始めで示したものである．以下にその処理内容を示す．

1. scan を行うそれぞれの for 文の処理を行う関数
を作成する• 関数の引数として，入力となる配列と scanの結果を格納するための配列を宣言する

2. reduce を行うそれぞれの for 文の処理を行う関数を作成する• reduce の結果の格納先はグローバル変数で宣言する• 関数の引数として，入力配列，前処理の scan
結果の配列，手前までのスプリットの global

scan の結果，最後のスプリットがどうかを示す真偽値を宣言する• 入力配列および scan 結果の配列は，変数の型が不明となるため型変換を追加する• 計算に使用する scan の値は，手前のスプリットまでの global scan の結果と自分自身の scan の結果を合わせたものとする (結合には reduce の結合演算子関数を使用する)• 末尾要素に関する reduce 計算がある場合

static void scan(char[] xs, int[] s){s[0] = 0;
for (int i = 0;i < xs.length; i++){s[i + 1] = s[i] + func0(xs[i])- func1(xs[i]);}}static boolean res = true;
static void reduce(Writable[] xs,
Writable[] s,
int scans,boolean isLast){
res = true;for (int i = 0; i < xs.length; i++){char xi = (Text)xs[i]).toString().charAt(0);int oi = ((IntWritable)s[i]).get();int globalScan = scansOp(scans, oi);
res = res && func2(xi, globalScan);}if (isLast){
int slast = ((IntWritable)s[s.length - 1]).get();int globalScan = scansOp(scans,slast);
if (globalScan != 0) {res = res && false;}}}
static int scansOp(int val0,int val1){
return val0 + val1;}

は，関数の最後の処理に追加する

3. 全ての関数を直接実行出来るように static 属性を追加する

reduce における型変換の必要性は，Hadoop MapReduce で転送されるデータの型の仕様によって求められる．Hadoop MapReduce 上で scan 結果や入力配列などのデータセットを転送する場合，ArrayWritable とよばれる型を使用する．これは，転送先では Writableという型の配列として得られる．Writable のサブクラスとして IntWritable や TextWritable などがある．
このサブクラスへ変換し，さらに get メソッドを用いて int 型や String 型の変数が得られる．

static boolean reduceresOp(boolean val0,
boolean val1){
return val0 && val1;}
static int func0(char val0){
if (val0 == ’(’){
return 1;} else if (val0 == ’)’){
return 0;}
return 0;}
static int func1(char val0){5. 自分自身 (Reducer) へ scan 結果および入力配
if (val0 == ’(’){
return 0;} else if (val0 == ’)’){
return 1;}
return 0;}
static boolean func2(char val0,int val1){
if (val0==’(’){} else if (val0==’)’){
if (val1 < 0){return false;}}
return true;}}

列を転送する6. 自分より後方のスプリットへ scan 結果の末尾要素を転送する

A. 2. 2 Reduce タスク
Reduce タ ス ク で は ，global scan お よ び local
map/reduce の計算を行う．入力として渡される型は，Map タスクで出力した型となる．出力するデータ型
は，local map/reduce で結果的に得られる型となる．
括弧のブラケットマッチングの例では，res の型である boolean に対応する BooleanWritable となる．
以下に Reduce タスクの処理ステップを示す．

1. 自身のスプリット番号を取得する
2. 入力配列，scan 結果の配列用の配列，前方スプリットまでの scan 結果用の変数を宣言する

A. 2 MRSCode.java
このプログラムは，Hadoop MapReduce で実行される Map タスクおよび Reduce タスクの動作を実装する．本研究で対象とするプログラムは，Map

3. 前方のスプリットから転送される scan 結果を全て結合する (global scan)

4. 自身のスプリットからデータが転送されてきた
場合は，入力配列と scan 結果の配列を取得する

タスクにおいて local scan を，Reduce タスクにお5. ScanFunction.java を用いて reduce を行う

いて global scan および local map/reduce を行う．

6. reduce により得られた結果を出力する

この scan，map，reduce の計算処理には，上述しA. 2. 3 Job の生成

た ScanFunction.java の関数を使用する．このため，

Hadoop MapReduce で実行される Job を設定す

MRSCode.java の動作はテンプレートで実装される．

る．Job の設定では，実行に使用する Map タスクお

以下に Map タスクおよび Reduce タスクの処理，Job

よび Reduce タスクが記述されたクラス名や，その出生成に関する処理のテンプレート概要を示す．

力の型などを追加する．本研究では，以下の設定を追A. 2. 1 Map タスク
Map タスクでは，scan の計算を行う．入力として加し Job を生成した．

1. Map タスク/Reduce タスクのクラス

渡されるデータの型は InputFormat.java および In-

2. Map タスクおよび Reduce タスクの出力

putRecordReader.java に依存する．出力するデータ

3. セカンダリソート機能

型は，配列構造を転送するために新しい Writable ク• CustomPartitioner.java

ラスを生成する (OutputWritableForMapper.java)．

• CustomGroupingComparator.java

map 関数内では，scan の計算を行う．以下にその処• CustomKeyWritable.java

理ステップを示す．

1. 自身のスプリット番号を取得する

4. 入力ファイル分割サイズ
5. 分割ファイルの Map タスクへの転送方法

2. 入力用配列，scan の結果格納用配列を宣言する• SplitFileInputFormat.java

3. DataFunction.java を用いて入力データを解• SplitFileRecordReader.java)

析する

4. ScanFunction.java を用いて scan を行う

6. Reducer の起動数 (起動ノード数の 2 倍)