コグノスケ


link 未来から過去へ表示(*)  link 過去から未来へ表示

link もっと前
2023年2月27日 >>> 2023年2月14日
link もっと後

2023年2月27日

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] とします。

SGEMM素朴版

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です。

SGEMM素朴版の実行時間
$ 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にするとシングルスレッド動作になります)で計算した時間を見ると、

OpenBLASのSGEMMを呼ぶコード

	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);
OpenBLASのSGEMM実行時間
$ 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倍という驚異のスピードです。すごいですね……。

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

編集者:すずき(2024/01/13 14:33)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



2023年2月25日

東京の道の名前

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

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

通称とは一体?

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

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

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

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

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

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

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

ということみたいです。

編集者:すずき(2023/02/27 00:16)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



link もっと前
2023年2月27日 >>> 2023年2月14日
link もっと後

管理用メニュー

link 記事を新規作成

<2023>
<<<02>>>
---1234
567891011
12131415161718
19202122232425
262728----

最近のコメント5件

  • link 21年3月13日
    すずきさん (03/05 15:13)
    「あー、このプログラムがまずいんですね。ご...」
  • link 21年3月13日
    emkさん (03/05 12:44)
    「キャストでvolatileを外してアクセ...」
  • link 24年1月24日
    すずきさん (02/19 18:37)
    「簡単にできる方法はPowerShellの...」
  • link 24年1月24日
    KKKさん (02/19 02:30)
    「追伸です。\nネットで調べたらマイクロソ...」
  • link 24年1月24日
    KKKさん (02/19 02:25)
    「私もエラーで困ってます\n手動での回復パ...」

最近の記事3件

  • link 24年3月25日
    すずき (03/26 03:20)
    「[Might and Magic Book One TASのその後] 目次: Might and Magicファミコン版以前(...」
  • link 21年10月4日
    すずき (03/26 03:14)
    「[Might and Magicファミコン版 - まとめリンク] 目次: Might and Magicファミコン版TASに挑...」
  • link 24年3月19日
    すずき (03/20 02:52)
    「[モジュラージャックの規格] 古くは電話線で、今だとEthernetで良く見かけるモジュラージャックというコネクタとレセプタク...」
link もっとみる

こんてんつ

open/close wiki
open/close Linux JM
open/close Java API

過去の日記

open/close 2002年
open/close 2003年
open/close 2004年
open/close 2005年
open/close 2006年
open/close 2007年
open/close 2008年
open/close 2009年
open/close 2010年
open/close 2011年
open/close 2012年
open/close 2013年
open/close 2014年
open/close 2015年
open/close 2016年
open/close 2017年
open/close 2018年
open/close 2019年
open/close 2020年
open/close 2021年
open/close 2022年
open/close 2023年
open/close 2024年
open/close 過去日記について

その他の情報

open/close アクセス統計
open/close サーバ一覧
open/close サイトの情報

合計:  counter total
本日:  counter today

link About www.katsuster.net
RDFファイル RSS 1.0

最終更新: 03/26 03:20