паралельні та розподілені обчислення Лабораторна робота № 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]; } в ній b[i+1][j] безпосередньо залежить від b[i][j], а c[i][j+1] від c[i][j], A[i][j], b[i][j]. Відповідний граф залежностей лише з локальними зв’язками має вигляд:
ГЗ для множення матриці на вектор (для N=4) з локальним зв’язком. Виходячи з локалізованого ГЗ можна дати означення: Локально-рекурсивний алгоритм – це алгоритм, відповідний ГЗ якого має лише локальні залежності, тобто розмір задачі не впливає на довжину кожної дуги і більшість вузлів ГЗ складається з операцій одного типу. ЗАВДАННЯ. Запропонувати та реалізувати локально-рекурсивний алгоритм обчислення виразу: , де А та В матриці з елементами та , відповідно(), тобто: () . Тип вхідних послідовностей визначається згідно варіанту. ПОРЯДОК ВИКОНАННЯ РОБОТИ Написати програму з одноразовим присвоюванням. Знайти рекурсивні рівняння (тобто рекурсивний алгоритм). Побудувати граф залежностей та виходячи з нього локалізований граф залежностей. Оптимізувати граф залежностей, врахувавши тип вхідних даних, тобто усунути зайві фрагменти обчислень. Визначити та порівняти кількість арифметичних операцій, що потрібно здійснити при обчисленні виразу за безпосереднім та оптимізованим графами залежностей. Написати програму, що реалізовує локально-рекурсивний алгоритм. Зробити висновок про ефективність обчислень виходячи з графу залежностей. ЗМІСТ ЗВІТУ 1. Тема, мета, аналіз завдання. 2. Результати виконання роботи, тобто: текст програми з одноразовим присвоюванням; рекурсивні рівняння; локалізований граф залежностей; оптимізований граф залежностей; аналітичні оцінки кількості арифметичних операцій та їх порівняння; текст програми, що реалізовує оптимізований локально-рекурсивний алгоритм; результат роботи програми на довільному наборі вхідних даних, для розмірності n?3. 3. Висновки. ЛІТЕРАТУРА С.Немногин О.Стесик “Параллельное программирование для многопроцессорних систем” Петербург “БХВ-Петербург”, 2002 Томас Бройнль “Паралельне програмування. Початковий курс”Київ "Вища школа, 1997
ВАРІАНТИ ЗАВДАНЬ Матриця А задається однозначно і залежить лише від розмірності даних. Для матриці В: заштрихована область – довільні цілі числа, відмінні від нуля, а незаштрихована область – нулі. варіант № Тип матриці А Тип матриці В
1 n 0 .... 0 0 n-1...0 .... 0 .... 1
2 1*2 0 ... 0 0 2*3 ... 0 .... 0 .... n(n+1)
3 11…11 1 … 1 . 0 . 1 … 1 11…11
4 111…111 011…110 … 011…110 111…111
5 100…001 110…011 ………… 110…011 100…001
6 n 0 .0 ... 0 n-1 n 0 . ..0 n-2 n-1 n .... .., 1 2 3 … n
7 1 2 3 … n …. n-2 n-1 n .... n-1 n 0 . ..0 n 0 .0 ... 0
ВАРІАНТИ ЗАВДАНЬ Матриця А задається однозначно і залежить лише від розмірності даних. Для матриці В: заштрихована область – довільні цілі числа, відмінні від нуля, а не заштрихована область – нулі. варіант № Тип матриці А Тип матриці В
11 n 0 .... 0 0 n-1...0 .... 0 .... 1
12 1*2 0 ... 0 0 2*3 ... 0 .... 0 .... n(n+1)
13 11…11 1 … 1 . 0 . 1 … 1 11…11
14 111…111 011…110 … 011…110 111…111
15 100…001 110…011 ………… 110…011 100…001
16 n 0 .0 ... 0 n-1 n 0 . ..0 n-2 n-1 n .... ... 1 2 3 … n
17 1 2 3 … n …. n-2 n-1 n .... n-1 n 0 . ..0 n 0 .0 ... 0
ВАРІАНТИ ЗАВДАНЬ Матриця А задається однозначно і залежить лише від розмірності даних. Для матриці В: заштрихована область – довільні цілі числа, відмінні від нуля, а не заштрихована область – нулі. варіант № Тип матриці А Тип матриці В
21 n 0 .... 0 0 n-1...0 .... 0 .... 1
22 1*2 0 ... 0 0 2*3 ... 0 .... 0 .... n(n+1)
23 11…11 1 … 1 . 0 . 1 … 1 11…11
24 111…111 011…110 … 011…110 111…111
25 100…001 110…011 ………… 110…011 100…001
26 n 0 .0 ... 0 n-1 n 0 . ..0 n-2 n-1 n .... ... 1 2 3 … n
27 1 2 3 … n …. n-2 n-1 n .... n-1 n 0 . ..0 n 0 .0 ... 0
