Overview Concurrent and Distributed Programming Patterns ...

Overview

Concurrent and Distributed

Programming Patterns in SALSA

? Programming techniques and patterns

�C

�C

�C

�C

�C

farmer-worker computations,

iterative computations,

peer-to-peer agent networks,

soft real-time: priorities, delays

causal connections: named tokens, waitfor property

? Distributed runtime architecture (World-Wide Computer)

Travis Desell

Carlos Varela

RPI

�C architecture and implementation

�C distributed garbage collection

? Autonomic computing (Internet Operating System)

�C architecture and implementation

�C autonomous migration

�C split and merge

November 6, 2009

? Distributed systems visualization (OverView)

Travis Desell and Carlos Varela

Travis Desell and Carlos Varela

1

Farmer Worker Computations

Farmer Worker Computations

Farmer

Worker 1

get

rec

? Most common ��Massively Parallel�� type of

computation

? Workers repeatedly request tasks or jobs from

farmer and process them

Worker n

get

rec

get

process

...

process

rec

get

rec

Travis Desell and Carlos Varela

2

3

Twin Primes & Brun��s Constant

process

get

rec

Travis Desell and Carlos Varela

4

Iterative Computations

?Investigators:

P. H. Fry, J. Nesheiwat, B. Szymanski (RPI CS)

?Problem Statement:

? Common pattern for partial differential equations,

scientific computing and distributed simulation

? Workers connected to neighbors

? Data location dependent

? Workers process an iteration with results from

neighbors, then send results to neighbors

? Performance bounded by slowest worker

Are there infinitely many twin primes?

Calculating Brun��s Constant (sum of inverse of all

twin primes) to highest accuracy.

?Application Information (Twin Primes):

Massively Parallel

Farmer/Worker

Non-Iterative

Travis Desell and Carlos Varela

5

Travis Desell and Carlos Varela

6

1

Iterative Farmer/Worker

Farmer

Worker 1

Iterative P2P

Worker n

process

Worker 1

Worker 2

Worker 3

Worker 4

comm.

process

process

comm.

...

process

process

process

process

process

comm.

process

process

Travis Desell and Carlos Varela

7

Adaptive Partial Differential

Equation Solvers

?

Investigators:

Problem Statement:

?

Applications/Implications:

?

Approach:

8

Case Study: Heat Diffusion

Problem

? A problem that models heat transfer in a solid

J. Flaherty, M. Shephard B. Szymanski, C. Varela (RPI)

J. Teresco (Williams), E. Deelman (ISI-UCI)

?

Travis Desell and Carlos Varela

? A two-dimensional mesh is used to represent the problem

data space

How to dynamically adapt solutions to PDEs to account for

underlying computing infrastructure?

Materials fabrication, biomechanics, fluid dynamics,

aeronautical design, ecology.

? An Iterative Application

Partition problem and dynamically map into computing

infrastructure and balance load.

Low communication overhead over low-latency connections.

?

? Highly synchronized

Software:

Rensselaer Partition Model (RPM)

Algorithm Oriented Mesh Database (AOMD).

Dynamic Resource Utilization Model) (DRUM)

Application Information (Heat):

Tightly coupled

Iterative

Travis Desell and Carlos Varela

9

Travis Desell and Carlos Varela

10

Parallel Decomposition of the

N Heat Problem

Original Data Space

�C

�C

Parallel Decomposition

?

Legend

Ghost Cells

Data Cells

N

Boundary Cells

Peer-to-Peer Computations

Ghost Cell Exchange

4-pt update stencil

N

P0

PTravis

Desell and Carlos

P2 Varela

1

Pn-1

11

Travis Desell and Carlos Varela

12

2

Peer-to-peer systems (1)

?

?

?

?

Peer-to-peer systems (2)

Network transparency works well for a small number of nodes; what do we

do when the number of nodes becomes very large?

�C This is what is happening now

We need a scalable way to handle large numbers of nodes

Peer-to-peer systems provide one solution

�C A distributed system that connects resources located at the edges of the

Internet

�C Resources: storage, computation power, information, etc.

�C Peer software: all nodes are functionally equivalent

Dynamic

�C Peers join and leave frequently

�C Failures are unavoidable

Travis Desell and Carlos Varela

?

Unstructured systems

�C Napster (first generation): still had centralized directory

�C Gnutella, Kazaa, �� (second generation): neighbor graph, fully decentralized

but no guarantees, often uses superpeer structure

?

Structured overlay networks (third generation)

�C Using non-random topologies

�C Strong guarantees on routing and message delivery

�C Testing on realistically harsh environments (e.g., PlanetLab)

�C DHT (Distributed Hash Table) provides lookup functionality

�C Many examples: Chord, CAN, Pastry, Tapestry, P-Grid, DKS, Viceroy,

Tango, Koorde, etc.

Travis Desell and Carlos Varela

13

Examples of P2P networks

? Hybrid (client/server)

R = 1 (others)

�C Napster

Scalable

?

Self organizing

�C

H=1

? Unstructured P2P

�C

�C

?

�C Gnutella

H = 1��7

�C Exponential network

�C DHT (Distributed Hash

Table), e.g., Chord

(but no guarantee)

�C

?

Works for any number of nodes

Routing tables updated with node joins/leaves

Routing tables updated with node failures

Provides guarantees

�C

R = ? (variable)

? Structured P2P

Properties of

structured overlay networks

?

R = N-1 (hub)

14

If operated inside of failure model, then communication is guaranteed with an upper bound on

number of hops

Broadcast can be done with a minimum number of messages

Provides basic services

�C

�C

Name-based communication (point-to-point and group)

DHT (Distributed Hash Table): efficient storage and retrieval of (key,value) pairs

R = log N

H = log N

(with guarantee)

Travis Desell and Carlos Varela

Travis Desell and Carlos Varela

15

Self organization

?

Chord: lookup illustrated

Maintaining the routing tables

�C Correction-on-use (lazy approach)

�C Periodic correction (eager approach)

�C Guided by assumptions on traffic

?

Given a key, find the value associated

to the key

(here, the value is the IP address of the

node that stores the key)

Cost

�C Depends on structure

�C A typical algorithm, DKS (distributed k-ary search), achieves logarithmic

cost for reconfiguration and for key resolution (lookup)

?

16

Example of lookup for Chord, the first well-known structured overlay

network

Travis Desell and Carlos Varela

17

15

node to be contacted

0

6

6

6

12

1

2

14

Assume node 0 searches for the value

associated to key K with virtual

12

identifier 7

Interval

[0,1)

[1,2)

[2,4)

[4,8)

[8,0)

0

3

13

4

11

5

10

6

9

8

7

Indicates presence of a node

Travis Desell and Carlos Varela

18

3

Message Properties

? SALSA provides message properties to control message

sending behavior:

Soft Real-Time

�C delay

? To delay sending a message to an actor for a given time

�C waitfor

? To delay sending a message to an actor until a token is

available

Travis Desell and Carlos Varela

Travis Desell and Carlos Varela

19

20

Delayed Message Sending

? To (asynchronously) send a message after a given

delay in milliseconds:

Causal Connections

a ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download