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

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

スケジューリング学会シンポジウム:大規模災害からの避難計画

2012年09月30日 00時26分33秒 | Weblog
スケジューリング学会シンポジウム(2012年9月29、30日:成蹊大学)で以下の特別セッションを行います。JST CREST でのグラフ探索プロジェクトとも関連性の高い内容です。


大規模災害からの避難計画【9:00~11:00】

OS3-1 大地震時における広域避難行動シミュレーション
○沖 拓弥, 大佛 俊秦 (東京工業大学大学院)

[概要] 本稿では,市街地における広域避難時の安全性を人々の避難場所への到達可能性というミクロな視点から捉え,①大地震時に生じる建物倒壊,市街地延焼,道路閉塞といった物的被害を記述するモデルを構築し,②パーソントリップ調査のデータから施設内滞留者と歩行者の時空間分布を推定し,③人々が大地震発生時の居場所から避難場所に向かうまでの避難行動をモデル化し,④現実のデータを用いて避難行動シミュレーションを行った。本稿で構築したシミュレーションモデルは,物的被害パターンや発災時刻の違いを加味し、広域避難時に人々が危険にさらされる可能性の高い地域を街区レベルのミクロな空間単位で特定できるだけでなく、人々の持つ属性(性別,年齢階層,職業など)や市街地の建物用途分布の違いも考慮できる。また、市街地の様々な空間性状と避難困難率の関係や、地域間比較、発災時刻の違いによる影響などに関する考察を行った。

OS3-2 津波避難シミュレーションによる避難計画策定支援
○志村 秦知, 北上 靖大, 森 俊勝 (株式会社構造計画研究所)

[概要] これまで災害対策として、防波堤・堤防の構築や 避難施設の構築,情報インフラ整備などハード面の対策に力が入れられてきた。しかし、東日本大震災の教訓から、人的被害を最小限にするためには、津波の到 達を防ぐ、または遅らせるといったハード面の対策に加えて、住民の早期避難の計画や防災意識の向上などのソフト面の対策が重要であることが指摘されている。ソフト面の対策である避難計画の策定に当たっては、津波の到達までに住民が高台、避難施設などの一時避難場所に到着可能かどうか、到着を可能にする方法はどのようなものかなどを検討する必要がある。そこで本発表では、避難弱者や防災知識の有無などの個々の特性や避難行動を考慮できるシミュレーションを中心に、避難困難地域の把握、避難プロセスの把握、避難誘導の評価、避難時ルールの周知度による影響の予測などによって避難計画策定を支援する津波避難シミュレーションについて紹介する。

OS3-3 緊急避難行動の動的ネットワークフローモデルとその応用
○瀧澤 重志, 加藤 直樹 (京都大学)

[概要] 避難行動をモデル化する研究は,土木や建築分野を中心として行われてきた.例えば土木分野では均衡流等に基づく交通流モデルを用いた研究が進んでおり,建築分野ではマルチエージェントモデルを応用した研究が行われている.一方,離散アルゴリズムの分野では,動的ネットワークフローを元にした避難計画の研究が進んできた.この分野で扱われるモデルは前者のモデルと比較して現実の条件の記述力がやや弱い面があるが,その反面,計算効率や最速避難完了時間を理論的に導出できるといった,他のモデルにはない利点を有している.本発表では,筆者らがこれまで行ってきた,動的ネットワークフローの枠組みによる避難計画問題に関する,津波避難などを含むいくつかの研究を紹介するとともに,近年行っている研究についても紹介したい.

OS3-4 東日本大震災後計画運転時の首都圏電車ネットワーク混雑シミュレーション
○田口 東 (中央大学)

[概要] 東京首都圏の鉄道網は,30の事業者,130路線,1800駅, 8000本の電車(いずれも概数)からなる大規模で広範囲なネットワークを形成しており,800万人の通勤通学客が移動している.これに対して,時刻表通りの電車運行を表現する時空間ネットワーク,通勤通学客の移動データ,利用者均衡に基づく電車選択ルールを用いて表現する数理モデルを構成している.昨年春,東日本大震災による電力供給不足に対応するため,電車運転本数の削減が行われた.輸送力削減の利用者に対する影響は,平常時に一緒にいる利用者の多寡だけでなく,ネットワーク全体から利用路線が受ける影響による.鉄道の混雑を和らげる決め手は,利用者による分散乗車である.ここでは,ネットワーク全体を対象として,分散乗車の詳細なシミュレーションを行ってその効果が提示できることを示し,分散乗車を説得する基礎となる実現目標を具体化できることを示す.
コメント
この記事をはてなブックマークに追加

次回:第25回 RAMP シンポジウム

2012年09月29日 01時02分52秒 | Weblog
まだ本決定ではありませんが、次回(第25回)シンポジウムの予定です。

場所:鹿児島大学稲森会館
日時:2013年10月(未定)
プログラム及びオーガナイザー:未定

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

3GTEPS の制限:その2

2012年09月28日 01時47分21秒 | Weblog
昨日は 3GTEPS の壁という話をしたが、さすがに以下のマシン(AMD Opteron 6174 x 4)では 3GTEPS を軽く超える。その値は 5.84GTEPS になっている。

----------------------------------------------------------------------
Parallel Breadth-First Search for Graph500 Benchmark version 3.44
----------------------------------------------------------------------
CPU name is AMD Opteron(tm) Processor 6174
freq / RAM is 2199.975 MHz / 251.91 GB
#cpu, #nodes, #cores is 48 8 6
COMPILER is GCC (GNU C Compiler) version 4.7.2
----------------------------------------------------------------------
scale, edgefactor is 25 16
energy_loop is disable
#threads, #NUMAs is 48 8
mpol_bind is ON(mmap with mbind(MPOL_BIND))
mem_interleave is OFF
switching parameter is 0.000035 (n ~= 1.174405e+03)
queue buffer size is 65536
----------------------------------------------------------------------
SCALE: 25
nvtx: 33554432
edgefactor: 16
terasize: 8.58993459199999983e-03
A: 5.69999999999999951e-01
B: 1.90000000000000002e-01
C: 1.90000000000000002e-01
D: 5.00000000000000444e-02
generation_time: 1.67543580532073975e+01
construction_time: 1.58551478385925293e+01
nbfs: 64
min_time: 7.30950832366943359e-02
firstquartile_time: 7.78018832206726074e-02
median_time: 9.18971300125122070e-02
thirdquartile_time: 1.07358932495117188e-01
max_time: 1.30918025970458984e-01
mean_time: 9.39249694347381592e-02
stddev_time: 1.62639719317221459e-02
min_nedge: 5.36865498000000000e+08
firstquartile_nedge: 5.36865498000000000e+08
median_nedge: 5.36865498000000000e+08
thirdquartile_nedge: 5.36865498000000000e+08
max_nedge: 5.36865498000000000e+08
mean_nedge: 5.36865498000000000e+08
stddev_nedge: 0.00000000000000000e+00
min_TEPS: 4.10077599337726879e+09
firstquartile_TEPS: 5.21346694917975998e+09
median_TEPS: 5.84458185425835419e+09
thirdquartile_TEPS: 7.03729207755900383e+09
max_TEPS: 7.34475527254737568e+09
harmonic_mean_TEPS: 5.71589750021723461e+09
harmonic_stddev_TEPS: 1.24698064099856243e+08
コメント
この記事をはてなブックマークに追加

3GTEPS の壁

2012年09月27日 00時58分54秒 | Weblog
以下の Intel Xeon X5690 3.47GHz x 2 マシン(メモリ192GB)だが、median_TEPS で 3G を超えていない。他のサーバでも 3G を超えることは出来ていない。ちなみに1ノードで 3G を超えているのは Intel Xeon Westmere-EX 2.4GHz x 4 マシンと Xeon Sandybridge-EP 2.9GHz x 2 マシンのみとなっている。

----------------------------------------------------------------------
Parallel Breadth-First Search for Graph500 Benchmark version 3.44
----------------------------------------------------------------------
CPU name is Intel(R) Xeon(R) CPU X5690 @ 3.47GHz
freq / RAM is 3466.864 MHz / 189.15 GB
#cpu, #nodes, #cores is 24 2 12
COMPILER is GCC (GNU C Compiler) version 4.4.6
----------------------------------------------------------------------
scale, edgefactor is 25 16
energy_loop is disable
#threads, #NUMAs is 24 2
mpol_bind is ON(mmap with mbind(MPOL_BIND))
mem_interleave is OFF
switching parameter is 0.000035 (n ~= 1.174405e+03)
queue buffer size is 65536
----------------------------------------------------------------------
SCALE: 25
nvtx: 33554432
edgefactor: 16
terasize: 8.58993459199999983e-03
A: 5.69999999999999951e-01
B: 1.90000000000000002e-01
C: 1.90000000000000002e-01
D: 5.00000000000000444e-02
generation_time: 2.82982687950134277e+01
construction_time: 2.94177212715148926e+01
nbfs: 64
min_time: 1.57860040664672852e-01
firstquartile_time: 1.71346008777618408e-01
median_time: 1.91974878311157227e-01
thirdquartile_time: 2.08445191383361816e-01
max_time: 2.88492918014526367e-01
mean_time: 1.94484390318393707e-01
stddev_time: 3.09511709459013712e-02
min_nedge: 5.36865498000000000e+08
firstquartile_nedge: 5.36865498000000000e+08
median_nedge: 5.36865498000000000e+08
thirdquartile_nedge: 5.36865498000000000e+08
max_nedge: 5.36865498000000000e+08
mean_nedge: 5.36865498000000000e+08
stddev_nedge: 0.00000000000000000e+00
min_TEPS: 1.86093128973435473e+09
firstquartile_TEPS: 2.59243812652744484e+09
median_TEPS: 2.80723269125115538e+09
thirdquartile_TEPS: 3.15244983066783619e+09
max_TEPS: 3.40089547512794924e+09
harmonic_mean_TEPS: 2.76045546442615938e+09
harmonic_stddev_TEPS: 5.53481111342410892e+07
コメント
この記事をはてなブックマークに追加

第24回 RAMP シンポジウム 前日

2012年09月26日 01時05分28秒 | Weblog
いよいよ RAMP シンポジウムが明日に迫ってきました。当日参加も大歓迎ですので是非ご参加ください。

----------------------------------------------------------------------------
RAMPシンポジウムは,日本オペレーションズ・リサーチ学会の数理計画研究部会
(RAMP: Research Association of Mathematical Programming) によって
年一度開催される,最適化・数理計画に関するシンポジウムです.
今年は仙台にて9月の27,28日に開催されます.

シンポジウムのプログラムも充実したものとなっておりますが,
懇親会の方も仙台ならではの食べ物,日本酒を用意しております.
懇親会の参加人数を見積もる都合上,懇親会参加申し込みがまだの方は
メールで構いませんので,事前に実行委員会までご連絡いただければ幸いです.

日時 : 2012年9月27日(木),28日(金)
会場 : 東北大学 片平キャンパス・さくらホール
(仙台駅から近いキャンパスでの開催です)
http://orsj.or.jp/ramp/2012/index.html

実行委員長:
村松 正和(電気通信大学)
塩浦 昭義(東北大学)
コメント
この記事をはてなブックマークに追加

10GTEPS 越え

2012年09月25日 22時38分48秒 | Weblog
ついに1ノードで 10GTEPS(median_TEPS)を越えるようになった。実行は 80 コア(HT) で Scale は 26 となっている。

----------------------------------------------------------------------
Parallel Breadth-First Search for Graph500 Benchmark version 3.44
----------------------------------------------------------------------
CPU name is Intel(R) Xeon(R) CPU E7- 4870 @ 2.40GHz
freq / RAM is 2400.149 MHz / 504.78 GB
#cpu, #nodes, #cores is 80 4 20
COMPILER is GCC (GNU C Compiler) version 4.4.6
----------------------------------------------------------------------
scale, edgefactor is 26 16
energy_loop is disable
#threads, #NUMAs is 80 4
mpol_bind is ON(mmap with mbind(MPOL_BIND))
mem_interleave is OFF
switching parameter is 0.000035 (n ~= 2.348810e+03)
queue buffer size is 65536
----------------------------------------------------------------------
SCALE: 26
nvtx: 67108864
edgefactor: 16
terasize: 1.71798691839999997e-02
A: 5.69999999999999951e-01
B: 1.90000000000000002e-01
C: 1.90000000000000002e-01
D: 5.00000000000000444e-02
generation_time: 2.53357210159301758e+01
construction_time: 1.96022217273712158e+01
nbfs: 64
min_time: 9.60519313812255859e-02
firstquartile_time: 1.04277431964874268e-01
median_time: 1.06773018836975098e-01
thirdquartile_time: 1.15906953811645508e-01
max_time: 3.73064994812011719e-01
mean_time: 1.38678360730409622e-01
stddev_time: 7.97296027813284292e-02
min_nedge: 1.07373120400000000e+09
firstquartile_nedge: 1.07373120400000000e+09
median_nedge: 1.07373120400000000e+09
thirdquartile_nedge: 1.07373120400000000e+09
max_nedge: 1.07373120400000000e+09
mean_nedge: 1.07373120400000000e+09
stddev_nedge: 0.00000000000000000e+00
min_TEPS: 2.87813442411303043e+09
firstquartile_TEPS: 9.37520035705756378e+09
median_TEPS: 1.00686062340452461e+10
thirdquartile_TEPS: 1.03184288991767941e+10
max_TEPS: 1.11786529282624359e+10
harmonic_mean_TEPS: 7.74260092450422573e+09
harmonic_stddev_TEPS: 5.60825176113054872e+08
コメント
この記事をはてなブックマークに追加

Graph500 解説記事

2012年09月24日 00時58分50秒 | Weblog
Graph500 に関する日本語の解説記事は以下が一番早いかどうかはわからないが、相当早い段階で書かれたことは間違いない。今見ても結構詳しく書かれていると感じる。

藤澤克樹, 安井雄一郎, 高宮安仁, 佐藤仁, 最適化分野におけるクラウド技術の利用, オペレーションズ・リサーチ, Vol. 56, No. 6, pp. 318-324, 2011.

目次
1: はじめに
2: クラウドによる計算資源の動的な確保
3: グラフ探索と応用
4: 最短路を用いたグラフ解析
5: Graph500
コメント
この記事をはてなブックマークに追加

IBM Blue Gene/Q

2012年09月23日 21時44分58秒 | Weblog
IBM の Blue Gene/Q は各 CPU からラックまでが以下のような構成になっている。

http://news.mynavi.jp/articles/2011/12/13/blugeneq/index.html


IBM BG/Q(Sequoiaのピーク性能):4 FPU x 2演算(FMA) x 16コア x 1.6GHz (ここまで 1CPU = 204.8GFlops) x 32 カード x 16 ノード x 2 ミッドプレーン x 96 ラック = 20.133PFlops

BG/Q チップの特徴
◯16+1 core SMP:OS 用のコアが一つある
◯Each core 4-way hardware threaded:データインテンシブ系のアプリでは巨大な疎データに対するランダムアクセスが発生するので、スレッドを多数作って、レイテンシを隠蔽するやり方は有効

その他の特徴
◯Transactional memory and thread level speculation
◯Quad floating point unit on each core
◯204.8 GF peak node
◯Frequency: 1.6 GHz
◯563 GB/s bisection bandwidth to shared L2(Blue Gene/L at LLNL has 700 GB/s for system)
◯32 MB shared L2 cache
◯42.6 GB/s DDR3 bandwidth (1.333 GHz DDR3)
コメント
この記事をはてなブックマークに追加

2012年度 第1回 ORセミナー 『Excelで学ぶOR』

2012年09月22日 02時41分30秒 | Weblog
昨日以下のORセミナーを開催しました。一部の中身については少し難しいところがあったかもしれません。来年度のセミナー実施については未定です。その他の気付いた点ですが、

◯ Windows の Excel 2010 及び 2007 では普通に Excel での実行は可
◯ Mac の Excel 2011 でもソルバーの実行は可能。Excel 2008 ではインターネットでソルバーをダウンロードすれば可
◯ Excel で学ぶ OR の本では Excel の基本的な使用方法は書いていないので、Excel については別途学習が必要

開催趣旨:基礎からOR を学びたい受講者を対象とする。Excel を用いて実際にデータを入力して、ソルバーを用いて問題を解くことによって、ORの基本(モデリングや定式化)から様々な応用分野を具体的な問題例を通じて学習することを目的とする。参加者は予めExcel(2003以降可、2010推奨)をインストールしたノートパソコンを持参することによって講義及び演習形式でセミナーを行っていく。

日 時 2012年9月21日(金) 10:00~17:40
会 場  (株)構造計画研究所 本所新館(地下1階 レクチャールーム) 
コメント
この記事をはてなブックマークに追加

Graph500 と 4th List の更新

2012年09月21日 00時59分44秒 | Weblog
Graph500 4th List が更新されている。

◯Convey 抜いて正式に1ノード性能で世界一(25th rank : 8.15GTEPS)
◯TSUBAME 2.0 も GPU と CPU で2個ベスト10にエントリー。

なお SC12(11月)から、正式に Green Graph500 が開始される予定。
コメント (1)
この記事をはてなブックマークに追加

Graph500 とGreen Graph500 に関する話題

2012年09月20日 00時23分23秒 | Weblog
◯Green Graph500 の参照実装と ISC12 での発表スライド公開中

green.graph500.org

参照実装は基本的に Graph500 と同じ。時間測定用に BFS 64 回の部分だけ指定時間だけ繰り返すことができる。

◯IBM BG/Q(Sequoia) : Graph500 ベンチマークで Scale 39(0.5兆点, 8兆枝) & 4500GTEPS を達成。このサイズ(Scale 39)でも 1秒でグラフ探索(BFS)ができることになる。
コメント
この記事をはてなブックマークに追加

JST ポストペタ CREST 講演会

2012年09月19日 01時04分30秒 | Weblog
以下の日時で JST ポストペタ CREST 主催の講演会を開催します。講演内容は第3回 KSMAP 研究会と同じものになります。京都で参加できない方はこちらにご参加ください。講師の日程上の都合によりまして、9月26日と10月1日の2回分けて開催します。


◯JST ポストペタ CREST 主催講演会
場所:中央大学後楽園キャンパス2号館8階2822号室
http://www.chuo-u.ac.jp/chuo-u/access/access_korakuen_j.html

◯9月26日(水):16:00~17:00

Speaker: Stefan Vigerske (GAMS Software GmbH)

Title: Solving MINLPs with SCIP

Abstract: We discuss recent extensions of the constraint integer programming
framework SCIP for solving mixed-integer nonlinear programs.
Nonlinear constraints (convex or nonconvex) are handled within an
LP-based branch-and-cut algorithm by reformulation, linear relaxation,
and domain propagation. In an extensive computational study, we
compare the performance of our implementation with state-of-the-art
solvers for MINLP and analyze the impact of various solver components
on the overall performance.

◯10月1日(月): 13:30 ~ 15:45

Speaker: Ted Ralphs (Lehigh University)

Title: Complexity and Multi-level Optimization

Abstract: Many real-world optimization problems involve multiple decision-makers, multiple
objectives, and/or decisions that are made in multiple stages. Such problems arise both in practical
applications (game theory, stochastic programming) and in theoretical contexts (analysis of
recursive algorithms). The computational complexity of such problems is often difficult to discern,
but can generally be understood in terms of the so-called "polynomial time hierarchy," of which the
classes P and NP are the first two levels. In this talk, we discuss the
complexity of and relationships between a number of related problem classes, focusing specifically
on multi-level problems with discrete decisions at some or all levels/stages. We present a new
result that shows that the separation problem for a certain strengthened version of the well-known
generalized subtour elimination constraints is not in NP unless the polynomial time hierarchy
collapses to its second level.


Speaker: Thorsten Koch (Zuse Institute Berlin)

Title: What Could a Million Cores Do To Solve Integer Programs?

Abstract: Given the steady increase in cores per CPU, it is only a matter of time until
supercomputers will have a million or more cores. In this talk, we investigate the opportunities and
challenges that will arise when trying to utilize this vast computing power to solve a single
integer linear optimization problem. We also raise the question of whether best practices in
sequential solution of ILPs will be effective in massively parallel environments.
コメント
この記事をはてなブックマークに追加

「OR横断若手の会 (通称 KSMAP)」の第3回研究会開催

2012年09月18日 00時56分52秒 | Weblog
以下の日時で「OR横断若手の会 (通称 KSMAP)」の第3回研究会開催が開催されます。Ted Ralphs 氏とThorsten Koch 氏については RAMP シンポジウム でも発表されますが、これに加えて10月1日午後に中央大学(東京)でも講演予定です。また Stefan Vigerske氏は 9月26日の午後に中央大学で講演予定です。

<< 開 催 要 領 >>

●第 3 回研究会
日時:10 月 6 日 (土) 14:00 ~ 17:20
場所:京都大学 総合研究8号館 講義室3
  (2011年度まで工学部8号館と呼ばれていた建物です)

[京都大学周辺地図] http://www.kyoto-u.ac.jp/ja/access/campus/map5r.htm
[京都大学構内地図] http://www.kyoto-u.ac.jp/ja/access/campus/map6r_n.htm

-------------------------------------------------------------------
テーマと講師:

14:00 ~ 15:00
(1) Ted Ralphs (Lehigh University)
「Complexity and Multi-level Optimization」

Many real-world optimization problems involve multiple decision-makers,
multiple
objectives, and/or decisions that are made in multiple stages. Such
problems arise both in practical applications (game theory, stochastic
programming) and in theoretical contexts (analysis of recursive
algorithms). The computational complexity of such problems is often
difficult to discern, but can generally be understood in terms of the
so-called "polynomial time hierarchy," of which the classes P and NP are
the first two levels. In this talk, we discuss the complexity of and
relationships between a number of related problem classes, focusing
specifically on multi-level problems with discrete decisions at some or
all levels/stages. We present a new result that shows that the
separation problem for a certain strengthened version of the well-known
generalized subtour elimination constraints is not in NP unless the
polynomial time hierarchy collapses to its second level.

15:10 ~ 16:10
(2) Stefan Vigerske (GAMS Software GmbH)
「Solving MINLPs with SCIP」

We discuss recent extensions of the constraint integer programming
framework SCIP for solving mixed-integer nonlinear programs. Nonlinear
constraints (convex or nonconvex) are handled within an LP-based
branch-and-cut algorithm by reformulation, linear relaxation, and domain
propagation. In an extensive computational study, we compare the
performance of our implementation with state-of-the-art solvers for
MINLP and analyze the impact of various solver components on the overall
performance.

16:20 ~ 17:20
(3) Thorsten Koch (Zuse Institute Berlin)
「What Could a Million Cores Do To Solve Integer Programs?」

Given the steady increase in cores per CPU, it is only a matter of time
until
supercomputers will have a million or more cores. In this talk, we
investigate the opportunities and challenges that will arise when trying
to utilize this vast computing power to solve a single
integer linear optimization problem. We also raise the question of
whether best practices in sequential solution of ILPs will be effective
in massively parallel environments.


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

SDPARA-G 用の新クラスタ その2

2012年09月17日 01時48分14秒 | Weblog
以下の新クラスタ(4台)についての SDPARA-G の結果。そんなに性能値は悪くはないのかもしれないが、もっと性能を上げていきたいところ。

◯Cholesky 分解:
行列サイズ = 286552
ブロックサイズ = 1024
実行時間 = 2746.040017秒
性能値 = 2856.157914GFlops

◯ GPU 計算サーバ:Intel Xeon + 4 GPU マシン(4台)
CPU:Xeon X5690(3.46GHz,6コア)×2
メモリ:192GB(16GB×12)
HDD:SATA500GB×2(システム、システムバックアップ)
NIC : GbE x 1 & Inifiniband(FDR) x 1
GPGPU:Tesla C2075(C2070)×4
OS:CentOS 6.3 for x86_64

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

Graph500 電力測定中 その6

2012年09月16日 03時19分47秒 | Weblog
Graph500 の電力測定を行っているのだが、GTEPS/kW の指標で比較すると

Android タブレット(携帯電話も) >> MacBook Air >> 計算サーバ(SandyBridge-EP等) >> スパコン

となっている。電力測定の方法も異なってくるので、厳密な比較は難しいのだが Tegra3 あたりの CPU は単に消費電力が少ないだけでなく絶対的な性能もそこそこ高い。ビッグデータ処理と言っても常にスパコンを使えるわけではないので、やはり1台(タブレット等も含めて)での処理性能も非常に重要となっている。
コメント
この記事をはてなブックマークに追加