Как уменьшить количество задач путем объединения задач?

Question

У меня есть большой набор объектов задачи. Большинство задач имеют задачи родителей - которые необходимо выполнить раньше. Большинство задач имеют задачи для детей - которые могут быть выполнены только после. Дело в том, что такой набор объектов задач, созданных после его создания, часто выполняется и должен использовать все доступные ЦП, выполняя задачи параллельно. Проблема, с которой я сталкиваюсь, заключается в том, что объем работы, связанной с объектом задачи, чаще всего не слишком мал - код планирования работает только с самим собой - реальная работа, которая должна быть выполнена, не отображается в результатах профилирования (Гринь). Объект задачи действительно обеспечивает функцию стоимости! Я думал о создании другого набора объектов задачи, с каждым новым объектом задачи, содержащим коллекцию старых объектов задачи. Родители и дети, на которые ссылаются эти новые объекты задачи, также должны быть новыми объектами задачи. Это уменьшило бы связь, требуемую уменьшением параллелизма.

Очевидно, есть лучше и хуже способы объединения старых задач на новые задачи ...

Может кто-нибудь придумать алгоритм делает это? Я изобретаю колесо?

Answer 1

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

Если у вас есть мера стоимости выполнения задачи T2, и она меньше затрат на планирование, тогда вы можете рассмотреть ее оптимизацию.

Вы можете легко сделать это, если у него есть только один предшественник T1 (просто вставьте его код в конец предшественника T1 и свяжите предшественника T1 с преемниками T2) или только один преемник T3 (просто вставьте его код в начало преемника T3 и связать предшественники T2 с T3).

Предположим, у вас есть

 (;| 1 (<< 2 4) a 
      2 b 
      3 (<< 4) c 
      4 d) 

(частичный порядок программы PARLANSE с задачами 1 2 3 4, состоящих из работы ABCD, соответственно, с задачей 1 происходит прежде, чем задачи 2 и 4, а также задачи 3 перед 4. смешной оператор «;» мотивирован частичными порядками, смешивающими последовательные «;» и параллельные «|» вычисления. Смешной оператор (< < нм) означает «работает раньше времени, чем n и m». Обратите внимание, что задачи 1 и 3 могут параллельны, так что могут 2 и 3, а также 2 и 4. [Это наименьший частичный порядок, который можно выразить не чисто параллельным].

если б слишком мал, вы можете оптимизировать это:

 (;| 1 (<< 4) (;; a b) 
      3 (<< 4) c 
      4 d) 

где а и Ь выполняются последовательно.

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

Представьте, что задача 4 слишком мала.Поскольку ABCD действует линеаризация частичного порядка, можно объединить задачи с и d:

 (;| 1 (<< 2 3) a 
      2 b 
      3 (;; c d)) 

Взятые до крайности, этот процесс будет сериализовать все расчеты, если их стоимость инструмента мала, и это именно то, что вы хотите в этом случае.