DEIM Forum 2016 D2-3

メニーコア環境におけるグラフ処理エンジンの高速化
伊藤

竜一†

藤森

俊匡††

鬼塚

真††

† 大阪大学工学部電子情報工学科 〒 565–0871 大阪府吹田市山田丘 2–1†† 大阪大学大学院情報科学研究科 〒 565–0871 大阪府吹田市山田丘 1–5
E-mail: †{itou.ryuichi,fujimori.toshimasa,onizuka}@ist.osaka-u.ac.jp
あらまし近年, ネットワークやストレージ, センサなどの進歩により, 大規模なグラフ構造のデータが一般的になり, それを如何に効率的に処理するかが技術課題となっている. 特に, グラフ処理の基盤となるエンジンの高速化は重要な要素である. しかしながら, 並列度が増加すると, 同時実行制御がボトルネックとなり, 実行効率が悪化することが知られている. そこで, 本稿では, 並列環境として単一マシンメニーコア環境に焦点を当て, 同時実行制御にCompare-and-Swap 命令や Hardware Transactional Memory を用いて最適化を図ることで並列化のオーバーヘッドを減らし, 高速な処理を実現した. ベースとして用いたグラフ処理エンジンである GraphChi と比較して, 同時実行
制御に Compare-and-Swap 命令を利用した制御や Hardware Transactional Memory を用いた手法に置き換えること
で, 処理全体にかかる時間を最大約 19%, 同時実行制御にかかる時間を最大約 76% 短縮することに成功した. また,Hardware Transactional Memory の利用最適化を行うことで, 更に最大約 8% の高速化に成功した.
キーワード グラフ処理エンジン, メニーコア, 同時実行制御, Compare-and-Swap, Hardware Transactional Memory

1. は じ め にに, 現実世界で見られるようなグラフデータの多くには, 少数ながら, 多数の辺が集中する頂点が含まれることが知られてい身の回りの様々な事象がデータとして蓄積されることが一般る [7]. このような頂点は, 隣接頂点の多さから並列処理する際的になってきたことで, 結果として得られるソーシャルグラフ

に更新操作の資源として参照される回数が非常に多くなるため,や Web グラフといったグラフ構造のデータが大規模化してい一貫性を保つためのコストが高く, ボトルネックになりやすい.

る. 例えば, 2015 年 9 月時点の Facebook のユーザ数は 15 億

このような頂点に関する計算タイミングを分散させることで,5000 万人にも及び [1], その中でのユーザ同士の繋がりやポスト

競合を解決するコストを抑えることができるが, グラフデータとそれに対するコメントなどが, 大規模且つ複雑なネットワーの局所性を十分に活かすことができなくなる. 一方, 計算をシ

クを形成している. このような莫大なグラフデータ源から, 有リアル実行にすることで局所性を最大限に活かすことができる

益な情報を如何に迅速に取り出すかが技術課題となっている.

が, 並列環境を活かすことができなくなる, というトレードオ

これまではプロセッサの動作周波数向上により処理速度を上げ

フが発生する. 本稿の提案手法では同時実行制御に Lock-free

ることが可能であったが, その成長が鈍化しつつあり, 増加するである Compare-and-Swap 操作や Hardware Transactional

コアを活かした並列処理による高速化の重要性が増している.

Memory [8] を適用することで並列環境と局所性の両方を維持

並列処理へのアプローチとして, 単一マシン, 限られたコア,

し, グラフ処理の高速化を図った. 並列計算モデルとして, 同

共有メモリ環境であることを利用する方法がある. 実行環境の時実行制御を必要とするがデータの競合発生率は低い, というセットアップや管理が簡単であり, データのやり取りにネット

Lock-free な手法で用いられる投機的実行と相性の良い特徴をワークを介することがないのでレイテンシが少ないといった持つ Gather-Apply-Scatter computation model [9] を利用す利点がある一方, CPU の数が比較的少数で計算能力に制限がる. 更に, Gather-Apply-Scatter computation model を構成あり, 巨大なデータを一度に全てメモリ上にロードすることがする演算の一つである Sum 演算に関する部分が可換モノイド

できないといった欠点が存在する. そのため, 限られた計算資であるという性質に注目し, Sum 演算を多段階に分解すること源で, memory-based なシステムと比較すると非常に低速であで投機的実行の失敗を抑制する最適化を行った.

る disk-based なシステムとなる. 単一マシン用グラフ処理エ

本稿では Gather-Apply-Scatter computation model を利用

ンジンの既存の研究として, GraphChi [2] や TurboGraph [3],できる単一マシングラフ処理エンジンとして, GraphChi をベー

VENUS [4], GridGraph [5], NXGraph [6] が挙げられる. いずスに提案手法の実装し, 評価実験を行った. 同時実行制御に従来れの研究も, アクセスの局所性を生かすデータ構造とアルゴリの Mutex を用いた手法を Compare-and-Swap を用いた手法

ズムを設計することで, コアの利用率および IO 操作量の削減に置き換えることで処理全体にかかる時間を最大約 19%, 同時

して高速化を図っている.

実行制御にかかる時間を最大約 76%, Hardware Transactional

グラフ処理高速化の課題の一つとして, 更新処理時の一貫性

Memory を用いた手法に置き換えることで, 処理全体にかかを保つためにコストがかかるという問題が挙げられる. 一般的る時間を最大約 10% , 同時実行制御にかかる時間を最大約53% 短縮することに成功した. また, Hardware Transactional

タイミングで他のワーカーから書き換えられてしまう可能性がMemory の利用最適化を行うことで処理全体にかかる時間を更あるため, 計算精度が下がるが, 制御対象が少ないほど同時実行に最大約 8% 短縮することに成功した.

制御によるオーバーヘッドが抑えられ, また, 各ワーカーへのタ

本稿の構成は以下の通りである. 2 章 で本稿の前提となる知識について述べる. 3 章 で提案手法を詳説し, 4 章 で提案手法

スク分散に全体の実行時間が影響を受けなくなり, 実行時間を短縮することができる.

の実験とその評価・分析を行う. 5 章 で関連研究を紹介し, 6 章

2. 2 同時実行制御と同期プリミティブ

で本稿全体を俯瞰しまとめる.

Data consistency model を導入するなどしてデータの一貫

2. 前 提 知 識

性を保つためには, 共有資源を他のワーカーから操作されないように同期プリミティブを利用して同時実行制御をする必要が本章では, グラフ処理における同時実行制御で必要となる前ある. この同時実行制御には多くの手法が存在しており, 大きく

提知識と, 提案手法のベースに用いたグラフ処理エンジンと計分けて Lock-based と Lock-free な手法があり, それぞれ 2.2.1

算モデルについて述べる. 2.1 節 では同時並列的処理における

節 と 2.2.2 節で述べる.

データの一貫性を保つためのモデルについて, 2.2 節 では 2.1

2. 2. 1 Lock-based

節 を実現するために用いられる同期プリミティブについて, 2.3

Lock-based な手法として, 同期プリミティブに Lock 命令

節 ではグラフ処理で用いられる計算モデルについて, 2.4 節 でを使ったものが知られている. 特定の共有資源を利用する前にはベースに用いたグラフ処理エンジンである GraphChi についロックを取得することで, 他のワーカーが同時に同じ共有資源て述べる.

にアクセスしてしまうことを防ぐ排他的な方法である. コスト

2. 1 Data consistency modelがかかりやすいという問題点があるが, 仕組みが単純なため用

従来はシングルマシン―シングルコア―シングルスレッドでいられることが多い.

の計算が主流であったが, 近年, コア単体での性能向上速度が必

2. 2. 2 Lock-free

要とされる処理の大規模化に追いつかず, マルチマシン―マル

Lock-based な手法とは異なり, ロックを用いない, つまり,

チコア―マルチスレッドでの計算へと移行してきている. 大規

他のワーカーに影響を与えない Lock-free な手法が知られてい模グラフ処理のように, 一度に巨大な共有資源を扱う処理をマる. この手法は同期プリミティブに専用の機械語命令を用いる

ルチマシン―マルチコア―マルチスレッドで, データの一貫性ことで, 大きく分けて 2 つのアプローチから利用されている.

を保ちながら計算するためには, 同時実行制御 を行う必要があ

1 つ目は特定ドメインに特化した Lock-free データ構造をる. そのような処理では, 一度の更新処理に必要となる共有資作るというアプローチである. 同期プリミティブに Compare-

源は共有資源全体からするとごく一部であることが多いため,

and-Swap(CAS) という機械語命令を用いる. ロックを取るこ同時実行制御の対象範囲を変化させることで効率化を図ることとなく値の変更を検知することでデータの一貫性を保つことがができる. また, 多少の計算精度を犠牲にすることで処理をよ可能だが, 複数の値に対して一貫性が必要な場合, 実装が複雑にり高速化することができる場合もある. この, 同時実行制御のなってしまうという問題がある.

粒度や方法を定めたものを Data consistency model と呼ぶ.

2 つ目のアプローチとして, Transactional Memory(TM) [8]グラフ処理で利用される同期実行で制御を行うための具体的が挙げられる. TM とは, データベース分野におけるトランザ

な Data consistency model として, Bulk Synchronous Paral-

クションをメモリに応用したものである. 一連の処理を行う際

lel(BSP) [9] がある. これは, 処理に superstep という同期単位に, トランザクション内のすべての処理が完了するまでメモリを定め, superstep ごとに設けられた barrier のタイミングで全の共有部分に反映させず, トランザクション内のすべての処理

ワーカーのデータを一斉に同期させるというモデルである. 値が終わった時点でトランザクション内で使われたデータとメモを参照する場合は前回の superstep で得られた値を利用するこリの共有部分のデータをチェックし, T) 一貫性が保てる場合はとで, 他のワーカーによるデータの変更の影響を受けず, 計算精

トランザクションの結果をメモリに反映 (Commit) し, トラン

度と一貫性を保つことができる. しかしながら, barrier のタイザクションが成功したことを通知する; F) 一貫性が保てない

ミングはすべてのワーカーが処理を終えたときと決められてい場合はトランザクションの結果を破棄 (Abort) し, トランザク

るため, 各ワーカーへ分散されたタスクに偏りが生じているとションが失敗したことを通知する. このように一連のデータの処理時間の長いワーカーに全体の処理時間が左右されてしまう

読み込み・書き込みを 1 つのトランザクションとして扱うこと問題がある.

で原子性・一貫性を, 各トランザクションを個別に管理するこ一方, 分散グラフ処理エンジンである GraphLab などで用とで独立性を保証する.（注 1） TM を利用することで, 読み込み

いられている完全な非同期実行型の Data consistency model

側責任で悲観的となる Lock-based な手法とは違い, 書き込みとして, vertex consistency / edge consistency / full consis-

側責任で楽観的に処理できるため, トランザクションの Aborttency [10] がある. vertex consistency は注目頂点の値のみ,が発生しない限りでは同時実行制御のスループット向上を望edge consistency は注目頂点と隣接する辺のみ, full consis-

むことができる. また, トランザクションという単位で扱うた

tency は注目頂点と隣接する辺と頂点のみに同時実行制御を行う. 当然ながら, 同時実行制御対象外の辺や頂点の値は任意の（注 1）：揮発性メモリ上で行われるため, 耐久性については保証されないめ, 複数のトランザクションをまとめて 1 つのトランザクショ

Algorithm 1 Gather-Apply-Scatter computation model

ンとして利用することが容易であるという利点が挙げられる.

Input: Gn (V, E)

TM の実装として, Software Transactional Memory と Hard-

Output: Gn+1 (V, E)

ware Transactional Memory がある. Software Transactional

1: foreach e ∈ E do

Memory(STM) とは, TM をソフトウェアレベルで実装したものである. 同期プリミティブとして前述の CAS 命令が用いら

2:

vdest ← get vertex(e.out)

3:e.cur val ← Scatter(e)

4:

lock

れ, 1 つ目に挙げたアプローチの一種でもある. 一方, Hardware

5:

Transactional Memory(HTM) とは, TM をハードウェアレベ

6:ルで実装したものである. 現時点では, Intel Haswell [11], IBM

7: end forBlue Gene/Q [12]・POWER8 [13]・zEnterprise EC12 [14] な

8: foreach v ∈ V do

どの一部のプロセッサに, それぞれ独自の命令として実装されている. STM と比較して, *) トランザクションの途中経過はす

9:vdest .acc ← Sum(vdest .acc, Gather(e.prev val))unlockv.val ← Apply(v.acc)

10: end for

べて高速なキャッシュ上で管理される; *) ユーザランドにオブジェクトを生成しない; 等, ハードウェア資源を有効に利用でき

前者の場合は, Data consistency model を選択することがでるためスループットが高い.

き, Sum 演算は Mutex を使って同時実行制御が行われる. 後

2. 3 Gather-Apply-Scatter computation model者の場合は, 基本的に非同期で処理が行われるが, 競合が起こ

グラフ処理で用いられるユーザ定義の計算アルゴリズムをり得るデータに関しては全てシリアル実行することで同時実記述する方法は処理エンジンにより様々である. しかしなが行制御は行わない. ディスクアクセスには Parallel Sliding

ら, 前述の Data consistency model を効率的に実現するため,Windows(PSW) と呼ばれる, 実行時にランダムディスクア

ユーザが計算アルゴリズムを合成可能な形に分解することをクセスを発生させないアルゴリズムを利用してグラフデータの前提としたインターフェースが利用されることが多い. その

読み書きを行っている. PSW は, 全てのグラフデータを一度具体的な計算モデルとして, PowerGraph [9] で提案され, 他にメモリに載せることが出来ず, disk-based となることを前提のグラフ処理エンジンでも類似モデルが使われることが多いとしている. グラフ G = (V, E) に対して, 1〜3 からなるプリ

Gather-Apply-Scatter computation model(GAS) が知られて

プロセッシングを行う. 1) V を P 個のインターバルに分割すいる. GAS では, 辺から値を取得し, 集約するための Gather

る (後述する shard がメモリに載るように調整する); 2) 各イと Sum , 頂点の値を更新するための Apply , 頂点の値から隣

ンターバルに含まれる頂点を終点とする全ての辺をそれぞれの接する辺の値を更新するための Scatter と呼ばれる 4 つの演

インターバルに shard として関連付ける. つまり, 全ての辺算で 1 つの計算アルゴリズムを定義する. GAS の処理フローのは必ず唯一の shard に含まれる; 3) 各 shard に含まれる辺を擬似コードを Algorithm 1 に示す. 1〜5 行目の foreach ルー

始点でソートする; 実行時には, i〜iv からなる, shard に含まプで Gather と Sum, Scatter 演算を行い, 全ての辺に対して値れる辺がソートされていることを利用した高速なシーケンシャの割り当てと取り出しを完了させてから, 6〜8 行目の foreach

ルアクセスで処理を行う. i) 注目インターバルに関連付けられループで一括して Apply を実行し, 頂点データの更新をする.

た shard を memory-shard としてメモリにロードする; ii)

なお, これを非同期に計算する場合は, Sum 演算のみ同時実行

注目インターバルに含まれる頂点を始点とする辺をディスク上制御の対象とすれば全体のデータの一貫性を保つことができ,の shard からメモリにロードする. 始点でソートされているた

並列処理の恩恵を受けやすいという特徴を持つ.

め, インターバルごとに, 各 shard (Parallel) の対象となる辺集合 (Window) が前から後ろへとスライドしていく (Sliding);

表 1 Algorithm で使用されている主な記号の定義

Gi (V, E)i イテレーション目の頂点集合 V ,辺集合 E からなるグラフ Giii) 注目インターバルに含まれる各頂点に対し, ユーザ定義の更新処理を並列実行する; iv) i〜iii を残りのインターバルに対し

get vertex(i) 頂点番号 i から頂点データを取得する関数て繰り返す; このように実行することで, 1 インターバルにつき

e.cur val

BSP における現イテレーションの辺 e の値

P 回のシーケンシャルアクセス, つまり, 全体で P 2 回のシー

e.prev val

BSP における前イテレーションの辺 e の値

ケンシャルアクセスで処理を完了することができる. P は グラ

v.acc

頂点 v の Sum 演算におけるアキュムレータ

フサイズ/メモリサイズ 程度となるため, 現実的な値と言える.

3. 提 案 手 法
2. 4 GraphChi
本稿では, 提案手法を GraphChi [2] に組み込むことで, メ

事前実験として, CAS 操作や HTM を含む, 同期プリミティ

ニーコア環境に対応した高速なグラフ処理エンジンを提案す

ブの特性評価を行った. 類似した先行ベンチマーク調査として,る. そこで本節では, ベースとなるグラフ処理エンジンである

STAMP [15] [16] などが挙げられるが, 具体的なアプリケーショ

GraphChi について概説する. グラフ処理を行うユーザプロンを対象としたものであり, 競合率や計算負荷といった基本的グラムのために, GAS に基づくインターフェースと, 1 つの更な指標に基づくベンチマークはなされていなかった. そこで,新関数を定義して利用するインターフェースを提供している.

いくつかの指標に基づく同期プリミティブに関するベンチマー

クを作成した. 結果として, 図 1 から分かるように, ほぼすべ

Algorithm 2 GAS with CAS operationての条件において CAS 操作が高速であることが, また, 並列度

Input: Gn (V, E)

が高い / データ競合率が低い / 同時アクセス要素数がある程

Output: Gn+1 (V, E)

度少ない / トランザクションサイズが小さい, といった条件下

1: parallel foreach e ∈ E do

で HTM の性能が最大限発揮されることが確認された. ただし,

CAS 命令を使った操作は, 直接的には複数値に対する同時実行制御ができないという問題がある.

2:

vdest ← get vertex(e.out)

3:e.cur val ← Scatter(e)4:f etched ← Gather(e.prev val)

5:

while true do

本稿の提案手法では, GAS に基づく単一マシン用グラフ処理

6:

loaded ← vdest .acc.load()

エンジンの同時実行制御のコストを下げることでグラフ処理の

7:

intermediate ← Sum(vdest .acc, f etched)

高速化を実現する. GAS は, 構成する 4 つの演算のうち, Sum8:

if accdest .acc.compare and swap(の実行時のみ共有資源のデータの一貫性を考慮することで全体の一貫性を保つことができる計算モデルである. GAS による更新処理のうち, 並列セクションにクリティカルセクションがloaded, intermediate) then

9:

break

10:
11:

end if12:

end while

占める時間は多くのアルゴリズムで 20〜30%, 意図的に負荷を

13: end for

偏重させても 75% 程度と事前の計測により分かっている. 多

14: parallel foreach v ∈ V dov.val ← Apply(v.acc)

数のデータからごく一部のデータを非同期に取り出して扱って15:いることに注意すると, Sum は同時実行制御を必要とするが,16: end for

データの競合が起こる確率は非常に低い演算ということが分
かる. つまり, Lock-based な悲観的同期実行制御を用いると,lock/unlock によるオーバーヘッドが大きい. 一方, Lock-free
は楽観的同時実行制御であるため, データの競合が起こる確率が低い場合においてはほとんどコストが発生しない. そこで, 提Algorithm 3 GAS with HTM
Input: Gn (V, E)
Output: Gn+1 (V, E)
1: parallel foreach e ∈ E do
2:

vdest ← get vertex(e.out)

案手法では, Sum で既定の単一アキュムレータのみにアクセス

3:e.cur val ← Scatter(e)する場合は CAS 操作を, それ以外のオブジェクトにもアクセ

4:f etched ← Gather(e.prev val)

スする場合は CAS では制御出来ないため, HTM を適用する.

5:

transaction start

Algorithm 2 は同時実行制御に CAS 操作を, Algorithm 3 は

6:

HTM を適用した GAS による更新処理の擬似コードを示す.
前者は 5〜12 行目で CAS 操作を利用することで共有資源であvdest .acc ← Sum(vdest .acc, f etched)transaction end

7:

8: end for
9: parallel foreach v ∈ V do

る vdest .acc の一貫性を保つ. 後者は 5〜7 行を HTM のトラン

10:

ザクションとすることで, 他ワーカーからトランザクション内

11: end forv.val ← Apply(v.acc)

すべての共有資源の一貫性を保つ. どちらも Data consistencymodel に BSP を利用している.
3. 1 Hardware Transactional Memory 適用の最適化
ソーシャルグラフのような現実世界によるグラフデータでは,そのデータが大規模化すると隣接編が極端に多い頂点が発生し得る. このような頂点が含まれると, GAS の更新処理が集中し,に依存しないようにするため, 定義 1 に示すように, Sum を二項演算とする隣接辺データ集合が可換モノイドであることが必要条件である.


定義 1 Sum 演算における可換モノイド

データの競合が非常に発生しやすくなる. 特に, HTM において隣接辺データ集合

は, データの競合が発生した時点でトランザクションが Abort

二項演算 Sumされるため, 急激に同時実行制御のコストが増加する. そこで,

∀s1 ∀s2 ∀s3 ∈ S ; (s1 ⊙ s2 ) ⊙ s3 = s1 ⊙ (s2 ⊙ s3 )

本節では, 隣接辺が多い頂点が含まれる場合でも, 仮想ノード

データの競合発生率を抑える手法を提案する.

GAS 処理のうち, Sum は, 注目頂点の値を更新する際に必要となる隣接辺データを集約するための演算である. 隣接辺は複数存在する可能性があり, Sum による集約演算は隣接辺の数だ
け呼び出される. この際, 集約結果が処理対象となる辺の順序

S⊙:S×S →S∃z∀s ∈ S ; z ⊙ s = s ⊙ z = sという実際の 1 つの頂点に対して複数の中間結果を保持する概念を導入することで, 共有資源に対するアクセスを分散させて∀s1 ∀s2 ∈ S ; s1 ⊙ s2 = s2 ⊙ s1
そこで, 組 (S, Sum) が可換モノイドであることを利用して,Sum による集約演算を多段階に分割する. 一旦隣接辺データを仮想ノードに集約し, その後, 頂点単位で対応する仮想ノードを再度集約することで最終的な値を算出する. このように仮想ノードを挟んで部分集約をすることによって, 辺が集中する頂点の演算が発生してもデータの競合発生率が上がらず, トラン（注 2）：CAS の同時アクセス数が 2 以上の場合と No contrl は正確な同時実行制御が行われておらず参考値である



ザクションの Abort 率が抑制されることで HTM の特性を活(a) 同期プリミティブと並列度の関係(b) 同期プリミティブと計算負荷の関係(c) 同期プリミティブとアクセス対象
プールサイズの関係(d) 同期プリミティブとアクセス対象
要素サイズの関係(e) 同期プリミティブと 1 クリティカルセクショ (f) 同期プリミティブと並列セクション中に占めンあたりの同時アクセス要素数の関係

るクリティカルセクションの割合の関係

図 1 同時実行制御ベンチマーク （注 2）

かした処理の高速化することができる.

本実験で用いたグラフデータを概説する. Pokec [17] [18] は,

3. 2 GraphChi への実装

SNS である Pokec 内でのユーザの繋がりを能わすグラフデー

2.4 節 で述べた通り, GraphChi はユーザプログラムのためタである. Power law exponent（注 3） が高いという特徴を持つ.

に 2 つのインターフェースで提供しているが, 本稿での提案手

Flickr [19] [20] は Flickr という画像投稿コミュニティ内でのユー

法は GAS を対象とした手法であるため, GAS に基づくインザの繋がりを表すグラフデータである. Power law exponent がターフェースに対して実装を行った. なお, 提案手法では, 単一

低いという特徴を持つ. LiveJournal [21] [22] は, ブログサービ

マシンでスレッドプールを利用した並列処理を行うため, ロースである LiveJournal でのユーザの繋がりを表すグラフデータ

ドバランスを保つことは容易なので Data consistency modelである. Wikipedia, English [23] [24] は 英語版 Wikipedia 記には BSP に基づいたモデルを採用した. 隣接辺データを集約

事間のハイパーリンクを表すグラフデータである.

する Sum 演算は, メモリから shard をロードする際に, 辺単本実験で利用したグラフ処理アルゴリズムを概説する. PageR-

位で呼び出される. そこで, トランザクションの範囲を狭める

ank は有向グラフの各頂点の重要度を決定するためのアルゴリ

ため, 共有資源である演算の中間結果に Sum でアクセスするズムである. 更新時の計算量が少なく, データの更新回数が多部分のみに CAS 操作 と HTM を適用した. また, 各頂点に,いという計算的特徴を持つ. 単一始点最短経路問題 (SSSP) は,

スレッドごとに利用する中間結果を分けて持たせることで仮想更新時の計算量が少ないという計算的特徴を持つ. 予め開始頂ノードを実現した. これは, 仮想ノードがスレッドローカルに点を指定し, 収束するまで計算を行う. 加えて, 更新時のクリなっているため, 同時実行制御を必要としないため高速な実行

ティカルセクション内計算量を意図的に増やした検証用アルゴが可能である. 一方, 仮想ノードの個数が多くなり, 中間結果を

リズム (heavy) を利用した.

保持するためのメモリの使用量とのトレードオフとなる. その本実験では異なる特徴を持った 2 つの環境で行った. 1 つ目はため, 各頂点ごとに, 流入辺数が閾値以上であり, データの競合

コンシューマ向けの性能を持つデスクトップパソコン (PC) を利が発生しやすい頂点のみに仮想ノードを実装し, それ未満の頂用した. CPU は TSX をサポートしている Intel Core i5-6600,

点に関してはデータの競合率は低いと見なして仮想ノードを用

動作周波数は 3.3GHz で 物理 4 コアである. メモリは 16GB,

いずに HTM での同時実行制御を行う実装とした.

ストレージとして HDD を利用した. HDD の書き込み速度は

4. 実験・評価

約 350 MB/sec, 読み込み速度は 約 210 MB/sec であった. ソ
フトウェア環境として, OS に Fedora23(kernel-4.2.3), コンパ

提案手法の性能を評価するため, GraphChi における既存のイラに g++5.3.1 を利用した. 2 つ目の環境として, ハイエン実装である Mutex をベースラインとして検証を行った. グラ

ドサーバ (SV) を利用した. CPU は TSX をサポートしている

フデータやアルゴリズムの特徴による差異を確認するため, 表Intel Xeon E7-8890v3, 動作周波数は 2.5 GHz で物理 18 コア

2 に示すグラフデータで, 複数のグラフ処理アルゴリズムを用
いて実験を行った.

（注 3）：グラフデータが従う冪乗則の指数. 数値が高いと辺が集中する頂点の割合が下がる.

表2

Name

データセット

Edges Power law exp. shard 数 (PC) shard 数 (SV)

Nodes

Pokec [17] [18]1,632,803

30,622,564

3.08102

2

Flickr [19] [20]2,302,925

33,140,017

1.7110

2

2

LiveJournal [21] [22]4,847,571

68,993,773

2.6510

3

3

Wikipedia, English(dbpedia) [23] [24] 18,268,992 136,537,566

2.371065である. メモリは 2TB, ストレージとして HDD を利用した.

仮想ノードの使用メモリ量を 図 5 に示す. 横軸ラベルの仮想

HDD の書き込み速度は 約 1.3 GB/sec, 読み込み速度は 約 200

ノードに続く数値が閾値を示す. 図 5 や PC 環境での結果より,

MB/sec であった. ソフトウェア環境として, OS に Red Hat

HTM にスレッドローカル仮想ノードを利用した最適化を行う

Enterprise Linux7(kernel-3.10.0), コンパイラに g++5.3.0 をことで, 処理全体の時間を更に最大約 8% 短縮することに成功利用した. どちらの環境も -O3 オプションを用いることでコンした. 閾値を下げる, つまり, スレッドローカル仮想ノードによ

パイル時最適化を行っている. 並列度はそれぞれの環境における実行の割合を増やすと, 同時実行制御のコストを抑えることる物理コア数とした. また, グラフデータの環境別 shard 数は,ができ, 実行性能を上げることができるが, 多量のメモリを必

GraphChi の機能により, 表 3 のように定められた.

要とする. PageRank や SSSP のような Sum 演算の集約対象(A) 様々な環境における性能特性, (B) 並列度による性能変が単一値であるアルゴリズムでは影響は少ないが, 多値を取る化, (C)HTM に仮想ノードを用いた最適化を行った手法についアルゴリズムの場合は必要メモリ量が非常に多くなり, 1 shardての実験をそれぞれ行った.

あたりのサイズを減少させ, 処理全体のパフォーマンスを下げ(A) 同時実行制御方法の処理全体の時間の比較を 図 2 に示る可能性がある. 一方, 閾値を上げる, つまり, HTM での実行

す. また, 既存手法の Mutex によるオーバーヘッドが処理全体の割合を増やすと, スレッドローカル仮想ノードによる高速化の時間に占める割合を 表 3 に, 提案手法の同時実行制御にかか分を初期化処理のオーバーヘッドが上回り実行性能が低下してる時間の Mutex との比率を 表 4 に示す. 図 2, 表 3, 表 4 やしまう. 図 5 からこのトレードオフが見受けられ, アルゴリズ

PC 環境の結果より, CAS 操作を利用した場合は全て, HTM

ムやデータの特徴に合わせて適切な閾値を設定する必要がある

でもほとんどの場合において既存の Mutex を使った実装に対ことが分かった.

して高速化され, 処理全体の時間が最大 19% , 同時実行制御にかかる時間が最大 76% 短縮されたことが分かる. 一部の条件において, HTM を利用した場合の方が Mutex を利用した場合に表 3 (A) Mutex にかかる時間が全体に占める割合 (SV)(%)
アルゴリズムWikipedia

Flickr LiveJournal

Pokec

PageRank

14.948 19.839

17.039 19.521

比べて処理全体の時間が増加する結果となった. 表 4 と照らし

SSSP

11.623 13.761

11.222 12.970

合わせると, 元々の Mutex による同時実行制御コストが処理全

heavy

9.710 12.186

11.153 12.252体に対して小さい計算の場合は性能の向上があまり望めず, 場
合によっては性能が劣化する傾向が見受けられた. また, 横軸が CPU 使用率を表すヒストグラムを 図 3 に示す. 図 3(a) と表 4 (A) Mutex 比の同時実行制御にかかる時間 (SV)(%)

図 3(b) を比較すると, 提案手法が既存手法に比べて最も CPU

アルゴリズム手法

使用率が高く理想的な状態を表す階級である Ideal の占める割

PageRank

HTM

SSSP
heavy

CAS

合が増加したことから, 並列環境を活かすことができたと分かる. PC 環境においても同様の傾向が見られた.

(B) データセットを Wikipedia, アルゴリズムを PageRankに固定した環境で, コア数を制限することで並列度を変化させた

Wikipedia

Flickr LiveJournal

Pokec

94.008 73.696

46.680 52.050

CAS65.779 59.451

58.294 43.142

HTM

103.755 57.188

51.183 60.815

CAS81.217 39.549

64.143 54.082

HTM

190.068 84.201

66.535 55.249

97.568 60.363

94.153 75.727時の性能比較を 図 4 に示す. 図 4 より, 常に HTM が Mutex
に対して優勢であることが分かった. その中での傾向として,並列度が上がることで HTM の性能は確かに向上しているものの, HTM と Mutex の差異の減少が見受けられる. これは,

HTM は並列度が高くなるとデータの競合が発生してしまい,
投機実行に失敗する確率が増加するためと考えられる. 図 1(a)の結果を踏まえると, 並列度を更に上げるとやがて実行性能が悪化する可能性があるため, 高並列環境においては 3.1 節 で提案したような最適化の必要性が再認された.

5. 関 連 研 究
5. 1 単一マシン用グラフ処理エンジン
GraphChi [2] を参考に設計された単一マシン用グラフ処理エンジンとして, TurboGraph [3] や VENUS [4], GridGraph [5],NXGraph [6] などが挙げられる.
TurboGraph はデータの保存単位を細分化し, Pin-and-Slideという方法でデータのロードを行うことで, IO と CPU のオー(C) データセットを Wikipedia, アルゴリズムを PageRankに固定した環境で, 既存手法と 実験 (A) での提案手法に加え,いくつかの閾値における仮想ノードを用いた手法の性能比較と（注 4）：Intel VTune Amplifier 2016:

us/intel-vtune-amplifier-xe

https://software.intel.com/en-

(a) PageRank(b) SSSP(c) heavy

図 2 (A) 同時実行制御方法のデータセットごとの性能比較 (SV)をオーバーラップさせることで, IO と CPU を効率的に利用している.

GridGraph は, 頂点データを 1 次元に, 辺データを始点と終点に基づく 2 次元に分割して管理することで, 従来の vertex-

centric や edge-centric な手法と比べ, 1 イテレーション当たり(a) 既存手法の辺データのロード回数を 1 回限りに抑えている. また, グラ
フ処理のスケジューリングをユーザ定義のアルゴリズムに合わせて選択できるようにすることで, 不必要な辺データのロードを防ぎ, 高速化を行っている.

NXGraph は, 辺の始点と終点を考慮する Destination-Sorted(b) 提案手法の一例 (HTM)
図 3 (A) CPU 使用率ヒストグラムの一例 (SV)

（注 4）

灰: Idle, 赤: Poor, 黄: Ok, 緑: Ideal

Sub-Shard という手法を用いることで, 限られたメモリ空間でグラフの局所性を利用し, 更新処理時に発生する書き込みによるデータの競合発生率を抑えている. また, グラフデータのサイズと利用可能なメモリサイズに基いて更新処理に Single-Phase

Updating と Double-Phase Updating, Mixed-Phase Updating の 3 種類を使い分けることでディスクアクセスを減らしている.

5. 2 Hardware Transactional Memory の応用
HTM は古くから提案されてきたが [8], 近年ようやく商用の
図 4 (B) 同時実行制御方法ごと

図 5 (C) HTM と仮想ノードをのコア数と性能の関係 (SV)用いた手法の性能とメモリ
使用量 (SV)

バーラップ効率を上げている. Pin-and-Slide では, ページと呼ばれる単位でメモリにロード (Pin) し, 次のページのロードをしている間にロード済みのページ内のデータに関する更新処理を行う. ロードが終わり次第更新処理に移り (Slide), 別スレッ
ドで次のページのロードを行う. このように, 処理を細分化することで, ディスク IO 待ち / 更新処理待ち を減らしている.
また, ディスクとして SSD を使うことで, ディスク IO のレイ
テンシを減らしている.

VENUS は, 多くのグラフ処理アルゴリズムにおいて, 隣接
頂点から伝搬させる値を計算する際に, 伝搬値を一時的に対象頂点間の辺の値として保持する必要が無いことに着目している.
対象頂点の更新処理に隣接頂点の値を直接利用することで, 中間データをメモリ上に置く必要性やディスクに書き出す必要性をなく, 処理時間の短縮を行っている. しかしながら, 辺に中間データを保持させる必要がアルゴリズム, 例えば 2 ホップ以上
先の頂点の値を利用するようなアルゴリズム, を実行することができないという制限がある. 辺データの読み出しと更新処理

プロセッサにも実装され, 普及し始めたばかりの若い技術である. しかしながら, 同時実行制御は分散処理やデータベース等,広い分野で重要な技術であるため, その有用性は注目を集めており, 本稿で提案した単一マシングラフ処理エンジンだけでな
く, 既に分散処理におけるメッセージパッシング [?] やインメモ
リデータベース [25] などにも応用されている. これらの既に応用化が進んでいる分野の特徴として, 大部分は並列的に行われるものの, 同時実行制御が真に必要となるような複数アクセスが発生する割合が低い処理を扱っているということが挙げられる. データの競合が少ない限り, 同時実行制御としてのオーバー
ヘッドが非常に少ない, という HTM の特性を活かすことが重要であると分かる.

5. 3 MapReduce との類似点
本稿で提案した仮想ノードへの部分集約に類似する概念として, 分散処理モデルである MapReduce [26] における combinerによる部分集約が挙げられる. MapReduce は基本的なフロー
は, 値を mapper で処理してからネットワーク越しで reducerに渡し, 集約するというものである. そこに combiner を導入
し, reducer での集約の前に mapper のノード上で部分的に集約をすることで通信量を削減して高速化を図ることができる [27].

提案手法では同時実行制御を減らすため, MapReduce では通
信量を減らすため, と, 部分集約を利用する目的は異なるが, どちらも分割統治法の集約ストラテジを最適化することで, ボト
ルネックになり得る特定の処理を減らしている.

6. ま と め
本稿では, 単一マシンメニーコア環境でのグラフ処理エンジンにおいて, 同時実行制御方法を従来の Mutex から CAS 操作
や HTM に置き換えることで高速化を行った. 更に, GAS の特性を考慮し, HTM とスレッドローカル仮想ノードを組み合わせる高速な処理手法を提案した. また, 提案手法を GraphChiに実装し, 性能評価を行った. 同時実行制御に Mutex を用いた実装と比較して, CAS 操作に置き換えることで処理全体にかかる時間を最大約 19%, 同時実行制御にかかる時間を最大約 76%,

HTM を用いた手法に置き換えることで, 処理全体にかかる時間を最大約 10% , 同時実行制御にかかる時間を最大約 53% 短
縮することに成功した. また, HTM とスレッドローカル仮想
ノードを用いた最適化を行うことにより, 処理全体にかかる時
間を更に最大約 8% 短縮することに成功した.

謝

辞

本研究の実験環境を提供して頂いたヒューレット・パッカード社に深謝申し上げます.

文

献[1] Facebook. Facebook company info. http://newsroom.fb.
com/company-info/.
[2] Aapo Kyrola, Guy E Blelloch, and Carlos Guestrin.
GraphChi: Large-scale graph computation on just a pc. In
Proceedings of OSDI, Vol. 12, pp. 31–46, October 2012.
[3] Wook-Shin Han, Sangyeon Lee, Kyungyeol Park, JeongHoon Lee, Min-Soo Kim, Jinha Kim, and Hwanjo Yu. TurboGraph: a fast parallel graph engine handling billion-scalegraphs in a single pc. In Proceedings of SIGKDD, pp. 77–85.
ACM, August 2013.
[4] Jiefeng Cheng, Qin Liu, Zhenguo Li, Wei Fan, John CS Lui,and Cheng He. VENUS: Vertex-centric streamlined graphcomputation on a single pc. Proceedings of ICDE, April
2015.
[5] Xiaowei Zhu, Wentao Han, and Wenguang Chen. GridGraph: Large-scale graph processing on a single machineusing 2-level hierarchical partitioning. In Proceedings of the
USENIX ATC, pp. 375–386, July 2015.
[6] Yuze Chi, Guohao Dai, Yu Wang, Guangyu Sun, Guoliang
Li, and Huazhong Yang. NXgraph: An eﬃcient graph processing system on a single machine. Proceedings of ICDE,May 2016.
[7] Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg,
Christos Faloutsos, and Zoubin Ghahramani. Kronecker
graphs: An approach to modeling networks. Proceedingsof WAPA, Vol. 11, pp. 985–1042, September 2010.
[8] Maurice Herlihy and J Eliot B Moss. Transactional memory: Architectural support for lock-free data structures,Vol. 21. ACM, 1993.
[9] Joseph E. Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin. PowerGraph: Distributed graphparallel computation on natural graphs. In Proceedings of
OSDI, pp. 17–30, Hollywood, CA, October 2012. USENIX.

[10] Yucheng Low, Joseph E Gonzalez, Aapo Kyrola, Danny
Bickson, Carlos E Guestrin, and Joseph Hellerstein.
GraphLab: A new framework for parallel machine learning.
Proceedings of UAI, July 2014.
[11] Per Hammarlund, Rajesh Kumar, Randy B Osborne, Ravi
Rajwar, Ronak Singhal, Reynold D’Sa, Robert Chappell,
Shiv Kaushik, Srinivas Chennupaty, Stephan Jourdan, et al.
Haswell: The fourth-generation intel core processor. Proceedings of IEEE, No. 2, pp. 6–20, December 2014.
[12] Ruud Haring, Martin Ohmacht, Thomas W Fox, Michael K
Gschwind, David L Satterfield, Krishnan Sugavanam,Paul W Coteus, Philip Heidelberger, Matthias A Blumrich,
Robert W Wisniewski, et al. The IBM Blue Gene/Q compute chip. Proceedings of IEEE, Vol. 32, No. 2, pp. 48–60,
December 2012.
[13] B Sinharoy, JA Van Norstrand, RJ Eickemeyer, HQ Le,
J Leenstra, DQ Nguyen, B Konigsburg, K Ward,
MD Brown, JE Moreira, et al. IBM POWER8 processor
core microarchitecture. IBM Journal of Research and Development, Vol. 59, No. 1, pp. 2–1, January 2015.
[14] C Kevin Shum, Fadi Busaba, and Christian Jacobi. IBMzEC12: The third-generation high-frequency mainframe microprocessor. Proceedings of IEEE, No. 2, pp. 38–47, June
2013.
[15] Chi Cao Minh, JaeWoong Chung, Christos Kozyrakis, andKunle Olukotun. STAMP: Stanford transactional applications for multi-processing. In Proceedings of IISWC, pp.
35–46. IEEE, September 2008.
[16] Takuya Nakaike, Rei Odaira, Matthew Gaudet, Maged M
Michael, and Hisanobu Tomari. Quantitative comparison of
hardware transactional memory for Blue Gene/Q, zEnterprise EC12, Intel Core, and POWER8. In Proceedings of
ISCA, pp. 144–157. ACM, June 2015.
[17] Pokec network dataset – KONECT, May 2015.
[18] Lubos Takac and Michal Zabovsky. Data analysis in publicsocial networks. In International Scientific Conference andInternational Workshop Present DTI, May 2012.
[19] Flickr network dataset – KONECT, May 2015.
[20] Alan Mislove, Hema Swetha Koppula, Krishna P. Gummadi, Peter Druschel, and Bobby Bhattacharjee. Growthof the Flickr social network. In Proceedings of COSN, pp.
25–30, March 2008.
[21] LiveJournal network dataset – KONECT, May 2015.
[22] Jure Leskovec, Kevin J. Lang, Anirban Dasgupta, andMichael W. Mahoney. Statistical properties of community
structure in large social and information networks. In Proceedings of WWW, pp. 695–704, April 2008.
[23] Wikipedia, English network dataset – KONECT, May 2015.
[24] Sren Auer, Christian Bizer, Georgi Kobilarov, Jens
Lehmann, Richard Cyganiak, and Zachary Ives. DBpedia:
A nucleus for a web of open data. In Proceedings of ISWC,
pp. 722–735, October 2008.
[25] Viktor Leis, Alfons Kemper, and Tobias Neumann. Exploiting hardware transactional memory in main-memory
databases. In Proceedings of ICDE, pp. 580–591. IEEE,
March 2014.
[26] Jeﬀrey Dean and Sanjay Ghemawat. MapReduce: simplified data processing on large clusters. Proceedings of ACM,
Vol. 51, No. 1, pp. 107–113, March 2008.
[27] Jimmy Lin and Chris Dyer. Data-intensive text processing
with mapreduce. Synthesis Lectures on Human Language
Technologies, Vol. 3, No. 1, pp. 1–177, 2010.