SDPARA 7.3.1 と 7.3.2 その４

SDPA クラスタは Xeon 5460 なので Harpertown であるが、POWER クラスタは Xeon E5345 なので Clovertown となっている。前者の方が新しいので性能が良いのは当然としても、Harpertown では様々な細かい改良が施されている。どちらもメモリバンド幅はあまり高くはないが(6Gbytes/sec. 強)、L2 キャッシュの性能が良いので、メモリバンド幅の大きな AMD Barcelona や Shanghai よりも SDPA(SDPARA) では高性能な結果を残した。この POWER クラスタで SDPARA 7.3.1 と 7.3.2 の比較実験を行った。

○問題１：Be.1S.SV.pqgt1t2p.dat-s
SDPARA 7.3.1 : 765.1s
SDPARA 7.3.2 : 733.1s
○問題２：band_n800_m100_w5.dat-s
SDPARA 7.3.1 : 113.4s
SDPARA 7.3.2 : 85.7s
○問題３：N.4P.DZ.pqgt1t2p.dat-s
SDPARA 7.3.1 : 2648.6s
SDPARA 7.3.2 : 2502.6s

○ 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

SDPARA 7.3.1 と 7.3.2 その３

SDPAR クラスタで実験した結果がどうも悪い（遅い）と思っていたところ、SDPA クラスタの６番目のノードにメモリ異常が発生しているようなので（似たような現象は以前３番目のノードに発生した）、このノードを外して１５台で再実験を行った。１台のメモリ異常でこんなに性能が悪くなってしまうようだ。

○問題１：Be.1S.SV.pqgt1t2p.dat-s
SDPARA 7.3.1 : 233.5s
SDPARA 7.3.2 : 210.9s
○問題２：band_n800_m100_w5.dat-s
SDPARA 7.3.1 : 56.2s
SDPARA 7.3.2 : 40.4s
○問題３：N.4P.DZ.pqgt1t2p.dat-s
SDPARA 7.3.1 : 626.6s
SDPARA 7.3.2 : 580.5s

○ 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 7.3.1 と 7.3.2 その２

前回と同じように 7.3.1 と 7.3.2 の比較を SDPA クラスタで行った。7.3.2 の方が性能は良いのだが、公開はまだ先になりそうだが、SDPARA の次期バージョンも少しずつ開発中である。このソフトウェア SDPARA を使いこなすためには、最適化、内点法、ソフトウェア、並列計算、スパコンなどの知識と経験が必要なので一般ユーザには正直難しいと思われる。

○問題１：Be.1S.SV.pqgt1t2p.dat-s
SDPARA 7.3.1 : 14m1s
SDPARA 7.3.2 : 13m42s
○問題２：band_n800_m100_w5.dat-s
SDPARA 7.3.1 : 2m6s
SDPARA 7.3.2 : 1m48s

○ 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

整数計画ソルバーとマルチスレッド

おそらく CPLEX や Gurobi などのソルバーは deterministic なアルゴリズムをマルチスレッド化して並列実行を行っていると推測されるので、本当にこの方法がベストかどうかは別として、計算に使用するコア数を増やしていけば高速化が期待できる。ただしこれらのソルバーは MPI による並列化には対応していないので、多数のコアを要したサーバでの実行が望ましい。今は１サーバで AMD Opteron 12コア x 4個 = 48 コアを搭載したものが簡単に入手できるので、これらのソルバーの実行に適している。

新クラスタ計算機

電源 200V 単相 30A の工事は終わったのだが、発注手続きに少し手間がかかっているので実際の納入＆稼働時期は未定である。メモリ量は合計で 128GBytes x 12 台 = 1536Gbytes = 1.5Tbytes なので、現クラスタ計算機の２倍であるが、本当はもっと欲しかったところだ。総コア数 = 6 x 2 x 12 = 144、理論性能(Turbo Boost は使用しない) 144 コア x 2.93GHz x 4 演算 = 1687GFlops となる。

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

SDPARA 7.3.1 と 7.3.2

SDPA のホームページから公開している SDPARA 7.3.1 のソースファイルに開発版の 7.3.2 のソースをマージして改めて 7.3.2 とした。7.3.2 は例えば Intel Xeon で実行する場合では Harpertown よりも Nehalem 系の方が速いようだ。今後の新クラスタの実行を考慮すると良い傾向だ。

○問題１：control11.dat-s
SDPARA 7.3.1 : 5m44s
SDPARA 7.3.2 : 53s
○問題２：FH2+.1A1.STO6G.pqgt1t2p.dat-s
SDPARA 7.3.1 : 1m55s
SDPARA 7.3.2 : 1m48s

○ 計算サーバ (2 CPU x 4 コア = 8 コア)
CPU : Intel Xeon 5550 (2.66GHz / 8MB L3) x 2 (8コア)
Memory : 72GB (18 x 4GB / 800MHz)
OS : Fedora 13 for x86_64

二つのクラスタ計算機と SDPARA その３

ネットワークへの転送量の少ない ParaSCIP だけでなく, 転送量が多いと思われる SDPARA でもヘテロな複数のクラスタ計算機、さらに複数の計算サーバを束ねた環境でも性能が上がっていくことを確認した。さすがにグリッドのような広域環境での並列化での性能向上は厳しいかもしれないが、これからの並列計算環境（１ノード内には非常に高密度で計算資源が凝縮されているが、ノード間の結合は比較的に低密度）での大規模実行に期待が持てる結果にもなっている。

疎計算とマルチコア

Opteron (Istanbul) 4-way マシンだと密計算ではなかなか性能が上がらずに全てのコアを使う前に飽和してしまうのだが（問題１：mcp2000-10.dat-s）、疎計算の方は豊富なメモリバンド幅を利用する形でマルチコアでの計算に持っていけば以下のように性能向上が期待できる(FH2+.1A1.STO6G.pqgt1t2p.dat-s)。今後登場が予想される１マシンで 48 コアあるいはそれ以上のコアでも期待が持てる内容である。

SDPA 7.3.2
○問題１：mcp2000-10.dat-s
１８コア：56.7s
２４コア：1m0.1s

○問題２：FH2+.1A1.STO6G.pqgt1t2p.dat-s
１８コア：1m16.8s
２４コア：1m5.8s

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

2010 年度第３回 SCOPE 講演会

10月2日に SCOPE 講演会を行います。今回は整数計画問題に関する講演（２件）になります。是非ご参加下さい。

日　時 ： 2010年10月2日（土）14:00～
会　場 ： 中央大学 後楽園キャンパス 6 号館4階 6410号室
講演1
講演者 ： Karen Aardal氏（Delft Institute of Technology and CWI - Amsterdam）
講演題目 ： Integer programming, lattices, reduced bases
講演概要：
I will discuss how to use the structure of lattices to reformulate and solve
integer programming problems. I will take a closer look at integer knapsack
problems and illustrate how it is possible to use the structure of lattices
to prove properties of certain classes of knapsack problems, and how these
properties can be used in designing practically efficient algorithms.


講演2
講演者 ： Timo Berthold氏（Zuse Institute Berlin(ZIB), Berlin）
講演題目 ： Solving MIQCPs with SCIP
講演概要：
Mixed-integer programming (MIP) and constraint programming (CP) proved to be powerful tools to model and solve
large-scale optimization problems. Constraint integer programming (CIP) is a novel generalization of MIP that
supports the notion of arbitrary constraints as in CP. We introduce the algorithmic ideas of CIP and present
SCIP, a framework for constraint integer programming.
We show how to extend SCIP towards a solver for mixed integer quadratically constrained programs (MIQCPs).
The advantage of this approach is that we can utilize the full power of advanced MIP and CP technologies
already implemented in SCIP. We give an overview of the relaxation, reformulation, separation, and propagation
techniques that are used to handle quadratic constraints efficiently. Computational experiments indicating
the potential of the approach are provided.
In the second part of the talk, we present Undercover, a primal heuristic for mixed-integer nonlinear
programming (MINLP). The heuristic constructs a MIP subproblem (sub-MIP) of a given MINLP by fixing a subset
of the variables. We solve a set covering problem to identify a minimal set of variables which need to be fixed
in order to linearize each constraint. Subsequently, these variables are fixed to approximate values, e.g.
obtained from a linear outer approximation. The resulting sub-MIP is solved by a MIP solver. We present
computational results on a general test set of MIQCPs selected from the MINLPLib.

メニーコアと最適化問題 その２

SDPARA はローカルな複数のクラスタ計算機の加算によって、性能向上が期待できることを幾つかの例で確認した。SDPARA よりも通信量が少ない最適化ソフトウェア(例えば ParaSCIP)はさらに性能向上が期待できる。この場合では複数のクラスタ計算機だけでなく、複数の計算サーバを用いてもよい。また、SDPA の最新版はマルチスレッドでの高速計算に対応しているので、例えば Cray XMT のように大容量メモリを多数のスレッドで共有できるマシンでは性能向上も期待ができる。結局プログラミングの技術でどちらにも適用できるということになる。

二つのクラスタ計算機と SDPARA その２

前回の実験の続きでより大きな問題を解いてみた。現状でもヘテロなクラスタ計算機で性能向上が期待できる。

○ソフトウェア SDPARA 7.3.2 + GotoBLAS2 1.13 + MUMPS 4.9.2

○問題：NH.3Sigma-.DZ.pqgt1t2p.dat-s
SDPA クラスタ : 28004.2s
SDPA + POWER クラスタ : 23496.7s

○ 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

○ 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

メニーコアと最適化問題

CPU 数や CPU 内のコア数が増えても、メモリバンド幅などの様々なボトルネックの箇所が存在するために必ずしも性能が綺麗にスケールアップするわけでないが、これまで実験している範囲では幾つかの最適化ソフトウェアは多数のコアを有する計算機上での顕著な性能向上が期待できるようだ。例えば AMD Opteron 61xx では 12 コアを有しており、4-way のサーバでは合計 48 コアに達する。例えばマルチスレッド計算に対応している SDPA や MIP の Gurobi, CPLEX などでは 48 コアという量は大変有効な武器になる。

複数クラスタ計算機と MPI

ParaSCIP も以下の二つのクラスタ計算機を同時に用いて 128 + 32 = 160 プロセスで計算を行っている。ただし、まだ具体的な成果は出ていない。他にも様々な計算サーバもあるので、さらに数十プロセスほど追加も可能である。新クラスタ計算機が導入されれば、144 プロセスがさらに追加可能である。

マスタープロセスを除いて 159 プロセスで計算中である。しかし、この問題は上界(462)と下界(385)の差が全く縮まらない。

6515 77677397 63449890 159 462.0000 385.0000 20.00%
6520 77736666 63495988 159 462.0000 385.0000 20.00%
6525 77796512 63542633 159 462.0000 385.0000 20.00%
6530 77856200 63589107 159 462.0000 385.0000 20.00%
6535 77915482 63635260 159 462.0000 385.0000 20.00%

○ 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

○ 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

二つのクラスタ計算機と SDPARA

以下の二つのクラスタ計算機は Nyrinet-10G が同じ 10GbE スイッチを共有しているので、両者を同時に利用して SDPARA の計算を行った。1 CPU でも総 CPU 数でも上回る SDPA クラスタの方が速いのは当然として、同時に利用するとどうなるだろうか？ このため SDPARA 側にもちょっとした細工を入れてある。

○ソフトウェア SDPARA 7.3.2 + GotoBLAS2 1.13 + MUMPS 4.9.2
○問題１：N.4P.DZ.pqgt1t2p.dat-s
SDPA クラスタ : 2053.8s
POWER クラスタ : 2534.9s
SDPA + POWER クラスタ : 1859.6s

○問題２：HLi2.2A1.STO6G.pqgt1t2p.dat-s
SDPA クラスタ : 5820.4s
SDPA + POWER クラスタ : 5236.9s


○ 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

○ 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

イノベーション・ジャパン ２０１０ 展示

イノベーション・ジャパン２０１０において以下の展示を行う予定になっている。最短路関係が中心となっているので SDP に関連する高速計算技術や大規模実験に関する内容は含まれていない。

大規模動的ネットワークに対する最短路高速計算システム

技術の概要

大規模なネットワーク上で二点間の最短路を求める最短路問題は非常に幅広い応用が存在する。解法にはダイクストラ法というアルゴリズムが用いられるが、データ構造やメモリ階層構造を考慮した実装上の工夫により世界最高速レベルの速度、安定性、低メモリ消費などの特性を備えたソフトウェアの作成に成功した。また道路データだけでなく、鉄道などの時空間ネットワークなど大規模なネットワーク上での最短路検索への対応を行った。
産業界へのアピールポイント

現在よりも高性能かつ高機能なナビゲーションシステムの開発、また渋滞状況に応じた交通管制や大規模災害時における避難シミュレーションなどの新規分野の開拓が期待できる
技術の特徴

1: 世界最高レベルの性能を持った最短路計算エンジン
2: 拡張性の高いアルゴリズムとデータ構造により様々な条件を追加することが可能
3: クラウドコンピューティングの技術によるオンライン・ソルバーの構築
想定される用途

大規模ネットワークにおける最短経路の高速計算及びクラウドによる並列分散コンピューティング
関係する助成制度

日本私立学校振興・共済事業団　学術研究振興資金
企業に期待するもの

本システムは最適化、高速実装、並列計算、クラウドコンピューティングなどの最新の技術を備えた研究成果であり、これらの成果を発表すると共に新しい応用＆実用分野の開拓と提携先を探すのが出展目的である。