最短路問題とクエリファイル

最短路問題のプログラムを用いて実験を行ったが、プログラムの方は変更せずにクエリファイルだけを少しだけ加工してみた。

○計算サーバ
CPU : AMD Opteron 8439 (2.80GHz / 6MB L3) x 4
Memory : 128GB (32 x 4GB / 800MHz)
gcc : 4.4.2
OS : Fedora 12 for x86_64

HT Assist を ON にした方が良さそうだが、リモートでは変更できないので、OFF のまま使うことにする。また使用する問題は以下の CTR でクエリ数は１０００とする。
http://opt.indsys.chuo-u.ac.jp/portal/sp/G-G/sp_graphic.php?state=CTR

1: time numactl -i all --physcpubind=0,1,2,3,4,5,6,7,8,9,10,11 ./spp-solve ../../mmap/CTR-d.m-gr ../../query/CTR1000.p2p
real 5m22.781s

2: time numactl -i all --physcpubind=0,1,2,3,4,5,6,7,8,9,10,11 ./spp-solve ../../mmap/CTR-d.m-gr ../../query/CTR1000-1.p2p
real 5m22.099s

3: time numactl -i all --physcpubind=0,1,2,3,4,5,6,7,8,9,10,11 ./spp-solve ../../mmap/CTR-d.m-gr ../../query/CTR1000-2.p2p
real 5m21.466s

性能向上は少しだけではあるが、クエリファイルの処理方法によって改善の余地がまだまだありそうだ。

MPACK 0.6.4 その１

MPACK の 0.6.4 が登場していたので、0.6.0 と同じように make を行ってみた。

○環境１
CPU : Intel Xeon 5550 (2.66GHz / 8MB L3) x 2
Memory : 72GB (18 x 4GB)
gcc : 4.4.2
OS : Fedora 12 for x86_64

デフォルトで GMP 4.3.1 がインストールされているので、これを用いることにする。qd-2.3.7 は /usr/local/qd/lib にインストールした。また GotoBLAS2 は 1.09 を用いた。

./configure --with-qd-includedir=/usr/local/qd/include/ --with-qd-libdir=/usr/local/qd/lib/ --with-blas="-lgoto -lgomp" --with-lapack="-lgoto -lgomp -lgfortran"
make

このように configure & make を行って、何の問題もなく終了した。
ただし、SDPA-GMP 7.1.2 を作るときに 以下のように configure してみたが、新しい MPACK がリンクされないようだ。

./configure --with-mpack-includedir=/usr/local/include --with-mpack-libdir=/usr/local/lib

SCOPE 研究会(2009年度第5回, 2010年度第1回) : 確定

以下のように SCOPE 研究会を開催致します。夜には懇親会も予定しておりますので、多忙な時期ではございますが是非ご参集下さい。

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

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

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


2010年度 第１回研究会
日　時 ： 2010年03月27日（土）14:00～
会　場 ： 中央大学 後楽園キャンパス 6号館4階 6410号室

講演者：佐藤仁 (東京工業大学 学術国際情報センター)
講演題目： 大規模データ処理と最適化
講演概要：近年、科学技術計算において大量のデータに対する解析処理が広く行われている。多くの場合、このような処理は、スーパーコンピュータやクラウドのような大規模並列計算環境で行われるが、効率的に計算資源を利用するためには、最適化技術が不可欠である。この講演では、大規模並列計算環境でのデータ処理における最適化技術の応用事例として、複製配置を0-1整数計画問題としてモデル化したファイル複製配置最適化システム、及び、仮想マシンの移動を最短経路問題としてモデル化した大規模データアクセスの高速化技術、について紹介する。

講演者：竹房あつ子 (産業技術総合研究所 情報技術研究部門)
講演題目： 性能を保証する分散実行環境のためのコアロケーション手法
講演概要：グリッドとネットワーク資源管理技術により，複数の組織にある計算機やストレージなどの資源と広帯域ネットワークを必要に応じて組み合わせ，性能が保証された仮想的な利用環境を構築することが可能になった．この際，利用者の要求する計算機性能や通信帯域を保証しつつ，利用価格や資源の有効利用など，利用者や資源管理者の方針を考慮して，適切に資源を割り当てる（コアロケーション）必要がある．さらに，利用者の資源要求に対して即座に処理するためには，コアロケーションに要する時間も課題となる．
本研究では，資源が事前予約で複数の組織から提供されることを前提とし，利用者や資源管理者の方針が反映可能なコアロケーション手法を提案する．提案手法では，分散する計算機群とその間のネットワークのコアロケーションを最適化問題にモデル化し，複数の予約プランを作成して適切な資源群を確保する．評価では，コアロケーションの求解時間を制約条件とソルバの違いにより比較し，実用化に向けて議論する．
　

全米最短路 256 クエリによるベンチマークテスト

最短路のプログラム(msp-0.21)を用いて、全米データから 256 クエリ(始点と終点が 256 組)の最短路を求める時間を各マシンで測定した。1 クエリは 1 スレッドで計算するが、各マシンでは同時にコア数だけスレッドを立ち上げて 256 クエリを並列に処理する。よって、単に各コアの性能だけでなくコア数が多い方が有利になる。OS は マシン 5 と 8 が Fedora 11, マシン 10 が Momonga 6.1 であり、残りのマシンは全て Fedora 12 になる。コストパフォーマンスでは 4 コアグループが良さそうである。

○ 多数コア(8コア以上)グループ
1: AMD Opteron 8439SE 2.8GHz : 24 コア　→　1m29.348s

2: Intel Xeon X5550 2.66GHz : 8 コア　→　1m47.051s

3: Intel Xeon X5460 3.16GHz : 8 コア　→　1m59.272s

4: AMD Opteron 2435 2.6GHz : 12 コア　→　2m1.650s

○ 4 コアグループ
5: Intel Core i7 965 3.2GHz : 4 コア　→　2m34.942s

6: Intel Core 2 Quad 9650 3.0GHz : 4 コア　→　3m9.845s

7: AMD Phenom2 X4 955 3.2GHz : 4 コア　→　3m47.702s

8: AMD Phenom 9950 2.6GHz : 4 コア　→　5m45.394s

○ 少数コア(2 コア以下)グループ
9: AMD Opteron 240 1.6GHz : 2 コア　→　17m37.009s

10: Intel Pentium 4 3.0GHz : 1 コア　→　28m15.831s

11: Intel Atom 330 1.6GHz : 2 コア　→　31m28.811s

12: VIA Nano L2200 1.6GHz : 1 コア　→　42m6.397s

Yellow Dog Linux 6.2 と PS3

PS3 用の Linux である Yellow Dog を 6.1 から 6.2 にバージョンアップした。とは言ってもハードウェアは同じなので、性能については以下の内容を参考にしていただきたい。

Yellow Dog Linux 6.1 と PS3

Cell の今後は見えにくくなっているが、PS4 には搭載される可能性もありそうだ。HPC の分野で Cell に当初期待したような成果はなかなか得られそうもない。

IBM have not stopped Cell processor development

Mac OS X 10.6 (Snow Leopard) で SDPA

Mac OS X での SDPA のインストール＆実行が面倒でわかりにくいという意見や質問をたまに頂くので、自分でも試してみた。

MacBook Pro
CPU : 2.53GHz Intel Core 2 Duo
メモリ : 4GB
OS : Mac OS X 10.6 (Snow Leopard)

手順は確かに複雑だったので簡単に記す。デフォルトは gcc 4.2.1 で gfortran も無いので、fink で gcc(g++, gfortran) 4.4.1 インストールする。

1: Xcode のインストール
2: fink の構築とインストール
3: apt-get install libgettext3-dev=0.14.5-2
4: fink install gcc44
5: BLAS の構築
6: SDPA の構築

同じ CPU のマシンが無いので、一番性能が近いマシンを使って SDPA の性能差を比較する。クロック周波数の差を考慮しても CentOS(Linux)の方が速めになる。

自作 PC
CPU : Intel Core 2 Duo E8200 2.66GHz
メモリ : 4GB
OS : CentOS 5.4 for x86_64
gcc : 4.4.2

○ソフトウェア SDPA 7.3.2β + GotoBLAS2 1.09 + MUMPS 4.9.2
○ OMP_NUM_THREADS=2

問題１：mcp500-1.dat-s
MacBook Pro : 3.747s
自作 PC : 2.711s

問題２：theta6.dat-s
MacBook Pro : 38.748s
自作 PC : 34.104s

10U ブレードエンクロージャー

３月末にはいよいよ Intel Nehalem-EX 搭載のサーバが発売されるようで、4U の大きさでも 4-way(4CPU) ＆最大メモリ 1TB というサーバも予定されている。今の SDPA クラスタは PowerEdge 2900(5U) x 16台で合計 80U を使用している。80U で 16ノード, 32CPU, 128 コアになっているのだが、以下の 10U ブレードエンクロージャーには、ハーフハイト（高さ 5U)のブレードが 16 枚搭載することができる。

http://www1.jp.dell.com/jp/ja/hied/servers/pedge_m1000e/pd.aspx?refid=pedge_m1000e&s=hied&cs=jphied1

ブレード内には 2CPU を搭載できるので、CPU が Nehalem-EX だと仮定すると、16 ブレード x 2 CPU x 8 コア = 合計 256 コアになるので、10 U (現在の 1/8 のスペース)で、コア数で２倍も搭載できることになる。
Dell ではないが GPGPU カード (Fermi) を複数枚（４枚以上？）搭載できるraラックマウントサーバも発表されるらしい。

VMware と KVM と Hyper-V

1個の Xeon を搭載したサーバを１台購入して、Windows Server 2008 R2 を導入することにした。Hyper-V の使用が主目的になるが、仮想マシン上で Windows を使用する気はあまり無いので Linux の動作を予定している。
また、以前もこちらで報告したように KVM や VMware 上では最短路のプログラムはあまり性能低下は見られないが、SDPA だと仮想マシン上では 20 % 程度遅くなってしまうことがある。両者ともマルチスレッドで動作しているのだが、最短路のプログラムでは１個の経路探索は 1 スレッドで計算しているのに対して、SDPA では 1 個の行列計算をマルチスレッドで行っていることにも原因があるのだろう。

IEEE Multi-Conference on Systems and Control (MSC)

2010 IEEE Multi-Conference on Systems and Control (MSC) という国際会議が開催されます。まだ公表は出来ないのですが、要請もありましたので最適化分野の人として何らかの形でこの国際会議に関わる予定です。制御分野というのは以前から工学系では最も高度な数学を使う分野の一つとして知られています。制御系の分野の方が大きな興味を持っている内容としては、半正定値計画問題(行列補完も含む)や多項式最適化などがあるようです。少し前はロバスト最適化も注目されていたようですが、現在の状況はわかりません。

SCOPE 研究会の今後の予定 １月２２日午後９時更新

SCOPE 研究会の講演等について情報を更新しました。詳しくは以下のリンク先をご覧下さい。

http://blog.goo.ne.jp/scope_or/

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

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

講演者：小林和博 (海上技術安全研究所 物流研究センター)
講演題目： 未定
講演概要： 未定


2010年度 第１回研究会
日　時 ： 2010年03月27日（土）14:00～
会　場 ： 中央大学 後楽園キャンパス 6号館4階 6410号室

講演者：佐藤仁 (東京工業大学 学術国際情報センター)
講演題目： 大規模データ処理と最適化
講演概要：近年、科学技術計算において大量のデータに対する解析処理が広く行われている。多くの場合、このような処理は、スーパーコンピュータやクラウドのような大規模並列計算環境で行われるが、効率的に計算資源を利用するためには、最適化技術が不可欠である。この講演では、大規模並列計算環境でのデータ処理における最適化技術の応用事例として、複製配置を0-1整数計画問題としてモデル化したファイル複製配置最適化システム、及び、仮想マシンの移動を最短経路問題としてモデル化した大規模データアクセスの高速化技術、について紹介する。

講演者：竹房あつ子 (産業技術総合研究所 情報技術研究部門)
講演題目： 性能を保証する分散実行環境のためのコアロケーション手法
講演概要： グリッドとネットワーク資源管理技術により，複数の組織にある計算機やストレージなどの資源と広帯域ネットワークを必要に応じて組み合わせ，性能が保証された仮想的な利用環境を構築することが可能になった．この際，利用者の要求する計算機性能や通信帯域を保証しつつ，利用価格や資源の有効利用など，利用者や資源管理者の方針を考慮して，適切に資源を割り当てる（コアロケーション）必要がある．さらに，利用者の資源要求に対して即座に処理するためには，コアロケーションに要する時間も課題となる．
本研究では，資源が事前予約で複数の組織から提供されることを前提とし，利用者や資源管理者の方針が反映可能なコアロケーション手法を提案する．提案手法では，分散する計算機群とその間のネットワークのコアロケーションを最適化問題にモデル化し，複数の予約プランを作成して適切な資源群を確保する．評価では，コアロケーションの求解時間を制約条件とソルバの違いにより比較し，実用化に向けて議論する．


2010年度 SCOPE つくば合宿
2010年6月後半の土日 筑波大学
新企画考案中！！

SCOPE 研究会の今後の予定

SCOPE 研究会の今後の予定について記しておきます。予定でありますので、現時点では以下の全てが確定しているわけではございません。

2009年度 第５回研究会
2010年 2月27日(土) 中央大学理工学部

2010年度 第１回研究会
2010年 3月27日(土) 中央大学理工学部

2010年度 SCOPE つくば合宿
2010年6月後半の土日 筑波大学

Chrome OS その２

VMware player の設定において Network Adapter の設定を NAT にすると以下のような現象が発生するが、Bridged にすると図のように正常に最短路オンライン・ソルバーも動作する。OS 自体にはそれほど多くの機能は含まれていないが、クラウド端末としての機能は果たせるだろう。

-----------------------------------------------------------------------
Google の Chrome OS の VMware 仮想マシンのイメージファイルを入手して VMware Player でいろいろと試してみた。Chrome OS にいろいろとインストールしようとしたが、とりあえず無理そうなので Chrome のブラウザで最短路オンライン・ソルバーを使ってみたが、何故か opt.indsys.chuo-u.ac.jp から 133.91.122.126 の変換が出来ないので、画像のように IP 直打ち(http://opt.indsys.chuo-u.ac.jp/portal/)で入れてみたところ多少変だが実行は出来た。ちなみに Google Map を用いた最短路オンライン・ソルバーの実行は出来ない。

新企画

気軽に読めて、しかも中身のレベルも実は結構高いという入門書があまり無いのが以下の分野なので、新しい企画を考えています。著者にお聞きしたところ CUDA の入門書は結構売れているようなので、需要は大きいのではないかと思います。英訳なども考慮に入れておく必要があります。

１： スーパーコンピュータ
２： GPU コンピューティング
３： オペレーションズ・リサーチ

３の需要は本当にあるのかなと思いますが、日本で無くても海外ではあるのかもしれません。

KVM と VMware Player その４

前回の比較を行った後で、仮想マシンではないネイティブな環境での実行結果が無いことに気が付いたので追加をしておく。意外と仮想マシン上での性能は良かった。

ソフトウェア : sp_solve
ホストOS : Fedora 12 for x86_64
ゲストOS : Debian 5.0.3 for x86_64
仮想化環境１ : KVM(QEMU) 0.11
仮想化環境２ : VMware Player 3.0
ホストマシン : Core i7 860 2.8GHz, メモリ 8GB
スレッド数：４個

問題１： NY 1000クエリ
KVM : 5.617s
VMware : 5.543s
Native : 4.687s

問題２ : FLA 1000 クエリ
KVM : 21.500s
VMware : 21.598s
Native : 20.596s

問題３ : LKS 1000 クエリ
KVM : 63.323s
VMware : 61.147s
Native : 57.226s

SDPA 内部のマルチスレッド化 その６

以下の Istanbul 搭載のサーバで HT Assist を切るのを忘れていたので、BIOS の設定を変えて再実験を行った。このマシンでは 24 コアあるのだが、使用するのは 16 コア程度にしておいた方が性能が良い場合がある。これについてはまた別の機会に報告したい。

ソフトウェア
○: SDPA 7.3.2β : GotoBLAS2 1.09 + MUMPS 4.9.2

○計算サーバ１
CPU : AMD Opteron 8439 (2.80GHz / 6MB L3) x 4
Memory : 128GB (32 x 4GB / 800MHz)
gcc : 4.4.2
OS : Fedora 12 for x86_64
環境変数 : OMP_NUM_THREADS = 24

○計算サーバ２
CPU : Intel Xeon 5550 (2.66GHz / 8MB L3) x 2
Memory : 72GB (18 x 4GB / 800MHz)
gcc : 4.4.2
OS : Fedora 12 for x86_64
環境変数 : OMP_NUM_THREADS = 8

●問題１ : FH2+.1A1.STO6G.pqgt1t2p.dat-s
計算サーバ１ HT Assist ON : 66.1s(30回) 24スレッド
計算サーバ１ HT Assist OFF : 70.3s(30回) 24スレッド
計算サーバ２ : 96.4s(30回) 8 スレッド

●問題２ : mcp2000-01.dat-s
計算サーバ１ : HT Assist ON : 95.9s(16回) 24スレッド
計算サーバ１ : HT Assist OFF : 89.8s(16回) 24スレッド
計算サーバ２ : 46.2s(16回) 8 スレッド

●問題３ : thetaG51.dat-s
計算サーバ１ : HT Assist ON : 118.8s(28回) 24スレッド
計算サーバ１ : HT Assist OFF : 98.0s(28回) 24スレッド
計算サーバ２ : 83.6s(28回) 8 スレッド

問題１のように F3 式の計算が多くを占める場合には、HT Assist を OFF にすると遅くなるようだ。