Multi Core
Введение
Для создания и синхронизации потоков, а также для управления ими, в таких явных методах реализации многопоточности, как потоки Win32* или POSIX*, используются библиотеки. Использование явных потоков требует полной реструктуризации кода. OpenMP* – это набор директив, функций прикладных программных интерфейсов и переменных окружения, позволяющих внедрять потоки в приложения на достаточно высоком уровне. Директивы OpenMP используются для обозначения областей кода, которые можно выполнять одновременно. Компиляторы, совместимые с OpenMP, трансформируют код и вставляют необходимые вызовы функций для параллельного запуска указанных областей. В большинстве случаев последовательная логика оригинального кода может быть сохранена и без труда восстановлена путем игнорирования директив OpenMP во время компиляции.
Программы OpenMP – это многопоточные программы, и они могут содержать те же ошибки и проблемы производительности, что и приложения с явными потоками. Предполагается, что вы знакомы с OpenMP, поскольку в данной статье рассматривается использование инструментов Intel® Threading Tools, Intel® Thread Checker и Thread Profiler для анализа программ OpenMP. Что касается Intel Thread Checker, то мы отказались от обычного использования идентификационных конфликтов хранения в исходном коде, разделенном на потоке. Вместо этого мы используем диагностический вывод для идентификации и категоризации объема переменных в рамках параллельных областей. После этого обсуждаются две из наиболее характерных проблем производительности, которые наблюдаются в исходных кодах OpenMP. На примере демонстрируется использование Thread Profiler для выявления этих проблем, а также приводятся некоторые пути их решения. Для получения более подробной информации об использовании инструментария Intel® Threading Tools см. документы "Приступая к работе с Intel® Thread Checker" и "Приступая к работе с Thread Profiler", входящие в комплект документации для инструментов многопоточности.
Для того чтобы более наглядно проиллюстрировать нашу точку зрения, мы выбрали для анализа исходный код, в котором применяется алгоритм перебора для поиска простых чисел в пользовательском диапазоне переменных. Последовательный код выбирает потенциальное простое число (четные числа даже не рассматриваются) и делит его на все переменные, меньшие или равные квадратному корню этого числа. Если деление происходит без остатка, число является сложным, если с остатком – простым. Также существует возможность распечатки всех простых чисел, при этом всегда вычисляется количество найденных простых чисел. Известно, что простые числа, большие, чем 2, могут быть однозначно классифицированы на две категории: числа, которые могут быть разложены до вида 4n+1, и числа, которые могут быть разложены до вида 4n-1. Кроме подсчета общего количества найденных простых чисел, для каждого простого числа происходит приращение счетчика связанного класса простых чисел путем нахождения остатка от деления на 4.
#include <stdio.h>
#include <math.h>
main(int argc, char *argv[])
{
int i, j, limit;
int start, end; /* range of numbers to search */
int number_of_primes=0; /* number of primes found */
int number_of_41primes=0;/* number of 4n+1 primes found */
int number_of_43primes=0;/* number of 4n-1 primes found */
int prime; /* is the number prime? */
int print_primes=0; /* should each prime be printed? */
start = atoi(argv[1]);
end = atoi(argv[2]);
if (!(start % 2)) start++;
if (argc == 4 && atoi(argv[3]) != 0) print_primes = 1;
printf("Range to check for Primes: %d - %d\n\n",start, end);
for(i = start; i <= end; 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) {
if (print_primes) printf("%5d is prime\n",i);
number_of_primes++;
if (i%4 == 1) number_of_41primes++;
if (i%4 == 3) number_of_43primes++;
}
}
printf("\nProgram Done.\n %d primes found\n",number_of_primes);
printf("\nNumber of 4n+1 primes found: %d\n",number_of_41primes);
printf("\nNumber of 4n-1 primes found: %d\n",number_of_43primes);
Intel Thread Checker в качестве вспомогательного средства при использовании OpenMP
В таком небольшом исходном коде существует только одно логически подходящее место для вставки директив OpenMP: главный цикл for. Исправленный исходный код в начале цикла for выглядит следующим образом:
По умолчанию все переменные, кроме переменной итерации цикла, являются совместно используемыми. В большинстве случаев для некоторых потоков потребуются собственные копии определенных переменных во избежание состояния гонки. В некоторых случаях логика программы будет работать лучше, если доступ к некоторым из этих переменных будет синхронизирован. Перед определением оптимального метода защиты доступ к совместно используемым переменным мы должны понять, какие переменные нужно защитить.
При таком небольшом примере предполагается, что программисты даже с минимальными знаниями OpenMP потратят не более 30 секунд на выявление переменных, которые необходимо защитить, и еще 30 секунд на формулировку адекватных способов реализации защиты. Однако представим себе гораздо более объемный отрывок исходного кода, в котором область параллельной обработки содержит в себе сотни или тысячи строк исходного кода, множество вызовов функций, параметры которых указаны при помощи указателей и различных имен. Выявление потенциальных конфликтов хранения сейчас является более пугающей задачей.
К счастью, Intel Thread Checker автоматически идентифицирует переменные, для которых в каком-либо виде необходим монопольный доступ. После добавления директивы, как это показано выше, и проверки кода при помощи Thread Checker обнаружено, что переменные limit, prime, j, number_of_primes, number_of_43primes и number_of_41primes в отсутствии какой-либо формы синхронизации вызывают конфликты хранения. Это показано ниже на снимке экрана Intel Thread Checker.
(Нажмите на изображение для увеличения)
При изучении исходного кода и планируемого использования каждой переменной мы можем определить, как наилучшим образом исправить оригинальный исходный код, чтобы применить в нем результаты анализа переменных.
Все переменные, записанные в параллельную область до процесса считывания, должны быть индивидуальными. В случае с примером исходного кода программы для поиска простых чисел переменные limit, prime и j – это рабочие или временные переменные, используемые в рамках параллельной области. Значения этих переменных не используются за пределами параллельной области. Таким образом, мы можем распределять копии в каждом потоке при помощи индивидуального оператора директивы OpenMP. Оставшиеся три переменные счетчика должны содержать в себе глобальную сумму для вывода на печать после параллельной области. В этом следует оставить их совместно используемыми, но выполнить приращение счетчиков в рамках критического раздела. В результате мы получим следующий исходный код параллельного региона:
#pragma omp parallel for private (limit, j, prime)
for(i = start; i <= end; 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) {
if (print_primes) printf("%5d is prime\n",i);
#pragma critical
{
number_of_primes++;
if (i%4 == 1) number_of_41primes++;
if (i%4 == 3) number_of_43primes++;
}
}
}
Проверка этого кода при помощи Intel Thread Checker больше не приводит к появлению ошибок. Мы создали исходный код, корректно распределенный на потоки. В качестве альтернативы использованию индивидуального оператора можно сделать измененные переменные локальными для цикла for и, как следствие, для параллельной области. Это будет более корректным решением, если переменные больше нигде в коде не используются. Дополнительное преимущество подобной альтернативной реализации состоит в том, что в отношении переменных последовательный код больше соответствует параллельному коду.
Кроме поиска переменных, для которых требуется защита, Intel Thread Checker может также определить, является ли раздел исходного кода претендентом на параллельную обработку данных. При длинных или имеющих объемный список вызовов отрывках кода выявление существующих связей (зависимостей) с потенциальными параллельными циклами очень трудоемко и требует немало времени. Зависимости, такие как индукционные переменные (переменные, возрастающие при каждой итерации цикла) или рекуррентные соотношения (доступ к информации, вычисленной во время предыдущей итерации цикла), препятствуют корректной параллельной обработке при отсутствии алгоритмов, устраняющих зависимость. Intel Thread Checker указывает на конфликты хранения, а программист при изучении исходного кода подтверждает, что использование отмеченной переменной не приводит к формированию циклической зависимости.
Настройка производительности с помощью Thread Profiler
После создания корректного многопоточного кода следует измерить его производительность. Можно сравнить время выполнения последовательного и многопоточного кода. Если время выполнения многопоточного кода в два раза меньше времени выполнения последовательного кода при запуске двух потоков на двухпроцессорной системе, то вас можно поздравить с успешным применением параллельной обработки. Если время выполнения многопоточного кода приближается ко времени выполнения последовательного кода или превышает его, возникают определенные вопросы. Крупные сегменты исходного кода все еще запускаются последовательно? Сильно ли влияет синхронизация на производительность выполнения кода? Сбалансированы ли объемы работ для каждого потока?
Для ответа на эти вопросы можно использовать инструмент Thread Profiler для OpenMP, который укажет программисту на те места исходного кода, которые можно исправить для повышения производительности параллельной обработки. Благодаря структурному характеру OpenMP, ThreadProfiler может делать предположения об исполняемой модели приложения и указывать на очень специфические проблемы производительности. Среди таких обычных проблем – дисбаланс нагрузки и расходы на синхронизацию. Стоит взглянуть на то, как Thread Profiler выявляет обе эти проблемы и обсудить некоторые возможные пути их решения.
Дисбаланс нагрузки
Бездействующий процессор в входе параллельной обработки – бесполезный ресурс. Бездействующие потоки – это также бесполезный ресурс, который может повысить общее время выполнения параллельной обработки. По умолчанию в конце каждой параллельной области OpenMP или области равномерного распределения потоки ждут перед условным барьером до тех пор, пока все потоки не завершат назначенные им задания в рамках области. Когда потокам присваиваются неравные объемы работы, потоки с меньшим объемом работ бездействуют перед условным барьером области и ждут, пока завершится выполнения потоков с большим объемом работы.
При прогоне измененного кода программы для поиска простых чисел через инструмент ThreadProfiler при условии выполнения четырех потоков на двух процессорах с технологией Hyper-Threading (Технология HT) обнаруживается, что бездействующие потоки потребляют достаточно значительную часть времени (14%). Поскольку в данном примере кода существует только одна параллельная область, место возникновения дисбаланса очевидно. Однако при попытке определить источник дисбаланса в более сложных кодах для поиска области (областей), являющихся причиной непроизводительной работы, используется инструмент Regions View. Выбрав панель в параллельной области, можно найти исходный код в соответствующей ей области.
Для лучшего определения причины дисбаланса используйте инструмент Threads View для выбранной проблемной области. Пример использования приведен ниже.
(Нажмите на изображение для увеличения)
Ступенчатая модель снижения дисбаланса является стандартной и указывает на то, что рабочая нагрузка, хотя и распределена равномерно в виде количества задач на поток, постоянно повышает необходимый объем вычислительных ресурсов. В этом случае количество целых чисел, подлежащих проверке на предмет простоты, делится поровну при помощи стандартного статического распределения итераций. Однако с ростом целых чисел растет и число факторов, которые необходимо проверить. Таким образом, поток, проверяющий верхнюю четверть целых чисел, выполняет больше вычислений, чем три предыдущих потока.
Такая модель дисбаланса также указывает на то, что размеры и порядок задач фиксированы. Указанный дисбаланс можно исправить путем задания более динамичного распределения проверяемых задач или целых чисел. Добавление пункта планирования к директиве parallel-for предоставляет дополнительный контроль над присвоением итераций потокам. Использование динамического планирования с достаточно большим размером фрагмента данных, например, schedule(dynamic,100), способствует разнесению итераций для равного распределения вычислительных ресурсов, а также присваивает достаточное количество работы для каждого фрагмента данных с целью поддержки низкого уровня затрат на планирование. Менее очевидное планирование дисбаланса примера исходного кода – schedule(static,1). Данный тип планирования осуществляет распределение итераций по потокам по принципу игральных карт: одна итерация на поток через все потоки по кругу, до тех пока не будут присвоены все итерации. Ниже приведены результаты работы Thread Profiler для исходного кода с использованием динамического планирования целых чисел, подлежащих проверке.
Если дисбаланс более равномерно распределен между потоками, особенно в случае с областями, вызываемыми несколько раз в процессе выполнения, нагрузка будет изменяться от одного шага к другому. Это значит, что потокам будут присваиваться более объемные задачи, но возможности прогнозирования этих задач нет. Чтобы исправить эту ситуацию, попробуйте использовать более мелкие задачи для динамического присвоения потокам.
Влияние синхронизации
Потоки, ожидающие синхронизации, также потребляют определенное количество времени, хотя в новой версии тестового кода это время очень мало. Как и в случае с дисбалансом нагрузки, пример кода достаточно прост для того, чтобы точно обнаружить место для синхронизации потоков. В более сложных ситуациях используйте функцию Regions View в инструменте Thread Profiler для определения параллельных областей, содержащих подобные конфликты, и сконцентрируйте свое внимание на этом.
Фрагменты кода, защищенные при помощи синхронизации, должны быть как можно меньше и при этом содержать корректные участки кода. С помощью данного принципа уменьшается время бездействия, которое потоки должны проводить в ожидании доступа к защищенным фрагментам кода. В случае с приведенным примером кода критический раздел предельно мал. Внешние выражения, для которых не существует необходимости монопольного доступа со стороны потоков, отсутствуют. Каждое выражение может быть помещено в отдельный критический раздел. Однако в этом случае следует использовать именованные критические разделы, поскольку все безымянные критические разделы расцениваются OpenMP как одинаковые, даже если они находятся в совершенно разных функциях и файлах исходного кода. Чтобы использовать именованные критические разделы в приведенном примере исходного кода, измените значения приращения счетчиков следующим образом:
#pragma omp critical (cs1)
number_of_primes++;
#pragma omp critical (cs2)
if (i%4 == 1) number_of_41primes++;
#pragma omp critical (cs3)
if (i%4 == 3) number_of_43primes++;
При четырех потоках и трех критических разделах существует потенциальная возможность того, что, по крайней мере, один поток будет ожидать входа в один из критических разделов. Кроме того, затраты на вход в критический раздел и выход из него увеличились в три раза. Результаты работы Thread Profiler содержат информацию о процентном соотношении времени, потоках, ожидающих блокировки и удвоении затрат на параллельную обработку при использовании три именованных критических разделов в изначальном критическом разделе, состоящем из трех строк.
Еще одно железное правило, которого необходимо придерживаться – не размещать синхронизацию внутри цикла. Существует два варианта применения этого правила в приведенном примере исходного кожа. В первом варианте используются временные переменные для каждого счетчика, объявляемые в целях создания индивидуальной копии в каждом потоке. Эти локальные переменные увеличиваются внутри цикла, и перед окончанием цикла локальные значения добавляются к глобальным значениям в рамках одного критического раздела после создания равномерного распределения. Таким образом, в исходном коде существует только одно место, где потоки могут отложить выполнение других потоков. Одним из препятствия для данного метода является то, что в последовательный код необходимо внести изменения дня удовлетворения требований параллельной обработки.
#pragma omp parallel
{ int numPrimes=0; /* local number of primes found */
int num41Primes=0; /* local number of 4n+1 primes found */
int num43Primes=0; /* local number of 4n-1 primes found */
#pragma omp for schedule(dynamic,100)
for(i = start; i <= end; i += 2) {
int limit, j, prime;
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) {
if (print_primes) printf("%5d is prime\n",i);
numPrimes++;
if (i%4 == 1) num41Primes++;
if (i%4 == 3) num43Primes++;
}
} // end for
#pragma omp critical
{ // Update global counter values with local values
number_of_primes += numPrimes;
number_of_41primes += num41Primes;
number_of_43primes += num43Primes;
}
} // end parallel region
Второй метод использует возможности OpenMP для выполнения тех же операций, которые описаны выше, но при этом изменения в последовательный код не вносятся. Выражение уменьшения OpenMP создает индивидуальные копии совместно используемых переменных, осуществляет вычислительные операции с этими индивидуальными копиями в рамках каждого потока, а затем в конце параллельной области возвращает все частичные результаты в изначальные переменные. Синтаксис выражения уменьшения требует комбинирования связанного двоичного оператора и имен переменных с оператором при завершении параллельной области. В результате работы Thread Profiler после внесения указанных изменений в пример исходного кода (дополнительную информацию см. ниже) мы получаем почти идеальное параллельное выполнение (99,984%).
Резюме
Если вы следовали всем приведенным советам, окончательный вариант параллельной области в приведенном примере исходного кода должен выглядеть следующим образом:
#pragma omp parallel for schedule(dynamic,100)
reduction(+:number_of_primes,number_of_41primes,number_of_43primes)
for (i = start; i <= end; i += 2) {
int limit, j, prime; // locally declared for private
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) {
if (print_primes) printf("%5d is prime\n",i);
number_of_primes++;
if (i%4 == 1) number_of_41primes++;
if (i%4 == 3) number_of_43primes++;
}
}
Чтобы получить окончательный вариант, мы использовали инструмент Intel Thread Checker для первоначального определения того, можно ли запустить цикл последовательного кода в параллельной обработке, и какие переменные необходимо сделать индивидуальными или защитить при помощи монопольного доступа. После внесения первоначальных изменений в исходный код результаты, полученные при прогоне кода через инструмент Thread Profiler, позволили выполнить параллельное выполнение для наиболее полного использования вычислительных ресурсов системы.
ПО Intel® Threading Tools часто хвалят за способность быстрого поиска ошибок многопоточности в исходном коде и выявления невидимых узких мест. Используя эти инструменты на более ранней стадии разработки, можно автоматизировать некоторые из наиболее трудоемких задач, используемых для обнаружения мест эффективного применения параллельной обработки в последовательных приложениях.
Дополнительные ресурсы
Статьи
