Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






Программа умножения матрицы на вектор



Рассмотрим задачу вычисления произведения матрицы на вектор, которая естественным образом обобщается на задачу умножения матриц. Cоответствующая программа представлена ниже. Для наглядности единая программа матрично-векторного умножения разбита на три части: общую часть, код главного процесса и код подчиненного процесса.

В общей части программы описываются основные объекты задачи: матрица А, вектор b, результирующий вектор с, определяется число процессов (не меньше двух). Задача разбивается на две части: главный процесс (master) и подчиненные процессы.

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

 

program main

use mpi

integer MAX_ROWS, MAX_COLS, rows, cols

parameter (MAX_ROWS = 1000, MAX_COLS = 1000)

 

! матрица А, вектор b, результирующий вектор с

 

double precision a(MAX_ROWS,MAX_COLS), b(MAX_COLS), c(MAX_ROWS)

double precision buffer (MAX_COLS), ans

integer myid, master, numprocs, ierr, status (MPI_STATUS_SIZE)

integer i, j, numsent, sender, anstype, row

call MPI_INIT( ierr )

call MPI_COMM_RANK( MPI_COMM_WORLD, myid, ierr )

call MPI_COMM_SIZE( MPI_COMM_WORLD, numprocs, ierr )

 

! главный процесс – master

 

master = 0

 

! количество строк и столбцов матрицы А

 

rows = 10

cols = 100

if ( myid .eq. master ) then

 

! код главного процесса

 

else

 

! код подчиненного процесса

 

endif

call MPI_FINALIZE(ierr)

stop

end

 

Рис. 5.3. Программа умножения матрицы на вектор: общая часть

 

Код главного процесса представлен на рис. 5.4. Сначала главный процесс передает вектор b в каждый подчиненный процесс. Затем главный процесс пересылает одну строку матрицы A в каждый подчиненный процесс. Главный процесс, получая результат от очередного подчиненного процесса, передает ему новую работу. Цикл заканчивается, когда все строки будут розданы и от каждого подчиненного процесса получен результат.

 

! инициализация А и b

do 20 j = 1, cols

b(j) = j

do 10 i = 1, rows

a(i,j) = i

10 continue

20 continue

numsent = 0

! посылка b каждому подчиненному процессу

call MPI_BCAST(b, cols, MPI_DOUBLE_PRECISION, master,

MPI_COMM_WORLD, ierr)

! посылка строки каждому подчиненному процессу; в TAG – номер строки = i



do 40 i = 1,min(numprocs-l, rows)

do 30 j = I, cols

buffer(j) = a(i,j)

30 continue

call MPI_SEND(buffer, cols, MPI_DOUBLE_PRECISION, i, i,

MPI_COMM_WORLD, ierr)

numsent = numsent + l

40 continue

! прием результата от подчиненного процесса

do 70 i = 1, rows

! MPI_ANY_TAG – указывает, что принимается любая строка

call MPI_RECV(ans, 1, MPI_DOUBLE_PRECISION, MPI_ANY_SOURCE,

MPI_ANY_TAG, MPI_COMM_WORLD, status, ierr)

sender = status (MPI_SOURCE)

anstype = status (MPI_TAG)

! определяем номер строки

c(anstype) = ans

if (numsent .lt. rows) then

! посылка следующей строки

do 50 j = 1, cols

buffer(j) = a(numsent+l, j)

50 continue

call MPI_SEND (buffer, cols, MPI_DOUBLE_PRECISION, sender,

numsent+l, MPI_COMM_WORLD, ierr)

numsent = numsent+l

else

! посылка признака конца работы

call MPI_SEND(MPI_BOTTQM, 0, MPI_DOUBLE_PRECISION,sender,

0, MPI_COMM_WORLD, ierr)

endif

70 continue

Рис. 5.4. Программа для умножения матрицы на вектор: код главного процесса

 

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

Подчиненные процессы посылают результаты в главный процесс и параметр MPI_ANY_TAG в операции приема главного процесса указывает, что главный процесс принимает строки в любой последовательности. Параметр status обеспечивает информацию, относящуюся к полученному сообщению. В языке Fortran это – массив целых чисел размера MPI_STATUS_SIZE. Аргумент SOURCE содержит номер процесса, который послал сообщение, по этому адресу главный процесс будет пересылать новую работу. Аргумент TAG хранит номер обработанной строки, что обеспечивает правильное размещение полученного результата. После того как главной процесс разослал все строки матрицы А, на запросы подчиненных процессов он отвечает сообщением с отметкой 0. На рис. 5.5. представлена программа подчиненного процесса.



! прием вектора b всеми подчиненными процессами

call MPI_BCAST(b, cols, MPI_DOUBLE_PRECISION, master,

MPI_COMM_WORLD, ierr)

! выход, если процессов больше количества строк матрицы

if (numprocs .gt. rows) goto 200

! прием строки матрицы

90 call MPI_RECV(buffer, cols, MPI_DOUBLE_PRECISION, master,

MPI_ANY_TAG, MPI_COMM_WORLD, status, ierr)

if (status (MPI_TAG) .eq. 0) then go to 200

! конец работы__

else

row = status (MPI_TAG)

! номер полученной строки

ans = 0.0

do 100 i = 1, cols

! скалярное произведение векторов

ans = ans+buffer(i)*b(i)

100 continue

! передача результата головному процессу

call MPI_SEND(ans,1,MPI_DOUBLE_PRECISION,master,row,

MPI_COMM_WORLD, ierr)

go to 90

! цикл для приема следующей строки матрицы

endif

200 continue

 

Рис. 5.5. Программа для матрично-векторного умножения: подчиненный процесс

Каждый подчиненный процесс получает вектор b. Затем организуется цикл, состоящий в том, что подчиненный процесс получает очередную строку матрицы А, формирует скалярное произведение строки и вектора b, посылает результат главному процессу, получает новую строку и так далее.

 

3. Задания и упражнения:

3.1. Напишите и отладьте программу умножения матрицы на вектор.

3.2. Элементы матрицы и вектора должны определяться по формулам

 

,

 

, ,

 

где - номер варианта, - размерность матрицы.

 

3.3. Заполните таблицу:

 

Размер Последовательный алгоритм Параллельный алгоритм
2 процесса 4 процесса
Время Ускорение Время Ускорение
         
         
         
         
         
         

 

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

 


Лабораторная работа 6.

Тема: Разработка параллельного умножения матриц, блочные схемы распределения данных (алгоритмы Фокса и Кеннона). Оценка эффективности параллельного алгоритма.

 

Операция умножения матриц является одной из основных задач матричных вычислений. В данном разделе рассматриваются несколько разных параллельных алгоритмов для выполнения этой операции. Один из них основан на ленточной схеме разделения данных. Другие два метода основаны на блочной схеме разделения - это широко известные алгоритмы Фокса (Fox) и Кэннона (Cannon).

 

Постановка задачи.

 

Умножение матрицы A размера n×m и матрицы B размера m×l приводит к получению матрицы С размера n×l, каждый элемент которой определяется в соответствии с выражением

 

, , .

 

Этот алгоритм предполагает выполнение m×n×l операций умножения и столько же операций сложения элементов исходных матриц. При умножении квадратных матриц размера n количество выполненных операций имеет порядок .

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

double MatrixA[Size][Size];

double MatrixB[Size][Size];

double MatrixC[Size][Size];

int i,j,k;

...

for (i=0; i<Size; i++){

for (j=0; j<Size; j++){

MatrixC[i][j] = 0;

for (k=0; k<Size; k++){

MatrixC[i][j] = MatrixC[i][j] + MatrixA[i][k]*MatrixB[k][j];

}

}

}

 

Рисунок 6.1 – Последовательный алгоритм умножения матриц.


Эта страница нарушает авторские права

allrefrs.ru - 2019 год. Все права принадлежат их авторам!