キャッシュを考慮したコードを書いてみよう!

 

 

どうもこんにちは、勤続3年目にして業界3年目のプログラマーです。

今回はプログラムのお話をしていこうかと思います。
プログラムを行っていく上で最適化というものが必要になるケースが度々あると思いますが、
その最適化の手法の一つにキャッシュ・ブロッキングという方法があります。

キャッシュ・ブロッキングとは?

キャッシュ・ブロッキングはキャッシュに収まるようにデータ構造をブロック化します。
ブロック化の目的は、複数回使用されるデータをキャッシュに保持することでデータの再利用の機会を活用することにあります。

詳しい話はググってもらうとして、今日は実際にキャッシュブロッキングを考慮したプログラムを紹介していこうと思います。

実際のプログラム例

わかりやすい例が行列積の計算なので行列積のプログラムを紹介します。
というのも1年以上前にキャッシュブロッキングを使った行列積のコードを書いたのを思い出したのでこれをネタにしたブログを書いたというのもありますが;;
ちなみに実行環境は

  • CPU: core i7-6700K
  • OS: ubuntu LTS16.04
  • コンパイラ: g++ 5.40
    • 最適化オプション: -march=native -mtune=native -O3

となっています。
だいたい2年前ぐらいの環境です。

最適化なしの行列積プログラム

結果…

1024 * 1024行列同士の乗算プログラムです。

とりあえず10回ほど上のプログラムを回したところ、
平均およそ2.496秒
という感じになりました。
実際には10回という数字はかなり物足りないものだとは思いますが、気になる方は実際に上のコードを実行してみてください。

キャッシュを考慮したプログラム

上で挙げたmatrix_multiply関数にてdo_block関数を呼び出します。

結果…

BLOCK_SIZE*BLOCK_SIZEの部分行列を扱うことになります。今回は32*32の部分行列です。
double型(=8bytes)の要素を32*32=1024つをもつ行列3つのサイズ合計は24KiBなのでCore i7の32KiBのキャッシュに余裕を残して収まっています。
パタへネ本を参考にして書いたので詳細が気になる方は読んでみてください。

10回ほど上のプログラムを回したところ、
平均1.165秒
という感じになりました。さっきの1/2以下になりましたね。約2.14倍速です。

おまけ(OpenMPを使ったコード)

#pragma omp parallel forの一行を付け足すだけです。

結果…

めっちゃ早くなりましたね。約10.1倍速です^^
ちなみにAVXやループ展開などの手法を加えることでさらに早くなります。みなさんも興味があったら試してみてください。

 


コメント投稿は締め切りました。