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

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

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

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

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

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

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

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

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

Ответы

Ответ 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 справляется с моим маленьким примером намного лучше.