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

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

RAMP2007

2007年10月31日 01時14分19秒 | Weblog
数理計画シンポジウム RAMP2007 に始めから終わりまで参加して全部の発表を聞いた。
1: 会場は非常に素晴らしいところで(広く、奇麗で場所も良い)、懇親会も良かったらしい(私は参加していないが)。実行委員会の方には大変感謝している。
2: 理論系の研究でも応用面を重視し、反対に事例でも最適化手法などについても新しいものを取り入れていこうという姿勢が見られるので、良い傾向ではないかと思われる。企業系の参加者が増えているので、今後は離散系でも連続系でもあまりにも理論的すぎるものはシンポジウムの雰囲気にそぐわない感じもしてきた。
3: 計算量が指数オーダーの NP 困難な問題でも規模がそれほど大きくなければ最適に解けてしまうし、反対に計算量が多項式でも問題の規模が大きくなれば結局解けない。計算量の本を鵜呑みしていると危険。
4: 量子コンピュータがもし実現できれば NP complete(NP 完全)な問題も多項式で解ける可能性はあるが、量子コンピュータを使っても多項式時間では解決できない QMA complete という、さらに恐怖の問題のクラスがある。

SDP も12年前に研究を始めたときには、一部の人のマニアックな世界という感じだったが、最近では国内外で商用ソルバーなどにも組み込まれることになって随分と変わってきた印象を受ける。今では行列のサイズや制約式の数が数百ぐらいの SDP ならば LP 並みの気軽さで解いてしまっても構わない。SDPA 7 や Online Solver も少し宣伝することができた。
コメント
この記事をはてなブックマークに追加

mx ドライバ 1.2.3

2007年10月30日 23時26分58秒 | Weblog
Myrinet-10G の MX ドライバが 1.2.3 になったので入れ換えてみた。netperf を用いてネットワークの速度を測定してみると Gigabit Ethernet の接続では 941.48Mbps(TCP), 956.0Mps(UDP) とかなり 1000Mbps に近い値になっている。MX ドライバ 1.2.2 と 1.2.3 の比較ではわずかながら 1.2.2 の方が有利になっている。それにしても UDP で 8Gbps を越えるのはなかなかの性能だ。スイッチを介さない P2P 接続では 9Gbps を越えるそうだ。

1: Gigabi Ethernet(MTU 9000)

$netperf -H power01 -t TCP_STREAM -C -c -l 60
TCP STREAM TEST from 0.0.0.0 (0.0.0.0) port 0 AF_INET to opt-power01.indsys.chuo-u.ac.jp (10.0.200.1) port 0 AF_INET
Recv Send Send Utilization Service Demand
Socket Socket Message Elapsed Send Recv Send Recv
Size Size Size Time Throughput local remote local remote
bytes bytes bytes secs. 10^6bits/s % S % S us/KB us/KB

87380 16384 16384 60.03 941.48 6.60 8.14 4.597 5.665

$netperf -H power01 -t UDP_STREAM -l 60 -C -c -- -m 8972 -s 1M -S 1M
UDP UNIDIRECTIONAL SEND TEST from 0.0.0.0 (0.0.0.0) port 0 AF_INET to opt-power01.indsys.chuo-u.ac.jp (10.0.200.1) port 0 AF_INET
Socket Message Elapsed Messages CPU Service
Size Size Time Okay Errors Throughput Util Demand
bytes bytes secs # # 10^6bits/sec % SS us/KB

262142 8972 60.00 799128 0 956.0 7.21 4.944
262142 60.00 799102 955.9 8.35 5.727


2: Myrinet-10G (MTU 9000 : mx 1.2.2)

$netperf -H power01m -t TCP_STREAM -C -c -l 60
TCP STREAM TEST from 0.0.0.0 (0.0.0.0) port 0 AF_INET to opt-power01m.indsys.chuo-u.ac.jp (192.168.200.1) port 0 AF_INET
Recv Send Send Utilization Service Demand
Socket Socket Message Elapsed Send Recv Send Recv
Size Size Size Time Throughput local remote local remote
bytes bytes bytes secs. 10^6bits/s % S % S us/KB us/KB

87380 16384 16384 60.19 3397.08 10.90 9.80 2.102 1.891

$netperf -H power01m -t UDP_STREAM -l 60 -C -c -- -m 8972 -s 1M -S 1M
UDP UNIDIRECTIONAL SEND TEST from 0.0.0.0 (0.0.0.0) port 0 AF_INET to opt-power01m.indsys.chuo-u.ac.jp (192.168.200.1) port 0 AF_INET
Socket Message Elapsed Messages CPU Service
Size Size Time Okay Errors Throughput Util Demand
bytes bytes secs # # 10^6bits/sec % SS us/KB

262142 8972 60.00 6985419 0 8356.3 16.65 1.360
262142 60.00 6706036 8022.1 14.60 1.193


3: Myrinet-10G (MTU 9000 : mx 1.2.3)

$netperf -H power01m -t TCP_STREAM -C -c -l 60
TCP STREAM TEST from 0.0.0.0 (0.0.0.0) port 0 AF_INET to opt-power01m.indsys.chuo-u.ac.jp (192.168.200.1) port 0 AF_INET
Recv Send Send Utilization Service Demand
Socket Socket Message Elapsed Send Recv Send Recv
Size Size Size Time Throughput local remote local remote
bytes bytes bytes secs. 10^6bits/s % S % S us/KB us/KB

87380 16384 16384 60.00 3330.11 10.85 9.73 2.136 1.914

$netperf -H power01m -t UDP_STREAM -l 60 -C -c -- -m 8972 -s 1M -S 1M
UDP UNIDIRECTIONAL SEND TEST from 0.0.0.0 (0.0.0.0) port 0 AF_INET to opt-power01m.indsys.chuo-u.ac.jp (192.168.200.1) port 0 AF_INET
Socket Message Elapsed Messages CPU Service
Size Size Time Okay Errors Throughput Util Demand
bytes bytes secs # # 10^6bits/sec % SS us/KB

262142 8972 60.00 6722353 0 8041.5 15.48 1.304
262142 60.00 6502768 7778.9 14.34 1.208
コメント
この記事をはてなブックマークに追加

プリウス

2007年10月30日 00時49分18秒 | Weblog
レンタカーでプリウスを借りて、山、平地、高速、一般道と様々な道を乗る機会があった。走行距離はメータから計測できるが、ガソリンを正確に何リットル使ったかというのはレンタカーだとわかりにくい。走り始めた時点で本当に満タンだったのかがわからないので、結構誤差を含んでいると思うが、標高ほぼ 0 m から高速道路と一般道路を通って、上ったり下りたりしながら標高 700 m 地点まで達して、その後で山を降りて同じく高速道路を通って、標高ほぼ 0 m 地点まで戻り、走行距離はほぼ 120km になった。最後にガソリンを満タンにしたときに 7リットル入ったので推定燃費は120km / 7 ℓ = 17.14km/ℓ になる。普段乗っている車の倍の燃費がありそうだ。おそらく山の上り坂では燃費は相当悪いだろうが、帰りの下り坂ではずっと充電していたはずだ。バッテリー容量を考慮するとずっと下り坂では途中でバッテリーが満タンになってその後は無駄になったはずだ。
高速を 100km/h 程度で走行すると燃費は軽く 20 km/ℓを超える。カタログ値のように 30km/ℓ を超えることは難しいだろうが、これでも普段の車と比較すると 2倍近い燃費になる。
コメント
この記事をはてなブックマークに追加

SDPA 7.0.4

2007年10月29日 03時08分31秒 | Weblog
SDPA 7.0.2 と BLAS ライブラリの組み合わせによっては、途中の反復で実行が止まってしまう現象が発見されたので、終了条件などを一部変更した SDPA 7.0.4 と交代させることにした。

SDPA Online Solver で選択可能なソフトウェアは以下のようになった。
1: SDPA 6.2.1 + GotoBLAS 1.19 + ATLAS 3.7.40 (これはマルチスレッドでも動作するが、Online Solver ではシングルスレッドのみの動作)
2: SDPARA 1.0.1
3: SDPARA-C 1.0.1
4: SDPA 7.0.4 + Intel MKL 9.1.023
5: SDPA 7.0.4 + GotoBLAS 1.19

2 と 3 は MPI 並列、4 と 5 はマルチスレッドで動作する。
コメント
この記事をはてなブックマークに追加

超巨大型地震

2007年10月28日 02時58分57秒 | Weblog
何年か前に図書館で安政地震(たぶん東海地震)の資料を見たことがあるが、専門家の方に聞いたところ、卓袱台で食事したままの恰好で倒壊した家の下敷きになって死亡したケースがあったらしい。つまり箸を置いて逃げる間もなく地震動がやってきたことになり、S 波の第一撃によって家が一瞬で倒壊したと予想される。その様はおそらく地震よりも爆撃のイメージの方が正しいだろう。これでも M8.4 の巨大地震だが、過去には地殻の弾性限界の値を超える本当に破壊的な揺れが起こったと推定されている。その場合では特に断層付近ではいかなる耐震設計も無効になるような事態が起きる可能性がある。

東海地震:5000年に4回「超巨大型」 産総研など調査

 東海地方で過去5000年間に計4回、国内最大級の地震とされる1707年の宝永地震=マグニチュード(M)8.6=を上回る地殻変動を引き起こした未知の巨大地震が起きていたことが、産業技術総合研究所などが中部電力浜岡原発近くで実施したボーリング調査で分かった。この地震は約1000年周期で起きている可能性があり、次の東海地震がこのタイプの地震となって、想定を大幅に上回る被害を出す危険性が浮上した。産総研の藤原治・活断層研究センター研究員によると、ボーリング調査は05~07年に実施。浜岡原発の東約2キロ付近の計8カ所で深さ十数メートルまで掘り、地下の堆積(たいせき)物の年代などを調べた。その結果、約4800年前に大地震が原因とみられる約6.5メートルの地盤の隆起があったことを確認。4000~3800年前にも約2.5メートル、約2400年前にも約3.1メートルの隆起があったことも分かった。さらに、年代は特定できていないものの、この後にも数メートル隆起があったという。
宝永地震や1854年の安政東海地震(M8.4)では、地盤は1メートル前後しか隆起していない。このため、見つかった隆起を起こした地震は、国が想定している東海地震を大幅に上回り、これまで知られていないような巨大な規模だった可能性があるという。藤原研究員は「国の想定とは別タイプの東海地震が1000年周期で起きていると考えられる。今後は隆起量と地震の規模の関連を突き止めることが課題」と話す。

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

アメリカの高校生が学ぶ経済学

2007年10月27日 02時38分15秒 | Weblog
数年振りに経済学のテキストを買って読んでみた。題名はアメリカの高校生が学ぶ経済学で実際にアメリカで高校生が使っている教科書の日本語訳である。サムエルソンの経済学の本など内容が多すぎて普段読んでいる暇がないのでちょうど良いボリュームになっている。理系も含めて経済学の専門家以外にはこの程度の内容で十分ではないかと思う。難しい数式を使わないで分かりやすく解説となっていて、個人的には数式は入っていても構わないが、経済学の入門書で高度な数式を使うよりも概念や仕組みが大事だと思う。日本の政治・経済の教科書と比較すればわかるが、これだけ教科書の質と量に差があれば経済学で勝てるわけがない。中学生のときは経済学志望だったが、そちらの方に行かなくて良かった(多分今の分野の方が向いていると思うので)。
我々のころでは考えられないが、高校生の勉強時間が日米で逆転して今はアメリカの高校生の方が勉強時間が多いと言われている。しかも勉強時間が多い人とほとんどゼロの人に分かれるので平均時間で見てもあまり意味がない。
コメント
この記事をはてなブックマークに追加

SDPARA + GotoBLAS (Intel MKL) その2

2007年10月26日 04時30分26秒 | Weblog
先日の件の続きだが、結局いろいろとやってみて、1 と 2 は同等の性能(問題によっては 1 の方が速い)になって 1 = 2 > 3 という結果になった。

1: SDPARA 本体 → GotoBLAS
ScaLAPACK → GotoBLAS
2: SDPARA 本体 → ATLAS
ScaLAPACK → GotoBLAS
3: SDPARA 本体 → ATLAS
ScaLAPACK → ATLAS

ScaLAPACK が BLAS を呼び出す時は問題のサイズがかなり大きいので、GotoBLAS と ATLAS では差が生じるが、SDPARA 本体から呼び出すときは、それほど大きくないので、GotoBLAS や ATLAS でもほとんど差がない。またマルチスレッドで GotoBLAS を起動したときに ScaLAPACK → GotoBLAS は速くなっても、SDPARA 本体 → GotoBLAS ではかえって遅くなることもある。原因がわかれば前者はマルチスレッド、後者はシングルスレッドで呼び出してもよい。
とは言っても、まだ納得できないことが多いので、これから詳しく中身を調べていくことになる。
コメント
この記事をはてなブックマークに追加

DMA 転送と SIMD 演算

2007年10月25日 04時20分30秒 | Weblog
Cell (と言っても PS3 だが)の DMA 転送と SIMD 演算について、こちらでいろいろとデータを取ってもらっている。幸か不幸か使えるツール(関数)は限定されていてわかりやすいので、次にすべきことは見えてくるが、チューニングが大変面倒。他者のデータも重要だが、実機があるのでまずは自分でデータを取ってみるのが良い。Cell のように DMA 転送を行い、PPE と SPE では別の API を用いて、個別にプログラミングを行う方式は賛否両論あるが、少なくとも Intel はこの方式を次期チップでは採用しないようだ。
Cell では誰かがいろいろとライブラリを作成してくれれば良いと思っているが、それがあると今後はどれだけ最適化されているかが疑問になって、自分で作ったり変更したりしてみたくなる。
コメント
この記事をはてなブックマークに追加

SDP のデータチェック

2007年10月24日 04時00分23秒 | Weblog
SDPA の某開発部署で SDP のデータに誤りがないか(フォーマットや一次独立性など)をチェックするソフトウェアが出来上がった。
まずはデータが SDPA sparse format として正しいかどうかをチェックする。
1: コメント部分
2: ブロック対角行列の記述部分
3: データベクトル
4: データ行列
上記の4つが正しく抽出できれば、以下の確認もできる。
1: 制約条件のデータ行列の一次独立性を調べる(ただしこれは慎重にやらないと危険かもしれない)
2: 制約条件のあるブロックがさらに小さいブロックに分解できるかを調べる。確認できたら、実際に小さいブロックに変換したデータを生成する
3: 行列要素が複数回入力されていないかを調べる

このプログラムは SDPA 本体とどのような関係にするのか悩むところ。とりあえず SDPA Online Solver に入れてみるのがいいかもしれない。
コメント
この記事をはてなブックマークに追加

Ninf-G5

2007年10月23日 03時47分11秒 | Weblog
随分昔にここでも書いたのだが、Ninf-G は通信機構に Globus Toolkit の Globus-IO を用いているので、そのことがユーザに対する普及の妨げの大きな要因になっている。
つまり Ninf-G を使うためには、Globus Toolkit もインストールする必要があるので、そのノードに Global IP を割り当てて多くのポートを外部に対して開ける必要がある。よってプライベート IP の環境では使用できないし、大学の情報基盤センターのような場所でないと昨今の事情を考えると多くのポートを開けることは大変困難である。よって Ninf-1 と比較すると Ninf-G はほとんど使用していない(Ninf に関しては最古参のユーザの一人であることは間違いないが)。そこで現在開発中の Ninf-G Ver.5 ではリモート通信部を通信プロキシと呼ばれる別プロセスにすることで、コア部分を外部ライブラリ非依存になった。つまり Globus Toolkit が無くても利用可になった。
現在では一部性能低下が見られるようだが、いずれ解決されていくだろうし、個人的にはこちらの方が良い。また GridRPC API が OGF の標準化を通ったようだ。
コメント
この記事をはてなブックマークに追加

AIST SOA 仮想クラスタシステム

2007年10月22日 01時14分06秒 | Weblog
AIST SOA 仮想クラスタシステムが安定したら導入してみようと思っているが、そろそろいいのだろうか。何故導入するのかと言われても面白そうだからというのが一番の理由だ。Online Solver で並列計算の指定を受けたら専用の仮想クラスタシステムを作って、そこで並列計算するということを考えたのだが、ディスクあたりに高負荷がかかって結局性能が出ないのではないかという考えもある。昔は SCore を用いていたが、普通にジョブマネージャーを動かした方が効率がいいのかもしれない。

知識循環型サービス主導アーキテクチャ

 産総研では、仮想化技術の活用をさらに一歩進め、データセンターの計算機資源を依頼に応じて柔軟に利用できるようにすることを目標に「AIST-SOA仮想クラスタ管理システム」の開発を進めています。このシステムは、利用者からの依頼に応じて予約ベースで仮想クラスタを構築して提供する機能を実現します。 具体的には、利用者はまずWebインタフェースを使って、利用する計算機資源の量(CPUの個数、メモリー容量、ディスク容量など)と構成情報、その占有時間を指定して予約します。予約開始時刻が近づくと、システムは予約内容に基づいて、VMware Server 1.0またはXen 3.0の仮想計算機、VLAN、iSCSIストレージなど必要な計算機資源を生成して確保した後、OS・アプリのインストールと設定を行って、利用者に提供します。これまでにシステムに必要な要素技術の開発がほぼ完了し、プロトタイプシステムが稼動、 SC|06やComSys2006など国内外の会議でもデモンストレーションを行っています。今後はシステムの完成度を上げ、実用化に向けて実際のデータセンターと協力して実証実験やソフトウェアの改善を行っていく予定です。
コメント
この記事をはてなブックマークに追加

次期固体ロケット

2007年10月21日 02時39分26秒 | Weblog
日本の固体ロケットは M-V が引退しておしまいと勝手に思い込んでいたので、次期固体ロケット構想が進んでいると聞いて正直驚いた。何故日本に固体ロケットが必要なのかは関係者には良く知られていることだが、確かにその目的のためには M-V は少しオーバースペックでもあるし、以下の機能もあった方が良い。また予定のミッションの多くを達成したはやぶさもまだ地球帰還の可能性があるのは凄いことだ。

打ち上げシステムの革新

M-Vロケットの内之浦での打ち上げ準備には手間と時間がかかります。新しい固体ロケットの研究では、単に既存技術を組み合わせるだけでは及ばない打ち上げシステムの革新、世界に冠たる運用性の向上を図ろうと計画しています。例えば、地上設備や打ち上げオペレーションにかかる時間を、M-Vロケットの4分の1程度になるようにコンパクト化。このために、ロケット搭載系の点検は機上で自律的に行い、地上系の手間を省きます。極端に言うと、世界中のどこにいてもネットワークを介してロケットの点検や管制ができてしまう、それもノートパソコン1台でできる、そのような世界をめざしています。射場に依存しない究極の管制システムです。新しい固体ロケットのこうした革新コンセプトは、未来のロケットのお手本になるものです。
コメント
この記事をはてなブックマークに追加

SDPARA + GotoBLAS (Intel MKL)

2007年10月20日 13時17分30秒 | Weblog
SDPARA 1.0.1 から ATLAS に依存した部分の全て取り除いて、GotoBLAS(あるいは Intel MKL)のみをリンクすれば済むように改造した。

1: SDPARA 本体 → GotoBLAS
ScaLAPACK → GotoBLAS
2: SDPARA 本体 → ATLAS
ScaLAPACK → GotoBLAS
3: SDPARA 本体 → ATLAS
ScaLAPACK → ATLAS

普通に考えると 1 > 2 > 3 という順番で高速になるはずなのに、今は 2 > 1 > 3 という順番になっている。多分 SDPARA 本体で ATLAS に依存していた部分の書き換えに少し難があるのではなかろうか。大したことではないので、すぐに解決できると思う(授業、演習の準備、科研費の申請書が終わったらやろう)。
コメント (2)
この記事をはてなブックマークに追加

ブログシステムのバグ

2007年10月19日 13時20分20秒 | Weblog
goo ブログでは --> という記号を本文中に挿入すると表示がおかしくなる。このブログの表示も以下のような今日の記事へのリンクが挿入されている。これはバグのようだ。ちなみに --> をくっつけても -- > スペースを入れて離しても同じようになる。-- と > の間が文字が入れば大丈夫なようだ。
コメント
この記事をはてなブックマークに追加

価格

2007年10月18日 13時07分32秒 | Weblog
科研費の申請のために某有名数理計画問題用の最適化ソルバーの値段をホームページで調べるも、アカデミックライセンスでは大幅に値引きしますとあるだけで具体的な値段が見当たらなかった。交渉次第でかなり値引きしますという親切な話なのだろうが、暫定価格でもいいので書いておいてくれないとこういうときに大変困る。またオープンプライスというのも同様。価格.com 等で調べられれば良いが、Dell のオンラインで全部見積もりできてしまうのが一番良い(これも台数が多くなると交渉次第でもっと下げられるが)。
ちなみに ILOG のアカデミック価格表はこちらにあるとの情報を頂いた。
コメント (2)
この記事をはてなブックマークに追加