Нижегородский государственный университет им. Н.И.Лобачевского Факультет Вычислительной математики и кибернетики Лабораторная работа 3 Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Программирование для Intel Xeon Phi Козинов Е.А. Кафедра математического обеспечения ЭВМ При поддержке компании Intel

2 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Содержание Задача разложения чисел на простые сомножители Последовательная реализация алгоритма Перенос вычислений на сопроцессор intel xeon phi Параллельная реализация алгоритма –Распределение вычислений с использованием статического планировщика –Распределение вычислений с использованием динамического планировщика –Распределение вычислений с использованием динамического планировщика и подбор размера порции Оптимизация вычислительной функции Гибридная параллельная схема реализации алгоритма Дополнительные задания и литература

3 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Цели Рассмотрение на примере задачи разложения чисел на простые сомножители некоторых вопросов, возникающих при распараллеливании программ на сопроцессорах Intel Xeon Phi. Изучение одного из подходов переноса вычислений на сопроцессор Intel Xeon Phi. Рассмотрение вопросов влияния разных методов распределения вычислений на скорость вычислений. Изучения одного из подходов оптимизации вычислений под сопроцессор Intel Xeon Phi.

4 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Разложение множества чисел на простые сомножители Задача: разложить на простые множители (факторизовать) числа из диапазона от 1 до N. Используется алгоритм, который основан на попытке деления факторизуемого числа на каждое из меньших его чисел: Если остаток от деления равен нулю, то очередной множитель запоминается, после чего производится повторная попытка деления на это же число. При нахождении каждого множителя, факторизуемое число делится на него, и алгоритм завершает работу, когда частное от очередного деления становится равным единице.

5 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Разложение множества чисел на простые сомножители Пример: 12 = ?*?*...*? 12 / 2 = 6; // пробуем разделить на 2 раз 6 / 2 = 3; // пробуем разделить на 2 еще раз 3 / 2 = 1.5; // берем следующий делитель 3 / 3 = 1; // СТОП! – получили единицу

6 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Разложение множества чисел на простые сомножители Пример: 12 = ?*?*...*? 12 / 2 = 6; // пробуем разделить на 2 раз 6 / 2 = 3; // пробуем разделить на 2 еще раз 3 / 2 = 1.5; // берем следующий делитель 3 / 3 = 1; // СТОП! – получили единицу Результат: 12 = 2 * 2 * 3 Замечание: данный алгоритм факторизации использован только для демонстрации возможностей пакета Intel Parallel Studio На практике используют алгоритмы Полларда, Диксона и др.

7 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Тестовая инфраструктура Процессор 2 процессора на узел Xeon E (2.9 GHz, 8 ядер) Память 64 Gb СопроцессорIntel Xeon Phi 7110X Операционная системаLinux CentOS 6.2 Компилятор, профилировщик, отладчик Intel C/C++ Compiler 14

Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Н. Новгород, 2013 г. 8 Последовательная реализация алгоритма

9 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Объявление переменных В программе используются ряд объявлений и функций #include #include "omp.h" #include using namespace std; // Количество факторизуемых чисел #define NUM_NUMBERS // Вектора используемые для хранения // простых сомножителей чисел vector divisors[NUM_NUMBERS+1];

10 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Основная вычислительная функция void factorization() { for (int i = 1; i < NUM_NUMBERS; i++) { int number = i; int idx = number; for (int j = 2; j < idx; j++) { if (number == 1) break; int r; r = number % j; if (r == 0) { number /= j; divisors[idx].push_back(j); j--; }

11 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Вызов факторизации в основной программе int main() { … // Проведение вычислительного эксперимента time_s = omp_get_wtime( ); factorization(); time_f = omp_get_wtime( ); cout

12 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Компиляция и запуск Резервируем host salloc -N 1 --gres=mic:1 Переходим на host ssh $SLURM_NODELIST Компиляция icpc -O2 -openmp single.cpp –osingle Запуск./single

13 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Результаты экспериментов

14 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Результаты экспериментов

Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Н. Новгород, 2013 г. 15 Перенос вычислений на сопроцессор Intel Xeon Phi

16 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Перенос вычислений на Intel Xeon Phi Воспользуемся стандартной директивой в основной функции time_s = omp_get_wtime( ); #pragma offload target(mic:0) { factorization(); } time_f = omp_get_wtime( );

17 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Перенос вычислений на Intel Xeon Phi Попробуйте скомпилировать код. На выходе компилятора:./singleMIC.cpp(44): error: function "factorization" called in offload region must have been declared with compatible "target" attribute factorization(); Intel Xeon Phi имеет свою операционную систему и окружение. –Код, исполняемый на MIC, должен быть скомпилирован отдельно. –Каждая функция должна быть оформлена в программе соответствующим образом.

18 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Перенос вычислений на Intel Xeon Phi Правки в объявлении #pragma offload_attribute(push, target(mic)) #include #include "omp.h" #include using namespace std; #define NUM_NUMBERS vector divisors[NUM_NUMBERS+1]; void factorization(int chunk); int testThreadCount(); #pragma offload_attribute(pop)

19 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Перенос вычислений на Intel Xeon Phi Правки в реализации #pragma offload_attribute(push, target(mic)) … void factorization() {…} … #pragma offload_attribute(pop)

20 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Перенос вычислений на Intel Xeon Phi Откомпилируем и запустим программу. Как вы думаете, почему в результате вычислений не отобразились факторы чисел? Память центрального процессора и сопроцессора не являются общими.

21 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Перенос вычислений на Intel Xeon Phi Разработаем две функции –Получение размера векторов –Получение данных векторов

22 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Перенос вычислений на Intel Xeon Phi Получение размера векторов void getSizeVector(int count, int * num, int *size) { int sum = 0; int i = 0; for (i = 0; i < count; i++) { int Idx = num[i]; size[i] = sum ; sum += static_cast (divisors[Idx].size()); } size[i] = sum; }

23 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Перенос вычислений на Intel Xeon Phi Получение данных векторов void getVector(int count, int * num, int *pn) { int i = 0; int size = 0; int k = 0; for (i = 0; i < count; i++) { int Idx = num[i]; size = static_cast (divisors[Idx].size()); for (int j = 0; j < size;j++) { pn[k] = divisors[Idx][j]; k++; }

24 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Перенос вычислений на Intel Xeon Phi Изменения в main int num[10], countNum[11], * pn, sum; for (int i = 0; i < 10; i++) { int randomIdx = 1 + rand() % NUM_NUMBERS; num[i] = randomIdx; } #pragma offload target(mic:0) in(num[0:10]) out(countNum[0:11]) getSizeVector(10, num, countNum); sum = countNum[10]; pn = new int [sum]; #pragma offload target(mic:0) in(num[0:10]) out(pn[0:sum]) getVector(10, num, pn); for (int i = 0; i < 10; i++) { cout

25 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Результаты экспериментов

26 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Перенос вычислений на Intel Xeon Phi Центральный процессор приблизительно в пятнадцать раз обогнал сопроцессор Intel Xeon Phi. Причина - ядра сопроцессора гораздо более простые (с точки зрения архитектуры) и обладают меньшей тактовой частотой, чем ядра центрального процессора. Необходимо распараллеливание.

Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Н. Новгород, 2013 г. 27 Параллельная реализация алгоритма

28 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Статическое распределение нагрузки Стратегия распределения нагрузки между потоками: Достаточно использовать директиву OpenMP #pragma omp parallel for 50K100K150K200K

29 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Результаты экспериментов Ядер 60. Потоков 240. Что помешало большему ускорению? Вычисления сильно разбалансированы и тратится большое время на синхронизацию большого количества потоков.

30 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Динамическое распределение нагрузки. Стратегия 1. Стратегия распределения нагрузки между потоками: Для реализации используем расширенные возможности директив OpenMP: #pragma omp parallel for schedule(dynamic) …

31 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Динамическое распределение нагрузки. Стратегия 1. В чем причина подобного замедления? Основная причина в методе распределения чисел. –Все четные потоки получают четные числа. –Потоков четное число. Взамен того, что бы сбалансировать вычисления мы добились большего дисбаланса. Так как потоков много, дисбаланс при статическом планировании оказался менее ярко выраженным.

32 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Динамическое распределение нагрузки. Стратегия 2. Стратегия распределения нагрузки между потоками: Для реализации используем расширенные возможности директив OpenMP (укажем размер порции): #pragma omp parallel for schedule(dynamic, chunk) Какой размер порции выбрать? …

33 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Динамическое распределение нагрузки. Стратегия 2. Подбор размера порции: Размер порции сильно влияет на время вычислений. Из графика видно, что оптимальный размер порции составляет 30.

34 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Динамическое распределение нагрузки. Стратегия 2. Динамическое планирование при правильном подборе размера порции позволило получить большее ускорение вычислений!

Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Н. Новгород, 2013 г. 35 Оптимизация вычислительной функции

36 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Сравнение CPU и Intel Xeon Phi В предыдущих разделах лабораторной работы был рассмотрен наивный подход к переносу вычислений с центрального процессора на сопроцессор. Cравним время работы параллельной версии алгоритма на центральном процессоре и сопроцессоре Intel Xeon Phi.

37 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Анализ результатов Лучшее время параллельного алгоритма на сопроцессоре в почти четыре раза хуже, чем время на центральном процессоре. Исходя из характеристик, сопроцессор Intel Xeon Phi обладает большей пиковой производительностью. Почему не удается достичь большей производительности? Для достижения пиковой производительности ускорителя необходимо задействовать не только все ядра процессора, но и код должен быть векторизуем.

38 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Анализ результатов Соберем отчет по векторизации кода. icpc -O2 -openmp -vec-report3 parMIC.cpp Посмотрим полученный отчет: … parMIC.cpp(174): (col. 5) remark: *MIC* loop was not vectorized: unsupported loop structure parMIC.cpp(169): (col. 3) remark: *MIC* loop was not vectorized: nonstandard loop is not a vectorization candidate … Строки 169 и 174 соответствуют циклам функции факторизации. Циклы не векторизовались.

39 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Оптимизация кода. Предпосылки. Intel Xeon Phi содержит регистры длиной 512 бит для векторных операций. В разрабатываемой программе используются целые числа типа int. Размер int 4 байта. Как следствие, если бы код векторизовался, за раз можно было бы выполнить 16 операций. В рассматриваемой задаче основной операцией является поиск остатка от деления и сравнение с 0. –Фактор имеет несравнимо малое число делителей по сравнению с количеством делений. –Как правило, число не делится.

40 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Оптимизация кода. Рассматриваемый подход. Заведем массив из 16 чисел (размер регистра). В каждый элемент массива можно вычислить остаток от деления от текущего делителя плюс индекс элемента массива. Полученные делители можно перемножить. Если результат умножения не равен нулю, то 16 чисел можно уже не проверять на делимость. В противном случае необходимо выполнить исходную проверку на делимость и сместить «окно» проверяемых делителей.

41 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Оптимизация кода. Программная реализация. #define LOOP_SIZE 16 … void factorization(int chunk) { #pragma omp parallel for schedule(dynamic, chunk) for (int i = 1; i < NUM_NUMBERS; i++) { int rr[LOOP_SIZE]; int r, p; int number = i; int idx = number;

42 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Оптимизация кода. Программная реализация. for (int j = 2; j < idx; j++) { if (number == 1) break; #pragma simd for(int k = 0; k < LOOP_SIZE; k++) { rr[k] = number % (j + k); } p = 1; #pragma simd for(int k = 0; k < LOOP_SIZE; k++) { p *= rr[k]; } if(p != 0) { j += LOOP_SIZE - 1; } else { r = number % j; if (r == 0) { number /= j; divisors[idx].push_back(j); j--; }

43 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Результаты экспериментов

44 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Результаты экспериментов Особенностью оптимизации под Intel Xeon Phi является то, что оптимизация также положительно влияет и на время вычислений на центральном процессоре.

45 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Результаты экспериментов Ниже приведен график сравнение времени работы оптимизированных версий факторизации на CPU и сопроцессоры.

Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Н. Новгород, 2013 г. 46 Гибридная параллельная схема реализации алгоритма

47 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Результаты экспериментов Последним шагом попробуем организовать схему вычислений одновременно на центральном процессоре и на сопроцессоре. Так как времена стали слишком маленькие, что бы была возможность сделать какие-то выводы, увеличим количество факторизуемых чисел в 10 раз. Тенденции сохранились.

48 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Метод рапараллеливания Директива #pragma offload target(mic:0) по умолчанию является синхронной. В директиве есть дополнительная опция позволяющая выполнить вычисления асинхронно. –Для этого в директиве объявляется сигнал. –Для синхронизации сигнал можно проверять и ожидать. Отправим часть вычислений на Intel Xeon Phi в асинхронном режиме. Оставшуюся часть чисел факторизуем на центральном процессоре.

49 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Программная реализация Изменения в вызове float *f1; chunk = NUM_NUMBERS / 2; time_s = omp_get_wtime( ); #pragma offload target(mic:0) signal(f1) { factorization(chunk, 1); } factorization(NUM_NUMBERS - chunk, chunk + 1); #pragma offload target(mic:0) wait(f1) { end(); } time_f = omp_get_wtime( );

50 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Программная реализация Изменение в вычислительной функции void factorization(int chunk, int start) { #pragma omp parallel for schedule(dynamic, 30) for (int i = start; i < start + chunk; i++) { … }

51 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Результаты экспериментов Как видно из графика мы получили время вычислений среднее между временем сопроцессора и процессора. С чем это связано? Почему нет ускорения? Причина - некорректным распределением нагрузки. –Во-первых, время факторизации маленьких и больших чисел не одинаково. –Во-вторых, процессор и сопроцессор обладают разной вычислительной производительностью. Попробуем сдвинуть границу. Первые 8/10 чисел отдадим сопроцессору, а оставшиеся вычислим на CPU.

52 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Результаты экспериментов

Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Н. Новгород, 2013 г. 53 Дополнительные задания и литература

54 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Задания для самостоятельной работы Попробуйте путем изменения количества потоков OpenMP увеличить производительность параллельного алгоритма факторизации чисел. Учтите, что особенностью сопроцессора Intel Xeon Phi является то, что большая производительность может проявиться при наличии нескольких потоков OpenMP на ядро. Проверьте, можно ли повысить производительность алгоритма факторизации чисел при нечетном размере порции. Изучите, какие алгоритмические оптимизации можно выполнить, для повышения производительности кода.

55 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Задания для самостоятельной работы Рассмотрите, какие программные оптимизации можно выполнить еще с кодом для повышения производительности. Более точно подберите границу разделения порции вычислений для сопроцессора и процессора в гибридной схеме.

56 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Литература 1. Василенко О.Н. Теоретико-числовые алгоритмы в криптографии – М.: МЦНМО, 2003.Стр Кнут Д. Искусство программирования. – М.: Вильямс, Т.2, с Черемушкин А.В. Лекции по арифметическим алгоритмам в криптографии. – М.: МЦНМО, Стр Международный Вычислительный Центр Российской Академии Наук. – aURL: (дата обращения: )

57 Н. Новгород, 2013 г. Оптимизация вычислений в задаче о разложении чисел на простые сомножители. Векторизация и балансировка нагрузки Авторский коллектив Козинов Евгений Александрович, ассистент кафедры Математического обеспечения ЭВМ факультета ВМК ННГУ