NUMA-affinity : APSP(NY)

今度は NY(264K点/734K枝) に対して APSP(全対全最短路問題) を計算してみた。
環境はこれまでと同様 Nehalem-EP と Istanbul4 である。
Nehalem-EP : Intel(R) Xeon(R) CPU X5550 @ 2.67GHz (4cores x 2sockets)
Istanbul4 : Six-Core AMD Opteron(tm) Processor 8439 SE (6cores x 4sockets)


今回測定した実装は以下の通りである。いずれもコア数=並列数で計算している。
naive : 一般的な pthread 並列
huge/numactl : numactl による affinity 設定とHugePage(LargePage) によるメモリ確保
affinity : sched_setaffinity() による affinity 設定
hugepage/affinity : hugepage かつ affinity

やはり Istanbul は実装に応じた性能差が大きく、Nehalem-EP は性能差が少ない。
コア数は Nehalem-EP : Istanbul = 8 : 24 = 1 : 3 だが、
実行時間は Nehalem-EP : Istanbul = 1298.830 : 600.991 = 2.1611 : 1 となっており、
コアあたりの性能は Nehalem-EP の方が高い。


スループットとしての TEPS を算出すると、 Istanbul では 322.7969 ME/s、Nehalem-EP では、149.3604 ME/s となる。


画像には westmere が書いてあるのはご愛嬌ということで。

NUMA-affinity : 9th DIMACS refernce Solver との差

今回は mbp とこちらの実装を比べてみる。mbp は1スレッド時は確かに高速であるが、マルチスレッドに対応していない。対応したとしても資源の競合から性能が出しにくいと予想している。

naive : 一般的な pthread 並列
numactl : numactl による affinity 設定
hugepage : naive-based の HugePage(LargePage) によるメモリ確保
affinity : sched_setaffinity() による affinity 設定
hugepage/affinity : hugepage かつ affinity
reference : 9th DIMACS reference code 'mbp' / A.V.Goldberg

istanbul の結果。


nehalemep の結果。


このようにいずれも並列数分ほどの性能差が確認される。

NUMA-affinity @ Nehalem その2

前回の続き。

naive : 一般的な pthread 並列
numactl : numactl による affinity 設定
hugepage : naive-based の HugePage(LargePage) によるメモリ確保
affinity : sched_setaffinity() による affinity 設定
hugepage/affinity : hugepage かつ affinity
reference : 9th DIMACS reference code 'mbp' / A.V.Goldberg

各実装の1スレッド時を基準とした性能効率をみてみる。Istanbul ほどのばらつきはないが、やはり affinity 設定を行った実装の方が性能・並列効率が良い。


Istanbul でも行った naive[1] を基準にした並列効率をみてみる。naive[1] と hugepage/affinity[8] では、7.733 倍となる。

NUMA-affinity @ Nehalem その1

今度は Nehalem-EP アーキテクチャの Intel(R) Xeon(R) CPU X5550 を 2基搭載した計算サーバでの実験結果をまとめる。

グラフは全米(24M点/58M枝)である。クエリは SSSP x 576 となっている。

naive : 一般的な pthread 並列
numactl : numactl による affinity 設定
hugepage : naive-based の HugePage(LargePage) によるメモリ確保
affinity : sched_setaffinity() による affinity 設定
hugepage/affinity : hugepage かつ affinity
reference : 9th DIMACS reference code 'mbp' / A.V.Goldberg

まずは１クエリあたりの実行時間(スループット)から。前回の Istanbul に比べてコア数が少ないが、１コアあたりの性能が良い。やはり hugepage/affinity の並列効率が非常に良いことが確認できる。Instanbul での hugepage の特性はコア数が少ないためか確認はできない。

NUMA-affinity @ Istanbul その3

前回の続き。

naive : 一般的な pthread 並列
numactl : numactl による affinity 設定
hugepage : naive-based の HugePage(LargePage) によるメモリ確保
affinity : sched_setaffinity() による affinity 設定
hugepage/affinity : hugepage かつ affinity
reference : 9th DIMACS reference code 'mbp' / A.V.Goldberg

各実装の1スレッド時を基準とした性能効率をみてみる。hugepage/affinity は性能も並列効率も良い。


今度は、あまり意味のないことかもしれないが naive[1] を基準にした並列効率をみてみる。naive[1] と hugepage/affinity[8] では、24.053 倍となる。

NUMA-affinity @ Istanbul その2

Istanbul アーキテクチャの Six-Core AMD Opteron(tm) Processor 8439 SE を 4基搭載した計算サーバでの実験結果をまとめる。

グラフは全米(24M点/58M枝)である。クエリは SSSP x 576 となっている。

naive : 一般的な pthread 並列
numactl : numactl による affinity 設定
hugepage : naive-based の HugePage(LargePage) によるメモリ確保
affinity : sched_setaffinity() による affinity 設定
hugepage/affinity : hugepage かつ affinity
reference : 9th DIMACS reference code 'mbp' / A.V.Goldberg

まずは１クエリあたりの実行時間(スループット)から。いずれも並列効率が非常に良いことが確認されるが、やはり hugepage/affinity が良い。hugepage の特性が他と違っていて面白い。並列数が小さいときは hugepage による性能の良いメモリによる性能向上が確認されるが、並列数が大きくなると資源共有による性能低下の方が大きいため、affinity や hugepage/affinity に負けてしまう。

NUMA-affinity @ Istanbul その1

Istanbul(Opteron8439SE) 4sockets 構成には 6cores x 4sockets = 24cores が搭載されており、affinity の指定の組合せも非常に多い。割振りによって、性能が異なるか調べてみる。

ダイクストラ法をスレッド並列する際には、グラフデータを共有することでメモリ要求量を抑えつつ、そのためキャッシュメモリのヒット率が向上することとなる。

その際、「(グラフデータを共有したコア・グループ) x (グループ数)」という組合せで特性は決定する。理想的なのは「ソケット内でグラフデータを共有する」ことになると予想はあるものの、まずは確認していく。

でのマルチスレッドの組合せ 6x4, 3x8, 2x12, 1x24 に対して性能比較を行った。たとえば、
今度は 24 threads でのコアの組合せを変えて実験してみる。やはり、グラフデータは


hugepage & (6x4)--affinity=0,4,8,12,16,20:1,5,9,13,17,21:2,6,10,14,18,22:3,7,11,15,19,23
193.426 sec.  174.2951 GE/s

hugepage & (3x8)--affinity=0,4,8:12,16,20:1,5,9:13,17,21:2,6,10:14,18,22:3,7,11:15,19,23
196.382 sec.  171.0955 GE/s

hugepage & (2x12)--affinity=0,4:8,12:16,20:1,5:9,13:17,21:2,6:10,14:18,22:3,7:11,15:19,23
194.565 sec.  172.6930 GE/s

hugepage & (1x24)--affinity=0:4:8:12:16:20:1:5:9:13:17:21:2:6:10:14:18:22:3:7:11:15:19:23
198.523 sec.  169.2500 GE/s

hugepage & (1x24)--affinity=0,1,2,3,4,5:6,7,8,9,10,11:12,13,14,15,16,17:18,19,20,21,22,23
268.190 sec.  125.2846 GE/s

超大規模ネットワーク n=2^30, m=2^31-1 その3

以前の記事(こちら)で 10億点, 20億枝のグラフに対する SSSP(1対全最短路問題) の並列実行について書いてみたが、あまりにもマルチスレッドがうまくいかないことが分かった。そのときの TEPS はやはり低い。また Istanbul4(Opteron(tm) Processor 8439 SE) と Nehalem-EP(Intel(R) Xeon(R) CPU X5550 @ 2.67GHz) では倍以上の差が確認される(1thread時)。

グラフ : rand_1G_2G-1_1.gr(n=2^30, m=2^31-1, U=[1,1])
クエリ : SSSP(1) x 1 (始点1)

Time[sec.]
                 parse  construct       sssp
Istanbul4     1088.592   1363.551   1890.330
Nehalem-EP    1044.964    789.239    868.166
Nehalem-EP[2] 1044.964    820.822  29903.140

TEPS score[ME/s]
                 parse  construct       sssp
Istanbul4[1]    1.9727     1.5749     1.1360
Nehalem-EP      2.0545     2.7210     2.4736
Nehalem-EP[2]   2.0551     2.6163     0.0718

NUMA-affinity その1

これまでの 単純分割 & numactl ではなく、ソフトウェアとしてしっかり affinity を設定を行えるように対応した。もちろん計算ノード内のプロセス数が1となるので、非常にオーバーヘッドが削減される。また単純分割では事前に計算量がある程度見積もれる SSSP クエリでしか負荷分散が難しかったが、今回の更新で動的な負荷分散にも可能となる。

● Istanbul4
CPU : Six-Core AMD Opteron(tm) Processor 8439 SE (24)
GCC : 4.4.5
linux : 2.6.34.7-61.fc13.x86_64
Memory : HugeTLBfs(2MB)

● APSP( NY(#nodes: 264346, #arcs: 733846) )

実装1 : 685 秒 (283 GE/s)
affinity 設定なしのマルチスレッド計算 : 24-threads

実装2 : 633 秒 (306 GE/s)
クエリの単純分割 & numactl を用いてソケット数分のプロセスを立ち上げ、プロセス内はソケット内コアでのマルチスレッド計算 : 4-processes x 6-threads

実装3 : 601 秒 (323 GE/s)
affinity 設定ありのマルチスレッド計算 : 24-threads

非常に高効率が確認された。様々な実験を行う予定である。

Processor ID と APIC ID その2

単純だが、Processor ID 0 から #cores-1 まで、CPU_SET & sched_setaffinity した状態で APIC ID を調べるだけで、Processor ID - APICID 対応表が完成する。

● Intel(R) Xeon(R) CPU X5460 @ 3.16GHz (4cores x 2sockets)
0-th core -> 00 apicid
1-th core -> 04 apicid
2-th core -> 02 apicid
3-th core -> 06 apicid
4-th core -> 01 apicid
5-th core -> 05 apicid
6-th core -> 03 apicid
7-th core -> 07 apicid

● Intel(R) Xeon(R) CPU X5550 @ 2.67GHz (4cores x 2sockets)
0-th core -> 20 apicid
1-th core -> 00 apicid
2-th core -> 22 apicid
3-th core -> 02 apicid
4-th core -> 24 apicid
5-th core -> 04 apicid
6-th core -> 26 apicid
7-th core -> 06 apicid

● Six-Core AMD Opteron(tm) Processor 8439 SE (6cores x 4sockets)
 0-th core -> 00 apicid
 1-th core -> 30 apicid
 2-th core -> 20 apicid
 3-th core -> 10 apicid
 4-th core -> 01 apicid
 5-th core -> 31 apicid
 6-th core -> 21 apicid
 7-th core -> 11 apicid
 8-th core -> 02 apicid
 9-th core -> 32 apicid
10-th core -> 22 apicid
11-th core -> 12 apicid
12-th core -> 03 apicid
13-th core -> 33 apicid
14-th core -> 23 apicid
15-th core -> 13 apicid
16-th core -> 04 apicid
17-th core -> 34 apicid
18-th core -> 24 apicid
19-th core -> 14 apicid
20-th core -> 05 apicid
21-th core -> 35 apicid
22-th core -> 25 apicid
23-th core -> 15 apicid

第4回 SCOPE

第4回 SCOPE は高野 祐一 氏と Mozart Menezes 氏の両名によるご講演。お二人ともゆっくり離していただいたので、非常に理解しやすく面白かった。

Processor ID と APIC ID

/proc/cpuinfo に書かれた Processor ID は、OS が識別するための通し番号なので、再起動の度に変わる可能性がある。それに対して、eax=1 で cpuid を実行した際の ebx[24:31] の値である APIC ID は固定の ID となるため、識別子として非常に優秀である。

しかしながら、 sched_setaffinity() sched_getaffinity() で使用される CPU_SET() の第1引数の値は、Processor ID で指定しなければならないので、非常にややこしくしてしまっている。 まずは APIC ID と Processor ID の対応付けをすることがまずは先決であろう。

#include <sched.h>
int sched_setaffinity(pid_t pid, unsigned int cpusetsize, cpu_set_t *mask);
int sched_getaffinity(pid_t pid, unsigned int cpusetsize, cpu_set_t *mask);
void CPU_CLR(int cpu, cpu_set_t *set);
int CPU_ISSET(int cpu, cpu_set_t *set);
void CPU_SET(int cpu, cpu_set_t *set);
void CPU_ZERO(cpu_set_t *set);

Kyoto Prize Satellite Workshop in Tokyo

東工大 で行われた Kyoto Prize の Satellite Workshop に参加してきた。Satellite なので、映像かなと思いきや TSP で著名な William Cook 氏が壇上に登場したので驚いた。TSP まとめのような理解しやすいご講演で聞きやすかった。その後は理論的な話が多く、正直ほとんど分からなかった。今回 Kyoto Prize を 受賞された László Lovász 氏のご講演も非常に難易度が高く、予め予習していけば良かったと少々後悔。

NUMA を考慮した並列実行 その4

USA-road-d.NY.gr に対し、APSP(全対全最短路問題) をマルチスレッドで計算した際の TEPS 値性能をまとめる。以前おこなった実験はこちらに。赤が全体の性能を、青が１コアの性能で単純に全体性能をコア数で割り算した値である。

TEPS - traversed edges per second

Graph500 では TEPS という性能指標を用いる。

TEPS は FLOPS のように、1秒間に "何本の枝" を処理できるかを示しており、次のような式で算出される。ここで K2(n) は BFS を指している。

TEPS(n) = m / timeK2(n)

例えば Graph500.org の web site にある Complete Results を見ると、
現在の Rank1 は、Argonne National Laboratory にある Intrepid (IBM BlueGene/P, 8192 nodes/32k cores) という実行環境で、Scale 36 (Medium) instance を 6.6 GE/s で探索することができるとしている。