Степень разбиения и параллельная производительность

Granularity and Parallel Performance [Eng., PDF 270KB]

Введение

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

Вводные данные

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

Гранулярность часто соотносится с тем, как работа сбалансирована между потоками. Хотя легче сбалансировать работу, состоящую из большого количества мелких задач, в таком случае может возникнуть слишком большой объем издержек на коммуникации, синхронизации и т.д. Следовательно, можно снизить издержки, уменьшая гранулярность, объединяя малые задачи в одну более крупную. Такие средства, как Intel® Parallel Amplifier, могут помочь определить правильный ее уровень в приложении.

Следующий пример показывает, как можно улучшить производительность параллельной программы, благодаря уменьшению издержек на обмен и правильному уровню грануляции. Пример, использованный в данной статье – это алгоритм нахождения простых чисел, в котором используется простой лобовой тест, при котором каждое потенциальное простое число делится на все возможные делители, пока не найдётся реальный делитель или не будет доказано, что число простое. Поскольку положительные нечетные числа вычисляются как (4k+1), либо (4k+3), для k ≥ 0, код также ведет счет простых чисел, соответствующих одной из этих форм. В примере рассчитываются все простые числа от 3 до 1 миллиона.

В первом варианте кода для параллелизации используется OpenMP:

#pragma omp parallel 
{ int j, limit, prime;
#pragma omp for schedule(dynamic, 1) 
  for(i = 3; i <= 1000000; i += 2) {
    limit = (int) sqrt((float)i) + 1;
    prime = 1; // assume number is prime
    j = 3;
    while (prime && (j <= limit)) {
      if (i%j == 0) prime = 0;
      j += 2;
    }

    if (prime) {
      #pragma omp critical
      {
      numPrimes++;
      if (i%4 == 1) numP41++;  // 4k+1 primes
      if (i%4 == 3) numP43++;  // 4k-1 primes
      }
    }
  }
}
Этот код имеет высокий уровень издержек на коммуникацию (в форме синхронизации), к тому же размер отдельных задач слишком мал для потоков. Внутри цикла имеется критический участок, который используется для организации безопасного инкрементирования переменной счетчика. Критический участок добавляет циклу издержки на синхронизацию и блокировку, что отражено в окне Intel Parallel Amplifier на рис. 1.


Рис. 1. Анализ блокировок и ожиданий, который говорит, что критический регион OpenMP является причиной повышенных издержек на синхронизацию.

Увеличение количества переменных-счетчиков, опираясь на значения больших массивов данных, является часто применяемым методом, который называют редукцией. Издержки на блокировку и синхронизацию можно устранить, удалив критический регион и добавив оператор OpenMP reduction:

#pragma omp parallel 
{
  int j, limit, prime;
  #pragma omp for schedule(dynamic, 1) 
    reduction(+:numPrimes,numP41,numP43) 
  for(i = 3; i &;lt;= 1000000; i += 2) {
    limit = (int) sqrt((float)i) + 1;
    prime = 1;  // assume number is prime
    j = 3;
    while (prime && (j &;lt;= limit))
    {
      if (i%j == 0) prime = 0;
      j += 2;
    }

    if (prime)
    {
      numPrimes++;
      if (i%4 == 1) numP41++;  // 4k+1 primes
      if (i%4 == 3) numP43++;  // 4k-1 primes
    }
  }
}
В зависимости от того, сколько итераций выполняется в цикле, удаление критического участка из тела цикла может на порядок повысить скорость выполнения. Однако приведенный выше код все же имеет некоторые параллельные издержки. Они вызваны тем, что размер работы в каждой задаче слишком мал. Оператор schedule (dynamic, 1) означает, что планировщик динамически распределяет одну итерацию (кусок работы) за раз каждому потоку. Каждый рабочий процесс обрабатывает одну итерацию, затем синхронизируется с планировщиком и берёт следующую итерацию. Увеличив размер куска, мы увеличиваем размер работы в каждой задаче, которая назначается потокам, тем самым уменьшая количество обращений потока для синхронизации к планировщику.

Хотя такой метод может улучшить производительность, нужно иметь в виду (как было сказано выше), что слишком низкий уровень гранулярности может вызвать дисбаланс нагрузки. Например, попробуем увеличить размер задачи до 10000, как в приведенном ниже коде:

#pragma omp parallel
{
  int j, limit, prime;
  #pragma omp for schedule(dynamic, 100000) 
    reduction(+:numPrimes, numP41, numP43)
  for(i = 3; i <= 1000000; i += 2)
  {
    limit = (int) sqrt((float)i) + 1;
    prime = 1; // assume number is prime
    j = 3;
    while (prime && (j <= limit))
    {
      if (i%j == 0) prime = 0;
      j += 2;
    }

    if (prime)
    {
      numPrimes++;
      if (i%4 == 1) numP41++;  // 4k+1 primes
      if (i%4 == 3) numP43++;  // 4k-1 primes
    }
  }
}
Анализ работы данного кода с помощью Parallel Amplifier выявил дисбаланс в количестве вычислений, выполняемых четырьмя потоками, как показано на рис. 2. Основной причиной здесь является то, что в каждом куске работы имеется разное количество вычислений, а в наличии слишком малое количество кусков, назначаемых в качестве задач (десять кусков на четыре потока), что вызывает дисбаланс нагрузки. При увеличении количества потенциальных простых чисел (из цикла for), для тестирования всех возможных множителей (в цикле while) требуется большее количество итераций. Таким образом, общий объем работы в каждом куске требует большего количества итераций цикла while, чем в предыдущем случае.


Рис. 2. Результаты анализа параллельности, показывающие дисбаланс времени выполнения в разных потоках.

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

#pragma omp parallel
{
  int j, limit, prime;
  #pragma for schedule(static, 100) 
    reduction(+:numPrimes, numP41, numP43)
  for(i = 3; i <= 1000000; i += 2)
  {
    limit = (int) sqrt((float)i) + 1;
    prime = 1;  // assume number is prime
    j = 3;
    while (prime && (j <= limit))
    {
      if (i%j == 0) prime = 0;
      j += 2;
    }

    if (prime)
    {
      numPrimes++;
      if (i%4 == 1) numP41++;  // 4k+1 primes
      if (i%4 == 3) numP43++;  // 4k-1 primes
    }
  }
}

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

Параллельная производительность многопоточного кода зависит от гранулярности: как работа разделяется между потоками и как между ними происходит коммуникация. Ниже приведены рекомендации по улучшению производительности с помощью правильной настройки грануляции:

  • Надо знать свою программу
    • Понимать, какое количество работы делается в разных частях параллельного приложения.
    • Понимать требования приложения к коммуникации. Синхронизация является одним из видов коммуникации, но нужно также учитывать и издержки на пересылку сообщений и разделение данных через иерархию памяти (кэш, основную память и т.д.).
  • Нужно знать платформу и потоковую модель
    • Знать цену запуска параллельного выполнения и синхронизации в выбранной потоковой модели на выбранной платформе.
    • Убедиться, что объём работы на одну параллельную задачу существенно больше, чем издержки на многопоточность.
    • Использовать как можно меньше синхронизации, использовать самые малозатратные способы синхронизации.
    • Использовать partitioner в параллельных алгоритмах Intel® Threading Building Blocks, чтобы планировщик задач мог выбрать правильную гранулярность и баланс нагрузки между потоками.
  • Знать свои инструменты
    • В анализе “Locks and Waits” в Intel Parallel Amplifier нужно искать длительные блокировки, синхронизации и издержки на параллельность, как знак чрезмерной коммуникации.
    • В анализе“Concurrency” в Intel Parallel Amplifier нужно искать дисбаланс нагрузки, как признак слишком крупной гранулярности или что необходимо более качественное распределение задач по потокам.

Руководство по применению

Хотя приведенные выше примеры часто ссылаются на OpenMP, все советы и принципы применимы и к другим потоковым моделям, таким как Windows threads и POSIX* threads. Все потоковые модели имеют издержки, связанные с различными функциями, такими как запуск параллельного выполнения, блокировки, критические регионы, передача сообщений и т.д. Приведенные здесь рекомендации по уменьшению объема коммуникации и увеличению размера работы на поток без роста дисбаланса нагрузки применимы ко всем потоковым моделям. Однако разные уровни издержек в разных потоковых моделях диктуют разный выбор уровня гранулярности.

Для получения подробной информации о возможностях оптимизации компилятора обратитесь к нашему Уведомлению об оптимизации.