キャッシュコヒーレンシに囚われない並列カウンタ達

キャッシュコヒーレントに囚われ ない並列カウンタ達 #DSIRLNP @kumagi

この発表について Data Structure!

キャッシュ？ • CPUが高速化のためにメモリの一部を切り出 して複製している物

キャッシュ CPUコア L1キャッシュ L2キャッシュ L3キャッシュ メモリ

All programmer should know • • • • • L1 キャッシュ 参照 ......................... 0.5 ns 分岐予測ミス............................ 5 ns L2 キャッシュ 参照 ........................... 7 ns Mutex lock/unlock ........................... 25 ns Main memory 参照 ...................... 100 ns

キャッシュ メモリ

キャッシュコヒーレント？ • 複数のCPUコアから見えるメモリは同一でな いと困る • つまり複数のCPUコアのキャッシュは常に最 新の情報を保持してないと困る • だが常に最新の情報を全部のキャッシュに全 て書き続けるのは速度が出ないので、まるで 本当に全部のキャッシュにすべて書いてるか のように見せかけながらパフォーマンスを出 す必要がある

キャッシュ 2つのコアで L2キャッシュを共有 メモリ

キャッシュコヒーレント • 複数のL1キャッシュ間で一貫したデータを扱うため のキャッシュ間のプロトコル • Intel系CPUはMESIFプロトコル • AMD系CPUはMOESIプロトコル Core1 Core2 L1キャッシュ コヒーレント L2キャッシュ L1キャッシュ

キャッシュコヒーレントプロトコル • キャッシュラインが取る状態名の頭文字が由来 – Modified: メモリよりもキャッシュの方が新しい(書き換えた) – Exclusive: メモリとキャッシュが同一であり、他のコアはこの キャッシュラインを持っていない – Shared: メモリとキャッシュが同一であり、他のコアもこの キャッシュラインを複製している – Invalid: 正しいキャッシュを持っていないので読むな – Owned: 俺がメモリだ(Shared可能なModified) – Forward: Sharedのボス。アクセスする際にはこいつに伺え

L1キャッシュの状態 • 1ライン64byteで、アドレスの下位バイトが同 じ物ごとに8wayずつ32KBまで持っている • 1ラインごとにMESIFのどれかのステートを 持っている 64Byte invalid shared exclusive modified forward 全部のラインが独立して それぞれステートが遷移する 32KB

キャッシュコヒーレントプロトコル • MESI(F)プロトコルはModifiedなデータを他のコアが読み出す際 にメモリに書き戻す • Sharedなデータを書き換える時にはInvalidation要求をブロード キャストするためトラフィックが混む Modified 書き換えた 共有を要求 （1個下のメモリへアクセス） Exclusive 新規に読み出した Shared Invalidation要求が来た 他のコアから貰った Invalid

キャッシュを汚す事はギルティ • 他のスレッドから繰り返し読む値を書き換え続けると、キャッ シュラインのステートはModifiedとSharedの間を行ったりき たりすることになる。これは激しいトラフィックを起こす。 • 更にはModifiedからSharedになる度に下層のメモリに書き 込まなくてはならない うぉー！ うぉー！ Core1 write ぎゃー！！ L1キャッシュ Invalidate Core2 read L1キャッシュ write L2キャッシュ

キャッシュを汚す事はギルティ 共有/localデータから Readした場合の速度 localデータにWrite した場合の速度 共有データにWrite した場合の速度 http://www.1024cores.net/home/lock-free-algorithms/first-things-first から

まったくスケール しない！！！！ http://www.1024cores.net/home/lock-free-algorithms/first-things-first から

NUMAでのキャッシュコヒーレント • 最近のサーバはマルチソケットCPUがよく使 われる

cc-NUMA • 複数のCPUソケットから同一のメモリ空間が 見えて欲しい（まるでマルチコアCPUのように） • キャッシュ衝突するとQPIアクセスの刑 – かつては拷問にも使われていたQPI経由のキャッ シュコヒーレント

All programmer should know • • • • • • L1 キャッシュ 参照 ......................... 0.5 ns 分岐予測ミス............................ 5 ns L2 キャッシュ 参照 ........................... 7 ns Mutex lock/unlock ........................... 25 ns Main memory 参照 ...................... 100 ns QPI経由で隣のメモリ参照.............. 200 ns～

キャッシュ 隣のCPUのキャッシュは 自分のメインメモリよりも遠い！！！ メモリ メモリ

cc-NUMAの時代 • キャッシュ衝突をとにかく減らすアルゴリズム が望まれている

Combining Tree • 以下のインタフェースを備えるカウンタ – add(int a)：数値aを足す – read()：現在の数値を読む • ただしスケーラブル！ 擬似コード class counter { public: counter() : cnt_(0) {} void add(int a) { cnt_ += a; } int read() const { return cnt_; } private: int cnt_; };

Combining Tree • 1つのキャッシュラインを取り合うのが2スレッ ドまでになるようトーナメントを構成する • トーナメントでぶつかったスレッドは、先に来 たスレッドに後に来たスレッドが値を託して待 つ • キャッシュコヒーレントトラフィックを劇的に削 減！

Combining Tree • トーナメントのてっぺんを読めば値が読める root

Combining Treeアルゴリズム +1 +1 +2 +3 +2 +1

Combining Treeアルゴリズム +1 +1 +2 +3 +2 +1

Combining Treeアルゴリズム +3 +1 +3 待 +3 待

Combining Treeアルゴリズム +6 +4 待 待 待 待

Combining Treeアルゴリズム +10 待 待 待 待 待

Combining Treeアルゴリズム • • • • • • 結合法則を用いて計算の合成を行う x+1+1+2+3+2+1 x + 1 + (1 + 2) + 3 + (2 + 1) x + (1 + 3) + (3 + 3) x + (4 + 6) x + 10

詳細なアルゴリズム • 各ノードはIdle, First, Second, Rootのどれかの 状態を持つ – Idle: どのスレッドも触ってない – First: 最初のスレッドが既に触った – Second: 二つ目のスレッドが触った – Root: てっぺん(遷移しない) • 更にノードはロックを2つ持っている

Combining Tree • 初めに木を登りながらステートの変更を行う – Idleな物をFirstにしていく – ロックを取ってステートを変えて即アンロック Root First First

Combining Tree • 初めに木を登りながらステートの決定を行う – Firstを見たらSecondにして第二ロックを獲得 • こっちのロックはすぐには手放さない Root Second First First Second First

Combining Tree • 初めに木を登りながらステートの決定を行う – Secondにしたらそこで木を登るの停止 Root Second First First Second

Combining Tree • 木を登るのをやめた所で、自分の過去の経 路の第二ロックを獲得し直しながら値を清算 Root Second First First Second

Combining Tree • 木を登るのをやめた所で、自分の過去の経 路の第二ロックを獲得し直しながら値を清算 Root Second First +1 First +2 Second

Combining Tree • 清算しきった値を最初に自分が登った一番高 い所に書き込んでアンロックするのが基本戦 略 Root +3 Second First First Second

Combining Tree • 清算しきった値を最初に自分が登った一番高 い所に書き込んでアンロック Root +3 Second First First Second

Combining Tree • Secondのステートを見たら他のスレッドが清 算中なのでそれを待つ（第二ロック獲得待ち） Root Lock! Lock! Second First First Second

Combining Tree • 清算し終わった値を持って再帰的に自分の 値として生産する +4 Root Second First First Second

Combining Tree • 平均して木の深さnに対して2*n回のロックと アンロックを使うことになる – 大丈夫なの･･･？ • Mutex lock/unlock ........................... 25 ns • QPI経由で隣のメモリ参照.............. 200 ns～ キャッシュ衝突のペナルティを 考えると余裕でペイする

Combining Tree • 衝突がない場合でも2*n回のロック・アンロッ ク • レイテンシという点において非常に悪い – 改良として1ノードに3スレッド以上ぶら下げて木 の深さを減らすパターンもあるが、複雑さがマッ ハでレイテンシはむしろ悪化

Combining Funnel • Funnel = 上戸 • 乱数ベースで負荷を低減 – アルゴリズムはEliminationに近い – Eliminationと組み合わせることも可能 Counter

Combining Funnel • 配列の中のランダムな箇所にCAS命令で自分 のタスクを置く • ランダム時間の待機後、CASでタスクを引き上 げて次のレイヤーに進む(ここが上戸っぽい） +2 +1

Combining Funnel • 置こうと思った場所に先客が居たらそいつと 操作を結合して次のレイヤーに進む +3したい +2 +1

Combining Funnel • 置こうと思った場所に先客が居たらそいつと 操作を結合して次のレイヤーに進む +5せざるを得ない！ 待 +1

Combining Funnel • 置こうと思った場所に先客が居たらそいつと 操作を結合して次のレイヤーに進む あっ待てって言われてる 待 +1 +5 Counter

Combining Funnel • カウンタのレイヤーまで到達したらそいつに Compare And Swap • 感動的に簡単しかも速い

Combining Funnel Combining Funnels A Dynamic Approach To Software Combining より

SNZI • 数を数えようとするから残念なことになるん や！諦めろ！ – ゼロかどうか分かればええ！ • Scalable-Non-Zero-Indicatorの略でSNZY – pronounced "snazzy" : (和訳)粋な、おしゃれな、 優雅な、エレガントな、格好いい

SNZIのセマンティクス • 数字が読めないカウンタ • これをスケーラブルにする 擬似コード class snzi { public: counter() : cnt_(0) {} void inc() { cnt_ += 1; } void dec() { cnt_ -= 1; } bool is_zero() const { return cnt_ == 0; } private: int cnt_; };

SNZIの実装 • キャッシュラインで木構造を作る ここが0かどうかを 見れば良い 0 0 0 0 0 0 0

SNZIの実装 • 木の各ノードが1CPU – 上から数えてi番目のノードはi番目のCPUに割当 0 1 0 1 0 1 0 0 0 0 root以外を0から1に増やすときには1個上のノード の値をインクリメントする rootは常に普通にインクリメントするだけ

SNZIの実装 • 木の各ノードが1CPU – 上から数えてi番目のノードはi番目のCPUに割当 0 1 0 1 0 1 0 0 0 0 root以外を1から0に減らすときには1個上のノード の値をデクリメントする rootは常に普通にデクリメントするだけ

SNZIの実装 • 木の各ノードが1CPU – 上から数えてi番目のノードはi番目のCPUに割当 0 1 0 1 2 0 1 0 0 0 0 それ以外のときは普通にインクリメントするだけ ＝上のノードのキャッシュラインに触れずに済む

SNZI • すごくスケールする！！！ SNZI: Scalable NonZero Indicatorsより

しかもロックフリー！！

SNZIの実装 • 厳密には複数のスレッドが同一のノードにア クセスしに来た際に0⇔1周りで細かい調停が 必要 0から1のときは、先に自分の箇所の値を1/2という値にしてから上のノードをインクリメン トしにいき、そのあとで1/2を1にCASを試みる。もし上のノードのインクリメントに成功した 後に1/2→1のCASに失敗したら上のノードをデクリメントしておく • デクリメントの数はその前に行われたインクリ メントの数を越えては行けない（Read-Write ロックなどに用いるには充分）

SkySTMへの適用 What kinds of applications can benefit from Transactional Memory? より

時間が無くて書けなかったこと • STMの高速化のためにSNZIが必要とかいっと きながら実際にSNZIをRead-Write-Lockに用い たSkySTMは割とあっさりTLRWに負けている – TLRWはByteLockっていうまた別のロックプロトコ ルを用いてる（こっちの話はまた今度） • SNZIのためにHTMを用いたやつがあって凄い 速い – HTMの使い方についてもまた今度

HTM+SNZI 2倍 What kinds of applications can benefit from Transactional Memory? より