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

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

自己紹介と重要リンク

2016年10月19日 22時11分55秒 | Weblog
大規模最適化問題に対する超高速&安定計算。
半正定値計画問題(SDP)の対するソフトウェア SDPA, SDPARA の開発者及び SDP の超大規模計算に対する世界記録保持者。
JST CREST ポストペタスケールシステムにおける超大規模グラフ最適化基盤:研究代表者

1: GraphCrest ホームページ
2: SDPA ホームページ(sourceforge)
3: Katsuki Fujisawa HP
4: 最短路問題 Online Solver
5: SCOPE(「計算と最適化の新展開」研究部会)(すでに終了)
6: Twitter : sdpaninf

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

JST CREST : ポストペタスケールシステムにおける超大規模グラフ最適化基盤

2016年08月27日 23時53分47秒 | Weblog
JST CREST (Core Research for Evolutional Science & Technology)
応募研究領域 : ポストペタスケール高性能計算に資するシステムソフトウェア技術の創出
研究課題名 : ポストペタスケールシステムにおける超大規模グラフ最適化基盤

◯研究課題要旨
 大規模災害等は突発的に発生するため事前予測による防災計画だけでなく、動的なデータ収集等とスパコン上での高速計算によって速やかに避難、誘導計画を策定する必要がある。すでに研究代表者らのグループでは首都圏道路網や鉄道網を精密なグラフデータに変換して、超大規模なグラフ処理を用いた避難、誘導計画の策定を進めているが、非常に計算量やデータ量などの規模が大きく従来の手法では処理が困難である。ポストペタスケールスーパーコンピュータ(スパコン)における最重要カーネルのひとつでもある超大規模グラフ処理を実現するためには、理論的性能限界等からボトルネック箇所を特定、数値演算能力とメモリバンド等のトレードオフ関係を把握、計算量とデータ移動量の正確な推定、疎性やサイズなどのデータ特性と性能値の見極め、などが必要とされる。しかし、従来手法では、数千万規模の並列性を備え、ストレージの階層性が深化したポストペタスケールシステム上でのスケーラブルな実行は困難であり、アルゴリズム、システムソフトウェアと同時並行的な解決が求められている。我々は、これらの問題に対応した超大規模グラフ最適化システムを提案する。本システムは、大規模グラフデータに対するリアルタイムストリーミング処理、計算量とデータ移動量を考慮したグラフ最適化アルゴリズム、ストレージの階層性を考慮した大規模グラフデータストア、超大規模グラフのリアルタイム可視化など従来のスパコンでは実現されてこなかった新しい問題を解決する。これらのシステムは TSUBAME2.0のようなペタスケールスパコン上で構築と評価を行い、今後、出現が想定されるポストペタスケールスパコンのアーキテクチャ上での実行に適したソフトウェア基盤を構築し、エクサスケールスーパーコンピューティングへの方向性づくりに大いに貢献する。



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

2: リアルタイム大規模グラフストリーム処理系及びグラフ最適化ライブラリの開発 (グループリーダ : 鈴村豊太郎 (バルセロナスーパーコンピュータセンター))

3: 大規模グラフ処理向けオンデマンド階層型データストアの開発 (グループリーダ : 佐藤仁 (東京工業大学))
コメント
この記事をはてなブックマークに追加

SCIP-SDP : SDPA 7.4.0 その2

2016年07月24日 02時18分12秒 | Weblog
SCIP-SDP a mixed integer semidefinite programming plugin for SCIP

すでに 5.5 日間の連続実行中。 使用メモリ量も 500Gbytes を超えている。
15759 fujisawa 20 0 0.533t 0.532t 6700 R 95.2 27.0 7890:27 ../bin/scipsdp -f ./coloncancer_1701_1800_20.dat-s

残りの gap 0.1% がなかなか減らない。。。
7899m|455400 | 3839 | 51295k| 22.2 | 10.16%| 18M| 85 | 0 | 101 | 4 | 1 | 0 | 0 | 9.762646e+01 | 9.763391e+01 | 0.01%

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

九州大学情報基盤研究開発センター 教員(常勤)公募

2016年07月23日 02時30分38秒 | Weblog
九州大学情報基盤研究開発センター 教員(常勤)公募

1.募集人員 教授(常勤)1名
2.所 属 情報基盤研究開発センター 学習環境デザイン研究部門
(サイバーセキュリティセンターを兼任, 大学院システム情報科学府,工学部電気
情報工学科,理学部物理学科情報理学コース,基幹教育(全学教育)等の教育を担
当していただきます。)
3.任 期 なし(定年は65 歳)
4.専門分野 サイバーセキュリティに関する教育、教育支援、研究
5.担当科目 基幹教育、学部および大学院の講義担当予定
6.応募資格
(1) 博士の学位を有すること。
(2) 専門分野に顕著な研究業績があり,学生の教育研究指導に熱意を持って取り組める方。
(3) サイバーセキュリティに関する講義、学生指導ができること。
(4) 英語での授業ができる方。
(5) サイバーセキュリティセンターの研究ができること。
(6) 学内外の学術情報の電子化・情報発信支援,情報教育支援,大型計算機,ネットワーク,セキュリティ対策サービス支援等について取り組み,中核的役割を果たすことができること。
7.着任予定時期 平成28年度内のできるだけ早い時期
コメント
この記事をはてなブックマークに追加

SC16 Workshops (Sun/Mon/Fri)

2016年07月22日 02時48分13秒 | Weblog
SC16 での Workshop 開催は以下の HP から見ることが出来ます。

SC16 Workshops (Sun/Mon/Fri)
SC includes full- and half-day workshops that complement the overall Technical Program events, with the goal of expanding the knowledge base of practitioners and researchers in a particular subject area. These workshops provide a focused, in-depth venue for presentations, discussion and interaction. Workshop proposals were peer-reviewed academically with a focus on submissions that inspire deep and interactive dialogue in topics of interest to the HPC community.
コメント
この記事をはてなブックマークに追加

九州大学 マス・フォア・インダストリ研究所 文部科学省卓越研究員受入について

2016年07月21日 01時01分36秒 | Weblog
九州大学 マス・フォア・インダストリ研究所 文部科学省卓越研究員受入について

九州大学では、文部科学省卓越研究員事業 (http://www.mext.go.jp/a_menu/jinzai/takuetsu/index.htm)により「卓越研究員 制度の活用に係る将来構想」を策定し、自ら研究テーマを設定して研究室主宰者として新 たな研究領域に挑戦する若手研究者を募集します。なお、卓越研究員にはテニュアトラッ ク制を適用します。

[仕事内容(業務内容、担当科目、研究分野の詳細等)]

研究分野は広い意味での数学で、産業数学・産業応用に関心があることが望まれます。産 業技術分野をはじめとする他分野研究者と盛んに交流を行って、そこで出会った未解決問 題にその才能とエネルギーを降り注ぎ、必要があればみずから定式化・デザインし、独創 的なアイデアに基づいて挑戦することが求められます。新領域開拓のシーズとなるような 問題の発見・提案などの能力や諸科学との関連付けが行える連想力も考慮します。半年〜 1 年間、伊都キャンパス勤務の後、La Trobe 大学(メルボルン)に設置した IMI オースト ラリア分室に⻑期滞在し(1〜2 年)、現地の教員に協力しながら、研究・教育活動を行っ てもらう計画です。

伊都キャンパスでの業務:
○理学部数学科の講義(数理統計、計算数学を含む)の演習。
○その他通常の助教と同じ職務。

オーストラリア分室での業務:
○数理学府学生の La Trobe 大学での研究滞在やインターンシップの受け入れの世話:受 け入れた学生の英語教育、産業数学のプロジェクトの研究指導。 ○共同利用・共同研究拠点として提供する共同利用研究のオーストラリア分室実施分の世話。
○スタディ・グループ等産業数学関連ワークショップへの参加、アジア・太平洋産業数学 コンソーシアム(APCMfI)にかかわる活動。

[募集人員(人数、職名等)] 助教 1名
[着任時期(着任日、採用日等)]
平成 28 年 8 月以降、なるべく早い時期

[参考情報] 卓越研究員にはテニュアトラック制を適用し、研究費や海外渡航費の一定額を支援しま す。
[問い合わせ先] 担当部署:マス・フォア・インダストリ研究所 福本 康秀 電話番号:092-802-4437 e-mail:yasuhide@imi.kyushu-u.ac.jp
コメント
この記事をはてなブックマークに追加

ISM-IMI 協定記念合同シンポジウム

2016年07月20日 00時27分50秒 | Weblog






2016.06.29
<ISM-IMI 協定記念合同シンポジウム>


参加費 無料
参加方法:当日直接会場へお越しください。

開催日 2016年7月19日(火) 14:00 ~

開催場所 九州大学 伊都キャンパス ウエスト1号館 D棟 4階 IMIオーディトリアム (W1-D-413)
伊都キャンパスへのアクセス,伊都キャンパスマップ

式次第 15:00 - 15:30
《統計数理研究所の研究活動 - 統計数理が目指すフロンティア》
講演者:伊藤 聡 (ISM 副所長)

15:30 - 16:00
《大規模グラフ解析と都市 OS の開発 - ヒト・モノのモビリティに関する新しい数理モデルとその応用 -》
講演者:藤澤 克樹 (IMI 教授)

16:00 - 16:30 Tea Break

16:30 - 17:00
《天文データと統計的手法》
講演者:池田 思朗 (ISM 教授)

17:00 - 17:30
《ロバストなガウシアングラフィカルモデリングの効率的なアルゴリズム》
講演者:廣瀬 慧 (IMI 准教授)
コメント
この記事をはてなブックマークに追加

ISM-IMI 協定記念合同シンポジウム : 今日です

2016年07月19日 00時16分05秒 | Weblog
2016.06.29
<ISM-IMI 協定記念合同シンポジウム>


参加費 無料
参加方法:当日直接会場へお越しください。

開催日 2016年7月19日(火) 14:00 ~

開催場所 九州大学 伊都キャンパス ウエスト1号館 D棟 4階 IMIオーディトリアム (W1-D-413)
伊都キャンパスへのアクセス,伊都キャンパスマップ

式次第 15:00 - 15:30
《統計数理研究所の研究活動 - 統計数理が目指すフロンティア》
講演者:伊藤 聡 (ISM 副所長)

15:30 - 16:00
《大規模グラフ解析と都市 OS の開発 - ヒト・モノのモビリティに関する新しい数理モデルとその応用 -》
講演者:藤澤 克樹 (IMI 教授)

16:00 - 16:30 Tea Break

16:30 - 17:00
《天文データと統計的手法》
講演者:池田 思朗 (ISM 教授)

17:00 - 17:30
《ロバストなガウシアングラフィカルモデリングの効率的なアルゴリズム》
講演者:廣瀬 慧 (IMI 准教授)
コメント
この記事をはてなブックマークに追加

SCIP-SDP : SDPA 7.3.8 と SDPA 7.4.0 その2

2016年07月18日 02時36分02秒 | Weblog
SCIPSDP 2.1.0 と SDPA 7.3.8 と SDPA 7.4.0 の比較実験の結果

SCIP-SDP a mixed integer semidefinite programming plugin for SCIP

◎SDPA 7.4.0
3g_244_244_k9_3_4.dat-s:Total Time : 695.80
clique_60_k15_4_4.dat-s:Total Time : 24760.44
2x4_16bars.dat-s:Total Time : 352.93
2x5_1scen_8bars.dat-s:Total Time : 95.39
2x5_2scen_4bars.dat-s:Total Time : 1112.09
3x3_2scen_6bars.dat-s:Total Time : 23.87
3x3_3scen.dat-s:Total Time : 1040.21
3x4_2fixed_4bars_nominal.dat-s:Total Time : 62.93
bridge_3x7_2bars_nominal.dat-s:Total Time : 260.35
bridge_3x9_2bars.dat-s:Total Time : 6551.35
demonstsmall_1bar_4scen.dat-s:Total Time : 222.46
demonstsmall_2bar_3scen.dat-s:Total Time : 38.11
demonstsmall_3bar_2scen_nominal.dat-s:Total Time : 72.11
test_bridge2.dat-s:Total Time : 59.71

◎SDPA 7.3.8
3g_244_244_k9_3_4.dat-s:Total Time : 1085.10
clique_60_k15_4_4.dat-s:Total Time : 23173.74
2x4_16bars.dat-s:Total Time : 419.23
2x5_1scen_8bars.dat-s:Total Time : 113.92
2x5_2scen_4bars.dat-s:Total Time : 1527.82
3x3_2scen_6bars.dat-s:Total Time : 28.05
3x3_3scen.dat-s:Total Time : 1266.02
3x4_2fixed_4bars_nominal.dat-s:Total Time : 65.32
bridge_3x7_2bars_nominal.dat-s:Total Time : 432.14
bridge_3x9_2bars.dat-s:Total Time : 8816.17
demonstsmall_1bar_4scen.dat-s:Total Time : 175.41
demonstsmall_2bar_3scen.dat-s:Total Time : 47.18
demonstsmall_3bar_2scen_nominal.dat-s:Total Time : 89.86
test_bridge2.dat-s:Total Time : 70.41

SandyBridge-EP 32 コアマシン
CPU Intel Xeon E5-4640 (8-core 2.40GHz 16MB cacheTDP:95w) x 4
Memory 512GB ACTICA製HPC専用メモリ DDR3 1600Mhz (16GB x 32枚) x 32
OS : CentOS 7.2
コメント
この記事をはてなブックマークに追加

SCIP-SDP : SDPA 7.4.0

2016年07月17日 02時05分43秒 | Weblog
SCIPSDP 2.1.0 は結局 SDPA 7.4.0 とリンクして以下などのサーバで実行中です。

top - 02:05:21 up 48 min, 2 users, load average: 3.00, 3.09, 2.73
Tasks: 552 total, 4 running, 548 sleeping, 0 stopped, 0 zombie
%Cpu(s): 6.2 us, 0.1 sy, 0.0 ni, 93.7 id, 0.0 wa, 0.0 hi, 0.0 si, 0.0 st
KiB Mem : 52807632+total, 50868195+free, 5485280 used, 13909088 buff/cache
KiB Swap: 4194300 total, 4194300 free, 0 used. 52211724+avail Mem

PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
29007 fujisawa 20 0 884008 561032 6168 R 99.7 0.1 13:01.87 ../bin/scipsdp -f ./3g_244_244_k8_4_4.dat-s
30150 fujisawa 20 0 826272 502504 6148 R 99.7 0.1 2:55.98 ../bin/scipsdp -f ./bridge_2x9_2bars.dat-s
28797 fujisawa 20 0 1690048 1.082g 6220 R 99.3 0.2 21:52.49 ../bin/scipsdp -f ./random_128_6_c.dat-s

◯計算サーバ
CPU : Intel(R) Xeon(R) CPU E5-2670 v3 @ 2.30GHz x 2
メモリ:512GB
OS : CentOS 7.2







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

SCIP-SDP : SDPA 7.3.8 と SDPA 7.4.0

2016年07月16日 00時53分43秒 | Weblog
以下の SCIP-SDP 2.1.0 に SDPA をリンクして SDP の外部ソルバーとして利用することが可能である。

SCIP-SDP a mixed integer semidefinite programming plugin for SCIP

SCIP-SDP is a plugin for SCIP to solve mixed integer semidefinite programs (MISDPs). It combines the branch-and-bound framework of SCIP with interior-point SDP-solvers. It provides the data handling, some presolving and propagation as well as a reader for a modified sparse SDPA-format with additional lines for integrality constraints. It is possible to solve the resulting SDP-relaxations using a linear approximation procedure, but for full functionality one of the following SDP-solvers needs to be installed:
DSDP
SDPA

今回は SDPA 7.3.8 と SDPA 7.4.0 の違いで SCIP-SDP 2.1.0 の性能の違いが出るのか調べてみた。SDPA 7.4.0 を使用した方がかなり高速になっている。

◎ SCIP-SDP 2.1.0
◎ SDPA 7.3.8 or SDPA 7.4.0
◎ OpenBLAS 0.2.19dev

問題1:random_32_4_a.dat-s
◎SDPA 7.3.8
SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 6.23
Solving Nodes : 20
Primal Bound : +1.26693009594114e+01 (2 solutions)
Dual Bound : +1.26693009594114e+01
Gap : 0.00 %

◎SDPA 7.4.0
SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 3.07
Solving Nodes : 20
Primal Bound : +1.26693009594114e+01 (2 solutions)
Dual Bound : +1.26693009594114e+01
Gap : 0.00 %


問題2:bridge_2x5_5bars.dat-s
◎SDPA 7.3.8
SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 17.34
Solving Nodes : 924
Primal Bound : +2.49705627484800e+00 (1 solutions)
Dual Bound : +2.49705627484800e+00
Gap : 0.00 %

◎SDPA 7.4.0
SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 6.81
Solving Nodes : 924
Primal Bound : +2.49705627484800e+00 (1 solutions)
Dual Bound : +2.49705627484800e+00
Gap : 0.00 %


問題3:clique_20_k3_6_7.dat-s
◎SDPA 7.3.8
SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 19.80
Solving Nodes : 220
Primal Bound : +1.46999986786081e+02 (1 solutions)
Dual Bound : +1.46999986786081e+02
Gap : 0.00 %

◎SDPA 7.4.0
SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 5.46
Solving Nodes : 92
Primal Bound : +1.46999987743974e+02 (1 solutions)
Dual Bound : +1.46999987743974e+02
Gap : 0.00 %


◯計算サーバ
CPU : Intel(R) Xeon(R) CPU E5-2699 v3 @ 2.30GHz x 2 個
メモリ:512GB
OS : CentOS 7.2
コメント
この記事をはてなブックマークに追加

スーパーコンピュータ「京」が Graph500 で世界第1位を獲得

2016年07月15日 02時17分42秒 | Weblog
スーパーコンピュータ「京」が Graph500 で世界第1位を獲得
-ビッグデータの処理で重要となるグラフ解析で最高の評価-


九州大学と東京工業大学、理化学研究所、スペインのバルセロナ・スーパーコンピューティング・ センター、富士通株式会社による国際共同研究グループは、2016 年 6 月に公開された最新のビッグ データ処理(大規模グラフ解析)に関するスーパーコンピュータの国際的な性能ランキングである Graph500 において、スーパーコンピュータ「京(けい)」による解析結果で、2015 年 11 月に続き 3 期連続(通算 4 期)で第 1 位を獲得しました。大規模グラフ解析の性能は、大規模かつ複雑なデータ処理が求められるビッグデータの解析にお いて重要となるもので、今回のランキング結果は、「京」がビッグデータ解析に関する高い能力を有 することを実証するものです。本研究の一部は、科学技術振興機構(JST)戦略的創造研究推進事業 CREST「ポストペタスケール 高性能計算に資するシステムソフトウェア技術の創出」(研究総括:佐藤 三久 理研計算科学研究 機構)における研究課題「ポストペタスケールシステムにおける超大規模グラフ最適化基盤」(研究 代表者:藤澤 克樹 九州大学、拠点代表者:鈴村 豊太郎 バルセロナ・スーパーコンピューティン グ・センター)および「ビッグデータ統合利活用のための次世代基盤技術の創出・体系化」(研究総 括:喜連川 優 国立情報学研究所)における研究課題「EBD:次世代の年ヨッタバイト処理に向け たエクストリームビッグデータの基盤技術」(研究代表者:松岡 聡 東京工業大学)の一環として 行われました。
コメント
この記事をはてなブックマークに追加

日本のスパコン「京」、スパコン性能ランキング「Graph500」で3期連続で1位

2016年07月14日 16時01分50秒 | Weblog
日本のスパコン「京」、スパコン性能ランキング「Graph500」で3期連続で1位
 
[2016/07/13]
九州大学と東京工業大学、理化学研究所、スペインのバルセロナ・スーパーコンピューティング・センター、富士通による国際共同研究グループは7月13日、2016年6月に公開されたビッグデータ処理(大規模グラフ解析)に関するスーパーコンピュータ(スパコン)の国際的な性能ランキング「Graph500」において、日本の「京(けい)」が、2015年11月に続き3期連続で1位を獲得したことを発表した。
コメント
この記事をはてなブックマークに追加

SCIP-SDP a mixed integer semidefinite programming plugin for SCIP

2016年07月13日 01時43分23秒 | Weblog
scipsdp の 2.1.0 が公開されています。

SCIP-SDP a mixed integer semidefinite programming plugin for SCIP

SCIP-SDP is a plugin for SCIP to solve mixed integer semidefinite programs (MISDPs). It combines the branch-and-bound framework of SCIP with interior-point SDP-solvers. It provides the data handling, some presolving and propagation as well as a reader for a modified sparse SDPA-format with additional lines for integrality constraints. It is possible to solve the resulting SDP-relaxations using a linear approximation procedure, but for full functionality one of the following SDP-solvers needs to be installed:

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

2016年秋季研究発表会のプログラム公開

2016年07月12日 01時54分22秒 | Weblog
日本オペレーションズ・リサーチ学会 2016年秋季研究発表会
2016年秋季研究発表会のプログラム公開

http://www.orsj.or.jp/~nc2016f/program.html

日程
2016年9月15日(木)~16日(金)

会場
山形大学 小白川キャンパス (山形県山形市) (会場へのアクセス)

テーマ
再生・復興とOR

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