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


13

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?


1
Jednym ze sposobów rozwiązania tego problemu jest modelowanie węzłów na wykresie jako aktorów i pozwolenie, aby niektóre biblioteki aktorów zajęły się porządkowaniem.
svick

Odpowiedzi:


16

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 v(u,v)uv

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 )SiG=(V,E)

S0={vVuV.(u,v)E}Si+1={vVuV.(u,v)Euk=0iSk}

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:S0

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.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.