TPV1

Министерство образования и науки, молодежи и спорта Украины
Севастопольский национальный технический университет
Кафедра ИС
Лабораторная работа №1
Изучение понятий независимости операций (блоков) в последовательных программах. Исследования метода приведения программы к полной параллельной форме при распараллеливании последовательных программ
Выполнил: ст. гр. И-42д
Сычев П.Ю
Проверил: Кротов К.В.
Севастополь
2012
ЦЕЛЬ РАБОТЫ: изучить понятие независимости операций (блоков) в программе, исследовать метод распараллеливания программ путем их приведения к полной параллельной форме.
Умножение матриц:
c1,1 = a1,1xb1,1+a1,2xb2,1+a1,3xb3,1
c1,2 = a1,1xb1,2+a1,2xb2,2+a1,3xb3,2
c1,3 = a1,1xb1,3+a1,2xb2,3+a1,3xb3,3
c2,1 = a2,1xb1,1+a2,2xb2,1+a2,3xb3,1
c2,2 = a2,1xb1,2+a2,2xb2,2+a2,3xb3,2
c2,3 = a2,1xb1,3+a2,2xb2,3+a2,3xb3,3
c3,1 = a3,1xb1,1+a3,2xb2,1+a3,3xb3,1
c3,2 = a3,1xb1,2+a3,2xb2,2+a3,3xb3,2
c3,3 = a3,1xb1,3+a3,2xb2,3+a3,3xb3,3
S1 - a11xb11S5 - a1,1xb1,2S9 - a1,1xb1,3
S2 - a12xb21S6 - a1, 2xb2,2S10 - a1,2xb2,3
S3 - a13xb31S7 - a1,3xb3,2S11 - a1,3xb3,3
S4 - S1 + S2 + S3S8 - S4 + S5 + S6S12 - S9 + S10 + S11
S13 - a2,1xb1,1S17 - a2,1xb1,2S21 - a2,1xb1,3
S14 - a2,2xb2,1S18 - a2,2xb2,2S22 - a2,2xb2,3
S15 - a2,3xb3,1S19 - a2,3xb3,2S23 - a2,3xb3,3
S16 - S13 + S14 + S15S20 - S17 + S18 + S19S24 - S21 + S22 + S23
S25 - a3,1xb1,1S29 - a3,1xb1,2S33 - a3,1xb1,3
S26 - a3,2xb2,1S30 - a3,2xb2,2S34 - a3,2xb2,3
S27 - a3,3xb3,1S31 - a3,3xb3,2S35 - a3,3xb3,3
S28 - S25 + S26 + S27S32 - S29 + S30 + S31S36 - S33 + S34 + S35
S37 - вывод результата
Определим зависимости между операторами (на примере одного элемента матрицы)
C(S1)R(S4) = a11xb11, следовательно S4 находится в сильной зависимости от S1
C(S2)R(S4) = a12xb21 следовательно S4 находится в сильной зависимости от S2
C(S3)R(S4) = a13xb31, следовательно S4 находится в сильной зависимости от S3
C(S4)R(S37) = c1,1 , следовательно S37 находится в сильной зависимости от S4
S1 -> S4; S2 -> S4; S3 -> S4; S4 -> S37;
Для остальных элементов зависимости определяются аналогично
Проверка приводимости к ППФ
1. S1 и S5 - независимы;
2. Между ними имеется промежуточный оператор S4;
3. N1(S1, S5) = { S37} P(S4) = {S37}
N2(S1,S5) = {S4, S8} S4 N2
N1(S1, S5) P(S4) S1S2S3S4S11110S21110S31110S40001 S1 Y1 Y1
S2 S4 S3 S4
S5 - a11xb12
S6 - a12xb22
S7 - a13xb32
S8 - S5 + S6 + S7
S9 - a11xb13
S5 -> S8; S6 -> S8; S7 -> S8; S8 -> S37;
Проверка приводимости к ППФ
1. S5 и S9 - независимы;
2. Между ними имеется промежуточный оператор S6;
3. N1(S5, S9) = { S37} P(S8) = {S37}
N2(S5,S9) = {S8, S12} S8 N2
N1(S5, S9) P(S6) S5 Y2 Y2
S6 S8 S7 S8
S5S6S7S8S51110S61110S71110S80001
S9 - a11xb13
S10 - a12xb23
S11 - a13xb33
S12 - S9 + S10 + S11
S13 - a21xb11
S9 -> S12; S10 -> S12; S11 -> S12; S12 -> S37;
Проверка приводимости к ППФ
1. S9 и S13 - независимы;
2. Между ними имеется промежуточный оператор S12;
3. N1(S9, S13) = { S37} P(S10) = {S37}
N2(S9,S13) = {S12, S16} S10 N2
N1(S5, S9) P(S6) S9 Y3 Y3
S10 S12 S11 S12
S9S10S11S12S91110S101110S111110S120001
S13S14S15S16S131110S141110S151110S160001 S13 Y4 Y4
S14 S16 S15 S16
S17S18S19S20S171110S181110S191110S200001
S17 Y5 Y5
S18 S20 S19 S20
S21S22S23S24S211110S221110S231110S240001
S21 Y6 Y6
S22 S20 S23 S24
S25S26S27S28S251110S261110S271110S280001
S25 Y7 Y7
S26 S28 S27 S28
S29S30S31S32S291110S301110S311110S320001
S29 Y8 Y8
S30 S32 S31 S32
S33S34S35S36S331110S341110S351110S360001
S33 Y9 Y9
S34 S36 S35 S36
Y1 Y10 Y10
Y2 S37
Y3
Y4
Y5
Y6
Y7
Y8
Y9
S37
Y1Y2Y3Y4Y5Y6Y7Y8Y9S37Y11111111110Y11111111110Y11111111110Y11111111110Y11111111110Y11111111110Y11111111110Y11111111110Y11111111110S370000000001
Рисунок 1 - Представление ППФ
Код программы
#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include "mpi.h"
using namespace std;
int ranked;
int a[3][3] = {{1, 2, 3},
{4, 5, 6},
{7, 8, 9}},
b[3][3] = {{1, 2, 3},
{4, 5, 6},
{7, 8, 9}};
int pairs [2][27];
int main(int argc, char* argv[])
{
int result[3][3];
MPI_Init(&argc, &argv);
MPI_Status status;
MPI_Comm_rank(MPI_COMM_WORLD,&ranked);
int numprocs;
MPI_Group sums_grp, wrld_grp;
MPI_Comm sums_comm;
int ranks[10];
for (int i=28; i<=37; i++)
ranks[i-28]=i;
MPI_Comm_group(MPI_COMM_WORLD, &wrld_grp);
MPI_Group_incl(wrld_grp, 10, ranks, &sums_grp);
MPI_Comm_create(MPI_COMM_WORLD, sums_grp, &sums_comm);
int count=0;
int mult;
int buf[2];
int d;
if (ranked==0)
{
for (int i=0; i<3; i++)//делим на пары нашу матрицу
for (int j=0; j<3; j++)
for (int k=0; k<3; k++)
{
pairs[0][count]=a[j][i];
pairs[1][count]=b[i][k];
cout<<pairs[0][count]<<" ";
cout<<pairs[1][count]<<endl;
count++;
}
for (int i=0; i<27; i++)//выделям необходимую пару и отправляем на умножение
{
buf[0]=pairs[0][i];
buf[1]=pairs[1][i];
MPI_Send(&buf, 2, MPI_INT, i+1, 99, MPI_COMM_WORLD);
}
}
if (ranked>0 && ranked<28)//получаем наши 27 пар и перемножаем их (по 3 на 1 элемент)
{
MPI_Recv(&buf, 2, MPI_INT, 0, 99, MPI_COMM_WORLD, &status);
mult=buf[0]*buf[1];
int proc;
proc=28+((ranked-1)%9);
cout<<ranked<<" - "<<proc<<" "<<mult<<endl;
MPI_Send(&mult, 1, MPI_INT, proc, 99, MPI_COMM_WORLD);
}
if (ranked>=28 && ranked<=36)//принимаем перемноженные пары и складываем (получаем 1 элемент необходимой нам матрицы)
{
int a,b,c;
int proc;
proc=ranked-27;
MPI_Recv(&a, 1, MPI_INT, proc, 99, MPI_COMM_WORLD, &status);
MPI_Recv(&b, 1, MPI_INT, proc+9, 99, MPI_COMM_WORLD, &status);
MPI_Recv(&c, 1, MPI_INT, proc+18, 99, MPI_COMM_WORLD, &status);
d=a+b+c;
cout<<"d for"<<ranked<<" - "<<d<<endl;
MPI_Gather(result, 9, MPI_INT, &d, 9, MPI_INT, 37, sums_comm);
}
if (ranked == 37)//печатаем матрицу
{
MPI_Gather(result, 9, MPI_INT, &d, 9, MPI_INT, 37, sums_comm);
for (int i=0; i<3; i++)
for (int j=0; j<3; j++)
cout<<result[i][j]<<endl;
getch();
}
MPI_Finalize();
return 0;
}
Выводы
В ходе лабораторной работы были изучены понятия независимости операций (блоков) в программе, исследованы методы распараллеливания программ путем их приведения к полной параллельной форме.