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

http://www.software.unn.ac.ru/ccam/?doc=73

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

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

-       общий подход (как и в случае многопроцессорных вычислительных системах с распределенной памятью) на основе технологии передачи сообщений MPI;

-       подход, основанный на использовании возможностей стандарта OpenMP.

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

Программный интерфейс приложений (API) OpenMP (см., например, Chandra, R. аnd etc. (2000)) обеспечивает поддержку программирования в модели общей памяти на языках C/C++ и Fortran и представляет собой достаточно простой способ для разработки параллельных программ, являющихся переносимыми между различными типами мультипроцессоров и операционных систем.

Для проведения экспериментов использовались двух- и четырех- процессорные сервера вычислительного кластера Нижегородского университета. Разработка программ осуществлялась с помощью среды разработки MicrosoftÒ Visual Studio 6.0 с компиляторами Microsoft 32-bit C/C++ Optimizing Compiler и IntelÒ C++ Compiler 5.0.

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

·        последовательная программа, разработанная на основе стандартного алгоритма (см. п. 5 раздела 2);

·        параллельная программа, полученная из последовательного варианта путем добавления соответствующих директив OpenMP; следует отметить, что выполнение этой работы не потребовало значительных усилий; главное изменение исходной программы свелось к вставке директивы распараллеливания перед основными циклами умножения:

#pragma omp for private(i,j,k) nowait
for (i=0;i<N; i++)
  for (j=0; j<N; j++)
    for (k=0; k<N; k++)
      C[i][j]+=A[i][k]*B[k][j];

·        параллельная программа, использующая для организации взаимодействия процессоров механизм передачи сообщений MPI; для распределения элементов перемножаемых матриц между процессорами была задействована ленточная схема организации параллельных матричных вычислений (см., например, Kumar and etc. (1994)), когда на каждый процессор пересылается одновременно  строк матрицы A и  столбцов матрицы B (значение  может быть принято равным , где p есть число имеющихся в системе процессоров); для частного случая p=2, между процессорами следует разделять только одну матрицу; в этом случае, например, на одном процессоре осуществляется перемножение первых N/2 строк матрицы A и всех столбцов матрицы B; на другом процессоре матрица B перемножается на остальные N/2 строк матрицы A; основная вычислительная часть этой программы для случая двух процессоров имеет вид

if (rank == 0) {
  MPI_Send(A[N/2], N*N/2 , MPI_DOUBLE, 1, tag,MPI_COMM_WORLD);
  MPI_Send(B, N*N, MPI_DOUBLE, 1, tag,MPI_COMM_WORLD);
}
else {
  MPI_Recv(A[N/2],N*N/2,MPI_DOUBLE,0,tag,MPI_COMM_WORLD,&status);
  MPI_Recv(B, N*N, MPI_DOUBLE, 0, tag, MPI_COMM_WORLD,&status);
}

MPI_Barrier(MPI_COMM_WORLD);

time_calc = MPI_Wtime();
if (rank == 0){
  start = 0;    finish = N / 2;
}
else {
  start = N / 2; finish = N;
}
for (i = start; i<finish; i++){
  for (j = 0; j<N; j++){
    C[i][j] = 0.0;
    for (k = 0; k< N; k++
      C[i][j] = C[i][j]+ A[i][k] * B[k][j];
 }
}
MPI_Barrier(MPI_COMM_WORLD);

if (rank == 0)
MPI_Recv(C[N/2],N*N/2,MPI_DOUBLE,1,tag,MPI_COMM_WORLD,&status);
else
  MPI_Send(C[N/2], N*N/2 , MPI_DOUBLE, 0, tag, MPI_COMM_WORLD);
time_finish = MPI_Wtime();

Результаты экспериментов для двухпроцессорного (2 процессора Intel Pentium III Xeon 1000 MHz, 256 Mb RAM) и четырехпроцессорного серверов (4 процессора Intel Pentium III Xeon 700 MHz, 512 Mb RAM) в числовой форме сведены в таблицах 3.1 и 3.2 соответственно. В этой таблице приведены данные по времени выполнении операции перемножения матриц разного порядка (от 300 до 2100) для всех трех вариантов программной реализации вычислений. Кроме того, для параллельных программ приведены показатели получаемого ускорения времени решения задачи по сравнению с временем работы последовательной программы

Таблица 3.1. Сравнение времени выполнения последовательного варианта программы с вариантами OpenMP и MPI для 2-процессорного сервера

Порядок матрицы: (N)

Время Tпосл
(последовательный
алгоритм)

OpenMP

MPI

Время Tпар

Ускорение S

Время T

Ускорение S

300

0.42

0.39

1.08

0.39

1.07

600

4.69

3.55

1.32

3.85

1.22

900

16.20

12.05

1.34

14.17

1.14

1200

38.67

30.00

1.29

33.72

1.15

1500

76.56

58.20

1.32

60.19

1.27

1800

150.08

108.42

1.38

154.73

0.97

2100

258.09

171.75

1.50

177.03

1.46

Рис. 3.1. Ускорение матричного умножения при использовании параллельных вычислений

 

Для наглядности результаты вычислительных экспериментов представлены также на рис. 3.1 и 3.2 в графической форме в виде графиков коэффициентов ускорения процесса решения задачи при использовании параллельных вычислений.

 

Таблица 3.2. Сравнение времени выполнения последовательного варианта программы с вариантами OpenMP и MPI для 4-процессорного сервера

 

Порядок матрицы: (N)

Время Tпосл
(последовательный
алгоритм)

OpenMP

MPI

Время Tпар

Ускорение S

Время T

Ускорение S

300

0.36

0.17

2.09

0.32

1.14

600

6.66

3.78

1.76

5.61

1.19

900

22.92

12.70

1.80

20.01

1.15

1200

54.53

30.30

1.80

48.19

1.13

1500

107.91

59.67

1.81

93.27

1.16

1800

188.61

103.81

1.82

164.45

1.15

2000

262.09

142.73

1.84

226.45

1.16

Рис. 3.2. Ускорение матричного умножения при использовании параллельных вычислений на 4-процессорном сервере

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

Для оценки подобного подхода были выполнены вычислительные эксперименты с использованием двух 2-процессорных серверов кластера. Для организации параллельных вычислений были разработаны два варианта программ для ленточного алгоритма перемножения матриц:

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

-     программа с использованием интерфейса MPI и средств распараллеливания OPenMP; при выполнении этого варианта программы порождались 2 параллельных процесса (по одному процессу на каждый двухпроцессорный сервер), далее на каждом сервере для процессов средствами OpenMP создавались два параллельных потока (по одному на каждый процессор).

Результаты выполненных экспериментов приведены в таблице 3.3 и представлены в графическом виде на рис. 3.3. Как следует из приведенных данных, комбинированный вариант параллельной программы имеет заметное преимущество по эффективности в сравнении с программой, разработанной только с использованием интерфейса MPI.

Таблица 3.3. Сравнение времени выполнения MPI и MPI+OpenMP вариантов программы для двух 2-процессорных серверов