Міністерство освіти і науки Національний університет “Львівська політехніка” Кафедра ЕОМ / Звіт з лабораторної роботи № 3 з дисципліни: “Паралельні та розподілені обчислення” на тему: “Паралельне представлення алгоритмів” Мета лабораторної роботи Вивчити можливості паралельного представлення алгоритмів. Набути навиків такого представлення. Теоретичні відомості Можливі два підходи до побудови паралельного представлення алгоритму: Векторизація алгоритму представленого послідовно. Безпосередньо паралельне представлення: Кадри. Програми з одноразовим присвоєнням. Рекурсивні рівняння. Графи залежностей. Завдання Запропонувати та реалізувати локально-рекурсивний алгоритм обчислення виразу:
, де А та В матриці з елементами
та
, відповідно(
), тобто:
(
) . Тип вхідних послідовностей визначається згідно варіанту. Матриця А задається однозначно і залежить лише від розмірності даних. Для матриці В: заштрихована область – довільні цілі числа, відмінні від нуля, а не заштрихована область – нулі. варіант № Тип матриці А Тип матриці В  2 1*2 0 ... 0 0 2*3 ... 0 .... 0 .... n(n+1)    Графи залежностей (n = 4) Локалізований граф залежностей Оптимізований граф залежностей  

  Аналітичні оцінки кількості арифметичних операцій Локально-рекурсивний алгоритм (n = 8): / Локально-рекурсивний оптимізований алгоритм (n = 8): / Тобто операції додавання в оптимізованому алгоритмі не виконуються. Кількість операцій множення в n × 1.8 разів менша, порівняно з неоптимізованим алгоритмом. Результат роботи програми (n = 8) / Висновок Виконуючи лабораторну роботу, я отримав навички паралельного обчислення алгоритмів на базі множення матриць, також навчився реалізовувати алгоритм з одноразовим присвоєнням і локально-рекурсивний алгоритм, який працює на базі локалізованого графа.