Algoritmo di parallelizzazione di un processo.

[Hiskrtapps]

Sono alle prese con la gestione della paralizzazione di alcuni processi.

Diciamo che ho un processo parallelizzabile; questo processo è gestito da un Executor che delega a più Workers parti di questo processo.

Il requisito è che questo algoritmo sia adattativo, cioè, il numero di Workers non è deciso preventivamente ma si seleziona man mano che il processo viene eseguito analizzando il throughput totale e altri dati a disposizione.

In pratica ecco i punti fondamentali:
- L'Executor parte, istanzia un Worker e gli assegna una parte di lavoro.
- Ogni volta che un Worker ha eseguito il suo lavoro richiede all'Executor nuovo lavoro; l'Executor glielo da finchè c'è Lavoro.
- Ogni tot tempo l'Executor si sveglia, controlla i dati dei suoi Workers e decide se aggiungere o rimuovere Workers o tenere invariato il loro numero, per massimizzare il loro throughput.
(Questo è necessario perchè il carico dell'ambiente su cui gira il processo è molto variabile).

I dati disposizione dell'Executor sono:
- la lunghezza del lasso di tempo dall'ultima volta che ha controllato
- unità di lavoro svolta da ogni Worker in quel lasso di tempo; la somma di tutte le unità di lavoro di tutti gli Worker in quel lasso di tempo è il throughput di quel lasso di tempo
- numero di Worker che hanno lavorato in quel lasso di tempo
- Uno storico delle informazioni relative a lassi di tempo precedenti a questo

L'idea di base per fare eseguire questa valutazione è la seguente:
- se il throughput attuale è maggiore di x% rispetto a quello precedente aggiungi un Worker
- se il throughput attuale è inferiore di x% rispetto a quello precedente rimuovi un Worker
- altrimenti mantieni il numero di Worker attuale

Per quanto sembri vincente questo algoritmo non si comporta in maniera ottimale e sebbene il funzionamento si avvicini a quello voluto il risultato è ancora poco soddisfacente.
I problemi principali che posso indicare sono questi:
- se ho un Worker che funziona al massimo (diciamo throughput costante da molto tempo) come fa il mio Executor a sapere che con un Worker in più andrebbe più veloce? (es. perchè abbiamo un altro processore a disposizione);
- se ho un Worker che funziona al massimo (diciamo throughput costante da molto tempo) come fa il mio Executor a sapere che con un Worker in meno andrebbe più veloce?

La mia domanda è: esistono algoritmi già esistenti e documentati da poter implementare senza che mi inventi l'acqua calda?
Spero di aver spiegato il mio problema che mi sembra un buon argomento di discussione.

Grazie!

[starfred]

ciao, il tuo problema non è molto differente da un problema di throughput di una rete.
Quindi un consiglio potrebbe esser quello di andare a vedere tutti gli algoritmi di controllo di congestione ed i loro vari funzionamenti.
Tuttavia nel tuo caso potrei suggerirti differenti miglioramenti:
Il primo è il modo in cui aggiungi il nuovo Worker, ti basi sugli eventi passati. Così facendo hai bisogno di una storia, quindi hai bisogno di "tempo" per creare la storia che per l'appunto è dato dall'Executor che ogni tanto si sveglia, controlla e memorizza il throughput. Questo algoritmo è vincente ma è lento.
Invece di creare la storia potresti calcolarti il throughput massimo su quella macchina con un numero fisso di worker e basarti sempre su quello. Se per esempio tu sai che su quella macchina il TP max è 100 con 10 worker tu parti subito con quelle condizioni oppure potresti provare con l'incremento esponenziale dei worker, per esempio parto da 1 worker, misuro il TP (es. 5), allora metto altri 2 worker in più, rimisuro il TP che è 30 e rimetto allora 6 worker in più... per quest'ultimo aspetto guarda il meccanismo di controllo della congestione del TCP-reno.

http://upload.wikimedia.org/wikipedia/it/9/90/TCP-RENO.png

Un altro consiglio è levare il controllo dell'Executor che si risveglia ogni tot di tempo, crei overhead inutile. Demanda il compito di svegliare l'Executor ai vari Worker. Per esempio quando il Worker finisce e chiede un nuovo lavoro all'Executor, potresti sfruttare quest'evento per il calcolo del throughput.

Spero di esserti stato utile, ciao :)

[Hiskrtapps]

Ciao,

grazie della risposta.

E' vero quel che dici che il problema è simile al throughput su rete e mi sembra un buon consiglio quello che l'executor sia svegliato dai worker stessi.

Per quanto riguarda l'idea di cercare il numero ottimale di workers ed usare sempre questo, non si può fare.
E' proprio questo il problema, nel senso che il numero ottimale di workers calcolato in un dato momento potrebbe non andare bene in un altro (immagina un processo che dura ore e che gira su un sistema complesso in condizioni variabili)
E' come se l'executor dovesse fare questa ricerca del numero ottimale di thread continuamente (diciamo ogni tot intervallo di tempo)

Ho provato a buttar giù un'idea proprio basandomi su questo concetto, cioè lasciando perdere calcoli di percentuali. Cioè:

L'executor compie una azione possibile tra INCREASE (incrementare numero di workers) e DECREASE (diminuirla).
Per esempio incrementa. Il giro dopo si chiede se il throughput è migliorato. Se si persegue con questa azione, se no compie l'azione inversa, e così via.

Mi sembra che i risultati così siano un po' meglio, è come se in ogni momento ricercasse il numero ottimale di workers.