コグノスケ

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

目次: ベンチマーク

お手軽最適化のメモです。行列の掛け算を題材にします。

最初にお断りしておくとGEMMのような汎用処理の場合は、自分で最適化せずにOpenBLASを使ってください（素人が最適化しても勝てません）。しかしOpenBLASのような限界まで最適化されたコードは誰でも簡単には書ける、とは言えません。

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

GEMMってなんですか？

GEMMはGeneral Matrix Multiplyの略で、高校数学辺りでやった（はず）の行列の掛け算のことです。floatの場合はSGEMMと呼ばれ、doubleの場合はDGEMMと呼ばれます。最適化の題材はどちらでも良いんですけど、今回はSGEMMを使います。

忘れている方のために2行3列の行列Aと3行2列Bの掛け算A x B = Cだとこんな感じです。

行列の掛け算の例

Aの列数とBの行数は一致していなければなりません。行数と列数の関係を表すと、行列A（M行K列）x行列B（K行N列）= 行列C（M行N列）となります。

行列の掛け算の行数と列数

Cの1要素を計算するには、Aの1行とBの1列が必要です。式、および、視覚的に示すと下記のようになります。

行列の掛け算（式）

行列の掛け算（Aの行とBの列の関係）

説明はこれくらいにしてコードを見ましょう。

基本コース - 素朴に演算

SGEMMを素直にコードにするとこんな感じです。行方向にデータを格納（Row-major orderといいます）しているので、N列の行列Cのi行j列（以降Ci,jと書く）にアクセスする際はc[i * N + j] とします。

void sgemm_naive(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 k = 0; k < kk; k++) {
				c[i * nn + j] += a[i * kk + k] * b[k * nn + j];
			}
		}
	}
}

行列のサイズを適当に設定（M = 1519, N = 1517, K = 1523）して、実行時間を測ります。CPUはRyzen 7 5700Xです。

$ gcc -Wall -g -O2 -static sgemm.c

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

実行時間は実行するたびに変わりますが、大体2.27秒くらいでしょうか。OpenBLASのシングルスレッド（環境変数OPENBLAS_NUM_THREADS=1にするとシングルスレッド動作になります）で計算した時間を見ると、

	c_ex = malloc(m * n * sizeof(float) * 2);

	// C = alpha AB + beta C
	float alpha = 1.0f, beta = 0.0f;
	int lda = k, ldb = n, ldc = n;

	printf("----- use CBLAS\n");

	gettimeofday(&st, NULL);
	cblas_sgemm(CblasRowMajor, CblasNoTrans, CblasNoTrans,
		m, n, k, alpha, a, lda, b, ldb, beta, c_ex, ldc);
	gettimeofday(&ed, NULL);
	timersub(&ed, &st, &ela);

	printf("verify: %d.%06d\n", (int)ela.tv_sec, (int)ela.tv_usec);

$ export OPENBLAS_NUM_THREADS=1

$ gcc -Wall -g -O2 -static -L path/to/openblas/ sgemm.c -lopenblas

$ ./a.out
matrix size: M:1519, N:1517, K:1523
----- use CBLAS
verify: 0.052149

わずか0.05秒、実に43倍という驚異のスピードです。すごいですね……。

行列の掛け算の説明でほぼ終わってしまいました。お手軽最適化はまた次に。

東京の道の名前

東京の道はようわからん通称（明治通り、みたいなやつ）が付いています。東京育ちの人にはなじみ深い名前だと思うんですが、都外出身者からすると、東京の道の通称と国道何号線、都道何号線の区分が全く合っていないので、知らない場所の道の通称を言われると結構困ります。

なぜかというと国道何号線、都道何号線という表記は地図で省かれることはない一方で、東京の道の通称は高速道路や地下鉄と重なったときに省かれてしまうことがあるためです。地図を見ても「〇〇通り？何それ？どこ？？」と困惑します。

通称とは一体？

東京の道の通称は東京都が決めています（東京都通称道路名〜道路のわかりやすく親しみやすい名称〜 - 東京都建設局）。道案内の青看板に載るような名前と思ってもらえばわかりやすいでしょう。

東京都がまとめてくれているのはありがたいんですが「東京都が公式に定めた通称」というのは不思議な響きで、それは公称ではなかろうか？通称とは一体……？？

なぜか存在しない大正通り

東京の道の通称には「年号」＋「通り」という名前がいくつかあります。このうちなぜか大正通りだけは存在しません。不思議ですね。

• 江戸通り（No.26: 国道6号など、千代田区大手町二丁目〜台東区花川戸二丁目）
• 明治通り（No.3: 都道416, 306号など、港区南麻布二丁目〜江東区夢の島）
• 昭和通り（No.24: 国道4号など、港区新橋一丁目〜台東区根岸五丁目）

調べてみると割と有名な話らしいです（「明治通り」「昭和通り」はあるのに、なぜか「大正通り」はない東京のちょっとした謎 - アーバン ライフ メトロ）。詳しくは記事を読んでいただくとして、簡単に言えば、

• 東京日日新聞の公募で大正通りと呼ぼうとした（今の靖国通り）が定着せず
• 東京都の公募で靖国通りが選ばれた、東京都建設局のまとめる一覧に大正通りは入ってない
• 東京に「大正通り」はある（武蔵野市吉祥寺）
• 「平成通り」もある（中央区兜町〜築地二丁目）
• 「令和通り」はまだない

ということみたいです。