Міністерство освіти і науки
Національний університет “Львівська політехніка”
Кафедра ЕОМ
/
Звіт
з лабораторної роботи № 2
з дисципліни: “Паралельні та розподілені обчислення”
на тему: “Паралельне представлення алгоритмів”
Мета лабораторної роботи
Вивчити можливості паралельного представлення алгоритмів. Набути навиків такого представлення.
Теоретичні відомості
1. Векторизація
Це процес генерації паралельних машинних кодів на основі послідовного алгоритму, записаного на деякій мові програмування. Вона виконується, як правило векторизуючим компілятором (автоматично) і полягає у виявленні та аналізі залежностей між операторами з метою паралельного виконання незалежних, невпорядкованих дій.
2. Пряме представлення паралельних алгоритмів
2.1. Кадр – опис обислювальних дій в конкретний момент часу. Кадри є найбільш природнім засобом представлення алгоритму, за допомогою якого розробник може перевірити певний математичний алгоритм.
2.2. Програма з одноразовим присвоєнням – це форма, в якій кожній змінній присвоюється лише одне значення при виконанні алгоритму.
Приклад.
Розглянемо задачу множення матриці на вектор, яка описується формулою:
(1)
Безпосередня реалізація на послідовній мові програмування (в даному випадку – на мові СІ) має вигляд:
for (i=0; i<N;i++)
{
c[i]=0;
for (j=0; j<N; j++)
c[i]=c[i]+A[i][j]*b[j];
}
В цій програмі с[і] переписується багато разів з метою економії пам’яті. Таким чином, значення с[і] присвоюється більше одного разу. При перетворенні цієї ж програми в програму з одноразовим присвоюванням кількість індексів векора с – зросте:
for (i=0; i<N;i++)
{
c[i][0]=0;
for (j=0; j<N; j++)
c[i][j+1]=c[i][j]+A[i][j]*b[j];
}
Тепер, кожному елементу вектора с буде присвоєно лише одне значення, а остаточні значення будуть отримані на останньому кроці ітерації.
2.3. Рекурсивний алгоритм –це алгоритм, який визначається за допомогою правила одноразового присвоювання і є стислим представленням багатьох алгоритмів. Побудова рекурсивного алгоритму зводиться до виведення рекурсивних рівнянь. Дії паралельних алгоритмів адекватно описуються в рекурсивних рівняннях з просторово-часовими індексами якщо один індекс використовується для часу, а інші – для простору (надалі – індексний простір).
Приклад.
Для випадку множення матриці на вектор, рекурсивне рівняння буде мати вигляд:
(2)
j – індекс рекурсії.
2.4. Граф залежностей (ГЗ) - це граф, який описує залежність обчислень в алгоритмі. ГЗ може розглядатися як графічне представлення алгоритму з одноразовим присвоєнням. ГЗ називається повним, якщо він визначає всі залежності між всіма змінними в індексному просторі. Переважно, операції в вузлах графу не розкриваються, оскільки будуть виконуватися незалежними обчислювальними засобами (часто – процесорними елементами) і граф є скороченим..
Приклад. Для обчислення (1), виходячи з наведеного алгоритму з одноразовим присвоєнням очевидно, що с[і][j+1] безпосередньо залежить від с[і][j], А[і][j], в[j]. Представивши кожну залежність у вигляді дуги між відповідними змінними, що розташовані в індексному просторі, можна отримати ГЗ:
ГЗ для множення матриці на вектор (для N=4) з глобальним зв’язком.
З нього видно, що значення b[j] кожного елемента вектора b має бути розповсюджене у всі індексні точки, що мають однаковий індекс j. Цей тип даних називається “поширюваними” даними. Це означає, що має бути глобальний зв’язок, що не завжди прийнятна умова для обчислювальної системи.
Можна стверджувати, що алгоритм є зчисленним, якщо його повний граф не містить петель і циклів
Локалізований Граф Залежностей. Алгоритм є локалізований, якщо всі змінні безпосередньо залежать лише від змінних в сусідніх вузлах. Дані, що пересилаються незмінними до всіх вершин графу називаються передаваними, в іншому випадку – це непередавані дані.
Приклад. Програма для локалізованого алгоритму має вигляд (b[0][j]=b[j]):
for (i=0; i<N;i++)
{
c[i][0]=0;
for (j=0; j<N; j++)
b[i+1][j]=b[i][j]
c[i][j+1]=c[i][j]+A[i][j]*b[i][j...
