Topologiczne algorytmy sortowania mogą dawać różne rozkazy wyników, więc nie można po prostu wziąć kilku pierwszych elementów i założyć, że są niezależne.
Zamiast topologicznego sortowania sugerowałbym sortowanie zadań według liczby przychodzących krawędzi zależności. Na przykład, jeśli twój wykres ma A -> B, A -> C, B -> C, D -> C, sortujesz go jako A [0], D [0], B [1] , C [3] gdzie [i] to liczba przychodzących krawędzi.
Przy sortowaniu topologicznym można również uzyskać A, B, D, C. W takim przypadku nie byłoby łatwo dowiedzieć się, że możesz wykonywać A i D równolegle.
Pamiętaj, że po całkowitym przetworzeniu zadania musisz zaktualizować pozostałe zadania, w szczególności te, które były zależne od ukończonego zadania. Jeśli jednak liczba zależności wchodzących w zadanie jest ograniczona do stosunkowo niewielkiej liczby (powiedzmy kilkaset), można łatwo polegać na czymś takim jak radix/bucket-sort i utrzymywać strukturę sortowania w stałym czasie.
Dzięki takiemu podejściu można łatwo rozpocząć nowe zadania po zakończeniu pojedynczego zadania równoległego. Po prostu zaktualizuj liczbę zależności i uruchom wszystkie zadania, które mają teraz 0 zależności przychodzących.
Należy zauważyć, że to podejście zakłada, że masz wystarczającą moc obliczeniową do przetworzenia wszystkich zadań, które nie mają zależności w tym samym czasie. Jeśli masz ograniczone zasoby i dbasz o optymalne rozwiązanie pod względem czasu przetwarzania, będziesz musiał zainwestować więcej wysiłku, ponieważ problem staje się NP-trudny (jak już wspomniano).
Tak więc, aby odpowiedzieć na twoje oryginalne pytanie: Tak, masz rację, jednak brakowało ci wyjaśnienia, jak efektywnie określić te niezależne zadania (zobacz mój przykład powyżej).
Co powiecie na rekursywne uruchamianie każdej zależności równolegle przed wykonaniem zadania zależnego? Będziesz potrzebował pewnej księgowości, aby upewnić się, że każde zadanie jest wykonywane tylko raz, ale poza tym wydaje się proste i wydajne. –