Transcript The IC Wall Collaboration between Computer science + Physics

Parallel Programming
on Computational Grids
Outline
•
•
•
•
Grids
Application-level tools for grids
Parallel programming on grids
Case study: Ibis
Grids
• Seamless integration of geographically distributed computers,
databases, instruments
– The name is an analogy with power grids
• Highly active research area
– Open Grid Forum
– Globus middleware
– Many European projects, e.g.:
• Gridlab: Grid Application Toolkit and Testbed
• DEISA: Distributed European Infrastructure for
Supercomputing Applications
• XtreemOS: Linux-based OS for grids
– VL-e (Virtual laboratory for e-Science) project
– ….
Why Grids?
• New distributed applications that use data or
instruments across multiple administrative domains
and that need much CPU power
–
–
–
–
–
–
–
Computer-enhanced instruments
Collaborative engineering
Browsing of remote datasets
Use of remote software
Data-intensive computing
Very large-scale simulation
Large-scale parameter studies
Web, Grids and e-Science
• Web is about exchanging information
• Grid is about sharing resources
– Computers, data bases, instruments
• e-Science supports experimental science by
providing a virtual laboratory on top of Grids
– Support for visualization, workflows, data management,
security, authentication, high-performance computing
The big picture
Application
Application
Application
Potential
Potential
Potential
Generic
Generic
Generic
Management
Virtual
Laboratory
part
Management
Management
part
part
of comm. & Application
oriented
of comm.
& services of comm. &
computing
computing
computing
Grids
Harness distributed resources
The data explosion
• e-Science experiments generate much data, that often
is distributed and that need much (parallel) processing
–
–
–
–
–
high-resolution imaging:
Bio-informatics queries:
Satellite world imagery:
Current particle physics:
LHC physics (2010?):
~ 1 GByte per measurement
500 GByte per database
~ 5 TByte/year
1 PByte per year
10-30 PByte per year
Grid programming
• The goal of a grid is to make resource sharing very
easy (transparent)
• Practice: grid programming is very difficult
– Finding resources, running applications, dealing with
heterogeneity and security, etc.
• Grid middleware (Globus) makes this somewhat
easier, but is still low-level and changes frequently
• Need application-level tools
Application-level tools
• Paper (on Blackboard):
– Blueprint for a New Computing Infrastructure (2nd Edition,
editors I. Foster and C. Kesselman); Chapter 24: ApplicationLevel tools (Bal, Casanova, Dongarra, Matsuoka)
• Builds on grid software infrastructure
• Isolates users from dynamics of the grid hardware
infrastructure
• Generic (broad classes of applications)
• Easy-to-use
Taxonomy of application-level tools
• Grid programming models
–
–
–
–
RPC
Task parallelism
Message passing
Java programming
• Grid application execution environments
– Parameter sweeps
– Workflow
– Portals
Remote Procedure Call (RPC)
• GridRPC: specialize RPC-style (client/server)
programming for grids
– Allows coarse-grain task parallelism & remote access
– Extended with resource discovery, scheduling, etc.
• Example: NetSolve
– Solves numerical problems on a grid
• Current development: use web technology (WSDL,
SOAP) for grid services
• Web and grid technology are merging
Task parallelism
• Many systems for task parallelism (master-worker,
replicated workers) exist for the grid
• Examples
– MW (master-worker)
– Satin: divide&conquer (hierarchical master-worker)
Message passing
• Several MPI implementations exist for the grid
• PACX MPI (Stutgart):
– Runs on heterogeneous systems
• MagPIe (Thilo Kielmann):
– Optimizes MPI’s collective communication
for hierarchical wide-area systems
• MPICH-G2:
– Similar to PACX and MagPIe, implemented on Globus
Java programming
• Java uses bytecode and is very portable
– ``Write once, run anywhere’’
• Can be used to handle heterogeneity
• Many systems now have Java interfaces:
– Globus (Globus Java Commodity Grid)
– MPI (MPIJava, MPJ, …)
– Gridlab Application Toolkit (Java GAT)
• Ibis and ProActive are Java-centric grid programming
systems
Parameter sweep applications
• Computations what are mostly independent
– E.g. run same simulation many times with different
parameters
• Can tolerate high network latencies, can easily be
made fault-tolerant
• Many systems use this type of trivial parallelism to
harness idle desktops
– APST, SETI@home, Entropia, XtremWeb
Workflow applications
• Link and compose diverse software tools and data
formats
– Connect modules and data-filters
• Results in coarse-grain, dataflow-like parallelism that
can be run efficiently on a grid
• Several workflow management systems exist
– E.g. Virtual Lab Amsterdam (predecessor VL-e)
Portals
• Graphical interfaces to the grid
• Often application-specific
• Also portals for resource brokering, file transfers, etc.
Outline
•
•
•
•
Grids
Application-level tools for grids
Parallel programming on grids
Case study: Ibis
Distributed supercomputing
• Parallel processing on geographically distributed
computing systems (grids)
• Examples:
– SETI@home (
), RSA-155, Entropia, Cactus
• Mostly limited to trivially parallel applications
• Questions:
– Can we generalize this to more HPC applications?
– What high-level programming support is needed?
Speedups on a grid?
• Grids usually are hierarchical
– Collections of clusters, supercomputers
– Fast local links, slow wide-area links
• Can optimize algorithms to exploit this hierarchy
– Minimize wide-area communication
• Wide-area bandwidth is increasing
– DAS-3 has 10 Gb/s dedicated optical links between sites
– Wide-area latency remains high (limited by speed-of-light)
Example: N-body simulation
• Much wide-area communication
– Each node needs info about remote bodies
CPU 1
CPU 1
CPU 2
CPU 2
Amsterdam
Delft
Trivial optimization
CPU 1
CPU 1
CPU 2
CPU 2
Amsterdam
Delft
Wide-area optimizations
• Message combining on wide-area links
• Latency hiding on wide-area links
• Collective operations for wide-area systems
– Broadcast, reduction, all-to-all exchange
• Load balancing
Conclusions:
– Many applications can be optimized to run efficiently on a
hierarchical wide-area system
– Need better programming support
Outline
•
•
•
•
Grids
Application-level tools for grids
Parallel programming on grids
Case study: Ibisal., AGRIDM’03 (Workshop on Adaptive Grid
Middleware, New
• Paper:
– Real-World Distributed Computing with Ibis, Sept. 2003
The Ibis system
• High-level & efficient programming support for distributed
supercomputing
• Use Java-centric approach + JVM technology
– Inherently more portable than native compilation
• Goal: drastically simplify programming and deployment of high
performance distributed applications
• Target:
– Large-scale distributed systems, including clusters, grids,
desktop grids, clouds, mobile devices ….
– Possibly all at the same time for 1 application
Real-world distributed systems
World wide testbed
Problem
• How to write (high-performance) applications for
real-world distributed systems?
• How to deal with:
–
–
–
–
–
Performance:
Heterogeneity:
Malleability:
Fault tolerance:
Connectivity:
efficiency on wide-area system
different systems & APIs
resources come and go
crashes
firewalls, NAT, etc.
Our approach
• Study fundamental underlying problems
• … hand-in-hand with realistic applications
• … integrate solutions in one system: Ibis
User
Distributed Systems
Applications
• Scientific applications
– Imaging (VU Medical Center, AMOLF)
– Bioinformatics (sequence analysis)
– Astronomy (data analysis challenge)
• Multimedia content analysis
• Games and model checking
• Semantic web (distributed reasoning)
Multimedia content analysis
• Automatically extract information from images & video
– E.g., video archive, surveillance cameras
• Extract feature vectors from images
– Describe properties (color, shape)
– Data-parallel task on a cluster
• Compute on consecutive images
– Task-parallelism on a grid
Example: object recognition
●
●
Analyze video stream from camera to learn and
recognize every-day objects
Representative for more serious applications
●
●
Same algorithms used for surveillance cameras
London Underground  >120.000 years of processing for
>> 10.000’s CCTV cameras
Games and Model Checking
• Can solve entire Awari game on
wide-area DAS-3 (889 B positions)
– Needs 10G private optical network
• Distributed model checking has very
similar communication pattern
– Search huge state spaces, random work distribution, bulk
asynchronous transfers
• Can efficiently run DeVinE model checker on widearea DAS-3, use up to 1 TB memory
Distributed reasoning
• MaRVIN (Frank van Harmelen et al, VU):
– A distributed platform for massive RDF inferencing
(deductive closure)
– ``a brain the size of a planet’’
• Uses Ibis to run on heterogeneous systems
(clusters, desktop grids)
• Used for Billion Triple track of Semantic Web
Challenge 2008
– Inputs 800M RDF triples, derives 29B triples
Awards
Astronomy
DACH 2008 – BS
DACH 2008 - FT
(Cluster/Grid’08)
SCALE 2008
(CCGrid’08)
ISWC 2008
Multimedia
Computing
AAAI-VC 2007
Semantic Web (van Harmelen et al.)
Ibis Philosophy
• Real-world distributed applications should be
developed and compiled on a local workstation, and
simply be launched from there
Ibis Approach
• Virtual Machines (Java) deal with heterogeneity
• Provide range of programming abstractions
• Designed for dynamic/faulty environments
• Easy deployment through middleware-independent
programming interfaces
• Modular and flexible: can replace Ibis components by
external ones
Ibis Design
• Applications need functionality for
– Programming (as in programming languages)
– Deployment (as in operating systems)
Programming
Deployment
Logical
Practical
Likes math
Visual (GUI)
Ibis System
Ibis brains
Programming system
Programming models
• Message passing (IPL, RMI, MPJ)
• Satin:
• Fault-tolerant, malleable divide-and-conquer system
• Jorus:
• Transparent library with multimedia operations
• Maestro:
• Self-optimizing fault-tolerant dataflow framework
Satin: a parallel divide-and-conquer
system on top of Ibis
• Divide-and-conquer is inherently hierarchical
• More general than master/worker
• Satin: Cilk-like primitives (spawn/sync) in Java
fib(5)
cpu 2
fib(2)
fib(1)
fib(1)
fib(0)
fib(4)
fib(3)
fib(3)
fib(2)
fib(2)
fib(1)
fib(1)
fib(0)
fib(1)
fib(0)
cpu 3
cpu 1
cpu 1
Example
interface FibInter {
public int fib(long n);
}
class Fib implements FibInter {
int fib (int n) {
if (n < 2) return n;
return fib(n-1) + fib(n-2);
}
}
Single-threaded Java
Example
interface FibInter
extends ibis.satin.Spawnable {
public int fib(long n);
}
class Fib
extends ibis.satin.SatinObject
implements FibInter {
public int fib (int n) {
if (n < 2) return n;
int x = fib (n - 1);
int y = fib (n - 2);
sync();
return x + y;
}
} Java + divide&conquer
IPL (Ibis Portability Layer)
• Java-centric “run-anywhere” library
• Point-to-point, multicast, streaming
• Simple model for tracking resources
– Join-Elect-Leave
– Supports malleability & fault-tolerance
SmartSockets library
• Detects connectivity problems
• Tries to solve them automatically
• With as little help from the user as possible
• Integrates existing and several new solutions
• Reverse connection setup, STUN, TCP splicing, SSH
tunneling, smart addressing, etc.
• Uses network of hubs as a side channel
Ibis Deployment system
IbisDeploy GUI
JavaGAT
• GAT: Grid Application Toolkit
– Makes grid applications independent of the underlying
grid infrastructure
• Used by applications to access grid services
– File copying, resource discovery, job submission &
monitoring, user authentication
• Successor API is currently being standardized
Grid Applications with GAT
File.copy(...)
Grid Application
GAT
Remote
Files
submitJob(...)
Monitoring
Info
Resource
service
Management
GAT Engine
GridLab
Globus
Unicore
SSH
P2P
Local
Intelligent
dispatching
gridftp
globus
Koala
Zorilla: Java P2P supercomputing
middleware
Ibis demo (movie)
Object recognition
Client
Servers
Ibis
(Java)
• Runs simultaneously on clusters (DAS-3,
Japan, Australia), Desktop Grid, Amazon
EC2 Cloud
• Connectivity problems solved automatically
by Ibis SmartSockets
Broker
Ibis movie (part 1)
Performance on 1 DAS-3 cluster
• Relative speedups of Java/Ibis and C++/MPI
– Using TCP or Myricom’s MX protocol
• Sequential performance Java: 88% of C++
DAS-3
Speedup (wide-area)
• Homogeneous wide-area systems (DAS-3):
– Frame rate increases linearly with #clusters
• World-wide experiment:
– 24 frames per second
(@ 640 x 480 resolution)
– Speed limited by camera,
not computing infrastructure
Smart Phones
• GSM + PC + GPS + camera + networks + ….
• Will become ubiquitous (like GSMs)
• Our goal: study distributed applications running on
(multiple) smart phones & other resources
Example: eyeDentify
• Implemented Ibis on Android
– Google’s open-source Java-based platform
• Object recognition (eyeDentify) on a G1 smartphone
• Deploys computation server on DAS-3 cluster
• Launched from IbisDeploy/eyeDentify client on phone
+
+
Summary
• Parallel computing on Grids (distributed supercomputing)
is a challenging and promising research area
• Many grid programming environments exist
• Ibis: a Java-centric Grid programming environment
• Extends to the mobile world