p ノードセンター問題の近似解法の GPGPU クラスタを用いた並列実装
2009SE072 稲本 裕貴 2009SE277 竹内 伊吹
指導教員 宮澤 元1

はじめに1．p 個のジェネレータをランダムに選ぶ．

大規模グラフにおけるさまざまな配置問題を解くことは， 2．グラフをジェネレータごとのボロノイ領域に分割する．
現実の道路網における最適配置問題やセンサネットワー
3．各ボロノイ領域で 1 ノードセンターを求める．
クのスケジューリング問題など幅広い分野で役立つ．これ
4．求めた各領域のセンターノードと，元のジェネレーらの配置問題の多くは NP(Non-deterministic Polynomial
タを比較し，求めたセンターノードとジェネレータtime) 困難であり，厳密解を求めるのにグラフが大規模にが全て等しければ，求めた p 個のセンターがそのグなる程時間がかかる．そこで近似解を求めるヒューリス
ラフの p ノードセンターの近似解とする．センターティクスが研究されてきた．例えば，古田らは，ネットノードとジェネレータが異なる時，求めたセンター
ワークボロノイ図を用いた p ノードセンター問題の近似ノードを新しいジェネレータとして 2．へ戻る．
解法を提案している [1]．しかし，数千〜数万ノード以上
この近似解法では最初に選ぶジェネレータの組合せにの大規模グラフでは近似解法であっても十分高速である よっては局所最適解で終了してしまう可能性がある．そことはいえない．
で初期値を変えて複数回実行するマルチスタートを用い，一方で，複数の PC をネットワーク接続したクラスタ環 その中で最適なジェネレータの組合せを最適解とする．
境や，GPGPU(General-Purpose computing on GraphicsProcessing Units) といった並列計算環境が比較的安価に 2.2 並列解法利用できるようになってきている．また GPGPU を利用
上記の p ノードセンターの近似解を求めるアルゴリズするための CUDA[2] や，クラスタ環境で並列計算を行う ムは以下の 2 つの観点から容易に並列化できる．
ためのライブラリである OpenMPI[3] などのソフトウェ
最短路問題 ジェネレータからネットワークボロノイ図をア開発環境も整いつつある．しかし，並列計算のための求める時に単一始点最短路 (SSSP:Single Source Shortest
問題のタスク分割や，タスクのプロセッサへの割り当てPath) 問題を複数回計算する必要があり，また 1 ノードは一般には自明では無い．
センターを求める時に全点対最短経路 (APSP:All-Pairs
本稿では，マルチコア CPU と GPGPU を備えた PCShortest Path) 問題を解くために SSSP 問題を繰り返し複数台を LAN で接続したクラスタ (GPGPU クラスタ)計算する必要がある．これらの最短路問題を並列計算すを想定し，CUDA と MPI を用いてネットワークボロノることができる．また，SSSP 問題自体を並列に計算する
イ図を用いた p ノードセンター問題の近似解法を並列にこともできる．
実装する方法について述べる．またこの近似解法で必要となるボロノイ分割の繰り返しを効率化するためのアル ボロノイ領域 各ジェネレータのボロノイ領域ごとに 1ゴリズムの最適化についても述べる．
ノードセンターを求める時，各ボロノイ領域は独立で他のボロノイ領域における計算の影響は受けないので，ボ2 p ノードセンター問題とその近似解法
ロノイ領域ごとに並列計算することができる．
大規模グラフの配置問題のひとつに p ノードセンター問題がある．p ノードセンター問題は，需要点と枝から構
文献 [4] では，文献 [1] の近似解法をこれらの視点から成されるネットワーク (グラフ) 上に，需要点とその最寄 MPI を用いて並列実装している．
りの施設との最大距離が最小となるように p 個の施設を配置する問題である．最大距離を最小にすると言う性質 3 GPGPU クラスタにおける並列実装
GPGPU クラスタ上でネットワークボロノイ図を用いから現実の道路網における消防署や病院などの緊急施設たp ノードセンター問題の近似解法を実装する方法につの最適配置問題，センサネットワークのスケジューリンいて述べる．また，ネットワークボロノイ分割を効率的グ問題などに適しているとされている．に繰り返すためのアルゴリズムの最適化についても示す．
2.1 ネットワークボロノイ図を用いた近似解法
3.1 実装の概要
ネットワークボロノイ図はグラフ上に母点 (ジェネレー
本実装では 2.2 節の最短経路問題の観点から CUDA をタ) が与えられたとき，各頂点からの距離がグラフ上で最も近い母点によってグラフを分割するものである．分割 用いて並列化した実装 [5, 6] と，2.2 節のボロノイ領域の観点から OpenMPI を用いて並列化した実装を組み合わされた領域をボロノイ領域と呼ぶ．
このネットワークボロノイ図を用いて p ノードセンター せる．
CUDA を用いた所は，SSSP 問題を解いてジェネレー問題の近似解を求める近似解法の概略を示す．
タからボロノイ領域に分割する箇所，SSSP 問題を繰り返し解きボロノイ領域の 1 センターを求める箇所である． 3.2 計算機資源の効率的な利用
MPI を用いた所は，ボロノイ領域の 1 センターを求める
前節の 4-3．で CUDA と MPI にどのように領域を割り箇所である．
当てるべきかは自明ではない．1 台の PC において MPI以下に実装の流れを示す．
プロセスと GPU の個数は等しくないので，同時に複数の1．1CPU に 1MPI プロセスを割り当てる．各 MPI プロ
セスは rank と呼ばれる固有の番号を持っている．

MPI プロセスが GPU を利用することはできない．これは，GPU を利用するためには同じホストノードの CPU
2．各 MPI プロセスで同じグラフのデータファイルから で CUDA カーネル関数を起動しなければならないからである．
グラフを作成する．
そこで，1 センターを求める領域の CUDA と MPI へ
3．各 PC(ホストノード) の一番小さい rank から，ホスの割り当ての方針として，総ノード数が多い領域に GPUトノードが持っている GPU の個数分だけ CUDA でを割り当て，そして総ノード数が少ない領域に MPI を割計算するフラグをたてる．
り当てて計算をさせることにした．具体的には各領域の4．GPGPU クラスタ上でネットワークボロノイ図を用
総ノード数を調べ各領域に総ノード数の降順に領域番号いて p ノードセンター問題の近似解法を解く．
をつける．そして，領域番号の小さい領域を CUDA に領4-1．p 個の頂点をグラフ全体から乱数で選択し，そ 域番号の大きなものに MPI を割り当てる (図 1)．
実装するにあたって，CUDA と MPI の領域の割り当ての頂点集合をジェネレータとする．
方法を，静的に基準を決めて割り当てた．この割り当て
4-2．rank0 で CUDA を使用して，ジェネレータからネットワークボロノイ図を求め，全てのプロ 基準は，領域の総ノード数が基準以上ならば CUDA に，セスに領域の情報を送る．このとき領域内の総 基準未満ならば MPI に割り当てるものである．これは実ノード数の降順に，各領域に領域番号を付ける． 験で，CUDA による 1 センターの計算は，小さすぎる領域では性能が出ず，C で計算するよりも遅くなってしま
4-3．CUDA と OpenMPI を用いて各領域のセンターうことがわかったからである (4.3 節参照)．
を求める (図 1)．
例として，2 台のホストノードがそれぞれ 4 個の CPUと 1 個の GPU を持つ計算環境において，割り当て基準値を 10 として，5 ノードセンター問題を解くケースを示
す．グラフがボロノイ分割されており，5 つの領域 R0 から R4 に分割されている．各領域の総ノード数は R0 の 16個が一番多く続いて R4 の 15 個，R2 の 11 個，R3 の 6個となり一番ノード数が少ない R1 の 4 個となっている．
最初のセンターを求める時，ノード数が多い領域である
領域 R0，R4 を GPU に割り当て，一番ノード数が少な
い領域 R1 を MPI を用いて GPU を使用していない CPU全てを用いて解く (図 2)．そして，割り当て基準値は 10なので GPU0 は R0 の 1 センターが計算し終えたら次にR2 を求める．MPI は次に R3 を求める．

図 1 1 ノードセンターを算出する

4-4．MPI で求めたセンターとそれに付随する情報は，GPU を使用していない全ての rank の中でrank が一番小さい MPI プロセスに集め rank0に送る．GPU で求めたものはそれぞれ rank0に集約する．センターとそれに付随する情報を全て rank0 に集めた後全てのプロセスに計算した全ての領域についてのセンターなどの情報を送信する．
4-5．もし p ノードセンター問題をネットワークボロノイ図を用いて解く方法の終了条件を満たしていれば終了．満たしていなければ求めたセンターをジェネレータとして 4-1．へもどる．

図 2 領域割り当ての例

3.3

ネットワークボロノイ分割アルゴリズムの最適化

グラフをボロノイ分割する際，設定されたジェネレー
タについて SSSP 問題を解くことで，全てのノードについて，どのジェネレータに一番近いかを調べることができる．これで，全てのノードはどのジェネレータの領域に属するか決定される．各領域でセンターを調べ，求めたセンターをジェネレータとして再びボロノイ分割する
際，上記の分割方法を再び実行する．しかし再びボロノイ分割する際，前のボロノイ分割の時の全てのノードについて一番近いジェネレータまでの距離コストの計算結果を捨ててしまっているので，無駄である．
そこで，1 つ前のボロノイ分割の結果，すなわち全てのノードについて一番近いジェネレータまでの距離コストを差分グラフとして記録しておく．そして再びボロノイ分割する際，各領域について求めたセンターとジェネレータが違う領域だけを，差分グラフを用いてボロノイ分割するという方法をとった．
実装の概略を示す．

1．1 回目のボロノイ分割を行う．このとき，全てのノードは一番近いジェネレータまでの距離コストを覚えておく，このグラフを差分グラフとする．
2．各領域でセンターを求め，各領域のどれか一つでもジェネレータとセンターが異なっている場合，再びボロノイ領域にグラフを分割する．

4.2

今回の実験では，実用的に用いることを想定して表 1に示す実際の道路網のデータを用いて行った．
表 1 都市の道路網
ファイル名 ノード数 総枝数
昭和区14248
18402
阿久比町
33598
35807
瀬戸市
58168
62102

4.3

5．ジェネレータを新しく求めたセンターにする．

計算実験

4

並列計算の性能確認のためと，提案実装の評価のために計算実験を行った．

4.1

実行環境

実験は以下のような仕様の PC を用いて行った．

• OS:UbuntuServer11.10• CPU: Intel(R) Core(TM) i7-2600 CPU @ 3.40GHz(4core 8Threads)• GPU: NVIDIA GeForce GTX 560 . CUDA Compute Capability 2.1• ネットワーク:1000base-T
4.3 節，4.4 節の実験では上記環境の PC を 3 台，24 スレッド，4.5 節の実験では PC1 台，1 スレッド使用した．

1 センターを求める予備実験

1 センターを求める時の実行時間の違いを，C のみの場
合，MPI を用いる場合，CUDA のみを用いる場合の 3 パターンについて調べた．この実験で，MPI は上記実行環境の PC を 3 台，24 スレッド用いて実験を行った．また，この実験では比較のために OR library による p メディア
ン問題用のグラフを使用した [7]．これは表 2 に示すノード数の少ないグラフとノード数の多い都市の道路網のグラフを比較するためである．

3．ジェネレータと求めたセンターが変わっている領域について，差分グラフの領域内全てのノードの距離コストを∞にし所属領域の情報を新しく求めたセンターに属するようにする．また，新しく求めたセンターの距離コストは 0 にする．ジェネレータと求めたセンターが変わっていない領域はそのままにする．
4．ジェネレータと求めたセンターが変わっている領域のセンターから，差分グラフの距離コストの更新を更新ができなくなるまで行う．また，領域を跨いで距離コストの更新を確認する時は，距離コストの確認をされたノードからも逆に距離コストの更新できるかを確認する．

実験対象グラフ表 2 ノード数の少ないグラフデータ
ファイル名
ノード数 総枝数
pmed1
100200pmed204003200
全ての実験について，グラフを 1 回実行した時間の結果を示した．
表 3 実行結果 (p=1)
pmed1
pmed20
昭和区
阿久比町
瀬戸市

p値
1
11
1
1

CPU (秒)0.001
0.064
3979.068
43486.757
232734.017

MPI (秒)0.002
0.012
760.7177982.393
20961.472

CUDA (秒)
0.075
0.081
202.013849.2095129.429

表 3 に結果を示す．結果から，CUDA はノード数が少ないグラフの場合だと性能を発揮できないので，C や MPIを用いて解くよりも遅くなった．しかし，1 万点以上のノード数のグラフでは MPI を使って解くより CUDA を使って解く方が実行完了までの時間が短いことから，CUDAは都市の道路網のようなノード数が多いとき MPI で解く場合より高速に解くことができるということがわかった．

4.4

p ノードセンター問題の実行時間

表 1 の道路網における p ノードセンター問題を C のみの場合，MPI を用いる場合，CUDA のみを用いる場合，
CUDA と MPI を組み合わせた提案実装の 4 パターンで行った．CUDA と MPI を組み合わせた実装について，総ノード数を p 値で割ったものを丸めた数値を基準値として，領域の総ノード数が基準値以上の領域を GPU に割り当て，基準値未満の領域を MPI に割り当てる (表 4)．

昭和区
阿久比町
瀬戸市

表 4 割り当て基準値
ノード数 p 値 割り当て基準値
14248
30400
101500
33598
30
1000
10300058168
302000105000

この実験で，MPI は上記実行環境の PC を 3 台，24 ス
レッド用いて実験を行い，GPU は 1 つの PC につき 1 つ使用した．都市の道路網のグラフを用いて一回実行した
時間の結果を示した．
表 5 道路網に対する p ノードセンター問題の実行結果
昭和区
阿久比町
瀬戸市

p値
3010301030
10CPU (秒)150.875
1318.547
661.879
2342.984
4234.637
39938.538

MPI (秒)
24.240153.11190.002276.598766.3513622.691

CUDA (秒)287.6323035.842
766.351
1100.456
6106.339
12049.410

提案実装 (秒)117.2721138.054
593.462352.7422391.223
3171.396

表 5 に結果を示す．結果から，CUDA と MPI を組み合わせて解く場合，CUDA への割り当て基準のノード数が少ない場合，CUDA の性能が引き出せなかったため遅くなった．しかし，ノード数が 5000 ノード以上の領域については CUDA に解かせると，MPI のみや CUDA のみで解く場合よりも高速に解くことができるということがわかった．

4.5

ネットワークボロノイ分割アルゴリズム最適化の効果

ネットワークボロノイ分割を効率的に繰り返すためのアルゴリズムの最適化の効果を調べるために，C だけのプログラムで，p ノードセンター問題の計算を行い，最適化の有無で比較したものである．この実験で，PC を 1台，1 スレッドを用いて実験を行った．都市の道路網のグラフを 1 回実行した時間の結果を示した．
表 6 道路網に対するボロノイ分割の最適化の実行結果
昭和区
阿久比町
瀬戸市

p値303030

最適化・有 (秒)150.875
661.8794234.637

最適化・無 (秒)165.396800.3764244.087

表 6 に実験結果を示す．ボロノイ領域の分割の繰り返しのアルゴリズムを改良した結果，瀬戸市のグラフでは効果を発揮できていないが，おそらく差分の量が多く最適化前と同じ回数処理をしてしまい，一部増やした最適化の処理の時間で遅くなってしまったと考えられる．しかし，グラフによっては改良前より高速化することができた．また，p 値が大きいグラフの多くは最適化によって計算時間が短縮できた．これは距離コストの計算回数が最適化前に全ノードに対して行ってた距離コストの計算を，改良後は差分ノードのみに対して計算しているからだと考える．

5

まとめと今後の課題

GPGPU クラスタを想定し，ネットワークボロノイ図を用いた p ノードセンター問題の近似解法を，CUDA とMPI を用いて実装した．予備実験で CUDA はより大規模なグラフで効率的に動作することがわかったので，ネッ
トワークボロノイ分割されたグラフの領域を，領域の総ノード数が多いものは GPU に，少ない領域は MPI に割り当てて計算した．実験の結果，CUDA に割り当てる領域のノード数が多いほど CUDA の性能を活かして高速化ができることがわかった．またボロノイ分割の繰り返しを効率化するためのアルゴリズムの最適化も行った．実験の結果，ボロノイ分割された領域の差分を用いることで一部高速化することができた．
今後の課題としては，GPU と MPI の領域割り当てを動的に行う．具体的には，1 つの MPI プロセスをサーバとして，領域の計算が終わったプロセスに，まだ計算されていない領域をオンデマンドで割り当てることができると考えている．また，実装の最適化を行い，大規模実験で有効性を確認する．

参考文献[1] 古田壮宏, 鈴木敦夫, “ネットワークボロノイ図を利用した p ノードセンター問題 の近似解法”, アカデ
ミア 数理情報編, 第 6 巻, 2006 年.
[2] NVIDIA Corporation,“NVIDIA CUDA C Programming Guide”,
http://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html ,2012.
[3] Indiana University, “OpenMPI:Open Source High
Performance Computing”,
http://www.open-mpi.org/ ,2004.
[4] Hajime Miyazawa, Takehiro Furuta, Atsuo Suzuki,“An Approximate Parallel Solution of the Vertex pCenter Problem Using Network Voronoi Diagram”,
in Proceedings of the 2009 International Conference on Parallel and Distributed Processing Techniques and Applications(PDPTA’09), 2009.
[5] Pawan Harish, and P.J. Narayanan, “Accelerating large graph algorithms on the GPU using CUDA”, in Proceedings of the 14th International Conference on High Performance Computing(HiPC’07),pp.197-208,2007.
[6] 奥山 倫弘, 伊野 文彦, 萩原 兼一, “CUDA による全点対最短経路問題の高速化”, 社会法人 情報処理学会 研究報告,pp.145-150 ,2008 年.
[7] J.E.Beasley, “OR-Library: distributing test problems by electronic mail”, in Journal of the Operational Research Society, Vol.41,pp.1069-1072,1990.