паралельні та розподілені обчислення Лабораторна робота № 1 ВИКОРИСТАННЯ ФУНКЦІОНАЛЬНОЇ ДЕКОМПОЗИЦІЇ ДЛЯ РОЗВ’ЯЗКУ ОБЧИСЛЮВАЛЬНИХ ЗАДАЧ. МЕТА РОБОТИ. Вивчити методи декомпозицій задач. Набути навиків розв’язування задач з використанням функціональної декомпозиції. ТЕОРЕТИЧНІ ВІДОМОСТІ. Найважливішим та найважчим етапом при створенні програми є розробка алгоритму, особливо, якщо мова йде про паралельний алгоритм. Процес створення паралельного алгоритму можна розбити на чотири кроки. 1. Декомпозиція. На цьому етапі вихідна задача аналізується, оцінюється можливість її розпаралелювання. Іноді виграш від розпаралелення може бути незначним, а трудоємкість розробки паралельної програми велика. В цьому випадку перший крок розробки алгоритму виявляється і останнім. Якщо ж ситуація відмінна від описаної, то задача та пов’язані з нею дані розділяються на дрібніші частини – підзадачі і фрагменти структур даних. Особливості архітектури конкретної обчислювальної системи на цьому етапі можуть не враховуватися. 2. Проектування комунікацій(обміну даними) між задачами. На цьому етапі визначаються зв’язки, необхідні для пересилання вхідних даних, проміжних результатів виконання підзадач, а також комунікації, що необхідні для керування роботою під задач. Обираються методи та алгоритми комунікацій. 3.Укрупнення. Підзадачі можуть об’єднуватися у більші блоки, якщо це дозволяє підвищити ефективність алгоритму і знизити трудоємкість розробки. Основними критеріями на даному кроці є ефективність алгоритму (в першу чергу продуктивність) та трудоємкість його реалізації. 4. Планування обчислень. На цьому кроці виконується розподіл під задач між процесорами. Основний критерій вибору способу розміщення під задач – ефективне використання процесорів з мінімальними затратами часу на обмін даними. Декомпозиція (сегментування). На цьому етапі визначається степінь можливого розпаралелення задачі. Іноді декомпозиція поставленої задачі природним чином випливає з самої задачі тому є очевидною, іноді – ні. Чим менший розмір підзадач, отриманих в результаті декомпозиції, чим більша їх кількість, тим гнучкішим виявляється паралельний алгоритм і тим легше забезпечити рівномірне завантаження процесорів обчислювальної системи. Надалі, можливо доведеться укрупнити алгоритм, оскільки слід прийняти до уваги інтенсивність обміну даними та інші фактори. Сегментувати можна як обчислювальний алгоритм, так і дані. Застосовуються різні варіанти декомпозиції. В методі декомпозиції даних спочатку сегментуються дані, а потім алгоритм їх обробки. Дані розбиваються на сегменти приблизно однакового розміру. З фрагментами даних пов’язуються операції їх обробки, з яких і формуються підзадачі. Визначаються необхідні правила обміну даними. Перекриття частин, на які розбивається задача, повинне бути мінімальним. Це дозволяє уникнути дублювання обчислень. Схема розбиття може в подальшому уточнюватися. Іноді, якщо це необхідно для зменшення кількості обмінів, допускається збільшення степені перекриття фрагментів задачі. При декомпозиції даних спочатку аналізуються структури даних найбільшого розміру, або ті, до яких найчастіше відбувається звертання. На різних стадіях розрахунків можуть використовуватися різні структури даних, тому можуть бути необхідними динамічні, тобто такі, що міняються в часі схеми декомпозиції цих структур. В методі функціональної декомпозиції спочатку сегментується обчислювальний алгоритм, а потім під цю схему підбирається схема декомпозиції даних. Успіх у цьому випадку не завжди гарантовано, оскільки схема може вимагати багатьох додаткових пересилань даних. Цей метод декомпозиції може виявитися корисним у випадку, якщо немає структур даних, які б могли бути розпаралелені очевидним чином. Функціональна декомпозиція відіграє важливу роль і як метод структурування програм. Вона може виявитися корисною при моделюванні складних систем, що складаються з множини простих підсистем, зв’язаних між собою набором інтерфейсів. Розмір блоків, з яких складається паралельна програма, може бути різним. В залежності від розміру блоків, алгоритм може мати різну “зернистість”. Її виміром в найпростішому випадку є кількість операцій у блоці. Виділяють три степені зернистості: дрібнозернистий, середньоблоковий та великоблоковий. Зернистість пов’язана з рівнем паралелізму. Паралелізм на рівні команд найбільш дрібнозернистий. Його масштаб менше ніж 20 команд на блок. Кількість підзадач, що паралельно виконуються – від однієї до кількох тисяч, при чому середній масштаб паралелізму складає біля п’яти команд на блок. Наступний рівень - паралелізм на рівні циклів. Переважно, цикл містить не більше 500 команд. Якщо ітерації циклу незалежні, вони можуть виконуватися, наприклад за допомогою конвеєра або на векторному процесорі. Це також дрібнозернистий паралелізм. Паралелізм на рівні підзадач – середньоблоковий. Розмір блоку – до 2000 команд. Виконання такого паралелізму реалізувати важче, оскільки слід враховувати можливі міжпроцедурні залежності. Вимоги до комунікацій менші, ніж у випадку паралелізму на рівні команд. Паралелізм на рівні програм (задач) – великоблоковий. Він означає виконання незалежних програм на паралельному комп’ютері. Великоблоковий паралелізм повинен підтримуватися операційною системою. Обмін даними через спільні/розподілені змінні використовується на рівнях дрібнозернистого і середньоблокового паралелізму, а на великоблоковому – засобами передачі повідомлень. Досягнути ефективності роботи паралельної програми можна, якщо збалансувати зернистість алгоритму і затрати часу на обмін даними. Частини програми можуть виконуватися паралельно, лише якщо вони незалежні. Незалежність за даними полягає в тому, що дані, які обробляються однією частиною програми не модифікуються іншою її частиною. Незалежність за керуванням полягає в тому, що послідовність виконання частин програми може бути визначена лише під час виконання програми(наявність залежності по виконанню наперед визначає порядок виконання). Незалежність за ресурсами забезпечується достатньою кількістю комп’ютерних ресурсів(об’єм пам’яті, кількість функціональних вузлів та ін.). Залежність за виводом виникає, якщо дві підзадачі виконують запис в одну і ту ж змінну. А залежність за вводом/виводом, якщо оператори вводу/виводу двох чи декількох під задач звертаються до одного файлу(чи змінної). Дві підзадачі можуть виконуватися паралельно, якщо вони незалежні за даними, за керуванням і за операціями вводу виводу. ЗАВДАННЯ. Використовуючи метод функціональної декомпозиції, розробити алгоритм обчислення запропонованого матрично-векторного виразу, який би враховував можливість паралельного виконання і був оптимальним з точки зору часових затрат. На основі створеного алгоритму написати програму яка дозволяє обчислити вираз та ілюструє проведену декомпозицію. ПОРЯДОК ВИКОНАННЯ РОБОТИ Проаналізувати, наведені нижче, правила обрахунку елементів виразу; Провести декомпозицію задачі, виходячи з можливості паралельного виконання окремих підзадач; Об’єднати отримані проміжні результати і обрахувати кінцевий вираз; Написати і продемонструвати програму обчислення виразу; Визначити паралелізм якого рівня присутній в алгоритмі та зробити висновки щодо залежностей даних, керування, ресурсів, вводу/виводу; Скласти звіт про виконану роботу. ЗМІСТ ЗВІТУ 1.Тема, мета, аналіз завдання(згідно варіанту). 2. Схема декомпозиції задачі та коментарі до неї. 3. Текст програми та результат її роботи на довільному наборі вхідних даних, для розмірності n>3. 4. Висновки. Вагомі зауваження. а) Окрім безпосередніх обчислень, програма повинна мати інтерфейс користувача, який забезпечує: ввід(з клавіатури) розмірності даних (n); можливість вибору–ввід даних(тобто елементів матриці та векторів) з клавіатури чи генерування їх випадковим чином; вивід на екран (або у файл) проміжних результатів за потребою користувача; обов’язковий вивід остаточних результатів на екран і у файл у зрозумілому вигляді. б) Всі вхідні дані є цілими числами, більшими за нуль. в) Необхідно знайти такі коефіцієнт нормалізації результатів(тобто пониження чи підвищення їх порядку). Правила знаходження елементів виразу. 1).Задати* квадратну матрицю А порядку n. Отримати вектор(стовпець) , де b – вектор-стовпець, елементи якого обраховуються за формулою, згідно варіанту. 2).Задати квадратну матрицю А1 порядку n та вектори-стовпці b1 та c1 з n елементами кожен. Отримати вектор згідно формули, що задається варіантом. 3).Задати квадратні матриці А2 та B2 порядку n. Отримати матрицю , яка залежить від А2, B2 та додатково визначеної матриці С2, елементи якої знаходяться за формулою, вказаною варіантом. ЛІТЕРАТУРА С.Немногин О.Стесик “Параллельное программирование для многопроцессорних систем” Петербург “БХВ-Петербург”, 2002 Томас Бройнль “Паралельне програмування. Початковий курс”Київ "Вища школа, 1997 ВАРІАНТИ ЗАВДАНЬ. При чому: означає операцію транспонування; i,j=1…n (n – вхідна розмірність). 25 стовпець
bi=13/(i+2) для парних і bi=13/i2 для непарних і A1b1-c1 A2-B2C2 Cij=13/(i2+j2)
26 матриця
bi=14/(i3) для парних і bi=1/(i+14) для непарних і A1(14b1+14c1) A2C2-B2 Cij=14/(i+j4)
27 рядок
bi=i для парних і bi=15/i для непарних і 15A1b1+c1 A2С2+B2 Cij=15/(i2+j)
28 число
bi=16/(i3) A1(b1+16c1) A2(B2+16C2) Cij=16/(i+j)2
29 матриця
bi=17/i2 A1(17b1+c1) A2(B2+C2) Cij=17/(2i+j)
30 матриця
bi=18/(i+18)2 A1(b1-c1) A2B2-A2C2 Cij=18/(i+2j)
31 число
bi=19/(i2+1) для парних і bi=19 для непарних і A1(b1+19c1) A2(B2+C2) Cij=19/(i+2j)3
32 число
bi=20/(i3+20) A1(20b1-c1) A2C2- B 2 Cij=20/(i3-j3+2)
33 рядок
bi=21/i4 A1(b1+20c1) A2B2-C2 Cij=21/(i2+2j)
34 стовпець
bi=22i для парних і bi=22 для непарних і A1(b1-21c1) A2(B2-C2) Cij=22/(i+j)
35 матриця
bi=23/i для парних і bi=23/i2 для непарних і A1(b1+c1) A2(23B2+C2) Cij=23/(3i+j)2
ВАРІАНТИ ЗАВДАНЬ. При чому: означає операцію транспонування; i,j=1…n (n – вхідна розмірність). 36 матриця
bi=1/(i2+2) для парних і bi=1/i для непарних і A1(b1+c1) A2(B2-C2) Cij=1/(i+2j)
37 матриця
bi=1/(i2+2+i) для парних і bi=1/i для непарних і A1(b1+2c1) A2(C2-B2) Cij=1/(i+j)
38 рядок
bi=3/(i2+3) для парних і bi=3/i для непарних і A1(3b1+c1) A2(B2-C2) Cij=1/(i+j)2
ВАРІАНТИ ЗАВДАНЬ. При чому: означає операцію транспонування; i,j=1…n (n – вхідна розмірність). 69 число
bi=24/(i2+4) для парних і bi=24 для непарних і A1(b1-24c1) A2(B2+24C2) Cij=24/(i+3j2)
70 число
bi=25 для парних і bi=25/i3 для непарних і A1(b1+c1) A2(B2+C2) Cij=25/(i+j)3
71 число
bi=26i3 A1(26b1-c1) A2(B2+26C2) Cij=1/(i2+j)
72 матриця
bi=27/i2 A1(27b1-26c1) A2(27B2+C2) Cij=1/(i+j)3
73 число
bi=28i A1(b1+28c1) A2(B2-28C2) Cij=1/(i3+j2)
74 стовпець
bi=29/i A1(29b1+3c1) A2(29B2-C2) Cij=1/(i+j+2)
75 рядок
bi=30/i для парних і bi=30/i2 для непарних і A1(b1-c1) A2(B2+C2) Cij=30/(i+j)
Приклад виконання роботи. Завдання: Вираз, який слід обрахувати, заданий наступним чином:
При чому елементи визначаються згідно правил: , де , і=1,2,...n
, де Послідовність виконання. 1. Аналіз завдання. Для заданого виразу вхідними даними є: розмірність матриць – n; матриці ; вектори-стовпці . Ці параметри повинні вводитися з клавіатури, або генеруватися випадковим чином (крім розмірності). При чому, елементи всіх матриць та векторів є цілими додатними числами, більшими за нуль. Вектор-стовпець та матриця обраховуються, виходячи з уведеної розмірності, зауважимо, що значення їх елементів завжди менші одиниці і різко спадають зі збільшенням розмірності. Наприклад для n=3, значення вектора-стовпця будуть становити: ; ; ,а значення матриці , відповідно:
. При утворенні враховуємо, що результатом множення матриці А на вектор-стовпець b є вектор-стовпець, елементи якого будуть раціональними числами(тобто матимуть значущу дробову частину). При утворенні враховуємо, що результатом віднімання двох векторів-стовпців є вектор-стовпець, елементи якого можуть бути меншими за нуль цілими числами. Далі, при множенні цілочисельної додатної матриці А1 на результат віднімання, отримаємо вектор-стовпець з цілочисельними елементами довільного знаку. При утворенні враховуємо, що присутні лише операції додавання та множення, а тому вихідний результат завжди буде додатнім і завжди матиме значущу дробову частину. Таким чином, згідно поставленої задачі, в обчисленні загального виразу приймають участь три різні елементи – два вектори стовпці та матриця .
Перший доданок загального виразу містить три множники – транспонований вектор-стовпець ,(тобто вектор-рядок), вектор-стовпець та матрицю піднесену до квадрату. Оскільки, згідно правил матричних обчислень, добуток не є комутативною операцією, всі множення слід виконувати в тій послідовності, яка задана. Результатом множення рядка на стовпець є число, а матриці на матрицю - матриця. Тому, в загальному, перший доданок буде матрицею. Аналогічний аналіз можна застосувати до всіх решти доданків даного виразу. Другий доданок повністю повторює перший, третій доданок – рядок (матрицю=рядок, рядок ( стовпець=число, число ( матрицю = матриця. Таким чином, з попереднього випливає, що остаточний результат є матрицею, елементи якої можуть бути як додатними так і від’ємними і завжди мають дробову частину. 2. Декомпозиція задачі. Однозначно, всі обчислення безпосередньо залежать від розмірності даних, тому найперше, слід забезпечити ввід змінної n, що визначає цю розмірність. Далі, можна паралельно виконувати обчислення значень вектора b та матриці С2, оскільки вони незалежні від інших параметрів. Крім того, на тому ж рівні декомпозиції слід визначати вхідні дані, тобто вводити з клавіатури, або генерувати випадковим чином матриці та вектори-стовпці . Наступний рівень декомпозиції – це знаходження елементів виразу. Значення залежить від введеної матриці А та обрахованого вектора b. Значення залежить від введеної А1 та різниці векторів b1 і c1, тому знайти його можна лише після обчислення (b1 - c1). Зауважимо, що множення на константу не є окремою операцією, як і транспонування векторів. Аналогічно, знаходимо . Подальша декомпозиція відбувається згідно заданої послідовності операцій та врахування залежностей отриманих на кожному рівні даних. Повна схема декомпозиції обчислення заданого виразу приведена нижче. 3. Об’єднання частин виразу проведено безпосередньо у схемі декомпозиції, оскільки воно однозначно визначається порядком обчислень. 4. Для написання програми, що ілюструє процес обчислення виразу згідно розробленої схеми декомпозиції, слід врахувати наступні особливості: Дані, що вводяться з клавіатури, або генеруються випадковим чином повинні бути цілими числами, більшими за нуль. Результати проміжних обрахунків будуть містити дробову частину, виняток складає лише елемент y2. Тому слід обирати відповідний тип даних(багатобайтний). Оскільки на окремо взятому рівні декомпозиції обраховуються незалежні частини підвиразів, функції що їх програмно реалізують повинні викликатися псевдо-одночасно.(Тобто перш ніж виконувати будь яку функцію третього рівня, слід виконати всі функції другого рівня і т.д.) Для того, щоб результат загального виразу був співмірний з вхідними даними, слід нормувати отримані значення, визначивши тим самим порядок результату.
Схема декомпозиції обчислення виразу 5. Висновки В роботі використано паралелізм на рівні підзадач, оскільки передбачається, що кожен блок зі схеми декомпозиції є реалізований у виді функції. Це є середньоблоковий паралелізм. Обмін даними відбувається через використання спільних змінних. Присутня залежність даних між різними рівнями декомпозиції, але в межах одного рівня її немає. Є залежність за керуванням, оскільки послідовність обчислювального процесу наперед однозначно відома. Залежність за ресурсами та вводом/виводом може бути визначена лише у відношенні до певної обчислювальної системи.
