�ݺ�ߣ

Concurrent Objects, Agents,
and HPC
Aki Yonezawa
Advanced Institute of Computational Science (AICS)
RIKEN, Kobe

My Background,
Current and in the past
? Currently:
�C in charge of the research and operation divisions
of the national supercomputing center, AICS.
�C personally have a keen interest in large scale
agent-based modeling and simulation.
? In the past:
�C have been engaged in research on
concurrent objects and actors,
reflection, mobile objects, ��

Synopsis
? AICS
? Concurrent Objects
? Modeling with mobile/concurrent objects
? Modeling with Agents, my understanding

? (Reflective concurrent objects)
? HPC with concurrent objects
? (ultra) Large scale simulation with Agents
�C Evacuation simulation
�C Traffic simulation

Advanced Institute for Computational Science (AICS)

Has been established as the international
COE for computational sciences and computer science.
Since 2010. (currently ~150 staffs, including 65 researchers)
Missions are:
? Operating the K computer efficiently for users of wide research
areas as well as of industry

? Carrying out the leading edge research of computational science,
promoting strong collaborations between
computer scientists and computational scientists

? Plan and develop Japan's strategy for
computational science, including defining
the path to Exascale computing

Supercomputer K, a 10 peta-flops machine

5

A Glimpse of K Computer

Number of CPUs (nodes) > 80 K
Local file
system
Number of cores > 640K
> 11PB Total memory capacity > 1.7PB

1TB/s 350GB/s

Global file systems
�� 30PB

SPARC64 VIIIfx CPU designed and made by Fujitsu.

Location of AICS & K Computer

Kobe
K Computer Mae
Station

Tokyo

423km (263miles)
west from Tokyo
Research Computer
Building building

Computer room 50m*60m=3,000m2
Chillers Electric power up to 30MW
Substation Supply Gas-turbine cogeneration 5MW*2
Water Cooling System

��HPC�� ?
? In Japan,
��HPC�� should be read as
Highly Political Computing!

? What about in the States or Europe?

? Some episode in Japan��

Televised Congress Hearing
on the plan of K supercomputer (Nov. 2009)
Chairwoman asked:
? Any reason to be No.1?
? why not the second
place is enough?.

She represented the intention
of Ministry of Finance.

Hearing verdict : 100% budget reduction
A big campaign by scientists including 7 Nobel laureates
Whole budget was recovered in March 2010!!!

8 Notable Large-scale Applications on K
? Multi-scale Multi-physics Simulation for Heart
Disease/Disorder (simulation of whole human heart)
? Tsunami Simulation and Disaster Mitigation
? Development of Virus Molecular Science
Based on 10M All-Atom Simulation
? Drug Design Applications
? Next-generation Fluid Design System Based on Direct
Computation of Turbulence
? Reduction of Weather Prediction Period using Global
Cloud Resolving Model (NICAM)
? Simulation of Supernova Explosions based on Neutrino
Heating
? Prediction of electro-functions of nano-structures

Prof. Imamura
Prof. Sugita
(Univ. Tokyo)

UT Heart Simulator Hisada & Sugiura
Finite Element Model
? 1000M
degrees
? of freedon !!

? takes two
days for
one beat

UT Heart is a multi-scale and multi-physics
simulator, starting with physiological models
describing the dynamics of various ion
currents and sarcomeric proteins. UT Heart
leads to beating of the heart and ejection of
blood, which produces the blood pressure and
electrocardiogram (ECG)

Tsunami simulations
using the tsunami-coupled equation of motion in 3D
Maeda and Furumura (2011) Pure and Applied Geophysics - under review Navier-Stokes eq
?u ?u ?u ?u ?p ? ? 2u ? 2u ? 2u ?
+u +v +w = ? +�� ? 2 + 2 + 2 ? + g x
?t ?x ?y ?z ?x ? ?x ?y ?z ?
?v ?v ?v ?v ?p ? ? 2v ? 2v ? 2v ?
+ u + v + w = ? +�� ? 2 + 2 + 2 ? + g y
?t ?x ?y ?z ?y ? ?x ?y ?z ?
?w ?w ?w ?w ?p ? ?2w ?2w ?2w ?
+u +v +w = ? +�� ? 2 + 2 + 2 ? + g z
?t ?x ?y ?z ?z ? ?x ?y ?z ?

[Present] Resolution: 1km
CPU Time: 2 hour
(ES 64 node)

[Expected] Resolution:
0.25 km
CPU Time: < 10 min
(K Computer)

It��s possible to issue
Tsunami Warning

Introducing my early career
? 1974, joined Carl Hewitt��s group, MIT
? 1977, finished PhD
? 1985, ABCL (concurrent OO language),
at pre-1st ECOOP
? 1986, 1st OOPSLA, ABCL/1 paper
��Object-Oriented Concurrent Programming�� (MIT Press)
? 1988, 3rd OOPSLA, ABCL/R paper
? 1900, 5th OOPSLA/ECOOP PC chair
��ABCL: an Concurrent Object-Oriented System�� (MIT Press)
��

My idea of Concurrent Objects (1975)
For modeling and programming,��
? Concurrent Object
= Encapsulated(Stateful Object + thread)

Object Concurrent
thread/cpu ��> Object

? Asynchronous message passing among concurrent objects

? Actor Approach
-C.Hewitt and H.Baker:
Laws for communicating Parallel Processes, IFIP1977
-G.Agha: A Model for Concurrent Computation in Distributed Systems,
MIT Press 1987

Concurrent objects
Each CO
? has a globally unique identity/name,
? may have a protected, yet updatable local memory,
? has a set of procedures that manipulates the memory,
? receives a message that activates one of the procedures,
? has a single FIFO queue for arrived messages, and
? has autonomous thread(s) of control.
- In each CO, memory-updating procedures are activated
one at a time with the message arrival order.
- The contents of the memory of a CO,
which is the local state of the CO.

my Modeling of Real World
with Concurrent Objects

Modeling
domain
Representing

concurrent

Real World Interacting Agents

Concurrent Objects &
Message Passing
WEB

Entities,people,
machines & their
interactions

Example:
Modeling a small Post Office (1977)
Mail Box in counter-section
PostOffice

door

clients

Modeling Post Office in COs
? Post Office Building ? the door
? door CO
? Counter with clerks
? counter CO
? Mail Box
? mailbox CO
? Customers
? customer COs not messages!

Modeling Movement of Customers

? Two ways:

1. a customer object is transmitted
in a message
2. a customer object moves by itself
(autonomously)

Object (or its code) migrates autonomously!!

Mobility increases CO��s power
? Increases CO��s
�C modeling power
�C intellectual power

? Entering a new environment
�C > increase accessibility of
potentially available information and knowledge

If COs are equipped with appropriate means for
access to surrounding environments, their
power increases.

JavaGO: our Mobile Concurrent
Objects Language (1998)
and
its application systems

Realization of Self-migration/mobile
Concurrent Objects �C JavaGo Language
Adding (Goto: L) statement to the language
T.Sekiguchi &
L1 H.Masuhara

��
(go-to L1)

L2

? �ʣ��ǣ� Language and its implementation
that enables programmers to write concurrent
objects moving around network nodes (1999)

JavaGoX: transformation for
transparent thread migration

? Java��s support for mobile objects
�C dynamic class loading
�C ��serialization�� of object states

? JavaGoX enables efficient migration of running objects
�C by inserting code for
saving/restoring execution stack into heap
�C implemented as a bytecode transformation system
Cf. Sakamoto, Sekiguchi, Yonezawa: Bytecode Transformation for Portable
Thread Migration in Java, in ASA/MA'00, 2000 for details.

An Application of Mobile Concurrent Objects

Automatic Software Install/Update System

Installing/updating software in PCs
on LAN is painful

? There are many PCs
on a single LAN.

? Users of the PCs do not
install/update software
�C They are busy or non-geek

Features of
Mobile Automatic Installation System
? Mobile software (called mobile installers)
migrates from administrative PCs to client PCs
and installs/updates software automatically
�C Administrative costs can be largely reduced
? Number of client PCs does not matter
? Totally unattended installation/update is possible
? Encryption and digital signature are supported
�C Risks of illegally-copied software and virus programs
are addressed

Overview of Our System

Administrative PC

Mobile Installer

Target Software

Encryption

Decryption Key

Client PCs
Digital Signature

Reflection in COs and its Application
[ABCL/R language in OOPSLA88]
Reflection makes COs more intelligent,
and closer to Agents?

Computational Reflection
Computation about Oneself: Introspection & Self Modification

MCPs: meta-
M[S] interpreters,
meta-objects
S
A reflective system S can reason
base-level
about or act upon itself via the
causally-connected self
representation M[S].
Representation in a Reflective Tower (Smith, 1982)
Pioneers: S is reified as R[S] within the meta-circular processor
3-Lisp (B. C. Smith, 1982) MCP1. MCP1 is also reified in MCP2, and so forth.
3-KRS (P. Maes, 1986) Reflective behaviors are realized as normal operations
in the meta-levels (MCPs).

Why Reflection in COs?
? Customizable meta-objects can introduce
�C new language features
�C Modification of semantics of objects.
�C Application/Domain-Specific Language Features
? Highly Dynamic Behaviors
�C On-the-Fly Code Acquisition
�C Dynamically Adaptable Behaviors
�C Object Migration
�C Time control of distributed simulation
? A New Dimension of Modularization
�C Descriptions of Non-Functional Requirements/constraints using
Meta-Levels (Meta-Objects)

? This idea later evolved into AOP

ABCL/R
One Concurrent Object �C> One Meta-Object
Each object has its own meta- the meta-object of O methods execution
object that solely governs its engine
computation. The meta- (evaluator)
object reifies the structure of
the object. reified
message
The meta-object also has its internal
meta-object. So the reflective state
tower exists for each object.
message queue
The base-level object can
send messages to its meta- reflective
object: this realize reflective O message
behaviors.
incoming
message an object (base-level)
Watanabe & Yonezawa, OOPSLA '88

What is an Agent (Macal&North��06)
? An agent is identifiable,
�C a discrete individual with a set of characteristics and rules
governing its behaviors and decision-making capability
? An agent is autonomous and self-directed,
�C An agent can function independently in its environment.
? An agent is situated (and mobile),
�C living in an environment with which it interacts along with
other agents.
�C has protocols for interaction with other agents, such as for
communication, and the capability to respond to the
environment
? An agent may be goal-directed,
�C Has goals to achieve (not necessarily objectives to
maximize) with respect to its behaviors.

An Agent at a Glance (Macal&North��06)

Agents have more abilities than COs
? ( + goals to achieve)
? + Automatic update of location information and
other information
? + can modify its self (~a la reflection in CO)
? + sensor facilities for environment information
�C sight/vision
�C field force
�C��
? + actuator facilities
�C��

Applications of COs
in large scales
- Linden��s ��Second Life�� / Online Virtual World
- In the context of HPC, Charm++ and NAMD

Back to Original Motivation of COs

Real World Interacting Agents

Concurrent Objects &
Message Passing
WEB

Entities,people, machines &
their interactions
Linden��s Second Life ��
is a natural outcome from the motivation of COs:

Why COs for Second Life
? The idea of concurrent objects has been
adopted in Second Life (Linden Lab.) because:

�C COs can directly simulating virtual world objects,
�C which enables
easy modeling and
easy/safe concurrent programming!

COs in Second Life
? Jim Purbrick, Mark Lentczner,
��Second Life: The World��s Biggest Programming
Environment��,
Invited Talk at OOPSLA2007, said:
�C Objects and avatars cooperate and coordinate
each other by exchanging messages. COness!
�C each object or avatar is programmed to
? Have its own state,
? Have its own method to respond to an incoming message,
? Have different responses to different states, and
? Have its own thread.
�C About 2 millions of objects are programmed in Second
Life and they are in action.

Application of JavaGoX��s
transformation method to Second Life
? our JavaGoX [ASA/MA��00]
�C a bytecode transformation system
that enables migration of running objects on JVM
? Second Life employs similar transformation
for their new Mono-based script Sims//COs
execution engine
�C for migrating objects
between ��regions��
? a region is managed
by one server

region
Image from ��EVOLVING NEMO�� in New World Notes at Second Life Blog
(http://secondlife.blogs.com/nwn/2005/06/evolving_nemo.html)

Concurrent Object Languages for HPC
ABCL/f (U. Tokyo)
Charm++ (U. Illinois)

ABCL/f implementation
on Fujitsu AP1000 (PPoPP 93)
? One of the earliest attempts to implement
concurrent objects as a high performance parallel
programming language on distributed memory
massively parallel 512 processors (sparc)

Kenjiro Taura, Uni. Tokyo ? Information Processing Society of Japan

Charm++
? CO-based language system for
parallel/supercomputers developed by Sanjay Kale��s
group (U. Illinois) since 1993.
? Used for development of NAMD (Molecular
Dynamics), OpenAtom��quantum chemistry��,
ChaNCA��Galaxy generation��
? Operational for various supercomputers to date
�C Full Jaguar PF Cray XT5 (224,076 cores)
�C K computer (700,000 cores), Blue Gene/Q (65,536 cores)
? Has a framework for dynamic load balancing by
moving Cos from node to node

What is Charm++?
? Platform independent library
for writing parallel programs
�C C++, C, and Fortran are supported

? Based on the notion of concurrent objects
�C Charm++ programs consist of:
? Parallel running objects (named ��chare��), and
? Communication among them
via asynchronous method invocation

Overview of Programming Model:
Logical View

??? Chare (Concurrent Objects)

??? Asynchronous Method Invocation

Overview of Programming Model:
Physical View Chares migrate btwn processors

Processor Processor Processor

terconnect Interconnect Interconnect Intercon

Overview of Charm++ Implementation
Processor Processor

Chare A Chare B

Charm++ Charm++ Scheduler
Runtime Runtime

Proxy of Interconnect
chare B
Message Queue

Processor Processor

Invoke a
Chare A method of Chare B
chare B

Runtime Runtime

chare B
Message Queue

Processor Processor

Invoke a
Chare A method of Chare B
chare B

Invoke the
local proxy of
chare B

Runtime Runtime

chare B
Message Queue

Processor Processor

Chare A Chare B

The proxy creates
a message for
Charm++ invoking chare B Charm++ Scheduler
Runtime Runtime
Message

chare B
Message Queue

Processor Processor

Chare A Chare B

Runtime transmits
the message
via interconnects
Runtime Runtime
Message

chare B
Message Queue

Processor Processor

Chare A Chare B

Scheduler dispatches
the message
to invoke chare B

Runtime Runtime
Message

chare B
Message Queue

Applications of Charm++
? Molecular dynamics: NAMD
�C http://charm.cs.uiuc.edu/research/moldyn
? Quantum molecular dynamics: OpenAtom
�C http://charm.cs.uiuc.edu/research/qmmm/
? Rocket simluation: RocStar
�C http://www.csar.uiuc.edu/rocstar/index.html
? Cosmology simulation: ChaNGa
�C http://www-
hpcc.astro.washington.edu/tools/changa.html

? etc.

NAMD
(Nano-scale Molecular Dynamics Simulator)

NAMD
? Nano scale molecular dynamics simulator for
supercomputers

? Major application of Charm++

? Developed jointly by two groups in Illinois Univ.
Prof. Sanjay Kale (Computer Science)
Prof. Schulten (Theoretical Biology)

? Received Gordon Bell Prize in 2006

? Running on Juager PF (224,076 cores)
for 100M atoms proteins

This still from a Quicktime movie represents a view of the drug
buried in the binding pocket of the A/H1N1 neuraminidase protein.

Molecular
Structure

Analysis of Molecular Structure of
Swine Flu by NAMD
Showed:
? Structural changes of A/H1N1 protein induce
anti-tamiful effects.

Experimental Results: NAMD on K computer
Kamada(2012)
20

ApoA1 (92,224 atoms)
18

ATPase (327,506 atoms)
16

STMV (1,066,628 atoms)
14
CPU time per step [ms]

12

10

8

6

4

2

0 8 cores /node
0 512 1024 1536 2048
Number of nodes
? Benchmarks were obtained from http://www.ks.uiuc.edu/Research/namd/utilities/
? 7 workers per node

What is an Agent? (Macal&North��06)
? An agent is identifiable,
�C a discrete individual with a set of characteristics and rules
governing its behaviors and decision-making capability
? An agent is autonomous and self-directed,
�C An agent can function independently in its environment.
? An agent is situated,
�C living in an environment with which it interacts along with
other agents.
�C has protocols for interaction with other agents, such as for
communication, and the capability to respond to the
environment
? An agent may be goal-directed,
�C Has goals to achieve (not necessarily objectives to
maximize) with respect to its behaviors.

Ultra Large Scale Agent-Based
Simulation in Japan

? Evacuation from Tsunami Attack

? Whole city traffic simulation (Kyoto)

Mitigation of Tsuname Damages
- A TOTAL Simulation APPROACH -

1. An earthquake breaks out
2. Propagation of strong vibration
3. Simulation of the Tsunami
�C Broadcast early warning
4. Simulation of flooding cities
5. Simulation of building damages
6. Simulation of human evaluation
�C Evacuation guidance

Earthquake Vibration Simulation
Using available
geological stratum
data

Prof. Furumura
Univ. Tokyo 71

Simulation of an Expected Tsunami in Japan

Buildings in part of Tokyo

? GIS tile ID : 09ld171 (near Shinjuku)
? No. of buildings : 14,000
? SRA model : Fiber element model
? output size : 12 GB
? Strong ground motion data from 1995 Kobe earthquake

Evacuation Drill: before building damages assumed

Shelter Building

Human Evacuation after Earthquake

Shelter Building

Agent-Based
Human Evacuation Simulation
? Goal: Total evacuation time to be reduced
�C Find best evacuation plans

? Parameters: # of people, evacuation routes,��
? Modeling/predicting human behavior
�C By monitoring human behavior, using physical driver
simulator
�C By measuring human actions
�C��

Measuring people��s movement
in an evacuation drill

Large scale evacuation simulations
? Understanding the dynamics of mass evacuation is
important
�C to find strategies to save as many as possible,
�C in future urban developments, etc.
? Based on Multi-Agent Simulations (MAS)
�C Suitable for simulating heterogeneous and complex
phenomena
? Mass evacuation is contagious in nature
and have cascade effect
�C Whole affected area has to be simulated as a single domain
? HPC enhancements are necessary to simulate millions in a
city like Tokyo
�C Monte-Carlo simulations are necessary
�C Poor scalability has been reported in literature

Multi Agent Simulation
? Agents in evacuation simulation Agent
Thought
�C agent mimic people interacting with
Ability

each other and the environment
Speed
Ability Direction
Vision
Thought Speed
? Agents See the environment Passing
Path
? Uses its Think to make a decision
? Move according to the decision See()

�C numerous kinds of agent to model
Think()
Move()
heterogeneous crowds
? Different levels of abilities
such as see, think and act
? Different information about the
surrounding
�C residents, visitors, officials, etc.
? Different levels of responsibilities
�C police, fire fighters, community leaders,
etc.

Simulation: 2,000,000 agents
in a part of Kochi City Using K omputer

Environment of evacuation simulation
? Space in which human or human organization acts
? Automatically generated from GIS data
�C Space/Environment is modeled as a grid
�C Grid cells are classified as occupied and un-occupied

GIS data of the real environment Raster model for MAS
in vector format

Agent��s visual perception and moves
? Sophisticated vision:
�C Scan the environment in high resolution (at 0.5o intervals)
�C Identify paths, obstacles, neighbors and
slow moving groups within 30m
? Moves:
�C avoiding the obstacles such as slow moving groups of agents
�C choose the path closest to the direction of destination
�C avoid collision with individuals
60m

Direction of
destination

Walking
direction

Visual Sight
�C an official searching people astray -

Scalability of evacuation simulation module
12
K
Ideal gradient
11
lilac (6 core Xeon E5620)
10
Log(runtime,2)

9
Number of agents =
8 500,000
7
Dotted lines show the Area 19.2 km2 in Kochi city
ideal gradient, not the
ideal run time
6
3 4 5 6 7 8 9 10
Log(CPU cores,2)

? C++ in K seems to be slow
? May be STL is not well optimized

strategies for reducing pre-evacuation time
? Tsunami evacuation is highly time critical
? Anticipating Tokai-Tonankai-Nankai tsunami may arrive in 10 minutes

? Evacuation time = pre-evacuation time + travel time
? Pre-evacuation time: waking, change clothes, putting stuffs together,
? Pre-evacuation time may be as large as 30 minutes

? Appoint officials: deliver the warning personally
? People tends to neglect the warnings from announcements, TV, radio, etc.
? To personally deliver warning and give path to nearest evacuation center

? Need to study the effectiveness with different
influential power

Official agents personally advising
residents to evacuate early

Findings
? Preliminary study on pre-evacuation time
reduction
�C Delivering the warning personally could reduce
evacuation time significantly
�C Employing officials + community leaders could
save more lives
? High parallel scalability is attained
�C Can handle several millions of agents on
thousands of CPU cores

Traffic Flow Simulation with Agents

? S. Kato, G. Yamamoto,.. (IBM Res. Report RTO 759, 2008)

Simulator Architecture MASMITS
Agent Space Simulation Space
Driver Agent

Message
Driver Model

Driver Agent Message

Driver Model

Agent Space Simulation Space
? Collection of Agents
? Agent: messages
�C current states of traffic
�C Model of a car and �C the alignment of roads to
driver behavior driver agents
�C current speed and positions
of vehicles,
Messages from
S-space to A-space �C distance sbetween cars,
? NextSpeedMessage �C the curvature and gradient
? EnterSpeedMessage of roads on which individual
vehicles are running.
? NextRoadMessage
? EnterRoadMessage Keeps states of roads and agents
? ExitRoadMessage
? StartMessage

Simulation Results (single processor)
Kyoto City Road Network
? simulated the traffic of the Kyoto city.
? the road network of Kyoto, 32,654 links and 22,782 nodes.
? 894,802 pairs of origin and destination are assigned.
? 894,802 vehicle agents start their origins toward
destination at the same time.
? time step size is 0.1.
? used the IBM xSeries 335 (2.8GHz processor, 4GBmemory).

Traffic Simulation for a Kyoto festival day

Nation-wide Traffic Simulation
on a Supercomputer
? Nation-wide Road network:
�C 993,731 intersections, 2,552,160 roads
? The agent simulator written in X10.
�C X10 language (IBM) for HPC
�C X10: PGAS OO language
with places and async. activities
? No MPI, or No OpenMP!!
? Tsubame2: 1.19peta flops @ Titech

�ݺ�ߣ

Agere.talk

More Related Content

Agere.talk