局所性を時間で測ってみる
目標
同じデータを同じ回数だけ読むのに、読む順序1つで時間が何倍も変わることを、直接測ってみます。ストライド、行優先と列優先、タイリングの3つの実験を通じて、局所性が抽象的な言葉ではなく、手に取れる数字になります。
なぜ重要なのか
メモリ階層は、プログラムが局所性を持つという仮定の上に立っています。その仮定を破るコードは、ハードウェアが用意した助けを何も受けられません。キャッシュはデータを64バイトのライン単位で取得し、プリフェッチャーは一定の間隔で進むアクセスを先読みし、TLBは最近使ったページのアドレス変換を記憶しています。ストライドを大きくすると、この3つが順に無力になります。
ここで測るのはPythonの速度ではありません。Pythonは遅いですが、その遅さはどの実験にも同じように付くので、読み取りの回数を固定しておけば、残る差はメモリのせいです。この設計がこのラボのすべてだといってもよいでしょう。
数字の絶対値は、マシンごとに違います。採点ツールも絶対値は見ず、どちらがどれだけ遅いかだけを見ます。
ステップ
- このPodが動くCPUの、キャッシュラインサイズとキャッシュ階層を確認して、
/root/mem/01-cache.txtに残します。 /root/mem/stride.pyを作成します。ストライドを引数として受け取り、1回の読み取りあたりのナノ秒を、数字だけ1行で出力します。- ストライド1、16、65536を測って、
/root/mem/03-stride.txtに3行で残します。 stride.pyにrandの分岐を加え、順次とランダムを測って、/root/mem/04-random.txtに2行で残します。/root/mem/matrix.pyを作成します。Nと走査方向を引数として受け取り、要素1つあたりのナノ秒を出力します。Nを2048にして、行優先と列優先を測り、/root/mem/06-order.txtに2行で残します。matrix.pyにblockの分岐を加え、列優先とタイリングを測って、/root/mem/07-block.txtに2行で残します。- 3つの実験を1文ずつ整理して、
/root/mem/08-notes.mdに残します。
参考
- 成果物は、すべて
/root/mem/の下に置きます。mkdir -p /root/memを先に実行しておいてください。 - 時間は
time.perf_counter()で測ります。time.time()は分解能が足りません。 - 測る前に、1,000回ほど先に読んでウォームアップしてください。最初のアクセスには、配列を作るコストとページフォールトが混ざります。
- よくある間違い1: 配列を小さくとることです。キャッシュに収まるサイズだと、ストライドをどれだけ変えても差が出ません。
- よくある間違い2: 分岐ごとにインデックスの式を変えることです。片方で掛け算を省くと、その差が測定値に混ざり、メモリを測っているのか算術を測っているのかわからなくなります。
- 配列は96MBほどです。Podはメモリ2Giを受け取っているので余裕がありますが、複数のプログラムを同時に動かさないでください。
このマシンのキャッシュ階層を読み取る
このPodが動くCPUの、キャッシュラインサイズとキャッシュ階層(L1/L2/L3)を確認して、/root/mem/01-cache.txtに残します。int32が1ラインにいくつ載るかも計算して、一緒に書きます。
キャッシュラインサイズは/sys/devices/system/cpu/cpu0/cache/index0/coherency_line_sizeにあり、同じディレクトリのlevel、type、sizeを読めば、階層が見えます。int32は4バイトなので、ラインサイズを4で割れば、1ラインにいくつ載るかが出ます。この数字が、あとのステップでストライドを選ぶ基準になります。
ストライドを変えて測るツールを作る
/root/mem/stride.pyを作成します。python3 /root/mem/stride.py <보폭>で呼び出すと、int32が24,000,001個の配列(約96MB)を作って500,000回読み、1回の読み取りにかかったナノ秒を、小数点以下1桁で数字だけ1行出力する必要があります(プレースホルダーはストライドです)。
核心は、読み取りの回数をストライドと無関係に固定することです。そうすれば、Python自体の遅さが両側で同じように相殺され、メモリの差だけが残ります。
インデックスはあらかじめリストにしておき、測る区間ではそのリストだけを回してください。次のインデックスは、i = (i + 보폭) % 배열길이で移します(韓国語の語は、順に「ストライド」「配列の長さ」を意味します)。配列の長さが奇数なので、ストライドが大きくても、同じ場所をすぐには踏み直しません。
測定の前に、1,000回ほど先に読んでウォームアップしてください。最初の実行には、配列を作るコストが混ざります。
ストライドを1、16、65536に変えて測る
ステップ2のツールで、ストライド1、16、65536をそれぞれ測り、/root/mem/03-stride.txtに보폭 나노초の形式で3行残します(韓国語の語は、順に「ストライド」「ナノ秒」を意味します)。
for s in 1 16 65536; do echo "$s $(python3 /root/mem/stride.py $s)"; doneのように回すと、3行が一度に出ます。
ストライド16は、int32基準でキャッシュライン1つ分を飛ばすサイズで、ストライド65536は256KBなので、ページ境界も、プリフェッチャー(prefetcher)が追いかけられる範囲も、大きく超えます。プリフェッチャーはページ境界を越えられないので、ここで値が大きく跳ね上がります。
サイズはそのままで、順序だけを変える
/root/mem/stride.pyが引数としてrandを受け取ったら、ランダムな順序で読むように直します。そのあと、順次(ストライド1)とランダムをそれぞれ測り、/root/mem/04-random.txtにseq 나노초、rand 나노초の2行で残します(韓国語の語は「ナノ秒」を意味します)。
配列のサイズも読み取りの回数もそのままにして、読む順序だけを変えるのが、このステップの要点です。サイズが同じなので、容量のせいだとは言えず、残る説明は空間的局所性だけです。
ランダムなインデックスは、測る前にあらかじめ作っておいてください。random.Random(1)のようにシードを固定すれば、もう一度回しても同じ順序が出ます。
行列を2方向になぞるツールを作る
/root/mem/matrix.pyを作成します。python3 /root/mem/matrix.py <N> <row|col|block>で呼び出すと、int32のN×Nを平らな配列1つ(a[i * N + j])に入れて、指定した方向ですべてなぞり、要素1つあたりのナノ秒を、小数点以下1桁で数字だけ1行出力する必要があります。
rowはiが外側、jが内側です。colは逆です。2つの分岐とも、インデックスの式はa[i * N + j]で同じにしてください。片方だけ掛け算を省くと、測定の差にPythonの演算コストが混ざり、何を測っているのかわからなくなります。
blockはステップ7で使います。今はrowとcolだけでも、このステップは通過します。
行優先と列優先の差を測る
Nを2048にして、行優先と列優先をそれぞれ測り、/root/mem/06-order.txtにrow 나노초、col 나노초の2行で残します(韓国語の語は「ナノ秒」を意味します)。
同じ要素を同じ回数だけ読むのに、順序だけが違います。それでも、列優先が何倍も遅くなります。Nが2048なら、列方向に1マス進むと8KBで、これはページ1つ(4KB)を超える距離です。
差があまり出ないときは、Nを大きくしてみてください。行列がキャッシュに収まると、どちらの方向に読んでも似た結果になります。
タイルに切って、列優先の損を減らす
matrix.pyにblockの分岐を加えます。順序は列優先のままにして、64×64の断片の中だけを回るようにします。そのあと、Nを2048にして、列優先とタイリングをそれぞれ測り、/root/mem/07-block.txtにcol 나노초、block 나노초の2行で残します(韓国語の語は「ナノ秒」を意味します)。
外側の2重ループが断片の開始座標を移動し、内側の2重ループが断片の中で列優先に回ります。断片1つが64行×64列なら、その中で触れるキャッシュラインは16KBほどなので、L1に収まります。
同じ要素を同じ回数だけ読むのに速くなる理由は、取得したラインを捨てる前に使い切るからです。行列の乗算でタイリングを使う理由がこれです。
3つの実験を1文ずつ整理する
/root/mem/08-notes.mdに3行以上書きます。ストライドを大きくするとなぜ遅くなるのか、列優先の走査がなぜ損なのか、タイリングが何を取り戻すのかを、それぞれ1文で書きます。
3つの実験は、どれも同じ話を別の角度からしています。メモリはライン単位で動き、取得したラインを使わずに捨てれば、その分だけ損をするということです。
보폭、열 우선、타일という語が本文に含まれている必要があります(韓国語で、順に「ストライド」「列優先」「タイル」を意味する語です)。