---
title: 第6回 配信講義　計算科学技術特論A （2023）
tags:  #線形代数演算ライブラリ #blas #lapack  
author: [R-CCS　計算科学研究推進室](https://www.docswell.com/user/2300203199)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/4JZVVM5273.jpg?width=480
description: 第6回 5月25日　線形代数演算ライブラリ BLAS と LAPACK の基礎と実践１   一回目は、密行列のライブラリの決定版であるBLAS, LAPACKの紹介を行う。現在はもはや知らないで使っている場合がほとんどであるが、BLAS, LAPACKはどのような考え方で開発されているか、どうやって、どのように使えるか、コンピュータの仕組みも踏まえながら話をする。
published: May 22, 23
canonical: https://www.docswell.com/s/2300203199/ZQ81DV-2023-05-22-102059
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/4JZVVM5273.jpg)

線形代数演算ライブラリBLAS
とLAPACKの基礎と実践 (I)
BLAS, LAPACK入門編
中田 真秀
理化学研究所 開拓研究本部 柚木研
2023-05-25 13:00 (JST) 計算科学技術特論A
13:00


# Page. 2

![Page Image](https://bcdn.docswell.com/page/YE655NV6JV.jpg)

BLAS, LAPACK入門編 講義内容
1. 線形代数は重要
2. あらゆる分野で標準化が重要
3. コンピュータでの数値計算
4. コンピュータでの線形代数
5. BLAS, LAPACKは線形代数の事実上の標準的ライブラリ
6. BLASのプログラム例: dgemm (行列-行列積)
7. LAPACKのプログラム例: dsyev (行列の対角化)
8. はじめての行列-行列積高速化


# Page. 3

![Page Image](https://bcdn.docswell.com/page/GE5YY5D5E4.jpg)

線形代数は重要
• いまからでも遅くないから線形代数ちゃんと勉強または復習しと
こう
• 線形代数
連立一次方程式を解く 行列-行列積
• 学問の基本的に全ては線形代数で書ける
• なんでも(関数さえ)ベクトルに見えてくる→免許皆伝
• 抽象度が高い→自分の分野でイメージ作りするとよい
• 中田の場合は量子力学; 非常にイメージしやすかった。
• 人間は何かを線形代数の言葉でしか考えられないのかもしれない
a11 a12
a21 a22
A=
⋮
⋮
am1 am2
⋯
⋯
⋱
⋯
a1n
a2n
⋮
amn
x1
x = x2
x3


# Page. 4

![Page Image](https://bcdn.docswell.com/page/972GGN8G7R.jpg)

ChatGPT4先生に聞いてみた


# Page. 5

![Page Image](https://bcdn.docswell.com/page/DJYVVP6GJM.jpg)

我々はコンピュータで
線形代数ばかりやってきた
• 機械学習、AI
• ChatGPT, Stable Di
usion
• 行列-行列積を大量にやっている
• PlayStation5などでの3Dゲーム
• 宇宙は巨大な量子コンピュータ
ff
https://prtimes.jp/main/html/rd/p/000000033.000035388.html


# Page. 6

![Page Image](https://bcdn.docswell.com/page/V7NMM5Z8E8.jpg)

線形代数は紀元前までさかのぼれる
• 九章算術 方程より
• 中国、紀元前1世紀から紀
元後2世紀ころ、著者不詳
りゅう き
• 263年頃魏の時代に劉徽に
よって整理と注釈が加えら
れた。
• https://ctext.org/nine-chapters/fang-cheng/zh
• 人類史上初めての連立一次
•
方程式をGaussの消去法で
解いたと思う。
今でも1000年以上前の文
が何となく読めるのは凄い
https://zh.wikisource.org/wiki/Page:Sibu̲Congkan0392-劉徽-九章算術-3-3.djvu/8 より


# Page. 7

![Page Image](https://bcdn.docswell.com/page/YJ9NNYZXJ3.jpg)

九章算術 方程より 問題
• 有上禾三秉，中禾二秉，下禾一秉，實三十九斗；上禾二秉，中禾三
秉，下禾一秉，實三十四斗；上禾一秉，中禾二秉，下禾三秉，實二
十六斗。問上、中、下禾實一秉各幾何？答曰:上禾一秉，九斗、四分
斗之一，中禾一秉，四斗、四分斗之一，下禾一秉，二斗、四分斗之
三。
• 方程術曰，置上禾三秉，中禾二秉，下禾一秉，實三十九斗，於右
方。中、左禾列如右方。以右行上禾遍乘中行而以直除。又乘其次，
亦以直除。然以中行中禾不盡者遍乘左行而以直除。左方下禾不盡
者，上為法，下為實。實即下禾之實。求中禾，以法乘中行下實，而
除下禾之實。餘如中禾秉數而一，即中禾之實。求上禾亦以法乘右行
下實，而除下禾、中禾之實。餘如上禾秉數而一，即上禾之實。實皆
如法，各得一斗。


# Page. 8

![Page Image](https://bcdn.docswell.com/page/GJ8KK619ED.jpg)

九章算術 方程より 現代語訳
Powered by Google翻訳
• 問: 3束の上質のキビ、2束の中質のキビ、1 束の低質のキビが39個
のバケツに入っている。2束の上質のキビ、3束の中質のキビ、1束
の低質のキビが34個のバケツに入っている。1束の上質のキビ、2
束の中質のキビ、3束の低質のキビが26個のバケツに入っている。
上質、中質、低質のキビ1束はそれぞれバケツいくつになるか。
• 答: 上質 9 ¼ , 中質 4 ¼ , 低質 2 ¾ 個づつ
• 上質のキビ3束、中質のキビ3束、低質のキビ1束を39バケツを右行
に置く。中行、左行も右のように並べる。右の上質を中行にかけ、
右行で引く。また左行にもかけて右行から引く。次に、中行の中質
のキビの余りを左行にかけて、中行で引く。左の低質に余りがある
のでそして、割れば求まる(実を法で割る)。以下略


# Page. 9

![Page Image](https://bcdn.docswell.com/page/LJLZZ9QM7R.jpg)

九章算術 方程より 現代語訳
Powered by Google翻訳
•問
3x + 2y + z = 39⋯(右)
2x + 3y + z = 34⋯(中)
x + 2y + 3z = 26⋯(左)
• (右)はそのまま、(中)は(中)を3倍したものから(右)を2倍したものを引き、
(左)を3倍して(左)から(右)を引く。
3(2x + 3y + z = 34)
2(3x + 2y + z = 39)
3(x + 2y + 3z = 39)
3x + 2y + z = 39
5y + z = 24⋯(中)
4y + 8z = 39⋯(左)
• それから(左)を5倍する
3x + 2y + z = 39⋯(右)
5y + z = 24⋯(中)
20y + 40z = 195⋯(左)
36c = 99
あとは略


# Page. 10

![Page Image](https://bcdn.docswell.com/page/47MVVZ167W.jpg)

線形代数チートシート
•
•
a11 a12
a21 a22
A=
行列
⋮
⋮
am1 am2
ベクトルと基底
b = (b1, b2, b3, ⋯, bn)
x1
x = x2
x3
⋯
⋯
⋱
⋯
a1n
a2n
⋮
amn
∀x =
∑
i
ciei
1
e1 = 0
(0)
• 行列、ベクトルの線形結合
a, b ∈ R, x, y ∈ V → ax + by ∈ V
n
• 内積 a·b = ∑ aibi
i
• 行列と行列の掛け算
(AB)ij =
∑
k
Aik Bkj


# Page. 11

![Page Image](https://bcdn.docswell.com/page/P7R226LNJ9.jpg)

線形代数チートシート
• 連立一次方程式を解く
•
行列の特異値問題
• 行列の固有値問題
−1
Ax = b ⟶ x = A b
A = UΣV
Ax = λx
• エルミート行列とユニタリ行列
Hij =
• 行列の固有値と固有ベクトル
λ1
• 対角化
Hx = λx
U †HU =
0
λ2
T
−1
H*
U
ji
ij
0
λ3
⋱
λ∞
= U*
ji


# Page. 12

![Page Image](https://bcdn.docswell.com/page/PJXDDMW8EX.jpg)

あらゆる分野で標準化が重要
13:12


# Page. 13

![Page Image](https://bcdn.docswell.com/page/3JKXXGVLED.jpg)

あらゆる分野で標準化が重要
• International Organization for Standardization (ISO)
• ISOは、1国1加盟を基本として、157カ国の国家標準化機関が加盟するネットワーク
• 非常口ロゴマーク、カードサイズ、ねじ、食品安全、組織マネジメント...
• Request For Comments (RFC)
• Internet Engineering Task Forceが作る、インターネットのプロトコルの標準化。
個人参加が可能
• Système International d&#039;unités (SI) 単位系
• IEEE Standards Association
• 160ヶ国以上の共働志向のリーダーとともに、国際市場を創造・拡大し 健康と公共の安
全の保護を支援する合意形成に基づく組織
• 通信の規格 IEEE 802.11,
• 数値計算の標準化: IEEE 754
• binary32, binary64, binary128などの精度
• de fact standard:事実上の標準。


# Page. 14

![Page Image](https://bcdn.docswell.com/page/LE355NM6J5.jpg)

あらゆる分野で標準化が重要
• 標準化がないとどうなるか
• コンセントは各国で形状も電圧もばらばら
• 自動車は右を走るべきか左を走るべきか？
• 日本特有:電気の交流は50Hz or 60Hz
• 規格策定は各メーカー壮絶な戦い:ルール作る側はいつも強い
• SIがあるのに、ヤードポンド法を使うアメリカ (ネジが合わない)
• IEEE 754がない時
• 同じ数値計算プログラムの結果がコンピュータ、コンパイラのメーカーな
どによって変わる事多々。
• 線形代数演算には特に標準化はされてない
• しかし、往々にして規格というものは時代に追いつかない。


# Page. 15

![Page Image](https://bcdn.docswell.com/page/8EDDDW6MEG.jpg)

線形代数演算の標準化も重要
• 線形代数演算をコンピュータ上で行うなんらかの標準化はあっ
たほうが良い
• 事実上の標準ライブラリしかない
• 商業ベースで開発は難しいか。
• LAPACKは大学で外部資金で主に開発。NAGなど
• 似たライブラリが乱立すると極めてユーザーにとって不便
• BLASとLAPACKがあってよかった


# Page. 16

![Page Image](https://bcdn.docswell.com/page/V7PXX9YQE8.jpg)

コンピュータでの数値計算
13:16


# Page. 17

![Page Image](https://bcdn.docswell.com/page/2JVLLMGP7Q.jpg)

コンピュータでの実数演算はどうするか
•
コンピュータは有限の整数しか扱えないため、特別な表記
(フォーマット)を使う。
•
浮動小数点数表記 2進数で32桁、64桁などのビット列を実数と
みなす。
•
浮動小数点数は、符号、仮数部(fraction)、指数部(exponent)、
anは0 or 1から成る
fraction
n
exponent
⏞
1
± 1+
an
× 2m
∑ (2)
n=1
k
•
浮動小数点数を10進数で表す例。4ビット2進数−1.101 × 25 を10
進数になおす。
−1.101 × 25 = − (1 + 1 × 0.5 + 0 × 0.25 + 1 × 0.125) × 32 = 52


# Page. 18

![Page Image](https://bcdn.docswell.com/page/5EGXXG8QJL.jpg)

コンピュータでの数の取扱いbinary64 (倍精度)
•
“754-2019 IEEE Standard for Floating-Point Arithmetic”
•
binary64 フォーマットは 10進16桁の有効桁がある (よく倍精度とよぶ)
fraction
n
exponent
1
± 1+
an
× 2−1022∼1023
∑ (2)
n=1
52
•
•
binary32,128 などもある (単精度、四倍精度とよく呼ばれる)。
この規格に則って演算する場合がほとんど(最近の例外:PlayStation2)
•
規格が無いときはコンピュータ毎に違う結果が得られたりした
•
b oat16等、半精度もでてきたが、IEEE 754規格外!! 混乱の予想
• FLOPS(フロップス）という単語が頻出
• 1秒間に1回浮動小数点数が計算できること=Floating point operation per
second
• 速さ:Core i7 (Broadwell, 10 cores, 3.5GHz): 560GFlops, NVIDIA
fl
TESLA H100: 34TFlops〜PFlops, 京コンピュータ10PFLOPS, HOKUSAI
(3PFlops)、富岳：400PFlops (2022/5まで世界一) 世界一: Frontier@US
1.1ExaFlops


# Page. 19

![Page Image](https://bcdn.docswell.com/page/4JQ88X9W7P.jpg)

コンピュータでの線形代数
13:19


# Page. 20

![Page Image](https://bcdn.docswell.com/page/K74226X1J1.jpg)

自作は避けたほうがいい
• 線形代数演算をコンピュータでやるとき、プログラムを自作する場合が
あるかもしれないが、自作は避けたほうがいい
• 無駄な計算をしてしまうことがある。
• クラメールの公式を使うと宇宙時間待っても答えが出ない。
• 誤差が大きくなることがある。
•
逆行列は数値誤差を多く含む
数値アルゴリズムにおける精度と安定性
Accuracy and Stability of Numerical Algorithms, N. Higham 2002
• 行列の条件数が大きいと誤差も大きくなる
• 速いコンピュータのはずがパフォーマンスが出ない
• カタログに出てる理論性能値と比べて、1/100の速度しか出ない？
計算科学のためのHPC技術1
まずは既存のライブラリを探すこと
安直だが


# Page. 21

![Page Image](https://bcdn.docswell.com/page/LJ1MMVN5EG.jpg)

自作して失敗する例:連立一次方程式を
クラメールの公式で解く
• 以下のような連立一次方程式を解く。
a11x1 + a12 x2 + ⋯ + a1n xn = b1,
a21x1 + a22 x2 + ⋯ + a2n xn = b2,
⋮
an1x1 + an2 x2 + ⋯ + ann xn = bn
a11 a12
a21 a22
A :=
⋮ ⋮
an1 an2
⋯
⋯
⋱
⋯
a1n
a2n
,
⋮
ann
x1
x2
x :=
,
⋮
xn
b1
b2
b :=
⋮
bn
Ax = b
• 解は
a1,1 ⋯ a1,i−1 b1 a1,i+1 ⋯ a1,n
a2,1 ⋯ a2,i−1 b2 a2,i+1 ⋯ a2,n
Ai :=
⋮
⋮
⋮
⋮
⋮
an,1 ⋯ an,i−1 bn an,i+1 ⋯ an,n
• として、行列Bに対する行列式det(B)を用いて、以下のようにかける。
det(Ai)
xi =
det(A)


# Page. 22

![Page Image](https://bcdn.docswell.com/page/GJW33L4WJ2.jpg)

自作して失敗する例:連立一次方程式を
クラメールの公式で解く
• 理論的にはクラメールの公式を使ってプログラムを作ると、
コンピュータで解ける。
• しかしながら、行列のサイズ n が大きくなるとすぐ解けな
くなる。
• n=10で 36288000 回の演算
•
n = 100 で 9.3 x 10157回の演算
• あっというまに宇宙時間より長い時間が必要になる。


# Page. 23

![Page Image](https://bcdn.docswell.com/page/4EZVVM22J3.jpg)

自作して失敗する例:行列-行列積
ナイーブに作ると30-40倍くらい遅くなることがある̲
• 2000x2000の行列積AB＝Cを教科書どおりに計算するプログ
ラムを作って
• 0.4GFlops
(AB)ij =
∑
k
Aik Bkj
•最適化されたBLASを用いた場合
$ octave
... 途中略...
octave:1&gt; n=4000; A=rand(n); B=rand(n);
octave:2&gt; tic(); C=A*B; t=toc();
octave:3&gt; GFLOPS=2*n^3/t*1e-9
GFLOPS =84.1GFlops
マシン：MacBookPro (2017) i5-7360U 2.3-3.6GHz 2 cores
理論性能：73-115GFlops


# Page. 24

![Page Image](https://bcdn.docswell.com/page/Y7655566EV.jpg)

分野の違いと意識の違い
(偏見あり)
• 数学者の意識 : 原理的に可能, 解の存在のみ興味ある場合が多い
• 情報系の数学より : アルゴリズムが多項式程度なものを考えたがる
• 自然科学系研究者 : ともかく答えが求まる方法なら何でも良い
• とりあえず求まればよい。問題が出るまで放置。よく指数関数的なアル
ゴリズムを意識せずにゴリ押しする。
• HPC or 数値解析系研究者 : 1 clockでも速い方法 1bitでも転送量が少な
い方法、1桁でも精度の良い方法などから選択
• ハード依存高め。さまざまな現実的な制限を考慮し、なるべく良い結果
を出す。


# Page. 25

![Page Image](https://bcdn.docswell.com/page/G75YYY6574.jpg)

分野の違いと意識の違い (偏見あり)
連立一次方程式をどう解くか
• 数学者の意識 : 行列式が0でないなら解ける。終わり
• 情報系の数学より : LU分解も逆行列求める方法もオーダーは同じ
O(n^3)なので違いはない、クラメールはO(n!)なんで論外。
• 自然科学系研究者 : とりあえず逆行列求めとこう。LU分解って何? 解
きたい問題は別だし他に考えるべきことが多いし後まわしにしよう。
• 最近はnumpyになげときゃいいや
(実は正解)
• HPC or 数値計算系研究者 : LU分解経由一択。基本であるdgemm
だからキャッシュヒットも高いし、逆行列を使うより誤差もない少
よってLU分解経由以外あり得ない。クラメールは誤差も大きい。


# Page. 26

![Page Image](https://bcdn.docswell.com/page/9J2GGGMGJR.jpg)

BLAS, LAPACKは事実上の
標準の線形代数ライブラリ
13:28


# Page. 27

![Page Image](https://bcdn.docswell.com/page/DEYVVVXGEM.jpg)

線形代数演算ならBLAS, LAPACKを使おう
• 行列、ベクトルなどの線形代数演算のライブラリはある?
• BLASやLAPACKを用いましょう。
• コンピュータの仕組みを軽く知っておくと、手軽に高速な
ライブラリの利用方法がわかる
• 今回はBLAS, LAPACKをとりあえず使ってみる、という
ことをやります


# Page. 28

![Page Image](https://bcdn.docswell.com/page/VJNMMM1878.jpg)

BLAS, LAPACK:世界最高の線形代数演算パッケージ
• コンピュータで線形代数演算するならBLAS+LAPACKを使いましょう。
• 品質、信頼性がとても高く、無料で入手できる
• http://www.netlib.org/lapack/
• 標準で高速版がインストールされていることが多い
• http://www.openblas.net/
• 密行列のみ対応(疎行列は他のライブラリを利用する)。
• コンピュータでの行列線形代数演算の基礎中の基礎!
BLAS, LAPACKは人類の至宝


# Page. 29

![Page Image](https://bcdn.docswell.com/page/YE9NNN5XE3.jpg)

BLAS, LAPACKを利用したソフトウェア
• 著名な計算プログラムパッケージは大抵BLAS, LAPACKを利用して
いる.
• 機械学習系はほぼcuBLASを使ってる
• 物理、化学ではGaussian, Gamess, ADF, VASP
• 線形計画問題のCPLEX, NUOPT, GLPKなど..
• 高級言語からも利用可能
• Ruby, Python (numpy), Perl, Java, C, Mathematica, Maple,
Matlab, R, octave, SciLab


# Page. 30

![Page Image](https://bcdn.docswell.com/page/GE8KKKY97D.jpg)

BLAS : 基本的な線形代数サブプログラム群
•BLASはBasic Linear Algebra Subprogramsの略
•基礎的な線形代数の「サブ」プログラム Level 1 〜 3まである
•Level 1 : ベクトル-ベクトルの内積など x ⋅ y
•Level 2 : 行列-ベクトル積など
y ← αAx + βy
•Level 3 : 行列-行列積など
C ← αAB + βC
•Fortran90でさまざまなルーチンの仕様を提供している。
•参照実装の形で提供されている (Reference BLAS)
•BLASのルーチンを「ブロック」にしてより高度なことをする。
•この実装を「お手本」とする
•とても美しいコード!
•高速版もある。


# Page. 31

![Page Image](https://bcdn.docswell.com/page/LELZZZ4MJR.jpg)

Level 1 BLAS
• Level 1:ベクトル-ベクトル演算(+そのほか)のルーチン
• ベクトルの加算 DAXPY
y ← αAx + βy
• 内積計算: DDOT
&lt; x, y &gt; =
∑
i
• 2-ノルム計算
||x|| =
N
∑
i
xi yi
| xi |2
• など15種類あり, さらに単精度, 倍精度, 複素単精度, 複素数倍精
度についての4通りの組み合わせがある.


# Page. 32

![Page Image](https://bcdn.docswell.com/page/4JMVVVK6JW.jpg)

Level 2 BLAS
• Level 2:行列-ベクトル演算のルーチン
• 行列-ベクトル積: DGEMV
y ← αAx + βy
• 上三角行列とベクトルの積:DTRMV
x ← Ax
• 上三角行列の連立一次方程式を解く:DTRSV
x ← A −1x
• 列ベクトルと行ベクトルの積: DGER
A ← αxy t + A
• など25種類あり, 同じように単精度、倍精度、複素数の4通
りの組み合わせがある。


# Page. 33

![Page Image](https://bcdn.docswell.com/page/PJR222XNE9.jpg)

Level 3 BLAS
• Level 3 BLASは行列-行列演算のルーチン群
• 行列-行列積: DGEMM
C ← αAB + βC
• 対称行列-行列積: DSYMM
C ← αAB + βC
• 上(下)三角行列と行列の積: DTRMM
B ← αAB
• 対称行列の階数nの更新: DSYRK
C ← αAA T + βC
• 上三角行列の連立一次方程式を解く: DTRSM
• など9種類ある。
B ← αA −1B


# Page. 34

![Page Image](https://bcdn.docswell.com/page/PEXDDD687X.jpg)

BLAS Quick Reference
https://www.netlib.org/lapack/lug/node145.html


# Page. 35

![Page Image](https://bcdn.docswell.com/page/3EKXXX1L7D.jpg)

BLAS Quick Reference
https://www.netlib.org/lapack/lug/node145.html


# Page. 36

![Page Image](https://bcdn.docswell.com/page/L73555Q6E5.jpg)

LAPACKとは?
•LAPACK(Linear Algebra PACKage) : 線形代数パッケージ
•BLASをビルディングブロックとして使いつつ、より高度な問題である連立一次方
程式、 最小二乗法固有値問題、固有値問題、特異値問題を解くことができる.
•下請けルーチン群も提供する: 行列の分解(LU分解, コレスキー分解, QR分解, 特異
値分解, Schur分解, 一般化Schur分解)、条件数の推定ルーチン, 逆行列計算など。
•品質保証も非常に精密かつ系統的で、信頼がおける。
•パソコンからスーパーコンピュータまで様々なCPU、OS上で動く。
•Fortran 90で書かれ、3.11.0は1900以上のルーチンからなっている。
•webサイトはなんと約2億ヒット以上である
•githubで開発が続いている https://github.com/Reference-LAPACK
http://www.netlib.org/lapack


# Page. 37

![Page Image](https://bcdn.docswell.com/page/87DDDD9M7G.jpg)

LAPACK公式ドキュメント
• http://www.netlib.org/lapack/lug/ : ユーザーガイ
ド
• http://www.netlib.org/lapack/faq.html : FAQ
• http://www.netlib.org/lapack/lawns/index.html
LAWN: LAPACK Working Notes : 実装の詳細、アル
ゴリズム、パフォーマンスの比較など。
• 不断の努力の積み重ね


# Page. 38

![Page Image](https://bcdn.docswell.com/page/VJPXXXZQ78.jpg)

線形代数+コンピュータで最重要タスクたち
•連立一次方程式問題 : Ax=b
•最小二乗法 min ||b-Ax||
•固有値問題 Ax=λx
•特異値問題 M = UΣV*
規模、精度、行列のタイプ、解き方に多様な応用がある


# Page. 39

![Page Image](https://bcdn.docswell.com/page/2EVLLLWPJQ.jpg)

LAPACKのルーチンの種類
• Driver routines : 先程あげた固有値、連立一次方程式を解く
• Simple driver:
• Expert driver: Simple driverに比べて、条件数推定、解の改善、エラー
バウンド、行列の平衡化などを行う
• Computational routines
• 上記タスクなどのために行うLU分解や三角行列のリダクションを行うが
BLASよりは高級な処理を行う
• Auxiliary routines
• blockアルゴリズムのサブタスク、行列ノルム、スケーリングなどBLASの拡
張またはBLASに入れたほうがいいルーチンなど低レベル処理


# Page. 40

![Page Image](https://bcdn.docswell.com/page/57GXXXDQEL.jpg)

LAPACKで連立一次方程式を解く
simple driverたち
http://www.netlib.org/lapack/lapackqref.ps


# Page. 41

![Page Image](https://bcdn.docswell.com/page/4EQ8881WJP.jpg)

LAPACKで最小二乗法を解く
simple driverたち
http://www.netlib.org/lapack/lapackqref.ps


# Page. 42

![Page Image](https://bcdn.docswell.com/page/KJ4222R1E1.jpg)

LAPACKで一般化固有値問題、一般化特異値問題を解く
simple &amp; divide and conquer driverたち
http://www.netlib.org/lapack/lapackqref.ps


# Page. 43

![Page Image](https://bcdn.docswell.com/page/LE1MMMQ57G.jpg)

LAPACKで標準固有値問題、特異値問題を解く
simple &amp; dvide and conqure driverたち
http://www.netlib.org/lapack/lapackqref.ps


# Page. 44

![Page Image](https://bcdn.docswell.com/page/GEW333MWE2.jpg)

様々な解法が存在していて、
様々なルーチンが存在する
• たくさんLAPACKのルーチンを提示したが、これにそれ
ぞれExpert driverや、RRR (relatively robust
representation) 版などが存在する。
• simple/divide and conquer/RRR/Expertからどう
やって選べばよいか?
• これは問題に応じて個々人が選ぶ必要が出てくる。


# Page. 45

![Page Image](https://bcdn.docswell.com/page/47ZVVVQ2E3.jpg)

LAPACKのルーチン構造
• 例えば実対称行列の固有値を求めるのにはdsyevを使ったが下
請けには34のルーチン群がある。
• dorgtr, dorgql, dorg2l, dorgqr, dlarfb
• dlarf, dgemm, dcopy, dtrmv, dgemv, dger
• dsyr2k, dlatrd, dsytd2, daxpy, dsymv, dlarfg,
• dsyr2, dscal, dsteqr, dsterf, dlaev2, dlartg,
• dlaset, swap, dlascl, dlasr, dlasrt, dlae2
dsyevルーチン相関図


# Page. 46

![Page Image](https://bcdn.docswell.com/page/YJ6555N67V.jpg)

LAPACKのルーチン構造
• 実特異値分解はもっと複雑。dgesvdだけでも
3503行あるが、殆どが総計46の下請けルー
チンをコールしている。
dgesvdルーチン相関図


# Page. 47

![Page Image](https://bcdn.docswell.com/page/GJ5YYY55J4.jpg)

BLASプログラム例:dgemm
行列-行列積
13:40


# Page. 48

![Page Image](https://bcdn.docswell.com/page/LE3555N5J5.jpg)

BLAS、LAPACKのインストール
• BLAS、LAPACKの開発環境を整える on Ubuntu 22.04
$ sudo apt-get update ; sudo apt-get upgrade
$ sudo apt-get install gfortran g++ libblas-dev liblapack-dev
liblapacke-dev
...
g++ is already the newest version (4:11.2.0-1ubuntu1).
gfortran is already the newest version (4:11.2.0-1ubuntu1).
libblas-dev is already the newest version (3.10.0-2ubuntu1).
liblapack-dev is already the newest version (3.10.0-2ubuntu1).
liblapacke-dev is already the newest version (3.10.0-2ubuntu1).
0 upgraded, 0 newly installed, 0 to remove and 6 not upgraded.
• こんな感じであればok


# Page. 49

![Page Image](https://bcdn.docswell.com/page/8EDDDDWYEG.jpg)

行列-行列の積 DGEMMを使ってみる
• 行列-行列積DGEMMを使ってみる。ここでは
1 8
3
A = 2 10 8
9 −5 −1
9 8 3
B = 3 11 2.3
−8 6 1
α = 3,β = − 2
C ← αAB + βC
• を計算するプログラムを書いてみる.
• 答えは以下のようになる
21 336 70.8
−64 514 95
210 31 47.5
3 3 1.2
C= 8 4 8
6 1 −2


# Page. 50

![Page Image](https://bcdn.docswell.com/page/V7PXXX92E8.jpg)

行列-行列の積:DGEMMの詳細
C ← αAB + βC
• 今回はCBLASから、BLASを呼んでみる。
• BLASはFORTRANで書かれているが、Cから呼び出すことも可能。プロトタイプ宣言は以下のようになる
void cblas̲dgemm(CBLAS̲LAYOUT layout, CBLAS̲TRANSPOSE TransA,
CBLAS̲TRANSPOSE TransB, const int M, const int N, const int K, const double alpha, const
double *A, const int lda, const double *B, const int ldb, const double beta, double *C, const
int ldc);
• layout : Column major or Row major
• “transa”, “transb”, “transc” で行列を転置するか否かを指定。
• m, n, k は行列の次元。左図参照
• alpha, betaは行列積に対する掛けるスカラー
• A, B, CはRow major形式で格納した行列へのポインタ
• lda, ldb, ldc は 行列A, B, Cへのleading dimensionたち
• 配列はゼロから始まるか1からはじまるか
ここらへんがわかりにくいところ


# Page. 51

![Page Image](https://bcdn.docswell.com/page/2JVLLLMX7Q.jpg)

FortranとCの違いの吸収
配列は0か1から始める? 多次元配列を手で展開
• Fortranでは配列は1からスタートするのが普通が, C, C++では, 0か
らのみスタートする. 例えば
• ループの書き方が一般的には1からNまで(FORTRAN)か, 0からn
未満か(C,C++).
• ベクトルのxi要素へのアクセスはFORTRANではX(I)だが, Cでは
x[i-1]となる.
• 多次元配列はC/C++にはない。一次元配列に手で展開する。
• 行列のAij要素へのアクセスはFORTRANではA(I,J)だが, Cでは
column majorとしてA[i-1+ (j-1)*lda]とするとよい


# Page. 52

![Page Image](https://bcdn.docswell.com/page/5EGXXXGRJL.jpg)

行列をColumn majorでメモリに格納する
• 行列は2次元だが、コンピュータのメモリは1次元的である。次のような行
列を
A=
1 2 3
(4 5 6)
• 考えるとき、どのようにメモリに格納するか? column major式では、
• アドレスの小さい順から
1, 4, 2, 5, 3, 6
• のように格納する。
• FORTRANや、Matlab, octaveはcolumn majorである。


# Page. 53

![Page Image](https://bcdn.docswell.com/page/4JQ888XY7P.jpg)

行列をRow majorでメモリに格納する
同じように、行列A
1 2 3
A=
(4 5 6)
• について、row majorでは、行方向に
• 1, 2, 3, 4, 5, 6
• のように格納する。C/C++では普通row majorで格納。意
識的にcolumn majorにしたほうが良い
• BLAS, LAPACKを呼び出すときは、行列格納方法に注意!


# Page. 54

![Page Image](https://bcdn.docswell.com/page/K742226ZJ1.jpg)

行列-行列の積 DGEMMを使ってみる
• 行列-行列積DGEMMを使ってみる。ここでは
1 8
3
A = 2 10 8
9 −5 −1
9 8 3
B = 3 11 2.3
−8 6 1
α = 3,β = − 2
C ← αAB + βC
• を計算するプログラムを書いてみる.
• 答えは以下のようになる
21 336 70.8
−64 514 95
210 31 47.5
3 3 1.2
C= 8 4 8
6 1 −2


# Page. 55

![Page Image](https://bcdn.docswell.com/page/LJ1MMMVDEG.jpg)

行列-行列の積のリスト
#include &lt;stdio.h&gt;
#include &lt;cblas.h&gt;
//Matlab/Octave format
void printmat(int N, int M, double *A, int LDA) {
double mtmp;
printf(&quot;[ &quot;);
for (int i = 0; i &lt; N; i++) {
printf(&quot;[ &quot;);
for (int j = 0; j &lt; M; j++) {
mtmp = A[i + j * LDA];
printf(&quot;%5.2e&quot;, mtmp);
if (j &lt; M - 1) printf(&quot;, &quot;);
} if (i &lt; N - 1) printf(&quot;]; &quot;);
else printf(&quot;] &quot;);
} printf(&quot;]&quot;);
}
int main()
{
int n = 3; double alpha, beta;
double *A = new double[n*n];
double *B = new double[n*n];
double *C = new double[n*n];
A[0+0*n]=1; A[0+1*n]= 8; A[0+2*n]= 3;
A[1+0*n]=2; A[1+1*n]=10; A[1+2*n]= 8;
A[2+0*n]=9; A[2+1*n]=-5; A[2+2*n]=-1;
B[0+0*n]= 9; B[0+1*n]= 8; B[0+2*n]=3;
B[1+0*n]= 3; B[1+1*n]=11; B[1+2*n]=2.3;
B[2+0*n]=-8; B[2+1*n]= 6; B[2+2*n]=1;
C[0+0*n]=3; C[0+1*n]=3; C[0+2*n]=1.2;
C[1+0*n]=8; C[1+1*n]=4; C[1+2*n]=8;
C[2+0*n]=6; C[2+1*n]=1; C[2+2*n]=-2;
printf(&quot;# dgemm demo...\n&quot;);
printf(&quot;A
=&quot;);printmat(n,n,A,n);printf(&quot;\n&quot;);
printf(&quot;B
=&quot;);printmat(n,n,B,n);printf(&quot;\n&quot;);
printf(“C
=&quot;);printmat(n,n,C,n);printf(&quot;\n&quot;);
alpha = 3.0; beta = -2.0;
cblas_dgemm(CblasColMajor,CblasNoTrans,Cbl
asNoTrans, n, n, n, alpha, A, n, B, n,
beta, C, n);
printf(&quot;alpha = %5.3e\n&quot;, alpha);
printf(&quot;beta = %5.3e\n&quot;, beta);
printf(&quot;ans=&quot;); printmat(n,n,C,n);
printf(&quot;\n&quot;);
printf(&quot;#check by Matlab/Octave by:\n&quot;);
printf(&quot;alpha * A * B + beta * C =\n&quot;);
delete[]C; delete[]B; delete[]A;
}


# Page. 56

![Page Image](https://bcdn.docswell.com/page/GJW333L8J2.jpg)

行列-行列の積のコンパイルと実行
• 先ほどのリストを&#039;&#039;dgemm_demo.cpp&#039;&#039;などと保存する。
$ g++ dgemm_demo.cpp -o dgemm_demo -lblas -lapack
• でコンパイルができる. 何もメッセージが出ないなら, コンパイルは成功である。実行
は以下のようになっていればよい。OctaveやMatlabにこの結果をそのままコピー&amp;
ペースとすれば答えをチェックできるようにしてある
alpha = 3.000e+00
beta
= -2.000e+00
ans=[ [ 2.10e+01, 3.36e+02, 7.08e+01]; [ -6.40e+01, 5.14e+02, 9.50e+01];
[ 2.10e+02, 3.10e+01, 4.75e+01] ]
#check by Matlab/Octave by:
alpha * A * B + beta * C


# Page. 57

![Page Image](https://bcdn.docswell.com/page/4EZVVVM9J3.jpg)

Block行列が便利になる例
• 行列の積を考える
C = AB, Cij =
∑
k
Aik Bkj
• 行列積の定義は、要素ごとに積をとって和を取るだが、区
分行列にわけても、そのまま「数」のように積をとってよ
い
A A
⋯ A
B B
⋯ B
11
12
1q
⋯
A2q
C11 C12
C21 C22
AB =
⋮
⋮
Cp1 Cp2
⋯
⋯
⋱
⋯
C1r
C2r
⋮
Cpr
⋮
⋮
Ap1 Ap2
⋱
⋯
12
B21 B22
, B=
⋮
⋮
⋮
Bq1 Bq2
Apq
A21 A22
A=
11
Cij =
q
∑
k=1
⋯
⋱
⋯
Aik Bkj
1r
B2r
⋮
Bqr


# Page. 58

![Page Image](https://bcdn.docswell.com/page/Y76555NDEV.jpg)

Leading dimensionについて
• 行列をさらに小さい行列に分けて考えることがある。
• これらを区分行列、小行列、ブロック行列などとよぶ。
• たとえば 以下のように、A, B, C, Dという行列を考えて
2 −1 5
A = −1 4
1 ,
(8
1 −2)
−3 6
B= 1 3 ,
(
)
4 1
C = (−4 2 6),
D = (9 1)
• それらを組み合わせてより大きな行列を作ることができ
る。


# Page. 59

![Page Image](https://bcdn.docswell.com/page/G75YYY5874.jpg)

Leading dimensionについて
• 行列Aの区分行列A&#039;にアクセスするにはど
うしたらいい？
• leading dimensionを使うとよい。
• numpyのスライス、Fortran90の部分配
列に相当する。しかしCやC++にはない...
• 関数をまたぐと、スライスでは対応で
きなくなり、ldを渡す必要アリ
• Aʼ[1,1] のアドレスから、Aʼ[P,Q]は
Aʼ[1,1]+P*m+Qではなくて、
Aʼ[1,1]+P*LDA+Qとアクセスする。


# Page. 60

![Page Image](https://bcdn.docswell.com/page/9J2GGGNVJR.jpg)

たかが(?)行列積なのに
超めんどくさい
• numpyならA*Bですむのになんで？
• 高速なライブラリをちゃんと設計するとこうなる
• コンピュータへの分かりやすさ、人間への分かりやすさの違い


# Page. 61

![Page Image](https://bcdn.docswell.com/page/DEYVVVPQEM.jpg)

LAPACKプログラム例:
対称行列の対角化 (dsyev)
14:00


# Page. 62

![Page Image](https://bcdn.docswell.com/page/VJNMMM5278.jpg)

LAPACK実習:
行列の固有ベクトル、固有値を求める:DSYEV
• 3x3 の実対称行列の固有ベクトル、固有値を求めよう。これらは三つあり、
1 2 3
A= 2 5 4
3 4 6
Avi = λivi (i = 1,2,3)
という関係式が成り立つ。
• 固有値 λ1, λ2, λ3 は
• で、 固有ベクトルは、
−0.40973,1.57715,10.83258
v1 = (−0.914357,0.216411,0.342225)
v2 = (0.040122, − 0.792606,0.608413)
v3 = (0.402916,0.570037,0.716042)
となる


# Page. 63

![Page Image](https://bcdn.docswell.com/page/YE9NNNYDE3.jpg)

行列の固有ベクトル、固有値を求めるDSYEV
•C/C++からLAPACKをコールするにはLAPACKEを用いる。プロトタイプは以下の通り
•lapack_int
LAPACKE_dsyev( int matrix_layout, char jobz, char uplo,
lapack_int n, double* a, lapack_int lda, double* w );
•matrix̲layout : LAPACK̲COL̲MAJOR: column majorかrow majorか
•jobz:固有値、固有ベクトルが必要か、固有値だけでよいか指定。
•uplo:行列の上三角、下三角を使うか。
•A, lda:行列Aとそのleading dimension
•w:固有値を返す配列(昇順)
(注意) 以下はFORTRANを直接呼ぶ場合は必要だったが、LAPACKEではなくなった
• work, lwork:ワーク領域への配列またはポインタ、とそのサイズ
• info: =0 正常終了。&lt;0: INFO=-iではi番目の引数が不適当。&gt;0: INFO=i 収束せず。


# Page. 64

![Page Image](https://bcdn.docswell.com/page/GE8KKK657D.jpg)

対称行列の対角化dsyevの例
#include &lt;iostream&gt;
#include &lt;stdio.h&gt;
#include &lt;lapacke.h&gt;
//Matlab/Octave format
void printmat(int N, int M,
double *A, int LDA) {
double mtmp;
printf(&quot;[ &quot;);
for (int i = 0; i &lt; N; i++) {
printf(&quot;[ &quot;);
for (int j = 0; j &lt; M; j++) {
mtmp = A[i + j * LDA];
printf(&quot;%5.2e&quot;, mtmp);
if (j &lt; M - 1) printf(&quot;, &quot;);
} if (i &lt; N - 1) printf(&quot;]; &quot;);
else printf(&quot;] &quot;);
} printf(&quot;]&quot;);
}
int main()
{
int n = 3;
double *A = new double[n*n];
double *w = new double[n];
//setting A matrix
A[0+0*n]=1;A[0+1*n]=2;A[0+2*n]=3;
A[1+0*n]=2;A[1+1*n]=5;A[1+2*n]=4;
A[2+0*n]=3;A[2+1*n]=4;A[2+2*n]=6;
printf(&quot;A =&quot;); printmat(n, n, A, n);
printf(&quot;\n&quot;);
LAPACKE_dsyev(LAPACK_COL_MAJOR,
&#039;V&#039;, &#039;U&#039;, n, A, n, w);
//print out some results.
printf(&quot;#eigenvalues \n&quot;); printf(&quot;w =&quot;);
printmat(n, 1, w, 1); printf(&quot;\n&quot;);
printf(&quot;#eigenvecs \n&quot;); printf(&quot;U =&quot;);
printmat(n, n, A, n); printf(&quot;\n&quot;);
printf(&quot;#Check Matlab/Octave by:\n&quot;);
printf(&quot;eig(A)\n&quot;);
printf(&quot;U&#039;*A*U\n&quot;);
delete[]w;
delete[]A;
}


# Page. 65

![Page Image](https://bcdn.docswell.com/page/LELZZZ93JR.jpg)

対称行列の対角化dsyevの例
• 先ほどのリストを&#039;&#039;eigenvalue̲demo.cpp&#039;&#039;などと保存する。
•g++
dsyev_demo.cpp -o dsyev_demo -llapacke -lblas -llapack
でコンパイルができる。何もメッセージが出ないなら, コンパイルは成功である。
• 実行は以下のようになっていればよい。同様にOctaveやMatlabにこの結果をそのままコピー&amp;ペーストす
れば答えをチェックできるようにしてある。
$ ./dsyev_demo
A =[ [ 1.00e+00, 2.00e+00, 3.00e+00]; [ 2.00e+00, 5.00e+00, 4.00e+00]; [ 3.00e+00,
4.00e+00, 6.00e+00] ]
#eigenvalues
w =[ [ -4.10e-01]; [ 1.58e+00]; [ 1.08e+01] ]
#eigenvecs
U =[ [ -9.14e-01, 2.16e-01, 3.42e-01]; [ 4.01e-02, -7.93e-01, 6.08e-01]; [ 4.03e-01,
5.70e-01, 7.16e-01] ]
#Check Matlab/Octave by:
eig(A)
U&#039;*A*U


# Page. 66

![Page Image](https://bcdn.docswell.com/page/4JMVVVZMJW.jpg)

はじめての行列-行列積高速化
14:12


# Page. 67

![Page Image](https://bcdn.docswell.com/page/PJR2226LE9.jpg)

行列-行列積には高速化が必須
ナイーブに作ると30-40倍くらい遅くなることがある̲
• 2000x2000の行列積AB＝Cを教科書どおりに計算するプログ
ラムを作って
• 0.4GFlops
(AB)ij =
∑
k
Aik Bkj
•最適化されたBLASを用いた場合
$ octave
... 途中略...
octave:1&gt; n=4000; A=rand(n); B=rand(n);
octave:2&gt; tic(); C=A*B; t=toc();
octave:3&gt; GFLOPS=2*n^3/t*1e-9
GFLOPS =84.1GFlops
マシン：MacBookPro (2017) i5-7360U 2.3-3.6GHz 2 cores
理論性能：73-115GFlops


# Page. 68

![Page Image](https://bcdn.docswell.com/page/PEXDDDD67X.jpg)

歴史:高速なBLAS, LAPACKの実装について
• Reference BLAS/LAPACKはある意味仕様書そのままなので、非常に低速である。
メモリの階層構造などは非常に意識して書かれているが、CPUに最適化は、各々がや
ることになる。
• 2000年までは、だいたいSUN/IBM/DEC/Intel/Fujitsu/Hitachi/NECなどCPU、
OS,システムごとにベンダーの実装があり、高価で販売されていた、またはマシンを買
うとついてきたりした。
• ATLAS:R. Clint Whaley氏による, オートチューニング機構で高速化したBLAS。そ
れまでの2001年より多くのコンピュータのBLAS環境を劇的に改善した, パイオニア
的存在。ハンドチューニングしたBLASよりは数%から数10%低速程度(オープンソー
ス)
• GotoBLAS/GotoBLAS2 : 後藤和茂氏が、アセンブラで様々なCPUに対応した
BLASのソースコードを公開。マシンの性能の限界近くまで性能を追求(非オープンソー
ス、最終バージョンはオープンソースとなった)。
2000年ころから高速なBLAS/LAPACKの環境が良くなってきた


# Page. 69

![Page Image](https://bcdn.docswell.com/page/3EKXXXXG7D.jpg)

現状: 高速なBLAS, LAPACKの実装について
• OpenBLAS: Zhang Xianyi氏がGotoBLAS2の開発を引き継いだ。開発はアクティブ
でSandyBridge以降のプロセッサ, OSにも対応している。ARM各種、AMD、Power,
ICT Loongson-3A, 3Bにも対応。オープンソース https://www.openblas.net/
• Intel Math Kernel Library: Intelが開発している加速されたBLASおよびLAPACK。
x86系では最速と思われる。FFTなどもはいっている。https://software.intel.com/
en-us/mkl
• GPU向けBLAS, LAPACK
•b
oat16はOpenBLAS, cuBLASが対応 !! 標準化されてない !!
• MAGMAプロジェクトはCUDA, OpenCLなどGPUやアクセラレータ向けBLAS,
LAPACKを開発している。
fl
• https://icl.cs.utk.edu/magma/


# Page. 70

![Page Image](https://bcdn.docswell.com/page/L7355555E5.jpg)

現在のコンピュータ


# Page. 71

![Page Image](https://bcdn.docswell.com/page/87DDDDDY7G.jpg)

Top500
速いコンピュータのリスト
• 1位はFrontier@US 1.2 Exa
Flops = 一秒で10^18 回演算で
きる 史上初Exa越え;2022/5
• 2位は富岳@JP (2021/11まで1
位) 440 PFlops
• 3位はLUMI@FI
• 4位はLeonardo@IT
• 5位はSummit＠US
• 神威・太湖之光@CNは7位
(2017/11まで1位)
入れ替わり激しい


# Page. 72

![Page Image](https://bcdn.docswell.com/page/VJPXXXX278.jpg)

binary64(倍精度)の計算スピードの比較
縦軸はFlops (一秒に何回計算できるか）


# Page. 73

![Page Image](https://bcdn.docswell.com/page/2EVLLLLXJQ.jpg)

CPU黒歴史
• 遅いCPUはすべて市場から撤退させられる
• i860, Itaniumnなど
• 高速なCPUは多少使いにくくても人間が頑張る
• NVIDIAのGPUなど
• 理不尽に市場から撤退させられることもある
• 政治的(V30、PEZYなど)、商業的、技術的問題


# Page. 74

![Page Image](https://bcdn.docswell.com/page/57GXXXXREL.jpg)

ボトルネック概念図
wikipediaより


# Page. 75

![Page Image](https://bcdn.docswell.com/page/4EQ8888YJP.jpg)

プログラム全体の処理スピードを決める箇所
=ボトルネック


# Page. 76

![Page Image](https://bcdn.docswell.com/page/KJ42222ZE1.jpg)

主な２つの
コンピュータのボトルネック
• 計算能力が高い/低い CPUの速度が速い/遅い
• 計算バンド幅
• メモリの転送能力が高い/低い
• メモリバンド幅 (フォン・ノイマン型ボトルネック)
•
他にも
•
HDD/SSDの読み書き速度、SATA転送速度、レイテンシ(遅れ)=1bit欲しいと命令してからバスにの
るまでの時間などなどなど…あらゆるところに存在する


# Page. 77

![Page Image](https://bcdn.docswell.com/page/LE1MMMMD7G.jpg)

2大コンピュータのボトルネック
と高速化戦略
• やりたいことの特性を見極める
• 計算バンド幅 &lt; メモリバンド幅
• 計算能力が低く、メモリ転送が速い
• 計算結果をなるべくメモリに残す
• メモリバンド幅 &lt; 計算バンド幅
• 計算能力が高く、メモリ転送は遅い
• 少量のデータをなるべく使い回す


# Page. 78

![Page Image](https://bcdn.docswell.com/page/GEW33338E2.jpg)

結局行列-行列積しか
高速化できない...
• GEMM（行列-行列積）の高速化のみが主要な焦点。
• 行列-行列積はデータが使い回し＋演算量が多いので、高速化できる。
• 近い将来、メモリの大幅な高速化は困難。メモリは充放電器なので遅い。さらに光速
度も遅い。
• メモリ速度がボトルネックになるならメモリが高速なマシンを買うしかない。
• クロック速度の向上は期待できず、一方で演算器の微細化には可能性
• 計算機はまだ高速化する。さらにgemmに有利
• 全てのプログラムはGEMMを使用するように書き直すべし。
• メモリの転送は最小限に抑えること。むしろ計算の無駄を許容


# Page. 79

![Page Image](https://bcdn.docswell.com/page/47ZVVVV9E3.jpg)

なぜ行列積か
• A, B, Cは n x n の行列として、積を計算する
•C←A*B+
C
3回の浮動小数点演算
2n
•
• A * B : n3回積 ,n2(n-1)回和
• (A * B ) + C : n2回和
2回のデータの読み書き
4n
•
• A, B, C：3n2読み
• ( A * B ) + C : n2書き
• n→ でデータ読み書きより演算がボトルネックとなる。
2 / (2n3) * 8 -&gt; 16/n
4n
•


# Page. 80

![Page Image](https://bcdn.docswell.com/page/YJ65555D7V.jpg)

基本はblock化
SIMD+自明なマルチコア
https://malithjayaweera.com/2020/07/blocked-matrix-multiplication/
B. Kargstrom et al., ACM Trans. Math. Soft., 24(3):268‒302, 1998.
https://dl.acm.org/doi/pdf/10.1145/292395.292412
K. Goto et al., ACM Trans. Math. Soft. 34(3):1‒25, 2008
fl
https://www.cs.utexas.edu/~ ame/pubs/GotoTOMS̲revision.pdf


# Page. 81

![Page Image](https://bcdn.docswell.com/page/GJ5YYYY8J4.jpg)

ChatGPT4先生に聞いてみた
• ブロック化が基本
• 続けて、ブロック化はキャッシュ利用
の効率化を図るためのものであり、
キャッシュミスを減らすことが期待で
きます。ただし、これは一例であり、実
際の最適化はハードウェア、特にCPU
アーキテクチャの詳細に依存します。ま
た、実際のパフォーマンスを向上させる
ためには、並列化（マルチスレッディン
グ）、SIMD命令の使用、適切なメモリ
アライメントなど、さらなる最適化手
法を検討する必要があります。
と、ちゃんと教えてくれた
※こういうプログラムネタはすぐ検証でき
るからChatGPTでも信頼できる(!?)


# Page. 82

![Page Image](https://bcdn.docswell.com/page/9E2GGGGVER.jpg)

Block化は最も重要だが...
• single core, single Blockのみ化をやってもあまり高速化しないように見える
• 初心者にとって鬼門
• SIMD化もメモリアクセスを高速にするために重要。
• Kargstromの時代にはSIMD, マルチコアも無かった。
• パフォーマンスチューニングは、CPUやメモリのアーキテクチャを理解する必
要がある。
• ボトルネックの構造が分かりにくい。
• CPUのカウンタを使うのが面倒、専用ツールが必要か？


# Page. 83

![Page Image](https://bcdn.docswell.com/page/D7YVVVVQ7M.jpg)

高速化という獣道への入り口
• 40行で結構高速なgemmを書くチュートリアル
• https://en.algorithmica.org/hpc/algorithms/matmul/
• 100行でOpenBLASなみのコードを書くチュートリアル
• https://cs.stanford.edu/people/shadjis/blas.html
• CUDAのgemmを書くチュートリアル
• https://siboehm.com/articles/22/CUDA-MMM
• OpenCLでgemmを書くチュートリアル
• https://cnugteren.github.io/tutorial/pages/page1.html
14:24


# Page. 84

![Page Image](https://bcdn.docswell.com/page/VENMMMM2J8.jpg)

参考図書
• BLAS, LAPACKチュートリアル パート1 (基礎編) BLAS, LAPACKチュートリアル
パート2 (GPU編)
• http://nakatamaho.riken.jp/blas̲lapack̲tutorial̲part1.pdf
• http://nakatamaho.riken.jp/blas̲lapack̲tutorial̲part2.pdf
• LAPACK/BLAS入門 幸谷智紀 (https://www.morikita.co.jp/books/book/
2226)
• Matrix Computations, Gene H. Golub and Charles F. Van Loan
•
http://web.mit.edu/ehliu/Public/sclark/Golub%20G.H.,%20Van%20Loan%20C.F.-%20Matrix%20Computations.pdf
• Accuracy and Stability of Numerical Algorithms, Nicholas J. Higham
• LAPACK Working NOTE : 実装上の詳細ノートたちがある
• http://www.netlib.org/lapack/lawns/index.html
• 数値計算の常識, 伊理 正夫, 藤野 和建


