Міністерство освіти і науки України
Національний університет „Львівська політехніка”
Кафедра електронних
обчислювальних машин
Звіт
про виконання лабораторної роботи № 1
з курсу „ Паралельні та розподілені обчислення ”
ВИКОРИСТАННЯ ФУНКЦІОНАЛЬНОЇ ДЕКОМПОЗИЦІЇ ДЛЯ РОЗВ’ЯЗКУ ОБЧИСЛЮВАЛЬНИХ ЗАДАЧ.
Виконав:
Львів – 2005
Мета роботи: Вивчити методи декомпозицій задач. Набути навиків розв’язування задач з використанням функціональної декомпозиції.
Завдання
Використовуючи метод функціональної декомпозиції, розробити алгоритм обчислення запропонованого матрично-векторного виразу, який би враховував можливість паралельного виконання і був оптимальним з точки зору часових затрат. На основі створеного алгоритму написати програму яка дозволяє обчислити вираз та ілюструє проведену декомпозицію.
Вираз, який слід обрахувати, заданий наступним чином:
EMBED Equation.3 ( Варіант 20 )
При чому елементи EMBED Equation.3 визначаються згідно правил:
EMBED Equation.3 , де bi=20/(i3+20), і=1,2,...n
EMBED Equation.3
EMBED Equation.3 , де Cij=20/(i3-j3+2)
Аналіз завдання.
Вхідні дані: розмірність матриць – n, матриці EMBED Equation.3 ; вектори-стовпці EMBED Equation.3 .
Вектор-стовпець EMBED Equation.3 та матриця EMBED Equation.3 обраховуються, виходячи з уведеної розмірності, зауважимо, що значення їх елементів завжди менші одиниці і різко спадають зі збільшенням розмірності.
Згідно з поставленою задачею, в обчисленні загального виразу приймають участь три різні елементи – два вектори стовпці EMBED Equation.3 та матриця EMBED Equation.3 .
Оскільки, згідно правил матричних обчислень, добуток не є комутативною операцією, всі множення слід виконувати в тій послідовності, яка задана. Результатом множення рядка на стовпець є число, а матриці на матрицю – матриця, рядок матрицю = рядок, матрицю стовпець = стовпець, рядок стовпець = число, число матрицю = матриця.
Декомпозиція задачі.
Однозначно, всі обчислення безпосередньо залежать від розмірності даних, тому найперше, слід забезпечити ввід змінної n, що визначає цю розмірність. Далі, можна паралельно виконувати обчислення значень вектора b та матриці С2, оскільки вони незалежні від інших параметрів. Крім того, на тому ж рівні декомпозиції слід визначати вхідні дані, тобто вводити з клавіатури, або генерувати випадковим чином матриці EMBED Equation.3 та вектори-стовпці EMBED Equation.3 . Наступний рівень декомпозиції – це знаходження елементів виразу. Значення EMBED Equation.3 залежить від введеної матриці А та обрахованого вектора b. Значення EMBED Equation.3 залежить від введеної А1 та різниці векторів b1 і c1, тому знайти його можна лише після обчислення (b1 - c1). Зауважимо, що множення на константу не є окремою операцією, як і транспонування векторів. Аналогічно, знаходимо EMBED Equation.3 . Подальша декомпозиція відбувається згідно заданої послідовності операцій та врахування залежностей отриманих на кожному рівні даних. Порядок виконання програми умовно розбито на 8 етапів. Повна схема декомпозиції обчислення заданого виразу приведена нижче.
Об’єднання частин виразу проведено безпосередньо у схемі декомпозиції, оскільки воно однозначно визначається порядком обчислень.
Схема декомпозиції задачі
EMBED Visio.Drawing.6
Текст програми
#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 (...
