Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
vuoi
o PayPal
tutte le volte che vuoi
T2 calcCosì, per 4 processori...... e così via...
Quindi la formula precedente 26Capitolo 4 – Parametri di valutazione di un algoritmo - pt1diventa:
dove: (4.2)∗ ∗τ = T (N ) K µp pindica la complessità computazionale dell’algoritmo parallelo quando uso p pro-cessori.
È chiaro quindi che più processori uso, più ottengo un risparmio, IN QUE-STO PROBLEMA
In generale quindi quanto vale ?TpL’algoritmo che impiega meno tempo è quello che utilizza 8 processori.
27Capitolo 4 – Parametri di valutazione di un algoritmo - pt1Ma quanto differisce, cioè quanto è più veloce di quello sequenziale?/ è quindi il guadagno che otteniamo passando da un metodo sequenzialeT T1 pa parallelo.
Per calcolare il guadagno di un algoritmo parallelo, rapporto la complessitàcomputazionale di un algoritmo sequenziale con quella di un algoritmo parallelo.
SPEED-UPSi definisce il rapporto come
lo speed-up misura la riduzione del tempo di esecuzione rispetto all'algoritmo su 1 core. Non avremo mai il caso inverso, perché otterremmo un algoritmo superlineare, significa che siamo partiti da un algoritmo sequenziale sbagliato. Si definisce inoltre lo speed up ideale:
Capitolo 4 – Parametri di valutazione di un algoritmo - pt1 è tipico della somma di due vettori, cioè degli algoritmi full parallel
CALCOLO DELLA SOMMA DI N NUMERI
Purtroppo non tutti i problemi possono essere risolti con algoritmi completamente parallelizzabili.
EFFICIENZA DI UN ALGORITMO SEQUENZIALE
N-1 passi temporali per N-1 addizioni (si somma per coppia)
EFFICIENZA DI UN ALGORITMO PARALLELO
Nel caso in cui usassimo 2 core la prima e la seconda strategia coincidono:
Capitolo 4 – Parametri di valutazione di un algoritmo - pt1
1 core esegue le prime 7 addizioni → 1 core esegue le seconde 7 addizioni → insieme, in parallelo, quindi in 7 passi temporali.
eseguono 14 addizioni1 passo temporale (l'ottavo) per 1 addizione dei risultati parziali dei due core. Cioè è il tempo per la la reduction.collezione dei risultati,
È un passo sequenziale
Per 4 core:
1 core esegue le prime 3 addizioni→1 core esegue le seconde 3 addizioni→1 core esegue le terze 3 addizioni→1 core esegue le quarte 3 addizioni→↓insieme, in parallelo, quindi in 3 passi temporali, eseguono 12 addizioni
1 passo temporale (il quarto) per 2 addizioni dei risultati delle coppie di core
1 passo temporale (il quinto) per 2 addizioni dei risultati al passo precedente
Quindi di quanto si riduce il tempo di esecuzione su p processori rispetto al tempo di esecuzione su 1 processore? 30
Capitolo 4 – Parametri di valutazione di un algoritmo - pt1
per 1 core impiega 15 passi temporali per 16 addizioni per 2 core impiega 8 passi temporali per 16 addizioni
Capitolo 4 – Parametri di valutazione di un algoritmo - pt1
per 4 core impiega 5
passi temporali per 16 addizioni
In generale quanto vale ?TpN/p-1 è il tempo per il calcolo localeil logaritmo è la profondità dell'albero, per il calcolo delle collezioni.Diremo quindi che l'algoritmo che impiega meno tempo è quello che utilizza8 core
Ma quanto differisce, cioè quanto è più veloce di quello sequenziale?32
Capitolo 4 – Parametri di valutazione di un algoritmo - pt1
OVERHEAD
Abbiamo definito lo speed-up come e abbiamo detto che lo speed-up idealeT1T pè tale cheL'overhead misura quanto lo speed-up differisce da quello ideale.Cioè voglio che p - sia uguale a 0.T 1TpQuindi ritornando all'esempio della somma di N numeri:33
Capitolo 4 – Parametri di valutazione di un algoritmo - pt1
Quindi se si vuole calcolare la somma di 16 numeri nel minor tempo possibile, l'algoritmo su 8 processori è da preferire.Infatti aumentando il numero di processori si riduce il tempo
impiegato per eseguire le operazioni richieste. Ma confrontando lo speed-up ottenuto con lo speed-up ideale:
Capitolo 4 – Parametri di valutazione di un algoritmo - pt1
Cioè ho utilizzato 8 processori per avere un incremento dello speed-up ideale di quasi 4 volte. Lo speed-up quindi non basta a fornire informazioni sull’efficienza dell’algoritmo parallelo. Quindi: l’utilizzo di un maggior numero di processori/core NON è sempre una garanzia di sviluppo di algoritmi paralleli "efficaci", cioè di algoritmi che sfruttano tutte le risorse della macchina parallela. Come misurare allora se e quanto è stato sfruttato il calcolatore parallelo?
EFFICIENZA
Si definisce come il rapporto tra:
e misura quanto l’algoritmo sfrutta il parallelismo del calcolatore. Allo stesso modo dello Speed-up possiamo definire l’efficienza ideale:
Capitolo 5 Parametri di valutazione di un algoritmo - pt2
5.1 Lezione 6 - Legge di Ware-Amdhal
Abbiamo detto
parallelo che gira su 1 processore⇓quindi dà informazioni su quanto l’algoritmo si presta all’implementa-Spzione su un’architettura parallela.
Capitolo 5 – Parametri di valutazione di un algoritmo - pt2
Svantaggio:l’algoritmo parallelo su 1 processore potrebbe eseguire più operazioni del neces-sario
SECONDA SCELTAT1↓tempo di esecuzione del miglior algoritmo sequenziale⇓ dà informazioni sulla riduzione effettiva del tempo nella risoluzione diSpun problema con p processori
Difficoltà:• individuazione del miglior algoritmo sequenziale• disponibilità del software che implementi tale algoritmo.
CONVENZIONE: prima scelta
Dove è il tempo di esecuzione dell’algoritmo parallelo su 1 processoreTp ⇓e danno informazioni su quanto l’algoritmo si presta all’implementa-S Ep pzione su un’architettura parallela.
QUANDO È POSSIBILE OTTENERE SPEED-UP PROSSIMIALLO SPEED-UP
IDEALE?
- Negli algoritmi full parallel (somma di 2 vettori): SEMPRE!
- Negli algoritmi che necessitano una collezione dei risultati: possopensare di ottenere speed-up ideali all'infinito (aggiungendo processori all'infinito). Non è però sempre possibile.
5.1.1 Analisi asintotica dello speed-up
Ricordiamo che il punto di partenza per scrivere un buon algoritmo parallelo è aver scritto un ottimo algoritmo sequenziale.
Abbiamo visto, inoltre, che la complessità computazionale si può comporre in 2 parti:
- parte relativa alle operazioni che devono essere eseguite esclusivamente in sequenziale
- parte relativa alle operazioni che potrebbero essere eseguite contemporaneamente
Esempio per la somma di due vettori:
per la somma di n numeri:
in questo caso l'operazione sequenziale è il passo
reductionQuindi quando vado a parallelizzare la formulaottengocioè calcoliamo il tempo impiegato dall’algoritmo parallelo con p core• resta invariata perché resta sequenziale (è l’overhead)Ts• diventa perché le operazioni relative alla parte parallela sono oraT T /pc ceseguite concorrentemente dai p coreEsempio per la somma di due vettori abbiamo calcolato = 0 +(2+2) = 4T1Parallelizzato... 40Capitolo 5 – Parametri di valutazione di un algoritmo - pt2Così per la somma di n numeri = 1 + 2 = 3T1Parallelizzato... 41Capitolo 5 – Parametri di valutazione di un algoritmo - pt2In generale il tempo di esecuzione di un algoritmo parallelo, distri-buito su p processori comprende 2 argomenti:• : tempo per eseguire la parte serialeTs• tempo per eseguire la parte parallelaT /p:c5.1.2 Legge di Ware (Amdhal)Ricordiamo lo speed-up scritto in funzione dell’overheadPossiamo definire le due quantità trovate in
termini di notazioni in cui l'una è il complemento dell'altra (la loro intersezione è nulla)la legge di Ware è la caratterizzazione dello speed-up
Analizziamo asintoticamente questa formula:42Capitolo 5 – Parametri di valutazione di un algoritmo - pt2
In questo caso 1/α indica la parte che non siamo riusciti a paralleliz-zare.Mentre al tendere di p all'infinito, nel caso della somma di due vettori, ottenia-mo lo speed-up ideale, infatti abbiamo detto essere un algoritmo full parallel.(credo non so supposizione mia).Prestiamo attenzione alla somma di N numeri con n fissato e p variabile.
Se la dimensione n del problema è fissata, al crescere del numero p dicore, non solo non si riescono ad ottenere speed-up vicini a quello ideale, ma leprestazioni peggiorano!Non conviene usare un numero elevato di core, ma ne bastano 2, come os-servato dalla figura.Quindi proviamo
adesso a fissarep = 2 e aumentare n44
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
