[Algoritmi] Tempi thread paralleli

[gio.86]

Buongiorno,
è la prima volta che scrivo su questo forum, nonostante lo segua da diverso tempo.
Ho iniziato da un anno un corso di laurea in informatica e devo sicuramente ringraziare anche matematicamente per aver superato i primi esami di matematica.

La breve introduzione diciamo che c'entra poco con il problema che vado a sottoporvi.
Si tratta di determinare i tempi di esecuzione di una serie di thread in parallelo.

Sto incontrando questa necessità professionalmente, ma purtroppo non riesco a trovare (o probabilmente non cerco nel modo giusto) dei contenuti didattici adeguati per risolverlo.

Il problema è il seguente.
Supponiamo di avere tre funzioni F1, F2, F3.
Ognuna di queste, nell'ordine specificato, accetta in ingresso l'output della funzione precedente.

Per cui sono costretto ad eseguire sequenzialmente, come segue. Dato x, input originale, avremo:
y = F1(x);
z = F2(y);
risultato_finale = F3(z);

Supponiamo ora che le funzioni abbiano durata costante, come seque;
F1 -> 100ms
F2 -> 200ms
F3 -> 300ms

Sappiamo che processare l'elemento x sarà banalmente la somma dei tempi, quindi 600ms.

Quindi, con n = 1 (dove n è il numero di input da processare), avremo un tempo di 600ms.
Ora, con n = 100, se tutti gli elementi fossero processati sequenzialmente attendendo il termine delle tre funzioni prima di procedere all'elemento successivo, otterrò un tempo totale di esecuzione di (600 * 100)ms.

Detto questo, pensiamo invece ora che le tre funzioni possano essere parallelizzate, quindi, F1 processerà i 100 elementi in maniera indipendente. Man mano che preparerà i risultati F2 sarà liberà di iniziare a processare la sua parte e così a sua volta F3 non appena i risultati di F2 saranno pronti.
In questo caso faccio già fatica a stimare un tempo di esecuzione totale, però empiricamente dovrei aver trovato che il tempo totale è uguale a = [T.max(tra F1,F2,F3) * n] + "tempi residui inferiori al massimo". Nel nostro esempio => [300 * 100] + 200 + 100 = 30300ms => ~30sec

Già qui vorrei chiedere se intanto è comprensibile quanto scritto e quanto ho dedotto in merito ai tempi calcolati.

Passiamo oltre.
A questo punto, supponendo di aver calcolato i primi tempi correttamente. Cosa succederebbe se decidessi di parallelizzare N volte la funzione 1, N volte la funzione 2 e così anche per la funzione 3?
Come esprimo questo con una funzione matematica al fine di poter capire quanti processi parallelizzare e poter rimanere in un determinato tempo massimo?

Ringrazio in anticipo per l'attenzione e chiunque vorrà aiutarmi.
Giovanni

[apatriarca]

Quella che vuoi implementare è chiamata pipeline ed è uno dei modelli di parallelismo più comuni. E' per esempio usata a livello di hardware per l'esecuzione delle istruzione nel processore e nelle schede video per processare i poligoni in 3D. Il tempo di esecuzione è determinato dallo stadio più lento della pipeline (nel tuo caso F3) ed è circa uguale a N volte tale valore come hai già calcolato autonomamente.

Non mi è del tutto chiaro che cosa intendi nell'ultimo passaggio. Vuoi insomma eseguire le tue funzioni su blocchi di \(M\) valori in parallelo invece che su uno solo? In tale caso il tempo sarà probabilmente diviso per \(M\) (assumendo tutto venga eseguito in parallelo e che non ci sia alcun overhead). Ma in pratica è difficile raggiungere queste tempistiche teoriche.

Una formula potrebbe comunque essere \( \max(T(F1), T(F2), T(F3)) \, (N + 2) / M = t. \) Ma non hai un numero infinito di processori e quindi il parallelismo possibile è limitato. In pratica ti conviene misurare e fare tentativi.

Un'alternativa è anche quella di suddividere le funzioni ulteriormente in modo che ogni funzione possa essere eseguita in un tempo inferiore. Se riuscissi per esempio ad avere ogni stage della pipeline impiegare al più 100 ms riusciresti a ridurre il tempo totale di un terzo.

[gio.86]

Ciao,
grazie mille per la risposta. Mi hai dato tutta una serie di interessanti spunti di riflessione.

Si esatto l'idea che cercavo di spiegare nell'ultimo passaggio era proprio quella da te descritta. ossia poter parallelizzare le tre funzioni.

Cercando di rappresentare la cosa graficamente, dovrebbe essere una cosa del genere:

* esecuzione in parallelo delle funzioni (in caso di 5 elementi da processare e 5 thread paralleli)
1 ---> F1 ---> F2 ---> F3
2 ---> F1 ---> F2 ---> F3
3 ---> F1 ---> F2 ---> F3
4 ---> F1 ---> F2 ---> F3
5 ---> F1 ---> F2 ---> F3

* esecuzione in parallelo delle funzioni (in caso di 5 elementi da processare e 3 thread paralleli)
1 ---> F1 ---> F2 ---> F3
2 ---> F1 ---> F2 ---> F3
3 ---> F1 ---> F2 ---> F3
4 ------------> F1 ---> F2 ---> F3
5 ------------> F1 ---> F2 ---> F3

Nell'ultimo caso supponiamo appunto che gli elementi { 1,2,3 } partiranno al tempo t0.
{ 4, 5 } partiranno in ritardo dovendo attendere che un thread di F1 si liberi.

[apatriarca]

Per comodità si assume di solito c'è il numero di elementi è divisibile per il numero di processi paralleli. In pratica puoi arrotondare il tuo numero al successivo multiplo del numero di pipeline parallele per semplificare i calcoli.
Nota comunque che per le pipeline stai aumentando il tempo necessario perché un singolo elemento passi attraverso l'intera pipeline ma incrementi il numero di elementi processati in un determinato tempo. Questo significa che la pipeline deve essere il più possibile piena.

Puoi anche usare il parallelismo dei dati diversamente. Hai che il primo stadio della pipeline può generare valori molto più velocemente degli altri per cui puoi parallelizzare questi stadi diversamente. Per esempio 2 per F2 e 3 per F3.

EDIT: L'ho scritto un po' di fretta stamattina ma quello che intendevo è qualcosa come seque:

Codice:

F1 -+- F2 -+- F3
    |      |
    +- F2 -+- F3
           |
           +- F3


Se hai quindi 5 elementi hai i seguenti tempi:

Codice:

        a    b    c    d    e
-----------------------------
   0   F1    -    -    -    -
 100  F2a   F1    -    -    -
 200  F2a  F2b   F1    -    -
 300  F3a  F2b  F2a   F1    -
 400  F3a  F3b  F2a  F2b   F1
 500  F3a  F3b  F3c  F2b  F2a
 600    -  F3b  F3c  F3a  F2a
 700    -    -  F3c  F3a  F3b
 800    -    -    -  F3a  F3b
 900    -    -    -    -  F3b
1000    -    -    -    -    -


In 1s hai finito di processare tutti gli elementi usando 6 processi paralleli. Usando 3 pipeline in parallelo hai invece:

Codice:

        a    b    c    d    e
-----------------------------
   0  F1a  F1b  F1c    -    -
 300  F2a  F2b  F2c  F1a  F1b
 600  F3a  F3b  F3c  F2a  F2b
 900    -    -    -  F3a  F3b
1200    -    -    -    -    -


In questo caso ci voglio 1.2s e 9 processi paralleli, molti dei quali saranno in attesa per la maggior parte del tempo.

[gio.86]

Esempio chiarissimo. Grazie per lo schema.

A questo punto però non mi tornano i conti. Dicevamo, possiamo stimare circa il tempo di elaborazione dei nostri elementi in questo modo: max(T(F1),T(F2),T(F3))(N+2)/M=t (con N numero di elementi ed M numero di processi paralleli)

Nel tuo esempio avrei un diviso 6, nel mio un diviso 9. Sulla carta parrebbe più performante aggiungere processi, mentre nel tuo esempio si dimostra appunto l'esatto contrario, con più processi abbiamo le pipeline spesso inutilizzate/in attesa e quindi tempi elaborazione totali più elevati.

Allora mi chiedo, abbiamo un modo per stimare quanti processi parallelizzare per evitare di lasciare elementi ad aspettare o code in attesa a far nulla?
E' sufficiente creare un numero di processi proporzionale ai tempi di esecuzione? (nel nostro caso T(F2) = 2 * T(F1))

Provo a porre il quesito da un altro punto di vista. Mantenendo i tempi supposti prima (supponendo anche che questi non degradino a causa del parallelismo), se volessi processare 100.000 elementi in un'ora, come calcolo quanti processi devo parallelizzare?

A naso direi:
max(T(F1),T(F2),T(F3))(N+2)/M <= t
300ms (100000 + 2) / M <= 3600000ms
M >= 300ms (100000 + 2) / 3600000ms
M >= 8.33

Almeno 8 o 9 processi paralleli, probabilmente da bilanciare tra le varie funzioni.
Può avere senso quanto dedotto?

[apatriarca]

Ti conviene analizzare le performance separando le varie strategie di parallelismo. In una pipeline hai che lo stadio più lento determina le performance di tutta la pipeline. Se \(T\) è la durata dello stadio più lento (e quindi di tutti gli stadi della pipeline) e \(S\) è il numero di stadi hai che le performance saranno più o meno \((n + S) \times T\). Se invece ottieni parallelismo separando i dati ed eseguendo la stessa operazione in parallelo su di essi hai che il tempo sarà uguale a \( n \times T / M \) dove questa volta \(T\) è la durata di ogni singolo thread ed \(M\) è il numero di thread.

Nell'esempio che ti ho fatto ho usato più thread negli stadi più lenti in modo da ridurre il tempo impiegato in media in ogni stadio e quindi riducendo il valore \(T\) della formula della pipeline. Siccome i dati rimangono in T2 e T3 comunque rispettivamente 2 e 3 "stadi" hai che \(S\) viene incrementato di \(3\). Avresti potuto ottenere lo stesso risultato separando gli stadi T2 e T3 rispettivamente in 2 e 3 parti, ognuna di 100ms. Ma è in generale abbastanza difficile arrivare a formule chiuse che valgano poi nella realtà perché ci sono molte più variabili di quelle che stai considerando in pratica..