Как отсортировать зависимые объекты по зависимости для максимального параллелизма - PullRequest
Новая
       43

Как отсортировать зависимые объекты по зависимости для максимального параллелизма

0 голосов
/ 21 июля 2011

У меня есть список зависимостей (или лучше DAG без циклов):

Ввод (например): 

Item A depends on nothing
Item B depends on C, E
Item C depends on A
Item D depends on E
Item E depends on A

Что я ищуfor is: «Каков наилучший * параллельный порядок элементов?»

* наилучшее означает: максимальный уровень параллелизма

Результат (например): 

[A], [E, C], [D, B]

Наилучшим подходом, похоже, является Псевдокод для получения заказа на основе зависимости , но я думаю, что мне не хватает базового алгоритма для этого.

Ответы [ 3 ]

1 голос
/ 21 июля 2011

Это очень похоже на https://en.wikipedia.org/wiki/Program_Evaluation_and_Review_Technique и https://en.wikipedia.org/wiki/Critical_path_method

Предполагая, что вы хотите, чтобы максимальный уровень параллелизма позволил выполнить задачу как можно скорее, после того как вы упорядочите вещи так, что это займет не более критического пути, у вас есть что-то, что делает, а также наилучшее возможное решение - и если нет ограничения на количество параллельных задач, которые вы можете запустить, вы можете получить критический путь, просто запланировав каждое действие, как только все его зависимости завершены.

1 голос
/ 21 июля 2011

Я не уверен, что вы действительно хотите получить тот ответ, который, по вашему мнению, хотите.Например, в вашем сценарии вы можете выполнить элемент D перед элементом C, если D и E были быстрее, чем C, поэтому полученные списки не обязательно будут рассказывать всю историю.

Еслина самом деле вам нужно реализовать такой рабочий процесс, в отличие от простого прогнозирования рабочего процесса, его легко сделать оптимальным;всякий раз, когда задача завершается, просто просканируйте все оставшиеся задачи и запустите параллельно любую из них, чьи зависимости удовлетворены.Если вы хотите рассчитать это заранее, то, возможно, вы хотите пересмотреть структуру вашего результата?

0 голосов
/ 21 июля 2011 
  GetLists(tasks[1..m], depends[1..m])
   1. topological_sort(tasks)
   2. cumulative = set()
   3. lists = queue()
   4. i = 0
   5. while |cumulative| != m do
   6.    temp = set()
   7.    while depends[i] is a subset of cumulative do
   8.       temp = temp union {tasks[i]}
   9.       i = i + 1
  10.    cumulative = cumulative union temp
  11.    lists.enqueue(temp)

Нечто подобное может сработать. Обратите внимание, что lynchpin выполняет «топологическую сортировку», чтобы обеспечить получение завершения. Также обратите внимание, что, как есть, этот алгоритм корректен только для набора входов с допустимым решением. Если решения не существует, это циклы навсегда. Легко исправить, но вы можете справиться с этим.

Пример: A ни от чего не зависит, B и C зависят от A, E зависит от A и C, а D зависит от C и B. 

  Topological sort: A, B, C, D, E.
  cumulative = {}
  lists = []
  i = 0
  |cumulative| = 0 < 5 so...
     temp = {}
     depends[A] = {} is a subset of {} so
        temp = {A}
        i = 1
     depends[B] = {A} is not a subset of {}, so break
     cumulative = {A}
     lists = [{A}]
  |cumulative| = 1 < 5 so...
     temp = {}
     depends[B] = {A} is a subset of {A}, so
        temp = {B}
        i = 2
     depends[C] = {A} is a subset of {A}, so
  ...

Вы поняли.

...