МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра ЕОМ Звіт з лабораторної роботи №1 «ВИКОРИСТАННЯ ФУНКЦІОНАЛЬНОЇ ДЕКОМПОЗИЦІЇ ДЛЯ РОЗВ’ЯЗКУ ОБЧИСЛЮВАЛЬНИХ ЗАДАЧ» з дисципліни «Паралельні та розподілені обчислення» МЕТА РОБОТИ. Вивчити методи декомпозицій задач. Набути навиків розв’язування задач з використанням функціональної декомпозиції. ЗАВДАННЯ. Використовуючи метод функціональної декомпозиції, розробити алгоритм обчислення запропонованого матрично-векторного виразу, який би враховував можливість паралельного виконання і був оптимальним з точки зору часових затрат. На основі створеного алгоритму написати програму яка дозволяє обчислити вираз та ілюструє проведену декомпозицію. Вагомі зауваження. а) Окрім безпосередніх обчислень, програма повинна мати інтерфейс користувача, який забезпечує: ввід(з клавіатури) розмірності даних (n); можливість вибору–ввід даних(тобто елементів матриці та векторів) з клавіатури чи генерування їх випадковим чином; вивід на екран (або у файл) проміжних результатів за потребою користувача; обов’язковий вивід остаточних результатів на екран і у файл у зрозумілому вигляді. б) Всі вхідні дані є цілими числами, більшими за нуль. 9 
рядок   bi=9i A1(b1-c1) A2(B2+C2) Cij=1/(i+j)   Аналіз завдання. Для заданого виразу вхідними даними є: розмірність матриць – n; матриці
; вектори-стовпці
. Ці параметри повинні вводитися з клавіатури, або генеруватися випадковим чином (крім розмірності). При чому, елементи всіх матриць та векторів є цілими додатними числами, більшими за нуль. Однозначно, всі обчислення безпосередньо залежать від розмірності даних, тому найперше, слід забезпечити ввід змінної n, що визначає цю розмірність. Далі, можна паралельно виконувати обчислення значень вектора b та матриці С2, оскільки вони незалежні від інших параметрів. Крім того, на тому ж рівні декомпозиції слід визначати вхідні дані, тобто вводити з клавіатури, або генерувати випадковим чином матриці
та вектори-стовпці
. Наступний рівень декомпозиції – це знаходження елементів виразу. Значення
залежить від введеної матриці А та обрахованого вектора b. Значення
залежить від введеної А1 та різниці векторів b1 і c1, тому знайти його можна лише після обчислення (b1 - c1). Зауважимо, що множення на константу не є окремою операцією, як і транспонування векторів. Аналогічно, знаходимо
. Подальша декомпозиція відбувається згідно заданої послідовності операцій та врахування залежностей отриманих на кожному рівні даних. Повна схема декомпозиції обчислення заданого виразу приведена нижче. Об’єднання частин виразу проведено безпосередньо у схемі декомпозиції, оскільки воно однозначно визначається порядком обчислень.
Схема декомпозиції обчислення виразу Висновки В роботі використано паралелізм на рівні підзадач, оскільки передбачається, що кожен блок зі схеми декомпозиції є реалізований у виді функції. Це є середньоблоковий паралелізм. Обмін даними відбувається через використання спільних змінних. Присутня залежність даних між різними рівнями декомпозиції, але в межах одного рівня її немає. Є залежність за керуванням, оскільки послідовність обчислювального процесу наперед однозначно відома. Залежність за ресурсами та вводом/виводом може бути визначена лише у відношенні до певної обчислювальної системи.