Міністерство Освіти і Науки України Національний Університет “Львівська Політехніка” Кафедра ЕОМ
ЗВІТ до лабораторної роботи № 2 з курсу “Паралельні та розподілені обчислення ” Тема: ПАРАЛЕЛЬНЕ ПРЕДСТАВЛЕННЯ АЛГОРИТМІВ. Мета: Вивчити можливості паралельного представлення алгоритмів. Набути навиків такого представлення. Аналіз завдання Завдання: Варіант №25 Матриця А задається однозначно і залежить лише від розмірності даних. 100…001 110…011 ………… 110…011 100…001 Для матриці В: заштрихована область – довільні цілі числа, відмінні від нуля, а не заштрихована область – нулі. Запропонувати та реалізувати локально-рекурсивний алгоритм обчислення виразу:
, де А та В матриці з елементами
та
, відповідно(
), тобто:
(
) . Результати виконання роботи: Текст програми з одноразовим присвоюванням: if (radioButton1.Checked) { int oper1 = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { matrC[i, j] = 0; for (int l = 0; l < N; l++) { matrC[i, j]=matrC[i,j]+matrA[i, l] * matrB[l, j]; oper1++; } label3.Text += Convert.ToString(matrC[i, j]) + " "; } label3.Text += Environment.NewLine; } textBox2.Text += oper1; } Рекурсивні рівняння:


j – індекс рекурсії. Локалізований граф залежностей:
Аналітичні оцінки кількості арифметичних операцій та їх порівняння: Під час множення матриць з одноразовим присвоєнням програма потребує багато пам’яті і її виконання вимагає більше часу та арифметичних операцій множення на нуль та додавання до нуля і навпаки. Таким чином складність алгоритму сягає О3 для N розмірності матриць. Якщо матриця має розміри 3x3(NxN) то О3=27 арифетичних операцій для множення двох матриць. Під час оптимізованого множення матриць кількість індексів зменшується через те що не виконується множення на нуль, відповідно програма вимагає менше ресурсів для її виконання кількість арифметичних операцій зменшується майже на половину для N=3, Складність О=15. текст програми, що реалізовує оптимізований локально-рекурсивний алгоритм: if (radioButton2.Checked) { int oper = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { for (int l = 0; l < N; l++) { if (matrA[i, l] == 0 || matrB[l, j] == 0) { continue; } else { matrC[i, j] += matrA[i, l] * matrB[l, j]; oper++; } } label3.Text += Convert.ToString(matrC[i, j]) + " "; } label3.Text += Environment.NewLine; } textBox2.Text += oper; } Результат роботи програми на довільному наборі вхідних даних, для розмірності n≥3:
Висновки: Під час виконання даної лабораторної роботи вивчив можливості паралельного представлення алгоритмів. Набув навиків такого представлення. В результаті виконання обчислень виявилося що оптимізований локально-рекурсивний алгоритм працює швидше та потребує менше ресурсів.