コグノスケ

Docker のお掃除コマンド

Docker を使っていると要らなくなったイメージ、コンテナ、ビルドキャッシュがたまってきて、/var ディレクトリ以下が肥大化していることがあります。いつも忘れてしまうお掃除用のコマンドをメモしておきます。

### 終了している container の削除

$ docker container prune

### 確認

$ docker container ls -a


### タグもなく使われていない image の削除

$ docker image prune

### 確認

$ docker image ls -a


### build cache の削除

$ docker builder prune

### 確認

$ docker builder ls

Docker がディスク容量をどの程度使用しているのかについては system df が便利（docker system df のマニュアル）です。

$ docker system df

TYPE            TOTAL     ACTIVE    SIZE      RECLAIMABLE
Images          1         1         14.26GB   0B (0%)
Containers      2         1         0B        0B
Local Volumes   0         0         0B        0B
Build Cache     17        0         0B        0B

昔はコマンドの名前に一貫性がなかった記憶がありますが、今は xxx ls とすれば大抵の場合は一覧が出るため統一感があります。私のようなライトユーザーがやりたいと思う程度の機能は、大抵既に存在しており良くできていてありがたいです。

SIMD を使ったお手軽最適化 - その 2

お手軽最適化のメモ、昨日の続きです。行列の掛け算を題材にします。前回は行列の掛け算と素朴な実装のコードを紹介しました。今回はお手軽最適化を紹介します。

スカラー処理だと遅いけれど、お手軽に最適化（数倍程度）がしたいときの参考になれば幸いです。

お手軽コース - 自動ベクトル化

素朴版のコードですと i, j, k の順でループになっていて、k を最内ループにしていました。ループ内の計算は、

c[i * nn + j] += a[i * kk + k] * b[k * nn + j]

でした。このときメモリアクセスのパターンは、

• A: 行方向に連続（メモリアクセスパターンは連続 = 自動ベクトル化できる）
• B: 列方向に連続（メモリアクセスパターンは飛び飛びアクセス = 自動ベクトル化できない）
• C: 同一要素を何度もアクセス

素朴版の計算順（i, j, k ループ）

です。GCC の自動ベクトル化ですと、このアクセスパターンをうまく最適化できないようです。対象が最内ループのみなのかもしれません。ループを入れ替え j を最内にして、B と C を行方向に読むようにします。するとメモリアクセスのパターンは、

• A: 同一要素を何度もアクセス
• B: 行方向に連続（メモリアクセスパターンは連続 = 自動ベクトル化できる）
• C: 行方向に連続（メモリアクセスパターンは連続 = 自動ベクトル化できる）

ループ入れ替え版の計算順（i, k, j ループ）

です。ループを入れ替えるとループ内で C の 0 初期化ができないので、ループの外に追い出して最終的に下記のようなコードになります。

void sgemm_inner(const float *a, const float *b, float *c, int mm, int nn, int kk)
{
	for (int i = 0; i < mm; i++) {
		for (int j = 0; j < nn; j++) {
			c[i * nn + j] = 0.0f;
		}
	}

	for (int i = 0; i < mm; i++) {
		for (int k = 0; k < kk; k++) {
			for (int j = 0; j < nn; j++) {    //★★j が最内ループ★★
				c[i * nn + j] += a[i * kk + k] * b[k * nn + j];
			}
		}
	}
}

$ gcc -Wall -g -O2 -fno-tree-vectorize -static -march=znver3 sgemm.c

$ ./a.out
matrix size: M:1519, N:1517, K:1523
time: 1.528314

（参考: 素朴版の実行時間）
time: 2.277758

（参考: OpenBLAS シングルスレッドの実行時間）
$ export OPENBLAS_NUM_THREADS=1

----- use CBLAS
verify: 0.052149

ループ入れ替えで倍くらい速くなっていますが、この最適化の本領はコンパイラの自動ベクトル化です。GCC ならば -ftree-vectorize オプションを指定すると、行列 B と行列 C へのアクセスに SIMD 命令を使うようになります。

Ryzen 7 5700X の場合は AVX2 命令を使えます。他の CPU をお使いの場合は -march を適宜変更してください。

$ gcc -Wall -g -O2 -ftree-vectorize -static -march=znver3 sgemm.c

$ ./a.out
matrix size: M:1519, N:1517, K:1523
time: 0.181133

（参考: OpenBLAS シングルスレッドの実行時間）
$ export OPENBLAS_NUM_THREADS=1

----- use CBLAS
verify: 0.052149

素朴版と OpenBLAS では 1/43 もの差がありましたが、ループ入れ替えと自動ベクトル化によって OpenBLAS の 1/3.5 程度まで近づきました。GEMM が計算偏重の処理で最適化の効果が出やすい、という点を考慮する必要はあるものの僅かな書き換えで得られる効果にしては割と良いのではないでしょうか。

もう少し頑張るコース - intrinsics

ソースコードを書き換える元気があれば、別の最適化方法もあります。GEMM 特有の話に近付いてしまい、汎用的な話から遠ざかりますが、最適化ポイントの例という意味では参考になるはず……です。たぶん。

今回は SIMD 命令で j の方向に一気に読むまでは同じですが、j の方向に進めるのではなく、k の方向に進めて、計算結果を C に足していく戦略です。具体的に言えば Ai,k と Bk,j 〜 Bk,j+7 の 8要素を一気に掛け算して Ci,j 〜 Ci,j+7 へ一気に足します。なぜ 8要素かというと AVX/AVX2 のレジスタ長（256bit）を使うと、32bit 長の float を一度に 8要素処理できるためです。

Intrinsics 版の計算順

SIMD 命令には Ai,k を SIMD レジスタの全要素に配る命令（set1_ps から生成される broadcast 命令）や、掛け算と足し算を一度に行う fmadd 命令など、この計算順に最適な命令が揃っています。

broadcast 命令

fmadd 命令

AVX/AVX2 の Intrinsics の詳細については Intel のサイトなどを見ていただくとして（Intel Intrinsics Guide）、コードは下記のようになります。

#include <immintrin.h>

void sgemm_avx(const float *a, const float *b, float *c, int mm, int nn, int kk)
{
	for (int j = 0; j < nn;) {
		if (nn - j >= 8) {
			for (int i = 0; i < mm; i++) {
				__m256 vc = _mm256_set1_ps(0.0f);

				for (int k = 0; k < kk; k++) {
					__m256 va = _mm256_set1_ps(a[i * kk + k]);
					__m256 vb = _mm256_loadu_ps(&b[k * nn + j]);
					vc = _mm256_fmadd_ps(va, vb, vc);
				}

				_mm256_storeu_ps(&c[i * nn + j], vc);
			}

			j += 8;
		} else {
			for (int i = 0; i < mm; i++) {
				c[i * nn + j] = 0.0f;
				for (int k = 0; k < kk; k++) {
					c[i * nn + j] += a[i * kk + k] * b[k * nn + j];
				}
			}

			j++;
		}
	}
}

$ gcc -Wall -g -O2 -static -march=znver3 sgemm.c

$ ./a.out
matrix size: M:1519, N:1517, K:1523
time: 0.384861

（参考: 素朴版の実行時間）
time: 2.277758

（参考: ループ入れ替え版＋自動ベクトル化の実行時間）
time: 0.181133

（参考: OpenBLAS シングルスレッドの実行時間）
$ export OPENBLAS_NUM_THREADS=1

----- use CBLAS
verify: 0.052149

素朴版と比べると 6倍速いですが、ループ入れ替え＋自動ベクトル化には負けています。

もう少し頑張るコース - ループアンローリング

先程のコードは SIMD レジスタを 3個しか同時に使っていませんでした。AVX/AVX2 の YMM レジスタは 16個もあるのに 3個しか使わないのはもったいですから、i のループを 8要素ずつアンローリングして SIMD レジスタを同時にたくさん使いましょう。レジスタをうまく使いまわせば 12要素のアンローリング（B の保持に 1個、C の保持に 12個、A の保持に 1個、計 14個）まではできそうです。たぶん。

#include <immintrin.h>

void sgemm_avx_unroll8(const float *a, const float *b, float *c, int mm, int nn, int kk)
{
	for (int j = 0; j < nn;) {
		if (nn - j >= 8) {
			int i = 0;

			for (; i < (mm & ~7); i += 8) {
				__m256 vc0 = _mm256_set1_ps(0.0f);
				__m256 vc1 = _mm256_set1_ps(0.0f);
				__m256 vc2 = _mm256_set1_ps(0.0f);
				__m256 vc3 = _mm256_set1_ps(0.0f);
				__m256 vc4 = _mm256_set1_ps(0.0f);
				__m256 vc5 = _mm256_set1_ps(0.0f);
				__m256 vc6 = _mm256_set1_ps(0.0f);
				__m256 vc7 = _mm256_set1_ps(0.0f);

				for (int k = 0; k < kk; k++) {
					__m256 vb = _mm256_loadu_ps(&b[k * nn + j]);

					__m256 va0 = _mm256_set1_ps(a[(i+0) * kk + k]);
					__m256 va1 = _mm256_set1_ps(a[(i+1) * kk + k]);
					__m256 va2 = _mm256_set1_ps(a[(i+2) * kk + k]);
					__m256 va3 = _mm256_set1_ps(a[(i+3) * kk + k]);
					__m256 va4 = _mm256_set1_ps(a[(i+4) * kk + k]);
					__m256 va5 = _mm256_set1_ps(a[(i+5) * kk + k]);
					__m256 va6 = _mm256_set1_ps(a[(i+6) * kk + k]);
					__m256 va7 = _mm256_set1_ps(a[(i+7) * kk + k]);

					vc0 = _mm256_fmadd_ps(va0, vb, vc0);
					vc1 = _mm256_fmadd_ps(va1, vb, vc1);
					vc2 = _mm256_fmadd_ps(va2, vb, vc2);
					vc3 = _mm256_fmadd_ps(va3, vb, vc3);
					vc4 = _mm256_fmadd_ps(va4, vb, vc4);
					vc5 = _mm256_fmadd_ps(va5, vb, vc5);
					vc6 = _mm256_fmadd_ps(va6, vb, vc6);
					vc7 = _mm256_fmadd_ps(va7, vb, vc7);
				}

				_mm256_storeu_ps(&c[(i+0) * nn + j], vc0);
				_mm256_storeu_ps(&c[(i+1) * nn + j], vc1);
				_mm256_storeu_ps(&c[(i+2) * nn + j], vc2);
				_mm256_storeu_ps(&c[(i+3) * nn + j], vc3);
				_mm256_storeu_ps(&c[(i+4) * nn + j], vc4);
				_mm256_storeu_ps(&c[(i+5) * nn + j], vc5);
				_mm256_storeu_ps(&c[(i+6) * nn + j], vc6);
				_mm256_storeu_ps(&c[(i+7) * nn + j], vc7);
			}

			for (; i < mm; i++) {
				__m256 vc = _mm256_set1_ps(0.0f);

				for (int k = 0; k < kk; k++) {
					__m256 vb = _mm256_loadu_ps(&b[k * nn + j]);
					__m256 va = _mm256_broadcast_ss(&a[(i+0) * kk + k]);
					vc = _mm256_fmadd_ps(va, vb, vc);
				}

				_mm256_storeu_ps(&c[i * nn + j], vc);
			}

			j += 8;
		} else {
			for (int i = 0; i < mm; i++) {
				c[i * nn + j] = 0.0f;
				for (int k = 0; k < kk; k++) {
					c[i * nn + j] += a[i * kk + k] * b[k * nn + j];
				}
			}

			j++;
		}
	}
}

$ ./a.out
matrix size: M:1519, N:1517, K:1523
time: 0.108420

（参考: ループ入れ替え版＋自動ベクトル化の実行時間）
time: 0.181133

（参考: OpenBLAS シングルスレッドの実行時間）
$ export OPENBLAS_NUM_THREADS=1

----- use CBLAS
verify: 0.052149

もはや最適化前のコードの原型がありませんが、ループ入れ替え版＋自動ベクトル化の 1.7倍くらいの速度になりました。OpenBLAS の 1/2 程度まで迫っています。この最適化手法が汎用的か？と聞かれると何とも言えないですが、SIMD レジスタを同時にたくさん使う、最内ループ以外もアンローリング（最内ループはコンパイラがやってくれる）辺りは割と汎用的なアイデアです。

あと前回言った通り、GEMM は最適化の題材として取り上げただけなので、実際に GEMM を計算する場合はこのコードや自分で書いたコードを使うのではなく、信頼と実績の OpenBLAS を使ってくださいませ。