Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Лабораторна робота 1
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних технологій, автоматики та метрології
Факультет:
Не вказано
Кафедра:
Компютерна інженерія
Інформація про роботу
Рік:
2019
Тип роботи:
Лабораторна робота
Предмет:
Паралельні та розподілені обчислення
Варіант:
8 18 7
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
КАФЕДРА ЕОМ
/
Звіт
з лабораторної роботи №1
здисципліни
"Паралельні та розподілені обчислення"
Підготував:
Прийняв: Козак Н. Б.
Львів-2019
Мета роботи: вивчити методи декомпозицій задач,набути навиків розв’язування задач з використанням функціональної декомпозиції
ТЕОРЕТИЧНІ ВІДОМОСТІ.
Найважливішим та найважчим етапом при створенні програми є розробка алгоритму, особливо, якщо мова йде про паралельний алгоритм. Процес створення паралельного алгоритму можна розбити на чотири кроки.
1. Декомпозиція. На цьому етапі вихідна задача аналізується, оцінюється можливість її розпаралелювання. Іноді виграш від розпаралелення може бути незначним, а трудоємкість розробки паралельної програми велика. В цьому випадку перший крок розробки алгоритму виявляється і останнім. Якщо ж ситуація відмінна від описаної, то задача та пов’язані з нею дані розділяються на дрібніші частини – підзадачі і фрагменти структур даних. Особливості архітектури конкретної обчислювальної системи на цьому етапі можуть не враховуватися.
2. Проектуваннякомунікацій(обмінуданими) між задачами. На цьомуетапівизначаютьсязв’язки, необхідні для пересиланнявхіднихданих, проміжнихрезультатіввиконанняпідзадач, а такожкомунікації, щонеобхідні для керуванняроботоюпід задач. Обираютьсяметоди та алгоритмикомунікацій.
3.Укрупнення. Підзадачі можуть об’єднуватися у більші блоки, якщо це дозволяє підвищити ефективність алгоритму і знизити трудоємкість розробки. Основними критеріями на даному кроці є ефективність алгоритму (в першу чергу продуктивність) та трудоємкість його реалізації.
4. Планування обчислень. На цьому кроці виконується розподіл під задач між процесорами. Основний критерій вибору способу розміщення під задач – ефективне використання процесорів з мінімальними затратами часу на обмін даними.
Декомпозиція (сегментування).
На цьому етапі визначається степінь можливого розпаралелення задачі. Іноді декомпозиція поставленої задачі природним чином випливає з самої задачі тому є очевидною, іноді – ні. Чим менший розмір підзадач, отриманих в результаті декомпозиції, чим більша їх кількість, тим гнучкішим виявляється паралельний алгоритм і тим легше забезпечити рівномірне завантаження процесорів обчислювальної системи. Надалі, можливо доведеться укрупнити алгоритм, оскільки слід прийняти до уваги інтенсивність обміну даними та інші фактори. Сегментувати можна як обчислювальний алгоритм, так і дані. Застосовуються різні варіанти декомпозиції.
В методі декомпозиції даних спочатку сегментуються дані, а потім алгоритм їх обробки. Дані розбиваються на сегменти приблизно однакового розміру. З фрагментами даних пов’язуються операції їх обробки, з яких і формуються підзадачі. Визначаються необхідні правила обміну даними. Перекриття частин, на які розбивається задача, повинне бути мінімальним. Це дозволяє уникнути дублювання обчислень. Схема розбиття може в подальшому уточнюватися. Іноді, якщо це необхідно для зменшення кількості обмінів, допускається збільшення степені перекриття фрагментів задачі.
При декомпозиції даних спочатку аналізуються структури даних найбільшого розміру, або ті, до яких найчастіше відбувається звертання. На різних стадіях розрахунків можуть використовуватися різні структури даних, тому можуть бути необхідними динамічні, тобто такі, що міняються в часі схеми декомпозиції цих структур.
В методі функціональної декомпозиції спочатку сегментується обчислювальний алгоритм, а потім під цю схему підбирається схема декомпозиції даних. Успіх у цьому випадку не завжди гарантовано, оскільки схема може вимагати багатьох додаткових пересилань даних. Цей метод декомпозиції може виявитися корисним у випадку, якщо немає структур даних, які б могли бути розпаралелені очевидним чином. Функціональна декомпозиція відіграє важливу роль і як метод структурування програм. Вона може виявитися корисною при моделюванні складних систем, що складаються з множини простих підсистем, зв’язаних між собою набором інтерфейсів.
Розмір блоків, з яких складається паралельна програма, може бути різним. В залежності від розміру блоків, алгоритм може мати різну “зернистість”. Її виміром в найпростішому випадку є кількість операцій у блоці. Виділяють три степені зернистості: дрібнозернистий, середньоблоковий та великоблоковий. Зернистість пов’язана з рівнем паралелізму.
Паралелізм на рівні команд найбільш дрібнозернистий. Його масштаб менше ніж 20 команд на блок. Кількість підзадач, що паралельно виконуються – від однієї до кількох тисяч, при чому середній масштаб паралелізму складає біля п’яти команд на блок.
Наступний рівень - паралелізм на рівні циклів. Переважно, цикл містить не більше 500 команд. Якщо ітерації циклу незалежні, вони можуть виконуватися, наприклад за допомогою конвеєра або на векторному процесорі. Це також дрібнозернистий паралелізм.
Паралелізм на рівні підзадач – середньоблоковий. Розмір блоку – до 2000 команд. Виконання такого паралелізму реалізувати важче, оскільки слід враховувати можливі міжпроцедурні залежності. Вимоги до комунікацій менші, ніж у випадку паралелізму на рівні команд.
Паралелізм на рівні програм (задач) – великоблоковий. Він означає виконання незалежних програм на паралельному комп’ютері. Великоблоковий паралелізм повинен підтримуватися операційною системою.
Обмінданими через спільні/розподіленізміннівикористовується на рівняхдрібнозернистого і середньоблоковогопаралелізму, а на великоблоковому – засобамипередачіповідомлень.
Досягнути ефективності роботи паралельної програми можна, якщо збалансувати зернистість алгоритму і затрати часу на обмін даними.
Частини програми можуть виконуватися паралельно, лише якщо вони незалежні.
Незалежність за данимиполягаєв тому, щодані, якіобробляютьсяоднієючастиноюпрограми не модифікуютьсяіншоюїїчастиною.
Незалежність за керуваннямполягає в тому, щопослідовністьвиконаннячастинпрограмиможе бути визначеналишепід час виконанняпрограми(наявністьзалежності по виконанню наперед визначає порядок виконання).
Незалежність за ресурсамизабезпечуєтьсядостатньоюкількістюкомп’ютернихресурсів(об’ємпам’яті, кількістьфункціональнихвузлів та ін.).
Залежність за виводомвиникає,якщодвіпідзадачівиконуютьзапис в одну і ту ж змінну. А залежність за вводом/виводом, якщооператори вводу/виводудвохчидекількохпід задач звертаються до одного файлу(чизмінної).
Двіпідзадачіможутьвиконуватисяпаралельно, якщо вони незалежні за даними, за керуванням і за операціями вводу виводу.
ЗАВДАННЯ.
Використовуючи метод функціональноїдекомпозиції, розробити алгоритм обчисленнязапропонованогоматрично-векторноговиразу, якийбивраховувавможливістьпаралельноговиконання і бувоптимальним з точки зоручасових затрат.
Наосновіствореного алгоритму написатипрограму яка дозволяєобчислитивираз та ілюструєпроведенудекомпозицію.
Варіант №8
8
стовпець
bi=8/i
A1(2b1+3c1)
A2(B2-C2)
Cij=1/(i+j+2)
ВИКОНАННЯ РОБОТИ.
Створимо схему декомпозиції обчислення виразу:
bi=8/i Cij=1/(i+j+2) A1(2b1+3c1) A2(B2-C2)
n = input('n = '); %n - ñòâîðþºòüñÿ çì³íàííà,¿¿ òèì âèçíà÷àºòüñÿ çã³äíî ç òèì ùî ¿é ïðèñâîþºòüñÿ, ìîæå áóòè ÷èñëî, âåêòîð, ìàòðèöÿ, ðÿäîê
r = input('Ùîá çàäàòè ìàñèâè âðó÷íó ââåä³òü 1, ðàíäîìîì 2: '); %input() ôóíêö³ÿ äëÿ ç÷èòóâàííÿ çíà÷åííÿ ç êëàâ³àòóðè, ïàðàìåòðîì º ðÿäîê ÿêèé áóäå âèâîäèòèñü
if (r == 2) %if - îïåðàòîð if çàê³í÷óºòüñÿ îïåðàòîðîì end
A = randi(10,n,n); %A - çì³ííà, randint - ãåíåðàö³ÿ ìàñèâó ö³ëèõ ÷èñåë, ïàðàìåòðè n - ê-ñòü ðÿäê³â, n - ê-ñòü ñòîâïö³â, 10 - ä³àïàçîí ÷èñåë ùî ãåíåðóþòüñÿ 0..10
mess = 'A = '; %mess - ðÿäêîâà çì³ííà äëÿ çàïèñó â ôàéë, âñ³ ðÿäêè çàêëþ÷àþòüñÿ â îäèíàðí³ ëàïêè
dlmwrite('1.txt', mess, 'delimiter', ''); %dlmwrite - ôóíêö³ÿ çàïèñó â ôàéë
dlmwrite('1.txt', A, '-append','delimiter', '\t', 'precision',15); %âîíà ìຠíàñòóïí³ ïàðàìåòðè '1.txt' - ôàéë, A - Çì³ííà ÿêó òðåáà çàïèñàòè,'-append' - äîïèñóâàòè â ôàéë, 'delimiter' - çàäàòè ÿâíî ðîçä³ëþâà÷ äëÿ åëåìåíò³â ìàòðèö³, '\t' - ðîçä³ëþâà÷, 'precision' - çàäàòè òî÷í³ñòü òèïó double, 15 - ÷èñëî ìຠñêëàäàòèñü ç 15 çíàê³â
A1 = randi(10,n,n);
mess = 'A1 = ';
dlmwrite('1.txt', mess,'-append', 'delimiter', '');
dlmwrite('1.txt', A1, '-append','delimiter', '\t', 'precision',15);
b1 = randi(10,n,1);
mess = 'b1 = ';
dlmwrite('1.txt', mess,'-append', 'delimiter', '');
dlmwrite('1.txt', b1, '-append','delimiter', '\t', 'precision',15);
c1 = randi(10,n,1);
mess = 'c1 = ';
dlmwrite('1.txt', mess,'-append', 'delimiter', '');
dlmwrite('1.txt', c1, '-append','delimiter', '\t', 'precision',15);
A2 = randi(10,n,n);
mess = 'A2 = ';
dlmwrite('1.txt', mess,'-append', 'delimiter', '');
dlmwrite('1.txt', A2, '-append','delimiter', '\t', 'precision',15);
B2 = randi(10,n,n);
mess = 'B2 = ';
dlmwrite('1.txt', mess,'-append', 'delimiter', '');
dlmwrite('1.txt', B2, '-append','delimiter', '\t', 'precision',15);
else
A = randi(10,n,n);
A1 = randi(10,n,n);
b = randi(10,n,1);
b1 = randi(10,n,1);
c1 = randi(10,n,1);
A2 = randi(10,n,n);
B2 = randi(10,n,n);
C2 = randi(10,n,n);
for i = 1:n %Âêëàäåíèé öèêë for çìûííà ³ íàáóâຠçíà÷åíü â³ä 1 äî n
for j = 1:n %Âíóòð³øí³é öèêë for çì³ííà j íàáóâຠçíà÷åíü â³ä 1 äî n
A(i,j) = input('A[i,j] = '); %
end%Çàâåðøóº âíóòð³øí³é öèêë
end%Çàâåðøóº çîâí³øí³é öèêë
for i = 1:n
for j = 1:n
A1(i,j) = input('A1[i,j] = ');
end
end
for i = 1:n
b1(i) = input('b1[i] = ');
end
b1 = b1'; % b = b' - îïåðàö³ÿ òðàíñïîíóâàííÿ îïåðàòîð ' òðàíñïîíóº ìàòðèöþ.
for i = 1:n
c1(i) = input('c1[i] = ');
end
c1 = c1';
for i = 1:n
for j = 1:n
A2(i,j) = input('A2[i,j] = ');
end
end
for i = 1:n
for j = 1:n
B2(i,j) = input('B2[i,j] = ');
end
end
end%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
for i = 1:n
b(i) = 8/i;
end
mess = 'b = ';
dlmwrite('1.txt', mess,'-append', 'delimiter', '');
dlmwrite('1.txt', b', '-append','delimiter', '\t', 'precision',15);
y1 = A*b'; %y1 = A*b' - ìíîæåííÿ ìàòðèö³ íà ñòîâáåöü, b - áóëî ðÿäêîì, ï³ñëÿ òðàíñïîíàö³¿ ñòàëî ñòîâïöåì
mess = 'y1 = ';
dlmwrite('1.txt', mess,'-append', 'delimiter', '');
dlmwrite('1.txt', y1, '-append');
temp00 = 2*b1;
temp0 = 3*c1;
temp1 = temp00+temp0;
mess = '2*b1+3*c1 = ';
dlmwrite('1.txt', mess,'-append', 'delimiter', '');
dlmwrite('1.txt', temp1, '-append');
y2 = A1*temp1;
mess = 'y2 = ';
dlmwrite('1.txt', mess,'-append', 'delimiter', '');
dlmwrite('1.txt', y2, '-append');
for i = 1:n
for j = 1:n
C2(i,j) = 1/(i+j+2);
end
end
mess = 'C2 = ';
dlmwrite('1.txt', mess,'-append', 'delimiter', '');
dlmwrite('1.txt', C2, '-append','delimiter', '\t', 'precision',15);
temp2 = B2-C2;
mess = 'B2-C2 = ';
dlmwrite('1.txt', mess,'-append', 'delimiter', '');
dlmwrite('1.txt', temp2, '-append','delimiter', '\t', 'precision',15);
Y3 = A2*temp2;
mess = 'Y3 = ';
dlmwrite('1.txt', mess,'-append', 'delimiter', '');
dlmwrite('1.txt', Y3, '-append','delimiter','\t');
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
temp3 = Y3*Y3;
mess = 'Y3^2 = ';
dlmwrite('1.txt', mess,'-append', 'delimiter', '');
dlmwrite('1.txt', temp3, '-append','delimiter', '\t', 'precision',15);
temp4 = Y3*y1;
mess = 'Y3*y1" = ';
dlmwrite('1.txt', mess,'-append', 'delimiter', '');
dlmwrite('1.txt', temp4, '-append','delimiter', '\t', 'precision',15);
temp5 = y2*y2';
mess = 'y2*y2" = ';
dlmwrite('1.txt', mess,'-append', 'delimiter', '');
dlmwrite('1.txt', temp5, '-append','delimiter', '\t', 'precision',15);
temp6 = y1*y2';
mess = 'y1*y2" = ';
dlmwrite('1.txt', mess,'-append', 'delimiter', '');
dlmwrite('1.txt', temp6, '-append','delimiter', '\t', 'precision',15);
temp7 = y1*y1';
mess = 'y1*y1" = ';
dlmwrite('1.txt', mess,'-append', 'delimiter', '');
dlmwrite('1.txt', temp7, '-append','delimiter', '\t', 'precision',15);
temp8 = temp3*temp5;
mess = 'y2"y2Y3^2 = ';
dlmwrite('1.txt', mess,'-append', 'delimiter', '');
dlmwrite('1.txt', temp8, '-append','delimiter', '\t', 'precision',15);
temp09 = temp4*y2';
temp9 = temp09*y2;
mess = 'Y3y1y2y2" = ';
dlmwrite('1.txt', mess,'-append', 'delimiter', '');
dlmwrite('1.txt', temp9, '-append','delimiter', '\t', 'precision',15);
temp10 = temp8*temp7;
mess = 'y2"y2Y3^2y1*y1" = ';
dlmwrite('1.txt', mess,'-append', 'delimiter', '');
dlmwrite('1.txt', temp10, '-append','delimiter', '\t', 'precision',15);
temp11 = temp10+temp6;
mess = 'y2"y2Y3^2y1*y1"+y1*y2 = ';
dlmwrite('1.txt', mess,'-append', 'delimiter', '');
dlmwrite('1.txt', temp11, '-append','delimiter', '\t', 'precision',15);
temp12 = temp9+y2;
mess = 'Y3y1y2y2"+y2 = ';
dlmwrite('1.txt', mess,'-append', 'delimiter', '');
dlmwrite('1.txt', temp12, '-append','delimiter', '\t', 'precision',15);
x = temp11*temp12;
mess = 'x = (y2"y2Y3^2y1*y1"+y1*y2")(Y3y1y2y2"+y2) = ';
dlmwrite('1.txt', mess,'-append', 'delimiter', '');
dlmwrite('1.txt', x, '-append','delimiter', '\t', 'precision',15);
Результат виконання:
A =
9 10 5
1 7 2
1 3 3
A1 =
3 4 1
4 2 10
2 9 4
b1 =
1
4
8
c1 =
8
6
7
A2 =
9 1 8
1 2 9
4 8 6
B2 =
1 3 8
10 6 9
9 10 5
b =
8
4
2.66666666666667
y1 =
125.33
41.333
28
2*b1+3*c1 =
26
26
37
y2 =
219
526
434
C2 =
0.25 0.2 0.166666666666667
0.2 0.166666666666667 0.142857142857143
0.166666666666667 0.142857142857143 0.125
B2-C2 =
0.75 2.8 7.83333333333333
9.8 5.83333333333333 8.85714285714286
8.83333333333333 9.85714285714286 4.875
Y3 =
87.217 109.89 118.36
99.85 103.18 69.423
134.4 117.01 131.44
Y3^2 =
34486.5109920635 34771.7979478458 33508.5193594104
28341.6022619048 29741.9805782313 28105.9947704082
41070.920952381 42222.2216326531 41306.906377551
Y3*y1" =
18787.2952380952
18723.1793650794
25361.526984127
y2*y2" =
47961 115194 95046
115194 276676 228284
95046 228284 188356
y1*y2" =
27448 65925.3333333333 54394.6666666667
9052 21741.3333333333 17938.6666666667
6132 14728 12152
y1*y1" =
15708.4444444444 5180.44444444444 3509.33333333333
5180.44444444444 1708.44444444444 1157.33333333333
3509.33333333333 1157.33333333333 784
y2"y2Y3^2 =
8844360777.52903 21242619949.6816 17527180718.9388
7456751675.76021 17909823659.5884 14777306973.881
10759605262.1097 25842704876.1173 21322688053.6786
Y3y1y2y2" =
9637750946.07619
9604859952.03016
13010285812.1683
y2"y2Y3^2y1*y1" =
310486081960540 102394346178476 69363911927354.8
261773311853331 86329496462268.9 58481271797020.8
377721778351944 124567820520322 84384652610540.8
y2"y2Y3^2y1*y1"+y1*y2 =
310486081987988 102394346244401 69363911981749.4
261773311862383 86329496484010.2 58481271814959.5
377721778358076 124567820535050 84384652622692.8
Y3y1y2y2"+y2 =
9637751165.07619
9604860478.03016
13010286246.1683
x = (y2"y2Y3^2y1*y1"+y1*y2")(Y3y1y2y2"+y2) =
2.17731051765911e+26
1.22071446884465e+26
1.62385467968726e+26
Висновок: на даній лабораторній роботі я вивчила метод декомпозиції задач,набула навиківрозв’язування задач з використаннямфункціональноїдекомпозиції.
16.10.2020 13:10-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора