Участник:Юлия Жосан/Разбиение вершин графа на равные по мощности блоки методом рекурсивной координатной бисекции: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 77: Строка 77:
 
Структура параллельного алгоритма:
 
Структура параллельного алгоритма:
 
#Подготовительный этап:
 
#Подготовительный этап:
**определение числа и объема требуемых доменов по процессорам
+
##определение числа и объема требуемых доменов по процессорам
 
#Разделение доменов по процессорам:
 
#Разделение доменов по процессорам:
**вызов рекурсивной покоординатной бисекции по процессорам в соответствии с п.1.5
+
##вызов рекурсивной покоординатной бисекции по процессорам в соответствии с п.1.5
 
#Параллельные вызовы алгоритма для каждого процессора
 
#Параллельные вызовы алгоритма для каждого процессора
**вызов локальной координатной бисекции по доменам
+
##вызов локальной координатной бисекции по доменам
  
 
=== Входные и выходные данные алгоритма===
 
=== Входные и выходные данные алгоритма===

Версия 00:10, 16 октября 2016

Автор: Юлия Жосан

1 Свойства и структура алгоритмов

1.1 Общее описание алгоритма


Декомпозиция графа - это задача его разбиения на непересекающиеся подмножества доменов, для их последующей параллельной обработки группой процессоров. Основная сложность использования параллельных методов состоит в поиске оптимальной декомпозиции, которая дает сбалансированное распределение доменов по процессорам. Выделяют два основных свойства оптимальной декомпозиции, которые должны выполняться одновременно:

  • минимизация максимального веса исходящих из домена ребер
  • равномерное распределение по доменам суммарного веса узлов/ребер

Покоординатная декомпозиция основана на рекурсивном делении пополам сети по координатной оси, вдоль которой область наиболее протяженная, соотношение размеров полученных частей зависит от требуемого количества доменов в каждой из них. Этот метод применяется для обработки сеток больших размеров (объем описания сетки превышает объем оперативной памяти одного процессорного узла).

Основные этапы работы алгоритма:

  1. Выбор направления, вдоль которого будут упорядочиваться вершины домена
  2. Упорядочивание вершин вдоль выбранного в п.1 направления
  3. Вычисление номера m первой вершины второго домена
  4. Формирование двух новых доменов, первый из которых включает вершины от первой до m-1 входящего домена, а второй включает вершины с m до последней вершины входящего домена
  5. Запуск алгоритма для полученных в п.4 доменов

Выделяют следующие достоинства данного алгоритма:

  • высокая скорость работы
  • низкий уровень дисбаланса распределения вершин между доменами
  • экономичность по памяти

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


Пусть на вход алгоритму подаются следующие данные:

  • неориентированный граф [math]G=(V, E)[/math], где [math]V[/math] - множество вершин, [math]E[/math] - множество ребер
  • Требуемое число доменов [math]p[/math]

На выходе алгоритма требуется получить множество доменов [math]\{S_{p}\}[/math].Это множество [math]p[/math] непересекающихся подмножеств [math]\{V_{i}\}[/math]:
[math]V=\bigcup\limits_{i=1}^{p} V_{i}[/math], [math]V_{i}\cap V_{j}=\emptyset[/math] для [math]i\not=j[/math] при котором минимизируются следующие функционалы:

  • суммарный вес вершин в домене: [math]\vert S_{p}\vert=\sum\limits_{i=1}^{p} \vert v_{i} \vert\rightarrow min[/math]
  • суммарный вес разрезанных ребер:[math]\sum\limits_{ij} \vert e_{ij} \vert\rightarrow min , v_{i}\in S_{l}, v_{j}\in S_{r}, S_{l}\cap S_{r}=\emptyset[/math]

Опишем подробнее схему работу рекурсивного алгоритма:

  1. Выбор оси, вдоль которой будет осуществляться сортировка. Для этого вычисляется величина [math]l_{k}=max\left( v_{i}^{k}\right)-min\left(v_{i}^{k}\right) , v_{i}^{k}\in V , k [/math] - координатная ось, и выбирается ее максимальное значение.
  2. Сортировка множества вершин [math]V[/math] по выбранной в п.1 координате по возрастанию номеров коодинат вершин
  3. Вычисляется номер вершины, по которой пойдет разбиение множества: [math]m=(iend-istart+1)*\frac{\frac{p+1}{2}}{p}[/math], где [math]iend, istart[/math] - номер первой вершины в множестве и номер последней вершины в множестве соответственно
  4. Множество вершин делится на две части: [math]V_{l}=|v_{l}|, l=istart..m ,V_{r}=|v_{r}|, r=m+1..iend [/math]
  5. Алгоритм запускается для [math]V_{l}[/math] и [math]V_{r}[/math]
  6. Алгоритм останавливается на итерации, для которой [math]|V_{l}|=1 , |V_{r}|=1[/math]

1.3 Вычислительное ядро алгоритма


Вычислительное ядро алгоритма составляют:

  • сортировка массива координат вершин [math]V[/math] (могут применяться различные виды сортировок)
  • вычисление величины [math]l_{k}[/math]
  • вычисление величины [math]m[/math]

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


Основной составляющей метода является повторяющиеся сортировки множества координат вершин [math]V[/math] на каждом рекурсивном шаге. Всего таких шагов [math]p-1[/math].

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


Представим последовательную реализацию метода рекурсивной координатной бисекции с помощью псевдокода:
[math]BisectCoordRec\{V, iend, istart , p\}[/math]
{
[math]l_{k}=argmax{max\left( v_{i}^{k}\right)-min\left(v_{i}^{k}\right)} [/math] - //определение оси для сортировки
[math]Sort(V, iend, istart ,l_{k})[/math]- //сортировка вершин по выбранной координате
[math]m=(iend-istart+1)*\frac{\frac{p+1}{2}}{p}[/math] - //поиск точки для разделения множества вершин
[math]Bisect\left(V,(iend-istart) , V_{l}, \frac{p+1}{2}, V_{r}, \frac{\frac{(iend-istart)*(p+1)}{2}}{p}\right)[/math]- //разделение массива вершин на два
[math]if |V_{l}|\gt 1 : BisectCoordRec\{V_{l},\frac{(iend-istart)*\frac{p+1}{2}}{p} , \frac{p+1}{2}, p\}[/math]
[math]if |V_{r}|\gt 1 : BisectCoordRec\{V_{r}, (iend-istart) - \frac{(iend-istart)*\frac{p+1}{2}}{p} , p - \frac{p+1}{2}, p\}[/math]
}

1.6 Последовательная сложность алгоритма


Пусть в графе [math]G[/math] содержится [math]|V|=n[/math] вершин.

  • Для определения координат [math]iend, istart[/math] требуется [math]O(n)[/math] попарных сравнений
  • Для сортировки массива вершин по координате требуется [math]O(nlog_{2}n)[/math] попарных сравнений

Так как всего осуществляется [math]p-1[/math] шагов рекурсии, глубина ее составляет [math]-log_{2}p+1[/math] Значит можно определить сложность алгоритма следующим образом: [math]O(nlog_{2}nlog_{2}p)[/math]

1.7 Информационный граф


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


Структура параллельного алгоритма:

  1. Подготовительный этап:
    1. определение числа и объема требуемых доменов по процессорам
  2. Разделение доменов по процессорам:
    1. вызов рекурсивной покоординатной бисекции по процессорам в соответствии с п.1.5
  3. Параллельные вызовы алгоритма для каждого процессора
    1. вызов локальной координатной бисекции по доменам

1.9 Входные и выходные данные алгоритма


Вход алгоритма:

  • неориентированный граф [math]G=(V, E)[/math], где [math]V[/math] - множество вершин, [math]E[/math] - множество ребер
  • Требуемое число доменов [math]p[/math]

Выход алгоритма:

  • [math]p[/math] доменов [math]\{S_{p}\}[/math], задающих декомпозицию графа

1.10 Свойства алгоритма


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


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

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма


Параллельные реализации:

  • PARMETIS
  • JOSTLE
  • PT-SCOTCH
  • ZOLTAN

Последовательные реализации:

  • METIS
  • JOSTLE
  • SCOTCH
  • CHACO
  • PARTY

3 Литература


[1] Якобовский М.В. Введение в параллельные методы решения задач: Учебное пособие / Предисл.: В. А. Садовничий. – М.: Издательство Московского университета, 2012. – 328 с., илл. – (Серия «Суперкомпьютерное образование»), ISBN 978-5-211-06382-2 URL: http://lira.imamod.ru/ITTPMOPS/
[2] Головченко Е.Н. Декомпозиция расчетных сеток для решения задач механики сплошных сред на высокопроиводительных вычислительных системах. Дисс ... канд. ф.-м.наук. Институт прикладной математики им. М. В. Келдыша РАН, г. Москва URL: http://keldysh.ru/council/3/D00202403/golovchenko_diss.pdf
[3] Wikipedia.org
[4] Intuit.ru