Міністерство освіти та науки України Національний університет «Львівська політехніка» Кафедра ЕОМ паралельні та розподілені обчислення Лабораторна робота № 1 ВИКОРИСТАННЯ ФУНКЦІОНАЛЬНОЇ ДЕКОМПОЗИЦІЇ ДЛЯ РОЗВ’ЯЗКУ ОБЧИСЛЮВАЛЬНИХ ЗАДАЧ. Львів 2005 TEMA: Використання функціональної декомпозиції для розв’язку обчислювальних задач. МЕТА РОБОТИ. Вивчити методи декомпозицій задач. Набути навиків розв’язування задач з використанням функціональної декомпозиції. Завдання: Вираз, який слід обрахувати, заданий наступним чином:
При чому елементи
визначаються згідно правил:
, де bi=9i , і=1,2,...n

, де
Послідовність виконання. 1.  Аналіз завдання. Для заданого виразу вхідними даними є: розмірність матриць – n; матриці
; вектори-стовпці
. Ці параметри повинні вводитися з клавіатури, або генеруватися випадковим чином (крім розмірності). При чому, елементи всіх матриць та векторів є цілими додатними числами, більшими за нуль. Вектор-стовпець
та матриця
обраховуються, виходячи з уведеної розмірності, зауважимо, що значення їх елементів завжди менші одиниці і різко спадають зі збільшенням розмірності. При утворенні
враховуємо, що результатом множення матриці А на вектор-стовпець b є вектор-стовпець, елементи якого будуть раціональними числами(тобто матимуть значущу дробову частину). При утворенні
враховуємо, що результатом віднімання двох векторів-стовпців є вектор-стовпець, елементи якого можуть бути меншими за нуль цілими числами. Далі, при множенні цілочисельної додатної матриці А1 на результат віднімання, отримаємо вектор-стовпець з цілочисельними елементами довільного знаку. При утворенні
враховуємо, що присутні лише операції додавання та множення, а тому вихідний результат завжди буде додатнім і завжди матиме значущу дробову частину. Таким чином, згідно поставленої задачі, в обчисленні загального виразу приймають участь три різні елементи – два вектори стовпці
та матриця
. Оскільки, згідно правил матричних обчислень, добуток не є комутативною операцією, всі множення слід виконувати в тій послідовності, яка задана. Результатом множення рядка на стовпець є число, а матриці на матрицю - матриця. Тому, в загальному, перший доданок буде рядком. Аналогічний аналіз можна застосувати і до другого доданку виразу. Таким чином, з попереднього випливає, що остаточний результат є рядком, елементи якої можуть бути як додатними так і від’ємними і завжди мають дробову частину. 2.  Декомпозиція задачі. Однозначно, всі обчислення безпосередньо залежать від розмірності даних, тому найперше, слід забезпечити ввід змінної n, що визначає цю розмірність. Далі, можна паралельно виконувати обчислення значень вектора b та матриці С2, оскільки вони незалежні від інших параметрів. Крім того, на тому ж рівні декомпозиції слід визначати вхідні дані, тобто вводити з клавіатури, або генерувати випадковим чином матриці
та вектори-стовпці
. Наступний рівень декомпозиції – це знаходження елементів виразу. Значення
залежить від введеної матриці А та обрахованого вектора b. Значення
залежить від введеної А1 та різниці векторів b1 і c1, тому знайти його можна лише після обчислення (b1 - c1). Зауважимо, що множення на константу не є окремою операцією, як і транспонування векторів. Аналогічно, знаходимо
. Подальша декомпозиція відбувається згідно заданої послідовності операцій та врахування залежностей отриманих на кожному рівні даних. Повна схема декомпозиції обчислення заданого виразу приведена нижче.
3. Текст програми та результат її роботи на довільному наборі вхідних даних, для розмірності n>3. uses crt; type ArrayMatrix=array[1..10,1..10] of Real; var x:Real; n,d,i,j:Integer; isvvid:Boolean; h:Integer; iswrite:Boolean; f:Text; num:Integer; b,A,A1,b1,c1,A2,B2,C2,y1,y2,y3,xx:ArrayMatrix; y1_,y2_,tmp1,tmp2,tmp3,tmp4,tmp5,tmp6,tmp7,tmp8,tmp9,tmp10,rez:ArrayMatrix; procedure MultiplyMatrixes(n:Integer;m:Integer;k:Integer; const aa:ArrayMatrix; {A(nxm)*B(mxk)} const bb:ArrayMatrix; var xx:ArrayMatrix); var I : Integer; J : Integer; L : Integer; begin i:=1; while i<=n do begin j:=1; while j<=k do begin xx[i,j] := 0; l:=1; while l<=m do begin xx[i,j] := xx[i,j]+aa[i,l]*bb[l,j]; Inc(l); end; Inc(j); end; Inc(i); end; end; procedure MatxNum(m,k:Integer;num:Real;const aa:ArrayMatrix; var xx:ArrayMatrix); begin for i:=1 to m do for j:=1 to k do xx[i,j]:=num*aa[i,j]; end; procedure SumMatr(m,k:Integer;const aa,bb:ArrayMatrix; var xx:ArrayMatrix); begin for i:=1 to m do for j:=1 to k do xx[i,j]:=aa[i,j]+bb[i,j]; end; procedure TransMatrix(ss:ArrayMatrix;var xx:ArrayMatrix;m,k:Integer); begin for i:=1 to m do for j:=1 to k do xx[j,i]:=ss[i,j]; end; procedure PrintMatrix(str:String;xx:ArrayMatrix;m,k:Integer); begin writeln; writeln; writeln(str); if iswrite then begin writeln(f); writeln(f); writeln(f,str); end; for i:=1 to m do begin writeln; if iswrite then writeln(f); for j:=1 to k do begin write(xx[i,j]:15:2); if iswrite then write(f,xx[i,j]:15:2); end; end; end; procedure WriteStep; begin inc(num); writeln; writeln('---- Step',num,': ----'); if iswrite then begin writeln(f); writeln(f,'---- Step',num,': ----'); end; end; procedure WriteStr(str:String); begin writeln; writeln(str); if iswrite then begin writeln(f); writeln(f,str); end; end; begin assign(f,'result.txt'); rewrite(f); clrscr; writeln('x=y2''(Y3+y1''y1Y3^2+y2y2'')+y1''(y1''y1Y3+Y3^3)'); write('Vvedit n: '); readln(n); writeln('Vuberit jak budut vvodutus dani'); writeln('1-Random'); writeln('2-From keyboard'); readln(h); if h=2 then isvvid:=True else isvvid:=False; writeln('Zberigaty resultaty u fail?'); writeln('1-Tak'); writeln('2-Hi'); readln(h); if h=1 then iswrite:=true else iswrite:=false; writeln('Obchyslennya:'); if iswrite then writeln(f,'Obchyslennya:'); num:=0; WriteStep; {-------b-----------} for i:=1 to n do b[i,1]:=9*i; PrintMatrix('Vector b:',b,n,1); {-------A---------} writeln; randomize; for i:=1 to n do for j:=1 to n do begin if isvvid then begin write('A[',i,',',j,']='); readln(d); a[i,j]:=d; end else a[i,j]:=random(9)+1; end; PrintMatrix('Matrix A:',A,n,n); {-------A1-----------} writeln; for i:=1 to n do for j:=1 to n do begin if isvvid then begin write('A1[',i,',',j,']='); readln(d); A1[i,j]:=d; end else A1[i,j]:=random(9)+1; end; PrintMatrix('Matrix A1:',A1,n,n); WriteStep; {-------b1-----------} writeln; for i:=1 to n do begin if isvvid then begin write('b1[',i,']='); readln(d); b1[i,1]:=d; end else b1[i,1]:=random(9)+1; end; PrintMatrix('Vector b1',b1,n,1); {-------c1-----------} writeln; for i:=1 to n do begin if isvvid then begin write('c1[',i,']='); readln(d); c1[i,1]:=d; end else c1[i,1]:=random(9)+1; end; PrintMatrix('Vector c1:',c1,n,1); {-------A2-----------} writeln; for i:=1 to n do for j:=1 to n do begin if isvvid then begin write('A2[',i,',',j,']='); readln(d); A2[i,j]:=d; end else A2[i,j]:=random(9)+1; end; PrintMatrix('Matrix A2',A2,n,n); WriteStep; {-------b1-c1--------} for i:=1 to n do b1[i,1]:=b1[i,1]-c1[i,1]; PrintMatrix('b1-c1:',b1,n,1); {-------B2-----------} writeln; for i:=1 to n do for j:=1 to n do begin if isvvid then begin write('B2[',i,',',j,']='); readln(d); B2[i,j]:=d; end else B2[i,j]:=random(9)+1; end; PrintMatrix('Matrix B2:',B2,n,n); {----------C2------------} for i:=1 to n do for j:=1 to n do C2[i,j]:=1/(i+j); PrintMatrix('Matrix C2:',c2,n,n); WriteStep; {------------B2+C2-------------------------} for i:=1 to n do for j:=1 to n do B2[i,j]:=B2[i,j]+C2[i,j]; PrintMatrix('B2+C2:',b2,n,n); {--------------------y1-------------------------} MultiplyMatrixes(n,n,1,A,b,y1); PrintMatrix('Matrix y1:',y1,n,1); {---------------y2-------------------} MultiplyMatrixes(n,n,1,A1,b1,y2); PrintMatrix('Matrix y2:',y2,n,1); WriteStep; {-----------------y3---------------} MultiplyMatrixes(n,n,n,A2,B2,y3); PrintMatrix('Matrix y3:',y3,n,n); TransMatrix(y1,y1_,n,1); TransMatrix(y2,y2_,n,1); MultiplyMatrixes(1,n,1,y1_,y1,tmp1); PrintMatrix('y1^*y1:',tmp1,1,1); MultiplyMatrixes(n,1,n,y2,y2_,tmp2); PrintMatrix('y2*y2^:',tmp2,n,n); {--------------------------------} WriteStep; MultiplyMatrixes(n,n,n,y3,y3,tmp3); PrintMatrix('y3^2:',tmp3,n,n); MatxNum(n,n,tmp1[1,1],y3,tmp4); PrintMatrix('y1''*y1*Y3:',tmp4,n,n); SumMatr(n,n,Y3,tmp2,tmp6); PrintMatrix('Y3+y2y2'':',tmp6,n,n); {--------------------------------} WriteStep; MatxNum(n,n,tmp1[1,1],tmp3,tmp5); PrintMatrix('y1''*y1*Y3^2:',tmp5,n,n); SumMatr(n,n,tmp5,tmp6,tmp7); PrintMatrix('Y3+y1''*y1*Y3^2+y2y2'':',tmp7,n,n); SumMatr(n,n,tmp4,tmp3,tmp8); PrintMatrix('y1''*y1*Y3+Y3^2:',tmp8,n,n); {---------------------------------} WriteStep; MultiplyMatrixes(1,n,n,y2_,tmp7,tmp9); PrintMatrix('y2''*(Y3+y1''*y1*Y3^2+y2y2''):',tmp9,1,n); MultiplyMatrixes(1,n,n,y1_,tmp8,tmp10); PrintMatrix('y1''*(y1''*y1*Y3+Y3^2):',tmp10,1,n); SumMatr(1,n,tmp9,tmp10,rez); PrintMatrix('x=',rez,1,n); readln; close(f); end. Тестування: Obchyslennya: ---- Step1: ---- Vector b: 9.00 18.00 27.00 36.00 Matrix A: 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 Matrix A1: 2.00 2.00 2.00 2.00 2.00 2.00 2.00 2.00 2.00 2.00 2.00 2.00 2.00 2.00 2.00 2.00 ---- Step2: ---- Vector b1 3.00 3.00 3.00 3.00 Vector c1: 1.00 2.00 3.00 4.00 Matrix A2 3.00 3.00 3.00 3.00 3.00 3.00 3.00 3.00 3.00 3.00 3.00 3.00 3.00 3.00 3.00 3.00 ---- Step3: ---- b1-c1: 2.00 1.00 0.00 -1.00 Matrix B2: 1.00 2.00 3.00 4.00 1.00 2.00 3.00 4.00 1.00 2.00 3.00 4.00 1.00 2.00 3.00 4.00 Matrix C2: 0.50 0.33 0.25 0.20 0.33 0.25 0.20 0.17 0.25 0.20 0.17 0.14 0.20 0.17 0.14 0.13 ---- Step4: ---- B2+C2: 1.50 2.33 3.25 4.20 1.33 2.25 3.20 4.17 1.25 2.20 3.17 4.14 1.20 2.17 3.14 4.13 Matrix y1: 90.00 90.00 90.00 90.00 Matrix y2: 4.00 4.00 4.00 4.00 ---- Step5: ---- Matrix y3: 15.85 26.85 38.28 49.90 15.85 26.85 38.28 49.90 15.85 26.85 38.28 49.90 15.85 26.85 38.28 49.90 y1^*y1: 32400.00 y2*y2^: 16.00 16.00 16.00 16.00 16.00 16.00 16.00 16.00 16.00 16.00 16.00 16.00 16.00 16.00 16.00 16.00 ---- Step6: ---- y3^2: 2074.48 3514.19 5009.98 6531.49 2074.48 3514.19 5009.98 6531.49 2074.48 3514.19 5009.98 6531.49 2074.48 3514.19 5009.98 6531.49 y1'*y1*Y3: 513540.00 869940.00 1240225.71 1616875.71 513540.00 869940.00 1240225.71 1616875.71 513540.00 869940.00 1240225.71 1616875.71 513540.00 869940.00 1240225.71 1616875.71 Y3+y2y2': 31.85 42.85 54.28 65.90 31.85 42.85 54.28 65.90 31.85 42.85 54.28 65.90 31.85 42.85 54.28 65.90 ---- Step7: ---- y1'*y1*Y3^2: 67213215.64 113859611.36 162323399.11 211620158.22 67213215.64 113859611.36 162323399.11 211620158.22 67213215.64 113859611.36 162323399.11 211620158.22 67213215.64 113859611.36 162323399.11 211620158.22 Y3+y1'*y1*Y3^2+y2y2': 67213247.49 113859654.21 162323453.39 211620224.12 67213247.49 113859654.21 162323453.39 211620224.12 67213247.49 113859654.21 162323453.39 211620224.12 67213247.49 113859654.21 162323453.39 211620224.12 y1'*y1*Y3+Y3^2: 515614.48 873454.19 1245235.70 1623407.20 515614.48 873454.19 1245235.70 1623407.20 515614.48 873454.19 1245235.70 1623407.20 515614.48 873454.19 1245235.70 1623407.20 ---- Step8: ---- y2'*(Y3+y1'*y1*Y3^2+y2y2'): 1075411959.90 1821754467.30 2597175254.30 3385923586.00 y1'*(y1'*y1*Y3+Y3^2): 185621213.51 314443506.79 448284850.47 584426592.23 x=1261033173.40 2136197974.10 3045460104.70 3970350178.20 4.  Висновки В роботі використано паралелізм на рівні підзадач, оскільки передбачається, що кожен блок зі схеми декомпозиції є реалізований у виді функції. Це є середньоблоковий паралелізм. Обмін даними відбувається через використання спільних змінних. Присутня залежність даних між різними рівнями декомпозиції, але в межах одного рівня її немає. Найбільш раціональним є використання 3х процесорів, при вирішенні цієї задачі простій процесорів спостерігається тільки на останньому кроці.