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

Введение

Презентацию к лабораторной работе Вы можете скачать здесь.

Повышение производительности программ всегда была и будет актуальной проблемой. Для повышения производительности, эффективнее всего использовать алгоритмическую оптимизацию. К сожалению, алгоритмическая оптимизация, как правило, является очень трудоемкой. Второй путь повышения производительности программ – распараллеливание. В последнее время для распараллеливания используются не только ядра центрального процессора, но и различные ускорители и сопроцессоры. Одним из таких сопроцессоров является Intel Xeon Phi недавно появившейся на рынке.

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

Методические указания

Цели и задачи работы

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

Данная цель предполагает решение следующих основных задач:

Структура работы

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

Тестовая инфраструктура

Для проведения экспериментов использовались вычислительные ресурсы МСЦ РАН [10.4]. На момент проведения экспериментов тестовая инфраструктура представлена в таблице 8.1.

Задача разложения чисел на простые сомножители

Лабораторная работа построена на задаче факторизации (разложения на простые сомножители) чисел из диапазона от 1 до N. Используемый алгоритм базируется на попытке деления факторизуемого числа на каждое из меньших его чисел [10.2]. Если остаток от деления на некоторый множитель равен нулю, то этот множитель запоминается, частное становится делимым, после чего производится повторная попытка деления на это же число. Алгоритм завершает свою работу, когда частное от очередного деления равно единице.

Рассмотрим работу алгоритма для одного числа. Допустим, что необходимо определить простые множители числа 12. Для этого перебираются числа, меньшие 12, начиная с 2, и выполняется последовательность операций деления:

12 / 2 = 6 // остаток равен 0, пробуем делить еще раз на 2

6 / 2 = 3 // остаток равен 0, пробуем делить еще раз на 2

3 / 2 = 1,5 // остаток отличен от 0,

//рассматриваем следующее число, меньшее 12

3 / 3 = 1 // частное равно 1, алгоритм останавливает работу

Псевдокод последовательного алгоритма выглядит следующим образом:

1. for i = 1 to N
2.   number ← i;   
3.   for j = 2 to i
4.     if (number == 1) break; 
5.     r ← number % j;
6.     if (r == 0)
7.       number ← number / j;
8.       save_divisor(i, j);
9.       j ← j - 1;

В соответствии с приведенным псевдокодом может быть реализована простейшая последовательная версия алгоритма.

Последовательная реализация алгоритма

Начнем реализацию алгоритма с создания файла single.cpp. Для этого можно выполнить следующую команду:

-sh-4.1$ > single.cpp

Далее созданный файл можно редактировать любым привычным редактором. Один из редакторов с дружественным интерфейсом mcedit. Для редактирования файла необходимо выполнить команду:

-sh-4.1$ mcedit ./single.cpp

В результате откроется окно редактора, в котором можно разрабатывать программную реализацию алгоритма.

Начнем разработку программы с подключения необходимых заголовочных файлов и объявления констант.

#include <iostream>
#include "omp.h"

#include <vector>

using namespace std;

// Количество факторизуемых чисел
#define NUM_NUMBERS 100000
// Вектора используемые для хранения  
// простых сомножителей чисел 
vector<int> divisors[NUM_NUMBERS+1];

Далее объявим две вспомогательные функции, используемые при реализации алгоритма:

// Получение количества создаваемых потоков
int testThreadCount();
// Функция факторизации чисел
void factorization();

Реализация данных функций будет приведена позднее.

Далее разработаем главную функцию программы main.

int main()
{
  // Обявление переменных
  double time_s, time_f;
  int intel_th;
  
  // Вывод количества создаваемых потоков
  intel_th = testThreadCount(); 
  cout << "Intel CPU thread:\n" << intel_th << endl;

  // Проведение вычислительного эксперимента
  time_s = omp_get_wtime( );
  factorization();
  time_f = omp_get_wtime( );

  cout<< "Calculation time : " << (time_f - time_s) 
      << endl;

  // Вывод простых множителей произвольных 10 чисел
  for (int i = 0; i < 10; i++)
  {
    int randomIdx = 1 + rand() % NUM_NUMBERS;
    cout << randomIdx << ":\t";
    int size;
    size = static_cast<int>(divisors[randomIdx].size());
    for (int j = 0; j < size;j++)
    {
      cout << divisors[randomIdx][j] << "\t";
    }
    cout << endl;
  }
  return 0;
}

Ниже приведем код получения количества создаваемых потоков.

int testThreadCount() { 
  int thread_count; 
  #pragma omp parallel 
  { 
    #pragma omp single
      thread_count = omp_get_num_threads(); 
  } 
  return thread_count;
}

В финале разработаем код алгоритма факторизации чисел приведенный в виде псевдокода разделе 2.

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--;
      }
    }    
  }
}

Код готов.

Для проведения экспериментов в рамках вычислительных ресурсов МСЦ РАН необходимо вначале зарезервировать вычислительный узел. Сделать это можно с помощью команды salloc. Пример резервирования узла кластера представлен ниже:

-sh-4.1$ salloc -N 1 --gres=mic:1
salloc: Pending job allocation 9404
salloc: job 9404 queued and waiting for resources
salloc: job 9404 has been allocated resources
salloc: Granted job allocation 9404

Посмотреть имя выделенного хоста можно в переменной окружения SLURM_NODELIST.

-sh-4.1$  echo $SLURM_NODELIST
node196

Перейдем на выделенный хост.

-sh-4.1$ ssh $SLURM_NODELIST
-sh-4.1$ hostname
node196

Далее откомпилируем код и выполним его.

-sh-4.1$ icpc -O2 -openmp single.cpp –osingle
-sh-4.1$ ./single

На рис 8.1 приведен результат работы последовательной версии алгоритма.

Ниже, на рис 8.2 приведено время работы алгоритма:

Перенос вычислений на сопроцессор Intel Xeon Phi

В качестве следующего шага перенесем вычисления последовательного кода на сопроцессор Intel Xeon Phi. Для этого воспользуемся директивой #pragma offload target(mic:0).

  time_s = omp_get_wtime( );
#pragma offload target(mic:0)
  {
  factorization();
  }
  time_f = omp_get_wtime( );

Далее проведем попытку скомпилировать полученный код. Получим следующий вывод компилятора с ошибками:

./singleMIC.cpp(44): error: function "factorization" called in offload region must have been declared 
   with compatible "target" attribute
    factorization();

Intel Xeon Phi имеет свои операционную систему и окружение. Код, исполняемый на MIC, должен быть скомпилирован отдельно. В программной реализации алгоритма факторизации чисел не было указаний компилятору дополнительно скомпилировать для MIC функцию факторизации, что и привело к появлению ошибки. Чтобы исправить данную ошибку, необходимо объявление функций и сами функции обернуть директивами, как показано ниже:

#pragma offload_attribute(push, target(mic)) 
#include <iostream>
#include "omp.h"

#include <vector>

using namespace std;


#define NUM_NUMBERS 100000
vector<int> divisors[NUM_NUMBERS+1];


void factorization(int chunk);
int  testThreadCount();
#pragma offload_attribute(pop)

…

#pragma offload_attribute(push, target(mic)) 
int testThreadCount() { 
  int thread_count; 
  #pragma omp parallel 
  { 
    #pragma omp single
      thread_count = omp_get_num_threads(); 
  } 
  return thread_count;
}

void factorization() 
{…}
#pragma offload_attribute(pop)

Попробуем скомпилировать программу. Программа должна откомпилироваться без ошибок.

Для того чтобы убедится, что вычисления производятся на сопроцессоре, и узнать его параметры (количество создаваемых потоков), дополнительно модифицируем функцию main.

int main()
{
  double time_s, time_f;
  int intel_th, mic_th;
  
  intel_th = testThreadCount(); 
  cout << "Intel CPU thread:\n" << intel_th << endl;

  int number_of_coprocessors = _Offload_number_of_devices(); 

  if(number_of_coprocessors < 1)
  {
    cout << "for the program to need at least one Intel Xeon Phi coprocessor \n";
    return -1;
  }
  cout << "Intel Xeon Phi:\n"; 
  cout << "Number of coprocessors: " << number_of_coprocessors << endl;
  cout << "(used only the first coprocessor)" << endl;

#pragma offload target(mic:0)
  {
    mic_th = testThreadCount(); 
  }
  cout << "MIC thread:\n" << mic_th << endl;
  
  time_s = omp_get_wtime( );
#pragma offload target(mic:0)
  {
  factorization();
  }
  time_f = omp_get_wtime( );
  …
}

Откомпилируем и запустим программу. Результат выполнения программы представлен на рис 8.3.

Как вы думаете, почему в результате вычислений не отобразились факторы чисел?

Правильный ответ – память центрального процессора и сопроцессора не являются общими. Как следствие при объявлении глобальных данных, память под хранения данных выделяется как на центральном процессоре, так и на сопроцессоре. Изменение данных на сопроцессоре не влечет изменение данных на центральном процессоре.

Разработаем дополнительно две функции, которые позволят получить данные с сопроцессора.

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

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<int>(divisors[Idx].size());
  }
  size[i] = sum; 
}

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

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<int>(divisors[Idx].size());
    for (int j = 0; j < size;j++)
    {
      pn[k] = divisors[Idx][j];
      k++;
    }
  }
}

Модифицируем код функции main так, чтобы факторы чисел выводились корректно.

int main()
{
…
  time_s = omp_get_wtime( );
  #pragma offload target(mic:0)
  {
  factorization();
  }
  time_f = omp_get_wtime( );

  cout<< "Calculation time : " << (time_f - time_s) 
  << endl;

  // Получаем количество простых сомножителей
  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);
  }
  // Вывод простых сомножителей произвольных 10 чисел
  for (int i = 0; i < 10; i++)
  {
    cout << num[i] << ":\t";
    for (int j = countNum[i]; j < countNum[i + 1];j++)
    {
      cout << pn[j] << "\t";
    }
    cout << endl;
  }
  delete []pn;

  return 0;
}

Скомпилируем и выполним полученный код. На рис 8.4 приведен результат выполнения программы.

На рис 8.5 приведен график сравнения производительности кода, запущенного на центральном процессоре и на Intel Xeon Phi.

Как видно из графика, центральный процессор приблизительно в пятнадцать раз обогнал сопроцессор Intel Xeon Phi. Причина заключается в том, что ядра сопроцессора гораздо более простые (с точки зрения архитектуры) и обладают меньшей тактовой частотой, чем ядра центрального процессора. Основное преимущество Intel Xeon Phi в том, что ядер, пусть и простых, очень много. У сопроцессора Intel Xeon Phi 60 ядер против 8 центрального процессора. Также каждое ядро Intel Xeon Phi поддерживает четыре потока. Итого на ускорителе может выполняться 240 потоков. Следует учитывать, что для эффективного использования ядер сопроцессора необходимо, чтобы код был векторизован.

Параллельная реализация алгоритма

Для реализации параллельного алгоритма воспользуемся директивами OpenMP. Вначале произведем распараллеливание, используя статический планировщик. Затем, попробуем увеличить производительность за счет изменения планировщика.

Распределение вычислений с использованием статического планировщика

Простейший подход к распараллеливанию в задаче разложения чисел из диапазона от 1 до $$N$$ состоит в том, чтобы разделить множество факторизуемых чисел на равные части по числу потоков. На рис 8.6 показан пример распределения чисел при создании четырех потоков.

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

Модифицируем код факторизации с учетом выбранного способа распараллеливания.

void factorization() 
{
#pragma omp parallel for
  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--;
      }
    }    
  }
}

Скомпилируем и выполним код. На рис 8.7 приведен результат вычислений параллельного кода исполненного на ускорителе Intel Xeon Phi с применение статического планирования.

На рис 8.8 представлен график демонстрирующий ускорение параллельной реализации алгоритма.

Ускорение алгоритма факторизации чисел относительно последовательной версии исполненных на Intel Xeon Phi составило 47,2 раза. Результат можно считать неплохим, но далеким от идеала. Шестьдесят ядер могли обеспечить гораздо лучшее ускорение.

Что помешало большему ускорению?

Ответ простой, вычисления сильно разбалансированы и большое время тратится на синхронизацию потоков. Фактор для чисел первых потоков можно найти гораздо быстрее, чем для последних чисел.