MIP ソルバーに関する数値実験 その３

仮想マシンのマイグレーションに関する最適化問題(MIP)を様々な MIP ソルバーで解いている。Gurobi 3.0.1 と CPLEX 12.2 及び ParaSCIP 1.2.1.2？ では以下の上界と下界を求めることができるのだが、他の MIP ソルバー (Cbc 2.5, lp_solve 5.5.2.0, GLPK 4.44)では出来なかった（少なくとも１時間以内では）。

上界： 462
下界： 385

ParaSCIP は SCIP の MPI 並列版だが、MPI をインストールすれば 1 サーバでも稼働させることができる。以下の計算サーバでは ParaSCIP を 24 プロセスを動作させている。

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

top - 00:27:56 up 2 days, 22:29, 2 users, load average: 24.20, 24.16, 24.09
Tasks: 402 total, 25 running, 377 sleeping, 0 stopped, 0 zombie
Cpu(s): 99.2%us, 0.7%sy, 0.0%ni, 0.0%id, 0.0%wa, 0.0%hi, 0.1%si, 0.0%st
Mem: 132359900k total, 58692708k used, 73667192k free, 265492k buffers
Swap: 134217724k total, 0k used, 134217724k free, 1888904k cached

PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
17545 fujisawa 20 0 2546m 2.2g 6340 R 100.2 1.7 100:24.66 parascip
17530 fujisawa 20 0 1977m 1.6g 6732 R 99.8 1.3 100:40.50 parascip
17534 fujisawa 20 0 2206m 1.8g 6600 R 99.8 1.5 100:38.05 parascip
17541 fujisawa 20 0 2659m 2.3g 6764 R 99.8 1.8 100:36.11 parascip
17542 fujisawa 20 0 2687m 2.3g 6608 R 99.8 1.9 100:43.64 parascip
17543 fujisawa 20 0 2620m 2.3g 6536 R 99.8 1.8 100:31.34 parascip
17549 fujisawa 20 0 3206m 2.8g 6452 R 99.8 2.2 100:40.24 parascip
17551 fujisawa 20 0 2720m 2.4g 6452 R 99.8 1.9 100:25.29 parascip
17552 fujisawa 20 0 2814m 2.5g 6404 R 99.8 1.9 100:14.88 parascip
17553 fujisawa 20 0 317m 35m 6928 R 99.8 0.0 101:07.44 parascip
17535 fujisawa 20 0 2349m 2.0g 6616 R 99.5 1.6 100:23.91 parascip
17548 fujisawa 20 0 2002m 1.7g 6396 R 99.5 1.3 100:47.48 parascip
17550 fujisawa 20 0 3200m 2.8g 6268 R 99.5 2.2 100:26.27 parascip
17531 fujisawa 20 0 2542m 2.2g 6848 R 99.2 1.7 100:34.17 parascip
17536 fujisawa 20 0 3186m 2.8g 6472 R 99.2 2.2 100:33.29 parascip
17538 fujisawa 20 0 2454m 2.1g 6548 R 99.2 1.7 100:13.75 parascip
17540 fujisawa 20 0 2581m 2.2g 6628 R 99.2 1.8 100:30.62 parascip
17533 fujisawa 20 0 2071m 1.7g 6860 R 98.8 1.3 100:43.28 parascip
17539 fujisawa 20 0 2229m 1.9g 6600 R 98.8 1.5 100:30.01 parascip
17546 fujisawa 20 0 2393m 2.1g 6128 R 98.8 1.6 100:39.35 parascip
17544 fujisawa 20 0 2803m 2.5g 6252 R 98.5 1.9 100:19.72 parascip
17547 fujisawa 20 0 3000m 2.6g 6308 R 98.5 2.1 100:33.37 parascip
17532 fujisawa 20 0 2178m 1.8g 6804 R 98.2 1.4 100:39.52 parascip
17537 fujisawa 20 0 2929m 2.6g 6724 R 97.9 2.0 100:15.83 parascip

MIP ソルバーと CPU のアフィニテイ

MIPソルバー(ppscip と parascip)を用いて CPU のアフィニティの設定をいろいろと調べている。以下の結果からはこの MIP ソルバーに対しては敢えて設定を行うメリットは見当たらない。

ppscip (scip の pthread 並列版：LP ソルバーは soplex を用いる) : 24スレッド

○問題 nw04.mps
1: numactl -i all --physcpubind=0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23：7m10s
2: 設定無し：5m49s
○問題 air06.mps
1: numactl -i all --physcpubind=0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23：1m21s
2: 設定無し：1m20s

parascip (scip の MPI 並列版 : LP ソルバーは CPLEX を用いる) : 24 プロセス
○問題 nw04.mps
1: numactl -i all --physcpubind=0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23：4m39s
2: 設定無し：4m41s
○問題 air06.mps
1: numactl -i all --physcpubind=0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23：1m18s
2: 設定無し：1m17s

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

13日午後にサーバ一時停止

新クラスタ計算機増設のために 200V の電源及びコンセント設置工事を行うことになりました。１３日の午後、一時的に研究室のWeb サーバ及びクラスタ計算機が停止します。なるべく Web サーバの方は停止させないで工事を行いたいと思います。

SDPARA と CPU のアフィニテイ その３

またまた前回の続きで今度は 32 MPI x 4 Pthread の結果も追加した。

A: 0-1-2-3-4-5-6-7 (16 MPI x 8 Thread)
B: 0-4-2-6-1-5-3-7 (16 MPI x 8 Thread)
C: 0-4-2-6 & 1-5-3-7 (32 MPI x 4 Pthread)

どの設定が最速になるのかは、もちろん問題に依存するが、問題の特性を見ることによって事前に判断ができそうだ。

○問題１：NH.3Sigma-.DZ.pqgt1t2p.dat-s
A: 72m1s
B: 71m29s
C: 84m54s
○問題２：nug18_r2.dat-s
A: 45m6s
B: 43m35s
C: 41m37s

○ SDPA クラスタ
16 Nodes, 32 CPUs, 128 CPU cores;
CPU : Intel Xeon 5460 3.16GHz (quad cores) x 2 / node
Memory : 48GB / node
NIC : GbE x 2 and Myrinet-10G x 1 / node
OS : CentOS 5.5 for x86_64

ロットサイズ決定問題と最短路問題

こちらの OR Wiki にも解説されているように、ロットサイズ決定問題は最短路問題に変換して解くことができるので、試しに最短路問題に変換して最短路ソルバーで解いてみた。ロットサイズ決定問題のデータは添付図の数値を用いる。

○ dimacs format graph file
c Shortest Paths : Lotsizing Problem
c
p sp 6 15
c
c
a 1 2 13
a 1 3 22
a 1 4 50
a 1 5 55
a 1 6 79
a 2 3 6
a 2 4 20
a 2 5 23
a 2 6 39
a 3 4 24
a 3 5 28
a 3 6 48
a 4 5 6
a 4 6 22
a 5 6 7

○ query ファイル
c Shortest Paths : Lotsizing Problem
c
p aux sp p2p 1
q 1 6

以下が実行結果となるが、 1 → 2 → 5 → 6 と進むのが最短路（つまり 1, 2, 5 日目に生産を行う)であり、最短路長（ロットサイズ決定問題のコスト）は 43 となる。

c fixed source destination solution
c -----------------------------------------------------------
c 0 1 6 43

SDPARA と CPU のアフィニテイ その２

前回の続きで SDPARA の実行に際しては MPI のプロセス数 = CPU 数, Pthread(OpenMP)にスレッド数 = CPU 内のコア数に設定するのが良さそうなのだが（特に NUMA アーキテクチャの場合)、以下では 1 ノードあたり 1 プロセスを生成すると仮定してときのアフィニティの設定方法について考えてみる。以下の SDPA クラスタでの実行を仮定すると 1 プロセス内で 8 スレッドを生成することになる。スレッドのコアに対する割り当ての順番については以下の二つを考慮する。

A: 0-1-2-3-4-5-6-7
B: 0-4-2-6-1-5-3-7

SDPARA 内ではスレッド番号(omp_get_thread_num 等で得られる番号)順に並列計算を行う行列のデータを行単位を割り振っていく方法を採用している。よって、B の方法の方が L2 キャッシュ上で共有されるデータ(キャッシュヒット)が多くなる傾向がある（詳細は省略)。
幾つか実験してみると以下のように B の方が少しだけ速くなっている。

○問題１：199901-0.33.dat-s
A: 22m20s
B: 21m54s
○問題２：NH.3Sigma-.DZ.pqgt1t2p.dat-s
A: 72m1s
B: 71m29s
○問題３：nug18_r2.dat-s
A: 45m6s
B: 43m35s

○ SDPA クラスタ
16 Nodes, 32 CPUs, 128 CPU cores;
CPU : Intel Xeon 5460 3.16GHz (quad cores) x 2 / node
Memory : 48GB / node
NIC : GbE x 2 and Myrinet-10G x 1 / node
OS : CentOS 5.5 for x86_64

SDPARA と CPU のアフィニテイ その１

以下の POWER クラスタで SDPARA を実行するときに、普通にノード数やスレッド数を指定すると、以下のようになる。

○問題１:NH3+.2A2".STO6G.pqgt1t2p.dat-s
4 MPI x 8 Pthread : 4m1s
8 MPI x 4 Pthread : 3m56s

次にアフィニティの設定に関して、同じ MPI の RANK 番号のスレッドは同じ CPU の別のコアに割り当てるようにする。1 ノード内に 2 CPU あるので、8 MPI x 4 Pthread の方は、コア番号では {0,2,4,6} と {1,3,5,7} に分けて割り当てた。何も設定しなくても OS 側でも同じように割り当てているかもしれないが、ここでは明示的に設定を行っている。

4 MPI x 8 Pthread(アフィニティ) : 4m6s
8 MPI x 4 Pthread(アフィニティ) : 3m50s

もう一問同じように解いてみるが、結果の傾向としては問題１の場合と同じである。 4 MPI x 8 Pthread の場合は明示的に設定しない方が良い結果になっている。

○問題２：N.4P.DZ.pqgt1t2p.dat-s
4 MPI x 8 Pthread : 53m30s
8 MPI x 4 Pthread : 57m44s
4 MPI x 8 Pthread(アフィニティ) : 54m15s
8 MPI x 4 Pthread(アフィニティ) : 52m20s

○ POWER クラスタ
4 Nodes, 8 CPUs, 32 CPU コア;
CPU : Intel Xeon E5345 2.33GHz (quad cores) x 2 / node
Memory : 16GB / node
HDD : 2TB(RAID 5) / node
NIC : GbE x 2 and Myrinet-10G x 1 / node
OS : CentOS 5.5 for x86_64

MIP ソルバーに関する数値実験 その２

前回の実験に SCIP と CPLEX 及び Gurobi を LP ソルバーとしてリンクしたものと、Cbc を加えて再度実験を行った。Gurobi や CPLEX には敵わないが、それでも Cbc は思ったより速かった。

1: Gurobi 3.0.1
2: IBM CPLEX 12.2
3: SCIP 1.2.0 + SOPLEX 1.4.1
4: SCIP 1.2.0 + IBM CPLEX 12.2
5: SCIP 1.2.0 + Gurobi 3.0.1
6: Cbc 2.5
7: GNU GLPK 4.44

○問題１: nw04.mps
1: 9.86s
2: 5.01s
3: 549.90s
4: 79.39s
5: 104.67s
6: 13.01s
7: 523.90s

○問題２: stein45.mps
1: 1.46s
2: 2.52s
3: 24.76s
4: 23.10s
5: 57.91s
6: 24.21s
7: 42.30s

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

LAPACK 3.2.2 と SDPA その２

前回の実験では以下の 1 の方は、GotoBLAS2 内の dpotrf を用いていたので、両方とも LAPACK 内の dpotrf を使用するように変更したところ以下のように同じ結果となった。

1: SDPA 7.3.2 + GotoBLAS2 1.13 + LAPACK 3.1.1
○gpp500-1.dat-s : pdOPT
○gpp500-2.dat-s : pdOPT
○gpp500-3.dat-s : pdOPT
○gpp500-4.dat-s : pdOPT

2: SDPA 7.3.2 + GotoBLAS2 1.13 + LAPACK 3.2.2
○gpp500-1.dat-s : pdOPT
○gpp500-2.dat-s : pdOPT
○gpp500-3.dat-s : pdOPT
○gpp500-4.dat-s : pdOPT

LAPACK 3.2.2 と SDPA

現時点での LAPACK の最新版は Ver. 3.2.2 となっている。通常 SDPA で用いている LAPACK 3.1.1 と比較すると一部の関数(Cholesky 等)で計算の数値精度が向上しているようだ。全ての問題に対して効果が見られるわけではないが、以下のようにグラフ分割問題の SDP に対しては、最適解(pdOPT)が得られることが多くなっている。

1: SDPA 7.3.2 + GotoBLAS2 1.13 + LAPACK 3.1.1
○gpp500-1.dat-s : pFEAS
○gpp500-2.dat-s : pFEAS
○gpp500-3.dat-s : pdOPT
○gpp500-4.dat-s : pdOPT

2: SDPA 7.3.2 + GotoBLAS2 1.13 + LAPACK 3.2.2
○gpp500-1.dat-s : pdOPT
○gpp500-2.dat-s : pdOPT
○gpp500-3.dat-s : pdOPT
○gpp500-4.dat-s : pdOPT

mpack-0.6.7 の make

MPACK の 0.6.7 がリリースされたので、以下の三つの環境で make を試みた。

1: CentOS 5.5 for x86_64(gcc 4.1.2) : make 成功
2: Fedora 13 for x86_64(gcc 4.4.4) : make 成功
3: CentOS 5.5 for x86_64(gcc 4.5.1) : make 失敗で以下のエラーメッセージが表示された。

arithmetic_debug_mpfr-arithmetic.debug.o: In function `mp_sub_test2()':
arithmetic.debug.cpp:(.text+0x75): undefined reference to `std::basic_ostream<char, std::char_traits& std::__ostream_insert<char, std::char_traits(std::basic_ostream<char, std::char_traits&, char const*, long)'
arithmetic.debug.cpp:(.text+0xde): undefined reference to `std::basic_ostream<char, std::char_traits& std::__ostream_insert<char, std::char_traits(std::basic_ostream<char, std::char_traits&, char const*, long)'
arithmetic.debug.cpp:(.text+0x317): undefined reference to `std::basic_ostream<char, std::char_traits& std::__ostream_insert<char, std::char_traits(std::basic_ostream<char, std::char_traits&, char const*, long)'
arithmetic.debug.cpp:(.text+0x384): undefined reference to `std::ctype<char>::_M_widen_init() const'
arithmetic.debug.cpp:(.text+0x3a4): undefined reference to `std::ctype<char>::_M_widen_init() const'
arithmetic.debug.cpp:(.text+0x3c4): undefined reference to `std::ctype<char>::_M_widen_init() const'
/home/fujisawa/DL/mpack-0.6.7/mpfrc++/.libs/libmpfrcxx.so: undefined reference to `std::basic_ostream<char, std::char_traits& std::__ostream_insert<char, std::char_traits(std::basic_ostream<char, std::char_traits&, char const*, long)@GLIBCXX_3.4.9'
/home/fujisawa/DL/mpack-0.6.7/mpfrc++/.libs/libmpfrcxx.so: undefined reference to `std::basic_ostream<char, std::char_traits& std::basic_ostream<char, std::char_traits::_M_insert<long>(long)@GLIBCXX_3.4.9'
/home/fujisawa/DL/mpack-0.6.7/mpfrc++/.libs/libmpfrcxx.so: undefined reference to `std::ctype<char>::_M_widen_init() const@GLIBCXX_3.4.11'
collect2: ld returned 1 exit status
make[3]: *** [arithmetic.debug_mpfr] エラー 1
make[3]: ディレクトリ `/home/fujisawa/DL/mpack-0.6.7/mblas/testing/mpfr' から出ます
make[2]: *** [all-recursive] エラー 1
make[2]: ディレクトリ `/home/fujisawa/DL/mpack-0.6.7/mblas/testing' から出ます
make[1]: *** [all-recursive] エラー 1
make[1]: ディレクトリ `/home/fujisawa/DL/mpack-0.6.7/mblas' から出ます
make: *** [all-recursive] エラー 1

Intel と gcc コンパイラ

Intel コンパイラと gcc の最新バージョンを用いて最適化ソフトウェアの性能を比較したのだが、両者の性能差はほとんど無いという結果になった。

Intel C/C++ 及び Fortran コンパイラ : 11.1.073
gcc/g++/gfortran : 4.5.1

○最短路ソルバー msp 1.12
○USA データ : 256 クエリ
1: Intel
c -- profile per threads --
c threadID fixed MB
c 000 33 365.49
c 001 33 365.50
c 002 30 365.50
c 003 31 365.50
c 004 29 365.49
c 005 34 365.49
c 006 32 365.50
c 007 34 365.50
c
c total memory space is 3460.38 MB (3628466260 bytes)
c total time is 126.558 seconds
c parse solve total is 0.818 125.739 126.558 seconds

2: gcc
c -- profile per threads --
c threadID fixed MB
c 000 32 365.50
c 001 36 365.49
c 002 28 365.50
c 003 31 365.49
c 004 36 365.50
c 005 32 365.49
c 006 30 365.50
c 007 31 365.50
c
c total memory space is 3460.37 MB (3628462164 bytes)
c total time is 126.796 seconds
c parse solve total is 0.831 125.964 126.796 seconds

○ SDPA 7.3.2 + GotoBLAS2 1.13

○ mcp2000-10.dat-s
1: Intel ; 57.363s
2: gcc ; 57.592s

○ thetaG51.dat-s
1: Intel ; 1m34.764s
2: gcc ; 1m33.897s

サイエンスセミナー 2010 終了

８月２３日にサイエンスセミナー 2010 を開催したが、受講した中高生のアンケート結果を見ると全体的に評判が高いようで、次回以降も機会があれば参加してみたいと考えている。
最適化問題、最短路問題、ダイクストラ法、クラスタ計算機、大規模計算と特に中学生には難しい内容ではあったが、たとえ全てを理解できなくても、中高のレベルを超えた最新の情報や成果に触れてみたいという強い意欲が感じられた。特にクラスタ計算機関連については現物の展示も含めて説明等に多くの時間を割いた。
優秀で意欲の高い中高生の方が、そうでない大学生や院生よりも理解が早いのも事実であり、努力だけでは越えられない本質的な才能の差も強く感じた。

Office 2010

Excel ファイルの動作を確認するために、Microsoft Office 2010 の評価版をダウンロードしていろいろと試してみた。速度や使い勝手共に Office 2007 よりは随分と向上しているが、反対に Office 2007 が悪すぎたとも言える。使ったことは無いのだが、Office 2010 の Web 版は機能制限も多いので、こちらの使い勝手は良くないらしい。Web からダウンロードしてインストールした直後に Microsoft Update から Office 2010 の更新を行って再起動するように促された。Web からダウンロードできるファイルは最新版ではないようだ。

1ノードでの SDPA と SDPARA その３

各スレッドに対して、MPI の RANK とスレッド番号を入手してから、sched_setaffinity 関数でアフィニティの設定を行い、再実験を行った。

○ 計算サーバ１ (4 CPU x 6 コア = 24 コア)
CPU : AMD Opteron 8439 (2.80GHz / 6MB L3) x 4 (24コア)
Memory : 128GB (32 x 4GB / 800MHz)
OS : Fedora 13 for x86_64

まずは、以下のコマンドで CPU やコア番号等に関する情報を入手する。

○ numactl --hardware
available: 4 nodes (0-3)
node 0 cpus: 0 4 8 12 16 20
node 0 size: 32762 MB
node 0 free: 31590 MB
node 1 cpus: 3 7 11 15 19 23
node 1 size: 32768 MB
node 1 free: 31710 MB
node 2 cpus: 2 6 10 14 18 22
node 2 size: 32768 MB
node 2 free: 31716 MB
node 3 cpus: 1 5 9 13 17 21
node 3 size: 32768 MB
node 3 free: 31606 MB
node distances:
node 0 1 2 3
0: 10 20 20 20
1: 20 10 20 20
2: 20 20 10 20
3: 20 20 20 10

２ MPI のときは４つの CPU を２つに分けるが、この場合では分け方によって特に差は生じなかった。結局、同じ RANK に属するスレッドは同じ CPU 内に割り当てるのが最速(4m10s)となった。

○ 問題 : NH3+.2A2".STO6G.pqgt1t2p.dat-s
○ 計算サーバ１：
■ SDPA 7.3.2 (24コア) : 4m15s

■ SDPARA 7.3.2 (1 MPI x 24 Pthread) : 4m58s

■ SDPARA 7.3.2 (2 MPI x 12 Pthread) : 4m15s
RANK 0 : 0,4,8,12,16,20,3,7,11,15,19,23
RANK 1 : 1,5,9,13,17,21,2,6,10,14,18,22

■ SDPARA 7.3.2 (2 MPI x 12 Pthread) : 4m15s
RANK 0 : 0,4,8,12,16,20,2,6,10,14,18,22
RANK 1 : 1,5,9,13,17,21,3,7,11,15,19,23

■ SDPARA 7.3.2 (4 MPI x 6 Pthread) : 4m10s
RANK 0 : 0,4,8,12,16,20
RANK 1 : 2,6,10,14,18,22
RANK 2 : 1,5,9,13,17,21
RANK 3 : 3,7,11,15,19,23

■ SDPARA 7.3.2 (4 MPI x 6 Pthread) : 4m32s
RANK 0 : 0,1,2,3,4,5
RANK 1 : 6,7,8,9,10,11
RANK 2 : 12,13,14,15,16,17
RANK 3 : 18,19,20,21,22,23

■ SDPARA 7.3.2 (6 MPI x 4 Pthread) : 4m35s

■ SDPARA 7.3.2 (12 MPI x 2 Pthread) : 4m59s

■ SDPARA 7.3.2 (24 MPI x 1 Pthread) : 5m52s