Architetture Parallele e Distribuite
2008-09
1. ASSIST: cenno
2. Grid Computing
3. Adattività
indipendente dal concetto di processo
Applicazione sviluppata con
Livelli e moduli
strumenti user-friendly
compilata /
interpretata in
Applicazioni
indipendente dall’architettura
Processi
Assembler
Firmware
 Uniprocessor di vari tipi 
 Multiprocessor di vari tipi e con vari processori 
 Cluster di vari tipi e con vari processori 
Programma parallelo
(processi comunicanti e/o
oggetti condivisi)
compilato / interpretato
in un programma
parallelo eseguibile su
Architettura 1
Architettura 2
Architettura 3
supporto diverso
per ogni architettura
Architettura X
Hardware
2
Un ambiente di programmazione per macchine parallele
e Next Generation Grid
Department of Computer Science, University of Pisa
ASSIST
A Programming Environment for High-performance Portable Applications on
Clusters, Large-scale Platforms, and Grids
Projects:
Implementations:
•
ASI-PQE2000
• Heterogeneous Cluster/Beowulf
•
CNR Agenzia 2000
• CORBA, WS interoperability
•
MIUR-CNR Strategic Programmes
•
• Grid version (on top of Globus 4)
MIUR-FIRB Grid.it
•
SFIDA-PMI
•
BEInGRID
• CELL version, on top of LC
•
In.Sy.Eme
• ASSISTANT for Mobile Grid
• Component-based Grid-aware version
3
The parmod construct
i
n
p
u
t
s
e
c
t
i
o
n
VP
VP
VP
VP
VP
VP
VP
VP
o
u
t
p
u
t
s
e
c
t
Shared state
Multiple input and output typed data streams
Set of Virtual Processors (VP) executing user code
VPs have assigned topology for naming (one, none, arrays)
4
The parmod construct
i
n
p
u
t
s
e
c
t
i
o
n
VP
VP
VP
VP
VP
VP
VP
VP
o
u
t
p
u
t
s
e
c
t
Shared state
distribution and collection strategies
multicast, scatter, on-demand, scheduled;
gather from all, from any, reduce
input and output sections can also host arbitrary user code
5
The parmod construct
i
n
p
u
t
s
e
c
t
i
o
n
VP
VP
VP
VP
VP
VP
VP
VP
o
u
t
p
u
t
s
e
c
t
Partitioning rules,
replication
Shared state
VPs host several user functions, activation can be data-driven
(CSP-like nondeterministic execution, guarded channels)
VPs share data structures
(run-time provides consistency)
6
Architetture Parallele e Distribuite
2008-09
Grid Computing:
Stato e Prospettive
7
Le piattaforme abilitanti distribuite
• Cluster omogenei, in generale con nodi paralleli SMP / NUMA
 Cluster eterogenei
 Virtual Private Networks, su scala LAN, MAN, WAN
 Grid
Dom. amm.
Dominio amministrativo
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
Dom. amm.
Linux / Intel
Power PC / MacOS
2100
2100
2100
2100
2100
2100
2100
2100
2100
SUN / Solaris
Middleware
8
2100
2100
2100
2100
2100
2100
2100
2100
Data Storage
Grid locale su
Rete Fotonica
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
Mainframe
2100
2100
2100
2100
2100
2100
2100
Grid locale
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
Data Source
Cluster
2100
2100
2100
Esempi di scenari di
applicazioni su Grid:
• Singoli job lanciati su
singoli nodi
• Job paralleli lanciati su più
nodi, con co-allocazione
statica
• Job paralleli su più nodi
con esecuzione e coallocazione dinamica e
adattiva
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
Data Source
Dalla tecnologia Grid corrente a
Next Generation Grid
9
2100
2100
2100
2100
2100
2100
2100
2100
Esecuzione di un singolo job (sequenziale o
parallelo) su un singolo nodo
Risorse di esecuzione
candidate e selezione
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
codice, locale o remoto
dati
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
• Scheduling statico
• Spesso, esecuzione
Batch (code)
• Trasferimento dati via
File Transfer
• Possibilità di
pianificare più fasi
sequenziali utilizzando
risorse diverse e File
Transfer
10
2100
2100
2100
2100
2100
2100
2100
2100
Esecuzione di un job parallelo su più nodi,
con co-allocazione statica
Risorse di esecuzione
candidate e selezione
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
codice, locale o remoto
dati
• Scheduling statico e coallocazione
• Esecuzione on demand,
interattiva, (batch),…
• Parallelismo intra- e internodo: non solo task
indipendenti
• Dati comunicati via files,
virtualizzazione storage, e
data-streaming
• Forme di parallelismo
sensibili alla banda,
latency-hiding
11
2100
2100
2100
2100
2100
2100
2100
2100
Esecuzione di un job parallelo su più nodi, con coallocazione ed esecuzione dinamica e adattiva
Fase iniziale di co-allocazione
statica, ed esecuzione sulla
configurazione iniziale
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
In seguito ad eventi legati a
emergenze,
malfunzionamenti,
esigenze di più elevata
performance (Qos):
riallocazione e
ristrutturazione dinamica di
codici e dati
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
2100
(replicazione, partizionamento,
bilanciamento)
in modo da rispettare un
determinato
“contratto di performance”
12
Grid Computing
Piattaforma Grid:
• “ Distributed computing infrastructure for
• coordinated resource sharing
• coordinated problem solving
• in dynamic, multi-institutional Virtual
Organizations (VO),
• able to guarantee planned level of
performances ”
13
Grid Computing: una nuova tecnologia nata dalla
convergenza di tecnologie
Distributed/Web
Computing: Objects
/ Component
Software Technology
Mobile Device
Technology, Pervasive &
Ubiquitous Computing
High-performance
Computing, Cluster
Computing
Knowledge
Management and
Data Intensive
Computing
14
Applicazioni Grid-aware
•
•
•
•
•
•
•
•
•
•
•
Gestione rischi ed emergenze
Telecomunicazioni
Wearable computing
e-business, Filiere e distretti industriali (PMI), Digital Business
Ecosystems
Beni culturali
Progettazione cooperativa
Sanità, medicina
Biotecnologie
Robotica
Tutte le scienze computazionali
ecc.
15
“Non solo calcolatori”: tecnologia pervasiva e
“ubiqua”, dispositivi mobili
• Dispositivi mobili, PDA
 Miniaturizzazione, embedding
 Wearable Computing
Fonte:
EuroTeCH Group,
Udine
16
Tecnologia Grid:
“person-centric”
• Piattaforme facili da usare
– “People are nodes”
• Paradigma “Anytime - Anyhow - Anywhere”
– Esempi: e-Work, e-Health, …
– Nuovi supporti a Risk Management
 Grid = Milioni di nodi di elaborazione eterogenei,
interconnessi e cooperanti dinamicamente
 Applicazioni naturalmente distribuite, eterogenee, dinamiche e
adattive
17
Middleware minimale: servizi base
(ricerca di risorse, prenotazione, trasferimento dati, lancio
esecuzione, ecc.)
•
•
•
•
Grid Middleware “base”: standard
Globus 2.x, 4.x, …, UNICORE, …
Global Grid Forum (GGF): standardizzazione
Open Grid Service Architecture (OGSA)
– dai Web Services ai Grid Services
• …..
• Non sono strumenti di sviluppo applicazioni.
• Non sono adatti ad applicazioni caratterizzate da alta
eterogeneità, dinamicità, mobilità.
18
Grid nella loro interezza:
NEXT GENERATION GRID
Per applicazioni industriali
– in molti casi, anche per il calcolo scientifico
le caratteristiche di
– Eterogeneità,
– Dinamicità e adattività (“autonomicità”),
– Capacità di usare in parallelo un numero qualsiasi, e
variabile, di risorse,
– Security consistente con la tecnologia Grid,
– Gestione conoscenza Grid-wide,
sono irrinunciabili per un deciso miglioramento
rispetto alle attuali tecnologie IT e Web.
19
ADATTIVITÁ della configurazione alle prestazioni:
esempio (ASSIST)
Perturbation : new
applications are created
800000
5 processors
700000
600000
8 processors
4 processors
Comp. time (msec.)
500000
Maximum Service
Time
400000
specified in the
contract
300000
Current Service Time
200000
Average Service Time
100000
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Stream elements
Evolution of computation
20
Adattività in ASSIST:
stesso modulo autoriconfigurante (farm / map) per il controllo
dell’occupazione di memoria
Esecuzione con modalità
MAP e 5 worker
Esecuzione con modalità
FARM e 5 worker
120000
Modalità MAP 10 worker
VM_Data(KB)
100000


80000
Migrazione su
nodi diversi
60000
Riconfigurazione
delle prestazioni
Dimensione di N = 5000 interi
Occupazione N² = 25M interi
~ 95 MB
Virtual Memory Data
Size per Process
40000
20000
0
1
3
5
7
9
11
13
Trascorrere dell'elaborazione
complessiva (min)
21
Adattività in ASSIST:
stesso modulo autoriconfigurante (farm / map) per il controllo del
tempo di servizio
Caso iniziale con modalità
FARM e 1 worker
Modalità FARM e 5
worker
Tempo medio di servizio di
Presenta (sec)
140
Modalità MAP e 5 worker
120
Modalità MAP e 10 worker
100
Riconfigurazione
delle funzioni
Riconfigurazione
delle prestazioni
80
60
40
20
0
1
3
5
7
9
11
Trascorrere dell'elaborazione
complessiva (min)
13


Dimensione di N = 5000 interi
Occupazione N² = 25M interi
~ 95 MB
Tempo Medio di Servizio
di Presenta
Contratto di QoS:
variato
dinamicamente il
massimo Tempo di
Servizio consentito
22
Progetto In.Sy.Eme
(Integrated Systems for Emergency)
Mobile Grid
Concetto di Grid Computing applicato in
contesti pervasivi, mobili ed
estremamente dinamici
(WorkPackage 3)
23
Piattaforma distribuita In.Sy.Eme
Sistema UNICO
di risorse hw e sw, centrali e decentrate,
generali ed embedded, fisse e mobili, …
Cluster
Workstation
Integrazione ELABORAZIONE +
COMUNICAZIONE
per Modelli di Previsione,
Supporto alle Decisioni,
Gestione della Conoscenza, …
Workstation
PDA
PDA
MOBILE (PERVASIVE) GRID: gestione
globale,
PDA
PDA
adattiva e context-aware,
Workstation
per il
PDA
Workstation
controllo
dinamico della
Cluster
PDA
PDA
Qualità del Servizio (QoS)
Data & Knowledge
Server
delle applicazioni
vari tipi di reti fisse, mobili, ad hoc
24
Esempio: gestione delle inondazioni fluviali
livello acqua, morfologia terreno, …
Modello previsionale idrologico,
idrodinamico
Data Mining
sul percorso del
fiume, …
Post-elaborazione (non banale)
precipitazioni nel
tempo e nello spazio, …
da satellite, da radar
meteo, da rilevatori
pluviometrici, … (es:
ALADIN)
soccorritori, sovraintendenti,
autorità, …, altri sistemi, …
25
Flood Forecasting Model
Modello idrologico
Esempio: MIKE 21
Equazioni differenziali della massa e
momento
Sistemi tridiagonali di grandi
dimensioni
Data- & compute- intensive
26
Modelli di previsione: quando e come
eseguirli?
• Nella struttura piramidale dell’organizzazione per la
gestione delle emergenze, ogni soggetto (“utente”)
ha propri interessi ed esigenze.
• Diverse modalità per utilizzare, e interagire con, il
sistema di gestione delle emergenze.
• Modelli a medio-lungo termine
– offline
• Modelli a breve termine e in real-time
– on demand
27
Elaborazioni a medio-lungo termine, offline
 Elaborazione “di routine” e operatività normale
visualizzazione
Cluster
Workstation
Workstation
PDA
PDA
PDA
PDA
Workstation
PDA
PDA
elaborazione
modelli
Workstation
Cluster
PDA
Data & Knowledge
Server
PDA
visualizzazione
28
Elaborazioni offline vs on demand
• Offline:
– Definizione di strategie (GIS, Meteo, modelli, DSS, Data
Mining), alte prestazioni (data, computation)
– Problematica tecnologicamente avanzata, ma con
alcuni risultati scientifico-tecnici noti in letteratura
• On demand: Adattività e Context-Awareness
– Problematica sostanzialmente nuova
– Il sistema deve essere capace di adattare
dinamicamente le applicazioni alle caratteristiche
ed ai requisiti degli utenti e del contesto (QoS)
29
Applicazioni Adattive e Context-Aware
 (Potenziale) emergenza e operatività normale
elaborazione
modelli
Cluster
Workstation
visualizzazione
Workstation
PDA
PDA
PDA
PDA
elaborazione
modelli
PDA
PDA
Workstation
PDA
Workstation
Cluster
PDA
Data & Knowledge
Server
visualizzazione
30
Applicazioni Adattive e Context-Aware
 Emergenza e operatività ridotta
Gestione dinamica QoS-aware di risorse
molto eterogenee di calcolo + comunicazione:
uso ottimale delle risorse disponibili.
Recovery delle informazioni.
elaborazione
modelli
Cluster
Workstation
Workstation
PDA
PDA
PDA
PDA
PDA
PDA
Workstation
PDA
elaborazione
modelli
e
PDA
visualizzazione
Workstation
Data & Knowledge
Modifica dinamica di programmi
(modelli) e
Cluster
Server
di dati (informazioni disponibili / da inferire):
modelli predittivi.
visualizzazione
31
Applicazioni Adattive e Context-Aware
 Emergenza e operatività ridotta
Gestione dinamica QoS-aware di risorse
molto eterogenee di calcolo + comunicazione:
uso ottimale delle risorse disponibili.
Recovery delle informazioni.
PDA
PDA
PDA
PDA
PDA
PDA
PDA
elaborazione
modelli e
visualizzazione
Modifica dinamica di programmi (modelli) e
di dati (informazioni disponibili / da inferire):
modelli predittivi.
elaborazione
modelli e
visualizzazione
32
High-Performance Computing (HPC)
•
Diverse elaborazioni hanno caratteristiche DATA-& COMPUTE-INTENSIVE
–
•
Modelli previsionali, DSS, GIS, METEO, modelli predittivi, strategie di networking, …
Vari tipi di risorse per HPC, con tecnologie sia tradizionali che innovative:
On-chip Multicore TechnologyEmbedding in dispositivi mobili / indossabili
L2 cache
Cluster
P
L1 cache
P
P
Data & Knowledge
Server
L1 cache
P
P
P
P
Programmabilità +
Portabilità ?
P
PDA
PDA
PDA
PDA
PDA
33
First experiment
input data stream:
output data
tuple of scalar
stream:
parameters
solution matrix
Flood
Generator
Forecasting
Client
module
module
module
input data
interface
(from sensors,
visualization
(to operator’s PDA,
services, etc.)
services, etc.)
34
Experiment: flood forecasting
From sensors and monitoring, for each
point:
position (x,y)
water depth (H)
water surf. Elevation (ξ)
depth av. Velocity (u,v)
Mass and momentum partial
differential equations
Large tridiagonal systems
Data- & compute- intensive
Fx and Fy
tridiagonal system solving
We can obtain different qualities
with different samplings in
space
and time
35
Computing and communication resources
36
Features of a pervasive distributed platform
Central Servers
Monitoring areas: decentralized Interface Nodes connecting wireless
networks for sensors and mobile devices (PDA) to fixed networks and
servers
37
Adaptivity and Context-Awareness
PDA
PDA
PDA
Cluster
PDA
Data & Knowledge
Server
.
.
.
.
.
.
PDA
PDA
PDA
HPC application, suitable for
central servers
(performance, data size, precision,
…)
PDA
Dynamic restructuring, suitable for decentralized / embedded /
mobile nodes (trade-off: performance, memory, precision, faulttolerance, energy saving, …), and dynamic deployment
38
Experiment: adaptivity and context-awareness
Dynamic transitions
between alternative
versions :
RECONFIGURATION
and
communication
DEPLOYMENT
network 2
communication
network 1
Context
events
Forecasting model:
version 1
data streaming control
and network interfaces
interface node
Forecasting model:
version 0
Context
events
central server
Forecasting model:
version 2
Context
events
C lient visualization
PDAs
39
Experiment: configuration
Forecasting model:
version 1
data streaming control
and network interfaces
PDAs
Forecasting model:
version 2
Multicore-based
(CELL)
C lient visualization
Forecasting model:
version 0
40
Operations:
adaptive versions of the same module
Central
server
Interf.
OP0
Central Server is again
available and network is
able to guarantee the
requested QoS :
• switch to OP0 again,
• deployment of
application state onto
Central Server
+ other transitions between
versions
according to contex events and
system state
Central server is no more
OP1 node
available and/or network
has low QoS:
• switch to OP1,
• deployment of
application state onto
Interface Node
Client achieves low QoS for
visualization, PDA
resources are available :
• switch to OP2,
• deployment of
application state onto
PDA network
OP2
PDA
net
41
Events, adaptivity, and targets
Events related to:
• Network and monitoring
–
–
–
–
Availability
Connectivity
Bandwidth, Performance
Load, …
• Energy consumption
• Requests for better QoS
– Response/completion time
– Precision
– Client load balancing /
priority, …
Adaptivity actions:
• Increase QoS of current
operation
– parallelism degree
– data size
• Switch to a different
operation with the required
QoS or the best possible QoS
–
–
–
–
algorithm
parallelism paradigm
memory management
power consumption
Different resources
42
Reconfiguration and deployment
LOGICALLY SHARED REPOSITORY
(modules, operations, state, channels, run-time support, managers
cooperation)
Cache0
Working set of OP1
P0
Central
Server
Start deployment
Pn-1
...
(OP0)
• State consistency
• Checkpointing
• Active redundancy of
operations
Cachen-1
Interface
Node
(OP1)
OP1: processors and other
resources allocation
(parallelism construct)
43
da ASSIST …
External Objects
parmod
44
… a ASSISTANT
Context
Stream:
anche
da/verso
sensori,
attuatori
MANAGER
Rete di
Manager
• Manager come parte integrante (elemento primitivo) del Parmod
• Programmabile: formalismo opportuno facente parte di ASSISTANT
• Politiche di adattività e context-awareness
• Rete di Manager
45
ASSISTANT: adaptive and context-aware module
46
InSyEme Programming Model (ASSISTANT)
P
P
P
P
RED
Computational view of
information flows:
parallel and distributed
composition of
application modules
Management information
M
M
M
M
BLUE
Context information
Managers:
• adaptivity, contextawareness
• dynamic
reconfiguration and
deployment
• QoS control
C
C
C
C
Context interfaces:
devices , nodes and
GREEN networks monitoring
47
Experiment: module structure
RED: Information flows
Flood Forecasting
Module
Generator Module
Client Module
Functional Logic
Functional Logic
Functional Logic
Control Logic
Control Logic
Control Logic
BLUE: Manager
Context
interface
Network
monitoring
Context
interface
Performance
profiling
GREEN: Context
Context interface
48
RED
ASSISTANT application
BLUE
GREEN
49
Experimental results
9
scalability
8
7
6
5
Cluster 8M
Cell 8M
4
Cluster 32M
Cell 32M
3
2
1
0
0
2
4
6
8
10
parallelism degree
50
Experimental Results
128
service time
(sec)
64
32
24.4
16
Cluster 8M
8
Cell 8M
Cluster 32M
4
Cell 32M
3.1
2.66
2
1
0.98
0.5
0
2
4
6
8
10
parallelism degree
51
Low cost, low consumption, good performance solutions
for decentralized services
The application as a whole requires the cooperation of
BOTH centralized AND decentralized services in an ADAPTIVE way.
Decentralized HPC services are technologically feasible and valuable
to optimize QoS.
Localized computational power: aggregate performance and
scalability > (>>) central servers
52