2/5/2012
1
Real-Time Systems LaboratoryRETIS Lab
Giorgio Buttazzo
L’evoluzioneL’evoluzione dell’informaticadell’informatica
Sommario
ImpattoImpatto nellanella societàsocietà
TendenzeTendenze generaligenerali
ProgettiProgetti pressopresso lala ScuolaScuola Sant’AnnaSant’Anna
UnoUno sguardosguardo alal futurofuturoUnoUno sguardosguardo alal futurofuturo
2/5/2012
2
InformaticaScienza che si occupa dei fondamenti teoricidell’elaborazione dell'informazione:
Linguaggi per descrivere l'informazione
Algoritmi per trasformare l'informazione
Politiche di gestione delle risorse per rendere piùefficiente l’uso del calcolatore (Sistemi operativi)
I t lli tifi i l t di l i l i diIntelligenza artificiale - metodi per la risoluzione diproblemi e ragionamenti tipici della mente umana.
Reti di calcolatori - metodi per il trasferimento diinformazione su canali di comunicazione.
Informatica
L’evoluzione dell’informaticaè strettamente legataa quella dei calcolatori
2/5/2012
3
Evoluzione esponenziale
prestazioni
108 IPS
dimensioni10 m3 10 IPS10 m
1950 1960 1970 1980 1990 2000 2010
10 IPS 10 cm3
La legge di Moore
Nel 1965, Gordon Moore, uno dei fondatoridell’Intel predisse che il numero di transistor
In effetti, fino ad oggi,La poten a di calcolo dei comp ter è
dell Intel, predisse che il numero di transistornei circuiti integrati sarebbe raddoppiato ogni18 mesi fino al raggiungimento dei limiti fisici.
La potenza di calcolo dei computer èraddoppiata ogni 2 anniLa memoria dei computer è decuplicata ogni4 anni
2/5/2012
4
Oggi il 98% dei processori sono di tipo embedded.
Invisibilità
Sono oggetti contenenti al loro interno un computer,che controlla le funzionalità, gestisce le risorse, e
Sistemi Embedded
semplifica le interazioni con l’utente:
Ambienteattuatori
imicrocontrollore
Oggetto
sensori
comunicazione
utente altre unità
2/5/2012
5
Tale numero è destinato a crescere:
Smart objects
Chiavi elettroniche
penne cheregistrano
Localizzatori GPS
Contapassiregistrano
Scarpe energeticheCardiofrequenzimetri
Oggi l’informatica influisce su tutti i settori dellanostra società:
Pervasività
IndustriaIndustria
TrasportoTrasporto
AgricolturaAgricoltura
MedicinaMedicina
EdiliziaEdilizia
ArteArte ee intrattenimentointrattenimento
2/5/2012
6
Industria Industriaprogrammazione
e controllo di robot
Assemblaggio
Produzioneautomatizzata:
• precisioneffi i• efficienza
• qualità• costo
IndustriaControllo del trafficoSupporto alla guida:
Trasporti
• affidabilitài• sicurezza
• efficienza• prestazioni
2/5/2012
7
IndustriaControllo macchineAutomazionearatura, semina
Agricoltura
irrorazione, raccolta
rapiditàefficienzaefficienzariduzione uso sostanze chimiche
IndustriaMedicinaTAC, PET, NMR
AnalisiMonitoraggioMonitoraggioChirurgia assistita
2/5/2012
8
IndustriaEdilizia
Strumenti di misura Progettazione CAD
IndustriaArte e intrattenimento
Stereogrammi Virtual games
Animazione Smart toys
2/5/2012
9
Dall’Hardware al Software
• Oggi si assiste ad un processo dismaterializzazione in cui molte funzioni vengono
frealizzate via software.
• Perché?1. Il software è più flessibile dell’hardware
2. Può essere modificato e adattato velocemente
3. E’ possibile aggiungere nuove funzionalità
4. Può evolvere verso sistemi intelligenti e autonomi
5. Non ha peso
6. Può viaggiare alla velocità della luce!
IndustriaTrasferimento delle informazioni
scannerizzazione stampa
Se nel processo non si perde informazione, la
copia è uguale all’originale
codifica decodifica
trasmissione
2/5/2012
10
IndustriaTutto si traduce in un file
IndustriaSmaterializzazionedi parti meccaniche
Steer by wire
SensorMotor
SensorMotor
ControlUnit
2/5/2012
11
109
1010Linee di codice in un’auto
Complessità crescente
105
106
107
108
10
1980 1990 2000 2010 2020102
103
104
100 M30 M
100 M
Complessità crescenteLinee di codice
1 M
10 M
200 K
2 M
10 M
100 K
2/5/2012
12
Complessità e bug
Con il crescere della complessità crescono anchegli errori software:
100
1000
10.000bugs
1 K 100 K 1 M 10 M0
10
10K
Linee di codice
Affidabilità del software
Quando il controllo di un aereo è affidato a unprogramma lungo 100 milioni di istruzioni,l’ ffid bilità è bi tti i il’affidabilità è un obiettivo primario
100 milioni di istruzioni
2/5/2012
13
Affidabilità del software
L’affidabilità non dipende solo dalla correttezza delleoperazioni, ma anche dal tempo in cui sono eseguite:
controllorecontrollore
i
comandox(t)
Δ
azioney(t+Δ)
Un’azione corretta che arriva in ritardo può essereinutile o addirittura dannosa.
Sistemi Real-Time
I sistemi di calcolo che devono garantireritardi temporali limitati prendono il nomedi sistemi real-time.
I ritardi massimi devono essere garantitiper ogni possibile combinazione di eventi
ossia nel caso peggiore possibile!
2/5/2012
14
Leggi di Murphy
Se qualcosa può andar male, lo farà
Se un sistema smetterà di funzionare, lo farà nel peggior
momento possibile
P i i l iPrima o poi, la peggiore combinazione possibile di
circostanze è destinata a prodursi.
Dimostrazione della legge di Murphy
Qual è la probabilità che E accada in n giorni?Sia pE la probabilità che un evento E accada in un giorno
qE = 1 − pEprob. che E nonaccada in un giorno
Qual è la probabilità che E accada in n giorni?
day 1 day 2 day 3 day 4 day 5
pE pE pE pE pE
28
g
QE (n) = (1 − pE )nprob. che E nonaccada in n giorni
PE (n) = 1 − QE (n)prob. che Eaccada in n giorni
2/5/2012
15
Capire la legge di Murphy
PE (n) = 1 − (1 − pE )nPE (n)
n
1
pE = 0.0000000001
29
nSe qualcosa può andar male (per quanto pE siapiccolo), lo farà (cioè, la probabilità che E accada inun lungo periodo tende a 1).
Real-Time Systems LaboratoryRETIS Lab
2/5/2012
16
Struttura del software
OUTPUT
INPUT
OUTPUT
task buffer
Struttura del software
Generico task periodico
Ci
timer
tempo di calcolo
(periodo Ti )sincro
input
outputfattore di
utilizzazione
CiTi
Ui =
taskperiodico
Ti
Ci
timer (periodo Ti )
2/5/2012
17
Struttura del software
τ1 τ2
sensore
memorybuffer
motoresincro
sincro
input input
outputoutput
timer sincrotimertimer
La prevedibilità dipende dalla capacità di valutare i tempi dicalcolo e le interferenze subite dagli altri task.
Valutare Ci non è semplice
Ci tempo di calcolo massimo Cimax
?
# occorrenzeloop?
?
tempo diesecuzione
Cimin
Cimax
timer
2/5/2012
18
Priorità
Poiché molti task possono essere attivi simultaneamente, ilsistema operativo deve scegliere l’ordine con cui eseguirli.
Il metodo più comune consiste nell’associarea ogni task una priorità Pi e scegliere il taskcon priorità più elevata.
scheduling
Ad esempio, l’algoritmo Rate Monotonicassegna una priorità proporzionale allafrequenza di attivazione (rate) di un task:
Pi ∝ Ti
1
Esempio
τ1 τ2
C1 = 3 C2 = 6
Rate Monotonic: Pi ∝ 1/Ti
1
T1 = 102
T2 = 15
preemptionP1 > P2
τ1
3
τ1
τ210
15
20
300
6
tempo di risposta Ri
2/5/2012
19
Esempio
τ1 τ2
C1 = 3 C2 = 61
T1 = 102
T2 = 15
preemptionP1 > P2
τ1
3
costo di preemption
Rate Monotonic: Pi ∝ 1/Ti
τ1
τ210
15
20
300
6
tempo di risposta Ri
Esempio di schedulazione
τ1
τ2
τ3
τ4
Una schedulazione si dice fattibile se tutti i taskriescono a terminare entro il proprio periodo.
2/5/2012
20
Problemi di ricercaDato un insieme di task di cui è noto il codice: teoria
dei grafi
teoria deiValutare i tempi di calcolo massimo Ci
Determinare i “migliori” periodi di attivazione Ti
Esistenza: Dati un insieme di task di cui siano noti (Ci, Ti),d i l’ i di l i f ibil
teoria deicontrolli
ottimizzazionecombinatoriaDeterminare la priorità Pi dei task
determinare l’esistenza di una soluzione fattibile,indipendentemente dall’assegnamento di priorità.
Fattibilità: Dato un insieme di task (Ci, Ti) e un particolareassegnamento di priorità, verificare se laschedulazione è fattibile.
Problemi di ricerca
Esempio:TASK Ci (ms) Ti (ms)i ( ) i ( )
Altimetri 20 100Pressione 50 200Controllo 80 300Temperatura 30 500Visualizzazione 300 800
Assegnando le priorità secondo Rate Monotonic,
La schedulazione prodotta risulta fattibile?
Quali sono i tempi di risposta massimi dei task?
2/5/2012
21
Problemi di ricerca
Se si ha un sistema con n processori:
Come si estendono i problemi di esistenza e fattibilità?
P1 P2 P3 P4
Come si distribuisce il carico (ossia i task) sui variprocessori?
Come si tiene conto dei ritardi di comunicazione traprocessori per lo scambio dei dati?
Carico massimo
Per ogni algoritmo di scheduling e insieme di task, esiste uncarico massimo al di sopra del quale la schedulazione non èfattibile:fattibile:
12
0 18
τ1
τ2
P1 > P26
9
33
Un aumento di qualsiasi tempo di calcolo rende laschedulazione non fattibile.
833.093
63
=+=pU
2/5/2012
22
Carico massimo
Per ogni algoritmo di scheduling e insieme di task, esiste uncarico massimo al di sopra del quale la schedulazione non èfattibile:fattibile:
12
0 18
τ1
τ2
P1 > P26
9
S C t t i lt il i dSe C1 aumenta, τ2 termina oltre il suo periodo.
Carico massimo
Per ogni algoritmo di scheduling e insieme di task, esiste uncarico massimo al di sopra del quale la schedulazione non èfattibile:fattibile:
12
0 18
τ1
τ2
P1 > P26
9
S C t t i lt il i dSe C2 aumenta, τ2 termina oltre il suo periodo.
2/5/2012
23
Carico massimo
Dunque per questo insieme di task il carico massimo chegarantisce la fattibilità della schedulazione vale:
12
τ1
τ2
P1 > P26
833.065
31
21
==+=pU
0 189
Per un dato algoritmo, calcolare il carico massimo chegarantisca la fattibilità di un qualsiasi insieme di task.
Problema
Limite per Rate Monotonic
i( )12 /1 −≤ n
p nU
69%
carico
n
2/5/2012
24
Real-Time Systems LaboratoryRETIS Lab
ObiettivoAumentare prevedibilità ed efficienza dei sistemi dicontrollo computerizzati a bordo di aerei e automobili
2/5/2012
25
Risultato
E’ stato sviluppato un metodo che per ogni taskE stato sviluppato un metodo che per ogni task
calcola la massima lunghezza di una sezione noninterrompibile affinché la schedulazione sia fattibile;
seleziona i migliori punti in cui un task può essereinterrotto (che introducono il minore incremento).
VantaggiMaggiore prevedibilità nella stima dei tempi di calcolo;
Maggiore efficienza nell’utilizzo del processore.
ACTORS
ContestoSupporto per il software dei cellulari della prossimagenerazionegenerazione
ObiettiviSfruttare il parallelismo offerto dalle architetture multicoreRidurre l’interferenza tra le varie funzionalità del sistema
Ridurre il consumo energetico
2/5/2012
26
Il kernel Linux è stato integrato conmeccanismi di scheduling in grado di ridurrel i t f t l i tti ità di l l
ACTORS
le interferenze tra le varie attività di calcolo:
ARM11 (4 cores)Linux 2.6.x
Risparmio energetico
Assodato che conviene andare più lenti perrisparmiare energia, occorre capire come variano leprestazioni al variare della velocità:prestazioni al variare della velocità:
potenzaprestazioni
Livello minimo
velocitàvmin
2/5/2012
27
Risparmio energetico
Di solito le prestazioni dipendono dai vincolitemporali imposti sui task, per cui mantenere leprestazioni significa rispettare i vincoli:prestazioni significa rispettare i vincoli:
speed
1
0 5
S = 1 S = 0.5 S = 0.25
τi
time
0.5
Risparmio energeticoSupponiamo che un processore abbia 5 modalità difunzionamento: Modalità Consumo (mW)
ACTIVE (s = 1) 100ACTIVE (s = 0.75) 60ACTIVE (s = 0.5) 30ACTIVE (s = 0.25) 15SLEEP 4
E che l’applicazione sia costituita da 2 task periodici:S 1 τ1
τ2
S = 140 80
120600
1010 10
3030
U = 1/4 + 1/2 = 0.75
2/5/2012
28
Risparmio energetico
τ1
τ2
40 80
1010 10
3030
S = 1
P (mW)100
80
E = 100 T
2120600
t20
60
40
T
Risparmio energetico
τ1
τ2
40 80
1010 10
3030
S = 1
100
80
P (mW)U = 1/4 + 1/2 = 0.75
2120600
20
60
40
E = (100⋅0.75 + 4⋅0.25)T = 76 T
100 100
44t
T
2/5/2012
29
Risparmio energetico
τ1
τ2
40 80
1010 10
3030
S = 1
S = 0.75
120600
40 80
τ1
τ2
1313 13
4040
2120600
P ( W)
20
60
40
P (mW)
60
E = 60 T
tT
Reti di Sensori
© Scuola Superiore Sant’Anna 58
2/5/2012
31
Velivolo autonomo sensorizzato
Unità di CalcoloUnità di Calcolo ServomotoriServomotori
Scheda diScheda diComunicazioneComunicazione
Telecamera aTelecamera ainfrarossiinfrarossi
GPSGPSSensori di Sensori di TempTemp..
Monitoraggio del traffico
2/5/2012
32
ASCOLTA
Assistenza domiciliare allo SCOmpenso cardiaco attraversoLe Tecniche Avanzate di comunicazione digitale
Ridurre i costi di ricovero attraversoun monitoraggio continuo in casa.
Sviluppo di un sistema indossabilein grado di registrare, elaborare e
Obiettivi
g gtrasmettere via wireless un insiemedi parametri biomedici.
Rilevare automaticamentesituazioni critiche, richiedendoun intervento medico.
ASCOLTA
ECGSPO2 Blood
pressure
Breath signal
Body motion
2/5/2012
33
Invisibilità e pervasività:
computer e sensori sempre più piccoli
Tendenze dell’informatica
bottiglie (etichette elettroniche, tappi sensorizzati, …)
sedie (autoregolanti, massaggianti, riscaldanti)
occhiali (lenti adattive visione notturna )
computer e sensori sempre più piccoli,integrati in oggetti di uso quotidiano:
occhiali (lenti adattive, visione notturna, …)
abiti (adattivi, colori programmabili, mimetici, …)
Tendenze dell’informatica
La vera rivoluzione sarà l’integrazione diprocessori nel corpo umano:p p
cuore orecchio occhio cervello
Dalla compensazione di difetti al potenziamento disensi, memoria, capacità motorie
2/5/2012
34
Fin dove si spingerà questa tendenza?
Quali scenari possiamo prevedere nei prossimi
Prospettive future
Quali scenari possiamo prevedere nei prossimianni?
NanotecnologiaInformatica
Quale sarà l’impatto dell’integrazione tra
GeneticaRobotica
Telecomunicazioni ?
Real-Time Systems LaboratoryRETIS Lab