Баланс нагрузки и производительность в параллельном режиме

Load Balance and Parallel Performance [Eng., PDF 199KB]

Введение

Решающее значение для производительности приложения имеет сбалансированное распределение нагрузки между потоками. Главная цель выравнивания нагрузки (load balancing) заключается в том, чтобы свести к минимуму время их простоя. При условии минимальных затрат на распределение задач, равномерное распределение нагрузки между всеми потоками позволяет сократить количество неиспользуемых циклов из-за простоя потоков, не загруженных вычислениями, и, в конечном итоге, увеличить производительность. В то же время, достижение идеального баланса нагрузки является нетривиальной задачей и зависит от многих факторов, в том числе от уровня параллелизма в приложении, характера нагрузки, количества потоков, политики выравнивания нагрузки и модели параллелизма.

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

Простаивающее во время вычислений ядро – это, по сути, потеря ресурсов, которая ведет к увеличению общего времени работы многопоточного приложения. Простаивание ядра без работы может быть вызвано самыми разными причинами, в том числе выборкой из памяти или операцией ввода-вывода. Хотя полностью избежать периодического простаивания ядер невозможно, в распоряжении программистов есть средства, позволяющие сократить данный эффект, например, перекрывающиеся операции ввода-вывода, упреждающая выборка из памяти и переупорядочивание структуры доступа к данным для лучшего использования кэша.

Аналогичным образом, при многопоточном режиме выполнения простаивающие потоки также означают потерю ресурсов. Выделение потокам неравноценных объемов работы приводит к состоянию, которое называется «разбалансировкой» (load imbalance). Чем сильнее разбалансировка, тем больше потоков находятся в простое и тем больше затраты времени на выполнение вычислений. При равномерном распределении вычислительных нагрузок между доступными потоками общее время выполнения сокращается.

В качестве примера представим себе набор из двенадцати отдельных задач со следующим временем выполнения: {10, 6, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1}. Предположим, что для обработки этих задач доступно четыре потока; таким образом, самым простым вариантом распределения задач будет выделить каждому потоку по три задачи, выбираемых по порядку. То есть, потоку 0 будет назначен объем работы, соответствующий 20 единицам времени (такты, time units) (10+6+4), потоку 1 для выполнения потребуется 8 единиц времени (4+2+2), потоку 2 потребуется 5 единиц времени (2+2+1), а поток 3 сможет выполнить три назначенные ему задачи всего за 3 единицы времени (1+1+1). На Рисунке 1(a) показано соответствующее распределение задач: при этом общее время выполнения для двенадцати задач составит 20 единиц времени (затраты времени считаются сверху вниз).


Рисунок 1. Варианты разделения задач между четырьмя потоками.

Гораздо большей эффективности можно добиться при распределении объемов работы следующим образом: поток 0 {10}, поток 1 {4, 2, 1, 1}, поток 2 {6, 1, 1}, и поток 3 {4, 2, 2, 2}, как показано на Рисунке 1(b). В этом варианте выполнение программы занимает всего 10 единиц времени, и только два потока из четырех простаивают в течение 2 единиц времени каждый.

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

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

Итеративная логическая структура разделения задач в OpenMP* по умолчанию сводится к статическому распределению итераций между потоками (или же такой метод планирования может быть задан вручную). Если рабочая нагрузка в циклах различается, а ее структура с трудом поддается прогнозированию, лучшего баланса нагрузки можно добиться с помощью динамического распределения итераций. Эти два способа планирования потоков, динамический и управляемый, устанавливаются с помощью раздела (clause) schedule в директиве OpenMP. При динамическом планировании потоки получают блоки из некоторого числа итераций, а после выполнения вычислений поток запрашивает новый блок итераций. Опциональный параметр chunk для раздела schedule устанавливает фиксированный размер блока для динамического распределения.

#pragma omp parallel for schedule(dynamic, 5)
  for (i = 0; i < n; i++)
  {
    unknown_amount_of_work(i);
  }
При управляемом планировании потокам изначально назначаются большие блоки итераций; число итераций, которые поступают в распоряжение потоков, запрашивающих новые блоки работы, уменьшается по мере сокращения набора нераспределенных итераций. Учитывая такую структуру распределения нагрузки, управляемое планирование чаще требует меньших непроизводительных затрат, чем динамическое планирование. Опциальный параметр chunk для раздела schedule обозначает минимальное число итераций в блоке, который будет выделен в режиме управляемого планирования.

#pragma omp parallel for schedule(guided, 8)
  for (i = 0; i < n; i++)
  {
    uneven_amount_of_work(i);
  }
Особого внимания заслуживает ситуация, когда рабочая нагрузка монотонно возрастает (или убывает) от итерации к итерации. Например, количество элементов в строке нижней треугольной матрицы возрастает по определенной закономерности. В этом случае указание сравнительно небольшого размера блока (для того, чтобы получить большое количество блоков/задач) при статическом планировании позволяет создать в достаточной мере сбалансированную нагрузку без непроизводительных затрат, возникающих при динамическом или управляемом планировании.

#pragma omp parallel for schedule(static, 4)
  for (i = 0; i < n; i++)
  {
    process_lower_triangular_row(i);
  }
Если выбор подходящего способа планирования неочевиден, с помощью параметра runtime по желанию можно изменять размер блока и сам способ планирования, без необходимости в перекомпиляции программы.

При использовании алгоритма parallel_for из библиотеки Intel® Threading Building Blocks (Intel® TBB), планировщик разделяет итерационную процедуру на небольшие задачи, которые затем назначаются потокам. Если некоторые итерации требуют больше времени на вычисление, чем другие, то планировщик Intel TBB может динамически похищать задачи у тех или иных потоков, чтобы обеспечить оптимальный баланс нагрузки между потоками.

Модели распараллеливания с явным разделением на потоки (например, потоки Windows*, Pthreads* и потоки Java*) не предусматривают возможности автоматического распределения набора отдельных задач между потоками. При необходимости, данный механизм придется вручную добавлять в код приложения. В случае статического планирования потоков это не составит особого труда. В случае динамического планирования, проще всего реализовать следующие модели: поставщик-потребитель (Producer/Consumer) и мастер-рабочий (Boss/Worker). В первой модели один поток (поставщик) помещает задачи в общую очередь, откуда потоки-потребители берут задачи на выполнение по мере необходимости. Модель поставщик-потребитель часто используется там, где требуется предварительная обработка задач до момента передачи их потребителям, хотя это и не является строго необходимым условием.

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

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

Рекомендации по применению

Любой метод динамического планирования задач сопряжен с определенными затратами на выделение самих задач. Эти затраты можно сократить путем объединения отдельных мелких задач в один блок рабочей нагрузки, соответственно, при использовании разделов к директивам OpenMP можно задать размер блока, отличный от принятого по умолчанию, который ограничит минимальное количество итераций в рамках задачи. Чтобы определить оптимальный объем вычислений, который можно выделить в отдельную задачу, следует учитывать характер вычислений, а также количество потоков и других ресурсов, доступных во время выполнения программы.

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