Учасник Obirvalger

1.1.2 Критерії декомпозиції

Залежно від специфіки розв'язуваного завдання, на вигляд декомпозиції графів можуть бути пред'явлені різні вимоги. Існує багато критеріїв декомпозиції, проте найбільш класичним з них вважається мінімізація максимальної ваги ремен, що виходять з домену (у найпростішому випадку - мінімізація числа розрізаних ребер). Серед інших критеріїв можна виділити такі:

  • виділення відокремлених доменів;
  • мінімізація максимального ступеня доменів;
  • забезпечення зв'язності доменів;
  • забезпечення зв'язності багатьох внутрішніх вузлів доменів.

1.1.3 Метод рекурсивної бісекції

Метод рекурсивної координатної бісекції є окремим випадком більш загальногометоду рекурсивної бісекції. У цьому вся методі сітка послідовно за [math]k-1[/math] крок ділиться на [math]k[/math] частин. На першому етапі сітка ділиться на дві частини, далі кожна з отриманих частин також ділиться на дві частини і т.п. Конкретні алгоритми поділу сітки на дві частини (бісекції) та визначають метод рекурсивної бісекції. Співвідношення розмірів елементів залежить кількості доменів і процедури обчислення бажаного числа вершин у кожній із частин графа, що формуються.

1.1.4 Метод рекурсивної координатної бісекції

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

Метод рекурсивної координатної бісекції ґрунтується на методі рекурсивної бісекції. Для розбиття сітки на дві частини використовується така процедура:

  • вибирається одна з координатних осей;
  • безліч вершин сортується за цією координатою;
  • відсортована безліч розбивається на дві частини, тобто вказується індекс [math]i[/math] такий, що в першу частину потрапляють вершини з номерами меншими або рівними [math]i[/math], а в другу - вершини, що залишилися; геометрично це відповідає гіперплощині, перпендикулярній вибраній осі, яка розбиває безліч вершин сітки на дві частини, співвідношення розмірів яких залежить

1.1.5 Вибір координатної осі

Залежно від критеріїв декомпозиції та інших особливостей завдання можуть бути використані різні критерії вибору координатної осі вздовж, якою буде розбиватися сітка на дві частини. Найбільш використовуваними є такі:

  • Протяжність області вздовж цієї осі: кожної осі обчислюється різницю між максимумом і мінімумом координат вершин сітки даної осі, і вибирається вісь з найбільшим значенням цієї величини;
  • Число розрізаних ребер при розбитті сітки вздовж даної осі: вершини впорядковуються вздовж кожної з осей, і вибирається той варіант, який призводить до найменшої кількості ребер, що розрізають;

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

Вихідні дані:граф [math]G = (V, E) [/math] , вкладений у [math]\mathbb^N[/math] (тобто кожна вершина цього графа - це точка в [math]N[/math] мірному просторі ), і число [math] k [/ math] доменів, на яке потрібно розбити граф. Піддекомпозицієюграфа на [math]k[/math] доменів розуміється розбиття безлічі вершин [math]V[/math] на [math]k[/math] підмножин [math]V_1, \dots, V_k [/math] таких, що

[math]V = \bigcup_^k V_i[/math] і [math]V_i \cap V_j = \varnothing[/math] при [math]i \neq j[/math] .

З кожним доменом можна пов'язати породжений ним підграф [math]G(V_i) = (V_i, E_i)[/math] , де [math]E_i \subseteq E[/math] - безліч ребер, обидва кінці яких належать домену.

Завдання полягає у знаходженні декомпозиції [math]V_1, \dots, V_k[/math] , що доставляє мінімум деякого функціоналу (див. відповідний пункт), наприклад, числа розрізаних ребер [math]E_> = \ = E - \sum_^k E_i[/math] .

Дамо формальний опис алгоритму. Як вже згадувалося, метод заснований на алгоритмі рекурсивної бісекції, тому є рекурсивною процедурою, на вхід якої надходить граф [math]G = (V, E) [/math] і число доменів [math]k[/math] , на яке потрібно розбити безліч вершин цього графа. Усередині цієї процедури виконується наступна послідовність дій:

  • в залежності від числа доменів обчислюється "бажане" число доменів і вершин у кожній частині розбиття;
  • викликається процедура координатної бісекції отримання розбиття графа на частини;
  • для кожної з двох отриманих частин рекурсивно викликається процедура, що описується (якщо число доменів для цієї частини більше одиниці).

Процедура координатної бісекції влаштована таким чином:

  • вибираєтьсякоординатна вісь [math]m^* \in \[/math] ;
  • у разі максимізації протяжності: кожної осі [math]m[/math] обчислюється величина [math]l_m = \max_ v_m - \min_ v_m[/math] , і вибирається вісь [math]m^* = \arg\max_> l_m[/math];
  • у разі мінімізації числа розрізаних ребер: вершини впорядковуються вздовж кожної з осей, кожної осі обчислюється величина [math]E^m_>[/math] , рівна числу розрізаних ребер при розбитті вздовж даної осі, і вибирається вісь [math]m^* = \arg\max_> E^m_>[/math] ;
  • безліч вершин сортується за зростанням координати з номером [math]m^*[/math];
  • відсортований масив вершин ділиться на дві (безперервні) частини відповідно до бажаного числа вершин у кожній частині;
  • як правило, вибирається індекс [math]i = \lfloor\frac\rfloor \cdot V[/math] , що відповідає приблизно рівному поділу поточного графа на частини;
  • перша частина складається з вершин [math]v \in V[/math] з індексами [math]j \leqslant i[/math] , друга - з індексами [math]j \gt i[/math] .

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

    Обчислювальне ядро ​​алгоритму складають сортування масиву вершин сітки за обраною координатою при кожному [math]k - 1[/math] викликів процедури бісекції.

    Також, в залежності від критерію вибору координатної осі, потрібні додаткові обчислення:

    • У разі максимізації протяжності при кожному виклику потрібно обчислення величини [math]l_m[/math].
    • У разі мінімізації числа розрізаних ребер при кожному виклику потрібно сортування за кожною з координат (отже, при кожному розбитті здійснюється [math]N[/math] сортувань).

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

    Як записано в описі ядра алгоритму, основнучастину методу складають множинні (усього [math]k-1[/math] ) сортування (функція argsort у коді в наступному розділі).

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

    Опишемо послідовну реалізацію методу рекурсивної координатної бісекції, де вибір осі проводиться з умови максимізації протяжності вздовж цієї осі. Нижче наведено код даного алгоритму мовою Python 3.

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

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

    Позначимо через [math]D_k(n)[/math] складність алгоритму рекурсивної координатної бісекції для декомпозиції графа з [math]n[/math] вершинами на [math]k[/math] доменів.

    Визначимо величину [math] D (n) = D_n (n) [/ math]. Для [math]D(n)[/math] має місце така рекурентна рівність:

    [math] \begin D(n) = S(n) + 2D(\frac) \\ D(1) = S(1) = 0. \\ \end [/math] , де [math]S(n )[/math] - це складність алгоритму сортування масиву з [math]n[/math] елементів.

    Нехай [math]S(n) = O(n\log_2)[/math] (наприклад, для сортування злиттям), тоді за теоремою про рекурентні співвідношення [2] для довільного позитивного [math]\varepsilon[/math] має місце оцінка [math]D(n) \lesssim n^[/math] .

    Величину [math]D_k(n)[/math] можна явно порахувати за формулою [math]\sum\limits_^\rceil>2^i S(\frac)[/math] . Якщо використовувати сортування зі складністю [math]S(n) = O(n\log_2)[/math] , то

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

    Під операцією у цьому пунктірозумітимемо макрооперацію сортування. Передача даних відбувається після розбиття множини вершин на дві частини. Таким чином, інформаційний граф є бінарним деревом з [math]k[/math] листям. На малюнку нижче наведено частину інформаційного графа для [math]k = 16[/math]. Залежність від вершин [math]n[/math] враховується у самих вузлах дерева.

    obirvalger

    Висота ярусно-паралельної форми - [math]\log_2[/math].

    Ширина ярусно-паралельної форми - [math] k [/ math].

    Якщо розглядати дрібніші операції, що використовуються в процесі сортування, то глобально інформаційний граф буде виглядати також, однак кожен вузол буде замінений на інформаційний граф алгоритму сортування (або [math]N[/math] таких графів, якщо використовується критерій мінімізації числа розрізів) .

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

    Цей алгоритм має координатний паралелізм. Для декомпозиції графа з [math]n[/math] вершинами на [math]k[/math] доменів методом рекурсивної координатної бісекції в паралельному варіанті потрібно послідовно виконати [math]\lceil\log_2\rceil[/math] ярусів. На [math]i[/math]-му ярусі буде виконуватися [math]2^i[/math] операцій сортування. Розглянемо два випадки розпаралелювання нашого алгоритму:

    • Паралельне виконання операцій кожному ярусі з допомогою послідовного алгоритму сортування зі складністю [math]O(n\log_2)[/math] .
    1. На першому кроці один процесор здійснює сортування всіх вершин, розділяє граф на два підграфи і передає один із подрафів новому процесору.
    2. На [math]i[/math]-ом кроці кожен з процесор, що вже отримав свій граф, проводить сортування всіх вершин, розділяє граф на два підграфи і передає один з подрафів новомупроцесору.

    Тоді складність нашого алгоритму дорівнює:

    • Паралельне виконання операцій кожному ярусі з допомогою паралельного алгоритму сортування зі складністю [math]O(\log_2^2)[/math] [3] .

    На кожному кроці проводиться паралельне сортування вершин та розбиття графа на два підграфи. В цьому випадку

    Відомо [4] , що оптимальне паралельне сортування має складність [math]O(log_2)[/math] . В цьому випадку

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

    Вхідні дані:граф [math]G = (V, E) [/math] , вкладений у [math]\mathbb^N[/math] , і число [math]k[/math] частин (Доменів), на яке потрібно розбити граф. Таким чином, крім матриці суміжності (або будь-якого іншого уявлення графа) для кожної вершини [math]v \in V[/math] заданий набір її координат [math]v = (v_1, \dots, v_N) \in \mathbb^N [/math] , тому [math]V[/math] задається масивом [math]N[/math] -мірних векторів або матрицею розміру [math]V \times N[/math] .

    Обсяг вхідних даних:[math]NV + G[/math] , де [math]G[/math] - обсяг даних, що представляють граф [math]G[/math] , який у випадку залежить від обраного уявлення.

    Вихідні дані:[math]k[/math] доменів графа [math]G[/math] , що задають його декомпозицію.

    Обсяг вихідних даних:[math]V[/math] - для кожного домену достатньо зберігати відповідні вершин з цього домену індекси рядків у матриці, що представляє безліч вершин.

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

    Співвідношення послідовної та паралельної складності у разі необмежених ресурсів єлінійним(ставлення [math]O(n\log)[/math] до [math]O(\log))[/math] .

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

    Так як кількість вершин на різних процесорах приблизно однаковий алгоритм є збалансованим за кількістю операцій на кожному процесорі.

    Алгоритм досить простий та легко модифікується залежно від критерію декомпозиції.

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

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

    Нижче наведено приклад реалізації послідовного алгоритму мовою C++. Слід зазначити, вихідний масив вершин не змінюється, вся робота здійснюється з індексами.

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

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

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

    Експерименти проводилися на комп'ютері з чотириядерним процесором Intel Core i7 3610QM 2300 Mhz, який підтримує до 8 потоків та оперативною пам'яттю типу DDR3 1600 МГц розміром 8 Gb.

    Набір та межі значень змінюваних параметрів запуску реалізації алгоритму:

    • кількість потоків від 1 до 8 з кроком 1;
    • розмір сітки N x N, n від 500 до 2000 з кроком 500;
    • число доменів k 100 та від 2000 до 10000 з кроком 1000;