Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Використання функціональної декомпозиції для розв’язку обчислювальних задач
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2005
Тип роботи:
Звіт про виконання лабораторної роботи
Предмет:
Паралельні та розподілені обчислення
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет „Львівська Політехніка”
Кафедра ЕОМ
ЗВІТ
Про виконання лабораторної роботи № 1
з предмету „Паралельні та розподілені обчислення”
на тему:
„ Використання функціональної декомпозиції для розв’язку обчислювальних задач ”
м Львів – 2005
Мета: Вивчити методи декомпозицій задач. Набути навиків розв’язування задач з використанням функціональної декомпозиції.
Найважливішим та найважчим етапом при створенні програми є розробка алгоритму, особливо, якщо мова йде про паралельний алгоритм. Процес створення паралельного алгоритму можна розбити на чотири кроки.
1. Декомпозиція. На цьому етапі вихідна задача аналізується, оцінюється можливість її розпаралелювання. Іноді виграш від розпаралелення може бути незначним, а трудоємкість розробки паралельної програми велика. В цьому випадку перший крок розробки алгоритму виявляється і останнім. Якщо ж ситуація відмінна від описаної, то задача та пов’язані з нею дані розділяються на дрібніші частини – підзадачі і фрагменти структур даних. Особливості архітектури конкретної обчислювальної системи на цьому етапі можуть не враховуватися.
2. Проектування комунікацій(обміну даними) між задачами. На цьому етапі визначаються зв’язки, необхідні для пересилання вхідних даних, проміжних результатів виконання підзадач, а також комунікації, що необхідні для керування роботою під задач. Обираються методи та алгоритми комунікацій.
3.Укрупнення. Підзадачі можуть об’єднуватися у більші блоки, якщо це дозволяє підвищити ефективність алгоритму і знизити трудоємкість розробки. Основними критеріями на даному кроці є ефективність алгоритму (в першу чергу продуктивність) та трудоємкість його реалізації.
4. Планування обчислень. На цьому кроці виконується розподіл під задач між процесорами. Основний критерій вибору способу розміщення під задач – ефективне використання процесорів з мінімальними затратами часу на обмін даними.
Завдання:
Вираз, який слід обрахувати, заданий наступним чином:
При чому елементи визначаються згідно правил:
, bi=i2/12 для парних і bi=i для непарних і
y2= A1(12b1-c1)
Y3=A2(B2-C2), де Cij=1/(i+j2)
Перепишемо заданий вираз у вигляді:
y2'+(y1'Y32y1Y3y2+y1'y2Y3y2+y1y2'y2)'
1) Аналіз завдання:
Для заданого виразу вхідними даними є:
розмірність матриць – n;
матриці ;
вектори-стовпці .
Ці параметри повинні вводитися з клавіатури, або генеруватися випадковим чином (крім розмірності). При чому, елементи всіх матриць та векторів є цілими додатними числами, більшими за нуль. Вектор-стовпець та матриця обраховуються, виходячи з уведеної розмірності.
При утворенні враховуємо, що результатом множення матриці А на вектор-стовпець b є вектор-стовпець.
При утворенні враховуємо, що результатом віднімання двох векторів-стовпців є вектор-стовпець. Далі, при множенні цілочисельної додатної матриці А1 на результат віднімання, отримаємо вектор-стовпець з цілочисельними елементами.
При утворенні враховуємо, результатом множення матриці на різницю матрицей буде матриця.
Таким чином, згідно поставленої задачі, в обчисленні загального виразу приймають участь три різні елементи – два вектори стовпці та матриця .
Оскільки, згідно правил матричних обчислень, добуток не є комутативною операцією, всі множення слід виконувати в тій послідовності, яка задана.
Врахуємо такі особливості:
результатом множення матриці на матрицю є матриця.
cij=
результатом множення матриці на вектор-стовпець є вектор-стовпець.
cj=
результатом множення вектора-рядка на вектор-стовпець є число
с=
результатом множення вектора-стовпця на вектор-рядок є матриця
сij=
результатом множення двох векторів-стовпців є число.
с=
результатом множення вектора-рядка на матрицю на є вектор-рядок.
сj=
Згідно цього, проаналізувавши завдання, приходимо до висновку, що результатом буде вектор-рядок.
2. Декомпозиція задачі.
Однозначно, всі обчислення безпосередньо залежать від розмірності даних, тому найперше, слід забезпечити ввід змінної n, що визначає цю розмірність. Далі, можна паралельно виконувати обчислення значень вектора b та матриці С2, оскільки вони незалежні від інших параметрів. Крім того, на тому ж рівні декомпозиції слід визначати вхідні дані, тобто вводити з клавіатури, або генерувати випадковим чином матриці та вектори-стовпці . Наступний рівень декомпозиції – це знаходження елементів виразу. Значення залежить від введеної матриці А та обрахованого вектора b. Значення залежить від введеної А1 та різниці векторів b1 і c1, тому знайти його можна лише після обчислення (12b1 - c1). Зауважимо, що множення на константу не є окремою операцією, як і транспонування векторів. Аналогічно, знаходимо . Подальша декомпозиція відбувається згідно заданої послідовності операцій та врахування залежностей отриманих на кожному рівні даних. Повна схема декомпозиції обчислення заданого виразу приведена нижче.
3. Об’єднання частин виразу проведено безпосередньо у схемі декомпозиції, оскільки воно однозначно визначається порядком обчислень.
Схема декомпозиції обчислення виразу
Висновок: Вивчили методи декомпозицій задач. Набули навиків розв’язування задач з використанням функціональної декомпозиції. В роботі використано паралелізм на рівні підзадач, оскільки передбачається, що кожен блок зі схеми декомпозиції є реалізований у виді функції. Це є середньоблоковий паралелізм. Обмін даними відбувається через використання спільних змінних. Присутня залежність даних між різними рівнями декомпозиції, але в межах одного рівня її немає. Є залежність за керуванням, оскільки послідовність обчислювального процесу наперед однозначно відома. Залежність за ресурсами та вводом/виводом може бути визначена лише у відношенні до певної обчислювальної системи.
Вибірковий текст програми (результати тестування показує прога. Скріншоти досить великі ( )
type
arreal2d=array of array of real;
arint2d=array of array of integer;
var
n:integer; //Size of arrays
C:arreal2d;
b:array of real;
B2,A2,A1,A:arint2d;
b1,c1:array of integer;
//Stage2
B2mC:arreal2d;
b1mc1:array of integer;
//Stage3
Y3:arreal2d;
y2,y1:array of real;
//Stage4
Y3p2,y1y2t:arreal2d;
Y3y2:array of real;
y1ty2:real;
//Stage5
Y3p2y1,y1ty2Y3y2,y1y2ty2:array of real;
//Stage 6
y1tY3p2y1:real;
y1ty2Y3y2ADDy1y2ty2:array of real;
//Stage 7
y1tY3p2y1Y3y2:array of real;
//Stage 8
y1tY3p2y1Y3y2ADDy1ty2Y3y2ADDy1y2ty2:array of real;
//Stage 9
y1tY3p2y1Y3y2ADDy1ty2Y3y2ADDy1y2ty2TADDy2T:array of real;
…
n:=strtointdef(edit1.text,5);
SetLength(B2,n,n); SetLength(A2,n,n); SetLength(A1,n,n);
SetLength(A,n,n); SetLength(b1,n); SetLength(c1,n);
SetLength(C,n,n); SetLength(b,n);
…
//==============================
procedure stage1();
var i,j:integer;
begin
//****Generate C&b
for i:=0 to n-1 do
for j:=0 to n-1 do
C[i,j]:=(1/(i+1+(j+1)*(j+1)));
for i:=1 to n do
begin
if (i mod 2)=0 then b[i-1]:=i*i/12
else b[i-1]:=i
end;
randomize;
if form1.gen.Checked then
begin
for i:=0 to n-1 do
for j:=0 to n-1 do
begin
B2[i,j]:=random(9);A2[i,j]:=random(9);
A1[i,j]:=random(9);A[i,j]:=random(9);
b1[i]:=random(9);c1[i]:=random(9);
end;
end
end;
//=============STAGE 2===============
procedure stage2();
var i,j:integer;
begin
SetLength(B2mC,n,n);
SetLength(b1mc1,n);
for i:=0 to n-1 do
for j:=0 to n-1 do
begin
B2mC[i,j]:=B2[i,j]-C[i,j];
b1mc1[i]:=12*b1[i]-c1[i];
end;
end;
//=============STAGE 3===============
procedure stage3();
var i,j,k:integer;
tempS,TempS2:real;
begin
SetLength(Y3,n,n);
SetLength(y1,n);
SetLength(y2,n);
{}for i:=0 to n-1 do
for j:=0 to n-1 do
begin
TempS:=0;
for k:=0 to n-1 do
begin
TempS:=TempS+A2[i,k]*B2mC[k,j]
end;
Y3[i,j]:=TempS;
end;
{}for i:=0 to n-1 do
begin
TempS:=0;TempS2:=0;
for k:=0 to n-1 do
begin
TempS:=TempS+A1[i,k]*b1mc1[k];
TempS2:=TempS2+A[i,k]*b[k];
end;
y2[i]:=TempS;
y1[i]:=TempS2;
end;
end;
//=============STAGE 4===============
procedure stage4();
var i,j,k:integer;
TempS:real;
begin
SetLength(Y3p2,n,n);
SetLength(Y3y2,n);
SetLength(y1y2t,n,n);
{}for i:=0 to n-1 do
for j:=0 to n-1 do
begin
TempS:=0;
for k:=0 to n-1 do
begin
TempS:=TempS+Y3[i,k]*Y3[k,j]
end;
Y3p2[i,j]:=TempS;
end;
{}for i:=0 to n-1 do
begin
TempS:=0;
for k:=0 to n-1 do
TempS:=TempS+Y3[i,k]*y2[k];
Y3y2[i]:=TempS;
end;
TempS:=0;
{}for i:=0 to n-1 do TempS:=TempS+y1[i]*y2[i];
y1ty2:=TempS;
{}for i:=0 to n-1 do
for j:=0 to n-1 do
y1y2t[i,j]:=y1[i]*y2[j];
end;
//=============STAGE 5===============
procedure stage5();
var k,i:integer;
TempS:real;
begin
SetLength(Y3p2y1,n);
SetLength(y1ty2Y3y2,n);
SetLength(y1y2ty2,n);
{}for i:=0 to n-1 do
begin
TempS:=0;
for k:=0 to n-1 do
TempS:=TempS+Y3p2[i,k]*y1[k];
Y3p2y1[i]:=TempS;
end;
{}
for i:=0 to n-1 do
y1ty2Y3y2[i]:=y1ty2*Y3y2[i];
{}for i:=0 to n-1 do
begin
TempS:=0;
for k:=0 to n-1 do
TempS:=TempS+y1y2t[i,k]*y2[k];
y1y2ty2[i]:=TempS;
end;
end;
//=============STAGE 6===============
procedure stage6();
var i:integer;
TempS:real;
begin
SetLength(y1ty2Y3y2ADDy1y2ty2,n);
TempS:=0;
{}for i:=0 to n-1 do
begin
y1ty2Y3y2ADDy1y2ty2[i]:=y1ty2Y3y2[i]+y1y2ty2[i];
TempS:=TempS+y1[i]*Y3p2y1[i];
end;
y1tY3p2y1:=TempS;
end;
//=============STAGE 7===============
procedure stage7();
var i:integer;
begin
SetLength(y1tY3p2y1Y3y2,n);
{}for i:=0 to n-1 do
y1tY3p2y1Y3y2[i]:=y1tY3p2y1*Y3y2[i]
end;
//=============STAGE 8===============
procedure stage8();
var i:integer;
begin
SetLength(y1tY3p2y1Y3y2ADDy1ty2Y3y2ADDy1y2ty2,n);
{}for i:=0 to n-1 do
y1tY3p2y1Y3y2ADDy1ty2Y3y2ADDy1y2ty2[i]:=y1tY3p2y1Y3y2[i]+
+y1ty2Y3y2ADDy1y2ty2[i]
//LOL :-)
end;
//=============STAGE 9===============
procedure stage9();
var i:integer;
begin
SetLength(y1tY3p2y1Y3y2ADDy1ty2Y3y2ADDy1y2ty2TADDy2T,n);
{}for i:=0 to n-1 do
y1tY3p2y1Y3y2ADDy1ty2Y3y2ADDy1y2ty2TADDy2T[i]:=
y1tY3p2y1Y3y2ADDy1ty2Y3y2ADDy1y2ty2[i]+y2[i]
//LOL :-)
end;
….
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора