Come dividere efficacemente i lavori in gruppi per il multiprocessing quando le dimensioni del lavoro sono sconosciute

Question

Come dividere efficacemente i lavori in gruppi per il multiprocessing quando le dimensioni del lavoro sono sconosciute

#1 da (2 voti)

1

Con i core del processore K, come dividere in modo ottimale N lavori in gruppi, con ogni gruppo da elaborare sequenzialmente da un core del processore, quando il tempo di elaborare ogni lavoro è sconosciuto in anticipo e c'è un sovraccarico associato all'elaborazione di ciascun gruppo di posti di lavoro?

È possibile uccidere un gruppo di lavori prima che venga completato, ma in seguito non verrà estratto alcun utile progresso di elaborazione da quel gruppo di lavori.

Se faccio solo la dimensione di ciascun gruppo 1, li aggiungo a una coda e li elaboro in una sola volta, quindi il sovraccarico può dominare il tempo totale. Se li divido in gruppi di dimensioni uguali a K, il sovraccarico può ancora dominare il tempo totale e potrei essere sfortunato e avere tutti i lavori più lenti in un gruppo che rallenta ulteriormente le cose.

Questo è un esempio di un problema generale ben studiato con un algoritmo capito da elaborare in modo ottimale?

Ad esempio, supponiamo di avere 326400 lavori, 32 core e circa 5 secondi di overhead associati all'elaborazione di un gruppo.

3.200 lavori grandi richiedono 2 minuti ciascuno per l'elaborazione se eseguiti in quattro gruppi separati
3.200 lavori medi richiedono 1 minuto ciascuno da elaborare se eseguiti in quattro gruppi separati
i restanti 320.000 piccoli lavori occupano circa 5.001 secondi ciascuno per l'elaborazione se eseguiti in 320.000 gruppi separati.
per i 5.001 secondi per i piccoli lavori, 1 millisecondo è dovuto all'elaborazione e 5 secondi sono dovuti al sovraccarico di elaborazione di qualsiasi gruppo. se tutti i piccoli lavori sono eseguiti in un gruppo, ci vogliono 325 secondi per elaborare il totale a causa della condivisione del sovraccarico (320.000 * 1 millisecondo + 5 secondi = 325 secondi)

Se ho appena creato ciascuna dimensione di gruppo 1, ho messo i gruppi in una coda e ho eseguito 32 alla volta contemporaneamente su 32 core, e mi è capitato di scegliere prima i 3.200 lavori più importanti dalla coda, poi i 3.200 lavori medi dalla in coda, ci vorrebbero 200 minuti per finire i grandi lavori, 100 minuti per i lavori medi da finire e 833,5 minuti per i piccoli lavori da completare: 18 ore in totale.

In modo ottimale elaborerei prima i lavori più grandi (1 lavoro per gruppo), poi i lavori medi (1 lavoro per gruppo), quindi suddividerei i rimanenti piccoli lavori in 32 gruppi per un totale di circa 5 ore totali da finire.

Spero che ci sia un algoritmo ben studiato che non conosco che gestisca bene questa situazione.

multithreading scheduling multiprocessing

posta JDiMatteo 29.09.2014 - 23:50

fonte

1 risposta

Leggi altre domande sui tag multithreading scheduling multiprocessing

Crea una collezione con "punti medi" di N elementi da un pool con elementi di vari punti Esiste un modo più semplice per testare extras_require

score 2 · Accepted Answer

Sì, questo è un problema ben studiato. La programmazione del lavoro è stata per gran parte un obiettivo importante della ricerca attiva nella comunità informatica ad alte prestazioni per decenni.

Parte della risposta a questo problema dipenderà da come vengono distribuiti i lavori. Se possiamo supporre che un dato lavoro sia breve, medio o lungo è una variabile casuale indipendente (ad esempio la sua probabilità di essere di un tipo o di un altro è casuale e non dipende dal tipo di lavoro precedente), quindi uno dei i modi migliori per risolvere questo problema sarebbero probabilmente semplicemente eseguire una coda su ciascun core. Assegnare gruppi di posti di lavoro che, in media, saranno sufficientemente lunghi da dominare il tempo di attesa di 5 secondi, ma non così a lungo da poter funzionare per ore. Una volta che la coda è vuota, assegnagli un altro gruppo di lavori. Ciò si traduce in un effetto di bilanciamento del carico, poiché i core che completano il loro lavoro prima possono andare avanti e ottenere più lavoro.

Nel tuo esempio, le probabilità per un particolare lavoro sono le seguenti:
320,000 / 326,400 = .98 of 1 ms
3,200 / 326,400 = 0.01 of 60,000 ms
3,200 / 326,400 = 0.01 of 120,000 ms

Fornisce una durata prevista per un dato lavoro di (0.98 * 1) + (0.01 * 60,000) + (0.01 * 120,000) = 601 ms

Quindi, se, ad esempio, si desidera ridurre l'overhead 5s al 5% del tempo previsto per un dato gruppo di lavoro, sono necessari gruppi di lavoro di dimensioni (19 * 5000) / 601 = 158 jobs per gruppo. Quando un nucleo ha terminato quei lavori, basta dargli ancora molti altri dal resto del gruppo di posti di lavoro. Questo ti darebbe un runtime di gruppo di lavoro previsto di 158 * 601 ms + 5000 ms = 100,000 ms

Dove potresti incorrere in problemi con il metodo precedente è se l'assunzione precedentemente menzionata della lunghezza del lavoro è equamente distribuita non è valida. Se, ad esempio, tutti i tuoi lavori di grandi dimensioni avessero una probabilità significativa di essere adiacenti l'uno all'altro, potresti finire per assegnare gruppi di lavoro la cui durata varia notevolmente rispetto al valore atteso. Se questo è un potenziale problema nel tuo caso, potresti attenuarlo un po 'usando effettivamente qualcosa come un algoritmo round-robin per creare un gruppo di lavori. Ad esempio, invece di prendere un gruppo di lavori adiacenti dal pool di lavori rimanenti quando si crea un gruppo di lavoro per un core, si potrebbe prendere ogni 32 ° lavoro, in modo che i cluster di grandi lavori insieme sarebbero probabilmente suddivisi tra il diversi core.