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

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

グラフ分割問題に対する SDP 緩和と SDPA-GMP

2010年02月28日 10時09分56秒 | Weblog
応用に役立つ50の最適化問題の 5.4 章(グラフ分割問題に対する SDP 緩和問題)において SDP 緩和問題を SDPA-GMP を用いて解いているが、SDPA ではダメなのか?という質問があった。この問題では SDPA を用いても別に問題は無いと思われるが、以下のように数値精度という点で SDPA-GMP に劣るので、出来れば SDPA-GMP の値の方を使いたい。
SDPA では主問題の最適目的関数値(上界) -1.1972046804133166e-01 > 双対問題の最適目的関数値(下界) -1.2187341887583791e-01 であるが、双対問題の実行可能性の指標(d.feas.error) があまり良くないので、SDPA-GMP の最適目的関数値 -1.1957989287e-01 が SDPA のこの上界と下界の範囲に含まれていない。この点がやはり気になったので、SDPA-GMP の方を用いた。

SDPA 7.3.1
objValPrimal = -1.1972046804133166e-01   <-- 主問題の目的関数値
objValDual = -1.2187341887583791e-01   <-- 双対問題の目的関数値
p.feas.error = +2.2737367544323206e-13
d.feas.error = +2.1173717223987865e-09

SDPA-GMP 7.1.2
objValPrimal = -1.1957989287e-01 <-- 主問題の目的関数値
objValDual = -1.1957989287e-01 <-- 双対問題の目的関数値
p.feas.error = 2.8917634547e-76
d.feas.error = 4.5890565996e-38
コメント (4)
この記事をはてなブックマークに追加

スーパーコンピュータで最短路検索

2010年02月27日 09時55分05秒 | Weblog
中高生の方向けに以下の企画を考えてみました(今年の8月に予定)。コンピュータや数学の応用に興味のある方であれば、多分中学生でも大丈夫だと思います。というよりも公開セミナーに参加してくる中高生の方が、並の理工系大学生よりもやる気、能力、知識で上回っていることが多いです。

"スーパーコンピュータで最短路検索"
スーパーコンピュータと言っても中規模以下のものは研究室でも作れます。スーパーコンピュータの基本に触れてから、全米の道路ネットワークという非常に巨大データを使って、主要な地点間の最短路を高速に計算してみましょう。最短路を求める方法は難しくはないので、そのアルゴリズムとデータ構造についても学習しましょう。
コメント
この記事をはてなブックマークに追加

Fedora 12 と VMware Player 3.01

2010年02月26日 09時52分12秒 | Weblog
VMware Player の 3.0.1 がリリースされたが、やはり Fedora 12 上では以前と同じような現象が発生するようなので、以下のように設定した。理由は良くわからないが、これで一応正常に VMware Player が動作しているようだ。

1: yum install gcc kernel-devel (必要ならば)
2: vmware-modconfig --console --install-all
3: mv /usr/lib/vmware/resources/mozilla-root-certs.crt /usr/lib/vmware/resources/mozilla-root-certs.crt.old
コメント
この記事をはてなブックマークに追加

地震とマンション

2010年02月25日 01時18分50秒 | Weblog
地震とマンションという本が2000年に出版された。また改めて読み返してみたのだが、絶版になったのが大変惜しい本である(中古品は簡単に入手可能)。一方 2006 年に出版された本でマンションの地震対策という本があるが、こちらの中では前述の地震とマンションという本の中身にも触れられているので、参考にした点も多かったと思われる。簡単に論点をまとめると、以下のようになる。
1:大型の地震時にも一般住宅と比べるとマンション内での死傷者はかなり少ない。
2:RC(鉄筋コンクリート)の建物の中でも、比較的な単純な構造を持ち、広い部屋が少ないマンションの方が、商業ビルやオフィスビルよりも一般的には地震に強い
3:上の階の方が揺れやすいが、かかる重さが少ないので壊れにくい
4:新耐震基準(1981年以降)で立てられたマンションは崩壊、大破することはほとんどないが、中破以下の被害は結構多い
5:大破したマンションでも修復できる場合がある
6:古いマンションでも耐震補強を行うことによって、地震の被害を減らすことができる
7:液状化現象は地盤改良によって、かなり防ぐことはできる
8:中層以下のマンションは固有周期が短いので、長周期振動に関する心配はほとんどない
戦前に建てられたRC造の建築物で現存しているものは、非常に柱や梁も太くて素人目にも地震に強そうな感じがする(東工大の本館など)。一方、最新の建築の方が基準ぎりぎりで建てているせいか、どうしても華奢な感じを受けてしまう。
コメント
この記事をはてなブックマークに追加

高校数学

2010年02月24日 10時02分36秒 | Weblog
入試の採点を行うときに、まず自分でも解いたみたが、合格点を取るのではなく、模範解答(つまり満点の解答)を作るのは大変難しい。予備校などが出している解答も必ずしも満点ではないらしい(特に証明に関して)。また、解き方が高校数学の範囲を超えていても数学的に正しければ良いので、模範解答以外の別解も多く、結構苦労した。最適化問題に限らないが、数学的な諸問題に対して適切なアルゴリズムとデータ構造を考案して実装を行うには、やはり数学の知識、能力も重要であり、高校数学のレベル(これでも十分高いが)は押さえておくべきだと実感した。
コメント
この記事をはてなブックマークに追加

Windows 7 Ultimate 64bit とノートパソコン

2010年02月23日 09時51分48秒 | Weblog
CPU が Atom では非力すぎるので、少し性能が上の Celeron T1700(1.83G) 搭載のノートパソコンを購入したら、Windows 7 Ultimate 64bit がインストールされていた。DSP 版でも 22,280 円ぐらいはするので、ノートパソコンの価格が 69,107 円であることを考えると OS が占める価格が異様に大きい。
あとのスペックは 画面のサイズ 17inch, メモリ 4GB, HDD 320GB であって、OS 価格を引いた残り 45,000 円程度で済んでいることを考えるとかなり安い。安さには何か秘密があるかもしれないので、しばらく使用してみないとわからない。
コメント
この記事をはてなブックマークに追加

ソフトウェアは既存のものを使っただけです

2010年02月22日 01時50分42秒 | Weblog
現在審査している論文を始めとして、最適化問題の定義 → 定式化 → ソフトウェアの結果 → 考察というパターンを良く見かけるのだが、いくら自分でソフトウェアを作らないからとは言っても、これはちょっと悪いパターンだ。別の論文を見ると、少し良くはなっているのだが、やはり計算機環境、最適化問題のサイズや実行時間等が書かれていない。
ソフトウェアに関する部分が完全にブラックボックス化されているが、自分で作成したソフトウェアではないので、実際に定式化した問題が解けるかどうかはわかりません(作った人に聞いてくれということ)という答えが帰ってくる。定式化までが自分の仕事で、その後に実際に解けるかどうかは自分の責任ではないと思っている人も多いのではないだろうか。
コメント (3)
この記事をはてなブックマークに追加

Handbook of Semidefinite Programming の続編

2010年02月21日 23時12分03秒 | Weblog
Handbook of Semidefinite Programming という 2000 年に発行された半正定値計画問題(SDP)のハンドブックがあり、SDP の世界では非常に有名な書籍になっている。ゼミ等で使用している研究室も多いだろう。ただし、すでに発行から10年が経過して古くなっているので、ハンドブックの新版を作る計画がある。
ソフトウェアに限定しても 10 年前と今では段違いの性能差があるので、その辺の取り上げられることになるが、今度はソフトウェアとアプリケーションにも力が入れられるようである。
コメント (2)
この記事をはてなブックマークに追加

yum で落ちる Nehalem-EP マシン

2010年02月20日 23時01分53秒 | Weblog
以下の Nehalem-EP 搭載の PowerEdge R710 だが、最近 OS が落ちまくっている。yum コマンドでディスクアクセスを行うときに落ちる確率が高い。以前はこのような現象は無かったのだが、思い当たる原因?としては、BIOS で VT 機能を ON にしたぐらいしかない。とは言っても VT を ON したぐらいで落ちる理由はわからない。

○PowerEdge R710
CPU : Intel Xeon 5550 (2.66GHz) x 2 :
メモリ 72GB
OS : Fedora 12 for x86_64
コメント
この記事をはてなブックマークに追加

SCOPE 2009年度 第5回研究会

2010年02月19日 14時27分07秒 | Weblog
開催が一週間後に迫りましたので、再掲載します。大勢の方の参加をお待ちしております。夜はいつものように懇親会も予定しています。また、正式決定ではないですが、今年の SCOPE つくば合宿は例年よりも1ヶ月程度遅くなりまして、6月26、27日の予定です(ワールドカップの日本の試合も避けています。すでに負けそうですが)。

2009年度 第5回研究会
日 時 : 2010年02月27日(土)14:00~
会 場 : 中央大学 後楽園キャンパス 6号館4階 6410号室

講演者:渡部大輔 (東京海洋大学 海洋工学部流通情報工学科)
講演題目:一般化Weberモデルによる航空貨物ハブ施設配置の最適化
講演概要:本研究では、航空貨物輸送における輸送費用の変化が単一のハブ空港配置に与える影響について、輸送距離と輸送量をべき関数として一般化したウェーバー問題を用いて考察する。まず、一次元・二次元の規則的な点配置における輸送費用関数の変化による最適配置の分析を行う。さらに、東アジアにおける航空貨物の輸送を対象に分析を行い、各国の航空運賃から推定したパラメータにより、同じ需要分布でも異なる最適配置の結果が得られた。

講演者:小林和博 (海上技術安全研究所 物流研究センター)
講演題目:船舶スケジューリングと船の最短路問題
講演概要:船舶スケジューリングは、複数の荷物を運搬するための最も効率のよい船舶の運航スケジュールを求める問題である。数理的構造はVehicle Routing Problem(VRP)と同じであるが、船舶および港湾の運用上の特徴により、有効な解法が陸上のVRPとは異なる. 本発表では集合被覆問題と列生成によるヒューリスティックな解法を紹介する。船の最短路問題では、出発港から目的港までの航路の選定を、制約付き2目的最短路問題に定式化する。この問題に対して、ロバスト性をもつ解を与える計算方法について報告する。
コメント
この記事をはてなブックマークに追加

Pthread v.s. OpenMP その2

2010年02月18日 00時54分38秒 | Weblog
昨日の実験を他のマシンでも行ってみたが、現在の実装方法では基本的に以下の通り。

1: gcc 4.1.2 と 4.4.3 では性能差はほとんどない
2: Pthread と OpenMP の性能差はあまり大きくない
3: インテルコンパイラは gcc よりも性能が高い(Pthread でも OpenMP でも同じ傾向になる)

いつも上記のようになるわけではない。例えば以前行った以下のブログなどを参考にしていただきたい。

OpenMP の性能: gcc と Intel Compiler
コメント
この記事をはてなブックマークに追加

Pthread v.s. OpenMP

2010年02月17日 23時12分29秒 | Weblog
プログラムをマルチスレッド化するときに、Pthread を使うか、OpenMP を使うか迷うところで、OpemMP を用いると簡単にマルチスレッド化できるが、細かい制御があまり出来ないようなイメージがある。しかし、Pthread 風に thread function を作っておいて、その関数を for 文で包んでから

#pragma omp parallel for schedule(static)

とすると、結構いろいろな制御を行うことができる。以下で Pthread と OpenMP の性能比較を行う。gcc 4.1.2 の OpenMP の性能は一般的には良くないのだが、作り方に依存する面も大きいので、以下のように Pthread と OpenMP の性能差がほとんど無いということもある。

---------------------------------------------------------------
○最適化ソフトウェア : 最短路ソルバー msp Ver. 0.21

○計算サーバ
CPU : Intel Xeon 5460 (3.16GHz / 6MB L2 x 2) x 2
Memory : 48GB (12 x 4GB)
gcc : 4.4.3 (デフォルトは 4.1.2)
Intel コンパイラ : 11.1.064
OS : CentOS 5.4 for x86_64

○最短路問題 LKS 1000 クエリ
1: gcc 4.1.2
pthreads: 31.359s
openmp: 34.956s

2: gcc 4.4.3
pthreads: 31.472s
openmp: 34.939s

3: icc 11.1.064
pthreads: 28.198s
openmp: 30.976s
コメント (5)
この記事をはてなブックマークに追加

クラウド関係のセミナー

2010年02月16日 15時16分39秒 | Weblog
クラウド関係のセミナーの案内が幾つか来ましたので、紹介しておきます。

AMD Opteron(TM) プロセッサではじめる仮想化・クラウド」セミナー

https://reg.amd.jp/public/seminar/view/48

事例とデモでわかる!プライベート・クラウド構築セミナー
http://www-06.ibm.com/systems/jp/saiteki/event/pcloud03/

ついでに IBM Academic Initiative のリンクも貼っておきます(クラウドとは直接関係無いですが)。
コメント
この記事をはてなブックマークに追加

理論計算量と実際の計算性能

2010年02月15日 11時09分33秒 | Weblog
詳しくは添付の図を見ていただくとして、全米データでは 点数 n = 2400 万点, 枝数 m = 5800 万枝なので、優先キューなどを用いない原始的なダイクストラ法では計算量が O(n^2) になって、2400 万の二乗で計算量が計上される。一方、例えば 2-heap を用いたダイクストラ法の計算量は O(m log n) であるが、n = 23,947,347 でも log n = 約17 にしかならないので、実際には m (枝数) によって計算量が決定される。道路データでは点は交差点を表す場合が多いが、点の次数(つまり交差点に接続している道路)は多くても4程度なので、グラフはかなり疎になる(つまり n^2 >> m となる)。
ただし、理論計算量(最悪時想定)が小さい方が、ソフトウェアの性能においても上回るとは限らない。それは以下のような原因が考えられる。
1:最悪の場合はめったに起こらない
2:実装が悪い(そもそも実装を真面目にやる気がない)
3:定数項が予想以上に大きい
4:比較演算のコスト(分岐予測のミス)が大きい、スワップ操作の多用(書き込みと読み込みの連続)、演算とメモリ操作の混同による計算量推定。
よくある質問で、問題が非常に大きくなれば理論計算量が少ない方が結局は勝つ(速い)というものがあるが、必ずしもそうとは言い切れない。
1:計算機で扱える問題の大きさの範囲では、定数項の影響が非常に大きい場合が多い
2:上記の4のように、理論計算量の値が実際の計算性能を正確に反映していない場合がある。
我々もいろいろな事例で確認しているが、現在の計算機上で有名なアルゴリズムとデータ構造がどういった特性を示すのか調べてみると面白い。
コメント (2)
この記事をはてなブックマークに追加

仮想マシン

2010年02月14日 14時11分17秒 | Weblog
現在、様々なイメージファイルを用意して仮想マシンを多用している。用途は以下のようになる。
1:SDPA などのサポートのため(動作確認、デバッグ)
2:スパコンなどは実際に借りて使うと課金されるので、仮想マシンでほぼ同じ環境(OS, コンパイラ)を作って、開発やデバッグを行う
3:単なる趣味(Windows 95, BeOS, Chrome OS 等)。今度は OS/2 Warp V4 の仮想マシンが欲しい。
欠点は性能が実マシンに対して落ちることと、ノートパソコンで使うとバッテリの減り具合が激しいこと。
コメント
この記事をはてなブックマークに追加