最適化問題に対する超高速&安定計算

クラスタ計算機やスーパーコンピュータ上での大規模最適化問題やグラフ探索などの研究のお話が中心

Windows で Parallel Python

2008年01月31日 00時50分33秒 | Weblog
前回は Linux 上で Parallel Python を試したが、Windows 上でも出来るらしいので、試してみた。結果から言えば Python のダウンロードから並列計算までほんの数分で完了した。試したのは Windows XP Pro. SP2(32bit) の環境になる。

1: Python Windows 版のダウンロードとインストール
2: 環境変数で path を Python をインストールしたディレクトリに通す
3: コマンドプロンプトを起動
4: サンプルプログラムの起動 python sum_primes.py [ncpus]

実行結果
1CPU : 10.577s
2CPU : 6.796s

コメント
この記事をはてなブックマークに追加

Parallel Python

2008年01月30日 00時42分01秒 | Weblog
Parallel Python を使うと Python から簡単にジョブ並列(タスク並列)を行うことができる。以下のような環境で使用することができる。Linux マシン(クラスタ)で試したみたところ、確かに簡単に出来た。

1: SMP(マルチコアも含む)のマシンで並列計算
2: クラスタ計算機上での並列計算 (1も含む)

Parallel Python をダウンロードページから入手して、展開した後に python setup.py install とすればインストールは終わり(管理者権限のユーザで行う必要あり)。サンプルファイルとして配布されている sum_primes.py を用いてみよう。

1 の場合:
python sum_primes.py [ncpus] とすれば良い。[ncpus] は同時に使用する CPU(コア) の数。

1CPU : 5.731s
2CPU : 3.012s
4CPU : 1.628s
8CPU : 1.078s

2 の場合:
実行したいノード上で ./ppserver.py とサーバプロセスを起動する。その後でソースファイルの ppservers=("node-1", "node-2", "node-3") の部分を変更する。

これらのサンプルを見れば、実装方法は簡単に理解できる。Ninf と同じようにタスク並列を行うことができるが、こちらの方が簡単。
コメント
この記事をはてなブックマークに追加

宇宙の疑問

2008年01月29日 03時02分11秒 | Weblog
ブルーバックスに宇宙 300 の大疑問という本があって、専門家が非専門家(普通の素人も含めて)が抱きそうな疑問(二つのブラックホールが衝突したらどうなるか?など)と答えが掲載されている。本来、専門家というのは一見馬鹿馬鹿しく見える素人の質問にも、なるべく簡易に答えられないといけない。SF やアニメの世界では、とにかく頻繁に惑星が爆発する。宇宙戦艦ヤマトには惑星破壊ミサイルとかいうものまで登場する。この本によると惑星自体は爆発しないというか、例えば地球だと重力エネルギーに逆らって、地球をバラバラにしてしまうような巨大なエネルギーあるいはエネルギーを放出するようなプロセスは存在しない。反対に外部からエネルギーを加えて爆発させようとすると地球の総重力ポテンシャルエネルギー以上の量が必要になる。およそ 2.5 × 10^39 エルグ(太陽が10日間に生み出すエネルギー量に相当)なので、地球上の全核兵器や爆発物を用いても足りない。しかもこのエネルギーを地球の中心核に与える必要があるとのことなので、実際にはさらに困難な作業になろう。
コメント
この記事をはてなブックマークに追加

グラフ分割問題 その2

2008年01月28日 02時01分12秒 | Weblog
下界の定式化だが、添付の図の (5.9) のように定式化したら良い。これを定式化(A)としよう。(5.8) から (5.9) に変換してくるときに、C_ij が対称行列なので x_i^2 = 1/4 になっている。ここで x_i^2 = 1 として、行列 B の要素をすべて 1/4 にしても(つまり B' = 1/4 B)、等価な定式化になる。これを定式化(B) としよう。この (A) と (B) を両方とも SDPA + GotoBLAS の最新版を用いて解いてみた。こんな小さな問題に最新版の SDPA を用いるのは、ビルを1棟壊すのに直径数キロの小惑星を秒速30キロで宇宙からぶつけるくらいオーバーなことだが、(A)と(B)の両方を解くと基本的に解は同じになる。でも実験結果をよく見ると、少し結果が異なることに気付く。何故そうなるのか考察できると好ましい。
コメント
この記事をはてなブックマークに追加

グラフ分割問題 その1

2008年01月27日 01時13分40秒 | Weblog
レポートで提出した問題で、このグラフのグラフ分割問題の上界(全列挙でも、メタ解法でもよい)と下界(SDP 緩和)を求めるというもの。簡単なようだが、今まで一度も最適化問題やソフトウェアに触れたことがない人には結構大変なようだ。上界はすぐにわかる(全列挙しても20通りなので)。
コメント
この記事をはてなブックマークに追加

東京風景

2008年01月26日 00時58分41秒 | Weblog
NHK などは当然ながら昔から現在に至るまで日本各地の映像を大量に所有している。数年前に NHK 総合の深夜枠で例えば 70 年代の事件や風景などを当時ヒットした曲を BGM にして放送していたが、NHK が持つ 1945 年から 1980 年までの東京風景の映像が DVD になって発売されている。
中学生のときは第二次シンナーブーム?で学校に行っても部屋がシンナー臭かったりして、密かに巻き添えをくっていた。そのときに良く耳にしたのが、第一次シンナーブームと言うのかしらないが、60年代の後半ぐらいに新宿東口の路上でシンナーを吸っている若者(いわゆるフーテン族)が現れはじめたということだった。新宿の東口でシンナー吸えば即逮捕みたいなイメージがあったので、いくら60年代とは言っても実感が湧かなかったが、この NHK の DVD 東京風景第4巻には、1968年6月頃だが新宿東口でシンナーを吸う男性、ラリって足もとがふらついている女性の映像が収録されている。初めて本物を見たが、今だけが特別に世の中が乱れているわけではないことがわかる映像だ。
コメント
この記事をはてなブックマークに追加

博士課程

2008年01月25日 00時26分57秒 | Weblog
日本でも博士課程の学費を免除する大学が少しずつ現われてきているが、博士課程の学費はあまり高くはないので、それだけでは魅力に乏しいのではないかという意見がある。GCOE(グローバル COE)を取った大学では学生に教育に関する仕事を担当してもらう代わりにその分の給料を支払う仕組みを取っている。その他にも学振などがあるので、上位の大学では在学中はそれほどお金に不自由することなく研究できるようになっている。
昔はこういった制度はあまりなく、恩恵に預かれるのは一部の大学の一部の研究室だけだったので、自分が博士課程の学生だったころはもらえたのは育英会の奨学金ぐらいで後は何もなかったので、とにかく良く働いた。あまりお金を使わないように大学でみんなで自炊したりしたが、とにかく院生は大学にいることが重要だった。大学いれば基本的にインターネットしたり、ゲームしたり、漫画読んでいても、たまに思い出したように研究もするので、年間の総研究時間は結構なものになる。
今から振り返れば、あまり多くの奨学金等をもらえずお金にも苦労したことが、かえって適度に自分を追いつめて良かったのではないかと思う。ただ海外の学会等に行ってみて、海外の超一流大学の学生は一通り全ての分野で教育されてきているので、総合力では敵わないと思った(一点突破では勝てるが)。理論から実装まで全部習っているので何でも一応できる。でも大学で習わないところでは十分勝負できるので、そこが面白いところだ。
コメント
この記事をはてなブックマークに追加

GotoBLAS 1.22 と Cell

2008年01月24日 01時41分56秒 | Weblog
GotoBLAS 1.22 から Cell 正式対応になっている。Cell(PS3 上)において、GotoBLAS 1.22 以前では ppc970mpp として make を行っていたが、1.22 では普通に quickbuild.64bit で作成できるようになった。

1: SDPA 7.0.5 rev3 + LAPACK(BLAS) 3.1.1
2: SDPA 7.0.5 rev3 + ATLAS 3.8.0
3: SDPA 7.0.5 rev3 + GotoBLAS 1.21(ppc970mpp)
4: SDPA 7.0.5 rev3 + GotoBLAS 1.22(cell)

○問題 mcp500-1
1: 1m41.067s
2: 0m29.301s
3: 0m28.876s
4: 0m20.913s

○問題 theta3
1: 1m8.500s
2: 0m14.678s
3: 0m14.650s
4: 0m12.280s

○問題 r2S_broydenTri600
1: 0m20.795s
2: 0m21.809s
3: 0m21.709s
4: 0m21.324s

通常は GotoBLAS 1.22 > GotoBLAS 1.21 = ATLAS 3.8.0 > LAPACK(BLAS)3.1.1 だが、r2S_broydenTri600 のように SparseCholesky 分解を用いる場合は BLAS を使う比率が少ないので、あまり差がでない。
コメント
この記事をはてなブックマークに追加

Cell と gcc 4.3 と CFLAGS

2008年01月23日 01時06分58秒 | Weblog
gcc 4.3 以降では以下のように -mcpu=cell を使用することができる。
CFLAGS="-O2 -pipe -mcpu=cell -mabi=altivec"
gcc 4.3 は正式版がまだリリースされていないので、以下の開発版を用いる。
gcc version 4.3.0 20080111 (experimental) (GCC)
gcc 4.1.2 と 4.3 を比較してみよう。

1: gcc 4.1.2
gcc バージョン 4.1.2 20070925 (Red Hat 4.1.2-33)
CFLAGS="-O2 -funroll-all-loops -m64 -mcpu=G5 -mabi=altivec"

2: gcc 4.3
gcc version 4.3.0 20080111 (experimental) (GCC)
CFLAGS="-O2 -funroll-all-loops -m64 -mcpu=cell -mabi=altivec"

ソフトウェア SDPA 7.0.5 rev3 + LAPACK(BLAS) 3.1.1

○問題 mcp500-1
1: 1m31.231s
2: 1m31.726s

○問題 theta3
1: 0m55.756s
2: 0m58.067s

○問題 r2S_broydenTri600
1: 0m15.588s
2: 0m15.585s

というわけで、特に効果は認められない。
コメント
この記事をはてなブックマークに追加

SDPA の Callable library

2008年01月22日 03時40分36秒 | Weblog
SDPA 7 の方はマニュアル類が完成次第、すぐに公開ということになっているが、SDPA 6 以前ではコマンドラインでの実行だけでなく、Callable library も備えている。ただし Callable library の機能を加えるためには、新たな関数を用意するなどソースをかなり変更する必要がある。そのため毎回結構大変な思いをしているのだが、最初から関数を API 化して Callable library として作成して、コマンドライン版の SDPA 自体もこの library を利用して作成するという方が結局楽であるという話しになってきている。
コメント
この記事をはてなブックマークに追加

GPS による測位

2008年01月21日 03時16分32秒 | Weblog
GPS で位置を測位するためには、緯度、経度、高さの三つの要素が特定できれば良いので、三つの衛星が見えれば(電波が受信できれば)十分と思いこんでいたのだが、実際には GPS 受信機と GPS 衛星がそれぞれ内蔵している時計には時間差がある。GPS 衛星の方は精度の高い原子時計を搭載し、地上の基地からも補正しているので、かなり正確な時刻を持っているが、受信側はそれと比較すると誤差が大きい。というわけで受信機側の時間の誤差も変数に入れて、結局の四つの変数が存在するので、四つの衛星が見えていることが条件となる。もちろん四つ以上の衛星が見えればさらに精度は上がっていく(衛星数が2倍になると精度は√2倍になる)。
ただし衛星の数が多ければ良いというものでもないらしく、日本が打ち上げた MTSAT も同時に用いて精度を上げようとしても、かえって精度が悪くなることもあるらしい。どこかに技術的な問題があるのだろう。反対に一度測位してしまえば、受信機側の時間もすぐにずれるわけではないので、時間の誤差を省略して三つの衛星で測位ができる。さらに高さも変化していないと仮定すれば二つの衛星でも測位が可能である。

コメント
この記事をはてなブックマークに追加

Crusoe

2008年01月20日 02時48分05秒 | Weblog
一昔前に Crusoe という CPU が少しだけ流行った。Crusoe はトランスメタが開発したx86互換マイクロプロセッサであって、低消費電力が認められローエンドのノートパソコンに採用された。個人的にも Crusoe 搭載のシャープのメビウスノート(PC-MW1-H1W)を持っているが、メモリが 256Mbyte(x86 命令変換用のソフトウェア搭載のため、実際に使える容量は 240Mbyte)、クロックが 860MHz, ビデオカードが PCI 接続という仕様なので、現在では XP SP2 を動かすのも相当厳しい。そこで初期状態に戻して、必要最小限のソフトだけ入れ直して再出発することにした。
CPU を調べるとサポートする SIMD は MMX だけで、キャッシュは L1 データ & kbyte命令が 64kbyte ずつ、L2 は 512kbyte となっている。結局 Intel などの大手が Pentium M などの高性能、低消費電力の CPU は出荷したので、Crusoe もすぐに消えてしまった(一応 Efficeon という後継もあったのだが)。
コメント
この記事をはてなブックマークに追加

Shur complement 行列のマルチスレッド化 その2

2008年01月19日 03時21分15秒 | Weblog
前回の続きで簡単な実験を行ってみる。環境は SDPA 7.0.5 + pthread , CPU : Intel Xeon E5345(2.33GHz : 4コア×2CPU), OS : CentOS Ver.5 , GotoBLAS 1.20  である。

1: 並列化の効果が見えやすい問題 : D256.dat (GotoBLAS は 1スレッドで動作)

1スレッド : 実行時間 68.26 秒
2スレッド : 実行時間 41.24 秒
4スレッド : 実行時間 28.31 秒
8スレッド : 実行時間 23.85 秒

1スレッドのときの gprof の結果

Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ms/call ms/call name
42.39 21.93 21.93 daxpy_k
22.73 33.69 11.76 dgemm_kernel
10.84 39.30 5.61 78570 0.07 0.07 calF2_C
9.35 44.14 4.84 463608 0.01 0.01 calF1_C
6.42 47.46 3.32 ddot_
1.72 48.35 0.89 3276 0.27 0.27 multiply_C_SD
1.24 48.99 0.64 dgemm_otcopy
0.85 49.43 0.44 dgemm_oncopy
0.54 49.71 0.28 dgemm_beta
0.53 49.99 0.28 daxpy_
0.52 50.26 0.27 thread_func

2: 並列化の効果が見えない問題 : mcp500-1.dat-s (GotoBLAS は 1 スレッドで動作)

1スレッド : 実行時間 6.46 秒
2スレッド : 実行時間 6.56 秒
4スレッド : 実行時間 6.49 秒
8スレッド : 実行時間 6.40 秒

1スレッドのときの gprof の結果

Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ms/call ms/call name
61.70 3.48 3.48 dgemm_kernel
5.14 3.77 0.29 dtrsm_kernel_LT
4.08 4.00 0.23 dcopy_k
3.55 4.20 0.20 daxpy_k
3.55 4.40 0.20 dgemm_otcopy
3.55 4.60 0.20 dgemv_n
2.84 4.76 0.16 dtrmm_kernel_LN
2.66 4.91 0.15 thread_func
2.13 5.03 0.12 dgemm_oncopy
1.77 5.13 0.10 ddot_
1.60 5.22 0.09 dgemm_beta
1.42 5.30 0.08 dtrsm_kernel_RN
0.89 5.35 0.05 dscal_k

まだデータ収集中なので、細かい分析は出来ていないが、ある程度大きな問題でないとマルチスレッドの効果が得られにくい。また calF3_C(static inline なのでプロファイルには現れないが) の呼び出しを多用する場合にはマルチスレッドの効果が得られにくい。上記の mcp500-1.dat-s などがこれに該当する。
コメント
この記事をはてなブックマークに追加

Shur complement 行列のマルチスレッド化 その1

2008年01月18日 02時42分43秒 | Weblog
SDP に対する主双対内点法では、Shur complement 行列の全要素の計算と、この行列の Cholesky 分解という二大ボトルネックがある。特に前者のボトルネックは上手に計算すると隠蔽することができる。ただし、いろいろ工夫しても結局、行列積の計算は必要になるので、BLAS を用いている場合にはプロファイリングをして dgemm が一番上に上がって来たら、とりあえずは成功である。
この Shur complement 行列は全ての要素が独立して計算できるので並列計算に向いているが、計算式の関係から、ある行の全ての要素は一つのプロセス(スレッド)で計算した方が有利である(ただし対称行列なので行と列を反対しても議論は同じ)。SDPARA というソフトウェアでは、この Shur complement 行列の各行の計算を MPI とクラスタ計算機を用いて並列化した。これと同じようなアイデアで今回は pthread を用いて、クラスタ計算機ではなくマルチコア CPU 搭載の 1 マシンで並列化を行ってみた。結果についてはその2で報告する。
コメント
この記事をはてなブックマークに追加

連動して発生する巨大地震

2008年01月17日 02時16分37秒 | Weblog
定期的に地震について扱っている科学雑誌のニュートンムックの別冊で"連動して発生する巨大地震"が発売された。中身を見ると過去のニュートンの特集などを再構成して掲載されている。過去のムックも何冊か持っているので、必要ないかと思ったが結構新しい内容も含まれているので購入した。とにかく、地震や防災については毎年新しい話題が出てくるので定期的にチェックしておく必要がある。2003年に十勝沖地震で苫小牧の製油所タンクが炎上して、スロッシング現象が話題になったが、最近たまたま目にした研究ではダンパーなどを用いて、なるべく低価格で簡単にスロッシング現象を防ぐかというのがあった。我々が子供のときは、超高層ビルは柔構造で地震に強いと言われていたが、長周期振動という新たな問題点が発生しているし、最近では強化コンクリートが火災に遭ったときに熱によって破砕する可能性も指摘されている。これらも発生することがわかってしまえば対策も検討できるが、超高層のような”不自然”な建物は地震、台風、火事、テロなどから全て安全に守るのは無理ではないかと思う。個人的には本当に重要な建物(本社やデータセンターなど)は低層で柱、壁、梁などが厚い鉄筋コンクリートで造っておいた方が良いと思っている。
コメント
この記事をはてなブックマークに追加