グラフ解析の性能

グラフ解析における非常に重要な処理として最短路計算があります。具体的にはグラフ上で始点と終点を指定して、この二点間の最短路を計算するのが目的です。最短路計算の性能を表す指標としては実行時間の他にも１秒間に何本の枝を通過できるかを測定するTEPS(Traversed Edges Per Second) 値があります。現在のCPU 1 コアで10^7 = 1000 万TEPS 以上の性能を出すことができますので、全米データ(2400万点, 5800 万枝：下図) に対する最短路計算は 5 秒程度で終了することができます(最短路計算においては全ての枝を 1 回程度通過するため）。また複数の CPU コアで並列計算を行う場合ではさらに大きなTEPS値を出すことが加能です。

e-サイエンスに向けた革新的アルゴリズム基盤

日本学術会議に提案を行っておりました”e-サイエンスに向けた革新的アルゴリズム基盤”ですが、学術の大型施設計画・大規模研究計画マスタープラン２０１１に選ばれました。以下の資料の 35, 36 ページに説明があります。

http://www.scj.go.jp/ja/info/kohyo/pdf/kohyo-21-h135-1-4.pdf

e-サイエンスに向けた革新的アルゴリズム基盤
(Foundations of Innovative Algorithms towards E-Science)



第4の科学の方法論として重要なe-サイエンスの確立のために、諸分野において、従来手法では解決不可能な大規模な問題を数理解析に基づく革新的なアルゴリズムによって解決する共同研究拠点の構築を目指す。個別分野で開発されたアルゴリズムを整備し、標準化して諸分野に提供することにより、広範な学術向上、さらには国民生活の質の向上、新規産業創出等への寄与が期待できる。

以下のように情報学からの申請はやや少なめです。

(1) 人文・社会科学分野： 3 計画 → 4 計画
(2) 生命科学分野： 11 計画 → 14 計画
(3) エネルギー・環境・地球科学分野： 8 計画 → 9 計画
(4) 物質・分析科学分野： 4 計画 → 4 計画
(5) 物理科学・工学分野： 11 計画 → 9 計画
(6) 宇宙空間科学分野： 4 計画 → 3 計画
(7) 情報学分野： 2 計画 → 3 計画
合計： 43 計画 → 46 計画

SDPA Online Solver : 巨大な問題

SDPA Online Solver に以下のような巨大な問題を投入されている方がいるが、この大きさだと Online Solver ではかなり荷が重すぎる。

43758 = mDIM
29 = nBLOCK
(11,66,66,66,66,66,66,66,66,66,66,66,66,66,66,66,286,286,286,286,286,286,286,286,286,286,1001,1,,1,) = bLOCKsTRUCT

ただし、以下の OPT クラスタと SDPARA の組み合わせでは、わずか 29 分程度で終了した。

30 1.2e-08 5.5e-18 2.3e-16 +1.00e+00 +1.00e+00 9.9e-01 9.0e-01 1.00e-01
31 1.3e-09 2.2e-18 2.7e-16 +1.00e+00 +1.00e+00 1.0e+00 9.0e-01 1.00e-01
32 1.4e-10 3.3e-18 2.8e-16 +1.00e+00 +1.00e+00 1.0e+00 9.0e-01 1.00e-01
33 1.5e-11 5.5e-18 1.9e-16 +1.00e+00 +1.00e+00 1.0e+00 9.0e-01 1.00e-01

phase.value = pdOPT
Iteration = 33
mu = +1.4679615650636303e-11
relative gap = +7.1401650258984262e-08
gap = +7.1401650258984262e-08
digits = +7.1462913305051439e+00
objValPrimal = +9.9999906851798004e-01
objValDual = +9.9999899711632978e-01
p.feas.error = +5.5511151231257827e-16
d.feas.error = +5.1469939421622257e-13
total time = 1654.473228

実行時間の内訳だが、bMat(SCM)の計算で全体の約 27% で、Infiniband を用いた bMat のコピーに約 4 %、また bMat の Cholesky 分解には全体の約 2/3 を費やしている。

Make bMat time = 439.106645, 26.588019
copy bMat time = 72.028674, 4.361354
Cholesky bMat = 1100.352604, 66.626629

ちなみに以下のクラスタ計算機はまだ完全に元に戻ってはいない。今日も継続修理の予定。

○OPT クラスタ計算機
１：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.6 for x86_64

SDPA Online Solver バイナリ変更

久しぶりに SDPA Online Solver のバイナリを更新した。具体的には SDPA 7.3.1 から SDPA 7.4.0 に変更して、スレッド数を４から８に変更した。実行画面は下図を参照のこと。

新２号館

新２号館を少しだけ見学してきた。



文京区シビックホール２５階から見たキャンパス（9月24日撮影)。高校屋上の運動場（緑のネット）の向こう側が新２号館。新２号館と同じくらいの高さの奥の建物が６号館。左の高い建物は３号館。新２号館と３号館にはさまれた低い建物が１号館。また３号館の手前の L 字型の建物がもうすぐ解体される現２号館。奥で見えにくいがあと４号館と５号館もある。容積率がすでにいっぱいなので、新しいのを建てては古いのを壊すことの繰り返しになる。



８階の共同研究センターの研究室。窓の外には高所恐怖症の人には絶叫もののメカニカルバルコニーというものがあるらしい(個人的には少しだけ楽しそうに見えた）。



空調機、２４時間換気システムそれに加湿器が付いている。

大規模なグラフ解析が注目される理由

近年、社会における実データをグラフデータに変換して計算機で高速処理する需要が高まりつつあります。特に以下の理由から大規模なグラフ解析が注目を集めています。

1. 実社会における本質的課題の解決に必須な手法
下図のように社会や理工系の超大規模問題の解決のためには、最先端理論 + 超大規模実データ + 最新計算技術の融合が必要ですが、グラフ解析の技術はこの中で非常に大きな役割を果たします。



2. 適用が期待される多くの分野が存在する
現在では、以下の分野に対してグラフ解析を適用する研究が世界中で行われています。
(a) 交通データに対する経路探索：動的に変化する交通量等から高速な重要度判定を行うことによって、交通管制等に活用する
(b) ソーシャルネットワークデータ(マイクロブログやSNS など) やウェブデータに対する動的な重要度、影響度の判定。各点の周辺、及び広域内における影響（情報の伝播力）を推定する
(c) その他：疫病の拡散、人口の増減、経済動向等の分析。ライフライン等の基盤計画（電力、水、食料）。生命科学系（創薬、遺伝子）。ビジネス系（金融、データマイニング）。安全保障分野（組織構成の解明、事件事故の事前予測）。

3. HPC(高性能計算) 分野における注目のアプリケーション
今年の6 月に富士通製のスパコン(通称：京) が浮動小数点演算の能力測定で世界一になったことは知られていますが、その他にもグラフの探索速度でスパコンの性能を測定するGraph500 と呼ばれるベンチマークテストが提案されています。各国ともグラフ探索等のプログラム開発とスパコンでの実行を重視しています。

Excelで学ぶOR の スライド化

Excel で学ぶ OR の本は TeX で書かれているので、これを元にして beamer を用いてスライド化（講義等で使用できる形で）を行っている。1 章の半分ぐらいで 50 ページ以上になってしまった。時間はかかるだろうが、７章まで全て終われば数百ページの資料になるだろう。

OR概論/本書の使い方
第1部　基本編　ORの基本的なツールを学ぶ
第1章　数理最適化
第2章　シミュレーション
第2部　応用編　具体的な問題例を通じて学ぶ
第3章　都市・交通のデザインとネットワーク理論
第4章　計画、運用のためのモデルとサプライチェイン最適化
第5章　予測・検証・発見のための最適化モデルとデータマイニング
第6章　投資効率評価とDEA
第7章　不確実性下の意思決定とファイナンス理論
付録

Intel® C++ and Fortran Composer XE for Linux 2011.5.220 から 2011.6.233 その２

昨日の続きだが、SandyBridge においても以下のように性能向上は見られない。現時点では 2011.6.233 を使用するメリットはあまり感じられない。

○問題１：theta6.dat-s
SDPA 7.4.0 + GotoBLAS2 for Sandy Bridge : 8.865秒
SDPA 7.4.0 + Intel MKL 10.3.4-191 : 9.423秒
SDPA 7.4.0 + Intel MKL 10.3.5-220 : 9.407秒
SDPA 7.4.0 + Intel MKL 10.3.6-233 : 9.470秒

○問題２：FH2+.1A1.STO6G.pqgt1t2p.dat-s
SDPA 7.4.0 + GotoBLAS2 for Sandy Bridge : 100.630秒
SDPA 7.4.0 + Intel MKL 10.3.4-191 : 101.488秒
SDPA 7.4.0 + Intel MKL 10.3.5-220 : 100.794秒
SDPA 7.4.0 + Intel MKL 10.3.6-233 : 100.835秒

○問題３：nug12_r2.dat-s
SDPA 7.4.0 + GotoBLAS2 for Sandy Bridge : 110.980秒
SDPA 7.4.0 + Intel MKL 10.3.4-191 : 124.042秒
SDPA 7.4.0 + Intel MKL 10.3.5-220 : 123.984秒
SDPA 7.4.0 + Intel MKL 10.3.6-233 : 123.915秒

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

Intel® C++ and Fortran Composer XE for Linux 2011.5.220 から 2011.6.233

Intel Compiler と MKL を 2011.5.220 から 2011.6.233 にバージョンアップした。以下のように特に性能向上は見られない。むしろ遅くなる場合も多くなっている。

◯ソフトウェア SDPARA 7.3.3

◯問題：nug14_r2.dat-s
2011.5.220 : 402.99秒
2011.6.233 : 405.62秒

◯問題：Be.1S.SV.pqgt1t2p.dat-s
2011.5.220 : 312.26秒
2011.6.233 : 311.76秒

○ 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.6 for x86_64

ポストペタスケールシステムにおける超大規模グラフ最適化基盤：イノベーションジャパン 2011

イノベーションジャパン 2011 で研究の展示中です。21 日は台風の影響で例年よりもかなり参加者が少なかったようです。22 日は例年通りの参加者になると予想されます。

名　称 イノベーション・ジャパン2011‐大学見本市
会　期

2011年9月21日（水）～22日（木）
［9月21日(水）9:30～17:30］
［9月22日(木）10:00～17:00］

会　場 東京国際フォーラム（東京・有楽町）
入場料 無料

最短路検索を用いた大規模ネットワーク解析システム

技術の概要

ポストペタスケール環境における超大規模グラフ最適化システムの構築を行う。具体的には大規模グラフデータに対するリアルタイムストリーミング処理、計算量とデータ移動量を考慮したグラフ最適化アルゴリズム、ストレージの階層性を考慮した大規模グラフデータストア、超大規模グラフのリアルタイム可視化など従来実現されていなかった新しい技術によって超大規模グラフに対する高速最適化＆解析システムを実現する。

研究紹介のパンフレット

DSETツールによるログ採取

クラスタ計算機は現在の３台で異常が発生中となっていて全面復旧の見込みは立っていない。エラーが発生する度に以下の DSET ツールでログを採取して Dell のカスタマーサポートに送ることになる。



Dell PowerEdge シリーズ DSET ツールの使用方法

ログ採取の概要は以下の通り。

[root@opt01 ~]# sh ./delldset_v2.2.125_x64_A01.bin

Do you accept the terms of this license? (y/n): y

Dell System E-Support Tool (DSET) Options:


Choose an option:

1) Read DSET Release Notes First
Show latest information concerning features and known issues

2) Create DSET Report Only
Creates a DSET report and saves it to user's home directory

3) Clear ESM Hardware Log Only
Only clears the ESM Hardware Log contents

4) Install/Upgrade DSET Application
Permanently installs or upgrades the DSET application for repeat use

Enter option (1-4) or 'q' to quit: 2

Your Information:
Please enter your company name and e-mail address.
This information is optional but will help Dell Technical Support
when analyzing your report.

Company Name:
Your E-mail:

Preparing DSET components to create a report. One moment ...

Choose Report options:

Skip collecting info for all hardware categories(y/n): n
Skip collecting info for all storage categories(y/n): n
Skip collecting info for all software categories(y/n): n
Skip collecting any non-Linux log files(y/n): n
Append report filename with timestamp(y/n): y
Collect various advanced logs(y/n): y
Do you need to store in a different location(y/n): y
Specify the file name, file path or both: n
The options selected for the report are: --time --advanced -f n
Dell System E-Support Tool
@Copyright Dell Inc. 2004-2011 Version 2.2 build 125
* Collecting Dell OpenManage information ... [Please wait]

*** WARNING: Do not terminate this process, as it may affect the existing OMSA installation ***

* Getting Linux system summary information ...
Gathering Network Information ...
Gathering OS Summary Information ...
* Getting Linux operating system configuration information ...
Gathering Boot Information ...
Gathering Module Information ...
Gathering Memory Information ...
Gathering Storage Information ...
Gathering Network Information
Gathering Summary Information ...
* Gathering chassis information...
* Gathering DRAC Information...
* Converting DRAC txt information to XML format...
* Gathering storage information...
Note: Scanning for supported SCSI or RAID controllers... [please wait]
* Collecting storage information...
* Transforming XML files ...
* Creating table of contents ...
* Collecting various system logs and configuration files ...
* Gathering OpenManage logs...
* Collecting various OpenManage logs...
* Compressing report...
A compressed, encrypted ZIP report archive was saved at: /root/n-on-09-21-2011-at-02-01-AM.zip

Syntax: unzip <reportname> -d <newdirectory>
* Report creation completed successfully

これで作成された zip ファイルを送付すればよい。

ORセミナー

まだホームページ等には出ておりませんが、今年も OR セミナーで講師を務めることになりました(10月21日に開催予定：場所は昨年と同じ)

昨年は以下の内容で講演させていただきましたが、今年は非常に簡単で基礎的な内容で行う予定です。

◯昨年の題名、内容
21世紀の最適化、SDPのモデリングと応用及び大規模計算
概要：SDP が最近注目される理由としては次のような事項を挙げることができる。
1: 高速かつ安定したアルゴリズムが存在する 2: 問題解決能力が大きい 3: 応用分野が広い 4: ソフトウェアの整備が進んでいる
本講演ではこれらの事項について解説すると共に大規模な SDP を解くための最新の研究と成果についても触れていく。

◯今年の題名、内容
最適化（数理計画）問題の基礎
概要：線形計画問題や整数計画問題などを中心に最適化問題の基本的な考え方や定式化の方法について解説を行う。またExcel内の最適化ソルバーを用いて簡単な例題を解いていくことによって、最適化問題を解く手順等を感覚的に理解できるようにしていく。最後に最適化ソルバーに関する最新の研究や今後の展開についても簡単に解説する予定である。

京のすべて

日経 Linux 10 月号の 90 から 98 ページに
”究極の Linux 機！スパコン世界一「京」の全貌”
という解説記事が掲載されている。
この記事と重複する内容も多いが、こちらでも京の情報が公開されている。紙面の都合や情報公開に関する方針等もあって、ソフトウェアや性能に関する情報はあまり含まれていないようだ。

最適化理論の産業・諸科学への応用

最適化理論の産業・諸科学への応用というシンポジウムが以下のように１０月１３、１４日開催されます。場所が遠いのが難点ですが、ご興味がある方は是非ご参加下さい。

日時　： 2011年10月13日(木)9:55～14日(金)16：00
場所　： 九大伊都キャンパス 数理学研究教育棟 ( 福岡市地下鉄 時刻表 昭和バス九州大学線 時刻表 )
内容　： 最適化理論とその応用に関する最近の研究の動向と将来の方向性を探るため，最適化理論に関連する幅広い分野から講演者をお招きし講演して頂きます．

プログラム(9月14日現在)
講演者(50音順)．
恐神貴行氏(日本IBM 東京基礎研) 半正定値計画を用いた確率モデルの解析
神山直之氏(中央大) 安定マッチングモデルに対するアルゴリズムの最近の進展
来嶋秀治氏(九大) 確率と計算
小島政和氏(東工大) (1) 半正定値計画問題への招待 (2) 半正定値計画緩和による大域的最適化
武田朗子氏(慶應大) 数理最適化の視点から機械学習へのアプローチ
田中利幸氏(京都大) TBA
藤澤克樹氏(中央大) ポストペタスケールシステムにおける超大規模グラフ最適化基盤
三好直人氏(東工大) 半正定値計画を用いた拡散過程の数値計算
村松正和氏(電通大) 多項式計画に対する半正定値緩和の不思議な性質
室田一雄氏(東大) 半正定値計画と対称性

かなりハードな MIP その７

7月ぐらいにこのブログで触れていた MIP の件だが、結局既存の MIP ソルバー等では簡単に解くことができなかったが、手動による前処理とソルバーによる求解によって最適解が求められた。

最適値 235
最適解の1つ（以下の変数が1）
X122,X167,X217,X275,X292,X302,X305,X307,X007,X012,
X022,X032,X042,X057,X062,X077,X087,X092,X107,X112,
X137,X147,X152,X172,X187,X197,X207,X225,X235,X245,
X255,X265,X285

【元問題】
変数312個（自由連続変数 2個, 0-1変数310個）
【ソルバーが簡略した元問題】
変数310個（0-1変数310個）
制約式60本