2015年6月22日月曜日

PAPIでのFLOPSの計算の方法

PAPI(Performance API)というものがあります。キャッシュヒット率、ミス率、FLOPS、命令の呼び出し回数などを計測できるAPIで、CPUの機能を使います。命令の呼び出し回数を計測できるので、今回は浮動小数点演算の呼び出し回数を計測してFLOPSを計測するのに使おうと思います

PAPIには高レベルAPIと低レベルAPIがあります。高レベルAPIにはまさにFLOPSを計算するためのPAPI_flops関数があります。これを計測したい処理の前後に挟むだけでFLOPSを取得できます。ただし、複数回計測する場合は値がリセットされないので入力時に-1を入れておく必要があります。

普段使う分には高レベルAPIを使えばいいですが高レベルAPIは並列化に対応していないのでopenmpなどで並列化したときは低レベルAPIを使う必要があります。低レベルAPIを使う場合は時間と実行命令数からFLOPSを計算する過程を自分で実装する必要があります。

参考

2015年6月21日日曜日

シュトラッセンのアルゴリズムの計算量

シュトラッセンのアルゴリズムという行列積を求めるアルゴリズムがあります。行列積を求めるときに部分行列の積を求めることによって演算回数が少なくて済みます。通常の行列積の演算は$O(n^3)$ですが、シュトラッセンのアルゴリズムを使うと$O(n^{\log_2 7})$で行えます。巷には日本語だとシュトラッセンのアルゴリズムの説明はちらほらありますが計算量について言及している説明はほとんどないのでしてみようと思います。

サイズNの正方行列の掛け算を考える。因みにシュトラッセンのアルゴリズムを使うときは正方行列でなかったら端に0だけの行or列を追加して無理やり正方行列にする必要がある。Nが2のべき乗でない場合は漸化式が途中で計算できなくなるので途中で諦めるか最初から諦める必要があると思う。以下Nは2のべき乗ということにする。サイズNの正方行列のシュトラッセンのアルゴリズムによる計算時間を$T(N)$と書く。シュトラッセンのアルゴリズムでは半分のサイズの行列積を7回求める。行列和の計算量は$O(N^2)$なので $$ T(N) = 7 T(N/2) + O(N^2) $$ となる。マスターの定理を使うと$O(N^{\log_2 7})$となる(らしい)。

マスターの定理はよくわからないのでマスターの定理を使わないで$T(N) = O(N^{\log_2 7})$を示す。 $$2^n := N$$ として $$U(n) := T(N)$$ と書くと $$U(n) = 7 U(n-1) + O(2^{2n})$$ となる。漸化式を解く感じで整理すると \begin{align*} &\frac{U(n)}{2^{2n}} + \frac{4}{3} c \leq \frac{7}{4} \left(\frac{U(n-1)}{2^{2n-2}} + \frac{4}{3}c\right)\\ &\leq \left(\frac{7}{4}\right) ^ n \left( U (0) + \frac{4}{3}c\right)\\ &\leq \left(\frac{7}{4}\right) ^ n c' (c'はなんかしらの定数) \end{align*} となるので $$ \frac{T(N)}{N^2} \leq c'\left(\frac{7}{4}\right) ^ {\log_2 N} $$ \begin{align*} T(N) &\leq c' N^2 \left(\frac{7}{4}\right) ^ {\log_2 N} \\ &= c'7 ^ {\log_2 N}\\ &= c'N ^ {\log_2 7} \end{align*} となり $$ T(N) = O(N^{\log_2 7}) $$ が示せた。

計算量解析をしてみたけれど数値計算的にはシュトラッセンのアルゴリズムはほとんど使われない。というのも

  • オーダは小さいけど定数が大きいから普通はシュトラッセンのアルゴリズムの方が時間がかかる
  • 疎行列だともっといい方法がある
  • 部分行列の計算のところでメモリを一杯食う
  • 足し引きを一杯行うから浮動小数点演算の誤差が一杯乗る
だからだそうだ。

参考