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

行と列で走査順を変える

連続した同じ行列を二方向から全走査し、要素数と結果を揃えたC実験で、配置の予測と測定時間を比較します。

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

更新日

この記事の目次
  1. 同じ全要素を順番だけ変えて読む
  2. コンパイルする条件を固定する
  3. 連続領域の添字とコードを照合する
  4. 全標本と単位あたりの時間を見る
  5. 値の型と加算の順序を固定する
  6. 条件を一つ変える課題と解答
  7. この記事をロゲイアに質問する理解を確かめる

同じ全要素を順番だけ変えて読む

この実験では2048行×2048列のuint32_tを、一つの連続領域へ行優先で置きます。全要素の合計を、行を内側にする列方向と、列を内側にする行方向で求めます。読む要素と加算回数は同じです。strideの実験のように飛ばす要素はありません。キャッシュと配置のガイドを前提に、アクセス順の予測と、Cで実際に走査した時間を分けて確認します。Pythonの二重ループを代わりに測ると、言語処理系の費用も大きく入り、ここで比べたいコードとは変わります。

要素は4バイトなので領域は16 MiBです。行方向は隣へ4バイト進み、列方向は次の行まで8192バイト進みます。64バイトのラインを仮定した模型では、行方向は一つのラインの16要素を続けて使えます。列方向では次の要素が別のラインにあります。ただし後で別の列も読むので、全体で各ラインを一度しか使わないとは限りません。実際に何回転送されるかは、キャッシュの残り方や先読みなども含めて調べる必要があります。

コンパイルする条件を固定する

コード全体をrow.cへ保存します。POSIXのclock_gettimeを使うLinuxとGCCで、gcc -O2 -std=c11 -fno-loop-interchange -fno-ipa-pure-const row.c -o rowとして作り、./rowを実行します。交換最適化を止めるのは、書いた二つのループ順を観察するためです。通常のアプリにそのまま勧める設定ではありません。別のコンパイラを使う場合は、同名の設定があると仮定せず、生成コードで順序が保たれることを確かめてください。出力は走査方向、反復番号、ナノ秒、合計のCSVです。

初期化、割当て、期待値の照合、printfは測定区間の外へ置きます。a[i]はi mod 17で、合計を64ビットで保持するため、この入力の足し算は範囲内です。mallocが失敗した場合はassertで止まります。最初に二方向の答えを比較し、以後の各測定でも同じ値を確認します。この準備の走査があるので、最初の記録を「全階層が空のコールド実行」とは呼びません。準備後の観測として扱うことが、測定の条件に含まれます。

連続領域の添字とコードを照合する

a[i×SIDE+j]は行i・列jを表します。内側でjを増やすと連続し、内側でiを増やすと行の長さだけ飛びます。二つのループの外と内を、紙に書いた最初の四つの添字と比較してください。列方向の最初は0、2048、4096、6144です。行方向は0、1、2、3です。要素番号へ4を掛けるとバイトの差になります。二次元ポインタを各行ごとに確保する実装へ変えると、行同士が連続するという前提も変わるため、同じ実験として混ぜないようにします。

rとkを使って、反復ごとに先に測る方向を入れ替えます。一方を全て測り終えてからもう一方へ進む方法より、時間による環境変化を片側へ偏らせにくくします。ただし、直前の方向がキャッシュへ残す状態もあるので、順番の影響を完全に消したとは言えません。sinkへの代入と最終的なチェックサムの出力で結果を利用します。noinlineだけを頼りにせず、実際の呼出しとループを逆アセンブルでも確認するのが次の検査です。

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; }
enum { SIDE=2048 };
__attribute__((noinline)) static uint64_t walk(const uint32_t *a,int column) {
 uint64_t sum=0;
 if(column) { for(size_t j=0;j<SIDE;j++) for(size_t i=0;i<SIDE;i++) sum+=a[i*SIDE+j]; }
 else { for(size_t i=0;i<SIDE;i++) for(size_t j=0;j<SIDE;j++) sum+=a[i*SIDE+j]; }
 return sum;
}
int main(void) {
 size_t n=(size_t)SIDE*SIDE;
 uint32_t *a=malloc(n*sizeof(*a)); assert(a);
 for(size_t i=0;i<n;i++) a[i]=(uint32_t)(i%17);
 uint64_t expected=walk(a,0); assert(walk(a,1)==expected);
 for(int r=0;r<9;r++) for(int k=0;k<2;k++) {
  int column=(r+k)%2; uint64_t start=ns(),sum=walk(a,column),elapsed=ns()-start;
  assert(sum==expected); sink=sum;
  printf("%s,%d,%llu,%llu\n",column?"column":"row",r,(unsigned long long)elapsed,(unsigned long long)sum);
 }
 free(a);return 0;
}

全標本と単位あたりの時間を見る

正常なら二つの方向がそれぞれ9行表示され、全て同じ合計になります。時間の大小はassertしません。実行環境によって差や揺れが変わるためです。各方向の全標本を残し、中央値と分位点を計算します。要素あたりの時間は、計測ナノ秒を4,194,304要素で割ります。処理量が同じなので合計時間も直接比較できますが、正規化しておくとサイズを変えた場合の見方が揃います。最速の一行だけを選ぶと、実行待ちを含むばらつきが見えなくなります。

今回の実行環境は仮想化されたAMD EPYC表示のCPU、GCC 13.3です。掲載コードの正常終了とチェックサム、生成コードを確認していますが、PMUの値は取得していません。列方向が遅く見えた場合も、その差をキャッシュミスの個数へ読み替えません。TLB、先読み、共有資源、OSの実行待ちも関係します。再現する際はCPU、OS、コンパイラ版、設定、反復数を一緒に残し、実機のカウンタを追加した場合は時間の記録とは別の証拠にします。

値の型と加算の順序を固定する

この入力は非負の小さい整数なので、同じ全要素を64ビットで足す二つの順序で同じ正解を比較できます。floatへ変えると加算順による丸めが入り、ビット単位の一致をそのまま期待できない場合があります。時間だけを比べるため型を変えるなら、許容誤差と参照計算を先に定めてください。また、ループ交換が有効な別ビルドでは列順のソースが行順へ変わる可能性があります。逆アセンブルの内側のアドレス更新を確認し、同じ結果だったことだけで、意図した二つの順が残ったと判断しないことが大切です。

条件を一つ変える課題と解答

課題はSIDEを2049へ変えたとき、列方向のバイト間隔と正解の確かめ方がどう変わるかです。解答では行の幅が2049×4=8196バイトになります。配列の総要素数も変わるため、元の時間や合計をそのまま期待値にしません。二方向で同じ新しい要素集合を読むことを照合し、要素あたりの時間を計算し直します。キャッシュ集合の競合の仕方が変わる可能性はありますが、必ず速くなるとは言えません。別サイズの結果は元の標本と混ぜずに保存します。

さらに、一列だけを読む課題へ変えると、行方向の全走査と仕事量が一致しなくなります。それは別のアクセス問題で、合計時間だけで優劣を判断する比較から外れます。解答の説明には、配置、読む添字、要素数、結果の四つを含めてください。実験を終えたらrowとソース、CSVを残すか削除します。外部サービスや常駐プロセスは使っていません。次のstride実験では、訪問数の違いを明示したまま間隔を変え、同じ比較方法を誤って流用しない練習をします。

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

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

CS基礎を固める · STEP 8

AI基盤へ進む · STEP 5

学習コースから次を選ぶ