Il furto del lavoro è sempre l'algoritmo di schedatura del thread di livello utente più appropriato?

Question

Ho studiato diversi algoritmi di pianificazione per un pool di thread che sto implementando. A causa della natura del problema che sto risolvendo, posso supporre che le attività eseguite parallelamente siano indipendenti e non generino nuove attività. Le attività possono essere di dimensioni diverse.

Sono andato immediatamente per l'algoritmo di programmazione più popolare "rubare il lavoro" utilizzando deques lock-free per le code di lavoro locali, e sono relativamente soddisfatto di questo approccio. Tuttavia mi chiedo se ci siano casi in cui il furto del lavoro non è l'approccio migliore.

Per questo particolare problema che hanno una buona stima della dimensione di ogni singola attività. Il furto del lavoro non fa uso di queste informazioni e mi chiedo se ci sia uno schedulatore che fornirà un migliore bilanciamento del carico rispetto al furto del lavoro con queste informazioni (ovviamente con la stessa efficienza).

NB. Questa domanda si lega con un precedente question.

Answer 1

Distribuirò le attività in anticipo. Con le informazioni sulla loro durata di esecuzione stimata è possibile distribuirle in singole code, per ciascuna di esse.

La distribuzione dei compiti è fondamentalmente la knapsack problem, ciascuna coda dovrebbe prendere la stessa quantità di tempo.

si dovrebbe aggiungere una logica di modificare le code mentre corrono. Ad esempio, una ridistribuzione dovrebbe verificarsi dopo che il tempo di esecuzione stimato differisce di una certa quantità dal tempo reale di esecuzione.

Answer 2

È vero che lo scheduler di work-stealing non usa quell'informazione, ma è perché non dipende da esso per fornire i limiti teorici che fa (ad esempio, la memoria che utilizza, la comunicazione totale prevista tra i lavoratori e anche il tempo previsto per eseguire un calcolo completamente rigida come potete leggere qui: http://supertech.csail.mit.edu/papers/steal.pdf)

un interessante articolo (che spero è possibile accedere: http://dl.acm.org/citation.cfm?id=2442538) in realtà utilizza tempi di esecuzione limitati a fornire prove formali (che cercano di essere il più vicino possibile ai confini del furto del lavoro originale).

E sì, ci sono casi in cui il lavoro-furto non eseguire in modo ottimale (per esempio, le ricerche degli alberi sbilanciati e altri casi particolari). Ma per quei casi, sono state fatte ottimizzazioni (ad esempio permettendo il furto di metà del deque della vittima, invece di prendere solo un compito: http://dl.acm.org/citation.cfm?id=571876).