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

複数の頂点主体グラフ計算フレームワーク向けの中間表現とコード生成器
松崎 公紀

岩崎 英哉

江本 健斗

胡 振江

森畑 明昌

著者らは，大規模グラフ並列処理のための関数型領域特化言語 Fregel を提案し，そのコンパイラを作成している．
その最初の実装では，頂点主体グラフ計算フレームワークのひとつ Giraph 上で動作するプログラムを生成していた．生成されたコードが，Giraph の他 Pregel+など複数の頂点主体グラフ計算フレームワーク上で利用できること
は，領域特化言語の重要な利点である．現在，複数のフレームワークを対象としたコード生成器に向けて，コンパイ
ラの改良を行っている．本論文では，頂点主体グラフ計算に対するフレームワーク中立な中間表現の設計，中間表現へのプログラム変換と中間表現からのコード生成の実装について報告する．

• 多くのアプリケーションに共通して現れる計算

1 はじめに近年，グラフやネットワーク構造を持つ大規模デー
タ (以後「大規模グラフデータ」と呼ぶ) を処理対象

構造の簡潔な記述を可能とすること．

• 近年のグラフデータの巨大化に対応し，効率の良い並列処理を可能とすること．

とし，これらのデータから新しい知識を獲得する需要

グラフデータは，実世界の多くの場面で自然に現れが増している．典型的な大規模グラフデータの例としるため，これらの課題を解決することは極めて重要でては，ソーシャルネットワーク，文献参照関係等の書ある．

誌情報ネットワーク，生命システムの情報ネットワー

我々は，大規模グラフデータに対するスケーラブル

クなどがあげられる．このようなアプリケーションのな分散並列処理のためのモデルとして，Google によ開発支援に共通する一般的な課題は，次のような点でる Pregel [5] に注目している．Pregel の大きな特徴ある．

は，バルク同期並列 [7] に基づく頂点主体の計算モデ
ルを採用している点である．このモデルでは，グラフ

Kiminori Matsuzaki, 高知工科大学, Kochi Universityof Technology.
Hideya Iwasaki, 電 気 通 信 大 学, The University ofElectro-Communications.
Kento Emoto, 九 州 工 業 大 学, Kyushu Institute ofTechnology.
Zhenjiang Hu, 国立情報学研究所, National Institute ofInformatics.
Akimasa Morihata, 東京大学, The University of Tokyo.
∗

Intermediate Representation and Code Generator
for Frameworks for Vertex-centric Graph Computation
This is an unrefereed paper. Copyrights belong to the
Authors.

内の頂点はクラスタ中の計算ノードに分散され，各頂点は必要に応じて互いにメッセージを交換しながら，
スーパーステップ (superstep) と呼ばれる一単位の処理を繰り返し実行する．ひとつのスーパーステップにおいては，各頂点は (共通の) ユーザ定義関数を (並列に) 呼び出す．このユーザ定義関数は，スーパース
テップにおける頂点の振舞いを記述しており，典型的には，ひとつ前のスーパーステップにおいて自分に送られたメッセージを受信する，計算を行いその結果に基づいて当該頂点の状態を変更する，別頂点にメッセージを送信する (このメッセージは次のスーパース
テップにおいて送信先頂点が受け取る)，各頂点の持つ情報をグラフ全体で集約 (aggregate) して大域的なこれらの問題を解決するため，我々は頂点主体のグ情報を得る，などの動作を行う．計算の実行過程におラフ処理を記述するための関数型領域特化言語 Fregel

いて，各頂点は実行状態か停止状態のいずれかをとる．

[3] [9] を提案，実装している．Fregel は，関数型言語

スーパーステップにおいて共通のユーザ定義関数を

Haskell のサブセットとなっており，頂点主体の計算呼ぶのは，実行状態の頂点だけ (したがって集約に参を行うプログラムの宣言的な記述を可能としている．

加するのも実行状態の頂点だけ) である．実行状態のFregel を用いることにより，プログラマは上で述べ頂点が停止状態に移行するためには，voteToHalt()

たようなプログラミングの煩雑さから解放されるこ関数を明示的に呼ぶ必要がある．停止状態の頂点に対とが期待されている．

してメッセージが送られると，次のスーパーステップ

Fregel のコンパイラは，Fregel プログラムから，既においてその頂点は実行状態となり，メッセージを受存の頂点主体分散並列グラフ処理フレームワークのプ

け取り計算を行う．あるスーパーステップにおいて，ログラムへの翻訳系である．Fregel を提案した時点

全頂点が停止状態になりかつ送信されたメッセージがでは，Pregel のオープンソース実装のひとつである

なければ，全体の計算が終了する．

Giraph [1] 上で動作するプログラムを生成できるだ

頂点主体のバルク同期並列に基づく Pregel は，プけであった．現在，Giraph 以外にも Pregel+ [8] な

ログラマはデータフローや同期のことを考える必要

ど複数のフレームワークを対象としたコード生成器にがないという意味で自然なプログラミングモデルを向けて，コンパイラの改良を行っている．この改良で提供する．しかし，実際にスーパーステップに基づくは，複数のフレームワークへの翻訳をモジュラに行う

プログラミングを行おうとすると，以下のような煩雑ことを可能とするため，ユーザが記述した Fregel プ

さに直面することとなる [3] [9] [2]．

ログラムを正規化したあと，フレームワーク独立な中• 明示的な副作用に依存したプログラミング：グ

間表現にいったん変換する．この共通の中間表現を経

ラフ上の計算は，各頂点の持つ値の局所的な更新

由することで，各フレームワーク向けのプログラム生や，他頂点への明示的なデータ送信によって行わ成をより容易に行うことを狙う．

れる．そのため，ユーザ定義関数を越えた副作用

本稿では，頂点主体グラフ計算に対するフレームに依存したプログラミングを行う必要がある．

ワーク独立な中間表現 FregelIR (Fregel Intermediate• 明示的な状態制御：頂点間のメッセージ送受信

Representations) の設計，および，Fregel プログラ

では，ひとつ前のスーパーステップで送信されムから中間表現への変換と中間表現からのコード生た値が次のスーパーステップで受信される．大成の実装について報告する．

域的な情報を得るための集約でも，集約された値は次のスーパーステップでしか利用できない．

2 Fregel

そのため，メッセージ送受信や集約の前後で計

2. 1 概要

算処理を分断し，（ひとつの）ユーザ定義関数のFregel [3] [9] では，頂点主体の計算を「グラフ高階

中で計算処理の遷移を明示的に扱う必要がある．
分断された計算処理が増えて複雑になるほど，各関数」と呼ばれる高階関数群を用いて記述する．代表的なグラフ高階関数は関数 fregel であり †1 ，次の時点において送受信されるメッセージの意味やプ形をしている．

ログラムの流れを把握することが難しくなる．

fregel init step term graph• 明示的な計算停止制御：プログラムを停止す

ここで init は各頂点における初期化関数，step は各

るには，すべての頂点を停止状態にする必要が頂点における (論理的な) 反復処理 1 回分を記述するある．その際，頂点を停止状態へと移行させる

関数，term は計算の終了条件，graph は処理対象のvoteToHalt() は，計算の順番を正しく把握して適切な場所に挿入する必要がある．

†1 グラフ高階関数には他に gmap，gzip，giter がある．

1 data SVal = SVal { dist :: Int }2
deriving (Eq, Show)
3 sssp g =4
let init v =5SVal (if vid v == 1 then 0 else 999)
6
step v prev curr =7
let newdist =8prev v .^ dist ‘min‘
9minimum [ prev u .^ dist + e |10(e, u) <- is v ]11
in SVal newdist
12
in fregel init step Fix g
図1

単一始点最短路問題のための Fregel プログラム

グラフである．step は，頂点自身と他の頂点の 1 回前の計算結果をもとに計算を行い，新しい頂点の値を返すものである．このような step の内容を「論理スーパーステップ (logical superstep，以下 LSS)」 と呼ぶ †2 ．LSS の処理の中には，隣接頂点の値を参照す

1 data SVal = SVal { dist :: Int }2
deriving (Eq, Show)
3 data MVal = MVal { mval :: Int }4
deriving (Eq, Show)
5 ssspmaxv g =6
let ssspinit v =7
SVal (if vid v == 1 then 0 else 999)
8
ssspstep v prev curr =9
let newdist =10
prev v .^ dist ‘min‘
11
minimum [ prev u .^ dist + e |12(e, u) <- is v ]13
in SVal newdist
14maxvinit v = MVal (val v .^ dist)15
maxvstep v prev curr =16
let newmval =17
prev v .^ mval ‘max‘
18
maximum [ prev u .^ mval |19(e, u) <- is v ]20
in MVal newmval
21
g1 = fregel ssspinit ssspstep Fix g
22
g2 = fregel maxvinit maxvstep Fix g1
23
in g2
図2

グラフの直径を求める Fregel プログラム

ることや，集約処理を用いて大域的な情報を得ることがあるかもしれない．そのようなときには，LSS 1
回分は，Pregel における複数のスーパーステップから構成されることになる．

LSS 関数 step には，隣接頂点間のメッセージ送受
信を明示的には記述しない．LSS 関数の引数は，自.^ を用いて取得することができる．
4 行目からの init は初期化関数であり，その引数は頂点である．頂点番号が 1 の時には，得られている最短路を 0 とし，そうでなければ無限大 (ここでは999 としている) とする．

頂点 v，他頂点における前回の LSS における値を保6 行目からの step が LSS 関数であり，計算の主持する表 prev である †3 ．また，is v によって，自要部分である．step では，is v を生成子とする内分への入力辺の重み e とその辺で結ばれた隣接頂点

包表記を用いて，入力隣接頂点の直前の LSS におけu の対 (e,u) のリストを得ることができる．1 回前る計算値のレコードを prev u によって取得し，そのの LSS において隣接頂点 u が持つ値は prev u とし中のフィールド dist に辺の重み e を加えて自身まて得ることができる．

での距離とし，それらの最小値を minimum を用いてFregel の簡単なプログラム例として，単一始点最求める．さらに，この値と，自身の直前の LSS にお短路問題 (single-source shortest path，以下 SSSP)

ける計算値，すなわち現状得られている最短路 prev

を解くプログラムを，図 1 に示す．ここでは，頂点番v との最小値を newdist として，SVal newdist を号が 1 である頂点を始点とする．頂点 v の頂点番号

step の値とする．この値は次の LSS における step

は，プリミティブ関数 vid を用いて得る．

の中で，テーブル prev によって参照可能となる．

各頂点は，現時点で得られている自身までの最短路

12 行目で，上で定義した初期化関数，LSS 関数なを，レコード SVal (1 行目) のフィールド値 dist にどを引数にして fregel の呼び出している．第 3 引保持する．レコード中のフィールド値は，二項演算子

数の Fix は，LSS の反復により頂点の保持する値†2 step は頂点における LSS の内容を関数として定義したものであるため，step のことを LSS 関数とも呼ぶ．
†3 実際にはもう一つ curr と呼ばれる表も引数にとるが，後で述べる正規化の結果で使われてこの段階では用いられないので，ここでは説明しない，(SVal 型) がすべて変化しなくなったらプログラムを停止することを指定している．最終結果は，各頂点がSVal 型の値 (dist に最短路長がある) を持つような，
新しいグラフである．

CodeGeneration
FregelProgram

Normalization

Normalized
FregelProgram

Transformation
to FregelIR

FregelIR
Code

GiraphProgramPregel+ProgramGPS
Program

図3

Fregel プログラムのコンパイル処理の流れ

グラフ高階関数 fregel を複数回利用する簡単なプ

Fregel プログラムを，翻訳先のフレームワークが採用

ログラム例として，ある始点からの最短路の最大値，している Java，C++ などにより近い手続き的，かすなわちその始点を端点とするグラフの直径を求め

つ，フレームワーク独立な中間表現である FregelIR

るプログラムを，図 2 に示す．直径を求めるために，のコードへと変換する．最後に FregelIR のコードか

全頂点は SSSP のようにして始点からの最短路を求ら，Giraph，Pregel+ などのフレームワークのプロ

めた後，再度 fregel を用いてそれらの最大値を求め

グラムを生成する．

る (この部分を MAXV と呼ぶ) こととする．MAXVの fregel による計算は，SSSP とほとんど同じ構造をしているので，説明を省略する．このプログラム
を，以後 SSSP-MAXV と呼ぶ．

3 正規化
正規化は，改良前の (Giraph プログラムだけを生成可能な) Fregel コンパイラでも行っており，その処

このプログラムでは，SSSP のためのレコード SVal

理内容に特別な変更があったわけではないが，以降の(1 行目)，および MAXV のためのレコード MVal (3処理の理解のために必要なので，ここで説明する．

行目) の二つをはじめに定義している．SSSP に関する

SSSP-MAXV の プ ロ グ ラ ム 例 で 示 し た よ う に ，

初期化関数 ssspinit (6 行目) と LSS 関数 ssspstep

Fregel のプログラムには fregel 等のグラフ高階関(8 行目) は，図 1 と同じである．同様にして，MAXV数を複数含むことがあり得る．それぞれのグラフ高に関する初期化関数 maxvinit (14 行目) とと LSS 関

階関数を独立な Pregel の計算によって実行させるこ

数 maxvstep (15 行目) も定義している．maxvinit

とも可能ではあるが，一般に Pregel 計算には大きなにおいては，SSSP の結果の値を val v .^ dist に

起動コストが必要である．我々は，複数のグラフ高階

よって取得し，それを初期値としている点に注意さ関数の使用を fregel をひとつだけ用いるプログラ

れたい．1 回目の fregel (21 行目) では入力グラフ

ムに変換することにより，Pregel 計算の起動コスト

g の SSSP を計算し，その結果として得られる最短路をなくし，効率化をはかっている．この変換を「正規を各頂点に保持するグラフを g1 としている．2 回目

化 (normalization)」と呼ぶ．SSSP-MAXV の場合，の fregel (22 行目) では，g1 の MAXV を計算し，全体をまとめた単一の fregel は，はじめに SSSP

それを全体の結果としている (23 行目)．

の計算を行い，それが終わった後に引き続き MAXVの計算を行う．もとのプログラムにおける高階関数

2. 2 Fregel コンパイラに対応する処理の段階を「フェーズ (phase)」と呼図 3 に，Fregel コンパイラによる処理の流れをぶ．すなわち，SSSP-MAXV の場合，SSSP (に含ま示す．はじめに正規化処理により，ユーザが記述しれる fregel) は第 1 フェーズ，MAXV (に含まれる

た Fregel プログラムを正規化された Fregel プログ

fregel) は第 2 フェーズの処理となる．

ラムに変換する．次にこの正規化された (関数型の)

以下で，正規化の方針を SSSP-MAXV を例に用いて説明する．

スーパーステップを記述する関数の定義方法，他頂• 第 1 フェーズに引き続いて第 2 フェーズを行う

点との間のメッセージ送受信の方法，集約の方法なために，SSSP と MAXV のためのレコード，初

どは，フレームワークによって大きく異なる．また頂期化関数，LSS 関数を統合して，全体でひとつ点を停止中に移行させるプリミティブ voteToHalt()のレコード，初期化関数，LSS 関数を定義する．

の関数 (メソッド) 名など，細かな違いも多数ある．

• 全体の初期化関数は，最初に実行されるフェーズがどれかを指定する．

以上より，ここで定義する中間表現 FregelIR は，
フレームワークごとの違いを吸収できる程度の抽象• 全体の LSS 関数は，ひとつの LSS において，い度を持ちつつ，ブロック構造や制御構造 (条件分岐)

ずれかのフェーズの初期化関数・LSS 関数・終了などの共通部分に関しては，Java と C++ の最大公

判定のいずれか (これをステップと呼ぶ) の処理

約数的な表現を持つように設計した．ここで注意すべを行う．

きことは，FregelIR は Fregel プログラムを各フレー• 現在の処理がどのフェーズのどの処理であるか

ムワークに翻訳できれば十分であるため，共通部分を指定するため，フェーズ番号とステップ番号に関しては必要最低限の表現しか提供しない，といの組を「状態」として持つ．全体の LSS 関数は，う点である．たとえば，LSS 関数は，状態を保持し各フェーズ・ステップの計算処理の後，次の状態

スーパーステップごとに状態遷移を行うような Javaへの状態遷移を明示的に行う．

/ C++ のメソッドに翻訳されるが，その内部の個別

このようにして正規化されたプログラムは fregelの計算において while 等の制御構造を用いるようなをひとつしか含まないような Fregel プログラムであ

反復計算は必要としない．そのため，FregelIR は反る．SSSP-MAXV の場合，その初期化関数は計算が復のための制御構造に対応する表現を持っていない．

第 1 フェーズから始まることを示し，LSS 関数は第図 4 に，FregelIR の定義を一部簡略化したものを，

1 フェーズ (SSSP) の初期化関数・LSS 関数・終了判

Haskell の型定義として示す．

定および第 2 フェーズ (MAXV) の初期化関数・LSS

IRProg が，プログラム全体に対応する中間表現で関数・終了判定を順次行うようなものである．このよある．それは，各フェーズで使うデータ型，頂点，辺，

うな LSS 関数は，状態を陽に扱い状態に応じて処理

メッセージ，集約子のデータ型の情報と，フェーズにおを分岐するような比較的大きな定義となり，(これをける計算処理の内容を表すデータ (IRPhaseCompute

人間が読む必要はないが) 人間にとっては読みにくく型) から構成されている．

理解しにくいものとなる．

IRPhaseCompute 型は実質的には IRPhaseCompute
Process 型 の デ ー タ の リ ス ト で あ り，ひ と つ の

4 中間表現 FregelIR

IRPhaseComputeProcess 型のデータが，ひとつの4. 1 FregelIR の設計状態における計算処理を表している．ここには，状我々が Fregel プログラムからの翻訳対象としてい態，必要な局所変数の他，受信処理を含む計算本体のる頂点主体グラフ計算フレームワークは，当面 Giraph

ブロック，次の状態遷移のための条件と遷移先状態・[1]，Pregel+ [8]，GPS [6]，GraphX [4] としている．

送信処理を含むブロックが含まれる．

このうち GraphX はデータの表現および計算方法がブロックは，局所変数と文 (IRStatement) から成っ

Pregel と大きく異なるので FregelIR を通さずに翻訳ている．文は，隣接頂点から値を得てまとめる操作，することを考えている．それ以外のフレームワーク

集約子への書き込み操作，出力辺に沿ったメッセージについては，Giraph と GPS のプログラムは Java，の送信など，フレームワークによる違いを吸収するのPregel+ のプログラムは C++ といった言語の違いに十分な抽象度での定義になっている．

はあるが，大雑把にいうと C 風のブロック構造，制以下，SSSP において隣接頂点から値を得てまと御構造などを持つという点で共通点が多い．一方で，める操作を例として，この抽象度について説明する．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

data IRProg = IRProg String[IRTypeDecl]
IRVertexStruct
IREdgeStruct
IRMsgStruct
IRAggStruct
IRPhaseCompute−− プログラム名−− 各フェーズが使うデータ型−− 頂点のデータ型−− 枝の値のデータ型−− メッセージのデータ型−− 集約子のデータ型−− フェーズにおける計算処理

type IRNameAndType = (String, IRType) −− 名前と型 (IRType の定義は省略)
data IRTypeDecl = IRTypeDecl String [IRNameAndType] −− 構造体名とメンバー
data IRVertexStruct = IRVertexStruct String−− 名前[IRNameAndType] −− メンバー: Prev/Curr 付きのもの[IRNameAndType] −− メンバー: Prev/Curr なしでよいもの
data IREdgeStruct = IREdgeStruct String [IRNameAndType] −− 構造体名とメンバー
data IRMsgStruct = IRMsgStruct String [IRNameAndType] −− 構造体名とメンバー
data IRAggStruct = IRAggStruct String [(IRNameAndType, IRAggOp)] −− 構造体名と，名前，型，用いる演算type IRVertexComputeState = (Int, Int)−− 状態 (フェーズ番号とステップ番号)

data IRPhaseCompute = IRPhaseCompute [IRPhaseComputeProcess] −− 各 (phase,step) における処理内容
data IRPhaseComputeProcess =IRPhaseComputeProcess IRVertexComputeState −− 状態[IRNameAndType]−− 必要な局所変数
IRBlock−− 本体 (含受信処理)[(IRExpr, IRVertexComputeState, IRBlock)] −− 遷移条件，次の状態, 通信
data IRBlock = IRBlock [IRNameAndType] [IRStatement] −− 局所変数と本体
data IRStatement =IRStatementLocal IRVar IRExpr−− ローカルな計算による値の変数への代入| IRStatementMsg IRVar IRAggOp IRExpr −− 隣接頂点の値の集約| IRStatementReturn IRExpr−− return 文| IRStatementVTH−− voteToHalt| IRStatementAggr IRNameAndType IRExpr −− 集約子への書き込み| IRStatementSendN IRNameAndType IRExpr −− (通常の辺に沿った) 送信メッセージのメンバーの名前/型と値
data IRVar = IRVarLocal IRNameAndType −− 局所変数
| IRVarVertex IRNameAndType IRPrevCurr [IRNameAndType] −− 頂点のメンバー| IRVarEdge IRNameAndType [IRNameAndType] −− 枝の値，フィールドアクセス| IRVarAggr IRNameAndType−− 集約
data IRPrevCurr = IRPrev | IRCurr | IRNone
data IRExpr = IRIf IRExpr IRExpr IRExpr −− 条件分岐
| IRFunAp IRFun [IRExpr]−− 関数/演算子適用| IRVExp IRVar−− 変数| IRCExp IRType IRConst−− 定数| IRMVal IRNameAndType−− 送信メッセージ用| IRAggr IRNameAndType−− 集約子からの集約結果値の獲得
data IRFun = IRFun String | IRBinOp String
data IRAggOp = IRAggMin | IRAggMax | IRAggSum | IRAggProd | IRAggAnd | IRAggOr
data IRConst = IRCInt Int | IRCBool Bool | IRCString String | IRCDouble Double
図4

FregelIR の Haskell によるデータ型定義 (一部簡略化した)

SSSP の Fregel プログラムでは，内包表記を用いて隣含むようなプログラムは認めていないが，プログラ接頂点から値を受け取り，辺の重みを加えて最小値をムのそのままの順序で FregelIR に変換すると正しくとっている (図 1: 9-10 行目)．この部分は，FregelIR

動作しないことがある．また，Fregel における関数

では次のような IRStatement 型のデータとして表現

は，各計算の値を変数に束縛し，それらから一度にレされる．

コードを構築する．しかし，FregelIR (および生成さ

IRStatementMsg

れたコード) ではそのような一度の構築が不可能であ(IRVarLocal ("a", irInt))

る場合もあり，レコードの構築をレコードのメンバへ

IRAggMinの代入として分割・適切に配置する必要もある．

(IRMVal ("a", irInt) と辺の値の和)

LSS は (論理的な) 1 段階の処理を表現するが，隣接

ここで "a" はメッセージにつけられた固有の id で，頂点の値を参照したり全体の値を集約したものを利用

結果の代入先の局所変数名も同じ "a" としている．

したりするには LSS を複数の (物理) スーパーステッ

また irInt は整数型を表す．翻訳先を Giraph としプへと分断する必要がある．すなわち，正規化された

た時，次の段階の Giraph プログラムへの翻訳では，

Fregel プログラムでは各フェーズは初期化・LSS・終

上は次のようになる．

了判定の 3 つのステップからなるが，FregelIR では

int a = Integer.MAX_VALUE; // Min の単位元

より多くのステップからなることがある．(物理) スー

for (IntWritable msg : messages)

パーステップをまたいでローカル変数を保持すること

a = Math.min(a, msg.getValue() + 辺の値;
単位元の代入，メッセージに対する反復は，翻訳後はできないので，必要があればそのような変数を頂点の値として定義しなければならない．

において初めて出現し，FregelIR の段階ではこれら

Fregel では隣接頂点の値を直接参照するようにプは IRStatementMsg という抽象度の高い構造の中にログラムを記述する．FregelIR (および生成された

隠されている．

コード) では，そのような処理は，明示的な送信と受信とに分ける必要がある．集約処理についても同様で

4. 2 正 規 化 さ れ た Fregel プ ロ グ ラ ム か らある．

FregelIR への変換
Fregel プログラムの翻訳処理は，Fregel プログラ

5 フレームワークプログラムへの翻訳

ムの正規化の後，正規化された Fregel プログラムの5. 1 概要

FregelIR への変換，さらに FregelIR から各フレーム

4. 1 節で見たように，Fregel プログラム全体はワーク用のコード生成と進む．正規化により Fregel

IRProg 型で表現され，そこには各種データ型の情報，プログラムはひとつのグラフ高階関数からなるプロフェーズにおける計算処理の内容を表すデータが含まグラムとなるが，中間表現 FregelIR との間には次のれている．これをもとに，次のようにフレームワーク

ようなギャップがある．

のプログラムを生成する．

• 関数型言語と手続き型言語

まず各種データ型については，フレームワークごと• LSS の (物理) スーパーステップへのマッピングに必要なデータ型をクラスあるいは構造体を用いて• 隣接頂点の参照を送信と受信とに分離定義する．その際必要に応じてデータを追加すること

これらのギャップについて以下で説明する．

も行う．たとえば Pregel+ では，頂点の構造体の中(正規化された) Fregel プログラムは Haskell サブに出力辺のベクタを保持する必要があるため，このよ

セットの関数型プログラムである．一方，FregelIR

うな構造体メンバの追加などは 5. 2 節で述べる方法

は手続き型言語として設計した．特に，Haskell におを用いて個別に対処している．

いてはプログラム中に循環を許すことが一番大きな

フェー ズ に お け る 計 算 処 理 は ，状 態 ご と に問題となる．Fregel プログラムにおいて真に循環を

IRPhaseComputeProcess 型のデータが対応している．そこで，各頂点で実行されるスーパーステップの関数 (メソッド) は，当該頂点から現在の状態を取得し，その状態に基づき switch 文を用いて処理を分岐させる．各 case では，その状態に対応する

IRPhaseComputeProcess の処理を行うようにする．
5. 2 型クラスの利用
フレームワーク独立の中間表現 FregelIR から各フ
レームワークの Java あるいは C++ コードへの翻訳
は，Haskell により実装した．先に述べたように，中間表現からコードを生成する際，フレームワークによらない共通部分とフレームワーク依存部分がある．
フレームワーク依存部分の生成には，Haskell の型クラスを利用した．
頂点を停止状態に移行させるコードの生成という簡単な例を用いて，フレームワーク依存のコー
ド生成の基本的な考え方を説明する．停止状態への移行は，中間表現では IRStatement 型のデータ

IRStatementVTH で表現されており，これに対応する
実際のコードは，Giraph では当該頂点 vertex に対する vertex.voteToHalt() というメソッド呼出しであり，Pregel+ では vote to halt という関数呼出しである．

1 −− 依存コード生成のための型クラス
2 class PregelGenerator g where
3...
4−− VoteToHalt() に対応する文字列
5
sVoteToHalt :: g -> String
6...
7
8 −− Giraph プログラム生成用
9 data GiraphGenerator = GiraphGenerator
10
11 instance
12 PregelGenerator GiraphGenerator where
13
...
14
sVoteToHalt GiraphGenerator =15"vertex.voteToHalt()"
16
...
17
18 −− Pregel+プログラム生成用
19 data PregelPlusGenerator =20
PregelPlusGenerator
21
22 instance23 PregelGenerator PregelPlusGenerator where
24
...
25
sVoteToHalt PregelPlusGenerator =26"vote_to_halt()"
27
...
28
29 −− 中間表現 IRStatement の翻訳
30 ggStatement :: (PregelGenerator g) =>31
g -> IRStatement -> [String]
32 ggStatement g IRStatementVTH =33[sVoteToHalt g]
34 −− 他のパターンマッチは省略
図5

フレームワーク依存コードの生成

このようなコード生成を行うために，型クラス

例として，中間表現 IRStatement を翻訳する関数

PregelGenerator を定義する (図 5)．この型クラス

ggStatement の定義を，図 5 に示す．ggStatement

では，フレームワーク依存のコード生成を行うためのの第 1 引数は g であり，ここには GiraphGenerator，

いろいろな関数を定義する必要があり，その中のひと

PregelPlusGenerator など，翻訳先のフレームワー

つに sVoteToHalt という voteToHalt() に対応する

ク を 表 す PregelGenerator の イ ン ス タ ン ス が 与

実際の関数 (メソッド) 呼出しを表す文字列を返す関えられる．中間表現が IRStatementVTH の時には，数がある (5 行目)．

その翻訳結果はフレームワーク依存となるので，Giraph プログラム生成のために GiraphGenerator
型 を 定 義 (9 行 目) し ，こ れ を PregelGeneratorsVoteToHalt g として g のインスタンス宣言の中で定義された関数が呼び出されるようにする．

のインスタンスとする．そのインスタンス宣言のこのようにして，各フレームワークに対応する

中で，関数 sVoteToHalt を Giraph 用に定義 (14PregelGenerator のインスタンスを適切に定義すれ

行 目) する ．Pregel+ プ ログ ラ ム生 成 のた めに はば，依存部分はインスタンス宣言の中に閉じ込めるこ

PregelPlusGenerator 型を定義 (19 行目) し，インとができ，コード生成部のモジュール性を高めること

スタンス宣言を同様に記述する．

ができる．

中間表現からフレームワークコードを生成するプ
ログラム中の関数の大部分は，PregelGenerator ク

5. 3 集約子への書き込みの翻訳

ラスのインスタンス g を引数にとるように定義する．

集約子への値の書き込み処理は，フレームワークにより大きな違いがある．

Giraph の場合，スーパーステップのメソッドの中で
aggregate(name, value)

された Fregel プログラムから FereglIR への変換とFregelIR からのコード生成の方法を述べた．現状では，小さな例題を用いた動作の検証しか行われていなとして，集約子 (名前で区別できる) name に値 value

い．今後は，複数の例題を用いてコード生成するととを書き込むことができる．

もに，Giraph と Pregel+ 以外のフレームワークへ

一 方 Pregel+ で は ，ス ー パ ー ス テップ の 関 数の翻訳も実現し，本稿で述べた中間表現とコード生成の 中 で aggregate の よ う な 関 数 を 呼 ぶ の で は なの実用性を検証していく必要がある．また，中間表現

く，各 ス ー パ ー ス テップ が 終 わった 後 に 集 約 を 行上において，または，コード生成時に最適化を行うこうメソッド (具体的には Aggregator クラスの子クとにより，生成されたコードの性能を吟味することもラスの stepPartial，stepFinal，finishPartial，必要である．

finishFinal) が呼ばれ，実際の集約処理が行われる
ので，これらのメソッドを適切に定義しておかなけれ

謝辞 本研究の一部は，JSPS 科研費 JP26280020，

JP15K15974 の助成を受けたものである．

ばならない．
集約子への書き込みは，FregelIR では IRStatemnet型に属すデータ IRStatementAggr nt expr で表現されている．ここで nt は集約子を表す名前とデータの型を表す組，expr は書き込む値を表す式である．
これに対する翻訳は，Giraph の場合 expr を翻訳してから単純に aggregate を呼ぶようにするだけで良いが，Pregel+ の場合はスーパーステップ終了後の集約処理で正しく集約が行われるようにする必要がある．そのため，集約子をまとめた構造体 AggDataを定義し，さらに頂点の構造体の中に，以下のメンバを持つようにした．

• スーパーステップ後の集約処理が必要であることを表すメンバ needAgg．ここには，書き込む集
約子の番号を保持する．

• 集約子に書き込む値を保持する AggData 型のメ
ンバ aggv
そうすると，IRStatementAggr nt expr に対する
翻訳は，当該頂点の構造体中の needAgg に集約子の番号を代入し，aggv に expr の計算結果を代入すれば良い．さらに stepPartial メソッドは，needAgg
を参照して適切な集約が行われるような処理を行う
ように Pregel+ のコードを出力する．

6 おわりに本稿では，Fregel を複数の頂点主体グラフ計算フ
レームワークに対応させるために設計した，フレー
ムワーク独立な中間表現 FregelIR の設計と，正規化

参 考 文 献[1] Apache Giraph: The Giraph Website. http://giraph.apache.org/.
[2] Coll Ruiz, O., Matsuzaki, K., and Sato, S.:
S6Raph: Vertex-centric Graph Processing Framework with Functional Interface, Proceedings of the
5th International Workshop on Functional HighPerformance Computing, FHPC 2016, New York,NY, USA, ACM, 2016, pp. 58–64.
[3] Emoto, K., Matsuzaki, K., Hu, Z., Morihata, A.,
and Iwasaki, H.: Think Like a Vertex, Behave Likea Function! A Functional DSL for Vertex-centric
Big Graph Processing, Proceedings of the 21st ACM
SIGPLAN International Conference on Functional
Programming, ICFP 2016, ACM, 2016, pp. 200–
213.
[4] Gonzalez, J. E., Xin, R. S., Dave, A., Crankshaw,
D., Franklin, M. J., and Stoica, I.: GraphX: Graph
Processing in a Distributed Dataflow Framework,
11th USENIX Symposium on Operating Systems
Design and Implement ation, OSDI ’14, Broomfield, CO, USA, October 6-8, 2014., Flinn, J.
and Levy, H.(eds.), USENIX Association, 2014,
pp. 599–613.
[5] Malewicz, G., Austern, M. H., Bik, A. J., Dehnert, J. C., Horn, I., Leiser, N., and Czajkowski, G.:
Pregel: A System for Large-scale Graph Processing, Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, SIGMOD ’10, ACM, 2010, pp. 135–146.
[6] Salihoglu, S. and Widom, J.: GPS: A Graph
Processing System, Proceedings of the 25th International Conference on Scientific and Statistical Database Management, SSDBM, ACM, 2013,
pp. 22:1–22:12.
[7] Valiant, L. G.: A Bridging Model for Parallel Computation, Communications of the ACM,
Vol. 33, No. 8(1990), pp. 103–111.
[8] Yan, D., Cheng, J., Xing, K., Lu, Y., Ng, W., andBu, Y.: Pregel Algorithms for Graph Connectivity
Problems with Performance Guarantees, Proceedings of the VLDB Endowment, Vol. 7, No. 14(2014),
pp. 1821–1832.

[9] 江本健斗, 松崎公紀, 胡進行, 森畑明昌, 岩崎英哉: 大規模グラフ並列処理のための関数型領域特化言語 Fregelとその評価, 日本ソフトウェア科学会第 33 回大会 (2016年度) 講演論文集.