Представьте, что у меня есть ориентированный ациклический граф (DAG) с вершинами и ребрами.
Вершина может быть одного из следующих двух типов:
- Вычислительная задача (T)
- Ресурс (R)
Ребро представляет зависимость.Он ВСЕГДА происходит из некоторой вершины вычислительной задачи T и заканчивается в некоторой вершине ресурса R.
Ограничения на структуру графа:
- Вершины задачи зависят только от ресурсавершины (не для других задач).Это означает, что есть ТОЛЬКО исходящие ребра из вычислительных задач, и есть ТОЛЬКО входящие ребра в ресурсы.
- Вершина задачи не может иметь более одного ребра к одной и той же вершине ресурса.
- Вершины ресурса donне зависит от чего-либо (без исходящих ребер).
- Каждая вершина вычислительной задачи может иметь минимум 3 исходящих ребра и максимум 4 исходящих ребра.Это означает, что вычислительная задача зависит от минимум 3 ресурсов и максимум 4.
Семантика:
- Приведенный выше график представляет собойграф зависимости от задачи.Всякий раз, когда выполняется задача Tx, она блокирует ВСЕ ресурсы, от которых зависит, до тех пор, пока она не завершится.
- Каждый ресурс не может использоваться более чем одной задачей в любой момент времени.Таким образом, задачи могут на короткое время препятствовать выполнению других задач, пока они не будут выполнены.
Вопрос:
Учитывая приведенный выше график, какой алгоритм я могу использовать для вычислениявсе возможные задачи, которые я могу выполнять параллельно, чтобы они не блокировали друг друга?т.е. в любой момент времени я хочу быть в состоянии достичь максимального распараллеливания.Я буду использовать алгоритм для обнаружения всех задач, которые не блокируют друг друга, и запускаю их.Всякий раз, когда задача завершается, я хочу переоценить график, чтобы посмотреть, смогу ли я выделить дополнительные задачи, которые были разблокированы.
Я хочу знать алгоритм, который я мог бы использовать для такого рода вычислений.Это звучит как проблема с жестким графиком, но я подозреваю, что проблема такого рода не совсем новая ....
Пример:
В приведенном примере яможет сначала запустить T1 и T3.Когда это будет сделано, я могу запустить T2 и T4.
