1. 概要
本課題の目的は Graph500 のスコア更新を通じて, 世界最大規模となる計算機 (SGI UV 2000) 上でのスレッド並列計算の有用性を示すことである. これまでの取組みや今回の取組みにより, 我々の ULIBC ライブラリを用いた適切なスレッドとメモリデータの配置を制御により, OpenMP によるスレッド並列計算形式が安定的に動作することを検証できた. また, 今回の主な課題である SGI UV 2000 上の Graph500 に関しては, SGI UV 2000 1ラック (64 ソケット) あたりで最高スコア (昨年度までの共同利用の結果) であった 131.4 GTEPS を 152.2 GTEPS に 15.8% の性能向上を達成した. 加えて, 我々が以前より開発してきた中心性指標計算ソフ トウェア NETAL を SGI UV 2000 上に移植し性能評価を実施し, 媒介中心性計算において 1 ソケット時と比較した際に 32 ソケットで 23 倍と高い並列効率を確認した. さらに我々が開発した NUMA を考慮した制御ライブラリ ULIBC に対しても, Graph500 や NETAL の取組みを反映して安定性の向上を行った.
2. Graph500 のスコア更新
まず SGI UV 2000 システム上で, MPI の All-gather 演算と似た処理方法となる NUMA ノード毎の部分結果を全体に伝播する処理に対して, 高速化を検討するための基本的な計測を行った. 本システムは計 4 ラックを Hypercube トポロジーにより1 システムを構成しており, 少々複雑なネットワークトポロジーとなる. これらの性質を明らかにするために, 全システム4ラック中1ラックを対象に, STREAM ベンチマークの TRIAD 演算による 2 NUMA ノード間 (2ソケット間) のメモリ帯域幅の測定によりシステムのネットワーク特性の詳細な把握を行い, NUMA ノード内 (ローカルメモリ) のアクセスは 32.5 GB/s, 2ソケットからなる計算シャーシ内では 6.9 GB/s, 8シャーシから構成されるキューブ内で 4.8-5.6 GB/s, 更にキューブを接続したブロック内では 3.4-4.5 GB/s という結果を得た. なお, 1ラックを対象とするとブロック間を使用した組合せは存在しないが, システム上では距離が最も遠い2 NUMA ノード間となり最も性能が低い組合せとなる. 測定結果の中で最も高いメモリ帯域幅を有している NUMA ノード内の通信は既に考慮しており, その他の部分に関しては複雑なシステム構成に依存した高速化となるため, 汎用性とのトレードオフとなるため本課題で取り組むことは見送り, 全対間通信を最小限に押さえるアルゴリズムの修正に取り組んだ.
近年 Graph500 で主に利用されている BFS アルゴリズムは, 始点から開始して距離 (レベル) 毎に探索済領域を拡大するという基本方針を採用しており, 各レベルで始点から離れる方向へ現在の探索済領域の前線から隣接する枝を探索していく Top-down と, 未探索領域から探索済領域の前線を探索する Bottom-up のうち1つを選択する. 特に Bottom-up は探索済領域の前線が大きいときに不要な枝探索を削減することで, 全体の性能に大きく寄与している. この性質は共有メモリ型計算機上で最速の我々の実装にも同様である. 我々の実装の Bottom-up では全対間通信が必要となるが, PC などの小規模環境では性能上大きな問題にならないものの, SGI UV 2000 の規模ではボトルネックの候補となってしまう. そこで Top-down の効率化に取組み, リモートメモリアクセスを大きく削減したアルゴリズムを構築した. SGI UV 2000 1ラック(64 プロセッサ) で性能評価を行い 131.4 GTEPS から 152.2 GTEPS へ 15.8% と性能向上を達成した. 本結果は査読付き国際会議 [1] にて報告を行った.
3. NETAL
我々が以前より開発している中心性計算に関するライブラリ NETAL [2] を SGI UV 2000 上に移植し性能評価を行った. NETAL に対する性能評価は文献[3] では最大4ソケット48コアまでの計算機が最大の規模であったが, 本研究では 32ソケット 320 コアまで拡大して性能評価を行った. 26万点, 73万枝の道路ネットワークと 69万点, 1330万枝のウェブネットワークに対して, 媒介中心性 (Betweenness centrality) を計算し, 実行時間がそれぞれ 53 秒と 545 秒となった. その時の並列化効率は, 1ソケット時と比べてどちらも 23 倍ほどの性能向上を達した. 本結果は国際会議 [2] にて報告を行った
4. ULIBC
ULIBC [5] は NUMA を考慮したスレッドやメモリの位置に関する制御をおこなうことができるライブラリで LGPLv3 で公開している. ULIBC はプラットフォーム (Linux, Solaris, AIX) に対応し, 複数ソケットを搭載した中規模システムから, UV 2000 のような大規模システムまでを汎用的に扱うことを目指している. 本研究における Graph500 の性能向上や NETAL の移植にあたり, 得られた知見を ULIBC の反映することができた.
|