Является ли динамическое планирование openMp таким же, как планирование LPT, когда задачи отсортированы по времени обработки?

Question

Я запутался в динамическом планировании и LPT-планировании (я думаю, что оно статическое).

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

Итак, если я сортирую задачи по времени обработки, а затем применю динамическое планирование с размером фрагмента 1, то будет ли оно таким же, какПланирование LPT или нет?

Например, предположим, что существует цикл с 15 итерациями.В каждой итерации вычисляется декартово произведение векторов.Но в каждой итерации размеры векторов различны, что означает, что нагрузка не сбалансирована.Если я вычислил итоговый размер каждой итерации и отсортировал их по убыванию, а затем по графику (динамический, 1), это то же самое, что LPT в теории?

Answer 1

Во-первых, пункты расписания OpenMP применяются к циклам, а не к задачам, поэтому говорить о задачах в этом контексте довольно сложно, поскольку у OpenMP также есть задачи (и даже taskloop).Во избежание путаницы я назову объект, запланированный в цикле, «порцией», так как это непрерывная порция итераций.

Если вы хотите обсудить предложение schedule для циклов, то

1. Существует фундаментальное различие между алгоритмом планирования, таким как LPT, который предполагает предварительное знание времени выполнения чанка и любого другого.из алгоритмов, разрешенных OpenMP, которые не требуют таких знаний.
2. Начиная с OpenMP 4.5 теперь есть модификатор расписания (monotonic или nonmonotonic), который можно применять к расписанию dynamic (как и к другим), и это влияет на последовательности, которые расписаниеможет генерировать.
3. В OpenMP 5.0, по умолчанию, без декорации, schedule(dynamic) эквивалентен schedule(nonmonotonic:dynamic), который допускает последовательности, которые были бы невозможны с schedule(monotonic:dynamic), и, вероятно, нарушали бы ваше отображение (хотя выконечно, можно использовать schedule(monotonic:dynamic)!)
4. Поскольку все поведение планирования OpenMP описано в терминах состояния выполнения машины, вполне возможно, что будет создана последовательность, отличная от той, которую вы используете.можно было бы ожидать, поскольку состояние машины представляет собой основную правду, отражая такие проблемы, как помехи от нагрузки на другую машину, тогда как схема планирования, такая как LPT, основана на предполагаемом предварительном знании времени выполнения, которое может не отражаться в реальности.

Вы можете увидеть обсуждение schedule(nonmonotonic:dynamic) на https://www.openmp.org/wp-content/uploads/SC18-BoothTalks-Cownie.pdf