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

大規模最適化問題、グラフ探索、機械学習やデジタルツインなどの研究のお話が中心

SDPARA と PCSDP と PDSDP

2011年04月30日 00時14分36秒 | Weblog
MPI 並列で SDP と言えば PDSDP が実は一番初めに出来たソフトウェアである。PDSDP と PCSDP は開発者がすでに民間企業に移ってしまって後継者?がいないという状況になっている。

○問題1: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秒(精度は良くない)

○問題2: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秒(精度は良くない)

○問題3: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秒

○新クラスタ計算機
1:PowerEdge M1000e(ブレードエンクロージャー) x 1台
2: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
コメント
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする

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

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

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

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

残念ながら整数計画問題に対するアルゴリズムはこの二つの性質を持っていないので、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秒

並列計算による高速化の効果は実際に解く問題によって異なることが多いが、一般的には、マルチコア・プロセッサ上の並列計算によって高速化することが可能である。
コメント
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする

SDPARA と PCSDP

2011年04月28日 02時21分54秒 | Weblog
PCSDP の方は開発も終了しているようなので、最新版の SDPARA と比較するのは妥当ではないかもしれないが、新クラスタ計算機での比較実験を行なった。新クラスタ計算機上での PCSDP の作成は初めて。

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

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

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

○新クラスタ計算機
1:PowerEdge M1000e(ブレードエンクロージャー) x 1台
2: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
コメント
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする

第23回RAMPシンポジウム

2011年04月27日 02時27分59秒 | Weblog
第23回RAMPシンポジウムは当初東北大学で開催予定でしたが、東日本大震災の関係で開催場所が関西大学へと変更になりました。

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

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

コメント
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする

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

2011年04月26日 23時02分30秒 | Weblog
前回の実験が終わった瞬間に Gurobi 4.5.0 がリリースされたので再実験を行なった。

○問題 rol3000.mps (MPILIB2003)

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


次に前回 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
コメント (5)
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする

Sandy Bridge と SDPA その4

2011年04月25日 02時40分33秒 | Weblog
前回の数値実験に追加を行なった。問題1と3は Cholesky分解 つまり BLAS の性能に依存し、問題2は反対に BLAS に依存する部分は少ない。

○問題1: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秒

○問題2: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秒

○問題3: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
コメント
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする

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

2011年04月24日 02時37分12秒 | Weblog
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 スレッドまで変更しながら問題を解いていく。結果は以下の図とログファイルを参照のこと。



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


コメント (3)
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする

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

2011年04月23日 11時26分11秒 | Weblog
以下の内容の解説記事が某学会誌の6月号に掲載される予定となりました。6ページぐらいですので、そんなに量はありませんが可能なかぎり詳しく解説してあります。

○最先端理論(Algorithm Theory) + 大規模実データ(Practice) + 最新計算技術(Computation)
○クラウドによる計算資源の動的な確保
○グラフ探索と応用
○最短路を用いたグラフ解析
○Graph 500
コメント
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする

理論からスパコンまで

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

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

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

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

2011年04月21日 22時03分42秒 | Weblog
Gurobi 4.0.1 を用いて以下の問題を解く際にスレッド数を1から48まで変えながら実行してみた。スレッド数が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
コメント (2)
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする

某整数計画ソルバー

2011年04月20日 21時36分52秒 | Weblog
某整数計画ソルバーの実験結果。計算過程が異なるので単純に比較は出来ないが、計算サーバ2の方がスレッド数は少なくても実行時間は小さい。

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

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

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


○計算サーバ1 (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 (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
コメント
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする

Sandy Bridge と Nehalem

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

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

○問題2:S-20-20-2-3.mps
計算サーバ1:619.69秒
計算サーバ2:701.63秒

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

○問題2:S-20-20-2-3.mps
計算サーバ1:155.91秒
計算サーバ2:178.45秒

○計算サーバ1 (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

○計算サーバ2 (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
コメント (2)
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする

Gurobi でのスレッド数の変更

2011年04月18日 01時07分21秒 | Weblog
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
コメント (1)
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする

Sandy Bridge と SDPA その3

2011年04月17日 03時00分28秒 | Weblog
ATLASも最新版では AVX 命令対応になっているようなので、これを用いて Intel MKL との性能差を調べた。BLAS への依存度が少ない問題2では同等の結果になっているが、その他の問題では Intel MKL との差が大きい。

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

○問題2: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秒

○問題3: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
コメント
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする

Sandy Bridge と SDPA その2

2011年04月16日 04時26分06秒 | Weblog
esc16b_r2.dat-s の mDIM は 27376 なので、この SDP を解くと1反復において 27376 x 27376 行列の Cholesky 分解を1回行う必要がある。この場合では計算サーバ2のSandy Bridge (Core i7-2600K;3.4GHz)は、計算サーバ3の Nehalem(Corei7-965;3.2GHz)の2倍近い計算速度になっている。

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

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

○計算サーバ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

○計算サーバ2 (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

○計算サーバ3 (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

○新クラスタ計算機
1:PowerEdge M1000e(ブレードエンクロージャー) x 1台
2: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
コメント (2)
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする