レイテンシとバンド幅

最適化

最適化

基本

最適化

基本

• アルゴリズムの改善
  

最適化

基本

• アルゴリズムの改善
  まずこれ
  

最適化

基本

• アルゴリズムの改善
  まずこれ
  大事
  

最適化

基本

• アルゴリズムの改善
  まずこれ
  大事
  例: 計算量 O(N^2) → O(N) とか
  

最適化

基本

• アルゴリズムの改善
  まずこれ
  大事
  例: 計算量 O(N^2) → O(N) とか
  

  N=1000 でも 1000倍近く速くなる

最適化

でもこれだけじゃない

最適化

でもこれだけじゃない

• 何もせずに待ってる時間がある

最適化

でもこれだけじゃない

• 何もせずに待ってる時間がある
• サーバーへ要求を送って返事を待ってる時間

最適化

でもこれだけじゃない

• 何もせずに待ってる時間がある
• サーバーへ要求を送って返事を待ってる時間
• disk 読みだし待ち時間

最適化

でもこれだけじゃない

• 何もせずに待ってる時間がある
• サーバーへ要求を送って返事を待ってる時間
• disk 読みだし待ち時間
• システムコールオーバーヘッド

最適化

でもこれだけじゃない

• 何もせずに待ってる時間がある
• サーバーへ要求を送って返事を待ってる時間
• disk 読みだし待ち時間
• システムコールオーバーヘッド
• メモリアクセス待ち

最適化

でもこれだけじゃない

• 何もせずに待ってる時間がある
• サーバーへ要求を送って返事を待ってる時間
• disk 読みだし待ち時間
• システムコールオーバーヘッド
• メモリアクセス待ち
• キャッシュアクセス待ち

latency

latency

latency

latency

• 辞書: latency: 潜伏、潜在

latency

latency

• 辞書: latency: 潜伏、潜在
• 辞書: latency period: 潜伏期間

latency

latency

• 辞書: latency: 潜伏、潜在
• 辞書: latency period: 潜伏期間
• wikipedia:
  ある原因から、
  その効果が観察されるまでの遅延時間

latency 実例 (その1)

registerアクセス	0.25ns
L1 cache アクセス	1ns
L2 cache アクセス	3ns
L3 cache アクセス	4ns
関数呼び出し	5ns
memory アクセス	70ns
I/O syscall (cache hit)	300ns

※CPU種別や時代によって大幅に変わります。

latency 実例 (その2)

Infiniband LAN RTT	18μs
1000BASE-T LAN RTT	100μs
東京←→名古屋 RTT	8ms
disk アクセス	10ms
東京←→米国西海岸 RTT	100ms
東京←→米国東海岸 RTT	180ms

※CPU種別や時代によって大幅に変わります。

latency and bandwidth

latency が大きいと

• 反応が遅い
• バンド幅が出なくなることも
  データ送信→ACK待ち→データ送信→ACK待ち
  ACK待ちの間、何もしていない

latency and bandwidth

傾向

バンド幅

時代が進むと、どんどん向上する

レイテンシ

時代が進むと、ゆっくりと向上する

メモリ階層

ディスク/メモリ/L3 cache/L2 cache/L1 cache
時代が進むと、階層間の差が開く
一定以上に差が開くと、中間に階層が増える

改善策

今日の話

というわけで、今日は、latency に起因する問題に対する解決策のパターンを あれこれ紹介します。

改善策

まとめて回数を減らす

例:

• stdio
  システムコールread(2)/write(2)呼び出し回数が1/8192とか
• NFSでrsizeやwsizeを拡大
• 一般的に、バッファサイズ拡大

バンド幅: 向上
latency: (厳密に言うと)ちょっと悪化

改善策

read ahead (その1)

例:

• CPU - メモリ prefetch
  メモリアクセスパターン （シーケンシャル、固定サイズ飛び飛び…etc）を検知・予測して 先行して勝手にメモリ読み込み要求を発行 キャッシュに入れておく

改善策

read ahead (その2)

例:

• CPU - 分岐予測
  条件分岐や間接分岐の分岐先を予測し、命令先読みを行ない、 Out of Order CPUでは投機実行する。 投機実行の予測が外れた場合は、実行結果を捨てる。

改善策

read ahead (その3)

例:

• disk I/O
  カーネルはシーケンシャルアクセスを検知して、 ユーザからシステムコールに先行して ディスク読み込み要求を発行する

バンド幅: 通常は向上
   予測が外れると悪化する場合も
latency: 短縮

改善策

write back

例:

• cache memory - すぐにメモリに書かない。キャッシュから追い出される時に write back
• disk I/O - しばらくメモリに蓄えた後、書き込む (raw disk, O_DIRECT 以外)

バンド幅: 向上
latency: ある意味悪化
   ディスクにすぐ書かれない。
   クラッシュした場合は失われる。

改善策

write combining

例:

• cache memory
  frame buffer は write back 不可→書いた内容が見えないと困る
  連続した書き込みは結合する→トランザクション数が減る

バンド幅: 向上
latency: 問題なし
   フレームレートと比較すると一瞬

改善策

先行送信 (その1)

例:

• TCP window制御
  受信側が受信バイト数を、windowサイズとして申告。
  window サイズは、毎ACKパケットで更新。
  送信側は、window サイズまでは先行してデータを送る。
  

改善策

先行送信 (その2)

• TCP window制御 (つづき)
  帯域遅延積:
  バンド幅[byte/秒]×遅延[秒]
  =必要なwindowサイズ

バンド幅: 向上
latency: 短縮

改善策

中間にバッファを置いて並列処理 (その1)

例:

• データのproducerとconsumerがある
• データが届いてからconsumerがそれを消費し終えるのに時間がかかる、 producerがそれを待っていると無駄
• 中間にバッファを置いて解決

改善策

中間にバッファを置いて並列処理 (その2)

例:

• TCP window 制御も、これの一種と見ることができる

バンド幅: 向上
latency: 短縮

改善策

処理を細分化して並列処理

• CPUの命令パイプライン
  
  • 処理を分解（命令フェッチ・デコード・実行・レジスタ書き込み・etc）
  • 分解した各処理を並列して動作、データを順番に流す
• UNIXのパイプ

スループット: 向上
latency: 変化なし

改善策

並列性を抽出して並列実行する (その1)

例:

• CPU - スーパースカラー
  連続する命令で独立して処理できる場合は並列実行する

スループット: 向上
latency: 短縮

改善策

並列性を抽出して並列実行する (その2)

• CPU - Out of Order 実行
  独立して処理できる命令列をとにかく並列実行する
  同じ名前のレジスタ使ってても並列化できたりする (論理レジスタとは別に、もっと沢山の物理レジスタがある)。

スループット: 向上
latency: 短縮

改善策

投機実行

read ahead は、この一種
CPUの Out of Order 実行機能は、これを含んでいる。

スループット: 通常は向上
   予測が外れると悪化する場合も
latency: 短縮

改善策

インターリーブ

処理を複数のハードウェアで手分けして並列処理する

• memory channel
• RAID 0 (ストライピング)
• ネットワーク割り込みのコア分散

バンド幅: 向上する
latency: 変化なし

改善策

関係ない処理を並列して行なう (その1)

例:

• NFS のクライアントスレッド
  スレッド数だけ並列してRPC要求を発行する。
  単一のユーザースレッドからの要求が複数のNFSクライアントスレッドに 分割される場合は、rsizeやwsizeの拡大と同様な効果になる。

改善策

関係ない処理を並列して行なう (その2)

例:

• CPU - hardware multithreading
  
  • FGMT - Fine Grain Multithreading:
    SPARC T1/T2, PEZY
    in-order CPUで、複数の論理コア(=レジスタセット)を用意し、 ラウンドロビンでクロック毎に論理コアをぐるぐる切替える
    

改善策

関係ない処理を並列して行なう (その3)

例:

• CPU - hardware multithreading (続き)
  
  • CGMT - Coarse Grain Multithreading
    in-order CPU で、メモリアクセス待ちになった時、別の論理コアに切替える
    

改善策

関係ない処理を並列して行なう (その4)

例:

• CPU - hardware multithreading (続き)
  
  • SMT - Simultaneous Multithreading / a.k.a. Hyperthreading: Pentium 4 以降
    Out of Order CPU で、メモリアクセス待ちになった時、 別の論理コアを実行可能にする。
    (ある物理コアで、同時に実行している論理スレッドは複数)

改善策

関係ない処理を並列して行なう (その5)

バンド幅:

全体としてのスループットは通常は向上する。
スレッドあたりのスループットは同じか、 あるいはバンド幅ネックとなった場合は低下する。

latency:

絶対時間では同じ。スレッドに割り当てられたCPU時間比では短縮する。

改善策

差分を送る

データ全体ではなく、通信の両側でデータを保持しておき、差分のみを送る

• poll/select システムコール vs
  epoll/kqueue システムコール
• rsync

バンド幅: 通常は向上する
latency: 通常は短縮する

改善策

階層バイパス (その1)

• 伝統的 putchar()/putc() 実装
  関数ではなくマクロで実装し、関数呼び出しオーバーヘッドを避けている。
  Linux glibc はマクロではなく関数で実装
• マクロ / inline 関数実装

改善策

階層バイパス (その2)

• polling
  割り込みオーバーヘッドを避けるため、ビジーループでポーリングする
• VIA (Virtual Interface Architecture), DPDK
  カーネルをバイパスし、ユーザーランドで直接ネットワーク通信する

バンド幅: 通常はある程度向上する
latency: 短縮する

改善策

複合処理

• FMA (fused multiply-add) 命令
  浮動小数点命令の加算と乗算 a × b + 1 を単一の命令で実行すると レイテンシを短縮できる

バンド幅: 向上する
latency: 短縮する

改善策

データではなくプログラムを送る

• PostScript

バンド幅: 向上することが多い
latency: 短縮する (が、送り先の能力が低いと低下する)

改善策

物理的になんとかする

• クロックを上げる
• 線を増やす
• 距離を縮める
• 専用ハードウェア (FMA, AES-NI 命令, etc...)

まとめ

CPU時間だけでなく遊んでる時間にも注意

• レイテンシの隠蔽を試みる
• レイテンシとバンド幅は交換可能
  • read ahead や先行送信を aggressive に行なう→バンド幅を消費して latency を短縮
  • バンド幅が不足なら、データ全体ではなく、必要なだけ逐一問い合わせるといった方法で、latency をバンド幅に変換できる