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

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

-       общий подход (как и в случае многопроцессорных вычислительных системах с распределенной памятью) на основе технологии передачи сообщений 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-процессорных серверов