実験・実装 · 基礎から応用へ

strideを変えて訪問数と時間を比べる

二つの領域サイズと四つのstrideをCで走査し、訪問数・有用バイト・時間を分け、キャッシュやTLBについて言える範囲を確かめます。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 間隔を変えたときの仕事量を数える
  2. 要素の間隔とバイトの間隔を分ける
  3. 二つの領域サイズでコードを実行する
  4. 正規化した値と少なすぎる標本を読む
  5. 観測したことと原因候補を分ける
  6. 端の要素を忘れない条件を試す
  7. 端数の訪問数を計算する課題
  8. この記事をロゲイアに質問する理解を確かめる

間隔を変えたときの仕事量を数える

この実験は、配列の添字を1、16、64、1024ずつ進め、訪問した値を合計します。要素は4バイトのuint32_tで全て1です。間隔を大きくすると、同じ領域のうち読む要素が減ります。行列の二方向の全走査と違い、仕事量は等しくありません。まず訪問回数を計算し、その数と合計が一致することを確認します。キャッシュの配置とstrideを読んだ後に、総時間だけで「間隔が大きいほど速い」と決めない比較方法を練習しましょう。

配列長n、strideをsとすると、訪問する添字は0、s、2s、…で、n未満までです。回数はceil(n/s)、コードでは(n+s−1)/sの整数除算で数えます。例えばn=8192、s=16なら512回、s=1024なら8回です。この違いを隠すと、単に少ない加算で早く終わった結果を、キャッシュ効率の改善と呼んでしまいます。逆に要素あたりの時間が増えても、処理全体としてどれだけのデータを必要とするかで、採るべき方法は変わります。

要素の間隔とバイトの間隔を分ける

sはバイト数ではなく要素数です。4バイト要素なので、s=16は64バイト、s=64は256バイト、s=1024は4096バイトの差です。64バイトのラインという模型では、s=1なら運んだラインから複数の要素を使えます。s=16なら一つのラインから一要素だけ使う並びになります。ただし実際の転送回数は、階層と先読み、既に残っているデータによって変わります。読んだ値のバイト数は訪問回数×4ですが、実際に運んだバイト数と同じとは限りません。

4096バイトの間隔は、ページサイズが4096バイトの環境なら、次のページの同じ位置へ進む形です。TLBによる変換や、複数のアクセスを先読みする機会も、ラインの配置と同時に変わります。時間だけを見て「これはTLBミス」「これはL1ミス」と決めません。ページサイズを変える実験を追加するなら、実際の割当てにその設定が適用されたかも確かめてください。配列を確保したという事実から、特定の大きなページを使ったと推測しないことが大切です。

二つの領域サイズでコードを実行する

コードをstride.cへ保存し、gcc -O2 -std=c11 -fno-loop-interchange -fno-ipa-pure-const stride.c -o strideで作り、./strideを実行します。n=8192は32 KiB、n=16,777,216は64 MiBです。この大小は割当て量であり、全ての実行環境で前者が専有キャッシュに収まり、後者が全キャッシュを超えるという保証ではありません。CPUと共有範囲を記録したうえで、サイズごとに結果を分けます。初期化は測定の外で行い、確保に失敗したら停止します。

各サイズとstrideを9回ずつ測り、長さ、stride、訪問数、反復、ナノ秒をCSVへ出します。strideを測る順番は反復で回します。合計が訪問数と一致しなければassertで停止するため、終わるまで進んだことと正しい走査をしたことを区別できます。計測区間はwalkの一回だけで、printfや配列を1へ埋める時間は含みません。コンパイラ版と全設定をCSVと一緒に保存し、実行コードの違う結果を同じ系列へ混ぜないでください。

c
#define _POSIX_C_SOURCE 200809L
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
static volatile uint64_t sink;
static uint64_t ns(void) { struct timespec t; assert(!clock_gettime(CLOCK_MONOTONIC,&t)); return (uint64_t)t.tv_sec*1000000000u+t.tv_nsec; }
__attribute__((noinline)) static uint64_t walk(const uint32_t *a,size_t n,size_t stride) {
 uint64_t sum=0; for(size_t i=0;i<n;i+=stride) sum+=a[i]; return sum;
}
int main(void) {
 size_t sizes[]={8192,16777216},strides[]={1,16,64,1024};
 for(int z=0;z<2;z++) {
  size_t n=sizes[z]; uint32_t *a=malloc(n*sizeof(*a)); assert(a);
  for(size_t i=0;i<n;i++) a[i]=1;
  for(int r=0;r<9;r++) for(int k=0;k<4;k++) {
   size_t stride=strides[(k+r)%4],visits=(n+stride-1)/stride;
   uint64_t start=ns(),sum=walk(a,n,stride),elapsed=ns()-start;assert(sum==visits);sink=sum;
   printf("%zu,%zu,%zu,%d,%llu\n",n,stride,visits,r,(unsigned long long)elapsed);
  }
  free(a);
 }
 return 0;
}

正規化した値と少なすぎる標本を読む

要素あたりの時間はナノ秒を訪問数で割ります。読んだ有用データあたりの速度を出すなら、訪問数×4を時間で割れます。ただし、その値へ「DRAM帯域」と名前を付けないでください。ラインを丸ごと運ぶ費用やキャッシュの再利用を含んだ実転送ではないためです。表を作るときは領域サイズ、stride、訪問数、総時間、1訪問あたりの時間を並べます。総時間だけと正規化後の値で順位が変わる理由を、仕事量から説明します。

小さい領域でs=1024なら8回しか読まず、時計の呼出し費用が大きな割合を占める可能性があります。この場合は、低い桁まで出たから精密と考えず、空の計測区間と比べます。反復をまとめる方法を追加するなら、同じ配列の再利用で状態が変わることも明記します。全標本を残して中央値や分位点を計算し、最短の一回を原因の証拠にしません。時間の揺れと、仕事の少なさに由来する測定限界を別の問題として扱います。

観測したことと原因候補を分ける

掲載コードはGCC 13.3と仮想CPUで実行し、両サイズ・四つのstrideの合計を検証しています。PMUを取得していないため、ラインのミス数やTLBミス数は未測定です。サイズとstrideに応じた時間の違いは観測できますが、その曲線の折れ曲がりだけでキャッシュの容量や索引方式を確定しません。複数の要因が同じところで変わる場合があります。実機のイベントを使う追加調査では、CPU固有の定義、測定区間、多重化も残します。

この実験は読取りだけで、一つのスレッドが合計を求めます。別のコアから同じラインへ書く偽共有は起こしていません。書込みの実験へ変えれば、所有権の移動や書戻しも条件に入ります。主張する原因に対応する操作がコードにあるかを、時間のグラフを見る前に確かめてください。「メモリが遅い」という広い説明から、どの境界で何を観測したかへ問いを狭めることが、次の診断に役立ちます。データ配置の記事へ戻り、使わない値を運ぶ理由も検討します。

端の要素を忘れない条件を試す

nがstrideで割り切れない場合、最後の訪問は必ずn未満で、次の添字がn以上になります。n=17、s=16なら0と16の二回です。最後の一要素を落とす変更は、時間が短くても同じ走査ではありません。バイト数の計算と同じく、回数の独立した期待値を残すことで、ループの境界の誤りを速度改善と取り違えずに済みます。

端数の訪問数を計算する課題

課題はn=10、s=4に変えたときの添字、訪問数、期待する合計を求めることです。解答は0、4、8の三回で、値が全て1なら合計3です。10/4の整数除算だけでは2となり、最後の8を落とします。コードの(n+s−1)/sは、この切上げを実現しています。nより大きなsでも、nが正なら添字0は一回訪問することを確認してください。n=0も扱う拡張では、確保と期待値の仕様を先に決めます。

次に、s=1の合計10とs=4の合計3を「同じ結果の速い実装」と呼べるかを考えます。解答は呼べません。読みたい要素を減らしているからです。特定の間隔だけ必要な業務なら、その仕様を比較の前提へ置きます。最後に、元の大きいサイズを増やす場合は、メモリの確保量と実行時間を見積もり、並列に大量の領域を確保しないようにします。終了時にはfreeで領域を解放します。生成したCSVとバイナリ以外に後片付けが必要なサービスはありません。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 8

AI基盤へ進む · STEP 5

学習コースから次を選ぶ