“what every programmer should know about memory”, 6.3 の prefetch の章を読み終わった。

hardware prefetch がなかなか面白くて、 stream を扱うバッファがいくつかあり、単純なアクセスやストライドアクセスなどの アクセスパターンを stream とみなして処理しているのを見て良く出来てるなーと関心してしまった。

これを見て考えていた問題が解決したように思えた。というのもペーパーの中で行列の掛け算を高速化する話があり、以下のようなコードが出てきて

// straight forward
for(i=0;i<N;i++)
  for(j=0;j<N;j++)
    for(k=0;k<N;k++)
      r[i][j] += a[i][k] * b[k][j];

// transpose
for(i=0;i<N;i++)
  for(j=0;j<N;j++)
    t[i][j] = b[j][i]

for(i=0;i<N;i++)
  for(j=0;j<N;j++)
    for(k=0;k<N;k++)
      r[i][j] += a[i][k] * t[j][k];

このコードはどちらも計算結果を r 配列に収めようとしていて、素直な方法と b 配列を転置してから計算する方法があり、transpose するほうが早いという話だった。実際 LLC が 4MB ほどの Core i5 MBP で計算してみると straight forward なほうが実行に 2.5 秒、transpose が 1.5 秒程となりちょっと驚いた。

transpose は処理が多いものの、実際の再内ループでは cache line を無駄なく使うようになっていて早いという話が書いてあった気がする。あーこの配列は double の配列なので、各要素は 8 byte となる。最近の cpu は大体 cache line が 64 byte になっており、要素がすべて隣接している場合は 8 要素 cache line に含まれる形になる。

しかしながら straight forward の再内ループに注目すると a[i][k] は cache line 境界をまたがない限りは同じ cache line に含まれそうだが b[k][j] はそうではなく b[k+1][j] となり cache line のうち 8 byte しか使えずかなり富豪的な使いかたをしてしまっている。

ところが、LLC がもっと大きい 12MB とか 16MB とかの cpu で同じように計算してみると straight forward と transpose の実行時間の差は見られなくなってしまった。これはなぜだ…と考えていたが、cache line を無駄使いするものの hardware prefetch 自体は stride を認識して問題なく動いていたためではなかろうかと考えられた。

そのつぎの Direct Cache Access も面白かった。パケット処理などの技術はこれらに支えられているんだなと。

あとこの本だと Core2 の時期なのでメモリコントローラがチップセット上の LSI にあるらしく FSB とその帯域の話がよく出てくるが今はもう使われていないため、昔は大変だったんだなという感想だった。