Uzyskiwanie równoległych elementów w rozwiązywaniu zależności

Zaimplementowałem sortowanie topologiczne na podstawie artykułu z Wikipedii, którego używam do rozwiązywania zależności, ale zwraca ono listę liniową. Jakiego algorytmu mogę użyć do znalezienia niezależnych ścieżek?

Zakładam, że zbocze oznacza, że należy wykonać przed . Jeśli tak nie jest, odwróć wszystkie krawędzie. Ponadto zakładam, że jesteś mniej zainteresowany ścieżkami (te są już podane przez DAG) niż strategią dobrego wykonania, biorąc pod uwagę zależności.u $(u,v)$$u$$v$

Możesz łatwo dostosować procedurę sortowania topologicznego: zamiast dołączać, scal wszystkie elementy o tej samej „głębokości” w jeden zestaw. Otrzymasz listę zestawów, z których każdy zawiera elementy, które możesz wykonać / zainstalować równolegle. Formalnie zbiory są zdefiniowane w ten sposób dla wykresu : G = ( V , E $S_i$$G = (V,E)$

$\qquad \displaystyle \begin{align} S_0 &= \{ v \in V \mid \forall u \in V. (u,v) \notin E \} \\ S_{i+1} &= \{v \in V \mid \forall u \in V. (u,v) \in E \to u \in \bigcup_{k=0}^i S_k \} \end{align}$

Następnie możesz wykonać swoje zadania w ten sposób (załóżmy, że istnieje zestawów):$k$

for i=0 to k
  parallel foreach T in S_k
    execute T

Oczywiście nie zapewnia to maksymalnej przepustowości, jeśli zadania zajmują inny czas: dwa równoległe, niezależne łańcuchy liniowe synchronizują się po każdym elemencie. Aby to obejść, sugeruję, abyś pracował bezpośrednio na DAG z równoległym przechodzeniem zaczynającym się w węzłach źródłowych - tych w - i synchronizując / rozwidlając w węzłach z kilkoma krawędziami wejściowymi / wyjściowymi:$S_0$

parallel foreach T in S_0
  recursive_execute T

gdzie

recursive_execute T {
  atomic { if T.count++ < T.indeg then return }
  execute T
  parallel foreach T' in T.succ
    recursive_execute T'
}

i T.countjest prostym licznikiem zawierającym liczbę poprzedników, Tktóre zostały już wykonane, T.indegliczbę poprzedników i T.succzestaw następców.