Slide1 : Electronic Bayanihan
Parallel Processing and Volunteer Computing
Luis F. G. Sarmenta
The Ever-Growing Need for Speed : The Ever-Growing Need for Speed Machines are getting faster …
Moore’s Law (going strong since 1960’s):
for the same cost, you get a 2x faster proc. every 18 mos.
Want more speed? Just wait 18 mos.
… but not fast enough
Many new computationally-intensive apps, which still take days/weeks, even on latest processors
Examples of compute-intensive apps
Physics: CFD (auto/aero industry), weather, data analysis
Bio and Chem: modelling of DNA, proteins, etc.
Business: data mining, simulation and prediction
Multimedia: CGI rendering
Math: finding large primes, cryptography, etc.
We can do a lot if we have very fast computers!
Parallel Processing : Parallel Processing Want 2x speedup now? Use 2 processors!
Simple Example: adding 8 numbers 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8
3 + 7 + 5 + 6 + 7 + 8
10 + 11 + 7 + 8
21 + 15
36 Parallel (2 Procs.) 4 steps = 1.75x faster
(approaches 2x
with more numbers) Idea: give diff. parts of problem to diff. procs.
In general: up to N times faster with N procs.
Parallel Processing : Parallel Processing The Idea
partition problem into many parts
have processors work on different parts at the same time
“Embarassingly Parallel” apps
simplest form of parallelism
each part is independent
procs. can work without communicating with each other
very efficient because they don’t need to wait for each other
Master-Worker model
master assigns work
workers get and do work One BIG
Problem
Example: Code Cracking : Example: Code Cracking RSA RC5-56 challenge: crack the code and win $10,000
secret 56-bit key
first few letters are known, so we can know if we find right key
Strategy: search the whole key space by brute force
It works!
In 1997, distributed.net cracked the code
using thousands of computers around the world
Solved problem 26,000 times faster than a single Pentium
Workers search in parallel Eureka!
The key is 3124120797
Parallel Image Rendering : Parallel Image Rendering Another embarassingly parallel application
Ray tracing
trace light ray for each pixel
looong computation per pixel
but, pixels are independent
Idea: divide pixels and give to different computers
(or, even simpler, give differentframes)
Probably used in Toy Story, and Star Wars! One BIG
Picture divide into
independent blocks
Monte-Carlo Simulations : Monte-Carlo Simulations Simulation is based on randomized variables
Examples
Business
stock market and economy
simulating processing queues
Traffic Simulation
random traffic conditions, and driver behavior (!)
Input: random number seed
gives diff. sets of random #’s
Output: values of certain variables
e.g., stock price, travel time Traffic
Simulator
Parallel Monte-Carlo Simulations : Parallel Monte-Carlo Simulations Run many independent Monte-Carlo simulations with different random inputs in parallel
Collect statistical info, e.g., average travel times
Embarassingly parallel
each simulation is completely independent of the others Ave. Travel Time:
to Makati = 1.5 hrs.
to Manila = 70 mins. Do many runs
using actual
probability
distributions
What-If Simulations : What-If Simulations If we can compute averages fast enough, then we can do “what-if” experiments
First, choose (non-random) configuration (e.g., w/ or w/o color coding, or w/ or w/o flyover)
Then, run parallel Monte Carlo to determine averages
Repeat with other configurations you want to try
Select best
Ave. Travel Time:
to Makati = 1.5 hrs.
to Manila = 70 mins. without
flyover
What-If Simulations : If we can compute averages fast enough, then we can do “what-if” experiments
First, choose (non-random) configuration (e.g., w/ or w/o color coding, or w/ or w/o flyover)
Then, run parallel Monte Carlo to determine averages
Repeat with other configurations you want to try
Select best
Ave. Travel Time:
to Makati = 45 mins.
to Manila = 70 mins. What-If Simulations with
flyover
Master-Worker Computations : Master-Worker Computations Generalization of embarassingly parallel comp.
several embarassingly parallel computations in sequence
each “step” is composed of independent parts
but, each step can depend on previous step
In each step:
divide work into parts (aka “work packets”)
distribute to workers
collect results
create new work for next step (possibly based on results) Perform
Embarassingly Parallel
Computation (Next Parallel Step)
Other Master-Worker Examples : Other Master-Worker Examples Data Mining: finding patterns in data
collect lots of data (e.g., sales)
find associations
e.g., people who buy product A will also buy product B with probability 0.7
each work packet can be a subset of data
Optimizing multi-variable funcs.
start with m random points
choose k best ones and then generate new candidates from them
repeat until convergence
“genetic algorithms”
etc., etc.,
Perform
Embarassingly Parallel
Computation (Next Parallel Step)
Grid-Based Computations : Simulated
Space Grid-Based Computations The Idea
Divide space into 2D or 3D grid
Assign each cell to a different processor/computer
Procs. perform computation on their respective data in parallel
Exchange data between neighboring cells
Repeat step
Not “embarassingly parallel”
cells are not totally independent
requires communication b/w cells
make sure that communication time is less than computation time
Grid-Based Computations : Useful for modeling and simulation of physical systems
Computational Fluid Dynamics (CFD)
Heat Transfer/Diffusion
Weather forecasting
Computationally-Intensive
More accuracy -> more computation
finer grids
shorter simulated time intervals
Thus, we need parallel processing!
Grid-Based Computations
Other Forms of Parallel Processing : Other Forms of Parallel Processing N-Body Problem
compute movement of N bodies based on gravity
each proc gets a different subset of the N bodies
Matrix Multiplication
Fast-Fourier Transform
for image and sound processing
Pipelined Computations
etc., etc.,
The Main Idea
divide into parts
maximize computation-to-communication ratio (granularity) 1 2 3 4 8 12 16 15 14 9 5 6 7 11 10 13 One BIG
Problem divide into parts
How do we do Parallel Processing? : How do we do Parallel Processing? Supercomputers: VERY fast computers with MANY procs
e.g., Cray, Connection Machine, IBM Deep Thought, etc.
Different types
SIMD: single-instruction, multiple data
e.g., vector machines, array machines, CM2, etc.
MIMD: multiple-instruction, multiple data
More common today
Centralized Shared Memory
sometimes aka SMPs, e.g.. dual-Pentium PC’s
simpler memory model, but less scalable (only up to ~32)
Distributed Memory
each proc. has own memory; communicate via msg passing
much more scalable (up to thousands of procs)
Drawback: They’re EXPENSIVE!
Millions of $ each, plus not easily upgradeable
NOWs and Metacomputing : NOWs and Metacomputing Use existing networks of workstations (NOWs) as one big virtual metacomputer
“poor man’s supercomputer”
make use of idle time
Successful Projects
ad hoc systems: e.g., RSA-129 factoring (1994), GIMPS
general purpose systems: e.g., Condor, PVM, MPI
recent/ongoing projects:e.g. Legion, Globus, Beowulf, etc.
Problems
difficult to set up
requires giving out accounts
can take days, weeks, months to install
cannot be used by normal user
Volunteer Computing : Volunteer Computing The Idea: Make it very easy for even non-expert users to join a NOW by themselves
Minimal setup required Maximum participation
Can form very large NOWs very quickly!
just invite people
The Dream: Electronic Bayanihan
achieving the impossible through cooperation “Bayanihan” Mural by Carlos “Botong” Francisco, commissioned by Unilab, Philippines. Used with permission.
Examples of Volunteer Computing : Examples of Volunteer Computing distributed.net
cracked RC5 on October 19, 1997
average aggregate power of 26,000 Pentium-class PCs
involved 500,000 unique IP addresses over 250 days
SETI@home
data mining of radio telescope data to find ET
Ease of volunteering makes it possible to attract huge numbers of volunteers
volunteers download pre-compiled binaries from the web
Some Problems:
still need different versions for different platforms
still need a little technical knowledge from volunteers
download, install, and run
security: software can read/write user’s data
Project Bayanihan: Volunteer Computing with Java : Project Bayanihan: Volunteer Computing with Java Very easy to use
“one-click computing”: go to web site; applet runs automatically
minimal setup & distribution effort
even NC and WebTV users can join
Platform-independent
write once, run anywhere
easier for both programmers and volunteers
Secure
Java sandbox prevents applets from touching users’ data
minimal security risk Server
Potentials : Potentials True (Altruistic) Volunteer Computing
potentially tap millions of computers around the world
cool problems (e.g., RC5, Chess, computer “olympics”)
worthy causes
local (e.g., traffic), or global (e.g., medical, environmental)
Forced (Institutional) Volunteer Computing
easy & cheap supercomputing for companies and universities
collaboratories: enable institutions to share computing power
Paid (Commercial) Volunteer Computing
market systems: buy, sell, trade processor cycles as commodity
contract systems: use cycles to pay for online services
NOIA (Network of Information Appliances)
use computational power of set-top boxes (e.g., WebTV)
can be commercialized and/or contract-based
tens of millions of processors (note: Greek noia means “mind”)
Current Results : Current Results Bayanihan software framework
my ongoing Ph.D. thesis at MIT
Currently good for Master-Worker style apps
RSA RC5 challenge decryption
Distributed web-crawling (parallel communications)
Mandelbrot set (rendering)
Genetic algorithms (e.g., function optimization)
Research Issues
User Interface Design
Adaptive Parallelism
Fault and Sabotage Tolerance
Performance and Scalability
Implementing other types of Apps
Experimental Results : Experimental Results 200 Mhz Pentiums w/ Netscape 4.0, NT4.0, 10Mbit Ethernet
Mandelbrot
shows good performance of embarassingly parallel apps
Matrix Multiply
Broadcast B
distribute rows of A
Performance limited by
sequential broadcast of Matrix B
memory limits (can’t do 1000x1000 matrix)
Jacobi Iteration (Grid Computation)
shows that we can now write general scientific code (e.g., CFD)
BUT, performance is still BAD because we are just simulating a grid computation using master-worker
ongoing research
Experimental Results : 200 Mhz Pentiums w/ Netscape 4.0, NT4.0, 10Mbit Ethernet
Mandelbrot
shows good performance of embarassingly parallel apps
Matrix Multiply
Broadcast B
distribute rows of A
Performance limited by
sequential broadcast of Matrix B
memory limits (can’t do 1000x1000 matrix)
Jacobi Iteration (Grid Computation)
shows that we can now write general scientific code (e.g., CFD)
BUT, performance is still BAD because we are just simulating a grid computation using master-worker
ongoing research
Experimental Results Conclusion
At present, Bayanihan is best for master-worker and embarassingly parallel computations
BUT, still a lot of useful apps
especially Monte Carlo-like apps
Feel free to suggest some!
Related Work : Related Work Using Java applications
ATLAS (Cilk), ParaWeb, JPVM, WWWinda, Jada
IceT, Ninflet, Java//
DOGMA
Using Java applets
Univ. of Wash. Factoring, DAMPP (JavaWorld)
Charlotte: eager scheduling, shared memory
Javelin: brokers, servlets, Linda, Cilk-like scheduling
Bayanihan
ease-of-use and accessibility
minimal setup requirements maximum participation
flexibility
use OOP to make general application programming and volunteer computing research easy
For More Information : For More Information Papers & Presentations
Sarmenta. “Bayanihan: Web-Based Volunteer Computing Using Java.” WWCA’98. (Springer LNCS 1368)
Sarmenta, Hirano, Ward. “Towards Bayanihan: Building an Extensible Framework for Volunteer Computing Using Java.” ACM Java ‘98. (Concurrency, Oct? ‘98)
Sarmenta, Hirano. “Bayanihan: Building and Studying Volunteer Computing Systems Using Java.” FGCS ’99
Sarmenta, “An Adaptive, Fault-Tolerant Implementation of BSP for Java-based Volunteer Computing Systems.” IPPS Workshop Java for Par. and Dist. Comp. Apr. ‘99
URL
http://bayanihan.ateneo.net/
http://www.cag.lcs.mit.edu/bayanihan
Email: lfgs@pusit.admu.edu.ph, lfgs@mit.edu