Исправляем дисбаланс нагрузки с помощью Intel® Parallel Amplifier

Curing Thread Imbalance Using Intel® Parallel Amplifier [Eng., PDF 302KB]

Введение

Одним из критических факторов, отрицательно влияющих на производительность многопоточных приложений, является дисбаланс нагрузки потоков. Его корректировка – важнейший элемент отладки. Целью балансировки является минимизация времени простоя потоков и ровное распределение работы между всеми потоками с минимальными издержками на сам процесс распределения. Intel® Parallel Amplifier, являющийся частью Intel® Parallel Studio, помогает в тонкой настройке параллельных приложений для достижения оптимальной производительности при работе на многоядерных процессорах. Он облегчает задачу поиска критических участков при параллельной работе и помогает разработчикам ускорить процесс идентификации и исправления проблем такого рода.

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

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

Анализ, проводимый Intel Parallel Amplifier, показывает, как приложение использует доступные процессорные ядра конкретной системы. Parallel Amplifier собирает и выводит информацию по количеству активных потоков, то есть потоков, которые либо работают, либо стоят в очереди, а не ожидают на какой-нибудь блокировке. Количество работающих потоков соответствует уровню параллелизации приложения. Сравнивая его с количеством процессоров, Intel Parallel Amplifier классифицирует уровень использования приложением процессоров системы.

Чтобы показать, как Intel Parallel Amplifier определяет критические участки и проблемы дисбаланса нагрузки, мы использовали проверочную программу, написанную на С. Эта программа рассчитывает потенциальную энергию системы частиц на основе дистанции между ними в трёх измерениях. Программа является многопоточным приложением, использующим нативные потоки Win32* и создает потоки в количестве, указанном в переменной NUM_THREADS. Здесь мы не будем приводить начальные сведения о Win32 threads, потоковых технологиях и способах реализации многопоточности. Целью данной статьи является демонстрация, как Intel Parallel Amplifier может помочь при идентификации дисбаланса нагрузки и при разработке масштабируемых параллельных приложений.
for (i = 0; i < NUM_THREADS; i++)
{
  bounds[0][i] = i * (NPARTS / NUM_THREADS);
  bounds[1][i] = (i + 1) * (NPARTS / NUM_THREADS);
}
for (j = 0; j < NUM_THREADS; j++)
{
  tNum[j] = j;
  tHandle[j] = CreateThread(NULL,0,tPoolComputePot,&tNum[j],0,NULL);
}


DWORD WINAPI tPoolComputePot (LPVOID pArg) {
  int tid = *(int *)pArg;
  while (!done)
  {
    WaitForSingleObject (bSignal[tid], INFINITE);
    computePot (tid);
    SetEvent (eSignal[tid]);
  }
  return 0;
}
Ниже приведена процедура, выполняемая параллельно в каждом потоке. В процедуре computePot каждый поток использует сохраненные в массиве границы с индексом, соответствующим идентификатору потока (tid), которые означают начальную и конечную границы диапазона частиц, с которыми работает поток. После того, как поток инициализирует пространство своих итераций (значения start и end), он начинает вычислять потенциальную энергию частиц:
void computePot (int tid) {
  int i, j, start, end;
  double lPot = 0.0;
  double distx, disty, distz, dist;
  start = bounds[0][tid];
  end = bounds[1][tid];

  for (i = start; i < end; i++)
  {
    for (j = 0; j < i-1; j++)
    {
      distx = pow ((r[0][j] - r[0][i]), 2);
      disty = pow ((r[1][j] - r[1][i]), 2);
      distz = pow ((r[2][j] - r[2][i]), 2);
      dist = sqrt (distx + disty + distz);
      lPot += 1.0 / dist;
    }
  }
  gPot[tid] = lPot;
}
Анализ критических участков используется для поиска в приложении хот-спотов, чтобы разработчик мог сфокусировать свои усилия на нужных функциях. Общее время работы данного приложения составляет около 15.4 секунды в системе с одним процессором Intel® Core™ 2 Quad. Анализ показывает, что процедура computePot является самой времязатратной, в ней тратится большая часть процессорного времени (23.331 секунд). При более подробном рассмотрении функции computePot, мы видим, что конкретно является причиной его возникновения.

Рис. 1. Анализ критических участков кода.

Анализ уровня параллелизма показал, что использование процессора в данной процедуре является неэффективным (рис 2), в среднем приложение использует 2.28 ядра (рис. 3). Большую часть времени загрузка процессора является плохой (используется только одно ядро) или нормальной (используются два или три ядра). Далее встает вопрос, виноват ли в плохой загрузке процессора дисбаланс нагрузки. Самый простой способ найти ответ – выбрать Function-Thread-Bottom-up Tree или Thread-Function-Bottom-up Tree в качестве новой гранулярности, как показано на рис. 2.



Рис. 2. Результаты анализа параллельности.

Рис. 3. Обобщенный вид результатов анализа уровня параллелизма.

Значения времени в анализе параллелизма соответствуют следующим типам использования:
  • Неактивное состояние : Все потоки программы в состоянии ожидания, ни один из потоков не работает.
  • Плохо : По умолчанию, использование является плохим, если количество потоков не превышает 50% возможного параллелизма.
  • Нормально : По умолчанию, использование является нормальным, когда количество потоков находится между 51-85% возможного параллелизма.
  • Идеально : По умолчанию, использование является идеальным, когда количество потоков находится между 86-115% возможного параллелизма.


Рис. 4. Результаты анализа уровня параллелизма, показывающие соответствие Функция ->Поток.

На рис. 4 видно, что четыре рабочих потока, выполняющих данную процедуру параллельно, выполняют разный объем работы и таким образом провоцируют дисбаланс нагрузки и плохое использование процессора. Такое поведение потоков является препятствием для хорошего масштабирования любого многопоточного приложения. Внимательно всмотревшись в исходный код, можно увидеть, что внешний цикл основной программы статично разделяет итерации на основе количества рабочих потоков, создаваемых в пуле потоков (start = bounds[0][tid], end = bound[1][tid]). Внутренний цикл данной процедуры использует внешний индекс как условие для выхода. Таким образом, чем большее количество частиц используется во внешнем цикле, тем большее количество итераций выполняет внутренний цикл. Алгоритм устроен так, что каждая пара частиц только один раз участвует в расчете потенциальной энергии. Такое статичное распределение явно задает разный объём вычислений.

Одним из способов исправить эту проблему дисбаланса является использование динамичного назначения частиц потокам. Например, вместо того, чтобы назначать последовательные группы частиц, как это делается в оригинальной версии, каждый поток, начиная с частицы с индексом, соответствующим идентификатору потока (tid), может рассчитывать все частицы, чей номер отличается от номера потока. Например, если используется два потока, то один поток может обрабатывать частицы с четными номерами, а другой поток – с нечетными.
void computePot(int tid) {
  int i, j;
  double lPot = 0.0;
  double distx, disty, distz, dist;
  for(i=tid; i<NPARTS; i+= NUM_THREADS ) { //<-for( i=start; i<end; i++ )
    for( j=0; j<i-1; j++ ) {
    distx = pow( (r[0][j] - r[0][i]), 2 );
    disty = pow( (r[1][j] - r[1][i]), 2 );
    distz = pow( (r[2][j] - r[2][i]), 2 );
    dist = sqrt( distx + disty + distz );
    lPot += 1.0 / dist;
    }
  }
  gPot[tid] = lPot;
Анализ уровня параллелизма приложения после внесённых изменений показывает, что наша функция теперь полностью использует все имеющиеся ядра. (Рис. 5).


Рис. 5. Результаты анализа уровня параллелизма после внесения изменений.

На итоговом графике (Рис.6) показаны результаты и эффект внесённых изменений. Время работы снизилось с 15.4 до 9.0 секунд, а средняя загрузка процессора увеличилась с 2.28 до 3.9. Простая реорганизация рабочих потоков, чтобы они выполняли равное количество вычислений, позволило получить ускорение в 1.7 раза и уменьшить время работы на 41.5%.


Рис.6. Итоговый вид версии с хорошо сбалансированной нагрузкой.


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

Существуют разные методы реализации многопоточности, в каждом из них есть свой механизм управления распределением задач по потокам. Вот некоторые наиболее распространенные:
  • Явные или нативные потоковые методы (например, Win32 и POSIX* threads)
  • Абстрагирующие модели
    • Intel® Threading Building Blocks
    • OpenMP*
Явные потоковые методы (например, Win32 и POSIX threads) не имеют никаких средств автоматического планирования распределения независимых задач по потокам. При необходимости такая возможность должна быть запрограммирована в самой программе. Статическое планирование задач является простым упражнением, как было показано в приведённом примере. Для динамического планирования можно легко реализовать два метода: Производитель/Потребитель и Менеджер/Рабочий. В первом случае один или более потоков (Производители) помещают задачи в очередь, в то время как Потребитель берет задачи из очереди на обработку по мере надобности. Часто, хотя и не всегда, модель Производитель/Потребитель используется, когда задачи нужно каким-либо образом обработать перед тем, как передать потокам-Потребителям. В модели Менеджер/Рабочий рабочие потоки общаются с потоком менеджера в те моменты, когда готовы получить работу, и работа назначается напрямую.

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

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

При использовании динамического планирование могут возникать проблемы микроархитектуры под названием «ложное распределение». Ложное распределение – это проблема структуры доступа к памяти, снижающая производительность. Оно возникает, когда два или более потоков поочередно пишут в одну и ту же линию кэша. Поэтому при динамическом распределении нагрузки между потоками нужно быть особенно осторожным.

Intel® Threading Building Blocks (Intel® TBB) – это параллельная программная модель на основе динамических библиотек, которая состоит из динамической библиотеки на базе шаблонов и которая помогает разработчикам раскрыть все возможности многоядерных процессоров. Intel TBB позволяет разработчикам писать масштабируемые приложения, использующие наборы параллельных функций и алгоритмов. В Intel TBB предусмотрен алгоритм планирования «разделяй и властвуй» наряду с механизмом похищения задач, так что разработчику не надо беспокоиться об алгоритмах планирования. Используя механизм похищения задач, Intel TBB может балансировать нагрузку, распределяя задачи между рабочими потоками.

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