Міністерство освіти і науки України
Національний університет „Львівська політехніка”
Кафедра електронних
обчислювальних машин
Звіт
про виконання лабораторної роботи № 1
з курсу „ Паралельні та розподілені обчислення ”
ВИКОРИСТАННЯ ФУНКЦІОНАЛЬНОЇ ДЕКОМПОЗИЦІЇ ДЛЯ РОЗВ’ЯЗКУ ОБЧИСЛЮВАЛЬНИХ ЗАДАЧ.
Львів – 2005
Мета роботи: Вивчити методи декомпозицій задач. Набути навиків розв’язування задач з використанням функціональної декомпозиції.
Завдання
Використовуючи метод функціональної декомпозиції, розробити алгоритм обчислення запропонованого матрично-векторного виразу, який би враховував можливість паралельного виконання і був оптимальним з точки зору часових затрат. На основі створеного алгоритму написати програму яка дозволяє обчислити вираз та ілюструє проведену декомпозицію.
Вираз, який слід обрахувати, заданий наступним чином:
( Варіант 20 )
При чому елементи визначаються згідно правил:
, де bi=20/(i3+20), і=1,2,...n
, де Cij=20/(i3-j3+2)
Аналіз завдання.
Вхідні дані: розмірність матриць – n, матриці ; вектори-стовпці .
Вектор-стовпець та матриця обраховуються, виходячи з уведеної розмірності, зауважимо, що значення їх елементів завжди менші одиниці і різко спадають зі збільшенням розмірності.
Згідно з поставленою задачею, в обчисленні загального виразу приймають участь три різні елементи – два вектори стовпці та матриця .
Оскільки, згідно правил матричних обчислень, добуток не є комутативною операцією, всі множення слід виконувати в тій послідовності, яка задана. Результатом множення рядка на стовпець є число, а матриці на матрицю – матриця, рядок ( матрицю = рядок, матрицю ( стовпець = стовпець, рядок ( стовпець = число, число ( матрицю = матриця.
Декомпозиція задачі.
Однозначно, всі обчислення безпосередньо залежать від розмірності даних, тому найперше, слід забезпечити ввід змінної n, що визначає цю розмірність. Далі, можна паралельно виконувати обчислення значень вектора b та матриці С2, оскільки вони незалежні від інших параметрів. Крім того, на тому ж рівні декомпозиції слід визначати вхідні дані, тобто вводити з клавіатури, або генерувати випадковим чином матриці та вектори-стовпці . Наступний рівень декомпозиції – це знаходження елементів виразу. Значення залежить від введеної матриці А та обрахованого вектора b. Значення залежить від введеної А1 та різниці векторів b1 і c1, тому знайти його можна лише після обчислення (b1 - c1). Зауважимо, що множення на константу не є окремою операцією, як і транспонування векторів. Аналогічно, знаходимо . Подальша декомпозиція відбувається згідно заданої послідовності операцій та врахування залежностей отриманих на кожному рівні даних. Порядок виконання програми умовно розбито на 8 етапів. Повна схема декомпозиції обчислення заданого виразу приведена нижче.
Об’єднання частин виразу проведено безпосередньо у схемі декомпозиції, оскільки воно однозначно визначається порядком обчислень.
Схема декомпозиції задачі
Текст програми
#include "stdafx.h"
#include "stdlib.h"
#include "conio.h"
#include "math.h"
FILE *OutFile=fopen("output.txt","w");
int rows;
int Option(void)
{
char select;
while ( select!='y' && select!='Y' && select!='N' && select!='n' )
{
printf("\b");
select=getche();
}
if (select=='y' || select=='Y') return 1;
return 0;
}
/************************************ Memory allocation *****/
float** AllocateMatrix(int row)
{
int i;
float **A;
A=new float*[row];
if (A==NULL)
{
puts("Memory allocation error."); exit(0);
};
for (i=0; i<rows; i++)
{
A[i]=new float[row];
if (A[i]==NULL) {
puts("Memory allocation error."); exit(0); };
};
return A;
};
float* AllocateVector(int row)
{
float *A;
A=new float[row];
if (A==NULL)
{
puts("Memory allocation error."); exit(0);
};
return A;
};
/************************************ Memory freeing *****/
void DeleteMatrix( float **A, int row)
{ int i;
for (i=0; i<row; i++) delete A[i];
delete A;
};
void DeleteVector( float *A)
{ delete A; };
/**********************...
