DEIM Forum 2013 E8–1

SIMD 命令を用いたグラフクラスタリングの高速化
塩川 浩昭†

山室健†

藤原 靖宏†

鬼塚真†† NTT ソフトウェアイノベーションセンタ 〒 180–8585 東京都武蔵野市緑町 3–9–11
E-mail: †{shiokawa.hiroaki,yamamuro.takeshi,fujiwara.yasuhiro,onizuka.makoto}@lab.ntt.co.jp
あらまし

大規模グラフデータに対して CPU 特性を考慮した高速なクラスタリング手法を提案する．グラフデータ

に対するクラスタリング手法として Newman 法や CNM 法，BGLL 法などが提案されてきたが，これらの手法を大規
模なグラフデータに適用した場合，データのランダムアクセスと実行命令数の増大に伴い参照効率と実行効率の悪化が課題になることが判明した．そこで提案手法では，モジュラリティに基づくグラフクラスタリングに対して，CPUのキャッシュヒット率向上を考慮したデータ構造の適用，さらに近年注目されている CPU 内の SIMD 命令を活用することで従来手法の課題を解決する．
キーワード

グラフ，クラスタリング，並列化，SIMD

1. は じ め に年の研究 [1, 2, 3, 4, 5] では，高い Modularity の値を高速に求める課題となる．しかし，Modularity 値の最大化は NP 困難

グラフ構造はデータをノードとエッジで表現した基本的なであることから，Modularity を用いたクラスタリング手法でデータ構造であり，情報推薦や情報検索，科学データ分析など

は高速にかつ可能な限り高い Modularity の値をいかにして求の様々な分野で利用されている．特に近年では，数億ノードか

めるかという点が重要な研究課題となっている．

ら構成される大規模なグラフ構造が登場し，このようなデータ

その中でも，Blondel らによる BGLL [5] は，数億ノード規模に対する高速な解析処理技術への需要が高まっている．例えば，のグラフ構造に対して，高速かつ高い Modularity の値を示す

Facebook では 2012 年に 1ヶ月当たりのアクティブユーザ数が手法として知られている．BGLL では，2 つのフェーズからなる

10 億人，また Twitter では一日当たりの投稿数が 3 億 4000 万

パスを繰り返すことによりクラスタリングを行う．第 1 フェーを突破したと報告されている．このように，大規模なグラフ構

ズでは，グラフ構造を構成する各ノードがそれぞれ別のクラス

造は現実に存在し，今後もその規模をさらに増大させていくこ

タである状態から開始する．任意の順にノードを選択し，選択とが考えられ，これらのグラフ構造に対する高速な解析手法はしたノードに対して隣接するノードの中から最も Modularity

将来的に必要不可欠な技術となってくると言える．

を向上させる隣接ノードを 1 つ選択する．同一のクラスタとみグラフ構造解析のひとつとして，クラスタリング手法が挙げなす操作を，Modularity の値が向上する限り繰り返す．これられる．グラフ構造には，クラスタと呼ばれる相互に密な接続に続く第 2 フェーズでは，同一のクラスタと判定された全てのを有する部分ノード集合が存在する．例えば，Web グラフでは

ノードとエッジを 1 ノードへ集約する操作を行う．Modularity

トピックや関心の近いページ集合が互いにリンクすることで，の値が向上する限り，これら 2 つのフェーズからなるパスを反トピックや関心の類似したページ群がコミュニティを形成する

復しクラスタの抽出を行う．従来手法 [2, 3, 4] ではクラスタ同傾向にある．このようにグラフ構造中のクラスタは互いに共士の統合を行う際に，クラスタに含まれる全てのノードとエッ通した性質を持つことから，グラフ構造の理解や様々なアプリ

ジに対し，Modularity の向上量を計算する必要があった．こケーションに利用され，非常に重要な要素技術となっている．

れに対し，BGLL では収束した処理結果を 1 ノードへ集約す

このような背景からこれまで様々なクラスタリング手法の研究ることで，処理に必要となるノードとエッジの参照数を削減さが行われてきた．

せることに成功している．また BGLL は，任意の順に選択さModularity [1] を用いた手法は大規模なグラフ構造を高速にれたノードが，それぞれが隣接するノードに対してのみ統合のクラスタリングする手法として注目を集めている手法の一つ

可能性を検証する．ゆえに，抽出されるクラスタサイズの偏りである．Modularity は処理対象のグラフ構造をランダムグラを防ぐことができ，その結果高い Modularity の値を示すことフとみなしてモデル化し構築した指標であり，グラフ構造ががわかっている．BGLL は 1 億ノード規模のグラフデータにランダムグラフから離れるほど良いスコアを示す．すなわち

対して約 2.5 時間程度でクラスタリング処理可能であることがModularity は，よりクラスタ内のエッジが密であり，かつ，クBlondel らによる研究で報告されている [5].

ラスタ間のエッジが疎であるクラスタリング結果であるほど良

本稿では，より大規模な数億〜数十億ノード規模のグラフ構

い Modularity の値を示し，より適切にクラスタを抽出できて造に対する高速なクラスタリングの実現に向け，処理の並列化いることを表す特徴を持つ．ゆえに，Modularity を用いた近による BGLL の高速化手法を提案する．本手法では，BGLL に含まれる Modularity 計算部分に対し，複数の比較処理を CPU集約により，クラスタリング処理におけるノードとエッジの参の 1 サイクルで同時実行することが可能な SIMD 命令を活用す

照数の削減に成功している．BGLL の最悪計算量は知られていることで処理の高速化を行う．さらに，クラスタリング処理時ないが，文献 [5] において従来手法に対する高速性が実験的にに生じるメモリ上のデータアクセスの効率化を実現する，キャッ

示されており，我々の知る限り最も高速にクラスタリング処理

シュヒット率向上に向けたデータ構造を導入し，クラスタリン

が可能な手法である．文献 [5] では，最大で数億ノード規模まグ処理の更なる高速化を図る．SIMD 命令により Modularity

での処理が可能であると報告されている．さらに，BGLL は任計算を並列実行する際に，Modularity 計算の定義式をより単純意の順でノードを選択することで抽出されるクラスタサイズにな命令の組み合わせに置き換え，SIMD 命令の実行数の増加を偏りが生じることを防ぎ，これまで述べた手法の中で最も良い抑制する．本稿では，提案手法のプロトタイプを実装し実デー

Modularity の値を示すことも文献 [5] にて示されている．

タを用いた評価実験を行う．評価実験により，BGLL に対して

本稿はこれらの手法に対し，より大規模なグラフ構造の高速

Modularity の値を同程度に示しつつ，高速に処理可能であるなクラスタリング手法の実現に向け，SIMD 命令とキャッシュ

ことを示す．本稿の構成は以下の通りである．2 節で関連研究

ヒット率向上を考慮した BGLL のさらなる高速化に取り組む．

について述べ，3 節で本研究の前提となる概念と手法について

2. 2 SIMD 命令を用いた高速化説明する．4 節でキャッシュヒットを考慮したデータ構造につ2002 年頃以降，CPU や GPU の SIMD 命令を用いた各種手

いて述べ，5 節で提案手法の詳細を説明する．6 節で提案手法

法の高速化に関する研究は盛んに行われている. グラフクラスの評価を行う．最後に 7 節で本稿のまとめと今後の課題についタリングの高速化に関する従来研究 [10, 11] は存在するが，こて述べる．

れらの研究ではラベル伝搬やランダムウォークに着眼するものである．計算量の大きなこれらの手法に対して，局所的なデー

2. 関 連 研 究

タ並列化を行うことで処理性能の向上とスケーラビリティの確

2. 1 Modularity に基づくクラスタリング保を図っている．しかしながら，これらの手法の計算量は依然

Modularity を用いたクラスタリング手法について様々な研究として大きく，本研究で対象とするような数億〜数十億ノードが行われている．代表的な手法として Girvan–Newman 法 [1]，規模のグラフを対象としたクラスタリングは難しい．これに対Newman 法 [2]，CNM 法 [3]，WT 法 [4]，BGLL [5] などが挙し，Modularity による手法に着目し数億〜数十億ノードからなげられるが，いずれの手法においても本研究で対象とする大規る大規模なデータに対するクラスタリングを行う処理に SIMD

模なグラフ構造を高速に処理することは難しい．

命令を適用したものは本研究がはじめてである．

Girvan らはトップダウンにエッジを間引きグラフを分割する
Girvan–Newman 法 [1] を提案した．グラフ構造全体を 1 つのクラスタとみなし，クラスタ間を横断する可能性の高いエッジ

3. 事 前 準 備
3. 1 クラスタリング指標 Modularity

から順に切り離すことにより小さなクラスタへと分割していく．

本稿で提案するクラスタリング手法では，抽出結果の良さを

エッジを切り離す度に各エッジに付与されたスコアを再計算す示す指標 Modularity を対象とする．そこで，クラスタリング

ることから，エッジが疎なグラフ構造に対してノード数を n と

指標 Modularity について概説する．

3

すると O(n ) の計算量を必要とする．計算量が膨大であるた

Modularity はクラスタ内に含まれたノード間のエッジが密め，1 万ノード規模の処理には適用できないと報告されている．

であり，クラスタ間に存在するエッジが疎となる程良い値を示

Newman は，貪欲法によりボトムアップ式にクラスタを抽出す指標である．クラスタリング手法により取得したクラスタ集

する Newman 法 [2] を提案した．この手法では，各ノードがそ

合を C ，クラスタ i からクラスタ j へ接続されているエッジ

れぞれ別のクラスタである状態から処理を開始し，Modularity

数を eij ，グラフ構造全体に含まれる総エッジ数を m とするとが最も向上するノード対を貪欲法により同一クラスタへと統き，Modularity Q は定義 1 のように定義される．Modularity

合していく．統合させるべきノード対を全探索することから，が負の値を取る場合は Q = 0 とし，常に Modularity Q は

2

エッジが疎なグラフ構造に対してノード数を n とすると O(n )0<= 1 の値を示す．
=Q<の計算量を必要とする．これに対し，Clauset らは Newman 法［定義 1］ Modularity Q

に対してヒープ構造を導入することで高速化する CNM 法 [3]を提案し，計算量 O(n log2 n) を達成した．また，脇田らはクラスタ統合時のクラスタサイズの不均衡による処理速度の低下

Q=

∑
i∈C

{
eii
−
2m

(∑

j∈C eij)2 }2mを指摘し，新たに CNM 法のさらなる高速化を行う WT 法 [4]を提案している．WT 法ではクラスタ統合時に Modularity の3. 2 既存手法：BGLL

向上量をクラスタサイズで正規化するヒューリスティクスを用

本稿では BGLL に対して，キャッシュヒットを考慮したデーいることでクラスタサイズの不均衡を解消する．これらの手法

タ構造の導入と SIMD 命令を用いた並列化の導入により，処理では最大で数百万ノード規模までの処理可能と報告されている．

のさらなる高速化を行う．そこで本節では，既存手法 BGLL に

Blondel らは，Newman 法の高速化手法として BGLL [5] を提案した．BGLL は Modularity の局所最適化とノードの一括

ついて概説する．

BGLL は 2 つのフェーズから構成されるパスを繰り返すこ表 1 BGLL における処理時間と Modularity 向上量の評価
パス

Time(sec)ਸ਼ইख़‫ش‬६
ଂਚ৓ऩ0RGXODULW\ਈి৲

1

2

3

4

5

Modularity 0.669 0.06 0.01 0.01 0.01
ਸ਼パス⼊⼒グラフデータ

6

合計

418.7 3.34 0.17 0.03 0.01 0.01 422.3
0 0.759ਸ਼フェーズ終了時

ਸ਼ইख़‫ش‬६ঀ‫ॻش‬धग़ॵ४भ঳ฐૐ৺




ਸ਼ঃ५



増加する可能性を検証することで，クラスタの統合を行う．こ










てのノードをランダム順に参照し，Modularity 変化量 △Q がの処理は，Modularity 変化量 △Q が増加しなくなるまで継続

されるため，入力されるデータのノード数増加に伴い，第 1 パ

ਸ਼フェーズ終了時‫ق‬ਸ਼パス⼊⼒グラフデータ）

スにおける処理時間は増加することとなる．これにより，より
図 1 BGLL の処理の流れ

大規模なグラフ構造であるほど，第 1 パスにおける処理時間がとでクラスタを抽出する手法である．第 1 フェーズにて，各ノードと隣接するノード間のみにおいて Modularity の値を準最適化し，第 2 フェーズにて，第 1 フェーズで得られた結果を

1 ノードに一括集約する．BGLL は Modularity の値が増加する限り，2 つのフェーズからなるパスを反復する．各フェーズの詳細について以下に説明する．

3. 2. 1 第 1 フェーズ：Modularity の局所最適化
第 1 フェーズではまず，入力されたグラフ構造に対して，任意の順（ランダム順）にノードを選択する．その後，選択されたノードの全隣接ノードに対して，クラスタを統合した際に上昇する Modularity の値 △Q を計算する．一般的に定義 1 で示した Modularity Q を求めるためには，全てのノードとエッジを参照する必要があるため効率的ではない．しかし BGLL では Modularity の変化量にのみ着目し，定義 1 から Modularity
変化量 △Q を導出し，計算の効率化を図っている．2 つのクラ
スタ i と j を統合した際の Modularity 変化量 △Q を定義 5. 1に示す．

{
△Q = 2eij−
2mk∈C eik

2m

)(∑

なる．
具体例を表 1 に示す．表 1 では，ノード数 5,363,260，エッジ
数 79,023,142 から構成されるグラフデータに対して Blondel らが公開している Louvain 法のプログラム（注 1）を適用した際の処理時間と Modularity 値の変化の内訳を示している．表 1 のパスは BGLL を実行した際の反復回数，Time は各パスに消費した処理時間，Modularity は各パスで増加した Modularity の値を表している．表 1 からも分かる通り，BGLL では，第 1 パスにその処理時間の 99%以上を消費している．また Modularity
については，第 2 パス以降では大きな向上は見られないことがわかる．この傾向は，予備実験で使用したデータセットのみならず，他のデータセットにおいても同様に見られるものである．
このことから，我々は BGLL の第一パスを効率化することで，クラスタリング処理全体を大幅に高速化できると考えた．

4. キャッシュヒットを考慮したデータ構造設計
本稿では，グラフ構造 G = (V, E) を隣接リスト表現で扱う．

［定義 2］ Modularity 変化量 △Q(∑

ボトルネックとなり，クラスタリング処理時間の短縮が困難と隣接リスト表現では，各ノード毎にノード u とそのノードに隣k∈C ejk)}2m

接するノード集合 Γ(u) のみをリスト上にして表現したデータ構造であるため，隣接行列表現に対してより空間効率よくデー
タを保持することができる．しかしながら，Modularity による

第 1 フェーズでは，上記の定義に従い △Q を計算し，最もグラフクラスタリングにおいてはメモリ上のデータに対する参Modularity 変化量 △Q が大きくなるノード対を選出する．そ照が頻繁に発生するため，各ノード毎に離散したメモリ番地への後，選出したノード対を同一のクラスタとしてラベル付する．

のアクセスが生じる可能性のある隣接リスト表現はキャッシュ

この処理は Modularity の値が向上しなくなるまで継続する．

ヒット率の低下を招き，参照効率が悪化する可能性がある．

3. 2. 2 第 2 フェーズ：ノードとエッジの一括集約
第 2 フェーズでは，第 1 フェーズで得られた処理結果に対してノードとエッジを一括集約し，処理で扱うグラフ構造のサイ

そこで，本稿では隣接リスト表現をメモリ上において連続した領域に配置することで，データ参照時のキャッシュヒット率を向上させる．本データ構造の概要を図 2 に示す．

ズを縮小する．図 1 に示したように，同一のクラスタに含ま本データ構造は 2 つの連続した配列から構成される．一つはれるノードは，1 つのノードにまとめられる．また，クラスタ

ノード集合を格納した配列 Va ，もう一つは隣接ノード集合を格内に存在するエッジについては，自己ループのエッジ 1 本へ集納した配列 Ea である．まず，配列 Va では，配列の番地をノー約し元のエッジ本数の 2 倍の重みをつける，クラスタ間に存在ドの識別番号とし，その要素として配列の先頭から現在の番地するエッジについては，同一のクラスタ対につきエッジ 1 本にまでに含まれるノードの次数の合計値を格納する．ここで格納集約し，エッジ本数分の重みをつける．第 2 フェーズで生成さした次数は，配列 Ea のインデックスとして利用される．次にれた集約された重み付きグラフ構造は，次回以降のパスで入力

配列 Ea において，配列 Va に格納したノードの順にそれぞれデータとして与えられる．

のノードの隣接ノードを格納する．

3. 2. 3 BGLL の課題
BGLL は，第 1 パスの第 1 フェーズにおいて入力された全（注 1）：https://sites.google.com/site/findcommunities/䝜䞊䝗ŝĚ

Ϭ

ϭ

Ϯ

ϯ

ϰ

ϱ

ϳ

䞉䞉䞉

ϵϵ ϭϬϬ

ܸ௔

Ϭ

ϯ

ϰ

ϳ

ϴ

ϭϯ ϭϰ ϭϳ䞉䞉䞉ϮϮϭ ϮϮϯ

‫ܧ‬௔

ϲ

ィ⟬䝜䞊䝗
^/D䝺䝆䝇䝍ୖ䛻ᘧ䜢ᒎ㛤
^/D
䝺䝆䝇䝍Ă
^/D
䝺䝆䝇䝍ď
^/D
䝺䝆䝇䝍Đ
^/D
䝺䝆䝇䝍Ě

ྛ㞄᥋䝜䞊䝗䛻ᑐ䛧䛶∆䜢ィ⟬ϮϭϬ ϭϱ ϰϭϭ ϰϮ ϴϴϵ䞉䞉䞉ϮϮϭ ϮϮϯ

率良くアクセスすることが可能になる．例えば，あるノード uの隣接ノード集合 Γ(u) を参照する場合を考える．この場合，まず，配列 Va の番地 u にアクセスし，次数の合計値 Va (u) および Va (u + 1) を取得する．この合計値 Va (u) および Va (u + 1)
は，配列 Ea に存在するノード u およびノード u + 1 の隣接ノード集合を格納した領域の先頭番地を指すため，配列 Ea (Va (u))
から Ea (Va (u + 1)) − 1 にアクセスすればノード u の隣接ノード集合 Γ(u) が取得可能である．
例えば図 2 では，ノード 2 に隣接するノード集合を取得する場合を示している．ノード 2 の隣接ノード集合を取得する場合，まず配列 Va から配列 Ea の参照先 Va (2) = 4 を取得する．次に，ノード 2 の持つ次数を取得する．この場合，

Va (3) − Va (2) = 7 − 4 = 3 となり，ノード 2 の持つ次数は 3 である．最後に配列 Ea 中の Ea (3) から Ea (3 + 3)Ea (6) までア
クセスし，ノード 2 の隣接ノード集合 {11, 42, 88} を取得する．
このデータ構造では，データをメモリ上の連続した領域の載せた状態で処理を行うことが可能となるため，キャッシュヒッ
ト率が向上しやすく，メモリ上のデータ参照が頻繁に発生する
グラフクラスタリングにおいてデータアクセスを効率化できると考えられる．

5. SIMD 命令による Modularity 計算
本稿では，複数のデータに対する演算を CPU の 1 サイクる．3. 2 節で示したように，既存手法 BGLL は各パスの第一フェーズにおいて，全てのノードを走査する．そして，それぞれのノードの隣接ノード集合に対して Modularity 変化量 △Q

ଵ

ଵ

ଶ

ଷ

ସ

ଵ

∆ଵଶ

∆ଵଷ

∆ଵସ

∆ଵହ

に対して SIMD 命令を用いて並列に Modularity 変化量を計算する．提案手法では，BGLL と同様に任意の順にノード u を選択する．次に，選択されたノード u の隣接ノード集合 Γ(u) を

4. 節に示した手順で取得する．そして，取得した隣接ノード集
合 Γ(u) に対して，SIMD 命令を用いて並列に Modularity 変化量の計算を実行する．
この際に，従来手法では定義で示した，Modularity 変化量△Q を計算する必要がある．このとき，各計算に必要な eij や∑∑k∈C eik ，k∈C ejk が事前に求められていた場合，SIMD 命令を用いた △Q の演算には下記の 6 つの演算が必要となる．

•
•
•
•
•
•

eij と 2m の商∑k∈C eik と 2m の商∑k∈C ejk と 2m の商∑∑k∈C eik /2m とk∈C eik /2m の積∑∑
eij /2m と ( k∈C eik /2m)( k∈C eik /2m) の差∑∑
2 と eij /2m − ( k∈C eik /2m)( k∈C eik /2m) の積

しかしながら，この計算で本来求める必要がある事項は，Γ(u)に含まれるノードのうち Modularity 変化量 △Q を最大化し得るノードの発見である．すなわち，△Q に示した計算を全て実行する必要はなく，Γ(u) に含まれる全てのノードが △Q に関する相対的な順位が求まれば良いと考えられる．そこで本稿では Modularity 変化量 △Qij をより容易な計算の組合せに変換
した新たな Modularity 変化量 △Q′ij を以下に定義する．
［定義 3］（簡略 Modularity 変化量 △Q′ij ）△Q′ij = 2meij −ルで同時実行することが可能な SIMD 命令を活用することで，Modularity によるクラスタリングをデータ並列化し高速化すଵс

データを連続領域に格納しつつ，それぞれのデータに対して効ଵଵଵ

図 3 SIMD 命令による並列化の概要

図 2 キャッシュヒットを考慮したデータ構造

このようにノードとエッジを格納することにより，全ての

2

ଵସ

с

䝜䞊䝗Ϯ䛾ᣢ䛴㞄᥋䝜䞊䝗㞟ྜ

2

ଵଷ

с

௜௝ ∑௞ ௜௞ ∑௞ ௝௞

2
2 2

2

ଵଶ

с

∆  2

2

∑

eik

k∈C

∑

ejk .

k∈C

定義 3 で定義した Modularity 変化量 △Q′ij から下記の補題が導出される．
［補題 1］（△Q′ij と △Qij の大小関係） 簡略 Modularity 変化を計算し，△Q を最大化するノードとクラスタの併合を繰り返量 △Q′ij は，Modularity 変化量 △Qij によって得られる値のすことで最終的なクラスタを抽出する．しかしながら，BGLL

大小関係と等価な大小関係を示す．

ではこの処理を全てのエッジに対して複数回イテレーションする必要があり，クラスタリングの処理時間に対して支配的となり，その性能を劣化させる原因となっている．
そこで，本稿では BGLL の第一フェーズにおける，各ノードの Modularity 変化量 △Q の計算に対して SIMD 命令を用いたデータ並列化を導入し，その処理時間を短縮する．提案手法における SIMD 命令を用いたデータ並列化の概要を図 3 に示す．

5. 1 Modularity 変化量の並列計算
まず，任意のノードが与えられた際にその全ての隣接ノード

証明 定義 5. 1 より，
{
(∑
)(∑
)}
eij
k∈C eikk∈C ejk△Qij = 2
−
2m
2m
2m
2
∑
∑
4m
△Qij = 2meij −
eik
ejk .
2
k∈C

したがって，△Q′ij = 2meij −

∑
k∈C

k∈C

eik

∑

ejk ,

k∈C

となり，△Q′ij は，△Qij と相対的に等価となる．

□

△Q′ij を用いることで，Modularity 変化量 △Q では SIMD 命

なるようなアライメントを操作により取得することで，ノード

令上 6 回の演算が必要であったものを，下記の通り 3 回の演算

u に対して Modularity 変化量を最大化する隣接ノードを取得

で相対的に等価に求めることが可能になる．

する．

•
•
•

eij と 2m の積∑∑k∈C eik とk∈C ejk の積∑∑
2meij と k∈C eik k∈C ejk の差

6. 評 価 実 験
提案手法の有効性を評価するために，Blondel らによる BGLL

提案手法では，SIMD レジスタ上において △Q′ij を用いて並列に対して，本提案手法を適用し比較実験を行う．本実験で下記に計算を行うことにより，従来の BGLL よりも少ない CPU サの実データを利用し評価を行った．

•

イクルでクラスタを求めることができる．

Live [12] （注 2）：LiveJournal と呼ばれる 1999 年に開始さ

5. 2 Modularity 変化量最大化ノードの選択れた SNS のユーザの友達関係からなるネットワーク．ノード数

前述した Modularity 変化量からその値を最大化する隣接ノー

は 5,363,260 であり，エッジ数は 79,023,142 である．

ドを SIMD 命令を用いて取得する．本手法では Modularity 変•

uk-2005（注 3）：2005 年にクロールした uk ドメインの Web

化量を最大化するノードの取得を行うために，4 つの SIMD レジ

グラフのスナップショット．ノード数は 39,459,925 であり，エッスタ，reg id，reg result，reg max id，reg max，reg mask

ジ数は 936,364,282 である．

を使用する．reg id は 5. 1 節に示した手順によって計算対象•

webbase-2001 [12] （注 4）：WebBase クローラ（注 5）によってとなっている隣接ノード集合の ID を格納した SIMD レジス

2001 年にクロールされた Web グラフのスナップショット．ノータ，reg result は reg id に対応した Modularity 変化量の計算

ド数は 118,142,155 であり，エッジ数は 1,019,903,190 である．

結果が格納された SIMD レジスタ，reg max id は Modularity

これらのデータセットの次数分布を図 5 に示す．

変化量を最大化する可能性のある隣接ノード ID が格納された

ま た ，本 実 験 で は ，DynamIc Graph Generator (DIGG)

SIMD レジスタ，reg max はノード u と reg max id に存在す

（注 6）

る隣接ノードによって得られる Modularity 変化量を格納した生成するグラフのノード数とグラフ中に含まれるエッジの偏り

SIMD レジスタ，そして reg mask は最大化ノードを取得するを表すパラメータ β の値を指定することで，グラフデータを生ために利用するマスク用の SIMD レジスタである．

成することが可能である．β の値は大きな値を持つほど，ノーを用いて，人工のグラフデータを生成した．DIGG では，

まず，5. 1 節に示した手順によって，ノード u の隣接ノードド間の次数に偏りが生じ，小さな値を持つほどノード間で均一集合 Γ(u) のうち，1 つの SIMD レジスタにデータ入力可能な分な次数をもつグラフデータが生成される．本実験では，DIGGの隣接ノード部分集合 reg id に対する Modularity 変化量計算により生成したノード数を 10,000 ノードから 10,000,000 ノーが終了した場合を考える．この時，reg result には各隣接ノードまで 10 倍ずつ変化させた 4 つのグラフデータを利用し評

ドに対する Modularity 変化量の値が入力されている．次に図価を行った．また，DIGG で生成した全てのグラフデータは

4 のように，reg result と reg max の 2 つの SIMD レジスタ

β = 2.0 と設定されている．本実験では，これらのデータセッ

間の大小比較を行い，reg result の方が大きな値を持っているトに対して，クラスタリング処理が終了するまで処理を行った

SIMD レジスタ上のアライメントのビットを全て 1，そうでな際の処理時間を示し，比較を行う．本実験には CPU が Intelいアライメントのビットを全て 0 とし，その結果を reg mask

Xeon Quad–Core L5640，メモリが 144GB の Linux サーバをで保持する．

利用した．また，本実験で使用した SIMD レジスタのサイズは128bit であり，計算に利用するノード ID やエッジ数は 32bitƕƈƊƂƕƈƖƘƏƗ









ƕƈƊƂƐƄƛ









‫ڃ‬

‫ڃ‬

‫ڃ‬

‫ڃ‬





ƕƈƊƂƐƄƖƎ

 

のデータ型として扱った．

6. 1 実データによる評価
本実験では，前節で述べた実データに対して提案手法と BGLLの処理速度，処理制度を比較する．

図 4 reg result と reg max から reg mask の作成

図 6 に処理速度の比較結果を示す．図 6 の Original，Cache，Cache+SIMD はそれぞれ，BGLL，キャッシュを考慮したデー
reg mask 取 得 後 ，こ の マ ス ク の 値 と reg id お よ び

タ構造のみを用いた BGLL，キャッシュを考慮したデータ構造

reg max id を用いて，Modularity 変化量が大きくなったノーと SIMD による並列化を行った BGLL を示している．図 6 か

ド ID を下記のように抽出する．

らわかるように，Cache および，Cache+SIMD は全てのデー

reg max id = (!reg mask & reg max id) | (reg mask & reg id)

タセットにおいて，Original よりも高速に処理できていることがわかる．Cache は Original に対して約 5〜8 倍程度高速

ノード u に対して全ての Γ(u) に対して処理が終了するまで，上記の手続きを繰り返し，reg max id および，reg max（注 2）：http://law.di.unimi.it/webdata/ljournal-2008/に Modularity 変化量を最大化する可能性のある隣接ノードの（注 3）：http://law.di.unimi.it/webdata/uk-2005/

ID 及び Modularity 変化量を更新し保持し続ける．Modularity
変化量の計算が終了後，reg max id から reg max が最大値と（注 4）：http://law.di.unimi.it/webdata/webbase-2001/（注 5）：http://diglib.stanford.edu:8091/~testbed/doc2/WebBase/（注 6）：http://digg.cs.tufts.edu/

uk-2005

webbase-2001
107

106

106

106

105

105

105

4

10

3

10

Frequency

107

Frequency

Frequency

Live
107

4

10

3

10

104
103

102

102

102

101

101

101

100
100

100
100

101

102
103
104
105
Number of degrees for each node

106

107

101

102
103
104
105
Number of degrees for each node

106

100
100

107

101

102
103
104
105
Number of degrees for each node

106

107

図 5 各データセットの次数分布 (両対数グラフ)化に成功している．また，Cache+SIMD は，いずれのデータ

105

セットに対しても Cache に対して約 4 倍の高速化に成功して
104

Modularity 計算部分の並列化上限値は 4 である．図 6 の結果
はその並列化の上限値に達した結果となっている．このような結果が得られた理由として，キャッシュを考慮したデータ構造の導入が挙げられる．従来の BGLL では，大量のノードとエッWall clock time [sec]いる．本実験で用いた実験環境では SIMD レジスタのサイズ

128bit に対して 32bit のデータ型を利用した実装を行ったため，

Cache+SIMD
Cache
Original

103

102

101

100

Live

ジに対する参照と Modularity 計算の両方に計算コストが生じ
図6ていたが，本稿ではキャッシュを考慮したデータ構造を導入したことによりノードとエッジの参照コストを削減することに成uk-2005

webbase-2001

実データにより実行速度の比較
表 2 Modularity 値の比較

功している．そのため，BGLL のボトルネックが参照と演算のLive

2 つから演算のみにシフトし，演算部分の並列化による高速化

Proposed 0.755

0.977

0.980

が処理全体に寄与する割合が大きくなっているからだと考察で

BGLL

0.979

0.981

0.754

uk-2005 webbase-2001

きる．
また図 6 では，特に webbase-2001 のようにノード数やエッり，ノード数が 10,000 ノードや 100,000 ノード程度の時にはジ数が多く，次数の分布が広いデータセットに対してより高い提案手法 (Cache+SIMD) と BGLL はほぼ同程度の処理時間を高速化性能を示していることがわかる．これは，SIMD 演算要している．これはデータの規模が小さいことにより，グラフ

を用いて Modularity 変化量の計算を行う際に，SIMD レジス

全体に占める次数の大きなノードが少なく，並列化による高速

タ上に展開できるノード数の上限を超えるような次数を持つ化の効率が低下していることが理由として考えられる．しかしノードが多く存在する場合に，SIMD 命令による並列化されながら，1,000,000 ノードや 10,000,000 ノード規模のより大きた Modularity 計算が効果的に実行できるからだと考えられる．

なデータセットに対してはいずれのデータセットに対しても約

このような場合，SIMD レジスタの領域を残すことなくノード

3 倍から 4 倍程度の高速化性能を示していることが図 7 よりわが展開されやすくなるため，1 回の CPU サイクルで同時に計かる．この理由は 6. 1 節で述べた理由と同様に，規模の大きな算が可能となる隣接ノードの数が増加しやすくなる．ゆえに，

データセットになるほど，大きな次数を有するノードがグラフ

webbase-2001 や uk-2005 のようなエッジ数が多く，かつ，広全体に占める割合が大きくなり，SIMD 命令による Modularity

く分布したグラフデータである程，高速化しやくすなる傾向に

計算によって得られる計算の並列度が高くなりやすくなるかあると考えられる．

らだと考えられる．これより提案手法は，よりノード数やエッ次に表 2 に提案手法 (Cache+SIMD) と BGLL によるクラジ数が比較的大きなグラフデータに対して，従来手法である

スタリング結果の Modularity 値を比較した結果を示す．表 2

BGLL よりも約 3 倍から約 4 倍程度高速に処理可能であるとからわかるように，いずれのデータセットに対してもほぼ同考えられる．

程度の Modularity 値を示していることがわかる．提案手法はデータ構造の変更と SIMD による並列化を行なっているものの7. お わ り に

BGLL 法と本質的に同様の処理を行う手法である．ゆえに表 2

本稿では，グラフデータに対する高速なクラスタリングの実にも示されたように，最終的に得られるクラスタリング結果は現に向けた，SIMD 命令を用いたグラフクラスタリングの並列

BGLL と同程度のものが得られる．

化手法を提案した．本稿ではまず，既存のクラスタリング手法

6. 2 人工データによる評価

である BGLL のボトルネックが処理の第 1 パスにあることを本実験では，次数の分布傾向を示す DIGG のパラメータ β

明らかにした．そして本手法では，第 1 パスの計算時間を短縮

を 2.0 に固定し，ノード数が増加した時の本手法と BGLL のするために，複数の命令を 1 つの CPU サイクルで実行可能なスケーラビリティを評価する．図 7 に実験結果を示す．図 7 よ討を進める．

Proposed
BGLLb ) グラフデータの特性による性能の評価

102

Wall clock time [s]本稿では，SIMD 命令を用いたグラフクラスタリングの並列
101化の初期検討として，3 つの実データと 4 つの人工データを用いた性能の評価を行った．本稿の評価結果より，次数の分布の010

傾向や平均エッジ数などに依存して処理の並列度が影響を受け10-1

る可能性が考えられる．今後の課題として，ノードの計算順序
10-2
104

105

106

107

Number of vertices

や，グラフデータの傾向に即した並列化手法の検討を行う必要がある．

図 7 ノード数の変化による処理速度の比較
文

SIMD 命令をクラスタリングの Modularity 計算部に適用することによる計算時間を短縮し，メモリ上のデータ参照に対するキャッシュヒット率向上を目的としたデータ構造および索引構
造を導入することでデータアクセスを効率化した．本稿では，

128bit の SIMD レジスタを利用して実データセット及び人工
データセットに対して計算速度の評価を行い，数百万以上のノードを持つグラフデータに対しては高速化の理論上限値である 3 倍から 4 倍程度の高速化が可能であることを確認した．本手法は，SIMD レジスタのサイズの大きさに伴い，その処理の並列度を増加させることが可能であり，将来普及する可能性のあるより大きな SIMD レジスタを搭載した計算機においてさらなる高速化が期待できる．
本研究の今後の課題として次の点が挙げられる．

a ) 並列度の向上
本稿の評価実験で示したように，SIMD 命令による並列化はキャッシュを考慮したデータ構造と組み合わせることにより，並列化上限に近い高速化倍率を得られることがわかっている．そこで本研究ではこの特性を利用して，SIMD レジスタ上での並列化上限を向上させることによる本手法のさらなる高速化を検討する．具体的な方針として下記の 2 つのアプローチを検討している．

i ) ハードウェアによるアプローチ
本実験で用いた CPU の SIMD レジスタのサイズは 128bitであった．しかしながら，近年発売されている各種ハードウェ
アには SIMD レジスタが 256bit のものや 512bit のものが存在する．今後はこれらのハードウェアを利用したさらなる並列度の向上を検討する．

ii ) データ圧縮による並列度の向上
本稿ではデータの圧縮などは考慮せず，SIMD レジスタ上にノードを展開し Modularity 変化量の計算を行った．そのため，

SIMD 命令による Modularity 変化量計算の並列度は SIMD レ
ジスタのサイズと各ノード ID や各ノードの持つ次数のデータ型に依存して決定してしまう．例えば，本稿の評価実験では128bit の SIMD レジスタに対し 32bit のデータ型を利用した
ため 4 並列が理論上現値であった．これに対し，ノード ID や各ノードの次数に対して圧縮を行うことで SIMD レジスタ上に展開可能なノード数の数を増やすことが可能になり，さらなる高速化が期待できる．本研究では，今後 SIMD レジスタ上での並列度向上を目的とした，グラフデータの圧縮技術について検献[1] M. E. J. Newman and M. Girvan. Finding and evaluating
community structure in networks. Phys. Rev. E, Vol. 69, p.
026113, Feb 2004.
[2] M. E. J. Newman. Fast algorithm for detecting community
structure in networks. Phys. Rev. E, Vol. 69, p. 066133, Jun
2004.
[3] Aaron Clauset, M. E. J. Newman, and Cristopher Moore.
Finding community structure in very large networks. Phys.
Rev. E, Vol. 70, p. 066111, Dec 2004.
[4] Ken Wakita and Toshiyuki Tsurumi. Finding community
structure in mega-scale social networks. In Proceedings ofthe 16th International Conference on World Wide Web,WWW 2007, pp. 1275–1276, 5 2007.
[5] Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities
in large networks. Journal of Statistical Mechanics: Theory
and Experiment, Vol. 2008, p. P10008, October 2008.
[6] Xianchao Zhang, Liang Wang, Yueting Li, and Wenxin
Liang. Extracting local community structure from local
cores. In DASFAA Workshops, pp. 287–298, 4 2011.
[7] Pasquale De Meo, Emilio Ferrara, Giacomo Fiumara, andAlessandro Provetti. Generalized louvain method for community detection in large networks. In Intelligent Systems
Design and Applications, pp. 88–93, 11 2011.
[8] Qi Ye, Bin Wu, Zhixiong Zhao, and Bai Wang. Detecting link communities in massive networks. In Advances in
Social Network Analysis and Mining, pp. 71–78, 7 2011.
[9] Nam P. Nguyen, Thang N. Dinh, Ying Xuan, and My T.
Thai. Adaptive algorithms for detecting community structure in dynamic social networks. In IEEE INFOCOM, pp.
2282–2290, 3 2011.
[10] Di Wu, Tianji Wu, Yi Shan, Yu Wang, Yong He, Ningyi Xu,
and Huazhong Yang. Making human connectome faster:
Gpu acceleration of brain network analysis. In 16th International Conference on Parallel and Distributed Systems,
2010.
[11] Jyothish Soman and Ankur Narang. Fast community detection algorithm with gpus and multicore architectures. In
2011 IEEE International Parallel & Distributed Processing
Symposium, 2011.
[12] Paolo Boldi and Sebastiano Vigna. The WebGraph framework I: Compression techniques. In Proceedings of the Thirteenth International World Wide Web Conference (WWW
2004), pp. 595–601, 5 2004.