System Performance #6: CPU

work in progress.

@nikezono の読みながらメモ 兼 輪読会の補足資料.

私はペーペーの素人なのでおおいに誤りを含む. マサカリは歓迎

6.1 用語

ハードウェアスレッド

• ハードウェアスレッドとソフトウェアスレッドは違う. "スレッド"で混同しがち.
  • ハードウェアスレッドの数しか物理的に並列実行はできない
    • ハイパースレッディング等はパイプライン化等のアプローチでスレッド数を上げているので「論理コア」と呼ばれる.
    • 同じチップの同じ演算器を共用している.
  • 参考
    • lstopo は見て楽しい

CPU命令

• 自分が書いたコードがどんなCPU命令に落ちるかを考えるのが最適化の第一歩
  • Javascriptでも if(a == true) より if(a & 1)のほうが大抵の処理系でタブン高速?
  • CPU命令にはそれぞれベンダが出しているIPC(Instructions per cycle)の情報がある
    • 1クロックあたりその命令が何回できるかということ.
    • IPCが高い命令でプログラムを構成すると無駄クロックがない
      • というのが理想だがそれはかなり難しい.
      • 逆にCPI(Clocks per Instruction)を下げる努力をするのがわかりやすい.

6.2 モデル

6.3 CPUのメモリキャッシュ

• より効果なDRAMを高いレベルのキャッシュに使うのが基本.
  • だいたい32KB(L1) ~ 256KB(L2) ~ 2MB(L3) くらいが一般的?
  • アクセスにかかる時間については2章あたりにある.

6.2.3 CPUのランキュー

• ソフトウェアスレッドは待ち行列(キュー)に入る.
  • これで飽和率と使用率が計算できる.
  • キューはCPUコア毎に用意される.
    • なるべく同じスレッドを同じキューに入れる.これがアフィニティとかCPUバインドというやつ.
      • キャッシュの局所性を活かすだけでなく、コヒーレンスのコストも削れる.
      • たとえばあるLock bit一つが1000コアマシンの全L1キャッシュに乗っていたらもうコア間通信だけで日が暮れる.
      • そこで、そのロックを取得するロジックの書かれたスレッドは全て同じCPUに処理させることにしたらどうだろう
        • なんとメモリ(100ns)に書かなくてもL1キャッシュ(3ns)を操作するだけでロック処理が完結する
          • もちろんキャッシュコヒーレンスコストは無し.
        • いやそれって並列処理になってないやん... -> その通り. トレードオフがあるということ.
• スケーラビリティを論じるときは、並列数に対する性能向上率(アムダールの法則)を論じるのでは不十分.
  • この論文がイイことを言っている. 直列実行に対してどれだけ性能が出るかが重要.
    • 並列実行のためのオーバーヘッドで、スケールしているように見えても全体としては1マシン/1コアの性能に劣るなんてことはよくある.
    • もちろんそれが耐障害性とかのための"スケール"ならいいけども. スケーラビリティってなんだっけ？というのは考えるべき

6.3 コンセプト

クロックスピード

• クロックスピード(動作周波数)はCPUのパフォーマンスを示す指標としては完全ではない
  • 例をあげる
    • IPCが0.1の命令をループするプログラムを実行するとする
    • たとえば10GHzで動作する超高速なCPUでもクロックの9割はストールしている.
    • 1GHz CPUでIPCが1の命令をループして同じことができるとする.
      • パフォーマンスは同じ.
      • むしろこっちのほうが電力効率的に圧倒的に良い.
  • 他にもディスク/メモリ/ネットワークなどI/Oバウンドな処理であれば高速なクロックがあってもほぼストールだったりする.
    • このへんは perf とか time とか使うと詳細にプロファイルが見れて非常に良い.
      • 機能テストも重要だが,ベンチマークのスクリプト(shでよい)も書いておくと、パフォーマンスのリグレッションテストが出来てよい
      • あなたの知らないtime(1)の世界
      • perfの使い方

スーパースカラー

ここの数行だけでは理解するのが難しい.

勉強してきます.

命令幅

同上.

使用率

CPU使用率が100%に張り付いている == やばい

そう思っていた時期が私にもありました.

• 情報を運ぶのが主な目的のソフトウェアで100%に張り付いているのはやばい(I/Oバウンド)
• 情報を加工するのが主な目的のソフトウェアでは100%に張り付かないとやばい(CPUバウンド)

ユーザ時間/カーネル時間

CPUがどちらで時間を使っているかという指標.

htop とかすると赤くなっているのがカーネル時間.

• ひたすらディスク/ネットワークI/Oをループするプログラムだと恐らく真っ赤. CPUがストールしているから.
• ひたすらユーザランドで while ループを回してブロックデバイスを直に触ることもできる. こうすると緑一色だろう.
• この二つはどちらも同じことをしている. ランドが違うだけ.
• Web系だと基本的に赤いことが多いだろう.

プリエンプション

あるスレッドの次のタイムスライスを他のスレッドに使わせるようスケジューリングすること. 優先度付きのスケジューラだと優先度が高いスレッドは低いスレッドにはプリエンプションされない.

これもコンテクストスイッチという.

余談だがアクティブなスレッド数がコア数より少なければプリエンプションはめったに起こらない. CPUコアという有限の資源を時間で分割して奪い合う機構がプリエンプション.

ということでDB系のいわゆる「カリカリにチューニングしたベンチマーク」というやつでは、コア数==スレッド数でプログラムを実行するのが常識.

優先度の逆転

ロックを抱え込んでいる優先度の低いスレッドがプリエンプションされないようにする機構.

これも余談だがロックとプリエンプションの相性が非常に悪いことは想像に難くない.

• 100スレッドが実行されているとして、全てのスレッドが同じ処理ブロックを通るので、あるミューテックスを用いたとする.
  • このときコア数が一つしかないとする.
  • 100スレッドが順番にスケジューリングされるとする.
• 一番目のスレッドは時間内にロックを解放する処理まで到達できなかったとする. プリエンプションの時間が来た.
• 残りの99スレッドは全て、ロックが誰かに取られているため、起きてすぐsleep/yieldすることになる.
  • わざわざスレッド構造体をメモリからキャッシュに乗せて、離して、というのを99回繰り返すことになる.

ロックが一つでもこれなので、ロックが複数個あったり各スレッドの処理がバラバラであったりマルチコアであった場合のパフォーマンスの影響は非常に甚大かつ読み辛い.

これを解決するアプローチがLock-freeとWait-freeアルゴリズム/データ構造.

6.3.11 マルチプロセスとマルチスレッド

• マルチスレッドのほうがパフォーマンスにおいて優れている
  • たとえばPostgreSQL/Apache/Rails/Node.jsはマルチプロセスモデル
  • たとえばMySQL/NginX等がマルチスレッドモデル
  • マルチスレッドは実装が大変シンドい.
    • Node.jsのV8が回る uv_default_loop をマルチスレッド化しようという試みはいくつかあった様子
    • この論文などはその焼け野原の片鱗を語っている国内発表
  • マルチプロセスは共有メモリが使えない. このためロックオブジェクト等同期の扱いが難しい.
    • Inter Process Communicationするかファイルに書くかとか.

ワードサイズ

参考

サイズが大きい方がパフォーマンスはよくなり得るが、これは見かけほど単純な話ではない。サイズが大きいと、データ型によっては、未使用ビットの分、オーバーヘッドがかかることがある。

これの意味は、

• CPUが一命令でアクセスできるビット数が増える
  • 少ないアクセス回数でデータを引っ張ってこれる?
  • いや、1bitしか使わないランダムアクセス命令を連発したらどうか
  • ↑の参考にあるように1bitの変数がパディングされて64bitに整形されていたら?
    • 無駄にキャッシュヒット率が落ちるはず.
    • なので一概には言えない.

6.4 アーキテクチャ

書くのに飽きてきた.

CPUキャッシュ

複数のレベルのキャッシュが存在する意味は、参照の局所性に対応するため. キャッシュを考えるのは重要.

• トランザクションに関する業績でチューリング章を受賞したジム・グレイという人がいる
  • 国際会議SIGMODでTape is Dead Disk is Tape Flash is Disk RAM Locality is Kingという発表をした.
    • 面白いのでオススメ
    • SSDの時代が来てソフトウェアの世界も大きく変わるんじゃないかと騒いでいた時代に、変わらない指針を示した

ところで何故L1キャッシュの後にTLBがあるんだろう?

キャッシュライン

キャッシュとメモリ間でやりとりするデータのサイズ.

構造体のアラインメントをこれに沿うよう考えたりすると良い. 特にロックオブジェクトの偽共有を避けるためにキャッシュラインを考慮したりする.

このへんは前回の5.2章参照.

キャッシュコヒーレンシ

このへんを参照.

MESIプロトコルだけ動きを覚えている.

並列分散処理において同期を取るというのはこのキャッシュコヒーレンスの実装と本質的に近いと思っている.

6.4.2 ソフトウェア

完全に飽きました

6-12の図は最高にわかりやすい.

Linuxのスケジューラ

HWクロックが割り込み信号を送り、毎回カーネルが起きる.

最も優先度の高いスレッドにtickを割り振っていく. (前述した優先度逆転の問題がある(

Solarisのスケジューラ

HWクロックが割り込み信号を送り、毎回カーネルが起きる.

タイムスライスの経過をチェックし,与えられた時間は処理させる.

与えられた時間が過ぎると優先度が下がっていく. 次回tick以降からプリエンプションがかかる可能性がある.

スケジューリングクラス

ユーザがスレッドに優先度を付加することもできる. いくつかのポリシーに従うスケジューリングの分類がある.

• RT: ユーザレベル/カーネルレベルのプリエンプションが起こる. リアルタイムタスクを低いレイテンシでスケジュールさせることを狙う.
• O(1): 実装の経緯からそう名付けられた. I/Oバウンドなワークロードの優先度を上げている.
• CFS: キューではなく赤黒木でCPU時間をソートしている. これにより細かいCPU時間を必要とするワークロードを先に流すことができる.

スケジューラの実際の挙動は以下の分類がある.

• RR: ラウンドロビン.
• FIFO: 字のごとく
• NORMAL: 定義されたスケジューリングクラスに基づいて動かす.
• BATCH: 字のごとく

Solarisのスケジューリングクラスについては割愛.

アイドルスレッド

OS上で用意する、他に実行可能タスクがないときに実行するスレッド. 優先度が最も低い. 省電力モードのフラグを立てたりする.

6.5 メソドロジ

以下の順序で分析するのがオススメらしい

1. パフォーマンスモニタリング
   • 使用率と飽和を調べる.
   • 飽和にはロードアベレージかスケジューラのレイテンシを使う.
   • サンプリング時間がチューニングパラメータ.
2. USEメソッド
   • 使用率と飽和とエラーを調べる.
   • ECCのために使用率が落ちていることもあるので注意
   • クラウド環境では使用率が100%にならなくとも物理的に上限に達している可能性がある(noisy neighbor).飽和を見るのが良い.
3. プロファイリング
   • DTraceやperfでサンプリングする.
4. マイクロベンチマーキング
   • CPU/メモリ/言語処理系/OSのシステムコール回数など.
   • マイクロベンチマーキングとはいえ実際の動作環境とどこまで合わせられるかを考える.
     • マルチスレッドをサポートしているツールかどうかなど.
5. 静的分析

6.6 分析

ツールの話.割愛.実機でデモしましょう

6.7 実験

6.6が分析ツールの話なら、こちらはワークロードジェネレータの話.

• アドホックテスト: 単純なwhileループ. これでも十分ツールのテストには役に立つ
• Sysbench: 素数の計算等々のワークロードが用意されている.