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

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

新クラスタの予定

2008年04月30日 01時20分36秒 | Weblog
この夏の新設されるクラスタ計算機の仕様は以下のようになった。

ノード数 : 16
CPU数 : 32
コア数 : 128

PowerEdge 2900III
CPU : Intel X5460 (3.16GHz)
メモリ : 48GB
HDD : 1TB × 6 (RAID5)
ネットワーク : Myrinet10G + GbE
Linpack 予想 : 1.3TFlops 前後

公約なので、このクラスタ計算機も Online Solver に加える予定。いろいろと制限があるとは言っても、1TFlops 越えの計算機をインターネットから無料で使えるようにするのは珍しいことだと思う。

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

数値精度の問題 その2

2008年04月29日 01時12分36秒 | Weblog
同じプログラムを PS3 (Cell: PowerPC 互換)で動作させてみた。PowerPC では long double の仮数部が 112bit なので、今度は以下のようになる。

GMP 1024bit > dd (仮数部 212bit) > GMP 128bit > long double (仮数部 112bit) > dd (仮数部 106bit) > GMP 64bit > double (仮数部 53bit)

+14.89844637278335071073342987801879644393920898437500 double
+14.89844637278335236989269414146889391515276993864095 long double

0.148984463727833523698e2 GMP 64 bits
0.1489844637278335236989269414146880472509e2 GMP 65 bits
0.1489844637278335236989269414146880472510693786988417389928759183851738069265823364104030973932230874e2 GMP 1024 bits

+1.48984463727833523698926941414688047251069378698841738992875918e+01 qd_real
+1.4898446372783352369892694141469e+01 dd_real

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

数値精度の問題 その1

2008年04月28日 01時07分47秒 | Weblog
昨年の3月にもブログで触れたのだが、以下の PI + PI + IP の計算を行い、様々な変数の数値精度を調べている。今回も以下のライブラリを用いる。

ライブラリ GMP (任意精度ライブラリ)
http://gmplib.org/

ライブラリ qd (擬似 4倍、8倍精度ライブラリ)
http://www.cs.berkeley.edu/~yozo/

#define PI 3.141592653589793238462643383279502884197169399375105820
#define IP 5.02884197169399375105820314159265358979323846264338327

今回の目的は long double (Intel系では 80bit) の相対的な精度を調べることにある。
精度の良さは以下のようになる。

GMP 1024bit > dd (仮数部 212bit) > GMP 128bit > dd (仮数部 106bit) > GMP 64bit > long double (仮数部 64bit) > double (仮数部 53bit)


+14.89844637278335071073342987801879644393920898437500 double
+14.89844637278335237086379638782318579615093767642975 long double

0.148984463727833523698e2 GMP 64 bits
0.1489844637278335236989269414146880472509e2 GMP 128 bits
0.1489844637278335236989269414146880472510693786988417389928759183851738069265823364104030973932230874e2 GMP 1024 bits

+1.48984463727833523698926941414688047251069378698841738992875918e+01 qd_real
+1.4898446372783352369892694141468e+01 dd_real
コメント
この記事をはてなブックマークに追加

SDPA Online Solver メモリ制限

2008年04月27日 00時44分37秒 | Weblog
最近では SDPA Online Solver で解かれている SDP は非常に大きなサイズであることが多く、メモリ使用量も簡単に数 GByte を越えてしまう。かなり大きな問題も投入されて常時スワップ状態になり、マシンが壊れそうな感じがする。以下のように core クラスタはメモリ 4GB なので、すぐにメモリが飽和する。そこでジョブマネージャーの設定を変更して、メモリ制限 3GB にしてみた(core クラスタのみ)。

# Opteron Cluster (core)
Opteron 240(2.0GHz) x 2
4GB memory
1000BASE-T x 2
5 nodes
# Xeon Server (power)
Quad-Core Xeon 5345(2.33GHz) x 2
16GB memory
1000BASE-T x 1
Myrinet 10G (since October 2007)
4 nodes

#
# Create and define queue dque
#
create queue sdpa
set queue sdpa queue_type = Execution
set queue sdpa enabled = True
set queue sdpa started = True
#set queue sdpa resources_max.nodect=4
#set queue sdpa resources_max.nodes=4
set queue sdpa resources_max.ncpus=4
set queue sdpa resources_max.mem=3gb
コメント
この記事をはてなブックマークに追加

サーバのトラブル

2008年04月26日 02時24分04秒 | Weblog
またまた4月の初めと同じで、SDPA のサーバの調子が悪い。某社製のサーバで1台70から80万円ぐらいの購入予算が必要だったが、1年もしないうちに壊れ始めてきた。同じ会社から同時期に購入した PC も1日何回も熱暴走してしまう。特に後者は壊れたというよりも、当初からエアーフローなどの設計に欠陥があったということだろう。それはともかく、SDPA サーバは全く別のマシンと交替させることにしよう。

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

デフォルトの設定

2008年04月25日 15時38分09秒 | Weblog
家で使っている洗濯機には”標準”、”念入り”、”ソフト”、”手造り”、”おいそぎ”というボタンついていて、特に手造りを選択すると、水の量、洗濯時間、すすぎの回数や時間、脱水の時間などが選べるようになっている。しかし、実際にはほとんど場合では標準ボタンを押してお任せ状態にしてしまう場合が多い。製品を作る側では、様々な選択肢を用意しているのだが、多くのユーザはデフォルトの設定のまま使ってしまうことが多いだろう。
というわけで SDPA Online Solver もソルバー、クラスタ計算機、CPU(コア)の数、メール通知などの様々な機能が付いていても、多くのユーザがデフォルトの設定のまま使っているようだ。今まではソルバーの選択では SDPA 6.2.1 がデフォルトになっていたので、SDPA 7.1.0 に変更した。クラスタ計算機の方は opt クラスタよりも power クラスタの方が高速だが、気が付く人だけ power クラスタの方を使ってもらいたい。
コメント
この記事をはてなブックマークに追加

最適化 Online Solver

2008年04月24日 04時08分14秒 | Weblog
最適化 Online Solver のシステムだが、以前予告したように SDPA 用とそれ以外にシステムを分けることになる。それは別々にした方がシステム的に安全になるという理由もあるのだが、他にも理由が存在する。
1:当面は SDPA の方はそこそこユーザが来るだろうが、それ以外(組合せ最適化関係)はどれだけユーザ来るのかわからない。
2:両サーバでは異なった機能が必要になる
3:SDPA の方は計算量が必要なので、実際の計算はサーバではなく、クラスタ計算機の方に計算を任せる。組合せ最適化の方は主にサーバで処理。

SDPA の方は pthread, OpenMP, MPI と何でもありだが、組合せ最適化の方は現時点では全てシングルスレッドで動いているようである。ただし最短路問題に対するダイクストラ法は一応マルチスレッド化されている。
コメント
この記事をはてなブックマークに追加

省電力で最適化

2008年04月23日 03時56分01秒 | Weblog
Windows Vista が失敗した理由の一つは中の処理を大変複雑にして高価なパーツを搭載したマシンでしか満足に動作しないという時代に逆行したことを行ったからだと言われている。よく使われるトリックで A が正しいのか、正しくないのかを問うのではなく、関係ない B を用意して、A, B のどちらが正しいのかを問うという方法がある(答えは両方とも間違い)。Vista があまりにもダメなので、XP は”まだまし”、あるいは良いと思われがちだが、実は両方とも良くない。XP も 2001 年の後半に出たときは動作は軽かったのだが、XP SP2 になり、OS 本来の不備からウイルス・スパイウェア対策ソフトを常駐させる必要があるので動作が大変重くなった。古い XP 搭載パソコンなどは、まさにこの理由によって同じ XP のはずなのに今では使い物にならないほど遅い。それでも Windows 2000 が良かったというのは思い込みではなく多分本当だと思う。
というわけで時代は小型化、省電力化、簡易化ということで、分野によっても変わるのだが、ユーザがどのような予算、環境で、どの程度複雑なものを考えていきたいかによって計算方法や環境を変えていくことになろう。ユーザが携帯電話や PDA で処理したいと言えばその環境での実行を考慮することになろう。今まではパソコンよりも劣った環境で最適化というのはほとんど考慮されて来なかった。場合によってはクラスタ計算機でがんがん計算するということも出てくるが、実行環境がアルゴリズムやデータ構造にも影響を及ぼしてくる。
コメント
この記事をはてなブックマークに追加

PS3 でスーパーコンピュータ

2008年04月22日 03時16分24秒 | Weblog
以前に Yellow Dog Linux の Terra Soft の CEO が来日して講演を聞いた話を書いたが、その後も長く日本に滞在して日本の企業関係者といろいろと戦略を練っていたようだ。最近でも以下のような記事があり、米空軍の研究所(AFRL)は Cell プロセッサの評価のために300台の PS3を購入した話まで出ている。Cell は PS3 以外にも搭載されているので、Cell でスーパーコンピュータを作るのと、PS3 でスーパーコンピュータを作るのでは結構異なる。PS3 はメモリが少なく、信頼性も高くないのだが、とにかく激安なので大量に購入してスパコンを作ろうという人は少なくはない。PS3 を Linux で使っていると、ディスクアクセスはそこそこ速いが、通常の処理がかなり遅い。多分メモリが少ないことに原因があって、せめてメモリ 1GB でもあれば使い勝手はかなり変わりそうだ。
一方 PS3 を普通にデフォルトのシステムで起動するとゲームも含めて動作は非常に高速だ。SONY のハイビジョン Handycam で撮影した動画を PS3 に移動して再生すると非常にスムーズに再生できる(再生がもたついたのは見たことがない)。一方並のパソコンでこの動画を再生するとコマ落ちしまくる。同じハードなのに Linux の時とは別人のようである。PS3 の能力を引き出すのはかなり難しい。

一家に1台のスパコンを実現した PS3の CPU パワーの秘密
コメント
この記事をはてなブックマークに追加

鉄道革命

2008年04月21日 02時55分57秒 | Weblog
今週の東洋経済誌の特集は”鉄道革命”ということで、原油高の中で世界的に交通の比重が鉄道へのシフトしていることと日本 v.s. 欧州の世界中での高速鉄道の受注合戦を取り上げている。すでにパリ、ロンドン間の交通ではユーロスターのシェアが7割になって飛行機を圧倒する勢いである。パリ、ロンドン間は2時間15分なので、東京、京都間とほぼ同じである。良く比較に出される最高速度であるが、実際には定時運行率や列車運転間隔の方が重要であり、この点では日本の新幹線(特に東海道新幹線)に勝るものは他にはない。
JR東海としては東京、名古屋間にリニア新幹線を開通させて実績を作り、その後で大阪まで延伸することや海外進出を考えているようだが、欧州は日本の技術導入は心情的に無理であり(興味は持っている)、中国は20、30年後にどのような状況になっているのか大変不透明な事情もあって(これも中国政府は興味津々だが)、アメリカの東海岸(ニューヨーク、ワシントン間)が想定されている。世界的にみてもリニア新幹線を導入できるような地域は現在では東京、大阪間かニューヨーク、ワシントン間ぐらいであろう。アメリカのガソリン消費量は2位の日本から21位の韓国までを足したよりも多く、車、飛行機以外の交通手段を発展させなければ明らかに限界である。
海外のテレビを見ているとマグレブ(リニアモーターカーのこと)は速くて魅力的だが、コストが高く、鉄道も 500km/h 以上出せるので不要ではないかという意見がある。その通りである可能性も否定できないが、鉄道では 500km/h で安定して営業運転できるのだろうか。超電導リニアの方は 500km/h は別に限界速度というわけではない。
コメント
この記事をはてなブックマークに追加

Atom と Mobile PC

2008年04月20日 04時19分13秒 | Weblog
Willcom から新しい PHS & Mobile PC の D4 (SHARP 製)が発売される。一般的な反応としては Windows Vista 搭載や価格対する不満が多いようだ。それはともかく、Intel Atom 搭載の高速な PDA や Mobile PC の登場を待っていたので、そのスペックや価格は参考になるものが多い。他力本願だが、アーキテクチャ的には普通の PC と同じなので、誰かが Linux を動作できるようにしてくれるのではないかという期待がある。Linux が動けば Vista など消してしまって、補償が利かなくなっても、本来の機能が使えなくなって構わないので、他に適当な Atom 搭載マシンが無ければ購入するかもしれない。最短路問題に対するソルバーを入れて動かしてみるのが目的で、これだけの仕様があれば前処理なしで解いたり、前処理 + ダイクストラ法という方法を使うこともできる。

CPU Intel® Atom™プロセッサー Z520 (1.33GHz)
キャッシュメモリー 1次:56KB、2次:512KB内蔵
チップセット US15W
システムバス(メモリーバス) 133MHz(533MHz)
メインメモリー 1GB固定(DDR2-533、PC2‐4200対応)

ハードディスクドライブ ※7 約40GB(1.8型、Ultra ATA/100)
フォーマット NTFS
コメント
この記事をはてなブックマークに追加

メモリ 64MB + コンパクトフラッシュ 4GB

2008年04月19日 04時29分32秒 | Weblog
かなりきつい環境ではあるが、以下のハードウェア + コンパクトフラッシュ(4GB or 8GB)で前処理付きのダイクストラ法を動かしてみることにした。せめてメモリ 128 or 256MB あって欲しいところだが、この量ではさすがに無理かなという気もする。同様な研究は海外にあるので、どこで差を出すかを考案中。

ハードウエア仕様
Armadillo-500 CPUモジュール
プロセッサ Freescale i.MX31L
CPU コア ARM1136JF-S (400MHz)
  - I/Dキャッシュ 16KB/16KB
  - L2キャッシュ 128KB
  - ベクタ浮動小数点コプロセッサ(VFP)搭載
DDR SDRAM 64MB
フラッシュメモリ 16MB (NOR)
コメント
この記事をはてなブックマークに追加

SDPA-GMP の遊び方 その2

2008年04月18日 03時59分32秒 | Weblog
SDPA の内点法ではまず実行可能解を求めてから最適解を探すという方針を取っている。もう少し詳しく書くと実行可能性(解の残差)と相補性という二つの指標があり、ある解が最適解であるためには両方の指標がほぼ 0 になっている必要がある。そういった意味では二目的の多目的計画法に近いのだが、この二つは場合によっては両方を同時に 0 にするのは難しいので、どちらかはある程度大きくてもよいという妥協策を取ることもある。
実行可能解でなくても良いのならば相補性を 0 に近づけることは簡単だが、本来の最適解を求めるという目的から考えると意味のない答えである。以下の場合も SDPA 7.1.0 の結果を見ると最適目的関数値は-1.5444911 と -1.5445577 の間に存在するように見えるが、SDPA-GMP 7.1.0 の結果から -1.54449168 と 1.54449169 の間に存在する可能性が高いことがわかる。SDPA 7.1.0 の方が解の残差が大きく、実行可能解でないところで無理やり相補性を 0 にしようとした結果、このような現象が起きていると考えられる。

SDPA 7.1.0 (問題 gpp250-1.dat-s)
phase.value = pdFEAS
Iteration = 17
mu = 2.6786921662278472e-06
relative gap = 4.3126405688101595e-05
gap = 6.6967304155696183e-04
digits = 4.3652567360314469e+00
objValPrimal = -1.5444911298505602e+01
objValDual = -1.5445577396379282e+01
p.feas.error = 9.6633812063373625e-13
d.feas.error = 8.6997875570204997e-09
total time = 0.690
main loop time = 0.640000
total time = 0.690000
file read time = 0.050000


SDPA-GMP 7.1.0 (問題 gpp250-1.dat-s)
phase.value = pdOPT
Iteration = 24
mu = 4.5342833853426345e-10
relative gap = 7.2512646081384840e-09
gap = 1.1335708463356586e-07
digits = 8.1395862466093263e+00
objValPrimal = -1.5444916880799692e+01
objValDual = -1.5444916992794872e+01
p.feas.error = 1.3817869688151111e-76
d.feas.error = 5.6487209425962712e-15
relative eps = 8.6361685550944446e-78
total time = 867.000
main loop time = 866.860000
total time = 867.000000
file read time = 0.090000
コメント
この記事をはてなブックマークに追加

SDPA-GMP の遊び方 その1

2008年04月17日 03時40分40秒 | Weblog
無事に公開できた SDPA-GMP だが、大変にマニアックなソフトウェアにも関わらず複数のユーザがすでにいるようだ。SDPA-GMP では、通常の SDPA のパラメータにさらに新しいパラメータ(precision)が加わった。GMP は任意精度計算なので、計算する精度を指定することができる。

200 unsigned int maxIteration;
1.0E-8 double 0.0 <epsilonStar; 1.0E5 double upperBound;
0.1 double 0.0 <= betaStar < 1.0;
0.2 double 0.0 <= betaBar < 1.0, betaStar <= betaBar;
0.9 double 0.0 <gammaStar < 1.0;
precision で仮数部の bit 数を指定することができる。例えば 52 にすると仮数部だけみると double(倍精度)と同じになる。また上記のように 200 に指定すると 2^200 = 1.6069 times 10^{60}.} となり、約 60 桁の精度があることがわかる。というわけで、このパラメータを変化させながら問題を解いていって得られる解の精度を調べると、実際にどのくらいの大きさの仮数部があれば良いかがわかる。そうすると倍精度では精度が足りないが、4倍精度ならば十分といった情報を得ることも可能である。

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

最適化 Online Solver

2008年04月16日 03時08分34秒 | Weblog
SDPA Online Solver の拡張から始まる最適化 Online Solver だが、予算申請が通ったので正式に取り組むことになった。申請が通らなくても行うつもりだったのだが、今度は義務になった。申請が通ったということは、こういった最適化 Online Solver があった方が良いと思っている人も少なくないということだろうか。申請時よりもさらに構想が進んでていて、それらに対する計画や方針も決まっている。しかし人的資源が不足しているので、当初の計画は達成できると思うがそれ以上はどこまで出来るかわからない。何しろ人材の現地調達が出来ないので、あと数年ぐらいが限界か。
コメント
この記事をはてなブックマークに追加