理論的計算量の見積もりに関して - その3

2. 行列積
計算量はいうまでもなく O(n^3) だが、性能差が非常に大きい。

N: 3重ループ
B: ブロッキング(block=64)
G: GotoBLAS2

まずは n=1000 と n=2000 とした nxn 正方行列の積から。
n=1000
N: 6.07s, B: 1.99s G: 0.03s
n=2000
N: 60.19s, B: 16.78s, G: 1.38s

次に n=2000 でマルチスレッド計算[使用したプロセッサ数]
n=2000
G[1]: 1.38s, G[2]: 0.69s, G[4] 0.35s, G[8] 0.20s

このように、n=2000時で最も単純なものと高速化されたライブラリでの性能差は、60.19 / 0.20 ≒ 300.95 倍にも及ぶ。

このように計算量は非常に重要ではあるが、性能は単に計算量で決まるわけでもないことを念頭に入れてほしいと願っている。理論的に計算量を見積もるプロセスを研究している方は多いが、実験的にも行おうとしている方は非常に少なく感じる。