Параллельное программирование в стандарте MPI. Баканов В.М - 55 стр.

UptoLike

ВУЗ: 

МИРЭА | Москва

Составители: 

Рубрика: 

5 Лабораторная работа 5. Умножение матриц –
последовательная и параллельные версии
Цель работы – уяснение принципов распределения данных по вычисли-
тельным узлам кластера, приобретение практических знаний и навыков в
создании MPI-программ реализации стандартных алгоритмов.
Теоретическая часть. Операции с матрицами большой (тысячи/сотни ты-
сяч) размерности являются основой многих численных методов (например,
МКЭ – метода конечных элементов). Только одна (далеко не самая крупная)
квадратная матрица размером 3000
×
3000 double-чисел требует для размеще-
ния 72 Мбайт ОП (предполагаем, что матрица является плотнозаполненной –
т.е. число нулевых элементов мало; иначе потребуются специальные методы
хранения ненулевых элементов). Ясно, что в этом случае программист обязан
распределить по процессорам кластера не только вычислительные процеду-
ры, но и данные (те же матрицы); использование для хранения матриц диско-
вой памяти катастрофически замедляет процедуру.
Одна из простейших матричных операций – умножение. Известно, что в
случае [C]=[A]
×
[B] значение элементов результирующей матрицы вычисля-
ется как (стандартный способ):
∑
=
=
=
NCAk
k
ba
c
kj
ikij
1
,
где i=1
÷
NRA – строки матриц [A] и [C],
j=1
÷
NCB – столбцы матриц [B] и [C],
k=1
÷
NCA – столбцы матрицы [A] и строки матрицы [B].
Хотя известны более эффективные алгоритмы (напр., умножение матриц
по Винограду и рекурсивный алгоритм Штрассена умножения квадратных
матриц), в дальнейшем используется стандартный (требующий N
3
операций
умножения и N
3
-N
2
сложений, где N – характерный размер матрицы).
Тривиальная программа
MM_SER.C
умножения матриц стандартным спо-
собом (используется последовательный вариант вычислений одним процес-
сором) приведена ниже:
// source code of MM_SER.C program
#include <stdio.h>
#include <sys/timeb.h> // for ftime
double f_time(void); /* define real time by ftime function */
#include “f_time.c”
#define NRA 3000 /* number of rows in matrix A */
#define NCA 3000 /* number of columns in matrix A */
#define NCB 10 /* number of columns in matrix B */ 
   5 Лабораторная работа 5. Умножение матриц –
     последовательная и параллельные версии

  Цель работы – уяснение принципов распределения данных по вычисли-
тельным узлам кластера, приобретение практических знаний и навыков в
создании MPI-программ реализации стандартных алгоритмов.

   Теоретическая часть. Операции с матрицами большой (тысячи/сотни ты-
сяч) размерности являются основой многих численных методов (например,
МКЭ – метода конечных элементов). Только одна (далеко не самая крупная)
квадратная матрица размером 3000 × 3000 double-чисел требует для размеще-
ния 72 Мбайт ОП (предполагаем, что матрица является плотнозаполненной –
т.е. число нулевых элементов мало; иначе потребуются специальные методы
хранения ненулевых элементов). Ясно, что в этом случае программист обязан
распределить по процессорам кластера не только вычислительные процеду-
ры, но и данные (те же матрицы); использование для хранения матриц диско-
вой памяти катастрофически замедляет процедуру.
   Одна из простейших матричных операций – умножение. Известно, что в
случае [C]=[A] × [B] значение элементов результирующей матрицы вычисля-
ется как (стандартный способ):
        k = NCA
   cij = ∑ aik bkj ,
         k =1



  где i=1 ÷ NRA – строки матриц [A] и [C],
      j=1 ÷ NCB – столбцы матриц [B] и [C],
      k=1 ÷ NCA – столбцы матрицы [A] и строки матрицы [B].

  Хотя известны более эффективные алгоритмы (напр., умножение матриц
по Винограду и рекурсивный алгоритм Штрассена умножения квадратных
                                                            3
матриц), в дальнейшем используется стандартный (требующий N операций
              3 2
умножения и N -N сложений, где N – характерный размер матрицы).
  Тривиальная программа MM_SER.C умножения матриц стандартным спо-
собом (используется последовательный вариант вычислений одним процес-
сором) приведена ниже:

// source code of MM_SER.C program
#include 

#include  // for ftime
double f_time(void); /* define real time by ftime function */
#include “f_time.c”

#define NRA 3000 /* number of rows in matrix A */
#define NCA 3000 /* number of columns in matrix A */
#define NCB 10   /* number of columns in matrix B */

Страницы