SDPARA と PCSDP と PDSDP

MPI 並列で SDP と言えば PDSDP が実は一番初めに出来たソフトウェアである。PDSDP と PCSDP は開発者がすでに民間企業に移ってしまって後継者？がいないという状況になっている。

○問題１：Be.1S.SV.pqgt1t2p.dat-s
SDPARA 7.3.3 : 173.45秒
SDPARA 7.3.2 : 923.40秒
PCSDP 1.0 : 1067.06秒
PDSDP 5.8 : 948.08秒(精度は良くない)

○問題２：nug12_r2.dat-s
SDPARA 7.3.3 : 29.69秒
SDPARA 7.3.2 : 33.29秒
PCSDP 1.0 : 139.53秒
PDSDP 5.8 : 662.48秒(精度は良くない)

○問題３：CH4.1A1.STO6G.noncore.pqg.dat-s
SDPARA 7.3.3 : 221.40秒
SDPARA 7.3.2 : 272.93秒
PCSDP 1.0 : 527.16秒
PDSDP 5.8 : 540.03秒

○新クラスタ計算機
１：PowerEdge M1000e(ブレードエンクロージャー) x 1台
２：PowerEdge M710HD(ブレードサーバ) x 16台
ブレードサーバの仕様：
CPU : インテル(R) Xeon(R) プロセッサー X5670(2.93GHz、12MB キャッシュ、6.4 GT/s QPI) x 2個
メモリ： 128GB (16X8GB/2R/1333MHz/DDR3 RDIMM/CPUx2)
Disk : 73GB x 2(1台のみ 300GB x 2)
NIC : GbE x 1 & Inifiniband QDR(40Gbps) x 1
OS : CentOS 5.5 for x86_64

整数計画問題に対するソルバーに関する最新の状況について

計算機や通信技術はその登場以来、常に進化を遂げていることは良く知られている。例えば、最適化に関係が深いキーワードには、マルチコア・プロセッサ、GPU コンピューティング、スーパーコンピュータ、クラウド・コンピューティングなどがあり、インターネットやマスコミなどでこれらのキーワードに触れる機会は大変多くなっている。

例えば GPU は、汎用的な CPU とは異なり主にグラフィック関係などの特定の処理用に作られたプロセッサである。この数年の間に、 GPU の大手メーカである nVIDIAを中心に GPU をグラフィック以外の処理にも使用する試みが、積極的に行われている。GPU での高速化に向いた処理とは、一般的に言って次のような性質を持つアルゴリズムである。

１：アルゴリズムが単純で（比較や条件分岐などがない）、浮動小数点演算中心で構成されていること
２：処理データが並列計算数に合わせてほぼ均等に分割できて独立に処理できること

残念ながら整数計画問題に対するアルゴリズムはこの二つの性質を持っていないので、GPU コンピューティングの技術で高速化することは難しい。また、スーパーコンピュータで整数計画問題に対するアルゴリズムを高速化する試みは学術的な機関では成功を収めているが、一般のユーザーに対してスーパーコンピュータの使用を前提条件とすることは、現時点では技術的、コスト的に難しいので、商用ソフトウェアに対してはスーパーコンピュータの普及は進んでいない。

一方、クラウド・コンピューティングとは、クライアント側の端末は出来るだけ軽く、安く押さえておいて、計算や検索などの処理及びデータの保存や管理はインターネット上のサーバで行うための技術の集合である。例えばユーザーは手元に大規模な計算資源を持っていなくても、計算規模と使用時間に応じた料金を支払うことによって、Amazon EC2 などのクラウド資源上で使用したい最適化ソルバーを大規模かつ高速に実行することができる。今後は、最適化ソルバーに対してもクラウド・コンピューティングの技術を用いた多様なサービスが行なわれていくだろう。

また、現在の CPU の主流はマルチコア・プロセッサと呼ばれチップ内部に複数の CPU コアを搭載している。Gurobi Optimizerなどの最新のソルバーはマルチコア・プロセッサ上での並列(マルチスレッド)計算に対応しているので、簡単に並列計算による高速化の恩恵を受けることができる。以下の計算サーバは 1CPU が12コアを搭載し、全部で 4 CPU = 48 コアを搭載しており、現在ではかなり大規模な計算サーバである。

○計算サーバ : (4 CPU x 12 コア = 48 コア)
CPU : AMD Opteron 6174 (2.20GHz / 12MB L3) x 4個
メモリ : 256GB (16 x 16GB / 1066MHz)
OS : Fedora 14 for x86_64

Gurobi Optimizerでは特にユーザーが設定しなくても、計算機内の CPU コア数を検知して並列計算を行なうようになっているが、以下のように
m.setParam('Threads', 1)とすると並列計算のスレッド数を 1 に変更することができる（この計算サーバの場合では初期値は 48）。

gurobi> m = read('roll3000.mps')
gurobi> m.setParam('Threads', 1)
gurobi> m.optimize()

○問題 rol3000.mps (MPILIB2003)
Gurobi 4.5.0 : 48 スレッド : 30.79秒
Gurobi 4.5.0 : 1 スレッド : 321.14秒

並列計算による高速化の効果は実際に解く問題によって異なることが多いが、一般的には、マルチコア・プロセッサ上の並列計算によって高速化することが可能である。

SDPARA と PCSDP

PCSDP の方は開発も終了しているようなので、最新版の SDPARA と比較するのは妥当ではないかもしれないが、新クラスタ計算機での比較実験を行なった。新クラスタ計算機上での PCSDP の作成は初めて。

○問題１：Be.1S.SV.pqgt1t2p.dat-s
SDPARA 7.3.3 : 173.45秒
PCSDP 1.0 : 1067.06秒

○問題２：nug12_r2.dat-s
SDPARA 7.3.3 : 29.69秒
PCSDP 1.0 : 139.53秒

○問題３：CH4.1A1.STO6G.noncore.pqg.dat-s
SDPARA 7.3.3 : 221.40秒
PCSDP 1.0 : 527.16秒

○新クラスタ計算機
１：PowerEdge M1000e(ブレードエンクロージャー) x 1台
２：PowerEdge M710HD(ブレードサーバ) x 16台
ブレードサーバの仕様：
CPU : インテル(R) Xeon(R) プロセッサー X5670(2.93GHz、12MB キャッシュ、6.4 GT/s QPI) x 2個
メモリ： 128GB (16X8GB/2R/1333MHz/DDR3 RDIMM/CPUx2)
Disk : 73GB x 2(1台のみ 300GB x 2)
NIC : GbE x 1 & Inifiniband QDR(40Gbps) x 1
OS : CentOS 5.5 for x86_64

第23回RAMPシンポジウム

第23回RAMPシンポジウムは当初東北大学で開催予定でしたが、東日本大震災の関係で開催場所が関西大学へと変更になりました。

第23回RAMPシンポジウム
2011年10月24日(月)・25日(火)
関西大学千里山キャンパス100周年記念館（大阪府吹田市）

日本オペレーションズ・リサーチ学会常設研究部会
「数理計画（RAMP）研究部会」ホームページ

Gurobi でのスレッド数の変更 その４

前回の実験が終わった瞬間に Gurobi 4.5.0 がリリースされたので再実験を行なった。

○問題 rol3000.mps (MPILIB2003)

以下の計算サーバでスレッド数を１から４８まで変化させて実験を行なった。初期解を与えない通常の場合（ログファイル)と最適解を初期解として与えた場合(ログファイル)の二種類の実験が含まれている。


次に前回 Gurobi 4.0.1 の結果と重ねたグラフを掲載する


次に初期解を与えない場合の 4.0.1 と 4.5.0 の比較のグラフの掲載


最後に最適解を初期解として与えた場合の 4.0.1 と 4.5.0 の比較のグラフを掲載する


○計算サーバ : (4 CPU x 12 コア = 48 コア)
CPU : AMD Opteron 6174 (2.20GHz / 12MB L3) x 4個
メモリ : 256GB (16 x 16GB / 1066MHz)
OS : Fedora 14 for x86_64

Sandy Bridge と SDPA その４

前回の数値実験に追加を行なった。問題１と３は Cholesky分解 つまり BLAS の性能に依存し、問題２は反対に BLAS に依存する部分は少ない。

○問題１：theta6.dat-s
SDPA 7.3.3 + GotoBLAS2 for Sandy Bridge : 9.089秒
SDPA 7.3.3 + GotoBLAS2 1.13(Nehalem) : 13.428秒
SDPA 7.3.3 + Intel MKL 10.3：10.036秒
SDPA 7.3.3 + ATLAS 3.9.39：14.769秒

○問題２：FH2+.1A1.STO6G.pqgt1t2p.dat-s
SDPA 7.3.3 + GotoBLAS2 for Sandy Bridge : 105.293秒
SDPA 7.3.3 + GotoBLAS2 1.13(Nehalem) : 107.935秒
SDPA 7.3.3 + Intel MKL 10.3：111.08秒
SDPA 7.3.3 + ATLAS 3.9.39：110.05秒

○問題３：nug12_r2.dat-s
SDPA 7.3.3 + GotoBLAS2 for Sandy Bridge : 111.237秒
SDPA 7.3.3 + GotoBLAS2 1.13(Nehalem) : 189.667秒
SDPA 7.3.3 + Intel MKL 10.3：128.29秒
SDPA 7.3.3 + ATLAS 3.9.39：160.35秒

○計算サーバ (1 CPU x 4 コア = 4 コア)
CPU : Intel Corei7 2600K (3.40GHz / 8MB L3) x 2
Memory : 8GB (4 x 2GB)
OS : Fedora 14 for x86_64

Gurobi でのスレッド数の変更 その３

Gurobi 4.0.1 を用いて、まず問題を解いて最適解を得てから MIP start(mst) ファイルを作る。

m = read('roll3000.mps')
m.optimize()
m.write('roll3000.mst')

その後で以下のように、mst ファイルを用いて最適解から探索を開始する。
m = read('roll3000.mps'); m.read('roll3000.mst'); m.setParam('Threads', 1); m.optimize();

前回と同じように 1 スレッドから 48 スレッドまで変更しながら問題を解いていく。結果は以下の図とログファイルを参照のこと。



次に前回の結果（初期解無し）と重ねた図を掲載してみた。

最適化分野におけるクラウド技術の利用

以下の内容の解説記事が某学会誌の６月号に掲載される予定となりました。６ページぐらいですので、そんなに量はありませんが可能なかぎり詳しく解説してあります。

○最先端理論(Algorithm Theory) + 大規模実データ(Practice) + 最新計算技術(Computation)
○クラウドによる計算資源の動的な確保
○グラフ探索と応用
○最短路を用いたグラフ解析
○Graph 500

理論からスパコンまで

これまで以下の内容で日本のいろいろな場所で講演を行なった。1990年代ではある理論がソフトウェアの実装に向いているのか、またその時代の計算新技術と組み合わせることによって大規模な問題を解くことができるようになるのかについては、時間をかけてじっくりと調査してみないとわからないことが多かった。ところが最近ではある理論に関する有効性や実用性については短時間にかなり正確な判断が可能となっている。
現在、計画策定中の”数百万～数億頂点から構成される大規模動的ネットワークグラフに対するリアルタイム分析”においては,古典的で安定したアルゴリズムと最新の情報技術を組み合わせて発展させた方が良いという結論になっている。

---------------------------------------------------------------------------
大規模最適化問題に対するソフトウェアと高速＆安定計算による解決
　　　　　　　　--理論からスパコンまで--

○1990年代半ばに誕生した半正定値計画問題(SDP)に対する理論（主双対内点法）がその後どのような経緯を辿って、ソフトウェア化されて、スパコン上で大規模計算が行われるようになったのか
○優れた（綺麗な）理論が高速、高性能な実装（ソフトウェア）になるまでのお話
○SDP に対する主双対内点法がここまで達したのは必然ではなかった
○内容は最適化理論から応用分野、ソフトウェア化、大規模計算までと多岐に渡る

Gurobi でのスレッド数の変更 その２

Gurobi 4.0.1 を用いて以下の問題を解く際にスレッド数を１から４８まで変えながら実行してみた。スレッド数が１変わっただけで実行時間も大きく変動し、スレッド数が多い方が良いとは限らない。

○問題 rol3000.mps (MPILIB2003)
スレッド数：実行時間(秒)
1　160.07
2　96.21
3　387.94
4　76.65
5　80.21
6　58.03
7　145.86
8　96.12
9　423.78
10　168.45
11　77.31
12　90.14
13　200.47
14　91.95
15　78.93
16　157.72
17　100.14
18　58.24
19　87.61
20　47.40
21　215.34
22　42.41
23　49.83
24　43.28
25　57.90
26　31.32
27　39.26
28　33.24
29　72.17
30　80.95
31　94.45
32　40.92
33　70.12
34　63.03
35　41.29
36　170.97
37　99.80
38　63.68
39　59.51
40　87.69
41　1109.85
42　27.78
43　48.02
44　81.63
45　31.08
46　33.40
47　43.11
48　63.69



○計算サーバ : (4 CPU x 12 コア = 48 コア)
CPU : AMD Opteron 6174 (2.20GHz / 12MB L3) x 4個
メモリ : 256GB (16 x 16GB / 1066MHz)
OS : Fedora 14 for x86_64

某整数計画ソルバー

某整数計画ソルバーの実験結果。計算過程が異なるので単純に比較は出来ないが、計算サーバ２の方がスレッド数は少なくても実行時間は小さい。

○問題 mod011.mps
○計算サーバ１：
Solving Time (sec) : 450.2000
Solving Nodes : 1392
○計算サーバ２：
Solving Time (sec) : 291.5400
Solving Nodes : 1693

○問題 roll3000.mps
○計算サーバ１：
Solving Time (sec) : 1146.8900
Solving Nodes : 378804
○計算サーバ２：
Solving Time (sec) : 878.9500
Solving Nodes : 399640

○問題 stein45.mps
○計算サーバ１：
Solving Time (sec) : 157.8900
Solving Nodes : 16273
○計算サーバ２：
Solving Time (sec) : 11.8100
Solving Nodes : 15978


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

○計算サーバ２ (2 CPU x 6 コア = 12 コア)
CPU : Intel Xeon 5670 (2.93GHz / 12MB L3) x 2
Memory : 128GB (16 x 8GB)
OS : CentOS 5.6 for x86_64

Sandy Bridge と Nehalem

代表的な整数計画ソルバーである CPLEX と Gurobi を用いてSandy Bridge と Nehalem上で比較実験を行った。SDPA のような顕著な性能向上はなくクロック周波数相当の性能向上のみが見られる。

1: CPLEX 12.2.0.2
○問題１：roll3000.mps
計算サーバ１：31.52秒
計算サーバ２：37.32秒

○問題２：S-20-20-2-3.mps
計算サーバ１：619.69秒
計算サーバ２：701.63秒

2: Gurobi 4.0.1
○問題１：roll3000.mps
計算サーバ１：34.63秒
計算サーバ２：41.21秒

○問題２：S-20-20-2-3.mps
計算サーバ１：155.91秒
計算サーバ２：178.45秒

○計算サーバ１ (1 CPU x 4 コア = 4 コア)
CPU : Intel Corei7 2600K (3.40GHz / 8MB L3) x 2
Memory : 8GB (4 x 2GB)
OS : Fedora 14 for x86_64

○計算サーバ２ (1 CPU x 4 コア = 4 コア)
CPU : Intel Corei7 965 (3.20GHz / 8MB L3) x 1
Memory : 12GB (6 x 2GB)
OS : CentOS 5.6 for x86_64

Gurobi でのスレッド数の変更

Gurobi では特にユーザーが設定しなくても、計算機内の CPU コア数を検知して並列計算を行なうようになっているが、以下のように m.setParam('Threads', 1)とすると並列計算のスレッド数を 1 に変更することができる(この計算サーバの場合では初期値は 48)。

gurobi> m = read('roll3000.mps')
gurobi> m.setParam('Threads', 1)
gurobi> m.optimize()

○問題 rol3000.mps (MPILIB2003)
Gurobi 48 スレッド : 63.69秒
Gurobi 1 スレッド : 160.07秒

○計算サーバ : (4 CPU x 12 コア = 48 コア)
CPU : AMD Opteron 6174 (2.20GHz / 12MB L3) x 4個
メモリ : 256GB (16 x 16GB / 1066MHz)
OS : Fedora 14 for x86_64

Sandy Bridge と SDPA その３

ATLASも最新版では AVX 命令対応になっているようなので、これを用いて Intel MKL との性能差を調べた。BLAS への依存度が少ない問題２では同等の結果になっているが、その他の問題では Intel MKL との差が大きい。

○問題１：theta6.dat-s
SDPA 7.3.3 + Intel MKL 10.3：10.036秒
SDPA 7.3.3 + ATLAS 3.9.39：14.769秒

○問題２：FH2+.1A1.STO6G.pqgt1t2p.dat-s
SDPA 7.3.3 + Intel MKL 10.3：111.08秒
SDPA 7.3.3 + ATLAS 3.9.39：110.05秒

○問題３：nug12_r2.dat-s
SDPA 7.3.3 + Intel MKL 10.3：128.29秒
SDPA 7.3.3 + ATLAS 3.9.39：160.35秒

○計算サーバ (1 CPU x 4 コア = 4 コア)
CPU : Intel Corei7 2600K (3.40GHz / 8MB L3) x 2
Memory : 8GB (4 x 2GB)
OS : Fedora 14 for x86_64

Sandy Bridge と SDPA その２

esc16b_r2.dat-s の mDIM は 27376 なので、この SDP を解くと１反復において 27376 x 27376 行列の Cholesky 分解を１回行う必要がある。この場合では計算サーバ２のSandy Bridge (Core i7-2600K;3.4GHz)は、計算サーバ３の Nehalem(Corei7-965;3.2GHz)の２倍近い計算速度になっている。

○ソフトウェア SDPA 7.3.3 + Intel MKL 10.3

○問題：esc16b_r2.dat-s
計算サーバ１： 1919.2秒 (Cholesky 分解 : 1559.3秒)
計算サーバ２： 2616.9秒 (Cholesky 分解 : 2018.3秒)
計算サーバ３： 4399.4秒 (Cholesky 分解 : 3784.7秒)
参考
新クラスタ計算機(SDPARA 7.3.2)：318.8秒 (Cholesky 分解 : 280.1秒)

○計算サーバ１ (2 CPU x 6 コア = 12 コア)
CPU : Intel Xeon 5670 (2.93GHz / 12MB L3) x 2
Memory : 128GB (16 x 8GB)
OS : CentOS 5.6 for x86_64

○計算サーバ２ (1 CPU x 4 コア = 4 コア)
CPU : Intel Corei7 2600K (3.40GHz / 8MB L3) x 2
Memory : 8GB (4 x 2GB)
OS : Fedora 14 for x86_64

○計算サーバ３ (1 CPU x 4 コア = 4 コア)
CPU : Intel Corei7 965 (3.20GHz / 8MB L3) x 1
Memory : 12GB (6 x 2GB)
OS : CentOS 5.6 for x86_64

○新クラスタ計算機
１：PowerEdge M1000e(ブレードエンクロージャー) x 1台
２：PowerEdge M710HD(ブレードサーバ) x 16台
ブレードサーバの仕様：
CPU : インテル(R) Xeon(R) プロセッサー X5670(2.93GHz、12MB キャッシュ、6.4 GT/s QPI) x 2個
メモリ： 128GB (16X8GB/2R/1333MHz/DDR3 RDIMM/CPUx2)
Disk : 73GB x 2(1台のみ 300GB x 2)
NIC : GbE x 1 & Inifiniband QDR(40Gbps) x 1
OS : CentOS 5.5 for x86_64