УДК 004.021

Сравнительный анализ эффективности применения технологий параллельного программирования

Самхарадзе Коба Кобаевич – студент Института инженерных технологий и естественных наук Белгородского государственного национального исследовательского университета.

Ерошенко Яна Борисовна – аспирант, старший преподаватель кафедры Математического и программного обеспечения информационных систем Белгородского государственного национального исследовательского университета.

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

Ключевые слова: Параллельные вычисления, параллелизм, распараллеливание по данным, распараллеливание по задачам, обработка данных, OpenMP, MPI, CUDA.

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

Развитие научно-технического прогресса, обусловленного практической потребностью на современном этапе, расширило список прикладных задач, для решения которых требуются компьютеры больших мощностей, способных выполнять огромное количество вычислительных операций в единицу времени, что уменьшает время выполнения расчетов [5, с. 4].

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

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

Эти области постоянно развиваются, что требует увеличения объема производимых расчетов из года в год. В этом случае применение высокопроизводительной техники с параллельной обработкой данных является наиболее эффективным средством вычисления, и каждый специалист данной области вынужден изучать параллельное программирование [12].

Вычислительная техника представляет собой «совокупность технических и математических средств, методов и приемов, используемых для механизации и автоматизации процессов вычислений и обработки информации» [1, с. 6].

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

Основные шаблоны программирования параллельного процесса содержат два базовых подхода к распараллеливанию: распараллеливание по данным (data parallel) и распараллеливание по задачам (message passing). В зависимости от того, как обрабатываются данные в вычислительном устройстве, выделяют 4 класса архитектуры: SISD, SIMD, MISD и MIMD [3, с. 14].

Основные технологии параллельного программирования делятся на два типа: для систем с разделенной памятью и для систем с общей памятью.

В системах с распределенной памятью каждый вычислительный узел не зависит от другого. Они характеризуются определенным механизмом межпроцессорного взаимодействия, как передача по сети сообщений. Для этих целей был разработан стандарт Message Passing Interface – MPI. Эта технология работает только с процессами, для взаимодействия между ними используется 2 механизма: попарное взаимодействие между 2-я процессами и коллективное взаимодействие между всеми процессами коммуникатора [2, с. 5].

В системах с общей памятью более эффективно использование не многопроцессорную программу, а многопоточную. Для этих целей общепринятым мировым стандартом является технология OpenMP (Open Multi-Processing). Программирование состоит из 3-х частей: использование переменных окружения, использование функций OpenMP и директивы OpenMP. Данная технология использует «вилочный» параллелизм [6, с. 45].

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

На сегодняшний день находит широкое применение технология CUDA (Compute Unified Device Architecture), предназначенная для программирования видеокарт и GPU. CUDA подразумевает разбиение исходной задачи на подзадачи, каждая из которых решается определенным набором нитей, взаимодействующих между собой.

GPU – это вычислительное устройство, являющееся сопроцессором к CPU, имеющее собственную память и выполняющее одновременно очень много нитей. Код состоит из последовательных и параллельных частей. Последовательные части кода выполняются на CPU, а параллельные – на GPU как ядра. Параллельная часть кода представляет собой большое количество нитей, группирующиеся в блоки фиксированного размера, которые, в свою очередь, объединяются в сеть блоков, где выполняется ядро. Каждая нить и блок имеют свой идентификатор, нити взаимодействуют между собой только в рамках одного блока [8].

Основными параметрами эффективности параллельных вычислительных систем являются: время выполнения, ускорение и масштабируемость (эффективность). Максимальное ускорение (S) параллельного алгоритма определяется по формуле 1, а эффективность параллельного алгоритма (E) – по формуле 2 [11]:

где T1 – время выполнения последовательного алгоритма; Tp – время выполнения параллельной части алгоритма; α – доля последовательных операций в алгоритме; p – количество одинаковых процессоров.

Эффективность применения той или иной технологии параллельного программирования проанализируем на примере вычисления минимальных полиномиальных сплайнов или сплайн-функции. Выбор минимального сплайна для исследования эффективности параллельных вычислений основан на его широком применении [7].

Сплайн-функция – это кусочно-полиномиальная функция, параметры которой находятся на определенном отрезке, который разбит на конечное число i-ых кусочков. Данная функция со всеми производными на всем отрезке непрерывна, а на каждом кусочке является полиномом m-ой степени [10, с. 96]. Если степень полинома m равна 1 или 2, то полиномиальный сплайн является минимальным. При m = 2 сплайн-функция определяется по формуле 3 [4, с. 272]:

где μ=(μ01,…,μm) – заданный вектор, у которого μ0= 1 .

Постановка задачи такова, что требуется вычислить полиномиальный сплайн минимальной степени m = 2 с помощью различных технологий параллельного программирования и проанализировать результаты расчетов по основным параметрам эффективности путем сравнения.

Для реализации параллельного алгоритма вычисления минимального полиномиального сплайна была выбрана интегрированная среда разработки MS Visual Studio 2010 и язык программирования С++, а в качестве технологической платформы для проведения вычислительных экспериментов выступили учебный кластере НИУ БелГУ, включающий 12 физических ядер Intel Xeon E5-2620 2.00 Ghz (24 потока) и вычислительные процессоры: Nvidia Tesla C2070 GPU и Nvidia GTX 650. В процессе вычисления к параллельному алгоритму был применен параллелизм по данным, то есть каждый процесс вычислял определенную часть сплайн-функции.

Последовательный алгоритм выполнялся одним потоком (листинг 1).

Листинг 1. Последовательный алгоритм.

float u[3] = { 1.0, 1.61516000, 0.95849584 };

for (int i = 4; i <= 8; i++) { ...

int size = 1 / h + 1;

float h = 0.5 * pow(10.0, -i);

float *spline = new float [size];

for (int j = 0; j < 3; j++)

for (int k = 0; k < size; k++)

spline[k] = splineW2(float(k * h + j), u);

delete [] spline; ...

}

Параллельный алгоритм OpenMP исполнялся с помощью директив parallel для задания параллельной области и for для распределения итераций цикла между различными нитями (листинг 2).

Листинг 2. Использование директив OpenMP.

for (int i = 4; i <= 8; i++) { ...

float *spline = new float[size];

for (int j = 0, k = 0; j < 3; j++) {

#pragma omp parallel for num_threads(threads) shared(spline,h,j,u) private(k)

for (k = 0; k < size; k++)

spline[k] = splineW2(float(k * h + j), u);

} ...

delete [] spline; ...

}

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

Листинг 3. Параллельный алгоритм MPI.

for (int i = 4; i <= 8; i++) { …

int *recvCounts = new int[procNum]; int *displs = new int[procNum];

// вычисление длин локальных массивов каждого процесса

for (int j = 0; j < procNum; j++) {

recvCounts[j] = size;

for (int k = 0; k < j; k++) recvCounts[j] -= recvCounts[k];

recvCounts[j] /= (procNum - j);

}

// вычисление смещения локальных массивов каждого процесса

for (int j = 0; j < procNum; j++) { displs[j] = 0;

for (int k = 0; k < j; k++) displs[j] += recvCounts[k];

}

float *localSpline = new float[recvCounts[rank]];

for (int j = 0; j < 3; j++) {

for (int k = 0; k < recvCounts[rank]; k++)

localSpline[k] = splineW2(float(k*h+j+h*displs[rank]), u);

}

MPI_Gatherv(localSpline, recvCounts[rank], MPI_FLOAT, spline, recvCounts, displs, MPI_FLOAT, 0, MPI_COMM_WORLD); ...

}

Реализации параллельного алгоритма CUDA сопровождалось выделением памяти GPU для расчета данных и вызовом функции-ядра для выполнения параллельных вычислений непосредственно на GPU (листинг 4).

Листинг 4. Параллельный алгоритм CUDA.

__device__ float splineW2(float t, float *u) { /* формула 3 */ }

__global__ void kernelCalcSpline(float*spline,int size,float h,int j,float*u) {

int i = blockIdx.x * blockDim.x + threadIdx.x;

if (i < size) spline[i] = splineW2(float(i * h + j), u);

}

for (int i = 4; i <= 8; i++) { ...

float *dev_spline, *dev_u;

cudaMalloc((void**)&dev_spline, sizeMemory);

cudaMalloc((void**)&dev_u, 3 * sizeof(float));

cudaMemcpy(dev_u, &u, 3 * sizeof(float), cudaMemcpyHostToDevice);

int sizeThread = 32; int sizeGridX = (size + sizeThread - 1) / sizeThread;

dim3 threads(sizeThread); dim3 grid(sizeGridX);

for (int j = 0; j < 3; j++) {

cudaMemset(dev_spline, 0, sizeMemory);

kernelCalcSpline<<<grid, threads>>>(dev_spline, size, h, j, dev_u);

}

cudaMemcpy(spline, dev_spline, sizeMemory, cudaMemcpyDeviceToHost); ...

cudaFree(dev_spline);

}

Для анализа эффективности параллельных алгоритмов OpenMP и MPI были определены их основные параметры с различным количеством произведенных вычислений при 8, 16 и 24 потоках (табл. 1).

Таблица 1. Параметры эффективности OpenMP и MPI.

Кол-во вычислений

Количество потоков OpenMP

1

8

16

24

T1, мс

T8, мс

S

E

T16, мс

S

E

T24, мс

S

E

60003

2,00

1,00

2,00

0,25

1,00

2,00

0,13

7,00

0,29

0,01

600003

30,00

5,00

6,00

0,75

4,00

7,50

0,47

2,00

15,00

0,63

6000003

220,00

39,00

5,64

0,71

28,00

7,86

0,49

13,00

16,92

0,71

60000000

1710,00

265,00

6,45

0,81

184,00

9,29

0,58

123,00

13,90

0,58

600000000

16800,00

2197,00

7,65

0,96

1506,00

11,16

0,70

1200,00

14,00

0,58

Кол-во вычислений

Количество процессов MPI

1

8

16

24

T1, мс

T8, мс

S

E

T16, мс

S

E

T24, мс

S

E

60003

2,00

0,92

2,18

0,27

1,76

1,14

0,07

1,27

1,58

0,07

600003

30,00

4,49

6,69

0,84

3,20

9,38

0,59

13,34

2,25

0,09

6000003

220,00

37,81

5,82

0,73

23,91

9,20

0,58

30,89

7,12

0,30

60000000

1710,00

326,82

5,23

0,65

211,98

8,07

0,50

158,93

10,76

0,45

600000000

16800,00

2849,65

5,90

0,74

1873,91

8,97

0,56

1414,19

11,88

0,49


Из таблицы 1 видно, что с увеличением потоков с 8 до 24:

- время выполнения параллельных алгоритмов сократилось почти в 2 раза, но в OpenMP потоки исполнялись быстрее, чем процессы в MPI (рис. 1);

Рисунок 1. Время выполнения процессов (потоков).

- ускорение параллельных алгоритмов OpenMP и MPI увеличивалось, причем первый ускорялся быстрее второго (рис. 2);

Рисунок 2. Динамика ускорения параллельных алгоритмов.

- эффективность параллельных алгоритмов снизилась, но эффективнее алгоритм OpenMP, причем чем меньше количество потоков, тем эффективность значительно выше (рис. 3).

Рисунок 3. Анализ эффективности параллельных алгоритмов.

Ввиду того, что количество процессов (потоков) в технологии CUDA значительно отличается от предыдущих, целесообразно анализ вычислений с использованием CUDA проводить на разных GPU (табл 2).

Таблица 2. Параметры эффективности CUDA.

Кол-во вычислений

INTEL Xeon

E5-2620

Количество потоков

GTX 650

Tesla C2070

1

384

448

T1, мс

T384, мс

S

E

T448, мс

S

E

60003

2,00

1,45

1,38

0,17

1,12

1,78

0,11

600003

30,00

6,46

4,64

0,58

1,46

20,49

1,28

6000003

220,00

59,93

3,67

0,46

6,52

33,75

2,11

60000000

1710,00

34,85

49,07

6,13

28,86

59,25

3,70

600000000

16800,00

332,62

50,51

6,31

272,48

61,66

3,85


Из таблицы 2 видно, что с увеличением количества вычислений наибольшее ускорение наблюдается на Tesla C2070, причем оно существует даже при малых данных (рис. 4), при этом время выполнения алгоритма и эффективность ниже, чем на GTX 650 (рис. 5, 6).

Рисунок 4. Параметры ускорения CUDA при различных GPU.

Можно заметить, что разница в ускорении на различных GPU становится незначительной при расчете большего количества вычислений.

Рисунок 5. Время выполнения на CUDA.

Рисунок 6. Эффективность параллельного алгоритма CUDA.

Таким образом, анализ применения технологий OpenMP и MPI показал, что при вычислении минимального полиномиального сплайна следует использовать технологию OpenMP, а при использовании технологии CUDA, если важна скорость выполнения расчетов, эффективным является применение GPU Tesla C2070. В этом случае графический процессор будет не полностью загружен, а затраты на такую видеокарту будут значительными. Если сравнивать вместе все три технологии, то лучше использовать CUDA.

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

Список литературы

  1. Айдинян А. Р., Аппаратные средства вычислительной техники [Текст]: учебник – М., Берлин: Директ-Медиа, 2016 г. – 125 с.
  2. Антонов А. С. Параллельное программирование с использованием технологии MPI [Текст]: учеб. пособие. – М.: Изд-во МГУ, 2004. – 71 с.
  3. Биллиг В. А. Параллельные вычисления и многопоточное программирование [Текст]: 2-е изд. исправленное. – М.: НОУ «ИНТУИТ», 2016. – 311 с.
  4. Бурова И. Г., Демьянович Ю. К. Минимальные сплайны и их приложения [Текст]: учебник. – СПб.: СПбГУ, 2010. – 364 с.
  5. Гергель В. П. Высокопроизводительные вычисления для многоядерных многопроцессорных систем [Текст]: учеб. пособие. – Нижний Новгород: Изд-во ННГУ им. Н. И. Лобачевского, 2010. – 421 с.
  6. Основы параллельного программирования с использованием технологий MPI и OpenMP [Текст]: учеб. пособие / Р. В. Жалнин, Е. Н. Панюшкина, Е. Е. Пескова, П. А. Шаманаев. – Саранск: Изд-во СВМО, 2013. – 78 с.
  7. Применение – сплайн [Электронный ресурс]. – Режим доступа: http://www.ngpedia.ru/id316280p1.html
  8. Программно-аппаратный стек CUDA. Иерархия памяти. Глобальная память [Электронный ресурс]. – Режим доступа: http://nvidia.esyr.name/files/presentations/0829_CUDA.pdf
  9. Старченко А.В., Берцун В.Н. Методы параллельных вычислений [Текст]: учеб. пособие – Томск: Изд-во Том. ун-та, 2013. – 223 с.
  10. Шарый С. П. Курс вычислительных методов [Текст]: учебник. – Новосибирск: ИВТ СО РАН, 2017. – 578 с.
  11. Эффективность и ускорение параллельных программ [Электронный ресурс]. – Режим доступа: https://mipt.ru/drec/upload/d52/lab2-arpgyfe27m6.pdf
  12. J. Sanders, E. Kandrot. CUDA by example: an introduction to general-purpose GPU programming [Electronic resource]. – Available at: http://developer.download.nvidia.com/books/cuda-by-example/cuda-by-example-sample.pdf

Интересная статья? Поделись ей с другими: