close

Вход

Забыли?

вход по аккаунту

?

lab4 tpv2

код для вставкиСкачать
Министерство образования и науки Украины
Севастопольский национальный технический университет
Кафедра
Информационных систем
Лабораторная работа № 4
Синтез параллельных программ на основе моделей вычислений
ВыполнениеОценка
Выполнил:
ст. гр. И-41д
Лынок А.Ю.
Проверил:
Кротов К. В. Севастополь 2013
1 ЦЕЛЬ РАБОТЫ
Исследование сущности и особенностей методов распараллеливания последовательных ациклических программ с использованием моделей вычислений.
2 ВАРИАНТ ЗАДАНИЯ Осуществить распараллеливание линейных циклических программ в соответствии с вариантом и построить для них схему параллельно-последовательной программы для заданного числа процессоров.
Вариант 2.
Вычислить полином
Y=a0 x0+a1x1+...+a5x5
x0 =1; x1=x-(n+1)/2; x2 =x12 -(n2 -1)/12;
xk+1 = x1xk - k2(n2- k2)/(4(4k2-1))xk-1
Коэффициент n=5.
На МВКБ, состоящем из 5 процессоров.
3 ХОД РАБОТЫ
Используем программу Maple для составления результирующего полинома. Раскрывая скобки и приводя подобные слагаемые, получаем:
Последовательную программу можно представить в виде следующих операций:
ввод()
if (x = 0) then goto S18 else goto S3
print()
На рисунке 1 программа представлена графически. Исследование зависимостей в программе представлено в таблице 1.
Таблица 1 - Зависимости в программе
№Зависимые операции|in aj|ИнформационноЛогическиКонкуренционно12-20--72---13193, 18-2419--2519--2619--2719--2819--2919--21019--21119--21219--21319--21419--21519--21619--21719--21819--61920--1620---1
Рисунок 1 - Структурная схема линейной программы
Используя таблицу 1, построим таблицу 2, которая покажет, от каких операций зависит данная операция. С помощью таблицы 2 можно построить ЯПФ программы (таблица 3).
Таблица 2 - Зависимости №Зависит от1-2131, 2415161718191101111121131141151161171181, 2193-182019
Таблица 3 - ЯПФ программы
№ ярусаВключаемые операции0112, 4-1723, 18319420
Графическое представление ЯПФ изображено на рисунке 2.
Рисунок 2 - Графическое представление ЯПФ
Построим параллельно-последовательную форму программы, если число процессоров в системе n = 5. Для этого воспользуемся уже построенной ЯПФ.
Согласно алгоритму, на 1 ярусе ЯПФ операции равномерно распределяются по процессорам:
1: {2, 4, 5}
2: {6, 7, 8}
3: {9, 10, 11}
4: {12, 13, 14}
5: {15, 16, 17}
При этом предполагается, что r = 3 (кратность повторения) - этим обеспечивается равномерное распределение операций по процессорам.
Второй ярус распараллелим так:
1: {(wait(1(2=0)), 3); (wait(1(2=1)), 18)}.
3-й ярус:
1: {wait(3, 4, 5,..., 18), 19}.
4-й ярус:
1: {wait(19), 20}
Результат представлен на рисунке 3.
Рисунок 3 - Параллельно-последовательная программа
4 ТЕКСТ ПРОГРАММЫ
#include <iostream>
#include <iomanip>
#include <mpi.h>
using namespace std;
MPI_Status status;
void proc0()
{
float a0, a1, a2, a3, a4, a5, x;
a0 = 1; a1 = 2; a2 = 3; a3 = 4;
a4 = 5; a5 = 6; x = 1;
/*cout << "a0 = ";
cin >> a0;
cout << endl << "a1 = ";
cin >> a1;
cout << endl<< "a2 = ";
cin >> a2;
cout << endl<< "a3 = ";
cin >> a3;
cout << endl<< "a4 = ";
cin >> a4;
cout << endl<< "a5 = ";
cin >> a5;
cout << endl<< "x = " ;
cin >> x;*/
for (int i = 1; i <= 5; i++)
{
MPI_Send(&a0, 1, MPI_FLOAT, i, 0, MPI_COMM_WORLD);
MPI_Send(&a1, 1, MPI_FLOAT, i, 0, MPI_COMM_WORLD);
MPI_Send(&a2, 1, MPI_FLOAT, i, 0, MPI_COMM_WORLD);
MPI_Send(&a3, 1, MPI_FLOAT, i, 0, MPI_COMM_WORLD);
MPI_Send(&a4, 1, MPI_FLOAT, i, 0, MPI_COMM_WORLD);
MPI_Send(&a5, 1, MPI_FLOAT, i, 0, MPI_COMM_WORLD);
MPI_Send(&x, 1, MPI_FLOAT, i, 0, MPI_COMM_WORLD);
}
cout << "P0: all of the data has been sent" << endl;
getchar();
}
void proc1()
{
float a0, a1, a2, a3, a4, a5, x;
MPI_Recv(&a0, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(&a1, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(&a2, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(&a3, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(&a4, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(&a5, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(&x, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
cout << "P1: receiving the data" << endl;
float t17;
if (x == 0) {
t17 = a0 - 3*a1 + 7*a2 - 16.8*a3 + 216.0/5.0 * a4 - 120*a5;
cout << "P1: x = 0. The result is: " << t17 << endl;
return;
}
// s4
float t2 = a2 * x * x;
// s5
float t3 = -6 * a2 * x;
// s3
float t1 = a1 * x;
// s18
float t16 = a0 - 3*a1 + 7*a2 - 16.8*a3 + 216.0/5.0 * a4 - 120*a5;
// s19 (wait)
// wait (4,5,6,7,8,9,10,11,12,13,14,15)
float t4,t5,t6,t7,t8,t9,t10,t11,t12,t13,t14,t15;
MPI_Recv(&t4, 1, MPI_FLOAT, 2, 2, MPI_COMM_WORLD, &status);
MPI_Recv(&t5, 1, MPI_FLOAT, 2, 2, MPI_COMM_WORLD, &status);
MPI_Recv(&t6, 1, MPI_FLOAT, 2, 2, MPI_COMM_WORLD, &status);
MPI_Recv(&t7, 1, MPI_FLOAT, 3, 3, MPI_COMM_WORLD, &status);
MPI_Recv(&t8, 1, MPI_FLOAT, 3, 3, MPI_COMM_WORLD, &status);
MPI_Recv(&t9, 1, MPI_FLOAT, 3, 3, MPI_COMM_WORLD, &status);
MPI_Recv(&t10,1, MPI_FLOAT, 4, 4, MPI_COMM_WORLD, &status);
MPI_Recv(&t11,1, MPI_FLOAT, 4, 4, MPI_COMM_WORLD, &status);
MPI_Recv(&t12,1, MPI_FLOAT, 4, 4, MPI_COMM_WORLD, &status);
MPI_Recv(&t13,1, MPI_FLOAT, 5, 5, MPI_COMM_WORLD, &status);
MPI_Recv(&t14,1, MPI_FLOAT, 5, 5, MPI_COMM_WORLD, &status);
MPI_Recv(&t15,1, MPI_FLOAT, 5, 5, MPI_COMM_WORLD, &status);
t17 = t1+t2+t3+t4+t5+t6+t7+t8+t9+t10+t11+t12+t13+t14+t15+t16;
cout << "P1: The result is: " << t17 << endl;
}
void proc2()
{
float a0, a1, a2, a3, a4, a5, x;
MPI_Recv(&a0, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(&a1, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(&a2, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(&a3, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(&a4, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(&a5, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(&x, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
cout << "P2: receiving the data" << endl;
if (x == 0) return;
// s6, s7, s8
float t4, t5, t6;
t4 = a3 * x * x * x;
t5 = -9 * a3 * x * x;
t6 = 23.6 * a3 * x;
MPI_Send(&t4, 1, MPI_FLOAT, 1, 2, MPI_COMM_WORLD);
MPI_Send(&t5, 1, MPI_FLOAT, 1, 2, MPI_COMM_WORLD);
MPI_Send(&t6, 1, MPI_FLOAT, 1, 2, MPI_COMM_WORLD);
}
void proc3()
{
float a0, a1, a2, a3, a4, a5, x;
MPI_Recv(&a0, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(&a1, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(&a2, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(&a3, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(&a4, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(&a5, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(&x, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
cout << "P3: receiving the data" << endl;
if (x == 0) return;
// s9, s10, s11
float t7,t8,t9;
t7 = a4 * x * x * x * x;
t8 = -12 * a4 * x * x * x;
t9 = 347.0/7.0 * a4 * x * x;
MPI_Send(&t7, 1, MPI_FLOAT, 1, 3, MPI_COMM_WORLD);
MPI_Send(&t8, 1, MPI_FLOAT, 1, 3, MPI_COMM_WORLD);
MPI_Send(&t9, 1, MPI_FLOAT, 1, 3, MPI_COMM_WORLD);
}
void proc4()
{
float a0, a1, a2, a3, a4, a5, x;
MPI_Recv(&a0, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(&a1, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(&a2, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(&a3, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(&a4, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(&a5, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(&x, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
cout << "P4: receiving the data" << endl;
if (x == 0) return;
// s12, s13, s14
float t10,t11,t12;
t10 = -570.0/7.0 * a4 * x;
t11 = a5 * x * x * x * x * x;
t12 = -15 * a5 * x * x * x * x;
MPI_Send(&t10, 1, MPI_FLOAT, 1, 4, MPI_COMM_WORLD);
MPI_Send(&t11, 1, MPI_FLOAT, 1, 4, MPI_COMM_WORLD);
MPI_Send(&t12, 1, MPI_FLOAT, 1, 4, MPI_COMM_WORLD);
}
void proc5()
{
float a0, a1, a2, a3, a4, a5, x;
MPI_Recv(&a0, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(&a1, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(&a2, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(&a3, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(&a4, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(&a5, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(&x, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);
cout << "P5: receiving the data" << endl;
if (x == 0) return;
// s15, s16, s17
float t13,t14,t15;
t13 = 85 * a5 * x * x * x;
t14 = -225 * a5 * x * x;
t15 = 274 * a5 * x;
MPI_Send(&t13, 1, MPI_FLOAT, 1, 5, MPI_COMM_WORLD);
MPI_Send(&t14, 1, MPI_FLOAT, 1, 5, MPI_COMM_WORLD);
MPI_Send(&t15, 1, MPI_FLOAT, 1, 5, MPI_COMM_WORLD);
}
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
int main(int argc, char* argv[])
{
int rank;// ранг текущего процесса
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);// определяем идентификатор копии процесса switch(rank) {
case 0: proc0(); break; case 1: proc1(); break;
case 2: proc2(); break;
case 3: proc3(); break;
case 4: proc4(); break;
case 5: proc5(); break;
default: MPI_Finalize(); return -1; break;
}
MPI_Finalize();
return 0;
}
5 ПРОВЕРКА РАБОТЫ ПРОГРАММЫ
P1: receiving the data
P2: receiving the data
P0: all of the data has been sent
P4: receiving the data
P5: receiving the data
P3: receiving the data
P1: The result is: 5508.6
Результат, полученный в программе Maple: 5508.6.
ВЫВОДЫ
В процессе выполнения данной лабораторной работы исследовались методы распараллеливания программ с использованием моделей вычислений. Так, была реализована последовательно-параллельная программа, выполняющаяся на 5 процессорах. В её основе - уже построенная ЯПФ, параллельные операции которой равномерно распределены по процессорам. В результате получается, что некоторые операции начинают выполняться последовательно, а в некоторых случаях процессор приостанавливает работу до получения необходимых данных.
2
Документ
Категория
Рефераты
Просмотров
19
Размер файла
288 Кб
Теги
lab4, tpv2
1/--страниц
Пожаловаться на содержимое документа