latency・bandwidth・cache line

メモリアクセスには、主に2つの見方があります。

小さいデータを少しだけ読む場合は latency が効きやすく、大きな配列を連続して読む場合は bandwidth が効きやすくなります。

cache

CPUはメモリよりはるかに高速に演算できます。その差を埋めるために、CPUの近くには cache と呼ばれる小さく高速な記憶領域があります。よく使うデータや、近くのデータをcacheに置くことで、 CPUがメモリを待つ時間を減らします。

重要なのは、CPUがメモリから1個の f64 だけを読むとは限らないことです。多くの計算機では、メモリは cache line と呼ばれるまとまった単位でcacheへ運ばれます。典型的なcache lineは64バイト程度です。

f64 は8バイトなので、64バイトのcache lineには f64 が8個入ります。つまり、a[i] を読んだとき、近くの a[i + 1], a[i + 2] も同じcache lineに入っている可能性があります。

配列を先頭から順に読む場合、次に必要なデータが同じcache lineか、次のcache lineにある可能性が高くなります。このようなアクセスは計算機にとって予測しやすく、効率的です。

一方、遠く離れた要素を飛び飛びに読む場合、cache lineで運ばれたデータの多くを使わないまま捨てることになります。

連続アクセス:
  a[0], a[1], a[2], a[3], ...

飛び飛びアクセス:
  a[0], a[1024], a[2048], ...

数値計算では、同じ数式でも配列の並びとloop orderによって速度が変わります。これは、数学的な演算回数だけでなく、メモリからデータをどう運ぶかが効くためです。

実行時間の主な制約が浮動小数点演算である場合、その計算は compute bound です。一方、主な制約がメモリからデータを運ぶ速度である場合、その計算は memory bandwidth bound です。

大きな配列に対して単純な演算を1回ずつ行う処理は、memory bandwidth bound になりがちです。同じデータをcache上で何度も再利用できる処理は、compute bound に近づくことがあります。