Д. Пункт графика

Параллельный регион имеет по крайней мере один барьер, в конце и может иметь дополнительные барьеры внутри него. На каждом барьере остальные члены команды должны ждать последнего потока. Чтобы свести к минимуму это время ожидания, необходимо распределить общую работу таким образом, чтобы все потоки достигли барьера примерно в то же время. Если часть этой общей работы содержится в for конструкциях, для этой цели можно использовать schedule опцию.

При наличии повторяющихся ссылок на одни и те же объекты выбор расписания для for конструкции может определяться главным образом характеристиками системы памяти, например наличием и размером кэшей, а также временами доступа к памяти, которые могут быть одинаковыми или неодинаковыми. Такие соображения могут сделать предпочтительным, чтобы каждый поток постоянно ссылался на один и тот же набор элементов массива в ряде циклов, даже если некоторым потокам назначается относительно меньше работы в отдельных циклах. Эту настройку static можно выполнить с помощью расписания с одинаковыми границами для всех циклов. В следующем примере нулевое значение используется в качестве нижней границы во втором цикле, хотя k было бы более естественным, если расписание не было бы важным.

#pragma omp parallel
{
#pragma omp for schedule(static)
  for(i=0; i<n; i++)
    a[i] = work1(i);
#pragma omp for schedule(static)
  for(i=0; i<n; i++)
    if(i>=k) a[i] += work2(i);
}

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

Расписание static также подходит для простейшей ситуации, параллельной области, содержащей одну for конструкцию, с каждой итерацией, требующей одинакового объема работы.

#pragma omp parallel for schedule(static)
for(i=0; i<n; i++) {
  invariant_amount_of_work(i);
}

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

Для команды потоков p пусть округление вверх(n/p) будет целым числом q, которое удовлетворяет условию n = p*q - r при 0 <= r < p. Одна реализация static расписания для этого примера будет назначать итерации q первым потокам p-1 и итерации q-r последнему потоку. Другая допустимая реализация присваивает итерации q первым потокам p-r и итерации q-1 остальным потокам r . В этом примере показано, почему программа не должна полагаться на детали конкретной реализации.

Расписание dynamic подходит для случая for конструкции с итерациями, требующими различных или даже непредсказуемых объемов работы.

#pragma omp parallel for schedule(dynamic)
  for(i=0; i<n; i++) {
    unpredictable_amount_of_work(i);
}

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

Расписание dynamic может быть полезно, если потоки получают различные вычислительные ресурсы, что имеет тот же эффект, что и различные объемы работы для каждой итерации. Аналогичным образом динамический график также может быть полезным, если потоки приходят в for конструкцию в разное время, хотя в некоторых из этих случаев guided расписание может быть предпочтительнее.

Расписание guided подходит для случая, когда потоки могут поступать в различные периоды в for конструкции с каждой итерацией, требующей примерно одного объема работы. Эта ситуация может произойти, если, например, конструкция for предшествует одному или нескольким разделам или for конструкциям с nowait предложениями.

#pragma omp parallel
{
  #pragma omp sections nowait
  {
    // ...
  }
  #pragma omp for schedule(guided)
  for(i=0; i<n; i++) {
    invariant_amount_of_work(i);
  }
}

Как dynamic, расписание guided гарантирует, что ни один поток не ожидает на барьере дольше, чем требуется другому потоку для выполнения своей последней итерации, или последних k итераций, если указан размер блока k. Среди таких расписаний, расписание guided характеризуется тем, что требует наименьшего количества синхронизаций. Для размера блока k типичная реализация будет назначать q = ceiling(n/p) итераций первому доступному потоку, устанавливать n равным большему из n-q и p*k и повторять, пока все итерации не будут назначены.

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

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

Если все потоки начинаются одновременно, static расписание приведет к выполнению конструкции в 125 единиц без синхронизации. Но предположим, что один поток опаздывает на 100 единиц. Затем оставшиеся семь потоков ожидают в барьере в течение 100 единиц времени, а время выполнения всей структуры увеличивается до 225.

dynamic Так как и план, и расписание guided обеспечивают отсутствие ожидания более чем на одну единицу на барьере, задержка потока приводит к увеличению времени выполнения конструкции только до 138 единиц, возможно, за счёт задержек при синхронизации. Если такие задержки не незначительны, следует обратить внимание на то, что число синхронизаций составляет 1000 для dynamic, но только 41 для guided, если условный размер порции равен одному. С размером блока 25, dynamic и guided оба завершают выполнение за 150 единиц, а также возможные задержки из-за необходимой синхронизации, которые теперь составляют всего 40 и 20 соответственно.