come applicare la programmazione in parallelismo nei problemi grafici?

Question

Descrizione del problema:

c'è n tasks, e in questi compiti, one might be dependent on the others, che significa che se A è dipendente da B, allora B deve essere completato prima di A viene terminato.

1. trovare un modo per completare queste attività il più rapidamente possibile?

2.if take parallelism into account, come progettare il programma per completare queste attività?

Domanda:

A quanto pare, la risposta alla prima domanda è, topologico-sort questi compiti, poi finire in questo ordine.

Ma come si fa il lavoro se si tiene conto del parallelismo?

La mia risposta è stata, prima topologico-sort questi compiti, poi scegliere i compiti che sono indipendenti e arrivare primo, poi scegliere e finire quelle indipendenti nel resto ...

ho ragione?

Answer 1

Gli algoritmi di ordinamento topologico possono fornire vari ordini di risultato diversi, quindi non è sufficiente prendere i primi elementi e assumere che siano indipendenti.

Invece dell'ordinamento topologico suggerisco di ordinare le attività in base al numero di margini di dipendenza in entrata. Quindi, per esempio se il tuo grafico ha A -> B, A -> C, B -> C, D -> C lo ordinerai come A [0], D [0], B [1] , C [3] dove [i] è il numero di bordi in entrata.

Con l'ordinamento topologico, è possibile anche eseguire il gotting A, B, D, C. In tal caso, non sarebbe facile scoprire che è possibile eseguire A e D in parallelo.

Si noti che dopo che un'attività è stata completamente elaborata, è necessario aggiornare le attività rimanenti, in particolare quelle che erano dipendenti dall'attività completata. Tuttavia, se il numero di dipendenze in un task è limitato a un numero relativamente piccolo (ad esempio qualche centinaia), è possibile fare affidamento su qualcosa come radix/bucket-sort e mantenere la struttura di ordinamento aggiornata in tempo costante.

Con questo approccio, è anche possibile avviare facilmente nuove attività, una volta terminata una singola attività parallela. Basta aggiornare i conteggi delle dipendenze e avviare tutte le attività che ora hanno 0 dipendenze in entrata.

Si noti che questo approccio presuppone che si disponga di una potenza di elaborazione sufficiente per elaborare tutte le attività che non hanno dipendenze nello stesso momento. Se disponi di risorse limitate e ti preoccupi di una soluzione ottimale in termini di tempo di elaborazione, dovresti investire più sforzi, poiché il problema diventa NP-difficile (come già accennato).

Quindi, per rispondere alla tua domanda iniziale: Sì, hai praticamente ragione, tuttavia, ti mancava spiegare come determinare quelle attività indipendenti in modo efficiente (vedi il mio esempio sopra).

Answer 2

Vorrei provare a ordinarli in una struttura forestale diretta con il tempo di esecuzione dell'attività come limiti di bordo. Ordina le arborescenze dal più pesante al più leggero e inizia con il più pesante. Utilizzando questo approccio è possibile, allo stesso tempo, verificare le dipendenze circolari.

Utilizzando il parallelismo, si ottiene il problema del contenitore, che è NP-rigido. Prova a cercare soluzioni approssimative per questo problema.

Answer 3

Dai un'occhiata allo Critical Path Method, preso dallo stato di project management. Fondamentalmente fa ciò di cui hai bisogno: dati compiti con dipendenze e durate, produce quanto tempo ci vorrà e quando attivare ogni attività.

(*) Si noti che questa tecnica presuppone un numero infinito di risorse per la soluzione ottimale. Per risorse limitate ci sono euristiche per algoritmi ingordi come: GPRW [corrente + tempo di attività successive] o MSLK [tempo minimo total slack].

(*) Inoltre, è necessario conoscere [o almeno stimare] la durata di ciascuna operazione.