Post on 02-May-2015
Architetture Parallele e Distribuite2008-09
1. ASSIST: cenno2. Grid Computing
3. Adattività
Livelli e moduli
2
Firmware
Hardware
Applicazioni
Processi
Assembler
Applicazione sviluppata con strumenti user-friendly
Programma parallelo(processi comunicanti e/o
oggetti condivisi)
compilata / interpretata in
compilato / interpretato in un programma
parallelo eseguibile su
Firmware Uniprocessor di vari tipi
Multiprocessor di vari tipi e con vari processori
Cluster di vari tipi e con vari processori
Architettura 1
Architettura 2
Architettura 3
Architettura X
indipendente dal concetto di processo
indipendente dall’architettura
supporto diverso per ogni architettura
3
Un ambiente di programmazione per macchine parallele e Next Generation Grid
Projects:• ASI-PQE2000• CNR Agenzia 2000• MIUR-CNR Strategic Programmes• MIUR-FIRB Grid.it• SFIDA-PMI• BEInGRID• In.Sy.Eme
Implementations:• Heterogeneous Cluster/Beowulf
• CORBA, WS interoperability
• Grid version (on top of Globus 4)
• Component-based Grid-aware version
• CELL version, on top of LC
• ASSISTANT for Mobile Grid
Department of Computer Science, University of Pisa
ASSISTA Programming Environment for High-performance Portable Applications on
Clusters, Large-scale Platforms, and Grids
Department of Computer Science, University of Pisa
ASSISTA Programming Environment for High-performance Portable Applications on
Clusters, Large-scale Platforms, and Grids
4
The parmod construct
VP
VP VP
VP VP
VP
VP VP
i n p u t s e c t i o n
Shared state
o u t p u t s e c t
Multiple input and output typed data streams
Set of Virtual Processors (VP) executing user code
VPs have assigned topology for naming (one, none, arrays)
5
The parmod construct
VP
VP VP
VP VP
VP
VP VP
i n p u t s e c t i o n
Shared state
o u t p u t s e c t
distribution and collection strategiesmulticast, scatter, on-demand, scheduled;
gather from all, from any, reduce
input and output sections can also host arbitrary user code
6
The parmod construct
VP
VP VP
VP VP
VP
VP VP
i n p u t s e c t i o n
Shared state
o u t p u t s e c t
VPs host several user functions, activation can be data-driven(CSP-like nondeterministic execution, guarded channels)
VPs share data structures (run-time provides consistency)
Partitioning rules, replication
7
Architetture Parallele e Distribuite2008-09
Grid Computing: Stato e Prospettive
8
Le piattaforme abilitanti distribuite
• Cluster omogenei, in generale con nodi paralleli SMP / NUMA
Cluster eterogenei Virtual Private Networks, su scala LAN, MAN, WAN
Grid
2100 2100 2100 2100
2100 2100 2100 2100
Linux / Intel
2100 2100 2100 2100
2100 2100 2100 2100
Power PC / MacOS
2100
2100 2100 2100 2100
2100 2100 2100 2100
SUN / Solaris
Dominio amministrativo
Dom. amm.
2100 2100 2100 2100
2100 2100 2100 2100
Dom. amm.
Middleware
9
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
2100 2100 2100 2100
2100 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 co-allocazione dinamica e adattiva
Dalla tecnologia Grid corrente a Next Generation Grid
Data Storage
Mainframe
Cluster
Data SourceData Source
Grid locale su Rete Fotonica
Grid locale
10
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
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
codice, locale o remotodati
• Scheduling statico• Spesso, esecuzione
Batch (code)• Trasferimento dati via
File Transfer• Possibilità di
pianificare più fasi sequenziali utilizzando risorse diverse e File Transfer
11
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
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
dati• Scheduling statico e co-
allocazione• Esecuzione on demand,
interattiva, (batch),…• Parallelismo intra- e inter-
nodo: non solo task indipendenti
• Dati comunicati via files, virtualizzazione storage, e data-streaming
• Forme di parallelismo sensibili alla banda, latency-hiding
codice, locale o remoto
12
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
2100 2100 2100 2100
2100 2100 2100 2100
Esecuzione di un job parallelo su più nodi, con co-allocazione ed esecuzione dinamica e adattiva
Fase iniziale di co-allocazione statica, ed esecuzione sulla configurazione iniziale
In seguito ad eventi legati a emergenze, malfunzionamenti, esigenze di più elevata performance (Qos):riallocazione e ristrutturazione dinamica di codici e dati (replicazione, partizionamento, bilanciamento)
in modo da rispettare un determinato “contratto di performance”
13
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 ”
14
Grid Computing: una nuova tecnologia nata dalla convergenza di tecnologie
Distributed/Web Computing: Objects / Component Software Technology
High-performance Computing, Cluster Computing
Mobile Device Technology, Pervasive & Ubiquitous Computing
Knowledge Management and Data Intensive Computing
15
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.
16
“Non solo calcolatori”: tecnologia pervasiva e “ubiqua”, dispositivi mobili
• Dispositivi mobili, PDA Miniaturizzazione, embedding
Wearable Computing
Fonte: EuroTeCH Group, Udine
17
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
18
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à.
19
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.
20
0
100000
200000
300000
400000
500000
600000
700000
800000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Stream elements
Com
p. ti
me
(mse
c.)
Current Service Time
Average Service Time
Maximum Service Time
specified in the contract
4 processors
Perturbation : newapplications are created
5 processors
8 processors
ADATTIVITÁ della configurazione alle prestazioni: esempio (ASSIST)
Evolution of computation
21
0
20000
40000
60000
80000
100000
120000
1 3 5 7 9 11 13
Trascorrere dell'elaborazione complessiva (min)
VM
_D
ata
(KB
)
Virtual Memory DataSize per Process
Esecuzione con modalità FARM e 5 worker
Esecuzione con modalità MAP e 5 worker
Adattività in ASSIST:stesso modulo autoriconfigurante (farm / map) per il controllo
dell’occupazione di memoria
Dimensione di N = 5000 interi Occupazione N² = 25M interi
~ 95 MB
Riconfigurazione delle prestazioni
Migrazione su nodi diversi
Modalità MAP 10 worker
22
0
20
40
60
80
100
120
140
1 3 5 7 9 11 13
Trascorrere dell'elaborazione complessiva (min)
Tem
po m
edio
di s
ervi
zio
di
Pres
enta
(sec
)
Tempo Medio di Serviziodi Presenta
Adattività in ASSIST:stesso modulo autoriconfigurante (farm / map) per il controllo
del tempo di servizio
Dimensione di N = 5000 interi Occupazione N² = 25M interi
~ 95 MB
Caso iniziale con modalità FARM e 1 worker
Modalità FARM e 5 worker
Modalità MAP e 5 worker
Riconfigurazione delle funzioni
Modalità MAP e 10 worker
Contratto di QoS: variato dinamicamente il massimo Tempo di Servizio consentito
Riconfigurazione delle prestazioni
23
Progetto In.Sy.Eme(Integrated Systems for Emergency)
Mobile GridConcetto di Grid Computing applicato in
contesti pervasivi, mobili ed estremamente dinamici
(WorkPackage 3)
24
Cluster
Data & Knowledge ServerCluster
Workstation
WorkstationWorkstation
WorkstationPDA
PDAPDA
vari tipi di reti fisse, mobili, ad hoc
PDA
PDAPDA
PDA
Piattaforma distribuita In.Sy.EmeIntegrazione ELABORAZIONE +
COMUNICAZIONEper Modelli di Previsione,Supporto alle Decisioni,
Gestione della Conoscenza, …
Sistema UNICO di risorse hw e sw, centrali e decentrate, generali ed embedded, fisse e mobili, …
MOBILE (PERVASIVE) GRID: gestione
globale,
adattiva e context-aware,
per il controllo dinamico della
Qualità del Servizio (QoS)
delle applicazioni
Esempio: gestione delle inondazioni fluviali
25
soccorritori, sovraintendenti, autorità, …, altri sistemi, …
livello acqua, morfologia terreno, …
Post-elaborazione (non banale)
sul percorso del fiume, …
precipitazioni nel tempo e nello spazio, …
da satellite, da radar meteo, da rilevatori pluviometrici, … (es:
ALADIN)
Modello previsionale idrologico, idrodinamico Data Mining
Flood Forecasting Model
26
Modello idrologico
Esempio: MIKE 21
Equazioni differenziali della massa e momento
Sistemi tridiagonali di grandi dimensioni
Data- & compute- intensive
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
28
Elaborazioni a medio-lungo termine, offline
PDA
PDA
PDA
PDA
PDAPDA
PDA
PDA
Workstation
Cluster
Data & Knowledge ServerCluster
Workstation
WorkstationWorkstation
Elaborazione “di routine” e operatività normale
elaborazione modelli
visualizzazione
visualizzazione
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
30
Applicazioni Adattive e Context-Aware
PDA
PDA
PDA
PDA
PDAPDA
PDA
PDA
Workstation
Cluster
Data & Knowledge ServerCluster
Workstation
WorkstationWorkstation
(Potenziale) emergenza e operatività normale
elaborazione modelli
visualizzazione
visualizzazione
elaborazione modelli
31
Applicazioni Adattive e Context-Aware
PDA
PDA
PDA
PDA
PDAPDA
PDA
PDA
Workstation
Cluster
Data & Knowledge ServerCluster
Workstation
WorkstationWorkstation
Emergenza e operatività ridotta Gestione dinamica QoS-aware di risorse molto eterogenee di calcolo + comunicazione: uso ottimale delle risorse disponibili.Recovery delle informazioni.
Modifica dinamica di programmi (modelli) e di dati (informazioni disponibili / da inferire):modelli predittivi.
elaborazione modelli
elaborazione modelli e visualizzazione
visualizzazione
32
Applicazioni Adattive e Context-Aware
PDA
PDA
PDA
PDA
PDAPDA
Emergenza e operatività ridotta
elaborazione modelli e visualizzazione
elaborazione modelli e visualizzazione
PDA
Gestione dinamica QoS-aware di risorse molto eterogenee di calcolo + comunicazione: uso ottimale delle risorse disponibili.Recovery delle informazioni.
Modifica dinamica di programmi (modelli) e di dati (informazioni disponibili / da inferire):modelli predittivi.
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:
33
ClusterData & Knowledge
Server
PDA
PDA
PDAPDA
PDA
L1 cache
P P P P
L1 cache
P P P P
L2 cache
On-chip Multicore Technology
• 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:
Embedding in dispositivi mobili / indossabili
Programmabilità + Portabilità ?
First experiment
34
Flood
Forecasting
module
Generator
module
Client
module
input data
interface
(from sensors,
services, etc.)
visualization
(to operator’s PDA,
services, etc.)
input data stream:
tuple of scalar
parameters
output data
stream:
solution matrix
Experiment: flood forecasting
35
Fx and Fy
From sensors and monitoring, for each point:
position (x,y)water depth (H)water surf. Elevation (ξ)depth av. Velocity (u,v)
We can obtain different qualities with different samplings in
spaceand time
tridiagonal system solving
Mass and momentum partial differential equations
Large tridiagonal systems
Data- & compute- intensive
Computing and communication resources
36
Features of a pervasive distributed platform
37
Central Servers
Monitoring areas: decentralized Interface Nodes connecting wireless networks for sensors and mobile devices (PDA) to fixed networks and servers
38
Adaptivity and Context-Awareness
Cluster
Data & Knowledge Server
.
.
.
.
.
.
HPC application, suitable for central servers(performance, data size, precision, …)
PDA
PDAPDA
PDA
PDA
PDAPDA
PDA
Dynamic restructuring, suitable for decentralized / embedded / mobile nodes (trade-off: performance, memory, precision, fault-tolerance, energy saving, …), and dynamic deployment
PDAscentral server
interface node
communication network 1
communication network 2
Experiment: adaptivity and context-awareness
Forecasting model: version 0
Forecasting model: version 1
Forecasting model: version 2
data streaming control and network interfaces
C lient - visualization
Context events
Context events
Context events
Dynamic transitions between alternative
versions :RECONFIGURATION
and DEPLOYMENT
39
Experiment: configuration
40
Multicore-based (CELL)
Forecasting model: version 0
Forecasting model: version 1
data streaming control and network interfaces
C lient - visualization
PDAs
Forecasting model: version 2
PDA net
Interf. node
Central server
Operations: adaptive versions of the same module
41
OP0 OP1
OP2
Central server is no more 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
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
Events, adaptivity, and targetsEvents 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
43
Cachen-1Cache0
Pn-1
LOGICALLY SHARED REPOSITORY(modules, operations, state, channels, run-time support, managers cooperation)
P0
. . .Central Server
(OP0)
Interface Node
(OP1)
OP1: processors and other resources allocation
(parallelism construct)
Start deployment
Working set of OP1
• State consistency• Checkpointing
• Active redundancy of operations
da ASSIST …
44
In_Sect Out_SectVP
External Objects
parmod
… a ASSISTANT
45
• Manager come parte integrante (elemento primitivo) del Parmod• Programmabile: formalismo opportuno facente parte di ASSISTANT• Politiche di adattività e context-awareness• Rete di Manager
In_Sect Out_SectVP
Context
MANAGERRete di
ManagerStream:anche da/verso sensori, attuatori
46
ASSISTANT: adaptive and context-aware module
InSyEme Programming Model (ASSISTANT)
47
Computational view of information flows:parallel and distributed composition of application modules
Managers: • adaptivity, context-
awareness• dynamic
reconfiguration and deployment
• QoS control
Context interfaces:devices , nodes and networks monitoring
Context information
Management information
P
P
P
P
M
M
M
M
C
CC
C
RED
BLUE
GREEN
Experiment: module structure
48
Functional Logic
Control Logic
Generator Module
Functional Logic
Control Logic
Flood Forecasting Module
Functional Logic
Control Logic
Client Module
Context interface
Network monitoring
Performance profiling
Context interface
Context interface
GREEN: Context
BLUE: Manager
RED: Information flows
ASSISTANT application
49
RED
BLUE
GREEN
Experimental results
50
0 2 4 6 8 100
1
2
3
4
5
6
7
8
9
scalability
Cluster 8MCell 8MCluster 32MCell 32M
parallelism degree
Experimental Results
51
0 2 4 6 8 10
0.1
1
10
100
24.4
3.1
2.66
0.98
service time (sec)
Cluster 8MCell 8MCluster 32MCell 32M
parallelism degree
Low cost, low consumption, good performance solutions for decentralized services
52
Localized computational power: aggregate performance and scalability > (>>) central servers
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.