Модификация циклов для повышения производительности параллельной обработки данных

Loop Modifications to Enhance Data-Parallel Performance [Eng., PDF 226KB]

Введение

Обычно в приложениях с параллельной обработкой данных основной объем вычислений приходится на циклы, поэтому оптимизация циклов оказывает непосредственное влияние на общую производительность приложения. В случае вложенных циклов, производительность находится в прямой зависимости от степени разбиения (granularity) вычислений по потокам. Такие преобразования, как разложение и объединение вложенных циклов могут существенно упростить распараллеливание и повысить его эффективность.

Описание проблемы

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

Рассмотрим пример оптимизации цикла с помощью директивы OpenMP* for, используемой для распределения работы, как показано в приведенном ниже примере. В данном случае малое число итераций приводит к неравномерности нагрузки (load imbalance), если итерации цикла распределяются между четырьмя потоками. Если одна итерация занимает всего несколько миллисекунд, такая неравномерность не приведет к серьезным последствиям. Однако, если каждая итерация будет занимать около часа, то три потока будут простаивать в течение 60 минут, ожидая завершения четвертого. Сравните это с ситуацией, когда аналогичный цикл включает 1003 итерации продолжительностью по часу, которые выполняются на четырех потоках. В данном случае простаивание в течение часа после десяти дней выполнения не имеет существенного значения.

#pragma omp for
for (i = 0; i < 13; i++)
{...}


Рекомендации

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

void processQuadArray (int imx, int jmx, int kmx,
  double**** w, double**** ws)
{
  for (int nv = 0; nv < 5; nv++)
    for (int k = 0; k < kmx; k++)
      for (int j = 0; j < jmx; j++)
        for (int i = 0; i < imx; i++)
          ws[nv][k][j][i] = Process(w[nv][k][j][i]);
}
Если количество потоков не равно пяти, то распараллеливание внешнего цикла приведет к неравномерности нагрузки и простою потоков. Потеря производительности может оказаться еще серьезнее, если размерности массивов imx, jmx и kmx будут очень большими. В этом случае предпочтительным вариантом станет распараллеливание одного из внутренних циклов. От использования неявных барьеров в конце конструкции распределения работы следует отказаться, если это не представляет сложности. Все директивы OpenMP для распределения работы (for, sections, single) имеют неявный барьер в конце структурируемого блока. В этой точке все потоки должны встретиться для синхронизации, прежде чем исполнение кода продолжится. В ряде случаев такие барьеры не нужны и могут отрицательно сказываться на производительности. Можно использовать параметр OpenMP nowait, чтобы запретить барьеры, как в приведенном ниже примере:

void processQuadArray (int imx, int jmx, int kmx,
  double**** w, double**** ws)
{
  #pragma omp parallel shared(w, ws)
  {
    int nv, k, j, i;
    for (nv = 0; nv < 5; nv++)
      for (k = 0; k < kmx; k++) // kmx is usually small
        #pragma omp for shared(nv, k) nowait
          for (j = 0; j < jmx; j++)
            for (i = 0; i < imx; i++)
              ws[nv][k][j][i] = Process(w[nv][k][j][i]);
  }
}
Поскольку вычисления в самом внутреннем цикле независимы друг от друга, нет никаких причин для того, чтобы потоки ожидали синхронизации у неявного барьера, прежде чем переходить к следующей итерации k. Если количество работы в разных итерациях разная, параметр nowait позволит потокам продолжать выполнение полезной работы, не задерживаясь в точке неявного барьера.

Если в цикле имеется циклически порожденная зависимость (loop-carried dependence), которая мешает выполнению цикла в параллельном режиме, можно разбить тело цикла на отдельные меньшие циклы, которые будут выполняться параллельно. Такое разбиение цикла на два и более называется «разложением цикла». В приведенном ниже примере мы используем разложение имеющего зависимость цикла, чтобы создать несколько циклов, которые могут выполняться параллельно:

float *a, *b;
int i;
for (i = 1; i < N; i++) {
  if (b[i] > 0.0) 
    a[i] = 2.0 * b[i];
  else 
    a[i] = 2.0 * fabs(b[i]);
  b[i] = a[i-1];
}
Присваивание значений элементам массива a выполняется независимо, не учитывая знак соответствующих элементов массива b. Каждое присваивание элементу массива b не зависит от других, но при этом зависит от того, завершено ли присваивание требуемому элементу массива a. При использовании такого варианта кода рассмотренный выше цикл не может быть распараллелен.

Разбив цикл на две независимые операции, мы можем выполнять эти операции в параллельном режиме. Например, можно применить к каждому из них алгоритм parallel_for algorithm из библиотеки Intel® Threading Building Blocks (Intel® TBB), как показано ниже:
float *a, *b;

parallel_for (1, N, 1, 
  [&](int i) {
    if (b[i] > 0.0) 
      a[i] = 2.0 * b[i];
    else 
      a[i] = 2.0 * fabs(b[i]);
    });
parallel_for (1, N, 1, 
  [&](int i) {
    b[i] = a[i-1];
  });
Возвращение первого вызова parallel_for перед выполнением второго гарантирует, что все обновления в массиве a будут завершены до того, как начнутся обновления в массиве b.

Разложение цикла также может использоваться для локализации данных (data locality). Рассмотрим следующий пример кода, работающего по принципу решета:

for (i = 0; i < list_len; i++)
  for (j = prime[i]; j < N; j += prime[i])
    marked[j] = 1;
Внешний цикл выбирает начальный индекс элемента и шаг внутреннего цикла из массива prime. Затем внутренний цикл проходит по всей длине массива marked, помещая в выбранные элементы значение «1». Если массив marked достаточно большой, выполнение внутреннего цикла может привести к вытеснению из кэш-линий просчитываемых в первую очередь элементов массива marked, которые потребуются для последующей итерации внешнего цикла. Результатом этого станет низкая частота успешных обращений к кэшу как в последовательной, так и в параллельной версии цикла.

Если прибегнуть к разложению цикла, итерации внутреннего цикла могут быть разбиты на блоки (chunks), которые будут лучше помещаться в кэш и повторно использовать строки кэша, после того как те были заполнены. Для того чтобы применить разложение в этом случае, добавим другой цикл, которой будет контролировать диапазон, охватываемый самым внутренним циклом:

for (k = 0; k < N; k += CHUNK_SIZE)
  for (i = 0; i < list_len; i++) {
    start = f(prime[i], k);
    end = g(prime[i], k);
    for (j = start; j < end; j += prime[i])
      marked[j] = 1;
  }
На каждую итерацию самого внешнего цикла в приводимом выше примере будет выполняться полный набор итераций i-цикла. Исходя из выбранного элемента массива prime, находим начальный и конечный индексы в блоке массива marked (контролируемого внешним циклом). Эти вычисления заключены внутрь подпрограмм f() и g(). Таким образом, тот же блок в массиве marked будет обработан до того, как произойдет переход к следующему. Учитывая, что обработка каждого блока выполняется независимо от других, итерации внешнего цикла могут быть переведены в параллельный режим.

Еще одним способом оптимизации, который помогает эффективно распараллеливать итерации, является объединение вложенных циклов для увеличения числа итераций. В качестве примера рассмотрим приведенный слева фрагмент кода с двумя вложенными циклами, число итераций которых составляет 23 и 1000 соответственно. Поскольку 23 представляет собой простое число, итерации внешнего цикла невозможно эффективно разделить; кроме того, объема работы в 1000 итераций может оказаться недостаточно для того, чтобы существенно сократить затраты на распараллеливание только внутреннего цикла. С другой стороны, можно выполнить слияние этих циклов в один цикл с 23 000 итерациями (см. пример справа), что позволит смягчить трудности, возникающие при распараллеливании начального варианта кода.

#define N 23
#define M 1000
. . .
for (k = 0; k < N; k++)
  for (j = 0; j < M; j++)
    wn[k][j] = Work(w[k][j], k, j);
#define N 23
#define M 1000
. . .
for (kj = 0; kj < N*M; kj++) {
  k = kj / M;
  j = kj % M;
  wn [k][j] = Work(w[k][j], k, j);
}
В то же время, если каждая из переменных итерации используется внутри тела цикла (например, для индексации массивов), новый счетчик циклов должен быть переведен назад к соответствующим значениям параметров, что влечет дополнительные затраты, которые в исходном алгоритме отсутствовали.

Чтобы повысить степень разбиения и для эффективной локализации данных, при этом сокращая непроизводительные затраты на распараллеливание, можно использовать объединение циклов с аналогичными индексами. Два первых цикла из приводимого слева примера без труда поддаются объединению:

  for (j = 0; j < N; j++)
    a[j] = b[j] + c[j];

  for (j = 0; j < N; j++)
    d[j] = e[j] + f[j];

  for (j = 5; j < N - 5; j++)
    g[j] = d[j+1] + a[j+1];
  for (j = 0; j < N; j++)
  {
    a[j] = b[j] + c[j];
    d[j] = e[j] + f[j];
  }

  for (j = 5; j < N - 5; j++)
    g[j] = d[j+1] + a[j+1];
Объединение этих циклов увеличивает объем работы на итерацию (т.е. степень разбиения) и сокращает связанные с циклом затраты. Осуществить слияние третьего цикла уже не так просто, поскольку он имеет другое число итераций. Что еще важнее, между третьим циклом и двумя предыдущими циклами существует зависимость по данным.

Используйте параметр OpenMP if, чтобы выбрать последовательный или параллельный режим в зависимости от информации времени выполнения (runtime information). В некоторых случаях число итераций цикла не может быть установлено до времени выполнения. Если выполнение параллельной области OpenMP в нескольких потоках оказывает отрицательное влияние на производительность (например, малое число итераций), для достижения стабильной производительности следует задать минимальный порог (threshold), как в приведенном ниже примере:

#pragma omp parallel for if(N >= threshold)
  for (i = 0; i < N; i++) { ... }
В данном примере цикл выполняется в параллельном режиме только в том случае, если число итераций превышает установленный программистом минимальный порог.

Учитывая, что аналогичный механизм в Intel TBB отсутствует, для того, чтобы определить, какой режим выполнения кода использовать(последовательный или параллельный), можно ввести явную проверку условия. С другой стороны, можно вызвать параллельный алгоритм и предоставить планировщику задач Intel TBB возможность использования одного потока для малых значений N. Следует отметить, что последний вариант сопряжен с некоторыми непроизводительными затратами.

Пожалуйста, обратитесь к странице Уведомление об оптимизации для более подробной информации относительно производительности и оптимизации в программных продуктах компании Intel.
Возможность комментирования русскоязычного контента была отключена. Узнать подробнее.