gnuplotでeps

gnuplot> set terminal postscript eps
gnuplot> set output 'random.eps'
gnuplot> plot "random.mtx" using 1:2

これでOK。
しかし、Windows環境ならMetafile to EPS Converter使ったほうが楽で綺麗なときも。

今後の作業メモ

・StreamAPU 改善
解析的な手法を導入
　どのようなパラメータなら提案手法が用いることができるのか解析する
　並列数数、それぞれのコアの速度、性能、通信回数など
英語化

・ドキュメント化
サーバ管理関係（リストアップする）
　U君と連携して考えておく
StreamAPUのプログラムなどのSVNへの追加、使い方のPP化

修士論文

無事修士論文とSACSISを提出することができた。
自分なりにちゃんと取り組んだつもりだったが、
結果的に時間が足りずに適当になってしまった部分も多く、
スケジューリングが今後の課題だと思う。
特に修士論文やSACSISのはじめのほうの稿は文章を推敲する余裕がなく、
かなり酷い状態で添削していただかなくてはならなかったのが反省点だ。
せめてあと一週間でも早く全ての実験・実装が終わり、推敲時間を取れたなら、
最終日の昼レベルの原稿なら自力で持っていけたと思う。

研究の今後の課題として、VWAPのもう少しマシな実装とSSTに代わるアプリの調査がある。
今回のVWAPはCPUに絶対負けないために全てTRADEのときを想定したが、
QUOTEも混ざった場合にどのような挙動になるのかは一度試してみたい。

また、SSTはどうしても提案手法の優位性の検証には使えそうもないので、
新しくCPUとGPUが混在した処理を探して高速化してみたい。
昔痛い目に合ったXMLなんかが案外いけるかもしれないと考えている。
前回は全てGPUでやる前提だったのでダメだったが、
理想的なAPUを想定して適宜2つのデバイス間で適切に処理を割り振れば何とかなるかもしれない。

gnuplot

たびたび書いているような気がするが、gnuplotの使い方。


gnuplot> set term png nocrop medium size 450,160
Terminal type set to 'png'
Options are 'nocrop medium size 450,160 '
gnuplot> set output 'wiki.png'
gnuplot> plot "wiki-sort.mtx" using 1:2

これでファイルの1,2番目の要素をx,yとして指定したサイズのグラフをpngで吐ける。

VWAPの実験

修論の実験でVWAPの再試が必要だったのだが、、Teslaで書き直したものと、
OpenMPでCPUに最適化したもののテストが終わり、ただいま本実験のデータを取っている。

OpenMPは非常に簡単にマルチスレッドプログラムが書けるので使うのは楽だったっが、
TSUBAMEでのスレッド数の初期設定が1になっているのに気づかず、ちょっと時間を浪費した。
それ以外はすんなり動き、4スレッドくらいまではリニアスケールしたのを確認したのでひと安心。
ハイパースレッディングはあまり意味がないようで、12スレッドの結果が24スレッドに勝つ場合も。

行列生成スクリプト

行列生成スクリプトだが、Perlのものは遅すぎるため結局C++で書きなおした。
STLのstringでは文字列の分割がサポートされていないようなので、
ファイルの読み込みはCのfgetsでcharの配列に読んでstrtokしてからSTLのqueueで保持し、
書き込みはofstreamで行うという何ともちぐはぐで変な実装になってしまった。

Perlでは27+47行のスクリプトが、C+では39+101行のコードになり、倍ほどの差がある。
全く同じ処理のフローなのだが、いかにPerlでは略記が可能かがよくわかる。
その分処理は遅いので致し方ないが。

グラフサイズの概算

疎行列をCSRで持つとすると、AAとJCが非ゼロ要素数nz個分、
IAとV1,V2が行列の一辺の長さn個分の格納領域が必要となる。
単精度の場合、全ての配列は長さ*4Byteになるので、8nz+12n Byteになる。

nとnzはエッジファクタefを用いるとnz=n*efとなる。
だいたいefは16程度で生成するらしいので、これを適用すると140n Byte！！
倍精度だと、AAとV1,V2が2倍に増えるので、12nz+20n Byte = 212n Byteだ。


今回ターゲットとするメモリ必要量は、3～6GBには収まらず128～256GBよりは小さい領域。
よって、nは2^26～2^30程度の領域を相手にすればよいようだ。メモリ量は8.75GBから140GB程度。

n=2^26(scale s=26)だと、ベクトル1本が256MBで、どうにか扱えそうな感じだ。
n=2^30(scale s=30)だと4GBになるので、現状のFermiでも扱うのは不可能になる。
s=26のときAAとJCはそれぞれ16*2^26で、4GBになる。s=30では64GB。
s=26だとFermiのC2070なら全てメモリに乗ってしまうのであまり面白くなさそう。
ただし、現状のハードと実装ではBlock=2^15, Thread=2^10で合計2^25がベクトル長の最大になる。
ベクトルの分割を実装するのはちょっと面倒だが、s=25では行列分割の必要性がなく何かぱっとしない。

Pregelなどの評価ではef=128くらいらしいので、この場合も考えておく。
これを適用すると、メモリ量は8nz+12n = 1036n Byteで、scaleは23～28で、メモリ量は8.09GB～259GB。
ベクトルの容量はscaleでのみ決まるのでs=23なら8MB、s=26は変わらず256MB、s=28で1GB。
AAやJCはefの影響も受け、s=23で1GB、s=26で8GB、s=28だと32GBになる。
これくらい大きいと行列の分割の必要性、正当性も大いに主張できるし、ちょうどいいとは思う。

viの色が見づらい

TSUBAMEにPUTTYで繋いでvimでC/C++/CUDAのコードを書くと、
コメントなどの色の設定がよくないため、コードが非常に見づらい。
こういうとき、以下のコマンドをvi上で叩くとよい。

:highlight Comment ctermfg=Blue

コメント以外の色などの一覧も以下のコマンドで見れる。

:highlight

PageRank

G君とN君にPageRankの計算部分を聞き、ようやくうまく収束するものができた。
GPUへの最適化はU君の助けも借り、そこそこ動作するものが完成した。

PageRankの計算では、全ての要素は列に対して正規化されており、
各列の要素は全て同じ数値で和が1でなくてはならない。
もし、全ての値が0の列がある場合、その列の対角要素を1にする。

初期ベクトルも同様に正規化したものを使い、収束するまで行列ベクトル積を行う。

n=65536でもうまく計算できているので、次は収束判定と分割した行列への対応だ。
これさえできれば後は実験結果を取るのみだ。
収束判定部分は、ブロックを跨いだ同期で躓いたが正しいやり方はわかっているので大丈夫だ。

SpMVの実装

ランダムグラフだが、正規化されたcsr（非圧縮）の行列生成スクリプトをPerlで構築した。
簡単なコードだが、文字列の打ち間違いという痛恨のミスでなかなか時間を取られてしまった。
行数とエッジファクタが指定できるようにしたので、今後の実験に役立ちそうだ。

正規化の方法などはG君が色々アドバイスをくれたので、お陰でうまく生成できた。
現在n=8192、エッジファクタが16程度だと7分程度で生成できている。
n=65536、エッジファクタが19程度では22分かかってしまう。（共にPhenom 2.5GHzでの結果）

Perlのprintでいちいち標準出力経由でファイル書き込みしているため非常に遅いが、
実験で使いそうな範囲なら問題なく出力できそうなので高速化は考えないでおく。

CUDA, OpenCLそれぞれのSpMVを生成した行列を使ってテストしてみたが、
CUDAはOpenCLよりもやはり圧倒的に速い。OpenCLはメモリがボトルネックになっているようだ。
CUDAで実行すると、n=8192では5.11倍、n=65536だと37.00倍もの高速化がなされている。
アルゴリズムはどちらにも大して最適化されていないのもなのに、どうしてここまで差がつくのだろうか。
不思議だ。

PageRankの再帰回数

10数回程度の反復数で十分そう。10回程度で収束状態の7,8割の精度が達成されるらしい。

以下、参照元URLと原文の一部抜粋。

http://www.kentmiyajima.com/document/pagerank.pdf

4.4.2 収束判定基準の変更による効率化
べき乗法の収束判定基準を見直すことで PageRank 値の計算を高速化する手法を紹介
する。べき乗法による PageRank ベクトルの計算では、k 回目の反復時点の PageRank
ベクトル tr(k) と k + 1 回目の反復時点の PageRank ベクトル tr(k+1) の成分の差
の合計||tr(k+1) − tr(k)||1 が収束判定基準 ϵ を下回れば、PageRank ベクトルが収束した
（定常状態に達した）と判定していた。
Haveliwala は、PageRank ベクトルの計算において、必ずしも真の PageRank 値を
求める必要がないことに着目した [26]。PageRank 値はその相対的な大きさによって
Web ページの順位付けを行うための値であるため、正確な順位付けさえ可能であれば、
PageRank 値の近似値を算出できた時点で収束したと判定すればよいという考えを提示した。
Haveliwala は、収束判定基準の見直しによる PageRank 値の計算の高速化の可能性が
あることを実験により示している [26]。まず、べき乗法の反復を 5 回・10 回・25 回・50
回・100 回行って PageRank 値を算出し、それらの用いて Web ページの順位付けを行っ
ている。次に、反復を 100 回行って求めた PageRank 値による順位付けと、反復を 5 回・
10 回・25 回・50 回行って求めた PageRank 値の順位付けとの類似度*67を求めている。
クエリによる差はあるが、10 回程度の反復でも 7～8 割程度の正確な順位付けができるこ
とがグラフ [26] から読み取れる。Haveliwala はこの結果を受けて、収束判定基準の見直
しにより、PageRank 値計算にかかる時間を短縮することができる可能性があると述べている。

PageRankの進捗

現在PageRankで用いるSpMVのコードをOpenCLからCUDAへ移植している。
コンパイルエラーの原因などもわかり、一応動作してはいるが計算結果がまだ間違っている。
計算のアルゴリズム自体は非常に単純なものを使っているので、一つ一つ追っていけばどうにかなりそう。