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

クラスタ計算機やスーパーコンピュータ上での大規模最適化問題やグラフ探索などの研究のお話が中心

クラスタ間の性能差

2011年11月30日 16時25分55秒 | Weblog
以下のような複数のクラスタ計算機を用いて最新の SDPARA の比較実験を行った。各クラスタ計算機で状況や設定が異なるため参考まで。

◯問題:N.4P.DZ.pqgt1t2p.dat-s

◯ OPT クラスタ(32CPU x 6コア = 192コア):529.37 秒
◯ OPT クラスタ(16CPU x 6コア = 96コア):921.33 秒
◯ SDPA クラスタ(16CPU x 4コア = 64コア):937.46 秒
◯ POWER クラスタ(8CPU x 4コア = 32コア):2658.90 秒
◯ OPTERON クラスタ(2PU x 48コア = 96コア):1811.80 秒
◯ OPTERON クラスタ(16 x 8コア = 96コア):2036.45 秒

参考 : SDPA
◯ OPTERON 1台 (1CPU x 48 コア = 48コア) : 2548.71秒

----------------------------------------------------------------------------------------------
○ OPT クラスタ
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.7 for x86_64

○ SDPA クラスタ
8 Nodes, 16 CPUs, 64 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.7 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.7 for x86_64

◯ OPTERON クラスタ
2 Nodes, 8 CPUs, 96 CPU コア;
CPU : AMD Opteron 6174 (2.20GHz / 12MB L3) x 4 / node
Memory : 256GB (16 x 16GB / 1066MHz) / node
NIC : GbE x 4 / node
OS : Fedora 15 for x86_64
コメント
この記事をはてなブックマークに追加

HOKKE-19 : グラフ処理

2011年11月29日 09時44分07秒 | Weblog
現在、HOKKE-19 で以下のセッション発表中。

第19回ハイパフォーマンスコンピューティングとアーキテクチャの評価に関する北海道ワークショップ
未来の情報処理基盤のためのハードとソフトの研究協力・共創へ向けて
(第189回計算機アーキテクチャ・第132回ハイパフォーマンスコンピューティング合同研究発表会(HOKKE-19))


■日 程 : 2011年11月28日(月)~2011年11月29日(火)
■会 場 : 北海道大学学術交流会館
http://www.hokudai.ac.jp/bureau/map/map4.htm

11月29日(火)

●グラフ処理(9:20 ~ 10:30)
(20)TSUBAME2における大規模グラフ処理ベンチマークGraph500の最適化と性能評価
上野晃司(東工大),鈴村豊太郎(東工大/IBM東京基礎研)
(21)計算機のメモリ階層構造を考慮した高性能ネットワーク解析ライブラリNETAL
安井雄一郎,藤澤克樹(中央大),佐藤仁,鈴村豊太郎(東工大),後藤和茂(マイクロソフト)
(22)Wikipediaの編集履歴を用いた大規模2部グラフのデータストリーム処理
竹野創平,上野晃司,雁瀬優(東工大),鈴村豊太郎(東工大/IBM東京基礎研)
コメント
この記事をはてなブックマークに追加

TSUBAME 2.0 上での SDPARA

2011年11月28日 20時36分44秒 | Weblog
現在、TSUBAME 2.0 のような CPU + GPU 構成のマシンで動作する SDPARA の開発を行っている。まず TSUBAME 2.0 の仕様や性能は以下の通りになる。

◯東工大 TSUBAME 2.0
HP Proliant SL390s G7 1408台
HP Proliant SL390s G7
CPU: Intel Xeon 2.93GHz 6コア×2ソケット = 12コア(Hyperthreading時 = 24コア)
GPU: NVIDIA Tesla M2050 3GPU
Memory: 54GB (一部は96GB)
SSD: 120GB (一部は240GB)
ネットワーク: QDR InfiniBand x 2 = 80Gbps

◯1ノードあたりの性能(倍精度)
CPU 140GF(2.93GHz) + GPU 1545GF = 1685GF
CPU 153GF(3.2GHz : TB) + GPU 1545GF = 1698GF

ここでは以下の超巨大 SDP を解くと仮定して、性能見積りを行ってみる。



これまでの実験結果から、この種の問題を解く際には Cholesky 分解の実行時間が全体の実行時間のほとんど(95%以上)を占めると予想される。また、これまで実験から反復回数を 40 回と仮定する。このとき Cholesky 分解に必要な計算量とメモリ量は以下の通りである。

◯計算量 : 6.0291e+17 FLOP
◯メモリ量: 1.35Tbytes(実際には2倍近くかかる)

以下の仮定1と仮定2を比べると CPU + GPU と CPU の比率は 10 倍以上となる。かなり粗めの計算なので値は参考程度に。ちなみに現在 TSUBAME 2.0 で開発中の Cholesky (CPU + GPU)の性能効率は 25% 程度になる。

◯仮定1:ノード数 1350, Cholesky 分解(CPU + GPU)性能効率 40%
このときの計算能力は 1350 * 1698(GF) * 0.40 = 9.1692e+14 FLOPS なので、6.0291e+17 / 9.1692e+14 * 40 = 約 26,300秒

◯仮定1:ノード数 1350, Cholesky 分解(CPU)性能効率 40%
このときの計算能力は 1350 * 153(GF) * 0.40 = 8.2620e+13 FLOPS なので、6.0291e+17 / 8.2620e+13 * 40 = 約 291,900秒

◯仮定3:ノード数 1350, Cholesky 分解(CPU + GPU)性能効率 25%
1350 * 1698(GF) * 0.25 = 5.7308e+14 FLOPS なので、6.0291e+17 / 5.7308e+14 * 40 = 約 42,082 秒

◯仮定4:ノード数 300, Cholesky 分解(CPU + GPU)性能効率 40%
300 * 1698 * 0.40 = 2.0376e+14 FLOPS なので、6.0291e+17 / 2.0376e+14 * 40 = 約 118,360 秒

コメント
この記事をはてなブックマークに追加

Graph500 November 2011 の結果:その2

2011年11月27日 00時49分40秒 | Weblog
Graph500 November 2011 の結果で3位の東工大 TSUBAME での結果について。今回の評価は TEPS 値(中央値)に変更された。次回の評価基準はグラフ点数 x TEPS 値になる。実際の BFS は 1兆枝に対しても、わずか 10 秒程度で終わってしまう。現在の実装ではネットワークバンド幅に性能が律速されているので、ノード内の計算資源を増やしても効果が出てこない。

◯点数: 2^36 = 68,719,476,736
◯枝数: 約 2^40 本
◯使用計算機資源: 2732 processors / 1366 nodes / 16,392 CPU cores
◯カーネル1(construction_time)の実行時間: 581.028秒
◯カーネル2(任意の点からの BFS)の実行時間: 10.9662秒
◯TEPS 値(最大値): 1.03899e+11 (103.899 GE/s)
◯TEPS 値(中央値): 1.00366e+11 (100.366 GE/s)



コメント
この記事をはてなブックマークに追加

2011年度第2回 SCOPE講演会:更新

2011年11月26日 19時41分56秒 | Weblog
JORSJ の SCOPE 特集号(Vol.54, No.4)の刊行を記念しまして、以下の特集号論文による講演会を開催したいと思います。年末のお忙しい時期ではございますが、是非ご参集下さい。夜には懇親会も予定しています。

○2011年度 第2回 SCOPE 講演会

日 時 : 2011年12月17日(土)14:00~17:00
会 場 : 中央大学 後楽園キャンパス 6号館 6410号室

講演1 14:00 ~
講演者 : 高野 祐一(東京工業大学 大学院 社会理工学研究科 経営工学専攻)
題目 : A Nonlinear Control Policy Using Kernel Method for Dynamic Asset Allocation
(動的資産配分のためのカーネル法を利用した非線形制御ポリシー)
概要: 本発表では, 非線形制御ポリシーを用いて多期間にわたる動的な資産配分を決定する最適化問題を定式化し, 問題求解のための計算手法を提案する. ここで, 制御ポリシーとは投資対象資産の過去の収益の関数である.カーネル法を利用することで, 非線形関数の中から最適な制御ポリシーを選択する問題は凸2次最適化問題として定式化される. さらに, L1-ノルムを用いた正則化を利用することで問題を線形最適化問題に帰着する. 計算実験では, 投資対象資産の収益率のシナリオを1期間自己回帰モデルによって生成し,先行研究の手法と比較して我々の提案する投資戦略は良好な運用成績を得られることを示す.


講演1 15:30 ~
講演者 : 田中 勇真(名古屋大学大学院 情報科学研究科 計算機数理科学専攻)
題目 : Lagrangian-based column generation for the node capacitated in-tree packing problem
(頂点容量付き有向全域木パッキング問題に対するラグランジュ緩和に基づく列生成法)
概要:本論文では, 頂点容量制約付き有向全域木パッキング問題を扱う. この問題は入力として, 有向グラフ,ルート頂点, 頂点容量, 辺の始点側と終点側それぞれに消費量が与えられる. 目的はルート頂点に流入する有向全域木のパッキング回数を最大化することである.ただし, 有向全域木の各頂点に対する消費量の合計は, 与えられた頂点容量を超えてはいけない. この問題はNP 困難である.
 以前, 我々はこの問題に対して2段階の発見的解法を提案した. このアルゴリズムは, 1段階目に木の候補を生成し, 2段階目に生成したそれぞれの木のパッキング回数を決定する. 本論文では, ラグランジュ緩和を用いることで1段階目を改善した. 計算実験により, 提案アルゴリズムは以前のアルゴリズムより速く木を生成でき, 少ない木の候補でもよい解を得ることを確認した.
コメント
この記事をはてなブックマークに追加

HPCS2012

2011年11月25日 01時51分17秒 | Weblog
HPCS 2012 年は以下のように3日間の開催になりました。

HPCS2012
2012年ハイパフォーマンスコンピューティングと計算科学シンポジウム

2012年1月24日(火)-26日(木)
名古屋大学 豊田講堂 シンポジオンホール
コメント
この記事をはてなブックマークに追加

スモールワールド

2011年11月24日 01時53分36秒 | Weblog
インターネットに限らず人間関係を表現するネットワークはスモールワールド性を持つことが知られている。その他にもスケールフリー性を持つことも知られている。Facebook ではある人から出発して BFS(幅優先探索)を行いながら人間関係のネットワーク木を作成していくと、Hop Distance が 7 でほぼ全員の人に到達してしまうことになる。Graph500 では、このような探索を超並列に行って TEPS 値を競っている。スケールフリー性があるということは、Hop 数の半分くらいで Hub のような特性を持つ(つまり枝数が非常に多い)点を通過するだろうが(下記のサイトの図を参照)、この瞬間にインターコネクトによる通信が飽和状態になる。よって当初はメモリバンド幅に律速になると推測されていた Graph500 は現在ネットワーク性能に律速する状態になっている。

Facebook、世界中の4.7人目は友達の友達という調査結果

Facebookでは人々は「六次の隔たり」より少ない「四次の隔たり」でつながっている――。米Facebookが11月22日(現地時間)、7億2100万人のユーザーを調査した結果を発表した。
コメント
この記事をはてなブックマークに追加

調達予定 その2

2011年11月23日 02時11分44秒 | Weblog
前回の続き。現在も見積り作業中。

1:SuperServer 7046GT-TRF-FC475
次の構成で 170万円程度の価格になる。

CPU:Xeon X5690(3.46GHz,6コア)×2
メモリ:192GB(16GB×12)
HDD:SATA500GB×2(システム、システムバックアップ)
GPGPU:Tesla C2075×4
OS:CentOS 5
CUDAインストール、1年間センドバック保守

2:Dell PowerEdge R910ラックサーバ
CPUは Westmere-EX が 4CPU で 40 コア構成。ただし Dell のオンライン見積りは実際の価格とかけ離れている場合が多いので、別の会社に同じ CPU で Dell 社以外のサーバの見積りを行った。メモリ 512GB、水冷クーラー、HDD 1TB x 4 等で約 400 万円。

コメント
この記事をはてなブックマークに追加

MVAPICH2 1.8 と SDPARA

2011年11月22日 03時03分11秒 | Weblog
MVAPICH2 1.8 a1p1 がリリースされている。
http://mvapich.cse.ohio-state.edu/download/mvapich2/download.php

この MVAPICH2 で SDPARA の実行を行うと、以下のように 7.3.1 よりも 7.3.3 の方が少しだけ高速になっている。

◯ 問題 NH3+.2A2\".STO6G.pqgt1t2p.dat-s
SDPARA 7.3.1 : 53.99秒
SDPARA 7.3.3 : 48.22秒

◯ 問題 N.4P.DZ.pqgt1t2p.dat-s
SDPARA 7.3.1 : 538.34秒
SDPARA 7.3.3 : 524.97秒

○ OPT クラスタ
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.7 for x86_64
コメント
この記事をはてなブックマークに追加

Graph500 November 2011 の結果

2011年11月21日 01時19分07秒 | Weblog
すでに報告しましたように Graph500 November 2011 では我々の CREST チームが3位入賞となりました。


競争の激しい分野なので詳細な情報の掲載は控えますが、公開可能な結果のみ掲載します。

◯使用した計算機
TSUBAME 2.0 の基本構成は 1466 ノードで 1 ノードあたり 2CPU + 3GPU の構成になっているが、Graph500 では CPU のみ使用する。稼働中のノード(1366ノード)は全て使用した。
TSUBAME (2732 processors / 1366 nodes / 16,392 CPU cores) GSIC Center, Tokyo Institute of Technology

◯解いたグラフのサイズ
Scale 36 : 点数は 2^36 = 約 687 億点
TSUBAME 2.0 のメモリは 54GB/ノードなので、時間があれば Scale 38 までは解くことができる。

◯ TEPS 値
100,366,000,000 = 約 100G TEPS (ただし中央値)。最大値は約 103G TEPS

これらの内容については以下のシンポジウムで東工大の鈴村先生に発表していただく予定です。

「e-サイエンスに向けた革新的アルゴリズム基盤」第2回シンポジウム

日時:平成23年11月22日(火曜日)

場所:東京工業大学 大岡山キャンパス:西2号館 W241講義室
(地図:http://www.gakumu.titech.ac.jp/kyoumu/lectureroom/picture/nisi/W241.pdf)

プログラム(暫定案)
1.   13:00~13:15 「計画概要」 加藤直樹(京都大学)
2.   13:15~13:45 「大規模ビジネスデータのマイニングの可能性と限界
            ー Webログおよびニュース記事の解析を例に」
            羽室行信(関西学院大学)
3.   13:45~14:15 「都市内滞留者・移動者の時空間分布推定と大地震を
            想定した人間行動シミュレーション」
            大佛俊泰(東京工業大学)
4.   14:15~14:45 「ソフトウェア検証における計算理論的問題
            ~安全性検証および等価性検証の事例」
            住井 英二郎(東北大学)
5.   15:00~15:30 「「確率密度比を用いた機械学習アルゴリズムとその応用」
            杉山将 (東京工業大学)
6.   15:30~16:00 「Graph 500 ベンチマークへの挑戦」
            鈴村豊太郎(東京工業大学)
7.   16:00~16:30  ディスカッション
コメント
この記事をはてなブックマークに追加

調達予定

2011年11月20日 00時11分13秒 | Weblog
そろそろ以下の計算サーバを調達する予定。問題はこれらの機種を扱える人が他にいないので、全部自分でインストールや設定を行わなければならない。

1:SuperServer 7046GT-TRF-FC475
2CPU + 4GPU の構成。現在開発中の新 SDPARA のために必要な機種。

2:Dell PowerEdge R910ラックサーバ
CPUは Westmere-EX が 4CPU で 40 コア構成。AMD Opteron 4 CPU x 16 コアの新 CPU Interlagos (Bulldozer) の採用は見送り。ある意味何でも使える万能機。もちろん手に入れば Sandy Bridge 系 Xeon の方が好ましい。
コメント
この記事をはてなブックマークに追加

2011年度第2回 SCOPE講演会

2011年11月19日 09時02分00秒 | Weblog
JORSJ の SCOPE 特集号(Vol.54, No.4)の刊行を記念しまして、以下の特集号論文による講演会を開催したいと思います。年末のお忙しい時期ではございますが、是非ご参集下さい。夜には懇親会も予定しています。

○2011年度 第2回 SCOPE 講演会

日 時 : 2011年12月17日(土)14:00~17:00
会 場 : 中央大学 後楽園キャンパス 6号館 6410号室

講演1 14:00 ~
講演者 : 高野 祐一(東京工業大学 社会理工学研究科 経営工学専攻)
題目 : A Nonlinear Control Policy Using Kernel Method for Dynamic Asset Allocation
(動的資産配分のためのカーネル法を利用した非線形制御ポリシー)


講演1 15:30 ~
講演者 : 田中 勇真(名古屋大学大学院 情報科学研究科 計算機数理科学専攻)
題目 : Lagrangian-based column generation for the node capacitated in-tree packing problem
(頂点容量付き有向全域木パッキング問題に対するラグランジュ緩和に基づく列生成法)
コメント
この記事をはてなブックマークに追加

SC11 東工大

2011年11月18日 00時50分05秒 | Weblog
今回の SC11 は Graph 500 の関係上東工大の展示ブースにいることが多かったのだが、当 CREST の成果であるGraph 500(世界3位) を含む以下の大量受賞等によって大変盛り上がっていた。アプリ開発はまだ始まったばかりの物も多いので、来年もアプリ面で大きな成果が出ることが期待される。

ACM Gordon Bell Award Special Achievement (特別賞)
ACM Gordon Bell Award Honorable Mention (奨励賞)
HPCWire Reader's Choice Award x 2
HPCWire Editor's Choice Award
The Graph 500 (世界3位)
The Top 500 (世界5位)
The Green 500 (世界10位)
Special Recognition Award for Perfect Score
George Michael 博士フェローシップ Honorable Mention (奨励賞)
コメント
この記事をはてなブックマークに追加

Cholesky 分解の FLOPS 値

2011年11月17日 00時04分38秒 | Weblog
以下の巨大な SDP は mDIM = 198432 なので、Cholesky 分解の FLOPS 値は 2.6045e+15(演算量) / 106018.790543(秒) * 40(反復) = 9.8264e+11(FLOPS) = 982.64(GFLOPS) となる。以下の OPT クラスタのピーク性能は 3.2GHz(TurboBoost) * 16 CPU * 12 コア * 4 演算 = 2457.6 (GFLOPS) なので、現在の性能効率は 982.64 / 2457.6 = 40% となる。

◯ QAP 緩和問題:esc32b_r2.dat-s
198432 = mDIM
9 = nBLOCK
-198190 321 321 321 321 321 321 449 513 = bLOCKsTRUCT


phase.value = pdOPT
Iteration = 40
Make bMat time = 1052.343739, 0.957887
Cholesky bMat = 106018.790543, 96.502674
Total = 109863.411891, 100.002206

○ OPT クラスタ
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.7 for x86_64

コメント
この記事をはてなブックマークに追加

Graph500 リスト2011年11月公開中

2011年11月16日 02時40分07秒 | Weblog
Graph 500 リストが公開された。

Complete Results - November 2011

以下の CREST 研究の一つとして Graph500 に取り組んでいる(主担当は以下の鈴村班)。今回は上記のリストで3位にランクインした。東工大の TSUBAME 2.0 の 1366 ノード 16,392 CPU cores を用いて 100GTEPS を達成した。今後の計画は以下のツイッターの呟き通り。

@sdpaninf graph500.org/nov2011.html Graph500 の今後:1,2 位とはコア数で相当な差があるが、実装上の工夫で何とか勝負できるレベル。ネットワークバンド幅を上げ長時間の安定実行から大きな問題を解くことを目指す。それでもダメならば日本の最終兵器某スパコンの登場になるか?


◯研究組織
◇研究代表者
藤澤克樹(中央大学)
◇研究グループ
1: 超大規模データを伴う最適化問題に対する高速計算システムの構築と評価 (グループリーダ : 藤澤克樹 (中央大学))
ー グラフ探索(最短路、幅優先探索、重要性計算)、数理計画問題(半正定値計画問題:SDP, 混合整数計画問題 MIP or MINLP 等)

2: リアルタイム大規模グラフストリーム処理系及びグラフ最適化ライブラリの開発 (グループリーダ : 鈴村豊太郎 (東京工業大学))

3: 大規模グラフ処理向けオンデマンド階層型データストアの開発 (グループリーダ : 佐藤仁 (東京工業大学))

4: 大規模グラフストリームデータの対話的な閲覧システム (グループリーダ : 脇田建 (東京工業大学))
コメント
この記事をはてなブックマークに追加