Orz日記 by Akio Morita

_ [SAD]LAPACKまわり

GESVDによる SingularValues1[]の試験実装完成

• GESDDへの置き換えによる高速化
• Tolerance/Inverseサポート
• 例外処理

_ [SAD]LinearSolve

SVDによる擬似逆行列で線形問題を解いているので、SVDを使った 最小二乗法ソルバー GELSS/GELSDに相当する

_ [SAD]LAPACK TODO

• GEEVをバランス化前処理付きのGEEVXへ置き換える
• LinearSolveComplex2のZGELSD/ZGELSSによる実装
  • LinearSolveRealによるLinearSolveComplex2実装とのベンチマークが必要
• allocate error handlerの実装
• GELSDからGELSSへのフォールバック動作の実装？
• SingularValues1のフォールバック動作の修正
  • 破壊的に上書きされる行列の再ロード？

_ [SAD]LinearSolveComplex実装

実装してみたものの性能が微妙 orz

比較対象は、LinearSolveRealで実装しているLinearSolveComplex1 (MxN 複素行列上の代数を、等価な 2Mx2N 実行列上で計算する) な訳ですが、ある程度の大きさの正方行列の逆行列を計算させた場合

• Netlibの Reference BLAS/LAPACKでは、LinearSolveComplex1よりLinearSolveComplexが早い
• GotoBLASだと、LinearSolveComplex1がLinearSolveComplexより早い

(Core2 Duo T7200(2GHz))

演算精度は、小行列で試した範囲では、LinearSolveComplexの方が若干良いようです。

原因としては

• 複素BLAS/LAPACKの最適化が実数BLAS/LAPACKほど進んでいない
• 複素行列積などでメモリーアクセス・演算パターンが複雑化することによりキャッシュヒット率やパイプライン稼働率が悪化している

辺りが疑わしいです

_ [SAD]Math/LAPACK extension

当初予定分(LinearSolve, SingularValues, Eigensystem)は完成した。

SAD core側にも作業の余地はあるのだが、BLAS & LAPACKに依存することに なるので、インストール作業の手数が増えると質問続出になりそうなので、 ボトルネックになる事案が判明するまで放置する予定。

実用上改善の余地が有りそうな所としては、行列の Dot積(内部的にInner[]を 呼び出している？)辺りと専用の関数経由でGEMMを使わせると速くなるのでは 無いかと妄想中。(データ解析等で大きめの行列の行列積が出てくる)

SpaceCharge/Scheff moduleの経験からは有為な改善がありそうだが.... コストに見合うだけのボトルネックになっているか問題である。

_ [SAD][Fortran][数学]BLAS & LAPACKライブラリの選び方

• LAPACK-3.2.2 & BLAS-1.0
  • Netlib.orgで配布されている参照実装
  • ライセンス的には一番緩い？(原著者への正しいクレジットの表記のみ)
  • 最適化BLAS & LAPACKがおかしいときの比較用に持っておいて損はない
  • 3.2.2でも実用上問題になる Errtaが有るので、Errataリストには目を通すこと
• ATLAS
  • 3条項 BSDライセンス(宣伝条項無し)
  • 比較的に広い環境でそれなりの性能が出るソース付き最適化BLAS & LAPACK実装
  • コンパイル時に行う自動チューニングの時間が長いのが玉に瑕
  • 安定版の3.8.3と開発版の3.9.x系列がある
    • 一部環境では、3.8.3の性能に難があるため 3.9.xがおすすめ(Opteronでの QR分解とか)
• GotoBLAS-2.1.3
  • ソース付きだがライセンスは厳しい(再配布は出来ません)
  • Texas Advanced Computing Center製 後藤BLASの最終版らしい(中の人がMicrosoftに移籍)
  • 埋め込まれるLAPACKは、少し古めのLAPACK-3.1.1なので Errataに要注意
    • LAPACK-3.2.xでは修正済みの結構致命的なErrataがある
    • Working areaの LQUERY系は運用でごまかせるが、収束性や停止性にまつわる致命的 Errataあり
  • ソース付きの最適化BLAS & LAPACKとしては私の知る範囲では最速、測定条件によっては商業ライブラリを上回る性能を叩き出す
• ACML-4.0.0
  • AMDが自社CPU向けに用意してる最適化BLAS & LAPACKを含む数学ライブラリ
  • 開発者は、無料でダウンロード可能
  • Windows/Linux向けのバイナリ提供のみ
  • Linux gfortran環境向けバイナリなら、ELFかつLinuxと ABI互換な gfortran環境で利用可能と思われる
• IMKL-10.3
  • Intelが自社CPU向けに用意してる最適化BLAS & LAPACKを含む数学ライブラリ
  • 商品なので購入してください(単品もしくはC/Fortranコンパイラ商品に付属)
  • Windows/Linux/MacOSX向けのバイナリ提供のみ
    • 基本的には Intelコンパイラと組み合わせ
    • gfortranも可能だが、4.4.0以降はサポートしない(libgfortran APIが変更されてる)
• NAG Fortran Library
  • Numerical Algorithms Groupの最適化BLAS & LAPACKを含む数学ライブラリ
  • 商品なので購入してください
  • Windows/Linux/MacOSX向けのバイナリ提供のみ
  • BLAS & LAPACKにも nagの中の人のクレジットが入るくらいなので品質と性能は信用できる
• NVIDIA CUDA BLAS
  • CUDA Toolkitに含まれる Tesla/Fermi GPU上で動く並列BLAS
  • 行列サイズがある程度大きければ、CPUは追いつけない(演算・メモリ帯域的に)
  • 今時のMany coreマシンで、複数ユーザーが同時にジョブを流す場合は問題有

ほかにも、Fortranコンパイラベンダ謹製の最適化BLAS & LAPACKがあるようです

手元の Opteron 2376で測定した固有値分解(*GEEVX)やSVD(*GESDD)の single core性能だと

GotoBLAS-2.1.3 > ACML-4.0.0 > ATLAS-3.9.11 >> ATLAS-3.8.3 >> LAPACK-3.2.2

でした。

ATLASに関しては、3.9.3辺り QR分解まわりの改良が効いてるのか安定版と 大きな性能差が出ました。

トップ３ライブラリの差は10%前後ですが、GotoBLASの速さが目立ちました。 (ACML-4.0.0と ATLAS-3.9.11は、結構接戦でした)

まとめると...

• LAPACK-3.1.1の Errataを考えると ACML-4.0.0か ATLAS-3.9.xを選ぶのが better
• Errataを避けられる用途に限定する場合、GotoBLAS最速

_ [FreeBSD][数学][Fortran]ATLAS-3.9.32ビルド成功

FreeBSDの math/atlas-develが 3.9.11で止まってたので、 3.9.32の野良portsを作ったがうまく動かないので深追いしてたが、やっと成功。

コンパイルテストに長い時間がかかって苦労したけど、原因は至って簡単orz

tune/blas/gemvとtune/blas/gerで止まる問題は、生成された Makefileが 依存関係の解決にGNU makeで無いと問題が出る部分が有るにも関わらず*.c系から 吐き出す　shell command lineで make utilityの名前がmakeで 決め打ちになっているためだった。 (つまり、GNU makeでビルドしても途中で BSD makeが呼び出されて詰まる) この手の問題は、Linux上や darwin系では起こらない orz

細かなものでは、atlas_[sdcz]r[12].hとかatlas_[sdcz]mv[nt].hの 扱いに問題が有って BSD makeだとルール最後の mvコマンドの失敗で ルールが失敗扱いになってビルドが停止する問題も有りました。

これらは、makes/Make.mvtuneとmakes/Make.r1tuneにパッチを当てて修正

Kernel Tuningがらみだと、Opteron 2376で L1 Cacheが 1kBと検知される問題 が有ったのですが、tune/sysinfo/GetSysSum.cでGetL1CacheSize()に渡す L1 Cache Size探索の上限が 64kBしか無いので、L1 Cache Size Edgeでは無く 命令バッファか何か他のEdgeを検出するためで、探索上限を 256kBとかにすると 正しく 64kBのL1 Cacheを検知しました。 (ports-CURRENTのpatch-tune+sysinfo+L1CacheSize.cの修正だけでは、 後一歩足りない罠)

_ [雑記]T-ZONE DIY SHOP廃業

正確には、親会社がT-ZONE部門を清算して、サードウェーブへまるごと転売の模様。

Xeon/Opteronや RAIDカードなどのマニアックな品の扱いが残るかが問題だ。