L1キャッシュ怖い
4K Views
April 12, 23
スライド概要
Radix Sortを並列化して高速化する話
関連スライド
各ページのテキスト
L1キャッシュ怖い 3/23 広域センサネットワークとオーバーレイに関する ワークショップ @kumagi
Radix Sortとは • O(N)なソートアルゴリズム – iwiwi博士「経験上実測で一番速い」 • O(N)のメモリ領域が追加で必要になる – なので多くの場面ではMerge SortやQuick Sortが 採用されたりする。 – In-PlaceなRadix Sortは最近の研究トピックの一つ • 実装上内部でCounting Sortを使うことが多い – CountingSortに関しては次ページ
Counting Sortとは 2 3 3 5 9 4 3 3 9 4 2 3 1 1 4 7 1. 数える 1 2 2 2 3 5 4 3 5 1 7 1 9 2 2. マッピング 2 2 5 3 11 2 3. 埋める 1 1 2 2 3 3 3 3 3 4 4 4 5 7 9 9
Radix Sort with Counting Sort • CountingSortは値のバリエーションが増えると 死ぬ • 実用上8bit(256種)ずつCounting Sortする。 • Counting SortはStableなので下8bitから順に Sortする（Least Significant Digit first）。 • 上8bitからSortする事も可能(Most Significant Digit first)こっちはまた後で。
LSD Radix Sort • わかりやすいように10進数で 313 210 118 410 123 471 292 384 1の位でCountSort 210 410 471 292 313 123 384 118 10の位でCountSort 210 410 118 313 123 471 384 292 100の位でCountSort 123 118 210 292 313 384 410 471
LSD Radix Sort https://www.youtube.com/watch?v=kPRA0W1kECg
iwiwi sort • iwiwi特任助教授が過去に実装したのはこれ をOpenMPで並列化したもの
iwiwi sort • std::sortの19倍ぐらい速い。この人怖い。
iwiwi sortの基本戦略 • LSD Radix Sortを並列化している – Software Write Combiningというテクニックで高速化 – 基本的に結構素直な実装 • uint64_tなら、8回のCountSortを行う – データ全体を舐めてカウント – データ全体を隣のバッファにまるっと並べ替え移動 – 上記2ステップを8回繰り返す
SoftWare Write Combining • CPUが書き出すアドレスを絞って連続させて 溜めてから書き出す事でWriteBufferをギチギ チに埋める実装技法。 CPU キャッシュ WriteBuffer メモリ 書き込み先アドレスが次々変わると WriteBufferが埋まり切る前に書き出されて リソースが無駄になる
SoftWare Write Combining • CPUが書き出すアドレスを絞って連続させて 溜めてから書き出す事でWriteBufferをギチギ チに埋める実装技法。 CPU キャッシュ WriteBuffer WriteBufferが埋まり切る単位でしか キャッシュから書き出さないようにする。 メモリ データの移動回数の総量は倍に増えてる のに何故か高速化する。L1キャッシュ怖い。
SoftWare Write Combining • Intelのマニュアルに書いてある 小さなSowtWareWriteCombining(SWWC)メモリを確保してそこ にデータを書き出し、キャッシュラインが埋まったタイミングでし かグローバルな領域に書き出さないようにすることで性能を上 げる事ができるよ。 http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia32-architectures-optimization-manual.pdf
Radix Sort with SWWC
• Countingフェーズは変わらない
• データ移動フェーズで移動先候補が256箇所
あるのでそれを一旦ローカルの配列に書き込
んで、キャッシュライン長になったらmemcpy().
for (size_t j = 0; j < size; ++j) {
uint8_t idx = (from[j] >> i) &255);
to[offsets[idx]++] = from[j];
}
for (size_t j = 0; j < size; ++j) {
uint8_t idx = (from[j] >> i) &255);
wbuffer[idx][wbuff_n[idx]++] = from[j];
if (wbuff_n[idx] == 8) { // cache line
memcpy(&to[offsets[idx]],
&wbuffer[idx], 64);
offsets[idx] += 8;
wbuff_n[idx] = 0;
}
}
in NUMA環境 • LSD RadixSortは全対全のデータ移動が CountSort毎に行われる – CPUソケットを跨る移動のペナルティは大きい – Software Write Combiningは効果が大きくなるが 上のペナルティを相殺できるほどではない
勝つにはどうすれば? • ソケットを跨る通信を少なく抑えたい – よろしい、MSD Radix Sortだ • 巨大データのソートを相手にするなら、舐める 回数は最小限に抑えたい – よろしい、一度のイテレーションでCountingだ
MSD Radix Sort • わかりやすいように10進数で 313 210 118 410 123 471 292 384 100の位でCountSort 123 118 210 292 313 384 410 471 10の位でCountSort 118 123 210 292 313 384 410 471 1の位でCountSort 118 123 210 292 313 384 410 471
MSD Radix Sort • と簡単にできるわけではない。 • 上の桁で同一だった値同士でしかソートして はならない。 – 逆にいえば同一の桁の値が1つしかなければそ こで探索打ち切りできる • 個々のバケット毎に再帰的に掘り下げていく 形でソートせざるを得ない
MSD Radix Sort https://www.youtube.com/watch?v=kPRA0W1kECg
最初だけMSD Radix Sort • MSDで256バケットに分けた段階でCPUソケッ トを跨るように設計。跨った後は1バケット毎 に1CPUコアが専属で張り付いてLSD Radix Sortする • LSD Radix Sortの際にCountは一度に可能 for (int i = 0; i < 7; ++i) { for (int j = 0; j < size; ++j) { uint8_t base = i * 8; ++offsets[data[j]>> base & 255]; } // offsetsを使って並び替え } for (int j = 0; j < size; ++j) { for (size_t i = 0; i < 7; ++i) { uint8_t base = i * 8; ++l_offsets[i][data[j] >> base & 255]; } } // l_offsets[0:7]を使って7回並び替え
測定 • 144コアのXeon E7-8870v3@2.1Ghz • 1億要素から10億要素までのuint64_t • メルセンヌツイスタで一様に初期化
Prefix-Sumの並列化やら非 OpenMPなスピンバリアや らでの利得(面白くないので 説明は割愛) MSDの 差分 ・・・！！？
何この差？ • キャッシュラインにいくつ溜まったら書き出し たか、の差 msd8 for (size_t j = 0; j < size; ++j) { uint8_t idx = (from[j] >> i) &255); wbuffer[idx][wbuff_n[idx]++] = from[j]; if (wbuff_n[idx] == 8) { // cache line memcpy(&to[offsets[idx]], &wbuffer[idx], 64); offsets[idx] += 8; wbuff_n[idx] = 0; } } msd16 for (size_t j = 0; j < size; ++j) { uint8_t idx = (from[j] >> i) &255); wbuffer[idx][wbuff_n[idx]++] = from[j]; if (wbuff_n[idx] == 16) { // cache line memcpy(&to[offsets[idx]], &wbuffer[idx], 128); offsets[idx] += 8; wbuff_n[idx] = 0; } }
考察 • 64byteを256本使うのがmsd8 – 64*256=16KiB ← つまりL1-Dの半分を使う – もう半分はソート対象データのprefetchで適当に 上手く使われるのでは？（当初の思惑） • 128byteを256本使うmsd16の方が1割程速い – 128*256=32KiB ← L1-Dを全部使う – よくわからないがワンショットで読むぐらいなら キャッシュを気にする事はない？
考察
• msd32とmsd64が最速を奪い合う構図
– お前らL1-Dキャッシュから溢れてるやんけ！！
• 助けてVTune先生！
• VTune先生「if文が足引っ張ってるやで」
for (size_t j = 0; j < size; ++j) {
uint8_t idx = (from[j] >> i) &255);
wbuffer[idx][wbuff_n[idx]++] = from[j];
if (wbuff_n[idx] == 16) { // ここの分岐予測は1/16の確率で外れる
memcpy(&to[offsets[idx]],
&wbuffer[idx], 128);
offsets[idx] += 8;
wbuff_n[idx] = 0;
}
}
kumagiさんの次回作にご期待ください！