CS

Size: px

Start display at page:

Download "CS"

いおりかつま
5 years ago
Views:

1 性能並列計算法特論第 4 回情報基盤研究開発センター野謙 2017 年 5 9 ( )

2 成績評価その他の連絡事項出席点 5 割 + 期末試験 ( レポート作成 )5 割講義資料は毎回配布予定です席した場合, 各でダウンロードしてください PDF 版をその週の曜の朝までには公開予定講義開始後約 30 分で出を取ります研究室 : keno@cc.( 九州学のドメイン ) Subject には必ず性能並列計算法と記してください 2

3 この回の学習内容アーキテクチャのおさらい性能プログラム開発の指針並列性能評価 Byte / Flop 指標並列処理の効率 Amdahl 則ルーフラインモデル参考 The Software Optimization Cookbook High Performance Recipes for Intel Architecture, Intel Press Minami, High-performance parallel programming, AICS lecture

4 マイクロアーキテクチャー Intel Nehalem 4 cores/socket x 2 CPU マルチコアキャッシュメモリサブシステムバスインターコネクトシステムの階層性処理速度 CPU >> Cache >> Bus >> Memory >> IC >> Disk GHz few cycles GB/s GB/s GB/s GB/s System Bus Memory 記憶容量 CPU(register) << Cache << Memory << Disk KB KB~MB GB TB Inter Connect

5 Intel Core Microarchitecture Instruction F etch and P red ecode Instruction Q ueue Microcode ROM Decode Rename/Alloc Shared L2 Cache Up to 10.7 GB/s FSB Retirement Unit (R e-o rder B uffer) Scheduler ALU Branch MMX/SSE/FP Move ALU FAdd MMX/SSE ALU FMul MMX/SSE Load Store L1D Cache and DTLB 5 OM19808 Figure 2-1. Intel Core Microarchitecture Pipeline Functionality

6 Intel Core i7 の性能 Architecture Core i7 Clock 2.67 GHz Instruction throughput 4 µops/cycle Peak FP rate (Multi+Add) 4 flops/cycle L1 Cache 32 KB (10 µops) L2 256 KB x 4 (40 µops) L3 (Shared) 8 MB Main Memory 4GB~ (DDR3-1066) Channels 3 Memory clock 1066 MHz Theoretical Bandwidth 25.6 GB/s 4 flops/cycle x 2.67 = GFLOPS/core DDR GB/s x チャネル数 = バンド幅ハードウェアとしては, 全ての演算器を使いきった場合に 10.6GFLOPS を達成 (Intel 系では SIMD 演算器のフル利 )

7 スパコンハードウェアの傾向プロセッサ最近のマイクロアーキテクチャネットワーク広帯域の専設計ネットワークメモリ RDMAなど機能化 >> NV-Ram, 3Dstacking 演算加速器 GPU, FPGAなどヘテロな構成にディスク NV+SSD+HDD+ Flops ó Byte の能にきな乖離 Processor Memory Network Interface Controller P M NIC 性能を引き出すプログラムを書くためにはアーキテクチャを理解すること Network

8 並列処理の階層性 P! P! P! P! P P P P P P Network L1! L1! L1! L1! L2! L2! Memory Bus! SMP: メモリへの距離が同じ Memory! マルチコア :SMP を階層化 C! C! C! C! C! C! C! C! P P P P P P P P P P P P P P P P Bus! M! M! M! M! M! M! M! M! Memory! マルチソケット 8 way SMP <= Quad-core CPU x dual-socket Network! 分散共有 : 物理メモリは分散しているがアドレススペースは単

9 ネットワーク並列計算機でノード間を接続する通信網メモリバスと同様にネットワークバンド幅がある規格は10G, InfiniBandなどネットワークの接続形態をトポロジ Mesh/Torus Hypercube Crossbar Fat tree Tree

ネットワークトポロジ耐障害性, 性能などの点から多様な式バンド幅通信帯域 (GB/s) バイセクションバンド幅システムの全計算ノードを 2 分割したグループ間で衝突しないノードペアを選び通信するときに得られる総バンド幅フルバイセクションバンド幅では, 通信性能の下限が定値より下がらない http://wikipedia.

10 ネットワークトポロジ耐障害性, 性能などの点から多様な式バンド幅通信帯域 (GB/s) バイセクションバンド幅システムの全計算ノードを 2 分割したグループ間で衝突しないノードペアを選び通信するときに得られる総バンド幅フルバイセクションバンド幅では, 通信性能の下限が定値より下がらないレイテンシデバイスに対してデータ転送などを要求してからその結果が返送されるまでの遅延時間性能計算いバンド幅量のデータを短時間で送受信低レイテンシ多数のデータを短時間で送受信通信時間 (sec) 実測によりサンプリング傾きの逆数転送速度 10 切片立ち上がり時間最小二乗法でフィッティング 0 データサイズ (Byte)

11 針単体性能構成単位の HW の性能を引き出すマイクロアーキテクチャ計算アルゴリズム単体チューニング並列性能並列時のスケールアップを狙う並列化アルゴリズム並列チューニング

12 B/F Byte / Flop データの移動量と演算量の次の2つの意味でいられる計算機ハードウェアの持つ能アルゴリズムが要求する指標低 B/F データ供給能よりも演算能がい現在のアーキの傾向 B/F 演算能よりもデータ供給能がいベクトルレジスタ ( 価 )

13 性能指標ノイマン型コンピュータ命令とデータを記憶領域からロードし, 実するモデル FLOPS 1 秒あたりの浮動数点演算数 MIPS 1 秒あたりの命令実数 call cpu_time(t1) do n=1, a = b + c * d end do call cpu_time(t2) flop = 2*10000 flops = flop/(t2-t1) 13

単体性能向上の鍵メモリウォールの問題対策 CPU の演算能に対してメモリからのデータ供給能が相対的に不している低 B/F の HW になっている CPU~ メモリ間に速なキャッシュを設けるキャッシュのデータを何度も使うアルゴリズムをいる列積 AB :O (N 2 ) のデータで O(N 3 ) の演算

14 単体性能向上の鍵メモリウォールの問題対策 CPU の演算能に対してメモリからのデータ供給能が相対的に不している低 B/F の HW になっている CPU~ メモリ間に速なキャッシュを設けるキャッシュのデータを何度も使うアルゴリズムをいる列積 AB :O (N 2 ) のデータで O(N 3 ) の演算このアルゴリズムの要求 B/F B/F=O(N 2 )/O(N 3 )=O(1/N) キャッシュは万能ではない低 B/F アルゴリズムには有効である CPU Arithmetic Units L1 Data L1 Inst 再利 L2 Data L3 Data Memory L1 << L2 << L3 << Memory

15 データの再利列列積 N 3 個の演算 N 2 個のデータ N 2 個のデータメモリ上には連続となるようにデータが配置する ex) C a[j][i] でi 向に連続アクセス F a(i,j) でi 向に連続アクセス列 A はメモリ連続アクセスであるが列 B は不連続アクセス Nがある程度きくなるとキャッシュには載らなくなるつまり Aは効率的に再利できるが Bは常に再利できるとは限らない

16 キャッシュから溢れる場合キャッシュブロッキング列を列に分割して列がキャッシュに載るようにする

17 B/F の場合列ベクトル積 N 2 個の演算 N 2 個のデータ N 個のデータ B/F = (N2+N) / N 2 = 1 もし全てのデータがキャッシュに載ったとしても要求 B/F がきいその場合キャッシュからの B/F と較することになる

18 並列化逐次処理処理時間 task1 task2 task3 task4 Processor 1 並列処理計算資源が単ユニット各タスク間に依存関係がある task1 task2 task3 task4 Processor 1 Processor 2 Processor 3 Processor 4 計算資源が複数ユニット各タスク間に依存関係がなく独であるため同時実が可能

19 プロセス間の並列処理 Computation time Computation time Comm. time Comm. time Processor 1 task1 task1 Communication Processor 2 task2 task2 Processor 3 task3 task3 Processor 4 task4 task4

20 並列処理の性能向上 Computation time Computation time Comm. time Comm. time Processor 1 task1 task1 Communication Processor 2 task2 task2 1. 各タスクの計算時間を同じにする ( ロードバランス ) Processor 3 task3 task3 2. 通信時間を短くする 3. 通信を計算とオーバーラップさせる Processor 4 task4 task4

21 並列処理の効率 (1) Program あるプログラムの計算時間が逐次実で 100 秒かかるとする

22 並列処理の効率 (2) Program Serial 1 sec. Parallelizable 99 sec. 並列化できる部分は全体の 99% あり残りの 1% は並列化できない

23 並列処理の効率 (3) Program Parallelizable 1 sec sec = 1.99 sec. Speedup => 100 / 1.99 = processors 10 3 プロセッサでは 100/ = プロセッサでは 100/ =

24 並列処理の般化 1-α α 仕事を1とする同時に実できる部分をα α/n α/2 2 で作業すると? N では? N どんなに作業者が増えても, 残る仕事!!

25 並列化率と並列効率定義シングルプロセスの計算時間 n プロセスでの計算時間並列化率全体に対する並列化可能部分の割合並列効率 E n = T T = n T 1 T a n ( -a + a n) 並列部分とは何か? I/O 通信隣接間通信と域通信 etc 1-a a a n

26 Amdahlʼs Law 640k 並列化率 99.9% のとき, スピードアップの最は 1,000 倍.2000CPU でも 1000 倍が上限.

27 スケーラビリティ Weak Scaling プロセス ( コア ) あたり問題規模が定プロセス数に例して問題規模が増加演算量と通信量の率は, ほぼ定 Strong Scaling 問題規模が定プロセス数に反例して問題規模が減少演算量に対する通信量が増加現実の問題は,Strong Scaling と Weak Scaling の中間

28 並列性能向上の観点ループブロック毎にコードを評価していく並列可能なコード部分が最化されているか? 並列部分を極化することロードバランスはとれているか? タスクの分割隣接間通信および域通信の割合が並列数とともにどのように変化するか? 特に域通信に注意

29 並列化に伴うペナルティアルゴリズム逐次アルゴリズムを並列処理可能にする際に必要な付加的な処理この部分は並列化できないことが多い陰的なデータ依存性領域分割時のデータ同期, 袖領域の通信処理領域分割時のデータの集約 ( 反復計算の誤差評価など ) 実装通信処理通信バッファへの gather/scatter アイドルタイム同期待ち管理処理データ管理, タスク管理, 通信管理のための処理

( 計算機が分な性能を供給できる ) B M はメモリバウンド性能の上限をす単位時間に実できる演算数に対する単位時間に転送できるデータ量の Algorithmic balance B A

30 性能改善の基本的な考え計算機の特性とプログラムの特性を把握するボトルネックがどこで起こるか CPU bound 演算性能で性能が飽和する Memory bound メモリバンド幅で飽和する Metric Machine balance B M l = B M B A l>1 のとき, バンド幅制限ではない. ( 計算機が分な性能を供給できる ) B M はメモリバウンド性能の上限をす単位時間に実できる演算数に対する単位時間に転送できるデータ量の Algorithmic balance B A 反復ループ内のロードストア数と演算数の J. Treibig, et.al., Complexities of performance prediction for bandwidth-limited loop kernels on multi-core architectures, High performance Computing in science and engineering, Munich 2009.

31 Weak scaling 評価演算時間演算時間が増する場合並列部分が残っている Computational time 域通信域通信は並列数とともに増加する域通信の回数と通信量を抑える夫隣接間通信通信処理法が適切でないと並列数とともに通信時間が増加する Number of processes

32 ルーフラインモデルハードウェアの性能とコードの特性から実可能な性能を推定 B M ; マシンバランスメモリから CPU へのデータ供給能と演算能の Intel Core i7 (2.67GHz) >> 4 flops/cycle, DDR x 3 ch. B M = = 25.6 GB/s GFLOPS 2.4 B/F ピーク性能は演算器をフルに動作すること, つまり演算数が分にありコンパイラがうまくスケジューリングできる場合に達成される B A ; アルゴリズムバランスコードのループ内の変数のロードストアと演算数の

33 How to maximize Performance? Roofline Model [Williams, Commn. ACM. 52(4), 2009.] attainable Gflop/s AMD Opteron 2356 (Barcelona) peak stream bandwidth peak SP Gflop/s = min Peak roofline performance based on manual for single precision peak and a hand tuned stream read for bandwidth Peak Gflop/s Stream BW * actual flop:byte ratio 1 1 / 8 1 / 4 1 / flop:dram byte ratio Operational Intensity (Flop/Byte) To increase OI, i.e., Flop/Byte in a loop

34 並列化プログラム中の並列動作する部分を最化する並列アーキテクチャとの相性のよい ( アーキテクチャの所を引き出せる ) 並列化がある例えば領域分割 P0 逐次計算全領域を 1 プロセスで計算するループ分割 / タスク分割 for (i=0; i<100; i++) { r1 = a[i-1]+a[i+1]-2.0*a[i]; a[i] = a[i]+(r1-a[i])*omg; r0 = r1*r1; } P0 P1 P2 P3 領域分割並列計算全領域を N 領域に分割し各部分領域を各プロセスで計算する #pragma omp parallel for for (i=0; i<100; i++) { r1 = a[i-1]+a[i+1]-2.0*a[i]; a[i] = a[i]+(r1-a[i])*omg; r0 = r1*r1; } 環境変数 OMP_NUM_THREADS に設定されたスレッド数で実される

35 メモリバウンドなアプリメモリバンド幅が必要なアプリ流体解析 QCD FFT 遠距離相互作の必要な計算これらのアプリはコモディティ CPU の性能化アイテムが必ずしも性能向上には結びつかないキャッシュの利 => 万能では無い

36 並列プログラミングモデル Message Passing 分散メモリシステム向け ( 共有メモリでも可 ) プログラマがメッセージのやりとりを記述するプロセッサ数に対してスケーラブルに書きやすいプログラミングは結構倒 Shared memory 共有メモリシステム向け共有メモリを介してデータをやりとりするシステムがデータのやりとりを担当 ( プログラマは気にしなくて良い ) プロセッサ数に対してスケーラビリティは稼ぎにくいプログラムは較的簡単 Message Passing Interface (MPI) OpenMP

VXPRO R1400®　ご提案資料

VXPRO R1400®　ご提案資料 Intel Core i7 プロセッサ 920 Preliminary Performance Report ノード性能評価ノード性能の評価 NAS Parallel Benchmark Class B OpenMP 版での性能評価実行スレッド数を 4 で固定 ( デュアルソケットでは各プロセッサに 2 スレッド ) 全て 2.66GHz のコアとなるためコアあたりのピーク性能は同じ評価システム