OpenMP Dynamic vs Guided Scheduling

Я изучаю планирование OpenMP и, в частности, разные типы. Я понимаю общее поведение каждого типа, но уточнение было бы полезно в том, когда выбирать между dynamic и guided планированием.

Intel docs описывает dynamic scheduling:

Используйте внутреннюю рабочую очередь, чтобы получить блок цикла с размером блока итераций к каждому потоку. Когда поток завершен, он извлекает следующий блок итераций цикла из верхней части рабочей очереди. От по умолчанию размер блока равен 1. Будьте осторожны при использовании этого планирования типа из-за дополнительных накладных расходов.

В нем также описывается планирование guided:

Подобно динамическому планированию, но размер блока начинается с больших и уменьшается, чтобы лучше справляться с дисбалансом нагрузки между итерациями. Необязательный параметр chunk указывает их минимальный размер для использования. От по умолчанию размер блока приблизительно равен loop_count/number_of_threads.

Поскольку guided планирование динамически уменьшает размер куска во время выполнения, почему я когда-либо использовал планирование dynamic?

Я исследовал этот вопрос и нашел эту таблицу из Дартмута:

guided указан как имеющий служебные данные high, тогда как dynamic имеет средние служебные данные.

Это изначально имело смысл, но при дальнейшем исследовании я читал статью Intel по этой теме. Из предыдущей таблицы я предположил, что планирование guided займет больше времени из-за анализа и корректировки размера блока во время выполнения (даже при правильном использовании). Однако в статье Intel говорится:

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

Почему размер блока зависит от guided, занимающего больше, чем dynamic? Было бы разумно, если бы отсутствовала "гибкость", чтобы вызвать потерю производительности за счет слишком большого блокирования размера куска. Однако я бы не назвал это "накладными расходами", и проблема блокировки могла бы дискредитировать предыдущую теорию.

Наконец, в статье говорится:

Динамические графики дают максимальную гибкость, но производительность при неправильном расписании.

Для планирования dynamic имеет смысл быть более оптимальным, чем static, но почему он более оптимален, чем guided? Это просто накладные расходы, которые я допрашиваю?

Эта некоторая взаимосвязанная запись SO объясняет NUMA, относящуюся к типам планирования. Это не имеет отношения к этому вопросу, поскольку требуемая организация теряется в результате поведения этих типов планирования "первым пришел, первым обслужен".

dynamic планирование может быть коалесцентивным, что приводит к повышению производительности, но тогда такая же гипотеза должна применяться к guided.

Здесь приведены сроки каждого типа планирования для разных размеров блоков из статьи Intel для справки. Это только записи из одной программы и некоторые правила применяются по-разному для каждой программы и машины (особенно при планировании), но она должна обеспечивать общие тенденции.

EDIT (ядро моего вопроса):

Что влияет на время выполнения guided планирования? Конкретные примеры? Почему в некоторых случаях это медленнее, чем dynamic?
Когда я одобряю guided над dynamic или наоборот?
Как только это объясняется, поддерживайте ли источники выше ваши объяснения? Они вообще противоречат?

Ответ 1

Что влияет на время выполнения управляемого планирования?

Можно рассмотреть три эффекта:

1. Баланс нагрузки

Весь смысл динамического/управляемого планирования заключается в улучшении распределения работы в случае, когда не каждая итерация цикла содержит одинаковый объем работы. Фундаментально:

schedule(dynamic, 1) обеспечивает оптимальную балансировку нагрузки
dynamic, k всегда будет иметь ту же или лучшую балансировку нагрузки, чем guided, k

Стандарт указывает, что размер каждого фрагмента пропорциональный к числу неназначенных итераций, деленному на количество потоков в команде, уменьшаясь до k.

GCC OpenMP implmntation берет это буквально, игнорируя пропорциональный. Например, для 4 потоков, k=1, это будет 32 итерации как 8, 6, 5, 4, 3, 2, 1, 1, 1, 1. Теперь IMHO это действительно глупо: это приводит к дисбалансу плохой нагрузки, если первые 1/n итерации содержат более 1/n работы.

Конкретные примеры? Почему в некоторых случаях он медленнее, чем динамический?

Хорошо, давайте рассмотрим тривиальный пример, где внутренняя работа уменьшается с помощью итерации цикла:

#include <omp.h>

void work(long ww) {
    volatile long sum = 0;
    for (long w = 0; w < ww; w++) sum += w;
}

int main() {
    const long max = 32, factor = 10000000l;
    #pragma omp parallel for schedule(guided, 1)
    for (int i = 0; i < max; i++) {
         work((max - i) * factor);
    }
}

Исполнение выглядит так: ¹:

Как вы можете видеть, guided здесь действительно плохо. guided будет намного лучше для разных видов распределений работ. Также можно осуществлять руководство по-разному. Реализация в clang (который IIRC происходит от Intel), намного сложнее. Я действительно не понимаю идею, лежащую в основе наивысшей реализации GCC. В моих глазах это эффективно нарушает цель динамического баланса нагрузки, если вы даете 1/n работу для первого потока.

2. Накладные

Теперь каждый динамический блок имеет некоторое влияние на производительность из-за доступа к общему состоянию. Накладные расходы guided будут немного выше на кусок, чем dynamic, так как требуется немного больше вычислений. Однако guided, k будет иметь менее общие динамические фрагменты, чем dynamic, k.

Накладные расходы также будут зависеть от реализации, например. использует ли он атомы или блокировки для защиты общего состояния.

3. Cache- и NUMA-эффекты

Скажем, напишите в вектор целых чисел в вашей итерации цикла. Если бы каждая вторая итерация выполнялась другим потоком, каждый второй элемент вектора записывался бы другим ядром. Это очень плохо, потому что, делая это, они конкурируют с линиями кеша, которые содержат соседние элементы (ложное разделение). Если у вас небольшие размеры блоков и/или размеры блоков, которые не очень хорошо выравниваются для кэшей, вы получаете плохую производительность на "краях" кусков. Вот почему вы обычно предпочитаете большие красивые размеры (2^n). guided может дать вам большие размеры блоков в среднем, но не 2^n (или k*m).

Этот ответ (о котором вы уже указали) подробно обсуждает недостаток динамического/управляемого планирования с точки зрения NUMA, но это также относится к локалям/кэшам.

Не угадайте, измерьте

Учитывая различные факторы и трудности для прогнозирования специфики, я могу только рекомендовать измерить ваше конкретное приложение в вашей конкретной системе в вашей конкретной конфигурации с вашим конкретным компилятором. К сожалению, нет идеальной переносимости производительности. Я лично утверждаю, что это особенно верно для guided.

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

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

С другой стороны, guided может быть хорошей предпосылкой, с разумным соотношением балансировки нагрузки/нагрузки, по крайней мере, для умной реализации. Будьте особенно осторожны с guided, если вы знаете, что более поздние итерационные времена короче.

Имейте в виду, что существует также schedule(auto), который дает полный контроль над компилятором/временем выполнения и schedule(runtime), что позволяет вам выбирать политику планирования во время выполнения.

Как только это объясняется, поддерживайте ли источники выше ваши объяснения? Они вообще противоречат?

Возьмите источники, включая этот anser, с солью. Ни опубликованная вами диаграмма, ни мое временное изображение не являются научно точными числами. Существует огромная разница в результатах, и нет ошибок, они, вероятно, просто будут повсюду с этими очень немногими точками данных. Также диаграмма объединяет множественные эффекты, о которых я упоминал, не раскрывая код Work.

[Из документов Intel]

По умолчанию размер блока приблизительно равен loop_count/number_of_threads.

Это противоречит моему наблюдению, что icc справляется с моим маленьким примером намного лучше.

^{1: Использование GCC 6.3.1, Score-P/Vampir для визуализации, две переменные рабочие функции для окраски.}