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) = (max0i<p wi) + hg + 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