Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ПАРАЛЕЛЬНЕ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2010
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Паралельні та розподілені обчислення
Група:
КІ-44
Частина тексту файла (без зображень, графіків і формул):
Міністерство Освіти і Науки України
Національний Університет “Львівська Політехніка”
Кафедра ЕОМ
ЗВІТ
до лабораторної роботи № 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:
Висновки: Під час виконання даної лабораторної роботи вивчив можливості паралельного представлення алгоритмів. Набув навиків такого представлення. В результаті виконання обчислень виявилося що оптимізований локально-рекурсивний алгоритм працює швидше та потребує менше ресурсів.
19.11.2012 18:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора