Алгоритм Пурдома

Стан

вивірена

Алгоритм Пурдома
Послідовний алгоритм
Послідовна складність	[math]O(E + \mu^2)[/math]
Обсяг вхідних даних	[math]O(E + V)[/math]
Обсяг вихідних даних	[math]O(V^2)[/math]
Паралельний алгоритм
Висота ярусно-паралельної форми	[math]N/A [/math]
Ширина ярусно-паралельної форми	[math]N/A[/math]

Зміст

1 Властивості та структура алгоритму

1.1 Загальний опис алгоритму

Алгоритм Пурдома[1] знаходить транзитивне замикання орієнтованого графа за час [math]O(E + \mu V)[/math] , де [math]\mu \le E[/math] - число компонент сильної зв'язності цього графа. Алгоритм може бути модифікований для перевірки належності до транзитивного замикання безлічі пар пар вершин.

1.2 Математичне опис алгоритму

Алгоритм заснований на наступних властивостях:

Якщо вершини [math]v[/math] і [math]w[/math] належать одному компоненту сильної зв'язності графа [math]G[/math] , його транзитивне замикання [math]G^+[/math] містить ребра [math](v, w)[/math] та [math](w, v)[/math] .
Якщо вершини [math]x[/math] і [math]y[/math] належать одному компоненту сильної зв'язності графа [math]G[/math] , а вершини [math]z[/math] і [math]t[ /math] - інший, то ребра [math](x, z)[/math], [math](x, t)[/math], [math](y, z)[/math], [math] (y, t)[/math] належать або не належать транзитивному замиканню [math]G^+[/math] одночасно.

Таким чином, пошук транзитивного замикання графа [math]G[/math] зводиться до пошуку транзитивного замикання ациклічногографа [math]\tilde G[/math] , отриманого з [math]G[/math] зхлопування кожної компоненти сильної зв'язності в одну вершину. Транзитивне замикання ациклічного графа обчислюється з допомогою топологічного сортування вершин графа.

1.3 Обчислювальне ядро алгоритму

Алгоритм складається з трьох важливих обчислювальних частин, кожної з яких важливо оцінити відносний час виконання щодо інших частин.

Пошук сильно пов'язаних компонентів у вихідному графі
Побудови графа проміжного подання
Пошуків завширшки у графі проміжного уявлення для побудови підсумкового транзитивного замикання

1. У разі вирішення задачі перевірки приналежності до транзитивного замикання безліч заданих пар вершин, співвідношення обсягів різних обчислювальних частин алгоритму може бути різним, і, очевидно, залежить від числа пар вхідних вершин. Крім того, дане співвідношення може також залежати від типу вхідного графа, так як структура і кількість сильно-зв'язаних компонент сильно впливають як на час пошуку сильно-зв'язаних компонент, так і на час виконання пошуків в ширину. Далі представлена таблиця, демонструє відсоток часу виконання даних частин однієї з реалізацій алгоритму щодо різних типів графів з числом вершин [math]2^[/math] , і числом вхідних пар вершин для перевірки рівним 10000.

Важливо помітити, деякі алгоритми пошуку сильно-пов'язаних компонент (наприклад DCSC) як і грунтуються на пошуку завширшки. Таким чином, обчислювальним ядром алгоритму можна вважати пошук завширшки. У свою чергу обчислювальним ядром алгоритму пошуку в ширину є обхід вершин, суміжної до обраної вершини з подальшим додаванням вершин, що ще не відвіданихбезліч "передових" вершин.

2. У разі вирішення задачі пошуку повного транзитивного замикання найбільш обчислювально витратною частиною є пошуки в ширину в графі проміжного подання, так як його необхідно зробити від усіх вершин даного графа, число яких може бути значним при великій кількості сильно-зв'язаних компонентів у вихідному графі.

1.4 Макроструктура алгоритму

Обчислення виробляються у чотири етапи:

Знайти компоненти сильної зв'язності вихідного графа, замінити кожну компоненту на одну вершину і видалити ребра-петлі, що утворилися.
Виконати топологічне сортування одержаного ациклічного графа [math]\tilde G[/math] .
Обчислити транзитивне замикання графа [math]\tilde G[/math] , рухаючись від вершин з більшими номерами до менших.
За знайденим транзитивним замиканням [math]\tilde G[/math] відновити транзитивне замикання вихідного графа.

Останній етап є обов'язковим, якщо розглядати транзитивне замикання [math]\tilde G[/math] як «упаковане» транзитивне замикання [math]G[/math] .

1.5 Схема реалізації послідовного алгоритму

1 етап(обчислення компонент сильної зв'язності) може бути реалізований алгоритмом Тар'яна [2] , що знаходить компоненти сильної зв'язності в ході пошуку в глибину.

2 етап(топологічна сортування) може бути реалізований алгоритмом Кана [3] або послідовним застосуванням пошуку в глибину [2] для нумерації вершин у порядку.

3 етап(транзитивне замикання[math]\tilde G[/math] ) виконується наступним алгоритмом:

4 етап(транзитивне замикання[math]G[/math] ) або виконується наступним алгоритмом:

або транзитивне замикання може будуватися за упакованими даними [math]\tilde T(v)[/math] однією з наступних функцій:

1.6 Послідовна складність алгоритму

Перший і другий етап виконуються за допомогою пошуку у глибину зі складністю [math]O(E)[/math] .

На етапі основою операцією є об'єднання списків вершин. У разі зберігання списків у відсортованому вигляді об'єднання виконується за лінійний час. Кількість списків вбирається у [math]V[/math] , а кожному списку трохи більше [math]\mu[/math] вершин, де [math]\mu[/math] – кількість компонент сильної зв'язності. Загальна складність тоді становить [math]O(\mu^2)[/math]. Альтернативним форматом зберігання списку вершин є бітова маска з такою самою загальною складністю.

Складність четвертого етапу становить [math]O(\mu V)[/math] , тому що для кожної з [math]\mu[/math] компонент сильної зв'язності за лінійний час обчислюється список вершин з не більш ніж [math]V[ /math] вершин. Оскільки компоненти сильної зв'язності не перетинаються, на цьому етапі вже не потрібно зберігати списки у відсортованому вигляді.

Таким чином, загальна складність становить [math]O(E + \mu^2)[/math] , якщо не потрібна явна побудова транзитивного замикання, або [math]O(E + \mu V)[/math] в іншому випадку .

1.7 Інформаційний граф

На малюнку 2 представлений інформаційний граф алгоритму Пурдома, що демонструє зв'язок між його основними частинами. Алгоритм представлений для варіації постановки завдання, коли проводиться перевірка приналежності до транзитивного замикання безлічі заздалегідь заданих пар вершин.

[1] - ініціалізація масиву номерів сильно пов'язаних компонентів

[Пошук сильно пов'язаних компонентів (Tarjan, DCSC, etc)] - незалежний блокалгоритму, може бути реалізований будь-яким алгоритмом сильно пов'язаних компонентів: DCSC, Тар'яна та ін. Інформаційні графи даних алгоритмів можуть бути знайдені у відповідних розділах.

[2] - виділення пам'яті під вершини графа проміжного подання

[3] - додавання вершин до графа проміжного подання, кожна вершина відповідає одному сильно-пов'язаному компоненту

[4] - підрахунок числа вершин у графі проміжного подання

[5] - виділення пам'яті під ребра графа проміжного подання

[6] - додавання ребер до графа проміжного уявлення, що пов'язують різні пов'язані компоненти

[7] - підрахунок числа ребер у графі проміжного подання

[8] - перевірка номерів сильно пов'язаних компонентів для кожної пари сильно зв'язаних компонентів

[BFS] - пошуки завширшки від тих вершин, які знаходяться в одних сильно пов'язаних компонентах

1.8 Ресурс паралелізму алгоритму

У цьому розділі буде описано ресурс паралелізму, ґрунтуючись на інформаційному графі алгоритму, наведеному малюнку 2.

Ініціалізація сильно пов'язаних компонентів [1] може здійснюватися паралельно і вимагає [math]V[/math] операцій.

Пошук сильно пов'язаних компонентів може мати різний ресурс паралелізму, залежно від вибору алгоритму.

Додавання вершин і ребер до графа проміжного уявлення [2]-[7] вимагає [math]E[/math] та [math]u[/math] операцій ([math]u[/math] - число сильно пов'язаних компонент вихідного графа ), які можуть виконуватися паралельно. При цьому вершини і ребра додаються до графа незалежно один від одного, тому додавання вершин може здійснюватися паралельно з додаванням ребер.

Перевірка номерів сильно пов'язаних компонентів[8] так само може виконуватися паралельно і вимагає [math]n[/math] операцій ([math]n[/math] - число пар вершин, що подаються на вихід), які можуть виконуватися паралельно.

У разі приналежності вершин однієї пари до однієї сильно пов'язаної компоненти, проводиться пошук завширшки [BFS], для кожної відповідної пари. Дані пошуки завширшки так само можуть виконуватися паралельно один одному, при цьому кожен пошук завширшки має певний ресурс паралелізму, описаний у відповідному розділі.

Висота і ширина ярусно-паралельної форми залежить від структури графа (числа та розташування сильно-зв'язаних компонент), так як у свою чергу від неї залежить ширина та висота ЯПФ алгоритму пошуку сильно-зв'язаних компонент.

1.9 Вхідні та вихідні дані алгоритму

Обсяг вхідних та вихідних даних залежить від варіації постановки проблеми. Далі будуть розглянуті два випадки.

1. Пошук повного транзитивного замикання

Вхідні дані: граф [math]G(V, E)[/math] , [math]V[/math] вершин [math]v_i[/math] та [math]E[/math] ребер [math] e_j = (v ^_, v ^_) [/ math] .

Обсяг вхідних даних: [math]O(V + E)[/math] .

Вихідні дані: кожної пари вершин графа її приналежність до транзитивному замиканню.

Обсяг вихідних даних: [math]O(V^2)[/math] .

2. Перевірка приналежності до транзитивного замикання для [math]n[/math] заздалегідь заданих пар вершин [math](v_, v_)[/math]

Вхідні дані: граф [math]G(V, E)[/math] , [math]V[/math] вершин [math]v_i[/math] та [math]E[/math] ребер [math]e_j = (v^_, v^_)[/math] , [math]n[/math] пар вершин [math](v_, v_)[/math] .

Обсяг вхідних даних: [math]O(V + E + n)[/math] .

Вихідні дані: длякожної вхідної пари вершин її приналежність до транзитивного замикання.

Обсяг вихідних даних: [math]O(n)[/math] .

1.10 Властивості алгоритму

2 Програмна реалізація алгоритму

2.1 Особливості реалізації послідовного алгоритму

2.2 Локальність даних та обчислень

2.2.1 Локальність реалізації алгоритму

2.2.1.1 Структура звернень на згадку та якісна оцінка локальності

2.2.1.2 Кількісна оцінка локальності

2.3 Можливі способи та особливості паралельної реалізації алгоритму

Програма, що реалізує пошук транзитного замикання, складається з CPU частини, що відповідає за загальну координацію обчислень, що використовує допоміжні класи.

2.4 Масштабованість алгоритму та його реалізації

2.4.1 Масштабованість алгоритму

2.4.2 Масштабованість реалізації алгоритму

Для демонстрації ефективності представлені графіки часу виконання різних режимів обчислень залежно від вхідного графа.

Основною характеристикою порівняння було обрано час виконання, оскільки продуктивність (визначення як TEPS тобто число ребер графа, яке алгоритм обробляє за секунду) для цієї операції не відбиває реальної ситуації.

Справа в тому, що складність обраного алгоритму Пурдома залежить від кількості ребер у графі не лінійно, та, крім того, залежить ще й від структури графа кількості сильно пов'язаних компонент).

Аналізуючи час виконання можна оцінити, наскільки знижується ефективність обробки графа зі збільшенням його розміру (дані перестають поміщатися в кеш, пам'ять GPU, вузла тощо.). На представлених графіках по осі X граф з кожним розподілом збільшується вдвічі, і попредставленому графіку можна оцінювати, наскільки збільшився час виконання. Так само час виконання можна порівнювати для різних версій, наприклад, послідовної CPU, паралельної CPU або GPU. На наведеній діаграмі (рисунок 1) для різних розмірів графа (від 220 до 226) представлено час виконання трьох різних версій: послідовної, паралельної CPU і GPU. Шкала на цій діаграмі логарифмічна.