Transcript Document
Design of
Departmental
Metacomputing ML
Frédéric Gava
ICCS 2004 Gava
1
Computing Unit
Goal
Computing Unit
Storage
User
ICCS 2004 Gava
2
Bulk Synchronous Parallelism +
Functional Programming = BSML
Advantages of the BSP model:
1. Portability
2. Scalability, deadlock free
3. Simple cost model Performance prediction
Advantages of functional programming:
1. High level features (higher order functions, pattern-matching,
concrete types, etc…)
2. Savety of the environment
3. Programs Proofs
ICCS 2004 Gava
3
The BSP model
Proc.
0
1
2
3
p-1
T(s) = (max0i<p wi) + hg + L
4
The BSML language
Confluent language : deterministic algorithms
Library for the « Objective Caml » language (called BSMLlib)
Operations to access to the BSP parameters
4 Operations on a parallel data structure called parallel vector
mkpar : create a parallel vector
apply : parallel point-wise application
put : send values
at : projection of a value
5
Problems with BSP
Global synchronization is too expensive
No hierarchical network capacities
No heterogenelity
ICCS 2004 Gava
6
The MP model
MP = messages passing
No super-steps but m-steps
Proc.
0
1
2
3
Local computing
Communication
7
New model: DMM
We have :
• P BSP units
• L, latency of the global network
• G, time to send one word
List of nb of processes :
List of times for a barrier :
List of times for a 1-relation :
We have d-steps of super-steps
ICCS 2004 Gava
8
New communication
BSP Unit i
G et L
BSP Unit j
Intranet
gi
et
li
gj et lj
ICCS 2004 Gava
9
New communication
Unit i
gi
Unité j
et
li
ICCS 2004 Gava
10
New language: DMML
Library for the « Objective Caml » language
Operations to access to the DMM parameters
Operations on departmental vectors
mkdpt : creation of a departmental vector
applydpt : departmental point-wise application
get : received values
Conclusion
BSML = BSP + ML
New model for departmental meta-computing
New language called DMML
ICCS 2004 Gava
12
Future Work
Polymorphic type system for the language
Implementation of « big » applications
Static Dependent Costs for Estimating Execution Time
ICCS 2004 Gava
13
ICCS 2004 Gava
14