Паралельне виконання операцій множення матриць

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

СПИСОК ЛІТЕРАТУРИ.

1. Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж, 1999
2. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб: БХВ-Петербург, 2002.
3. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. М.:Мир, 1991.
4. Программирование на параллельных вычислительных системах: Пер с англ./Под ред. Р.Бэбба.М.:Мир, 1991.
5. Бройнль Т. Паралельне програмування: Початковий курс: Навчальний посібник. – К.:Вища школа.,1997.
6. Воеводин В.В. Математические основы параллельных вычислений.- М.: Изд-во МГУ, 1991.
7. Векторизация программ: теория, методы, реализация: Пер. с англ. и нем. /Под ред. Г.Д.Чинина. - М:. Мир, 1991.
8. Організація паралельних обчислень : Навчальний посібник з дисципліни “Паралельні та розподілені обчислення” для студентів базового напрямку 6.0915 "Комп'ютерна інженерія" / Укладачі: Є. Ваврук, О. Лашко – Львів: Національний університет “Львівська політехніка”, 2007, 70 с.
9. http://www.parallel.ru – Інформаційно-аналітичний центр з паралельних обчислень.
10. http://www.csa.ru – Інститут високопродуктивних обчислень і баз даних.
11. http://www.hpc.nw.ru – Високопродуктивні обчислення.

 

 

 

 

 

 

 

 

 

 

Додаток А

Текст програми на C++ з використанням бібліотеки МРІ:

#include <stdio.h>

#include <iostream>

#include <stdlib.h>

#include <iostream>

#include "mpi.h"

#include <Windows.h>

#include <conio.h>

 

using namespace std;

 

const int route=0;

const int circle[] = {0,4,6,1,3,7,2,5};

const int procNumber=8; 

const int N1=190;

const int N2=88;

const int N3=149;

int procRank;

const int root=0;

MPI_Status Status;

struct A{

int row;

int n1;

int n2;

double arr[N1/8+N1][N2];

};

struct B{

int col;

int n2;

int n3;

double arr[N2][N3/8+N3];

};

struct R{

int n1;

int n3;

double arr[N1/8+N1][N3];

};

double matrixA[N1][N2]={0};

double matrixB[N2][N3]={0};

double Res[N1][N3]={0};

A subA[procNumber];

B subB[procNumber];

A procA;

B procB;

B procBtmp;

R procRes;

R result[procNumber];

int NextProc;

int PrevProc;

int procSize;

//Збір

void DataReplication(){

if(procRank==7||procRank==5||procRank==1||procRank==4){

MPI_Send(&procRes,sizeof(procRes),MPI_BYTE,root,0,MPI_COMM_WORLD);

if(procRank==1){

MPI_Recv(&procRes,sizeof(procRes),MPI_BYTE,6,0,MPI_COMM_WORLD,&Status);

MPI_Send(&procRes,sizeof(procRes),MPI_BYTE,root,0,MPI_COMM_WORLD);

}

if(procRank==7){

MPI_Recv(&procRes,sizeof(procRes),MPI_BYTE,3,0,MPI_COMM_WORLD,&Status);

MPI_Send(&procRes,sizeof(procRes),MPI_BYTE,root,0,MPI_COMM_WORLD);

}

if(procRank==5){

MPI_Recv(&procRes,sizeof(procRes),MPI_BYTE,2,0,MPI_COMM_WORLD,&Status);

MPI_Send(&procRes,sizeof(procRes),MPI_BYTE,root,0,MPI_COMM_WORLD);

}

}

if(procRank==2)MPI_Send(&procRes,sizeof(procRes),MPI_BYTE,5,0,MPI_COMM_WORLD);

if(procRank==6)MPI_Send(&procRes,sizeof(procRes),MPI_BYTE,1,0,MPI_COMM_WORLD);

if(procRank==3)MPI_Send(&procRes,sizeof(procRes),MPI_BYTE,7,0,MPI_COMM_WORLD);

if(procRank==root){

result[root]=procRes;

MPI_Recv(&result[7],sizeof(procRes),MPI_BYTE,7,0,MPI_COMM_WORLD,&Status);

MPI_Recv(&result[5],sizeof(procRes),MPI_BYTE,5,0,MPI_COMM_WORLD,&Status);

MPI_Recv(&result[1],sizeof(procRes),MPI_BYTE,1,0,MPI_COMM_WORLD,&Status);

MPI_Recv(&result[4],sizeof(procRes),MPI_BYTE,4,0,MPI_COMM_WORLD,&Status);

MPI_Recv(&result[2],sizeof(procRes),MPI_BYTE,5,0,MPI_COMM_WORLD,&Status);

MPI_Recv(&result[6],sizeof(procRes),MPI_BYTE,1,0,MPI_COMM_WORLD,&Status);

MPI_Recv(&result[3],sizeof(procRes),MPI_BYTE,7,0,MPI_COMM_WORLD,&Status);

}

}

 

//початкова розсилка

void DataDistribution(){

if(procRank==root){ 

procA = subA[root];

procB = subB[root];

for(int i=0;i<procNumber;i++)

if(i!=root){

MPI_Send(&subA[circle[i]],sizeof(subA[circle[i]]),MPI_BYTE,circle[i],0,MPI_COMM_WORLD);

MPI_Send(&subB[circle[i]],sizeof(subB[circle[i]]),MPI_BYTE,circle[i],0,MPI_COMM_WORLD);

}

}

MPI_Status Status; 

if(procRank!=root){

MPI_Recv(&procA,sizeof(procA),MPI_BYTE,root,0,MPI_COMM_WORLD,&Status);

MPI_Recv(&procB,sizeof(procB),MPI_BYTE,root,0,MPI_COMM_WORLD,&Status);

}

}

//пересилка підматриці і перемноження

void mull(){

for(int i=0;i<procA.n1;i++)

for(int j=0;j<procB.n3;j++)

for(int k=0;k<procA.n2;k++)

procRes.arr[i][j+procB.col]+=procA.arr[i][k]*procB.arr[k][j];

}

void DataSend(){

procRes.n1=procA.n1;

procRes.n3=N3;

//mull();

for(int k=0;k<procNumber;k++){

for(int i=0;i<procNumber;i++){

if(procRank==circle[i]){ 

if( i % 2==0 ) {

MPI_Send(&procB,sizeof(B),MPI_BYTE,circle[(i+1)%procSize],0,MPI_COMM_WORLD);

MPI_Recv(&procBtmp,sizeof(B),MPI_BYTE,circle[(i+procSize-1)%procSize],0,MPI_COMM_WORLD,&Status);

procB=procBtmp;

} else {

MPI_Recv(&procBtmp,sizeof(B),MPI_BYTE,circle[(i-1)%procSize],0,MPI_COMM_WORLD,&Status);

MPI_Send(&procB,sizeof(B),MPI_BYTE,circle[(i+1)%procSize],0,MPI_COMM_WORLD);

procB=procBtmp;

} 

}

}

mull();

}

}

 

void SetRank()

{

if(procRank==0)

{

NextProc = 4;

PrevProc = 5;

}

if(procRank==1)

{

NextProc = 3;

PrevProc = 6;

}

if(procRank==2)

{

NextProc = 5;

PrevProc = 7;

}

if(procRank==3)

{

NextProc = 7;

PrevProc = 1;

}

if(procRank==4)

{

NextProc = 6;

PrevProc = 0;

}

if(procRank==5)

{

NextProc = 0;

PrevProc = 2;

}

if(procRank==6)

{

NextProc = 1;

PrevProc = 4;

}

if(procRank==7)

{

NextProc = 2;

PrevProc = 3;

}

}

 

int main(int argc, char* argv[])

{

MPI_Init(&argc, &argv);

MPI_Comm_rank(MPI_COMM_WORLD,&procRank);

MPI_Comm_size(MPI_COMM_WORLD,&procSize);

if(procSize!=8){

cout<<"Must be 8 process"<<endl;

MPI_Finalize();

return 1;

}

if(procRank==root){

//заповнення А

for(int i=0;i<N1;i++)

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

matrixA[i][j]=rand()%9+1;

cout<<"Matrix A"<<endl;

for(int i=0;i<N1;i++){

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

cout<<matrixA[i][j]<<" "; 

cout<<endl;  

}

 

//заповнення В

for(int i=0;i<N2;i++)

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

matrixB[i][j]=rand()%9+1;

cout<<endl<<"Matrix B"<<endl;  

for(int i=0;i<N2;i++){

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

cout<<matrixB[i][j]<<" "; 

cout<<endl;  

}

 

//перемноження матриць

for(int i=0;i<N1;i++)

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

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

Res[i][j]+=matrixA[i][k]*matrixB[k][j];

cout<<endl<<"Result"<<endl;  

for(int i=0;i<N1;i++){

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

cout<<Res[i][j]<<" "; 

cout<<endl;  

}

//розбиття на  підматриці

//А

int rowsSum=0;

int restRows = N1;

int restProc = procNumber;

for(int i=0;i<procNumber;i++)

{   

subA[i].row=rowsSum;

subA[i].n1 = restRows/restProc;

subA[i].n2 = N2;

for (int k=0;k<subA[i].n1;k++)

for(int j=0;j<subA[i].n2;j++)

subA[i].arr[k][j] = matrixA[k+rowsSum][j];

rowsSum+=subA[i].n1;

restRows -= restRows/restProc;

restProc--;

}

//В

rowsSum=0;

restProc = procNumber;

restRows = N3;

for(int i=0;i<procNumber;i++)

{

subB[i].col = rowsSum;

subB[i].n2 = N2;

subB[i].n3 = restRows/restProc;

for (int k= 0;k<subB[i].n2;k++)

for(int j=0;j<subB[i].n3;j++)

subB[i].arr[k][j] = matrixB[k][j+rowsSum];

rowsSum+=subB[i].n3;

restRows -= restRows/restProc;

restProc--;

}

}

//cout<<"SetRank"<<endl;

SetRank();

//cout<<"DataDistribution()"<<endl;

DataDistribution();

DataSend();

//cout<<"DataReplication()"<<endl;

DataReplication();

 

if(procRank==root){ 

cout<<endl<<"Paralel rez"<<endl;  

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

for(int i=0;i<result[k].n1;i++){

for(int j=0;j<result[k].n3;j++)

cout<<result[k].arr[i][j]<<" "; 

cout<<endl;  

}

}

MPI_Finalize();

return 0;

}