Transcript A Functional Language for Departmental Metacomputing

A Functional Language for
Departmental Metacomputing
Frederic Gava & Frederic Loulergue
Universite Paris Val de Marne
Laboratory of Algorithms, Complexity and Logic
Structured Parallelism
Concurrent
Programming
• High Level Programming
• Deadlock free, deterministic
•Parallel Algorithms (BSP)
Automatic
Parallelisation
CMPPs



CMPP 98: BSl-calculus (Loulergue, Hains, Foisy)
A confluent calculus of functional Bulk
Synchronous Parallel programs
CMPP 2000: Bulk Synchronous Parallel ML
(Hains, Loulergue)
A library for Objective Caml based on BSl
CMPP 2004: Departmental Metacomputing ML
The Caraml Project 2002-2004
French National Grid Program
3 Phases:
 Improvement of the safety of the existing
parallel programming libraries
 Multiprogramming on one cluster:
Parallel Compositions for BSML (Iccs, Europar)
 Programming clusters (cluster of clusters)
http://www.caraml.org
Outline
Bulk Synchronous Parallel ML
The Bulk Synchronous Parallel model
 BSML primitives

+ Minimally Synchronous Parallel ML
The Message Passing Machine model
 MSPML primitives

= Departemental Metacomputing ML
DMML primitives
 Semantics
 Implementation

Bulk Synchronous Parallelism


BSP machine: p processor-memory pairs +
network+ global synchronisation unit
BSP execution: sequence of super-steps
Asynchronous computation phase
 Communication phase
 Global synchronisation


BSP cost model (one super-step):
(max0<=i<p wi) + h*g + l
The BSMLlib Library






For Objective Caml
No SPMD
Deadlock free, deterministic semantics
Usual Objective Caml programs + operations
on a parallel data structure
Parallel vector of size p: a par (no nesting)
Access to the BSP parameters:
bsp_p, bsp_g, bsp_l
BSML Primitives (1)



mkpar: (int->a) -> a par
mkpar f = <(f 0), … , (f (p-1))>
apply: (a->b) par -> a par -> b par
apply <f0,…fp-1> <v0,…,vp-1>=
<(f0 v0),…(fp-1 vp-1)>
projection: at
BSML Primitives (2)

put: (int->a option) par -> (int->a option) par
put <f0,…,fp-1> = <g0,…,g p-1>

If (f0 2) = None
“0 will send no value to 2”
(f0 3) = Some v “0 will send value v to 3”
Then (g2 0)=None “2 received nothing from 0”
(g3 0)=Some v “3 received value v from 0”

BSMLlib 0.25: http://bsmllib.free.fr
The Message Passing Machine model


machine: p processor-memory pairs + network
execution: seen as sequence of m-steps
Asynchronous computations
 Asynchronous communications


cost model:
p: number of processors
 g: time required to send one word
 L: network latency

MSPML Primitives

Same primitives than BSML

But for communications: get instead of put

get: a par -> int par -> a par
get <v0,…vp-1> <i0,…,ip-1>=
<vi0,…vip-1>

communication environments

http://mspml.free.fr
Departemental Metacomputing ML

machine:
cluster of BSP clusters within the same
organisation
contains the whole BSML language

based on departmental vectors: a dep

int dep: all proc. of the same BSP unit contain the same
value
 int par dep: possibly different values

Access to Parameters

Parameters of the BSP units:





(dm_bsp_p i): number of proc. of BSP unit i
(dm_bsp_g i)
(dm_bsp_l i)
(dm_bsp_s i): processor speed of BSP unit I
Parameters of the metacomputer:



dm_p(): number of BSP units
dm_g(): time required to echange 1 word between two units
dm_l(): inter-units network latency
Primitives

mkdep: (int->a) -> a dep
dm_p()=3
dm_bsp_p = [3;2;4]
mkdep(fun c->mkpar(fun i->c+2*i))
[ <0,2,4> , <1,3> , <2,4,6,8> ]

apply: (a->b) dep -> a dep -> b dep

projection: atdep
Communications


get: (int-> int-> int option) par dep ->
(int-> a option) par dep ->
(int-> int-> a option) par dep
On cluster a at process i:
(* f *)
(* g *)
(* h *)
(f b j)=Some n : wants the nth value of process j on
cluster b
 (h b j)= Some v: values sent by process j of cluster b


On cluster b at process j:

(g n) = Some v
Formal Semantics

Operational semantics:
mini-ML (purely functional)+ DMML operations
 Confluence


Formal costs:
C: expression -> cost formula
Implementation & Experiments

Library for Objective Caml:




MPI for intra BSP unit communications
TCP/IP for inter BSP units communications
Experiments …
not yet: 2 months ago no cluster dedicated to research
Future metacomputer:



12 nodes PIII cluster+FastEthernet (classroom)
6 nodes PIV cluster + Gigabit Ethernet
Virtual Private Network
Future Work (1)


Algorithms & implementation in DMML
Benchmark suite:
recently done for BSML
 Ongoing work for MSPML & DMML


Modular implementation (parametric modules)
BSMLlib 0.3 in september
(MPI,PVM,PUB,TPCP/IP)
 Abstraction done for MSPML
 Ongoing for DMML

Future Work (2)

Type system:
to avoid nesting of par and dep
 interaction with imperative features



Certification:
Program extraction from Coq proofs
Fault tolerance