チューニング技法入門 : チューニングの基礎太田幸宏 ( 高度情報科学技術研究機構 ) 教科書青山幸也チューニング技法虎の巻 ( 平成 28 年 8 月 1 日版 ) 質問について ( 主に ) 休憩時間に受け付けますもご利用ください

(1)

チューニング技法入門

_{: チューニングの基礎}

太田幸宏

_{(高度情報科学技術研究機構)}

E-mail: yota@rist.or.jp 教科書青山幸也「チューニング技法虎の巻」(平成28年8月1日版) 質問について (主に)休憩時間に受け付けます E-mailもご利用ください (後日, 回答します)

(2)

2018年11月一般財団法人高度情報科学技術研究機構本資料を教育目的等で利用いただいて構いません。利用に際しては以下の点に留意いただくとともに、下記のヘルプデスクにお問い合わせ下さい。  本資料は、構成・文章・画像などの全てにおいて著作権法上の保護を受けています。  本資料の一部あるいは全部について、いかなる方法においても無断での転載・複製を禁じます。  本資料に記載された内容などは、予告なく変更される場合があります。  本資料に起因して使用者に直接または間接的損害が生じても、著作者はいかなる責任も負わないものとします。問い合わせ先：ヘルプデスク　helpdesk[-at-]hpci-office.jp（[-at-] を＠にしてください）

(3)

前置き

_{1: 教科書との対応}

タイトルとトピックスタイトル例) １－２経過時間とCPU時間 “１－２”は節番号に対応 (ページ番号ではない) トッピクス例) 経過時間 (1-2) “1-2”はページ番号 (教科書の各ページの最下段に表示) 文献番号は教科書に準拠 (A-2 参考文献) たとえば, [1] と表示リストにない場合は, その度提示

(4)

前置き

_{2: 教科書全般を通して}

時間に焦点プログラムの実行時間(のどの部分)を、どのようにして、どれだけ削減できるか、に着目具体例 (モデル) による理解 チューニング技法 _{(の一部)の理解: ハードウェアの知識を要求} 教科書本質を取り出したモデルで理解 (厳密さは多少犠牲に) 専門書 [27, 31] を理解するための土台にサンプルコード (自習用) scalar-sample.tar.gz

alloc2d, endian, ET, mattp, prof-ex, stripmining, thrashing, timer, timer-res, unroll

(5)

前置き

_{3: C/C++に関する補足情報}

教科書(及び本セミナー): Fortran ベースに解説 C/C++ についても共通事項が多い差異については適宜コメント (例: 配列のデータ格納パターン) CとFortranの差異 (HPCの視点) → [27]の第1章を参照参考資料: 本資料のC版 (コード例をCで記述) C++による科学技術計算コードの書き方 留意点に関するまとめ

G. Hager and G. Wellein, Introduction to High Performance Computing for

Scientists and Engineers (CRC Press, 2011) 2.5節

(6)

前置き

_{4: Fortranについて}

便利な参考書

基本 [7]

各種Tips

A. Markus, Modern Fortran in Practice (Cambridge, 2012) Fortran Wiki; http://fortranwiki.org/fortran/show/HomePage

包括的

(7)

アウトライン

第１章チューニングの基礎経過時間, CPU時間, ホットスポット第２章コンパイルオプションコンパイラ(最適化)を上手に使う第３章パフォーマンス測定方法時間計測の方法, ホットスポットの特定第４章キャッシュチューニングメモリ階層(キャッシュの役割), キャッシュ(手早く取れるデータ)の活用第５章その他のチューニング ”高価”な作業・無駄な計算の削減, 条件分岐(if文),ループアンローリング第７章数値計算ライブラリーよく調整されたコード利用(BLAS, LAPACK, FFTW)

(8)

１－２経過時間と

_CPU時間

経過時間 (1-2) 計算ジョブの開始から実行までの時間 (Elapsed time) 別のジョブが動く場合 → 待ち時間発生 → 経過時間の遅れ本書:「別のジョブが全く動いていない」という設定で考察 CPU時間 (1-2) ユーザーCPU時間ユーザプログラム自体が消費システムCPU時間オペレーティングシステムが消費 (入出力割込み,etc.)*) → 通常はわずか → 無視可能 *) 内田啓一郎, 小柳滋「コンピュータアーキテクチャ」(オーム社)

**) Patterson & Hennessy「コンピュータの構成と設計: ハードウェアとソフトウェアのインタフェース」第5版 (日経BP社) 第1章

Memo

ユーザ_{CPU時間とシステムCPU時間を正確に区別することは難しい}

(9)

I/O時間 (1-2) (典型的には) [I/O時間] = [経過時間] - [CPU時間] (図1-2-1) ユーザプログラムによるI/O時間ファイルや画面への入出力 (結果の書き出し, など) ページングによるI/O時間ディスク(ページスワップスペース)とメモリ間の入出力(6章) 例. [実際のメモリ] < [実行可能モジュールが必要とするメモリ] 128 MBytes a.out: 256 MBytes 必要

１－２経過時間と

_CPU時間

Memo

I/O処理にもCPU時間は(多少)必要

CPU時間 I/O時間経過時間

(10)

１－３ホットスポットとチューニング

Case study: 3重ループ (図1-3-1) 最も内側の部分 (処理3) が全体のほとんどを占める → ホットスポット処理1の寄与はわずか → 無視してよいホットスポットとは (1-3) プログラムの実行時間の主要部 (図1-3-1) 本書 (単体チューニング): プログラム内でCPU時間を特に多く消費する限られた部分→ CPU時間のみに焦点 (HPCの主要課題) cf. I/O時間を減らすチューニング: I/Oチューニング (6-1節, 6-2節) 処理1: 100回 CPU時間 I/O時間経過時間処理2: 10000回 処理3: 1000000回 $ ./a.out a=100 b=10000 c=1000000

(11)

１－３ホットスポットとチューニング

Case study: チューニングのターゲット (図1-3-2) サブルーチンAのCPU時間を0.5倍 → 全体で35%のパフォーマンス向上 A以外のCPU時間を0.000001倍 → 全体で高々30%のパフォーマンス向上パフォーマンス向上の目安ホットスポットとは (1-3) ホットスポットの部分のみをチューニング (図1-3-2) 最小の努力で最大の効果を上げる CPU時間の割合 70% 15% 5% 5% 5% サブルーチンA B C D E

(12)

１－３ホットスポットとチューニング

ホットスポットとは (1-3) ホットスポットの部分のみをチューニング (図1-3-2) 最小の努力で最大の効果を上げる Memo ● CPU (コア) 1個のみを使用する場合のチューニング → CPU時間に着目が妥当

● 並列計算: コア数が増加するとCPU時間は増大 (by definition)

(13)

１－３ホットスポットとチューニング

チューニングの手順 (1-3, 8章) (0) 入力データの準備 (8-1, 8-2) ✔ メモリに乗る配列サイズの設定 ✔ 計算実行時間の短縮 (ex. タイムステップを短く, 収束条件を緩く, etc.) 配列サイズ縮小: 好ましくない (ホットスポット変更の可能性) (1) ホットスポットの特定 (3章) (2) ホットスポットに対してチューニング ✔ 数値計算ライブラリの利用 (7章) ✔ ループにおける配列アクセスパターンの検証 (4-2節) ✔ “高価な”処理 _{(除算や組込関数) や無駄な計算の削減 (}_{5-1節, 5-2節}₎ ✔ ループにおけるロード/ストアの削減 (5-5節) (3) 結果が正しいこと, パフォーマンスが向上の有無を確認結果の不正 or パフォーマンスの向上不足 → (2)へ戻る参考情報 (RISTの支援活動) 高速化ノウハウ集: http://www.hpci-office.jp/pages/tuning_knowhow

(14)

２－２パフォーマンスに関するコンパイルオプション

最適化のためのコンパイルオプション (2-2) パフォーマンス向上のための操作(最適化)を指定 ”自動的にチューニング”: 演算順序の変更, 無駄な計算の削減, etc. 最適化オプションの種類 “-O” (Optimizeの意味) による指定が多い

大きい数字 → 最適化レベルの上昇 (例: -O0 < -O1 < -O2 < -O3 )

Memo ● 最適化の意味と指定法コンパイラに依存 → 詳細はマニュアル (ex. gcc --help=optimizer) ● 最適化 → コンパイル時間の増大プログラムの文法エラー修正では”最適化なし”が効率的 ● コンパイラが自動的に最適化する → 何故チューニング技法を学ぶか? 最適化の内容 _{(副作用の有無)}_,最適化の阻害要因 ₍_5-3節_{) を把握} コンパイラを上手に利用する知識

(15)

２－２パフォーマンスに関するコンパイルオプション

最適化のレベルを高くした場合の副作用 (2-2) 計算結果の変化, コンパイラ自体のバグ発生 (誤ったコード生成) 最適化オプションの指針 →「そこそこ」速くて安全最適化オプションを何も指定しないとどうなるか (2-2) 挙動はコンパイラ依存 → マニュアルの確認は必須 (1) 最適化を全く行わず, パフォーマンスが悪くなる (2) 標準的な最適化オプションが指定される (3) 最も高度な最適化オプションが指定される (危険な選択の可能性) Memo ● コンパイラのマニュアルで確認すべき事項最適化オプションの指定と種類最適化レポート (診断レポート) の表示方法レポートを上手に使う → 最適化の阻害要因の把握に繋がる

(16)

３－１ジョブ全体のパフォーマンス測定方法

timeコマンドの使用方法 (3-1)

UNIXやLinuxで提供されるコマンド → ジョブ全体の経過時間とCPU時間

ディスプレイに結果が出力 (図3-1-2)

Windowsユーザ: Cygwin, MinGW, Bash on Ubuntu on Windows, etc.

ジョブ全体のパフォーマンスを測定する場合の注意 (3-1) 他のジョブが流れていないことを確認 $ time ./a.out TEST real 0m0.005s user 0m0.002s sys 0m0.002s

(17)

３－２プログラムの一部分のパフォーマンス測定方法

経過時間/CPU時間の測定方法 (Fortran )*) ₍_3-3₎

基本的な考え方: 測定部分の前後で時間を取得→時間の差を計算経過時間: SYSTEM_CLOCK (Fortran90で提供) (図3-2-5)

CPU時間: CPU_TIME (Fortran95で提供) (図3-2-7)

Cのタイマールーチンを呼び出す

サンプルコード: timer

経過時間を測定したい部分

(18)

３－２プログラムの一部分のパフォーマンス測定方法

経過時間/CPU時間の測定方法 (Fortran )*) ₍_3-3₎

基本的な考え方: 測定部分の前後で時間を取得→時間の差を計算経過時間: SYSTEM_CLOCK (Fortran90で提供) (図3-2-5)

CPU時間: CPU_TIME (Fortran95で提供) (図3-2-7)

Cのタイマールーチンを呼び出す

*) M. Metcalf et al., Modern Fortran explained (Oxford) Chap.8

Memo

● タイマーの精度 (resolution): 信頼できる計測時間を把握

→ 短すぎる計測時間で性能向上を議論すべきではない

(19)

３－４ホットスポットの特定方法

ホットスポットを特定するためのツール (プロファイラ) (3-6, 3-8)

Function profiling: サブルーチン (or 関数) 単位の情報収取

典型的なツール: gprof (GNUのパッケージの一部) (3-4-3節)

admin@myserver MSYS ~ $ man gprof

"gprof" produces an execution profile of C,

Pascal, or Fortran77 programs... The profile data is taken from the call graph profile file

(gmon.out default) which is created by programs that are compiled with the -pg option of "cc", "pc", and “f77” ...

● 分析結果はgmon.outから取得

● コンパイル時に「-pg」オプションを付ける

(20)

３－４ホットスポットの特定方法

admin@myserver MSYS ~ $ gcc -pg -O3 sample.cc

Case study: gprofによる性能評価の流れ (3-8)

1. コンパイル

2. 実行・分析

admin@myserver MSYS ~

$ gfortran -pg -O3 sample.f90

admin@myserver MSYS ~

$ ./a.out 実行後, gmon.out, が生成

3. データ取得 admin@myserver MSYS ~

$ gprof ./a.out > prof.out

分析結果をテキストファイル,

(21)

$ cat prof.out Flat profile:

Each sample counts as 0.01 seconds.

% cumulative self self total

time seconds seconds calls us/call us/call name 78.55 58.43 58.43 1000000 58.43 58.43 sub3_ 14.63 69.31 10.88 200000 54.40 288.12 sub2_ 6.64 74.25 4.94 100001 49.40 166.26 sub1_

0.19 74.39 0.14 _mcount_private

% the percentage of the total running time of the time program used by this function.

cumulative a running sum of the number of seconds accounted seconds for by this function and those listed above it. self the number of seconds accounted for by this seconds function alone. This is the major sort for this listing.

３－４ホットスポットの特定方法

典型的なツール: gprof (GNUのパッケージの一部) (3-4-3節) → サブルーチンごとのCPU時間(図3-4-3), 呼び出し回数, コールグラフ測定用ルーチンの稼働時間 →無視すべきホットスポットサンプルコード: timer 0.01秒毎に(関数の使用状況を)サンプリング することで計測 (OSの割り込み機能を利用)

(22)

３－４ホットスポットの特定方法

→ サブルーチンごとのCPU時間, 呼び出し回数, コールグラフ (図3-4-4)

Call graph (explanation follows)

granularity: each sample hit covers 4 byte(s) for 0.01% of 74.39 seconds index % time self children called name

<spontaneous> [1] 99.8 0.00 74.25 MAIN__ [1] 10.88 46.74 200000/200000 sub2_ [3] 4.94 11.69 100000/100001 sub1_ [4] 11.69 0.00 200000/1000000 sub1_ [4] 46.74 0.00 800000/1000000 sub2_ [3] [2] 78.5 58.43 0.00 1000000 sub3_ [2] 10.88 46.74 200000/200000 MAIN__ [1] [3] 77.5 10.88 46.74 200000 sub2_ [3] 46.74 0.00 800000/1000000 sub3_ [2] 図3-4-4 メイン関数の情報 mainから呼び出す関数の情報 sub3の情報 sub3から呼び出す関数の情報 サブルーチン/関数間の関連図を作成したい場合に便利

(23)

３－４ホットスポットの特定方法

Memo

● Function profiling (gprof など)

サブルーチン内のどの_{line (行) が高コストか, はわからない} ● 詳細情報を調べたい場合 → オープンソースのツール例 (Linuxの場合) perf (https://perf.wiki.kernel.org/index.php/Tutorial) Oprofile (http://oprofile.sourceforge.net/news/) ● ハードウェア情報 [31] マシン環境によっては, 収集および分析ツールが提供*) FLOPS (3-3節), キャッシュミス率(4-3節), メモリバンド幅**)_{, など} perfやOprofileでも可能 (アーキテクチャに依存) ● 手動でタイマー挿入 (3-2節) の意義プロファイラ利用で発生するオーバヘッドが大きい場合は有用

*) S. V. Moore et al., Software Interface to Hardware Counters, in Performance Tuning of Scientific Applications (CRC press)

(24)

まとめ

第１章チューニングの基礎 [経過時間]=[CPU時間]+[I/O時間] ホットスポット・チューニング (最小の努力で最大の効果を) 第２章コンパイルオプションコンパイラによる最適化を上手に使う「そこそこ」速く安全な選択を第３章パフォーマンス測定方法タイマーによる時間計測プロファイラの利用 (ホットスポットの特定へ)

(25)

(26)

１－３ホットスポットとチューニング

ホットスポットとは (1-3) Memo ● 科学技術計算におけるホットスポットの典型例連立一次元方程式ソルバー, 固有値ソルバー, 高速フーリエ展開, etc. ● ホットスポットは常にあるか? 顕著に現れないこともある ● 「[ホットスポット] = [プログラムの機能における主要部]」か? 成立するとは限らない (5-2-1節)

(27)

２－４デバッグに関するコンパイルオプション

デバッグ時に役に立つオプション (2-6) 通常のコンパイル/リンクでエラーにならない問題を検出サブルーチンコール間の矛盾, サブルーチンコールの引数不一致パフォーマンスは低下 → デバッグ時のみの指定を推奨演算例外 ₍_2-6₎ 浮動小数点 (実数) の演算例外[31] オーバーフロー, アンダーフロー, ゼロ除算, 無効演算演算例外に対する(デフォルトの)対処法 → マシン環境依存 (1) メッセージを表示して異常終了 (2) 計算を続行 (結果に文字InfやNaNが表示)*) コンパイルオプションで(1)に変更可の場合パフォーマンスの低下が軽度 → (1) の設定を推奨

(28)

３－３パフォーマンス測定の考慮点

人工的なプログラムでのパフォーマンス測定 (3-4) 典型例: プログラム or サブルーチンの特定部分 (図3-3-1) 動作確認とパフォーマンスデータ取得特定部分のみ抽出 → 適切に計測されない場合 (例: 経過時間がゼロ) Case study: 人工的なコードにおける対策 (図_3-3-1₎ Line8: 最初のサブルーチンコールで計算 時間が遅くなる可能性を排除 (図3-3-1の①) Line 10: ループ追加により計算時間を長く することで確実な計測 (図3-3-1の③) Line 14: “スマート”なコンパイラ対策 (=不要な計算を削除) のため配列Aの使用を「見せかける」(最適化の抑制) (図3-3-1の⑥)

(29)

３－３パフォーマンス測定の考慮点

MFLOPSの求め方(3-5)

FLOPS (Floating-point Operations Per Second): マシン性能を示す一つの指標ハードウェア情報を入手可能なプロファイラで計測可能

Case study: 手作業によるループに対するFLOPS の estimation (図3-3-3)

(1) ループ内における浮動小数点演算 (+, - , *) の回数をカウント (2) ループの実行にかかったCPU時間(sec.)をタイマールーチンで計測 (3) FLOPS = [ループの反復回数] × [(1)の数値] / [(2)の数値] MFLOPS (メガフロップス) → [FLOPS] ×10-6 GFLOPS (ギガフロップス) → [FLOPS] ×10-12 注意_{1: 整数演算のみ → FLOPSはゼロ} 注意2: 除算(/)も1回としてカウントすることが多い*)

(30)

３－４ホットスポットの特定方法

ホットスポットを特定するためのツール (プロファイラ)

Memo+α

● gprofのオプション (https://www.ibm.com/developerworks/jp/linux/library/l-gnuprof/index.html) 関数ごとのコストのみ表示 (flat): gprof -p

コールグラフのみ取得 (call graph): gprof -q

コストの注記付きソースを生成 (annotated): gprof -A (cf. gcov) ● perf およびOprofile

Linuxカーネルを利用したサンプリングインストールの有無の確認 (例: perf)

Red Hat, Cent OS: yum list installed |grep -E -i “perf”

Ubuntu (>14.04): apt list --installed |grep -E -i “perf”

インストール (システム管理者のみ; 例: Ubuntu) (cf. ソースからコンパイルも可能) perf: sudo apt install linux-tools-common

Oprofile: sudo apt install oprofile

使い方

perf: B. Gregg 「詳解システム・パフォーマンス」 (オライリー・ジャパン, 2017) 6章 Oprofile: 吉岡弘隆他著, DeBug Hacks (オライリー・ジャパン, 2009) 6章

(31)

３－４ホットスポットの特定方法

ホットスポットを特定するためのツール (プロファイラ)

Memo+α

● perfの使用例

基本: perf record a.outでプログラム実行 → 統計情報がperf.dataに集約

→ perf reportでperf.dataからデータ取得サブルーチン毎のコスト (cpu使用率)取得

perf record --event=cpu-cycles a.out

perf report --header -stdio --input=perf.data → 標準出力にデータ出力 (gprofに相当) ユーザのサブルーチンのみのコストの取得

perf record --event=cpu-cycles:u a.out キャッシュミス率の取得

perf record --event=cache-misses a.out コールグラフの取得

perf record --call-graph dwarf a.out

perf report --stdio --input=perf.data --call-graph

注釈付き (コスト, 機械語命令) ソースの生成 (要デバッグオプション「-g」) perf annotate --input=perf.data --source --symbol=<symbol>

<symbol>: 対象とするサブルーチン名 (perf reportの出力のSymbol欄に従う) 注釈付き (コスト, 機械語命令) ソースの生成 + 高コストの行数表示

perf annotate --input=perf.data --print-line --source --symbol=<symbol>

チューニング技法入門 : チューニングの基礎太田幸宏 ( 高度情報科学技術研究機構 ) 教科書青山幸也 チューニング技法虎の巻 ( 平成 28 年 8 月 1 日版 ) 質問について ( 主に ) 休憩時間に受け付けます もご利用ください