資料2

HPC による計算社会科学
産業技術総合研究所

野田五十樹

計算社会科学とHPC●マルチエージェント社会シミュレーションを中心として（人工知能アプローチ）▶ 事例 交通シミュレーション
 人流シミュレーション
 市場シミュレーション▶ 計算社会科学で必要なもの

2

まとめ●計算社会科学をより実用的にするには、▶ 非常に多数の試行を効率的かつ気軽に実施。
 多岐にわたる条件を網羅する必要。
 繰り返しデータ同化・パラメータ探索の必要性。
 真の人のモデル・社会の初期条件の不可知性を補完。

▶ 離散データ、構造化データをnativeでサポート。
 表現の柔軟性。
 データとしてのプログラム。

●次世代HPCに望まれる要件▶ 数値計算偏重でない開発環境。
 多様なプログラム言語サポート。
 通常のPCとのシームレスなエコシステム。

▶ 柔軟なジョブ管理。
 ブロック単位でのジョブ割り付けを柔軟化。
 ジョブ実行の仮想化？

3

交通 シミュレーション

オンデマンド交通サービス●Smart Access Vehicle(SAV) System▶ 主目的：都市生活者へのモビリティの提供
 公共交通の充実▶ 特徴
 バス＋タクシー（乗り合いタクシー or オンデマンドバス）
 全自動
 シミュレーションと連動▶ 共同研究 はこだて未来大学
 産業技術総合研究所
 名古屋大学

5

システム概要
 (1) リクエスト (乗降地・希望時刻・人数)
 (2) 送迎要求 (経由点リスト、利用者リスト）
 (3) 配車案内（予定時刻・号車）
 (*) 走行情報（現在地等)(1)リクエスト(3)配車案内(2)送迎要求(*)走行情報

解くべき問題●そもそも、オンデマンド型交通サービスは成り立つのか？
▶ どういう場合にメリットがあるのか？

●最適配車？
●メリットを最大化する条件は？
▶ 何台、運行すべきか？
 採算性とサービスの質の関係は？

▶ どれくらいの範囲をカバーすべきか？
 どらくらいの地域と人を対象とするのか？

計算社会科学での共通の視点
7

On-demand Bus Simulation●Comparison of fixed-route and on-demand bus systems▶ scalability▶ city types

0 center

1 center

2 centers

Scale Merit of On-demand Bus
work with Prof. Nakashima, Future Univ. Hakodate8

Comparison under Optimum Operation●on-demand bus▶ “successive bestinsertion”●fixed-route bus▶ genetic algorithm
 to find the best route to find the best bus

assignments

assignment by auction

Compare travel time under●same number of bus●
same number of demand9

結果1●利用者数に応じてバス台数を増減

結果2●一極集中・二極集中の場合
0 center

1 center

条件により得手・不得手
条件により得手・不得手がある。
がある。
●● その条件は必ずしも自明
その条件は必ずしも自明ではない。
ではない。
●●2 centers函館スマートシティプロジェクト
はこだて未来大・産総研・名大●SAVS (Smart Access VehicleService)▶ オンデマンドバス（乗り合いタクシー)▶ サービス連携も可能◆ 病院◆ ショッピングモール◆ 観光●シミュレーションによる利便性総合評価▶ 多様な状況での評価▶ 普及過程も評価
12

シミュレーション評価と運用規模の決定●人工知能学会@函館にむけて▶ 1000人の参加者に何台必要か?
 いろいろな条件でシミュレーション評価（待ち時間評価）◆ 結果 : 通常日で20台、繁忙日で30台.

middle size car

requests per hour

# of vehicles

Wagon type

requests per hour

wait time (normalized)

wait time (normalized)◆ 実データと比較：ほぼシミュレーションと同等の結果。

# of vehicles

13

市民全員がSAVSを使うと?
●全函館市民が自家用車を捨て、SAVSを利用すると、何台必要か？
25000 demands per day

wait time (sec.)

wait time (sec.)

5000 demands per day

demand orders

demand orders

14

漸近的普及と利便性

300 trip / day

10000 trip / day3000 trip / day

30000 trip / day15

Whole Japan・Whole World
Traffic Simulation●Whole Japan●Whole World 8 millions links, 12 millions vehicles

 100 millions links, 100 millions

vehicles real time simulationTokyo using 20K nodes of K-Computer no intelligence in agents

5000

時間

500

Kobe時間
地図作成時間50

ファイル時間Performance of Parallelism

550

500

5000

50000

Roma計算量ロードマップ（交通制御・分析）
ポストペタ

106
京クラス HPC

排他制御105全国・簡易Sim.

密結合クラウド全国・イベント
全国・交通規制 全国・交通流相関分析

104103

クラスタ
102

X10, XAXIS

1runの計算量（メモリ量・演算量・通信量）

107

全国・仮想交通流

東京・イベント
首都圏・交通規制

32core101

首都圏・イベント展
時間発

東京・交通規制
神戸・簡易Sim.
地方都市・交通規制

10

5,10年後
経済・OD変化0

実行計画最適化

ナイロビ・信号制御
OACIS

Xeon 1core
1週間
100

101

102

CARAVAN
103

104

105

10 6107

場合の数

経済 シミュレーション

Large Scale Market Simulation
using K-comp. and X10 [東大 和泉潔先生]

Final Target: simulation of whole Tokyo Stock Market (2-3 K stocks, options)

市場シミュレーションによる市場システム評価
市場間競争において、マーケットシェアの維持に必要な tic サイズを、マルチエージェント市場シミュレーションの網羅実行により同定。
② Evaluation by Real Data

① Simulation③ Design of Markets

価格変動

東証シェアの減少

過大なティックサイズ

充分なティックサイズ

価格変動の増大閾値
ティックサイズ

In 2014, different ticksizes are introduced basedon our simulation results

分析結果は、東証のシステム改革の判断材料として活用。
*1 Mizuta, Izumi, et.al., The 8th International Workshop on Agent-based Approach in Economic and Social Complex
Systems , 2013

Market Simulation of Flush Crash.
How the shock on stock-1 spread to whole markets?

東大：和泉潔教授ら

Plham: Platform for large-scaleand high-frequency
Artificial market simulator① h and leO rd ers(List[O rd er])
artificial market
ORIGINAL, FULL INFORMATION
Market Market Market Market

Background

Information
may not be latest;
may be delayed

New trading technologies may fluctuate financial markets.
Flash Crash?

•••

High-frequency trading (HFT)
Portfolio trading
Financial derivatives:if(p) buy()else sell()

COPIED, PARTIAL INFORMATION
Market Market Market Market

Agents

HFT agents② p laceO rd ers(List[M arket])Result 1: Tick size reduction
We found a threshold of the tick size of market
stability by simulation.
The relationship between Tick Size and PTS’s Share

Increase ofPrice Fluctuation
Threshold

Tick Size

PTS’s Share (Upside Down)

Price Fluctuation

Excessive
Tick Size

The impact of shock transfer is determined by
the local traders’ reaction speed to the shock

HFT agents

Agents② p laceO rd ers(List[M arket])Result 3: VaR shock simulation
Introduction of traders with Value-at-Risk
management may destabilize a market# clashDecrease ofTSE’s Share

Sufficient
Tick Size

Result 2: Shock transfer by HFT
arbitrage

COPIED, PARTIAL INFORMATION
Market Market Market Market

VaR management
increased clashes

Multiple stocks
decreased crashesDegree of VaRmanagementロードマップ
京クラス HPC
実行時間の見積もり

モンテカルロ計算

X10, XAXIS

1runの計算量（メモリ量・通信量・演算量）

巨大クラスタ１週間

リスク管理
ボラティリティ歪み

クラスタ
１週間
スケール
アップ

32core
１週間

ポストペタ

複合的社会シミュレーション
システミックリスク（銀行間ネットワーク）
東証丸ごと
シミュレーション

現物 =3400,先物 =300,派生 =200
208 days
京で計算すると：現物 =3400,先物 =300,派生 =200

ポートフォリオ
ポジション管理複数銘柄取引バーゼル規制
銘柄間ネットワーク
現物 =100, 先物 =100, 派生 =10
ショック伝搬
京で計算すると：

3.5 days

裁定取引，ショック伝搬
サーキットブレーカ
現物 =10,先物 =10,派生 =54.16 hours
京で計算すると：

ティックサイズ
値幅制限（時系列的な場合の数）

現物 =1, 先物 =0, 派生 =04.95e-06 sec
京で計算すると：

OACIS

場合の数
探索

CARAVAN
場合の数

人流 シミュレーション

(GAによる多目的最適化)

大阪西淀川区津波避難(ネットワークフロー最大化(藤沢チーム)との比較を目指して。)● スケール▶ 地図：2933ノード、8924リンク▶ 避難者: 49276人▶ OD: 73の町丁目から経由点(533箇所から１つ)を経て

ルール A

エントロピー>

86か所の避難場所へ。
 1町丁目につき、２つのグループに分割。
● 全パラメータ数：365▶ 探索空間は R73×533146×86146● 評価軸:▶ 避難時間▶ 避難誘導ルールの複雑さ
 ＝同じ地区の逃げ方のバリエーションの多さ＝同じ地区からのの異なる逃げ方の人数比の情報エントロピー

ルール B25

改良型NSGA-IIモジュール●NSGA-II：▶ 遺伝的アルゴリズムによる多目的最適化手法
 パレートランキング
 混雑度による子孫選択●部分的世代交代：▶ HPCの並列性の有効活用

26

世代交代とパレート解●大阪市淀川区での避難▶ 車道も使ったシミュレーション(wide)▶ 歩道のみのシミュレーション(narrow)27

Job Scale and Frameworks
class Aclass B

class Cclass D# of jobs

10^0 - 10^210^3 - 10^510^6 - 10^910^9 -# operaionts/job

10^19 - 10^1710^16 - 10^1410^13-10^10

10^9 -flops/jobs

10^18 - 10^1610^15 - 10^1310^12 - 10^910^8 -# of cores/job

10^8 - 10^610^5 - 10^310^2 - 10^-110^-2 -framework

capabilitycomp.

OACISCARAVAN

Map-Reduce

xcrypt

Map-Reduce

capability comp.

granularity of a job

MPI-para

MPI-para

SMP-para / job

functionsize of results- 1 TB- 1 GB- 1 kB- 100 B

how to analyze

by handby hand
/ statistics

statistics

statistics

application example

stencil calc.

replica ex. MC
data assim. for weather

genome analy.

MCMC
optimizationsocial simulation/pedestian/traffic in Tokyo
Tokyo Stock Market

city-level traffic
single market

data-drivenmodelOACIS
Organizing Assistant for Comprehensive and Interactive Simulations●Ruby on Rails + MongoDB, Unix-based OSCARAVAN
optimization, parameter search, data assimilation(implemented by X10, C++, or Python)
management and loadballancing(X10)

Receive parameter sets and return results.
C++ method or external proc.

OACIS/CARAVANによる並列実行性能●OACIS/CARAVAN:●OACIS/CARAVAN+NSGA-II+漸進的世代交代▶ 人流シミュレーション(CrowdWalk)の並列実行
 １実行: 10分 – 30 分

0Time

●京の上での充足率: 95.3%

0Time▶ 社会シミュレーションの大規模網羅的実行支援フレームワーク

10,00020,00030,00040,00050,00060,00070,00010,00080,00090,000100,000

110,000

20,000120,000

0

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

1920

21

22

23

107

ポストペタ

106
京クラス HPC
105
密結合クラウド
10

首都圏・帰宅困難者

4103

クラスタ
102

32core101

100

Xeon 1core
1週間

東京都・複合災害
広域避難（繰り返し）

X10, XAXIS

1runの計算量（メモリ量・演算量・通信量）

人流・避難誘導東京都・複合災害
広域避難（初回）

加要因増

大阪

NSGA-II

千住エリア・複合災害
人口密集地・津波避難
金沢
限定地域・津波避難鎌倉
実験計画法

複合ビル・避難100

101

CARAVAN

OACIS
102

103

104105

10 6

10 7

場合の数

計算社会科学のためのHPC●開発環境
 言語：java, ruby, python,…
 Fortran は使わない。

 テスト環境 = 実行環境
 docker 機能のサポート

 超並列クラウド計算機環境
 MPI より ssh 1コアあたりのメモリが多数。（知識や学習に必要）●並列性
 必要なのは、バカパラ的性能。
 ある意味、性能の無駄遣いかもしれない。
 HPC の専門家は、フルスペック性能ばかり求める。
◆ メモリ効率・CPU効率・通信効率

 計算社会科学では、計算モデル探求が目的。
 モデルの変更が研究そのもの。
◆ モデルを固定して最適化する時間がない。

●運用面
 ジョブのタイプの自由度
 コア数の動的配分、長時間実行

33

計算対象としての社会現象の特徴●モデルが未確定
 人間行動や思考のモデルは開発途上
 数値化・定量化の難しさ
 場合の数によるデータ同化●曖昧な現象境界

試行錯誤・
インタラクティブな分析 非独立事象・相互依存 規模効果 経年変化●不完全なビッグデータ
 不均一・不定形・不正確なデータ
 データの不備を計算で補完する必要。
 シンボル＋パターン

例えば、数時間〜数週間のturn-around time

まとめ
●計算社会科学をより実用的にするには、▶ 非常に多数の試行を効率的かつ気軽に実施。
 多岐にわたる条件を網羅する必要。
 繰り返しデータ同化・パラメータ探索の必要性。
 真の人のモデル・社会の初期条件の不可知性を補完。

▶ 離散データ、構造化データをnativeでサポート。
 表現の柔軟性。
 データとしてのプログラム。

●次世代HPCに望まれる要件▶ 数値計算偏重でない開発環境。
 多様なプログラム言語サポート。
 通常のPCとのシームレスなエコシステム。

▶ 柔軟なジョブ管理。
 ブロック単位でのジョブ割り付けを柔軟化。
 ジョブ実行の仮想化？

35