Algoritmo parallelo - Analisi
L'analisi di un algoritmo ci aiuta a determinare se l'algoritmo è utile o meno. Generalmente, un algoritmo viene analizzato in base al suo tempo di esecuzione(Time Complexity) e la quantità di spazio (Space Complexity) richiede.
Poiché disponiamo di sofisticati dispositivi di memoria a un costo ragionevole, lo spazio di archiviazione non è più un problema. Quindi, alla complessità dello spazio non viene data molta importanza.
Gli algoritmi paralleli sono progettati per migliorare la velocità di calcolo di un computer. Per analizzare un algoritmo parallelo, normalmente consideriamo i seguenti parametri:
- Complessità temporale (tempo di esecuzione),
- Numero totale di processori utilizzati e
- Costo totale.
Complessità temporale
Il motivo principale alla base dello sviluppo di algoritmi paralleli era ridurre il tempo di calcolo di un algoritmo. Pertanto, valutare il tempo di esecuzione di un algoritmo è estremamente importante per analizzarne l'efficienza.
Il tempo di esecuzione viene misurato sulla base del tempo impiegato dall'algoritmo per risolvere un problema. Il tempo di esecuzione totale viene calcolato dal momento in cui l'algoritmo inizia l'esecuzione al momento in cui si interrompe. Se tutti i processori non iniziano o terminano l'esecuzione nello stesso momento, il tempo di esecuzione totale dell'algoritmo è il momento in cui il primo processore ha iniziato la sua esecuzione fino al momento in cui l'ultimo processore interrompe la sua esecuzione.
La complessità temporale di un algoritmo può essere classificata in tre categorie:
Worst-case complexity - Quando la quantità di tempo richiesta da un algoritmo per un dato input è maximum.
Average-case complexity - Quando la quantità di tempo richiesta da un algoritmo per un dato input è average.
Best-case complexity - Quando la quantità di tempo richiesta da un algoritmo per un dato input è minimum.
Analisi asintotica
La complessità o l'efficienza di un algoritmo è il numero di passaggi eseguiti dall'algoritmo per ottenere l'output desiderato. L'analisi asintotica viene eseguita per calcolare la complessità di un algoritmo nella sua analisi teorica. Nell'analisi asintotica, viene utilizzata una grande lunghezza di input per calcolare la funzione di complessità dell'algoritmo.
Note - Asymptoticè una condizione in cui una linea tende a incontrare una curva, ma non si intersecano. Qui la linea e la curva sono asintotiche tra loro.
La notazione asintotica è il modo più semplice per descrivere il tempo di esecuzione più veloce e più lento possibile per un algoritmo utilizzando limiti alti e limiti bassi sulla velocità. Per questo, usiamo le seguenti notazioni:
- Notazione O grande
- Notazione Omega
- Notazione Theta
Notazione O grande
In matematica, la notazione Big O viene utilizzata per rappresentare le caratteristiche asintotiche delle funzioni. Rappresenta il comportamento di una funzione per input di grandi dimensioni in un metodo semplice e accurato. È un metodo per rappresentare il limite superiore del tempo di esecuzione di un algoritmo. Rappresenta il tempo più lungo che l'algoritmo potrebbe impiegare per completare la sua esecuzione. La funzione -
f (n) = O (g (n))
se e solo se esistono costanti positive c e n0 tale che f(n) ≤ c * g(n) per tutti n dove n ≥ n0.
Notazione Omega
La notazione Omega è un metodo per rappresentare il limite inferiore del tempo di esecuzione di un algoritmo. La funzione -
f (n) = Ω (g (n))
se e solo se esistono costanti positive c e n0 tale che f(n) ≥ c * g(n) per tutti n dove n ≥ n0.
Notazione Theta
La notazione theta è un metodo per rappresentare sia il limite inferiore che il limite superiore del tempo di esecuzione di un algoritmo. La funzione -
f (n) = θ (g (n))
se e solo se esistono costanti positive c1, c2, e n0 tale che c1 * g (n) ≤ f (n) ≤ c2 * g (n) per tutti n dove n ≥ n0.
Accelerazione di un algoritmo
Le prestazioni di un algoritmo parallelo sono determinate calcolandone speedup. L'accelerazione è definita come il rapporto tra il tempo di esecuzione nel caso peggiore dell'algoritmo sequenziale più veloce noto per un particolare problema e il tempo di esecuzione nel caso peggiore dell'algoritmo parallelo.
Numero di processori utilizzati
Il numero di processori utilizzati è un fattore importante per analizzare l'efficienza di un algoritmo parallelo. Viene calcolato il costo per l'acquisto, la manutenzione e il funzionamento dei computer. Maggiore è il numero di processori utilizzati da un algoritmo per risolvere un problema, più costoso diventa il risultato ottenuto.
Costo totale
Il costo totale di un algoritmo parallelo è il prodotto della complessità temporale e del numero di processori utilizzati in quel particolare algoritmo.
Costo totale = complessità temporale × numero di processori utilizzati
quindi, il efficiency di un algoritmo parallelo è -