読者です 読者をやめる 読者になる 読者になる

tom__bo’s Blog

情報系学生がプログラミングしたり、ボルダリングしたりボルダリングしたことを書くブログ。もはやダイアリー

Systems Performance 読んでいく (6章 その2)

Linux SystemsPerformance Performance

Systems Performance: Enterprise and Cloudを読んでいく。

前回の続き。
6章前半部分その2。

6.4 Architecture

この節ではCPUのアーキテクチャと実装をハードとソフトの両面から紹介する。 このトピックはあフォーマンス分析のバックグラウンドとしてまとめているので、より詳しい内容はベンダーのマニュアルとOSの内部を参照するように。

6.4.1 Hardware

CPUのハードウェアはプロセッサとそのサブシステム、複数のプロセサのためのCPU interconnectからなっている。

[processor]

一般的な2コアCPUのプロセッサを以下に示す。

f:id:tom__bo:20161109153132p:plain

control logicと書かれているcontrol unitはCPUの心臓である。 この例ではfloating-point unitとL3 cacheを共有するように書いている。実際のコンポーネントはプロセッサの型とモデルに依存する。

他のパフォーマンスに関連するコンポーネントを以下に示す。

  • P-cache
  • W-cache
  • Clock-Timestamp counter
  • Microcode ROM
  • Temperature sensors
  • Network interfaces

[CPU Cache]

様々な方法でCPUはキャシュを提供するが、以下に一般的なキャッシュアクセスの様式を示す。

f:id:tom__bo:20161109153201p:plain

キャッシュ容量は徐々に大きくなっており、1978年からの経過をいかに示す。

f:id:tom__bo:20161109153214p:plain

[Latency]

複数のレベルのキャッシュは適したサイズとレイテンシになるように提供されている。 L1キャッシュは数CPUサイクル、L2キャッシュは十数サイクル、メインメモリは60nsでおよそ240サイクルである。さらにMMUによる翻訳がレイテンシに加わる。
Intel Xeon E5620(2.4GH)のLMbenchを用いてマイクロベンチマークを取った結果を以下に示す。

f:id:tom__bo:20161109153233p:plain

このグラフは両対数になっている。 段状になっているのはそこであるキャッシュレベルの容量を超えたことを示している。

[Associativity]

associativityは新しいエントリ(メモリアクセスの結果)をどのようにキャシュに制約するかの特性である。

  • Fully associative
    • キャッシュは何処にでも配置できる。
    • 例えばLRUアルゴリズムはキャッシュ全体から一番使われていないものを犠牲にする
  • Direct mapped
    • それぞれのエントリは一つの場所にしか配置されない
    • 例えばメモリアドレスのハッシュがこれに相当する
  • Set associative
    • キャッシュのサブセットは何かしらのアルゴリズムによって配置先を決定される。
    • 例えば"four-ways set associative"マッピングは4つの配置可能な場所を列挙しその中で最適な場所に配置する

CPUキャッシュはfully associative(実行のコストが高い)とDirect mapped(キャッシュヒット率が低い)の中間を取ってset associativeがよく使われる

[Cache Line]

他のCPUの特性として、cache line sizeがある。 これは、ある入ん胃のバイトデータを1つのユニットとして保存、転送する仕組みである。

[Cache Coherency]

メモリの内容は同時に異なるCPUでキャッシュされていることがある。 そこで、メモリの内容が書き換えられた倍、他のCPUに変更を伝える必要がある。このプロセスは"cache coherency"と呼ばれ、常に正しいデータになるように保証している。

[MMU]

MMUは仮想アドレスから物理アドレスへの変換を行っている。
一般的なMMUを以下に示す。

f:id:tom__bo:20161109153453p:plain

このMMUはon-chipなTLBをアドレス変換のキャッシュとして利用している。ここでのキャッシュミスはメインメモリの"page table"によって解決する。この部分はMMuが直接呼び出すようになっている。

[Interconnects]

マルチプロセッサアーキテクチャでは、プロセッサ同士は共有システムバスか、インターコネクトのどちらかによってつながっている。 これは、メモリアーキテクチャに関連したuniform memory access(UMA)またはNUMAとして7章メモリで議論する。

"front-side bus"と呼ばれる共有システムバスを以下に示す。

f:id:tom__bo:20161109153509p:plain

これはCPUが増えるに連れて競合が発生してしまうので、スケーラビリティに問題がある。近年では、NUMAとCPUインターコネクトが使われている。

インターコネクトは、プロセッサ以外にもI/Oコントローラなどを接続できる。 例えば、IntelのQuick Path Inter connect(QPI)やAMDのHyper Transport(HT)等がある。
4プロセッサのQPIの例を以下に示す。

f:id:tom__bo:20161109153521p:plain

これにより、プロセッサ間のプライベートなアクセスや共有システムバスと比較して、高いバンド幅を実現できる。

[CPU Performance Counters]

CPU Performance Counters(CPCs)は様々な名前で呼ばれている。
Performance instrumentation Counters(PICs)やPerformance monitoring unit(PMU)やhardware events, performance monitoring eventsなどだ。
これらは低レベルのCPUアクティビティをプログラムによって取得できるレジスタである。

これらには特に以下のものも含む。

  • CPU cycles-per-instruction
  • CPU instructions
  • L1, L2, L3 cache accesses
  • Floating-point unit
  • Memory I/O
  • Resource I/O

それぞれのCPUはこれらのイベントをプログラムして取得できる2~8のレジスタを持っている。

シンプルな例として、Intel P6 familyのプロセッサでは、model-specific registers(MSRs)パフォーマンスカウンタを提供している。 このうち2つはカウンターで読み取り専用。 他の2つのMSRsはプログラムでき、"event-select"MSRsと呼ばれる読み書き可能なレジスタである。 32bitのevent-select MSRを以下に示す。

f:id:tom__bo:20161109153533p:plain

カウンタはEvent SelectとUMASKによって識別される。

インテルのプロセッサマニュアルを見ると、十数個のイベントがリストアップされている、代表的なものを以下に示す。

f:id:tom__bo:20161109153541p:plain

ここでは観測可能な異なるタイプのものを選んでリストにしている。
新しいプロセッサほど、これらの種類は多く、Intel Sandy Bridgeファミリーでは、カウンタのタイプだけでなく、レジスタも3つの固定、4つのプログラム可能なものがハードウェアスレッドごとに、そして、8つのプログラマブルカウンタが"general-purpose"としてコアごとにある。

6.4.2 Software

カーネルソフトウェアは、スケジューラ、スケジューリングクラス、そしてidleスレッドを含むCPUsをサポートしている。

[Scheduler]

カーネルのCPUスケジューラの中心的な関数を以下に示す。

f:id:tom__bo:20161109153603p:plain

ここには

  • Time sharing
  • Preemption
    • 優先度の高いスレッドが実行可能になったときに、スケジューラは現在実行中のスレッドを停止する
  • Load balancing
    • 実行可能なスレッドをidle状態やbusy状態でないCPUsに移動する

等がある。

この図ではCPU毎の実行キューを示している。 また簡単なまとめをカーネルの実際の関数名を元に示す。

[Linux]

Linuxでは時間の共有はscheduler_tick()と呼ばれるシステムタイマー割り込みによってなされている。これはスケジューラクラス関数を呼び出していて、優先度とCPU単位時間(time slice)の期限を管理している。
プリエンプションはスレッドが実行可能になり、check_preempt_curr()関数が呼ばれたときにトリガーされる。 ロードバランシングはload_balance()関数によって実行される。
スレッドの切り替えは__schedule()によって行われ、これはpick_next_task()を通して優先度の最も高いものを選択する。

[Scheduling Classes]

スケジューリングクラスは実行中のスレッドの振る舞いを管理している。 特に優先度とon-CPUの時間がtime-slicedを過ぎたかどうか(time quantumとしても知られる)などを監視する。

以下にスレッドの優先度のレンジを示す。

f:id:tom__bo:20161109153616p:plain

ユーザレエbルデのnice値はユーザレエbルニのみ影響する。 これらはスレッドのstatic priorityで、スケジューラが計算するdynamic priorityとは別の物である。 nice値は低いほど優先度が高い。

[Linux]

Linuxシステムにおいて、スケジューリングクラスは

  • RT
    • リアルタイムな負荷のために、固定の高い優先度を提供している
    • カーンルはRTタスクを低いレイテンシでディスパッチするために、ユーザとカーネルレベルのプリエンプションを許可している。
  • O(1)
    • O(1)スケジューラはLinux2.6でのデフォルトスケジューラとして導入された
    • これ以前のスケジューラはタスク数nに対してO(n)で走査をしていたが、O(1)で行える
  • CFS
    • Linux2.6.23で加えられた完全に康平なスケジューリングアルゴリズム
    • ユーザプロセスのデフォルトのスケジューリングアルゴリズム
    • 以前のようなランキューではなく、CPUの実行時間をキーとした赤黒木でスケジューリングを行っている

がある。

スケジューラクラスはsched_set_scheduler()を呼ぶことでscheduler policyを設定する。 RTクラスはSCHED_RRとSCHED_FIFOポリシーをサポートし、CFSクラスがSCHED_NORMALとSCHED_BATCHをサポートしている。

以下にポリシーを示す。

  • RR
    • SCHED_RRはラウンドロビンのスケジューリングである
    • 一定の時間間隔分、実行したらランキューの最後に移動する
  • FIFO
    • SCHED_FIFOFIFOのスケジューリングである
    • 実行中のタスクより優先度の高いタスクが来ない限り、実行中のタスクが自発的にCPUを明け渡すまで実行を続ける
  • NORMAL
    • SCHED_NORMALは以前はSCHED_OTHERとして知られていた
    • ユーザプロセスのデフォルトのスケジューリングアルゴリズム
    • スケジューラはスケジューリングクラスを元に優先度を動的に調整する
  • BATCH
    • SCHED_BATCHはSCHED_NORMALと煮ているが、CPUバウンドなタスクを想定していて、他のI/Oバウンドの関連の負荷による割り込みを受け付けない。

スケジューリングアルゴリズムは現在でも研究がされており、hyperthreading-awareやtemperature-awareなどのハードウェアの他の要因も考慮するようなものもある。
スレッドに実行すべきものがないときはidle task(idle thread)と呼ばれるものを実行する。