2010年1月30日土曜日

SNL の論文チェック

今日は、SNL の論文関係の論文を3本チェック。

1.A distributed SDP approach for large-scale noisy anchor-free graph realization with applications to molecular, SIAM Journal on Scientific Computing archive, 30(3), 2008.

これは、この前に読んだ An SDP-based divide-and-conquer algorithm for large scale noisy anchor-free graph realization とほぼ同じ。たぶん、1のものはこれをベースにしているはず。もし、実装するのであれば、両方読むと良い。

2. Learning a Kernel Matrix for Nonlinear Dimensionality Reduction, ACM International Conference Proceeding Series , 69

3. Nonlinear Dimensionality Reduction by Semidefinite Programming and Kernel Matrix Factorization, Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics

2と3は First author が同じ人で、Kernel trick のときにどれだけ少ない rank でできるか、を SDP で計算する、というもの。
2 の中にある locally isometric の考え方は、今後に応用できそうだ。

あとは、昨日まで読んでいた本のメモ。
読んでいたのは、 「たんぱく質のフォールディング」で、SNL の応用として読んでみたが、完璧にたんぱく質の話で SNL とは距離がある感じだ。
ただ、αへリックスやβストライド、など、特徴的な構造が何回も現れる、というのは面白かった。

明日は、グラフ理論の論文読み。

今日の作業内容: 論文読み 5h
今日のBGM: Xenosaga Episode III OST [1-2]
明日の予測作業時間: 5h

2010年1月29日金曜日

Linux 修理と Vine Linux 5.0

今日は、昨日不具合を起こして起動がうまくいかなくなった Linux 機の修理をした。
とりあえず、ふたを開けて、中を掃除したあと、電源を入れ直すがうまくいかず、メモリやグラフィックスカードも外して、確認したところ、CPUファンが回っていないことを発見。
どうやら、ちかくのケーブルが接触して CPU ファンが停止し、熱暴走に至っていたようだ。
ケーブル回しを修正したところ、今のところは無事に動いている。

修理と並行して、別の PC で Vine Linux 5.0 をvmplayer で確認。Vine と Ubuntu を比較すると、

Vine のいいところ
デスクトップが美しい(デスクトップ背景やフォントなど)
Linux ユーザがよく使うものが優先されて整備されている
初期のタスクバーアイコンが、「端末」「Firefox」「sylpheed」と利用頻度が高いものになっている

Ubuntu のいいところ
Windows ユーザがよく使うものが優先されてインストールされる
ユニティが動作する(Vine だとユニティがうまく動作していない)
Vine よりも、gcc などいろいろと新しい


Windows と併用しないのであれば、Windows と似た機能が豊富な Ubuntu が有利。
Windows と併用なら、Linux のアドバンテージを引き出しやすい Vine が有利。

基本的に Windows は、 Ubuntu のほとんどのことができる。(そうでなかったら、Windows にお金を出す必要がない。)
また、Ubuntu のほうが Windows よりも得意な分野は、Vine のほうが Ubuntu よりも作業に集中しやすい。

今日は、他に論文の原稿チェックをすすめた。
明日は、原稿チェックの反映と論文読みの続きになるはず。

今日の作業内容: Linux 修理+Vine 5h + 原稿チェック 2h
今日のBGM: MADLAX OST [1]
今日のランチ: 味庵 鶏肉唐揚げの黒酢ソース
明日の予測作業時間: 4h

2010年1月28日木曜日

打ち合わせと投稿と

今日は、午後から研究関係について打ち合わせ。いろいろと勉強になった。
CUDA はすぐに性能を引き出すのは難しいようなので、どう活用するかは長期戦になりそうだ。
ただ、現状で CUDA をやっている人は分野的に少ないので、ここで頑張るのも一興かと思う

あと、今日は論文をひとつ投稿。
かなり時間はかかったけど、それに見合うだけの内容だと考えている。
最近は論文投稿もオンラインシステムになってきており、今回のシステムは初めてで慣れていなかったけど、とりあえず「受領」のメールが来ていたので、投稿自体は行なわれているはずだ。

明日は、SNL の論文読みの続きを再開しよう。


今日の作業内容: 論文読み 1h + 打ち合わせ 2h + 投稿 1h
今日の BGM:なし
今日のランチ: らく 焼き魚定食
今日のディナー: 王将 焼き飯定食
明日の予測作業時間: 5h

2010年1月27日水曜日

SNLの論文を読む

今日は、とてもおめでたいことがあった(他の人に)。
自分も頑張ろうと思う。

昨日まで、コンピュータに張り付きすぎていたのを考えて、今日は論文読み。

An SDP-Based Divide-and-Conquer Algorithm for Large-Scale Noisy Anchor-Free Graph Realization, SIAM J. Sci. Comput., 31(6), 4351-4372, 2009.

アルゴリズムの基本はタイトルにもあるとおり、divide and conquer で、部分ごとに分解したのをどのように復元していくか、かまとめてあり、とても勉強になった。
いくつもいいアイデアが含まれているので、今後の参考になりそうだ。
ここで得られたアイデアを、明日もう少し練ってみよう。

あと、PLASMA がどのくらい速いかをチェック。sgemm での比較なので、LAPACK 重視の PLASMA には少し不利か?

N=2000 で
ATLAS 0.17 秒, CUBLAS 0.32 秒, GOTOBLAS 0.11 秒, PLASMA 0.33 秒
N=4096 で(NがCUBLASに有利にしてみた)
ATLAS 1.30 秒, CUBLAS 1.33 秒, GOTOBLAS 0.95 秒, PLASMA 2.94 秒
N=8192 で(CUBLAS はメモリオーバー)
ATLAS 9.73 秒, GOTOBLAS 7.6 秒, PLASMA 20.23 秒
N=30000 で
ATLAS 483.80 秒, GOTOBLAS 367.18秒, PLASMA (2時間で終了せず、打ち切った)

予想以上に PLASMA が遅い結果になっている。今のところは、BLAS は ATLAS/GotoBLAS のほうが性能が上である。

今日の作業内容: 論文読み 3h + 部屋の掃除 3h
今日のBGM: FF12 OST [1,2]
今日のランチ: つかさ カンパチ唐揚げ
明日の予測作業時間: 3h

2010年1月26日火曜日

PLASMA と Ubuntu on vmplayer と(つづき)

今日は、昨日に引き続いて PLASMA と Ubuntu。

VMplayer にインストールするときは、結局 easy install ではなく普通にインストールするほうが後々、楽だった。このときに、インストールが終わったあとのアップデートが終了したところで vmtools をインストールすると、共有フォルダなどが正常に動く。

Ubuntu は、Windows と似たようなところは整備されているが、そうでないところ (emacs など)はあまり整備されていないので、Linux でのプログラム開発にはさほど向いていないかもしれない。
常にアップデートされるので、セキュリティ面では安心だが、できることが Windows と同じなので Windows のほうが楽かもしれない。

ホームディレクトリに要らないフォルダが生成されてしまう問題は、~/.config/user-dirs.dirs で解決できた。この中で、フォルダ名を変更して、それに対応するフォルダを作成して、ログインしなおすと解決する。
たとえば、このファイルの中で
XDG_DESKTOP_DIR="$HOME/.Desktop"
としておいて、~/.Desktop を mkdir しておいて、ログインしなおせば、デスクトップのフォルダがホームディレクトリで目立たなくなる。

あと、これは重要なことだが、
Ubuntu 9.10 のext4 は不完全で、512MB 以上のデータが壊れることがある。
らしい。

あと、メール通知アプレットは複数があるが、自分としては「Mail Notification」がいちばん使いやすかった。

PLASMA については、testing_Xgemm 系の問題は解決。
これは、testing_Xgemm.c にバグがあって、alpha,beta を atol で整数変換していたために、小数点のある数字を入力すると正しい値になっていなかった。
ただ、testing_Xgesv の誤差が大きい問題は、まだ残ったまま。
今日だけで PLASMA を設定を変更しながら 10 回コンパイルしなおしたが、未解決。
(Xeon E5520 が2個の場合、1回のコンパイルで 18 分かかる。)

とりあえず、昨日、今日と PLASMA, Ubuntu を並行して行ったので、計算機関係はとりあえず置いておいて、明日は、SNL の論文をチェックしようと思う。

今日の作業内容: PLASMA,Ubuntu 6h
今日のBGM: FF7 OST [1-4]
今日のランチ: 角笛 さわらのソテー
明日の予測作業時間: 5h


追記
testing_Xgesv 系列は、出力される数値誤差の評価式が解かりにくかっただけで、計算自体は正しく行われていた。これで、大丈夫そうだ。

2010年1月25日月曜日

PLASMA と Ubuntu on vmplayer と

今日は、PLASMA のインストールにトライしてみたが、なぜかうまくいかない。
コンパイルなどは、setup.py を使うとすごくあっさりとできる。
このあたりは、SDPA のインストールについても参考になりそうだ

ただ、testing ディレクトリで、test_?gemm を実行すると、C = alpha*A*B + beta*C がなぜかいつも C = 0 になってしまう。PLASMA_sgemm, CORE_sgemm の両方で 0 になってしまう。
あと、test_sgemv も誤差が 1.0e-2 とか出てきてしまう。
明日、ひきつづいて調べてみよう

あと、今日は Ubuntu を vmplayer でインストールするとどうなるかを確認してみた。
vmplayer も 3.0 になると仮想マシンを作る機能はあるし、しかもユニティができるので、とても便利。Ubuntu 9.04 だと、easy install で vmtools も自動でインストールしてくれる。(その代わり、時刻やキーボードを自分で日本語に修正しないとダメ。)

しかし、ホームディレクトリに「デスクトップ」とか「公開」とかあって必要なかったので、rm で削除したら挙動がおかしくなった。しかたなく、仮想マシンごと一度削除しておいた。
あと、共有フォルダが作動していない。たぶん、vmtools が自動インストールされたあと、Ubuntu を 9.10 に update したので、それでインストールされた vmtools とずれているのかもしれない。


そうそう、今日教えてもらったが、CUDA には疎行列を扱う機能があるらしい。
密行列ほどのスピードはさすがに出ないとのことだが、これについては調べてみなければ

今日の作業内容: PLASMAとUbuntu 5h (並行作業)
今日のBGM: 小松未歩 BEST [1-2]
今日のランチ: シッダルータ チキンとマッシュルームとポテトのカレー
明日の予測作業時間: 6h

2010年1月22日金曜日

「はじめての CUDA プログラミング」とネットブック

今日は、「はじめての CUDA プログラミング」を読んでみた。
CUDA に関しては、現状では英語の情報がほとんどなので、こうして日本語でまとまった情報が手に入ると、とても便利だ。

CUDA の場合、記憶領域が「レジスタ」「ローカルメモリ」「シェアードメモリ」「グローバルメモリ」といくつかあって、記憶容量が小さいものほど高速に使用できるので、いかに小さい記憶領域で効率的に計算するかが肝心なようだ。

単純に配列の和なら、
for (int i=0; i < N; ++i) sum = sum + a[i];
でいいかと思っていたが、これだけでも GPU の性能をフルに発揮しようとすると、相当の工夫が必要ということが解かる。

今の時点で CUDA について勉強するのであれば、読んでおいて損はないと思う。

ただ、並列計算の分野では 2^n で離散化したりなどでプログラムを簡略化できるが、mathematical programming ではだいたい 2^n になることはないので、そのあたりでどのように性能を維持するかがポイントになりそうだ。sgemm でも N=4096 と N=4095 では2倍も速度が変わってしまうし。

とりあえず、ここで得た知識などを用いて、PLASMA/MAGMA を調べていくことにしよう。


あと、それと並行して、ネットブックがどれだけ使えるのかを試してみた。
ネットブックは SONY Type W で Atom CPU N280 @ 1.66GHz, Memory 2GB, Windows 7 Home Premium である。
Windows 7 は初めて使ったが、Office 2007 をインストールした時点で HDD は 20GB 程度になる。
Windows が起動しただけでメモリは 780MB 程度使用しており、Internet Explorer を起動すると 900MB を突破するので、メモリが 1GB しかない場合、Windows 7 Home Premium はきついかもしれない。
また、Word は起動時にかなりもたつくが、Word/Excel/PPT と3つ開いても1分ぐらいすると、それなりに動く。ただし、日本語入力はかなりのもたつきがある。
VMware で Ubuntu などを動かすのは、きつそうだ。


ただ、世の中の多くの人はインターネットエクスプローラを使っているだけの時間がかなりの割合を占めるので、そういった用途に絞っての2台目という点では、使い道が大きい。新しいページをひらくのに少しもたつくが、それほど致命的というわけでもない。
あと、出張のときに軽く持っていけるのもアドバンテージと言える。

今日の作業内容: CUDA 6h
今日のBGM: SKY OST [1-2]
今日のランチ: いろは 豚汁定食
明日の予測作業時間: 4h

2010年1月21日木曜日

Jack Dongarra 教授の講演

今日は、Jack Dongarra 教授の講演を聞いてきたので、それで大事と思ったところをメモ。
Jack Dongarra 教授は、High Performance Computing では、あまりに有名過ぎるので、どういう人かは省略。

まず、5個の重要なことがらについて。
  1. 複数コアがあるとき、いくつかのアーキテクチャが組み合わさっているときに、どうすれば効率的に利用できるか。
  2. 倍精度や単精度など精度を混合しながら、どう計算するか。(精度が必要なところだけ倍精度にすることで計算を速くする。)
  3. 自動チューニングはどうすればできるか。
  4. Fault Tolerant なアルゴリズムはどうすれば設計できるか。(1000以上の並列計算の場合、そのうちのいくつかが上手く動作しないことがあり、それをどう扱うか。)
  5. 複数コアや複数ノードの間で、いかに通信を少なくして計算するか。
などであった。これは、今後のアルゴリズム設計などにも勉強になりそうだ。
そのあとは、TOP500 に乗っているスーパーコンピュータがどれだけの性能を持っているか、という話で、

1993 年のとき、1位 は 59.7GFLOPS, 500位は 0.4GFLOPS で 1位から500位の合計が 3.27TFLOPS だったのが、
2009 年のとき、1位 は 3.76PFLOPS, 500位は 20.0TFLOPS で 1位から500位の合計が 27.68PFLOPS まで上昇しており、500 位の20.0TFLOPS でも 1997 年の合計に匹敵するとのこと。

そのあと、TOP5 ぐらいまでのスーパーコンピュータがどのように構成されているか、という話。
ちなみに、「日本は、どんどんと置いていかれている」ということだった。(たぶん、"Japan is falling down" って言っていたように聞き取れた、が英語の聞き間違いの可能性もある。)

あと、電力消費は電圧の2乗 x 周波数に比例して、周波数は電圧に比例するので、電力消費は周波数の3乗に比例するらしい。1位のスーパーコンピュータは、7MW(メガワット)の電力使用で普通の家の 7000 件に相当するとのこと。

ちなみに、国民一人当りのスーパーコンピュータ計算性能1位はニュージーランドで、映画撮影が多い影響でそれを処理するコンピュータも多い、ということで、これは面白い視点だった。

そのあとに、multicore でどのように LAPACK を高速化させるか、という話があって、これらは PLASMA というソフトに実装されている、とのこと。GPU の LAPACK は MAGMA になっていて、それぞれ

PLASMA : http://icl.cs.utk.edu/plasma
MAGMA : http://icl.cs.utk.edu/magma

から情報が得られる。これらについては、明日調べてみようと思う。並列計算をするときに、情報の依存性を DAG (Directed Acyclic Graph) で表現するのがポイント。

あと、並列計算のスケーラビリティの概念にもstrong と weak があって、weak scalability だと、問題が大きくなってくると台数が増えれば速くなる、のに対して strong だと問題のサイズは同じでも台数が増えただけ高速化される、という違いがある。


いずれにしても、これからは複数のコアなどが主流となり、いかに並列計算で性能を発揮させるか、そのようにアルゴリズム、ソフトウェアはどうあるべきか、が重要になるようだ。

Jack Dongarra 教授の英語は、ゆっくり喋ってくれたおかげか、だいぶ聞き取りやすかった。おかげでだいぶ勉強になった。


今日の作業内容: SNL の計算 3h + 講演聴講 1.5h
今日のBGM: かぜよみ 2回
今日のランチ: とりこまち 鶏唐揚げ定食
明日の予測作業時間: 5h

2010年1月20日水曜日

CUBLAS の sgemm のパフォーマンス測定

昨日にひきつづいて、sgemm を CUBLAS で実行したらどのくらいのスピードが出るかを確認。

結果としては、以下の感じ(GFLOPS, 理論性能値との比較)






N CUBLAS ATLAS GotoBLAS
4095 24.27, 27% 50.31, 65% 71.69, 93%
4096 50.55, 58% 53.47, 69% 72.19, 94%
4097 24.02, 27% 48.96, 63% 71.40, 92%

ただし、CUBLAS (Quadro FX 1800) の理論性能は86.9GFLOPS, CPU (Xeon E5520 x2) は 76.8GFLOPS として計算。

思っていたよりもCUBLAS は理論性能との乖離が大きい。あと、2^n になったときとそうでないときでの差も大きい。
実際に使うときには、このあたりを踏まえてプログラムを組む必要がありそうだ。

ちなみに、cublasSgemm は CPU の動きとは非同期で計算を進めているので、計算時間の測定は同期を取った上で行う必要がある。
他にも、実際に使うときの補足的な情報(時間計測などなど)は
http://matsu-www.is.titech.ac.jp/~naoya/teaching/gpgpu-tutorial-gsic-2009-library-usage.pdf
などが参考になるし、tune したときにどうなるのか、ということが書いてある PDF も発見。
http://mc.stanford.edu/cgi-bin/images/6/65/SC08_Volkov_GPU.pdf
そのうちに読んでみようと思う。


あとは、SNL の計算について。
SeDuMi でも、それなりに精度が出るが、SNL の計算結果の誤差を例えば 1.0e-8 に抑えるなら、SeDuMi の eps はいくつぐらい必要なのかを簡単な例で調べてみる。
どうやら、SeDuMi の eps とほぼ同等な桁で出てくるようだが、まだまだ調べる必要あり。
これに関して、SDPA-GMP でも同じ問題を解いた。ただ、%8.16e と出力桁数を増やして dat-s を生成すると pdOPT にならないが、%8.4e だと pdOPT になる。
4桁程度しか有効桁数がない情報で dat-s に %8.16eとすると、最後のあたりの桁が怪しい状態で dat-s に書き込まれるようだ。


ついでにメモ。RHEL で yum update したときに、
Error: failed to retrieve repodata/filelists.xml.gz from rhel-x86_64-server-5
と言ったエラーが出るときには、
# rhn-profile-sync
# yum clean all
# yum updae
とすると直る。この情報はどこかの Web ページで見つけたのだが、そのページがどこだったのか解からなくなってしまった。

今日の作業内容: sgemm 3h + SNL 3h
今日のBGM: 小松未歩ベスト [1-2], Chrono Trigger OST [1-3]
今日のランチ: らく カキフライ定食
明日の予測作業時間: 5h

2010年1月19日火曜日

2010年の学会下調べとBLASの簡易FLOPS測定

まず、昨日までの Matlab の戦いは、ついに終了。
Matlab を R2009b にしたら、SDPA-M が数値的に安定するようになった。
おそらく、Matlab に入っている libgfortran.X.dylib がバージョンが X=2 から X=3 になって、fink の gcc4.4 と同じバージョンになったことが効いているのかもしれない。
ちなみに、SDPA-M 用に修正した mexopts.sh で、そのまま SeDuMi もコンパイルできた。

あと、2010 年に行われる学会を教えてもらったので、それの下調べ。3つあるので、どれが内容として面白いか、などを他の仕事内容のスケジュールとすり合わせて検討する必要あり。

1. Erice 2010 [ホームページ]
非線形最適化の会議。
開催は 2010.7.2(Fri)-10(Sat) で、イタリアのシチリア島。
Contributed の Lecture 30分が、発表の時間のようだ。
ただ、若い人は CV と推薦状が必要と書いてある。
自分の年齢が、この若い人にあたるのかどうか、ちょっと解からない。
最初の〆切は Contributed Lecture の申込の 2010.4.2。

2. Euro 2010 [ホームページ]
ヨーロッパのOR学会。
開催は 2010.7.11(Sun)-14(Wed) で、リスボン。
Contributed talk があるようだけど、4ページの resume が必要かなどは不明。
最初の〆切は Abstract Submission で 2010.2.28。

3. 8th EuroOpt [ホームページ]
2の会議のサテライト会議で最適化中心。
開催は 2010.7.9(Fri)-10(Sat) で University of Aveiro。ポルトガルの中。
最初の〆切は Abstract Submission で 2010.5.10。

一番関係がありそうなのは、3だけど、うまくすれば 2と3ははしごできるかもしれない。そうすえば、2つの学会で勉強できて効率的だ。


あと、CUDA の BLAS (cublas)が実際にはいまひとつ性能が出ない、ということを耳にしたので、実際にどれくらい出るのかを試すためにまずは CUDA を使わない普通の CPU の BLAS を測定。
使ったのは、Xeon E5520 で、これは、
Intel のページ
を参照したところ、38.4GFLOPS ということ。
つまり、
2.4GHz(クロック数) x 4 (コア数) x 4 (1クロックあたりの計算) = 38.4 GFLOPS
であって、これを2基積んでいるので、最大で 76.8GFLOPS になる。
これに対して、GPU (Quadro FX 1800)は
64(SPの数)x 1.40 GHz(クロック数)= 89.6GFLOPS になる予定である。

[GPUのほうは、1クロックあたりの計算をカウントしていないので、もっと出るのかもしれないが、GFLOPS を載せてあるページがまだ見つからなかった。]

N=20,000 で sgemm を実行したところ、
GotoBLAS 108.78 秒 (73.54GFLOPS, 最大に対して95%)
ATLAS 143.69 秒(55.67GFLOPS, 最大に対して72%)
となった。
ただし、ここでのFLOPSの計算は、単純に[N^3/実測計算時間]なので厳密ではない。でも、とりあえず GPU と比較するには 十分かと思う。(どうやらATLAS の半分しか出ない、と聞いたので。それが FX1800 の限界なら、その性能をどう活かすかなので、今のところはOK。)
これで明日 cublas の sgemm を呼ぶプログラムを組んで比較してみようと思う。

今日の作業内容: Matlab 1h + 原稿チェック 2h + 学会下調べ 1h + sgemm 2h
今日のBGM: 小松未歩ベスト [1-2], MADLAX OST [1-2], Chrono Trigger OST [1,2]
今日のランチ: シッダルータ ほうれんそうとチキンのカレー
明日の予測作業時間: 6h

2010年1月18日月曜日

Mac と Matlab と gcc4.3 (つづき2)

今日も Mac で SDPA-M が動くかどうかの挑戦。
この前の時点で、64bit バイナリの SDPA はできているので、これに使った libsdpa.a を使って mex をすれば大丈夫、と思いきや、これが案外簡単ではなかった。

これに関して少しメモ。

Matlab は、R2009b の 64bit 版をインストール。
しかし、このバージョンの mex は maci64 のアーキテクチャでコンパイルしようとすると、gcc へのオプションが適切でなく、うまくいかない。(fink でインストールした gcc 4.4 を利用しているための可能性あり。)

まずは、Matlab の中で
mex -setup
として、~/.matlab/R2009b/mexopts.sh
を作る。これは、拡張子が示すとおり、シェルスクリプトなので、シェルスクリプトの要領で書き直すことができる。

fink の gcc4.4 を利用している場合、いくつかの変更が必要である。
まず、maci64 の部分を探して、以下の修正をする。
1. CC,CXX は gcc-4, g++-4 に変更する。gcc-4.0 などになっていることがある
2. gcc-4 は -arch をコマンドオプションとして受け付けないようなので、-arch $ARCH となっているところは削除する(g++-4にも注意)
3. LD も gcc-4 となっているので、これは g++-4 にする(しなくてもいいかもしれない)
4. LDFLAGS に -bundle があると crt1.10.5.0 にぶつかるので、このオプションは削除する
5. LDFLAGS に -dynamiclib をつけないと、
_main referenced in crt1.10.5.0
_MAIN__ referenced in libgfortranbegin.a
などと文句を言われる。Linux なら -shared で *.so が作られるが、Mac の場合は *.dylib なので -dynamiclib になる
6. CFLAGS, CXXFLAGS, LDFLAGS には -m64 オプションをつける

また、SDPA の make.inc からも -lcrt1.10.5 となっているところを削除する。

これらの修正をすると、SDPA-M を Mac のR2009b でコンパイルして実行できる。
ここまで長かった。

あと、BLAS/LAPACK のスレッド数を切替える maxNumCompThreads は将来的に消えてなくなる、という Warning が R2009b から出るようになった。
これがなくなると、Matlab が持っている MKL にリンクする理由がなくなるので、将来的に ATLAS か GotoBLAS にリンクするようにしたほうがいいのかもしれない。


あとは、SNL の計算。pertubation を加えて、すこし変更してみたが、このときに選ばれる枝まで変更されてしまい、位置が問題なのか枝が問題なのか切り分けがうまくいってない。これは明日調べてみよう。

今日の作業内容: Matlab との戦い 4h + SNL 2h
今日のBGM: ARIA OST [1-2]
今日のランチ: 味庵 ジャンボ餃子とピータンがゆ
明日の予測作業時間: 6h

2010年1月15日金曜日

Mac と Matlab と gcc4.3 (つづき)

今日も、昨日にひきつづいて Matlab について調べていたが、なんと MatlabR2008b は Mac 版は 32bit しかなかったことが判明。
うっかり 64bit だと思い込んでいたのがミスだった。
どうやら、fink にも 32bit, 64bit があるようで、fink でコンパイルされた atlas は 32bit 用のものだった。
つまり、SDPA の executables も 32bit だった。

そこで、atlas をソースからコンパイルしなおして、64bit 版の SDPA の executable を作成した。64bit 版のファイルかどうかは、

$ file ./sdpa
で解かって、ここで
sdpa: Mach-O 64bit executables x86_64
と表示される。Matlab については、
$ file /Applications/MATLAB_R2008b.app/bin/maci/MATLAB
とすると、
/Applications/MATLAB_R2008b.app/bin/maci/MATLAB: Mach-O executables i386
となって、32bit であることが解かる。

ちなみに、gcc に -m32 をつけたまま 64bit ライブラリとリンクしようとすると、
file is not of required architecture
と怒られる。つまり、-m32 なら全部を32bit, -m64 なら全部を64bit にしないと、上のようなエラーメッセージが出力されるようだ。

とりあえず、executables は 64 bit になったので、来週の頭に MatlabR2009b をインストールして、そこで SDPA-M をコンパイルしなおして確認してみよう。


あとは、SNL の入力用のサンプルを作ってみた。
SFSDP で解くと、思っていたのと違う答えが出てくるときがあるので、これについても来週調べることにしよう。
あと、rand('seed',1) で乱数を固定しているのに違う生成が起こるので、これも調べる必要があり。

今日の作業内容: Matlab 4h + SNL 2h
今日のBGM: EVA OST [1-3]
今日のランチ: らく うな重
明日の予測作業時間: 5h

2010年1月14日木曜日

Mac と Matlab と gcc4.3

今日は、数値実験を Mac でできるように Matlab をチェック。
結論から書くと、gcc4.3 の shared library をロードしてから MatlabR2008b を起動すると、クラッシュする。しかも、これが簡単には治せないようだ。

以下、あとでまた参考になるかもしれないので、メモ。

Mac の場合、どの shared library が載るかは
export DYLD_PRIT_LIBRARIES=
とすると解かる。ただし、ls を実行しただけでも表示されるので、shared library を調べるときだけに利用したほうがいい。

あと、shared library をMatlabに渡すには
$ export DYLD_LIBRARY_PATH=パス1:パス2
のようにする。複数あるときはコロンでつなぐ。
ただし、DYLD_LIBRARY_PATH は Matlab が利用するパスのあとに追加されるので、Matlab の shared library よりも先に指定したい場合には、
(MATLABのディレクトリ)/bin/.matlab7rc.sh
の途中で
LDPATH_PREFIX=''
という行を書き換える。
(デフォルトで '' なので、シェルスクリプトから export LDPATH_PREFIX としても、打ち消されてしまう。)

これらの情報をもとに
LDPATH_PREFIX='/sw/lib/gcc4.4/lib'
と書き換えてみたが、見事にクラッシュする。
どうやら、/sw/lib/gcc4.4/lib/libstdc++.6.dylib の ostream 関係と不具合を起こすらしい。


やはり、Matlab を R2009a/R2009b にするべきであろうか?
でも、R2009 から MKL のインターフェースが変更になってしまっていて、うまくいかない可能性が高い。

Mac OS X はまだまだ解からないだらけである。
明日も時間を作って調べることにしよう。

今日の作業内容: Mac 下調べ 6h
今日のBGM: EVA OST [1-3]
今日のランチ: いろは アスパラチーズ豚肉
明日の予測作業時間: 4h

2010年1月13日水曜日

SNLの計算の続き

今日は、まずホームページの更新をした。
リサーチレポート関係の情報にリンクを張るようにした。

SNL の計算については、昨日思いついたのは、よくよく考えると SFSDP に実装しているものによく似た結果になる可能性があった。そこで、明日 SFSDP の計算をもう一度よく見直してみようと思う(特に clique と correlative sparsity について)。

あと、SNL の計算を SDPA の複数スレッドで行うと、極端に遅くなることが判明。対角ブロックごとにスレッドを生成と終了を繰りかえしているが、SNL の場合には小さい対角ブロックが大量にあって、ひとつのスレッドが生成されてから終了するまでに実際に行う数値計算の時間が小さい割りにスレッドの管理が(相対的に)大きくなってしまう、ということが解かった。

対角ブロックの性質によって、スレッドに分けて計算するかどうするかを決めた方がいいかもしれない。

ついでに、MacOS X だと、SDPA-M を実行するときに libgfortran.dylib のところでメモリーリークになることがあるようだ。これは、Matlab にある libgfortran.dylib と MUMPS をコンパイルしているときの libgfortran.dylib(fink経由でインストールしたもの) にバージョン違いがあるためで、Linux だと LD_PRELOAD で回避できるが MacOS X だと LD_PRELOAD ではないので、LD_PRELOAD に相当するものが何かを今度調べる必要がある。
あと、valgrind を Mac OS X でソースからコンパイルしようとしたら、うまくいかなかった(tar+bz2もsvnのソースも)。いくつかパッケージが足りないようなのだが、あとで調べたら fink に valgrind が入っていたので、今度はこれをインストールしてみようと思う。

今日の作業内容: HP 更新 1h + 対角ブロック確認 2h + Mac OS X 調査 3h
今日のBGM: ARIA OST [1-2]
今日のランチ: シッダルータ キーマカレー
明日の予測作業時間: 6h

2010年1月12日火曜日

NT方向、難しすぎる

今日は、NT方向+ homogenous self-dual のプロトタイプ作成に挑戦してみたが、結果は今ひとつだった。
なぜか example1.dat-s を解くだけで、20000 反復もかかってしまう。やはり、homogenous self-dual は計算式が難しい。いろいろと修正はしてみたが、theta の収束が驚くほど遅い。2次収束するはずの step length なのに、1次収束よりも遅くなっている。
とりあえず、このプロトタイプ作りは、今日で打ち止めにして、また計算式を整理してから考えることにする。

それよりも、むしろ SNL の計算のほうをプライオリティをアップすることにした。
ひょっとしたら、変換をすると効率よく解けるかもしれない、というアイデアが出てきた。(うまく行けば)。
明日、So & Ye の論文をチェックして、どのような定理があったか、それが応用できるか確かめてみよう。

今日の作業内容: NT方向 5h
今日のBGM: FF5 Dear Friends, FF6 Grand Finale, FF7 Reunion
今日のランチ: らく 焼き魚定食
明日の予測作業時間: 6h

2010年1月9日土曜日

GotoBLAS だと Matlab からスレッド数を変更できない

今日は Matlab から GotoBLAS/ATLAS の dgemm を呼び出したらどうなるかをチェック。
コンパイルなどは特に問題なくできる。

ただ、Matlab の maxNumCompThreads に設定されているスレッド数を GotoBLAS に渡すことができないようだ。
実際にやっているのは、Matlab の中で、

setenv('OMP_NUM_THREADS','8');
setenv('GOTO_NUM_THREADS','8');
とすると、Matlab から mex を呼んでいるときに mex の中では両方とも環境変数として設定されているのだが、ここから libgoto2.a の関数を呼ぶときに伝わっていないようだ。ここで

$ nm mexDgemm.mexa64 | grep dgemm
とすると、

0000000000001b00 t dgemm_
の行があるので、すでに組み込まれているはずだが、ひょっとしたら、この中では OMP_NUM_THREADS を認識できないのかもしれない。

そういえば、mex でコンパイルするときに(内部で g++ を利用)、
-L(path) -lgoto2
だと、export LD_PRELOAD で指定しないとダメだったが、
(path)/libgoto2.a
だと、LD_PRELOAD を指定しなくてもOKだった。
このあたりとも影響があるのかもしれない。

ただし、Matlab を起動する前にコマンドラインで OMP_NUM_THREADS を指定すると、きちんと反映される。

以下は、行列のサイズを変更したときの dgemm のスピードの違い(単位は秒)。なお、
n: 行列のサイズ
th: スレッド数
Matlab: Matlab で普通に C0 = alpha*A*B + beta*C を実行
mwblas: Matlab にある blas を mex 経由で直接利用
プロセッサは、Xeon E5520 (2.27GHz) x2 でメモリは24GB
になっている。









dgemm スピードの違い
n th Matlab mwblas GotoBLAS2 ATLAS
6000 1 65.70 65.09 45.98 7.20
6000 8 9.11 8.69 19.94 7.23
10000 8 41.55 40.04 27.85 34.38
20000 8 332.43 327.77 258.81 308.74


どうやら、ATLAS は OMP_NUM_THREADS も無視して 8threads で計算するようだ。(libptf77blas.aはそうなのかもしれない。)
あと、行列が大きくなると、GotoBLAS が速くなるのがわかる。ただし、n=6000で 8スレッドが遅いのが不思議だ。

いずれにしても、GotoBLAS/ATLAS のスレッド数を maxNumCompThreads と連動できないとなると、SDPA-M で GotoBLAS/ATLAS に接続するのは難しいかもしれない

今日の作業内容: Matlab チェック
今日のBGM: NOIR OST [1-2]
明日の予測作業時間: 4h

2010年1月8日金曜日

情報収集な一日とそのメモ

今日は、調べているうちに、いろいろと調べるべきものが解かってきたので、そのメモが中心。

まず、
「数理計画法」コロナ社
の8.3,11章をチェックした。なかなかにいい内容だった。
このあたりの内容は、
Linear and Nonlinear Optimization, Igor Griva, Stephen G. Nash, Ariela Sofer, SIAM, 2009
にも詳しい。書いてある内容がよく似ているので、参考にしている論文が同じなのかもしれない。「数理計画法」の本のほうが証明などを省いている分、全体の見通しが解かりやすく、逆に「Linear and Nonlinear Optimization」は証明がある分、詳しい。

ところで、「Linear and Nonlinear Optimization」には、ステップ幅の取り方などが書かれている部分がある。これに従うと、局所的に2次収束するらしい。実際の数値計算でもそうなるのか、試してみようと思う。

あと、非線形最適化問題の内点法の詳細が書いてある論文として、
On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Mathematical Programming, 106 (2006), 25--57.
が紹介されていた。
よく書かれているなぁ、と思ったら Ipopt というソフトに実装されているもののようだ。
Ipopt もそのうち調べてみよう。ちなみに、Ipopt は COIN-OR のひとつでURLは
https://projects.coin-or.org/Ipopt
になっている。これは、MUMPS や LAPACK など SDPA でも使っているソフトを利用しているようだ。

他に調べたところでは、「情報幾何」という内容とのつながりがあった。
いくつかリンクを載せておくと、
対象錐上の主双対内点法と双対幾何構造(数値最適化の理論と実際) 魚橋慶子
対象錐線形計画法と群作用 魚橋慶子
正定値対称行列集合の数理-工学と代数・幾何の一つの接点 小原敦美

そのうちに時間ができたら、このあたりのことも調べてみようと思う。

とりあえずは、本当に2次収束するか、NT + self-dual + 本にあったステップの取り方 を Matlab でプロトタイプを組んでみようと思う。


あと、今後調べることのメモとして、GotoBLASやATLAS を Matlab から呼んだときに、Matlab が指定しているスレッド数をどのようにして GotoBLAS, ATLAS に渡すのか、を調べることにしよう。このあたりは、Linux と Mac OS X だと挙動が違うかもしれないので、注意が必要かもしれない。


今日の作業: 情報収集 5h
今日のBGM: FF12 OST [1,3]
今日のランチ: 味庵 マーボー春雨
明日の予測作業時間: 5h

2010年1月7日木曜日

DONLP2 の論文チェック

今日は、DONLP2 の論文をチェックした。
この論文は、DONLP2 の実装について詳しいので、実装に必要な数式などが細かく書いてある。
しかしながら、Sequential Quadratic Programmings 全体については、省略されているので、全体像が見づらい。
Wright の内点法の本でいうと 11 章の「実装の詳細」についてのような感じだ。

ただ、論文にしても DONLP2 のソースにしても、表現の癖がどうもしっくりとこないので、手強そうだ。
むしろ、自分で SQP を組んでしまったほうがいいのかもしれない。
どちらにしても、並列計算のソフトウェアを組むには、シリアル計算の段階から並列計算を意識したコードにしないといけない。

あと、SQP 関係を勉強しようと思って本を探していたところ、
「数理計画法」コロナ社
という本を発掘した。
この本は、非線形計画問題の基本的なところ(LagrangianやKKT条件)などについて基本的なところがまとめられており、なかなかにいい本なようだ。
特に感度分析のところが面白い。

SQP の復習も兼ねて、8.3 章と 11章を明日読んでみることにしよう。

今日の作業内容: DONLP2 チェック 2h + 本読み 2h
今日のBGM: DEWPRISM OST [1-2]
今日のランチ: シッダルータ ほうれんそうとチキンのカレー
明日の予測作業時間: 5h

2010年1月6日水曜日

CUDA と SDPA

今日は、SDPA で使っている BLAS/LAPACK が CUDA の CUBLAS/CULA で置き換えられるかをチェック。
CUBLAS は、それなりに関数が揃い始めているので使い勝手がありそうだ。まだ、三角行列などの一部関数が足りないが、それもそのうちにそろうかと思われる。(いまインストールしてある CUDA は ver 1.23)
ただ、CULA のほうは、あまり進んでいないようだ。まだ ge の行列だけで po や sy などは関数名が出てきていない。やはり、LAPACK レベルになると、GPU の特性を活かすのは難しいのかもしれない。

あと、DONLP2 の論文を久しぶりにチェック。
正月をはさんでしまったために、かなり忘れていることに気がつく。
あと、正月をはさんだことで英語を読むスピードも相当落ちてしまっていている。読んでいる途中に頭の中で日本語に訳してしまうところがある。もう少しスピードをあげないと。
ということで、DONLP2 の論文は、時間をかけてもダメなので、今週いっぱいと期限を決めて進めることにする。

今日の作業内容: CUDA チェック 2h + DONLP2 チェック 1h + その他 1h
今日のBGM: FF6 OST [1-3]
今日のランチ: つかさ 〆サバ
明日の予測作業時間: 5h

2010年1月5日火曜日

英会話スタート

今日から、仕事場が英語教室になった。

と、それはさておき、今日から 2010 年の仕事始め。
いきなり大きなことを始めるわけではなく、細かい作業から始めた。

まず、投稿用の文章は、正月休み中に数値実験が終わっていたので、これを文章に反映しておいた。文章としては、一通り形になったので、数日置いてからもう一度英語をチェックすることにする。

あとは、いろいろな下調べ。
まず、CUDA 関係では、
CUDA の固有値分解についてのレポート
をチェックした。どうやら、すべての固有値を列挙するところを、固有値が存在する範囲ごとに分割して並列計算に持ち込むようだ。lapack では dsyev などで固有値計算ができるが、これと数学的に同じことを CUDA の性能を活かしながら行っていくのは、かなりハードルが高いようだ。
というか、lapack のあちこちの関数を CUDA にするだけでも論文になってしまいそうな難しさだ。

あとは、SIAM News に載っていた Homology の論文をチェック。
関係論文へのリンク。
"Coordinate-free Coverage in Sensor Networks with Controlled Boundaries via Homology",
International Journal of Robotics Research , 25(12),2006, 1205--1222.

Homology を使って、ネットワークの構造を推定するようだ。(どこに頂点が少ない「穴」があるかがわかる、などなど。)ただ、Homology なので、ネットワークを構成する頂点の座標計算はしていないようだ。これは、他のとつないだら面白そうだ。

今日の作業内容: 文章校正 2h + 論文チェック 3h
今日のBGM: マクロスF OST [1], MADLAX OST [1-2], ARIA OST [1,3]
今日のランチ: らく 焼き魚定食
明日の予測作業時間: 6h