Алговики - Вклад [ru]

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

2016-11-07T09:01:50Z

Юлия Жосан:

{{Assignment}}

{{algorithm
| name =Метод рекурсивной координатной бисекции
| serial_complexity = <math>O(nlog_{2}nlog_{2}p)</math>
| pf_height = <math>O(log_2 k)</math>
| input_data = <math>|G|+p</math>
| output_data = <math>p*|S|</math>
}}

Автор: [[User:Юлия Жосан|Юлия Жосан]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
----
'''Декомпозиция графа''' - это задача его разбиения на непересекающиеся подмножества доменов, для их последующей параллельной обработки группой процессоров. Основная сложность использования параллельных методов состоит в поиске оптимальной декомпозиции, которая дает сбалансированное распределение доменов по процессорам. Выделяют два основных свойства оптимальной декомпозиции, которые должны выполняться одновременно:
*минимизация максимального веса исходящих из домена ребер
*равномерное распределение по доменам суммарного веса узлов/ребер

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

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

Выделяют следующие '''достоинства''' данного алгоритма:
*высокая скорость работы
*низкий уровень дисбаланса распределения вершин между доменами
*экономичность по памяти
===Математическое описание алгоритма===
----
Пусть на '''вход''' алгоритму подаются следующие данные:
*неориентированный граф <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>

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

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

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

=== Последовательная сложность алгоритма===
----
Пусть в графе <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>
=== Информационный граф===
----

[[File: Pokoorbi.jpg||thumb|center|1200px|Рисунок 1. Информационный граф.<ref name="G1"/>]]
 

=== Ресурс параллелизма алгоритма===
----
Структура параллельного алгоритма:
#Подготовительный этап:
#*определение числа и объема требуемых доменов по процессорам
#**Пусть имеется граф с n вершинами, он распределяется по k доменам. Тогда глубина рекурсии - <math>log_{2}k</math>, что равняется числу ярусов.
#Разделение доменов по процессорам:
#*вызов рекурсивной покоординатной бисекции по процессорам:
#**сортировка вершин графа (на i-м ярусе выполняется <math>2^i</math> операций)
#**разделение на два подграфа для разделения по доменам
#Параллельные вызовы алгоритма для каждого процессора
#*вызов локальной координатной бисекции по доменам

Пусть сложность сортировки равна <math>O(n\log_2{n})</math>.
 Тогда сложность алгоритма можно представить в следующем виде:
<math>O(\sum\limits_{i=0}^{log_2{k}}\frac{n}{2^i}\log_2{\frac{n}{2^i}})=
O(\sum\limits_{i=0}^{log_2{k}}(n\frac{(log_2{n}-i)}{2^i}))=
O(n(\sum\limits_{i=0}^{log_2{k}}(\frac{log_2{n}}{2^i})-\sum\limits_{i=0}^{log_2{k}}(\frac{i}{2^i})))=
O(n\log_2{n})-O(n)=O(n\log_2{n})</math>.

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

----

'''Вход алгоритма:'''
*неориентированный граф <math>G=(V, E)</math>, где <math>V</math> - множество вершин, <math>E</math> - множество ребер
*Требуемое число доменов <math>p</math>

'''Выход алгоритма:'''
*<math>p</math> доменов <math>\{S_{p}\}</math>, задающих декомпозицию графа
=== Свойства алгоритма===
----
*Низкий уровень дисбаланса распределения вершин между доменами. Т.е. количество вершин в доменах примерно одинаковое.
*Алгоритм детерминирован в случае использования устойчивой сортировки вершин.
*Алгоритм достаточно прост в реализации.

==Программная реализация алгоритма==
----
=== Особенности реализации последовательного алгоритма===
=== Локальность данных и вычислений===
=== Возможные способы и особенности параллельной реализации алгоритма===
=== Масштабируемость алгоритма и его реализации===
=== Динамические характеристики и эффективность реализации алгоритма===
=== Выводы для классов архитектур===
=== Существующие реализации алгоритма===

----
'''Параллельные''' реализации:
*[http://glaros.dtc.umn.edu/gkhome/metis/parmetis/overview ParMETIS]
*JOSTLE
*[https://www.labri.fr/perso/pelegrin/scotch/ PT-SCOTCH]
*ZOLTAN

'''Последовательные''' реализации:
*[http://glaros.dtc.umn.edu/gkhome/metis/metis/overview METIS]
*JOSTLE
*[https://www.labri.fr/perso/pelegrin/scotch/ SCOTCH]
*CHACO
*PARTY

== Литература==
----
[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

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

2016-11-01T10:05:32Z

Юлия Жосан:

{{Assignment}}
Автор: [[User:Юлия Жосан|Юлия Жосан]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
----
'''Декомпозиция графа''' - это задача его разбиения на непересекающиеся подмножества доменов, для их последующей параллельной обработки группой процессоров. Основная сложность использования параллельных методов состоит в поиске оптимальной декомпозиции, которая дает сбалансированное распределение доменов по процессорам. Выделяют два основных свойства оптимальной декомпозиции, которые должны выполняться одновременно:
*минимизация максимального веса исходящих из домена ребер
*равномерное распределение по доменам суммарного веса узлов/ребер

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

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

Выделяют следующие '''достоинства''' данного алгоритма:
*высокая скорость работы
*низкий уровень дисбаланса распределения вершин между доменами
*экономичность по памяти
===Математическое описание алгоритма===
----
Пусть на '''вход''' алгоритму подаются следующие данные:
*неориентированный граф <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>

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

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

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

=== Последовательная сложность алгоритма===
----
Пусть в графе <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>
=== Информационный граф===
----

[[File: bisec_gr.jpg]]
 

=== Ресурс параллелизма алгоритма===
----
Структура параллельного алгоритма:
#Подготовительный этап:
#*определение числа и объема требуемых доменов по процессорам
#**Пусть имеется граф с n вершинами, он распределяется по k доменам. Тогда глубина рекурсии - <math>log_{2}k</math>, что равняется числу ярусов.
#Разделение доменов по процессорам:
#*вызов рекурсивной покоординатной бисекции по процессорам:
#**сортировка вершин графа (на i-м ярусе выполняется <math>2^i</math> операций)
#**разделение на два подграфа для разделения по доменам
#Параллельные вызовы алгоритма для каждого процессора
#*вызов локальной координатной бисекции по доменам

Пусть сложность сортировки равна <math>O(n\log_2{n})</math>.
 Тогда сложность алгоритма можно представить в следующем виде:
<math>O(\sum\limits_{i=0}^{log_2{k}}\frac{n}{2^i}\log_2{\frac{n}{2^i}})=
O(\sum\limits_{i=0}^{log_2{k}}(n\frac{(log_2{n}-i)}{2^i}))=
O(n(\sum\limits_{i=0}^{log_2{k}}(\frac{log_2{n}}{2^i})-\sum\limits_{i=0}^{log_2{k}}(\frac{i}{2^i})))=
O(n\log_2{n})-O(n)=O(n\log_2{n})</math>.

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

----

'''Вход алгоритма:'''
*неориентированный граф <math>G=(V, E)</math>, где <math>V</math> - множество вершин, <math>E</math> - множество ребер
*Требуемое число доменов <math>p</math>

'''Выход алгоритма:'''
*<math>p</math> доменов <math>\{S_{p}\}</math>, задающих декомпозицию графа
=== Свойства алгоритма===
----
*Низкий уровень дисбаланса распределения вершин между доменами. Т.е. количество вершин в доменах примерно одинаковое.
*Алгоритм детерминирован в случае использования устойчивой сортировки вершин.
*Алгоритм достаточно прост в реализации.

==Программная реализация алгоритма==
----
=== Особенности реализации последовательного алгоритма===
=== Локальность данных и вычислений===
=== Возможные способы и особенности параллельной реализации алгоритма===
=== Масштабируемость алгоритма и его реализации===
=== Динамические характеристики и эффективность реализации алгоритма===
=== Выводы для классов архитектур===
=== Существующие реализации алгоритма===

----
'''Параллельные''' реализации:
*[http://glaros.dtc.umn.edu/gkhome/metis/parmetis/overview ParMETIS]
*JOSTLE
*[https://www.labri.fr/perso/pelegrin/scotch/ PT-SCOTCH]
*ZOLTAN

'''Последовательные''' реализации:
*[http://glaros.dtc.umn.edu/gkhome/metis/metis/overview METIS]
*JOSTLE
*[https://www.labri.fr/perso/pelegrin/scotch/ SCOTCH]
*CHACO
*PARTY

== Литература==
----
[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

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

2016-11-01T10:04:02Z

Юлия Жосан:

Автор: [[User:Юлия Жосан|Юлия Жосан]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
----
'''Декомпозиция графа''' - это задача его разбиения на непересекающиеся подмножества доменов, для их последующей параллельной обработки группой процессоров. Основная сложность использования параллельных методов состоит в поиске оптимальной декомпозиции, которая дает сбалансированное распределение доменов по процессорам. Выделяют два основных свойства оптимальной декомпозиции, которые должны выполняться одновременно:
*минимизация максимального веса исходящих из домена ребер
*равномерное распределение по доменам суммарного веса узлов/ребер

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

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

Выделяют следующие '''достоинства''' данного алгоритма:
*высокая скорость работы
*низкий уровень дисбаланса распределения вершин между доменами
*экономичность по памяти
===Математическое описание алгоритма===
----
Пусть на '''вход''' алгоритму подаются следующие данные:
*неориентированный граф <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>

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

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

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

=== Последовательная сложность алгоритма===
----
Пусть в графе <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>
=== Информационный граф===
----

[[File: bisec_gr.jpg]]
 

=== Ресурс параллелизма алгоритма===
----
Структура параллельного алгоритма:
#Подготовительный этап:
#*определение числа и объема требуемых доменов по процессорам
#**Пусть имеется граф с n вершинами, он распределяется по k доменам. Тогда глубина рекурсии - <math>log_{2}k</math>, что равняется числу ярусов.
#Разделение доменов по процессорам:
#*вызов рекурсивной покоординатной бисекции по процессорам:
#**сортировка вершин графа (на i-м ярусе выполняется <math>2^i</math> операций)
#**разделение на два подграфа для разделения по доменам
#Параллельные вызовы алгоритма для каждого процессора
#*вызов локальной координатной бисекции по доменам

Пусть сложность сортировки равна <math>O(n\log_2{n})</math>.
 Тогда сложность алгоритма можно представить в следующем виде:
<math>O(\sum\limits_{i=0}^{log_2{k}}\frac{n}{2^i}\log_2{\frac{n}{2^i}})=
O(\sum\limits_{i=0}^{log_2{k}}(n\frac{(log_2{n}-i)}{2^i}))=
O(n(\sum\limits_{i=0}^{log_2{k}}(\frac{log_2{n}}{2^i})-\sum\limits_{i=0}^{log_2{k}}(\frac{i}{2^i})))=
O(n\log_2{n})-O(n)=O(n\log_2{n})</math>.

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

----

'''Вход алгоритма:'''
*неориентированный граф <math>G=(V, E)</math>, где <math>V</math> - множество вершин, <math>E</math> - множество ребер
*Требуемое число доменов <math>p</math>

'''Выход алгоритма:'''
*<math>p</math> доменов <math>\{S_{p}\}</math>, задающих декомпозицию графа
=== Свойства алгоритма===
----
*Низкий уровень дисбаланса распределения вершин между доменами. Т.е. количество вершин в доменах примерно одинаковое.
*Алгоритм детерминирован в случае использования устойчивой сортировки вершин.
*Алгоритм достаточно прост в реализации.

==Программная реализация алгоритма==
----
=== Особенности реализации последовательного алгоритма===
=== Локальность данных и вычислений===
=== Возможные способы и особенности параллельной реализации алгоритма===
=== Масштабируемость алгоритма и его реализации===
=== Динамические характеристики и эффективность реализации алгоритма===
=== Выводы для классов архитектур===
=== Существующие реализации алгоритма===

----
'''Параллельные''' реализации:
*[http://glaros.dtc.umn.edu/gkhome/metis/parmetis/overview ParMETIS]
*JOSTLE
*[https://www.labri.fr/perso/pelegrin/scotch/ PT-SCOTCH]
*ZOLTAN

'''Последовательные''' реализации:
*[http://glaros.dtc.umn.edu/gkhome/metis/metis/overview METIS]
*JOSTLE
*[https://www.labri.fr/perso/pelegrin/scotch/ SCOTCH]
*CHACO
*PARTY

== Литература==
----
[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

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

2016-11-01T08:54:36Z

Юлия Жосан: /* Вычислительное ядро алгоритма */

Автор: [[User:Юлия Жосан|Юлия Жосан]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
----
'''Декомпозиция графа''' - это задача его разбиения на непересекающиеся подмножества доменов, для их последующей параллельной обработки группой процессоров. Основная сложность использования параллельных методов состоит в поиске оптимальной декомпозиции, которая дает сбалансированное распределение доменов по процессорам. Выделяют два основных свойства оптимальной декомпозиции, которые должны выполняться одновременно:
*минимизация максимального веса исходящих из домена ребер
*равномерное распределение по доменам суммарного веса узлов/ребер

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

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

Выделяют следующие '''достоинства''' данного алгоритма:
*высокая скорость работы
*низкий уровень дисбаланса распределения вершин между доменами
*экономичность по памяти
===Математическое описание алгоритма===
----
Пусть на '''вход''' алгоритму подаются следующие данные:
*неориентированный граф <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>

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

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

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

=== Последовательная сложность алгоритма===
----
Пусть в графе <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.8.

=== Ресурс параллелизма алгоритма===
----
Структура параллельного алгоритма:
#Подготовительный этап:
#*определение числа и объема требуемых доменов по процессорам
#**Пусть имеется граф с n вершинами, он распределяется по k доменам. Тогда глубина рекурсии - <math>log_{2}k</math>, что равняется числу ярусов.
#Разделение доменов по процессорам:
#*вызов рекурсивной покоординатной бисекции по процессорам:
#**сортировка вершин графа (на i-м ярусе выполняется <math>2^i</math> операций)
#**разделение на два подграфа для разделения по доменам
#Параллельные вызовы алгоритма для каждого процессора
#*вызов локальной координатной бисекции по доменам

Пусть сложность сортировки равна <math>O(n\log_2{n})</math>.
 Тогда сложность алгоритма можно представить в следующем виде:
<math>O(\sum\limits_{i=0}^{log_2{k}}\frac{n}{2^i}\log_2{\frac{n}{2^i}})=
O(\sum\limits_{i=0}^{log_2{k}}(n\frac{(log_2{n}-i)}{2^i}))=
O(n(\sum\limits_{i=0}^{log_2{k}}(\frac{log_2{n}}{2^i})-\sum\limits_{i=0}^{log_2{k}}(\frac{i}{2^i})))=
O(n\log_2{n})-O(n)=O(n\log_2{n})</math>.

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

----

'''Вход алгоритма:'''
*неориентированный граф <math>G=(V, E)</math>, где <math>V</math> - множество вершин, <math>E</math> - множество ребер
*Требуемое число доменов <math>p</math>

'''Выход алгоритма:'''
*<math>p</math> доменов <math>\{S_{p}\}</math>, задающих декомпозицию графа
=== Свойства алгоритма===
----
*Низкий уровень дисбаланса распределения вершин между доменами. Т.е. количество вершин в доменах примерно одинаковое.
*Алгоритм детерминирован в случае использования устойчивой сортировки вершин.
*Алгоритм достаточно прост в реализации.

==Программная реализация алгоритма==
----
=== Особенности реализации последовательного алгоритма===
=== Локальность данных и вычислений===
=== Возможные способы и особенности параллельной реализации алгоритма===
=== Масштабируемость алгоритма и его реализации===
=== Динамические характеристики и эффективность реализации алгоритма===
=== Выводы для классов архитектур===
=== Существующие реализации алгоритма===

----
'''Параллельные''' реализации:
*[http://glaros.dtc.umn.edu/gkhome/metis/parmetis/overview ParMETIS]
*JOSTLE
*[https://www.labri.fr/perso/pelegrin/scotch/ PT-SCOTCH]
*ZOLTAN

'''Последовательные''' реализации:
*[http://glaros.dtc.umn.edu/gkhome/metis/metis/overview METIS]
*JOSTLE
*[https://www.labri.fr/perso/pelegrin/scotch/ SCOTCH]
*CHACO
*PARTY

== Литература==
----
[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

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

2016-11-01T08:53:59Z

Юлия Жосан: /* Свойства и структура алгоритмов */

Автор: [[User:Юлия Жосан|Юлия Жосан]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
----
'''Декомпозиция графа''' - это задача его разбиения на непересекающиеся подмножества доменов, для их последующей параллельной обработки группой процессоров. Основная сложность использования параллельных методов состоит в поиске оптимальной декомпозиции, которая дает сбалансированное распределение доменов по процессорам. Выделяют два основных свойства оптимальной декомпозиции, которые должны выполняться одновременно:
*минимизация максимального веса исходящих из домена ребер
*равномерное распределение по доменам суммарного веса узлов/ребер

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

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

Выделяют следующие '''достоинства''' данного алгоритма:
*высокая скорость работы
*низкий уровень дисбаланса распределения вершин между доменами
*экономичность по памяти
===Математическое описание алгоритма===
----
Пусть на '''вход''' алгоритму подаются следующие данные:
*неориентированный граф <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>

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

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

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

=== Последовательная сложность алгоритма===
----
Пусть в графе <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.8.

=== Ресурс параллелизма алгоритма===
----
Структура параллельного алгоритма:
#Подготовительный этап:
#*определение числа и объема требуемых доменов по процессорам
#**Пусть имеется граф с n вершинами, он распределяется по k доменам. Тогда глубина рекурсии - <math>log_{2}k</math>, что равняется числу ярусов.
#Разделение доменов по процессорам:
#*вызов рекурсивной покоординатной бисекции по процессорам:
#**сортировка вершин графа (на i-м ярусе выполняется <math>2^i</math> операций)
#**разделение на два подграфа для разделения по доменам
#Параллельные вызовы алгоритма для каждого процессора
#*вызов локальной координатной бисекции по доменам

Пусть сложность сортировки равна <math>O(n\log_2{n})</math>.
 Тогда сложность алгоритма можно представить в следующем виде:
<math>O(\sum\limits_{i=0}^{log_2{k}}\frac{n}{2^i}\log_2{\frac{n}{2^i}})=
O(\sum\limits_{i=0}^{log_2{k}}(n\frac{(log_2{n}-i)}{2^i}))=
O(n(\sum\limits_{i=0}^{log_2{k}}(\frac{log_2{n}}{2^i})-\sum\limits_{i=0}^{log_2{k}}(\frac{i}{2^i})))=
O(n\log_2{n})-O(n)=O(n\log_2{n})</math>.

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

----

'''Вход алгоритма:'''
*неориентированный граф <math>G=(V, E)</math>, где <math>V</math> - множество вершин, <math>E</math> - множество ребер
*Требуемое число доменов <math>p</math>

'''Выход алгоритма:'''
*<math>p</math> доменов <math>\{S_{p}\}</math>, задающих декомпозицию графа
=== Свойства алгоритма===
----
*Низкий уровень дисбаланса распределения вершин между доменами. Т.е. количество вершин в доменах примерно одинаковое.
*Алгоритм детерминирован в случае использования устойчивой сортировки вершин.
*Алгоритм достаточно прост в реализации.

==Программная реализация алгоритма==
----
=== Особенности реализации последовательного алгоритма===
=== Локальность данных и вычислений===
=== Возможные способы и особенности параллельной реализации алгоритма===
=== Масштабируемость алгоритма и его реализации===
=== Динамические характеристики и эффективность реализации алгоритма===
=== Выводы для классов архитектур===
=== Существующие реализации алгоритма===

----
'''Параллельные''' реализации:
*[http://glaros.dtc.umn.edu/gkhome/metis/parmetis/overview ParMETIS]
*JOSTLE
*[https://www.labri.fr/perso/pelegrin/scotch/ PT-SCOTCH]
*ZOLTAN

'''Последовательные''' реализации:
*[http://glaros.dtc.umn.edu/gkhome/metis/metis/overview METIS]
*JOSTLE
*[https://www.labri.fr/perso/pelegrin/scotch/ SCOTCH]
*CHACO
*PARTY

== Литература==
----
[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

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

2016-11-01T08:45:43Z

Юлия Жосан: /* Свойства и структура алгоритмов */

Автор: [[User:Юлия Жосан|Юлия Жосан]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
----
'''Декомпозиция графа''' - это задача его разбиения на непересекающиеся подмножества доменов, для их последующей параллельной обработки группой процессоров. Основная сложность использования параллельных методов состоит в поиске оптимальной декомпозиции, которая дает сбалансированное распределение доменов по процессорам. Выделяют два основных свойства оптимальной декомпозиции, которые должны выполняться одновременно:
*минимизация максимального веса исходящих из домена ребер
*равномерное распределение по доменам суммарного веса узлов/ребер

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

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

Выделяют следующие '''достоинства''' данного алгоритма:
*высокая скорость работы
*низкий уровень дисбаланса распределения вершин между доменами
*экономичность по памяти
===Математическое описание алгоритма===
----
Пусть на '''вход''' алгоритму подаются следующие данные:
*неориентированный граф <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>

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

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

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

=== Последовательная сложность алгоритма===
----
Пусть в графе <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.8.

=== Ресурс параллелизма алгоритма===
----
Структура параллельного алгоритма:
#Подготовительный этап:
#*определение числа и объема требуемых доменов по процессорам
#**Пусть имеется граф с n вершинами, он распределяется по k доменам. Тогда глубина рекурсии - <math>log_{2}k</math>, что равняется числу ярусов.
#Разделение доменов по процессорам:
#*вызов рекурсивной покоординатной бисекции по процессорам:
#**сортировка вершин графа (на i-м ярусе выполняется <math>2^i</math> операций)
#**разделение на два подграфа для разделения по доменам
#Параллельные вызовы алгоритма для каждого процессора
#*вызов локальной координатной бисекции по доменам

Пусть сложность сортировки равна <math>O(n\log_2{n})</math>.
 Тогда сложность алгоритма можно представить в следующем виде:
<math>O(\sum\limits_{i=0}^{log_2{k}}\frac{n}{2^i}\log_2{\frac{n}{2^i}})=
O(\sum\limits_{i=0}^{log_2{k}}(n\frac{(log_2{n}-i)}{2^i}))=
O(n(\sum\limits_{i=0}^{log_2{k}}(\frac{log_2{n}}{2^i})-\sum\limits_{i=0}^{log_2{k}}(\frac{i}{2^i})))=
O(n\log_2{n})-O(n)=O(n\log_2{n})</math>.

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

----

'''Вход алгоритма:'''
*неориентированный граф <math>G=(V, E)</math>, где <math>V</math> - множество вершин, <math>E</math> - множество ребер
*Требуемое число доменов <math>p</math>

'''Выход алгоритма:'''
*<math>p</math> доменов <math>\{S_{p}\}</math>, задающих декомпозицию графа
=== Свойства алгоритма===
----
*Низкий уровень дисбаланса распределения вершин между доменами. Т.е. количество вершин в доменах примерно одинаковое.
*Алгоритм детерминирован в случае использования устойчивой сортировки вершин.
*Алгоритм достаточно прост в реализации.

==Программная реализация алгоритма==
----
=== Особенности реализации последовательного алгоритма===
=== Локальность данных и вычислений===
=== Возможные способы и особенности параллельной реализации алгоритма===
=== Масштабируемость алгоритма и его реализации===
=== Динамические характеристики и эффективность реализации алгоритма===
=== Выводы для классов архитектур===
=== Существующие реализации алгоритма===

----
'''Параллельные''' реализации:
*[http://glaros.dtc.umn.edu/gkhome/metis/parmetis/overview ParMETIS]
*JOSTLE
*[https://www.labri.fr/perso/pelegrin/scotch/ PT-SCOTCH]
*ZOLTAN

'''Последовательные''' реализации:
*[http://glaros.dtc.umn.edu/gkhome/metis/metis/overview METIS]
*JOSTLE
*[https://www.labri.fr/perso/pelegrin/scotch/ SCOTCH]
*CHACO
*PARTY

== Литература==
----
[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

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

2016-10-31T22:40:35Z

Юлия Жосан:

Автор: [[User:Юлия Жосан|Юлия Жосан]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
----
'''Декомпозиция графа''' - это задача его разбиения на непересекающиеся подмножества доменов, для их последующей параллельной обработки группой процессоров. Основная сложность использования параллельных методов состоит в поиске оптимальной декомпозиции, которая дает сбалансированное распределение доменов по процессорам. Выделяют два основных свойства оптимальной декомпозиции, которые должны выполняться одновременно:
*минимизация максимального веса исходящих из домена ребер
*равномерное распределение по доменам суммарного веса узлов/ребер

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

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

Выделяют следующие '''достоинства''' данного алгоритма:
*высокая скорость работы
*низкий уровень дисбаланса распределения вершин между доменами
*экономичность по памяти
===Математическое описание алгоритма===
----
Пусть на '''вход''' алгоритму подаются следующие данные:
*неориентированный граф <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>

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

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

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

=== Последовательная сложность алгоритма===
----
Пусть в графе <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.8.

=== Ресурс параллелизма алгоритма===
----
Структура параллельного алгоритма:
#Подготовительный этап:
#*определение числа и объема требуемых доменов по процессорам
#**Пусть имеется граф с n вершинами, он распределяется по k доменам. Тогда глубина рекурсии - <math>log_{2}k</math>, что равняется числу ярусов.
#Разделение доменов по процессорам:
#*вызов рекурсивной покоординатной бисекции по процессорам:
#**сортировка вершин графа (на i-м ярусе выполняется <math>2^i</math> операций)
#**разделение на два подграфа для разделения по доменам
#Параллельные вызовы алгоритма для каждого процессора
#*вызов локальной координатной бисекции по доменам

Пусть сложность сортировки равна <math>O(n\log_2{n})</math>.
 Тогда сложность алгоритма можно представить в следующем виде:
<math>O(\sum\limits_{i=0}^{log_2{k}}\frac{n}{2^i} \log_2{\frac{n}{2^i}})=n\sum\limits_{i=0}^{log_2{k}}(\frac{\log_2{n}}{2^i} - \frac{i}{2^i})=O(n\log_2{n})-O(n)=O(n\log_2{n})</math>.

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

----

'''Вход алгоритма:'''
*неориентированный граф <math>G=(V, E)</math>, где <math>V</math> - множество вершин, <math>E</math> - множество ребер
*Требуемое число доменов <math>p</math>

'''Выход алгоритма:'''
*<math>p</math> доменов <math>\{S_{p}\}</math>, задающих декомпозицию графа
=== Свойства алгоритма===
----
*Низкий уровень дисбаланса распределения вершин между доменами. Т.е. количество вершин в доменах примерно одинаковое.
*Алгоритм детерминирован в случае использования устойчивой сортировки вершин.
*Алгоритм достаточно прост в реализации.

==Программная реализация алгоритма==
----
=== Особенности реализации последовательного алгоритма===
=== Локальность данных и вычислений===
=== Возможные способы и особенности параллельной реализации алгоритма===
=== Масштабируемость алгоритма и его реализации===
=== Динамические характеристики и эффективность реализации алгоритма===
=== Выводы для классов архитектур===
=== Существующие реализации алгоритма===

----
'''Параллельные''' реализации:
*[http://glaros.dtc.umn.edu/gkhome/metis/parmetis/overview ParMETIS]
*JOSTLE
*[https://www.labri.fr/perso/pelegrin/scotch/ PT-SCOTCH]
*ZOLTAN

'''Последовательные''' реализации:
*[http://glaros.dtc.umn.edu/gkhome/metis/metis/overview METIS]
*JOSTLE
*[https://www.labri.fr/perso/pelegrin/scotch/ SCOTCH]
*CHACO
*PARTY

== Литература==
----
[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

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

2016-10-15T21:34:45Z

Юлия Жосан:

{{Assignment}}
Автор: [[User:Юлия Жосан|Юлия Жосан]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
----
'''Декомпозиция графа''' - это задача его разбиения на непересекающиеся подмножества доменов, для их последующей параллельной обработки группой процессоров. Основная сложность использования параллельных методов состоит в поиске оптимальной декомпозиции, которая дает сбалансированное распределение доменов по процессорам. Выделяют два основных свойства оптимальной декомпозиции, которые должны выполняться одновременно:
*минимизация максимального веса исходящих из домена ребер
*равномерное распределение по доменам суммарного веса узлов/ребер

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

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

Выделяют следующие '''достоинства''' данного алгоритма:
*высокая скорость работы
*низкий уровень дисбаланса распределения вершин между доменами
*экономичность по памяти
===Математическое описание алгоритма===
----
Пусть на '''вход''' алгоритму подаются следующие данные:
*неориентированный граф <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>

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

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

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

=== Последовательная сложность алгоритма===
----
Пусть в графе <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.8.

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

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

----

'''Вход алгоритма:'''
*неориентированный граф <math>G=(V, E)</math>, где <math>V</math> - множество вершин, <math>E</math> - множество ребер
*Требуемое число доменов <math>p</math>

'''Выход алгоритма:'''
*<math>p</math> доменов <math>\{S_{p}\}</math>, задающих декомпозицию графа
=== Свойства алгоритма===
----
*Низкий уровень дисбаланса распределения вершин между доменами. Т.е. количество вершин в доменах примерно одинаковое.
*Алгоритм детерминирован в случае использования устойчивой сортировки вершин.
*Алгоритм достаточно прост в реализации.

==Программная реализация алгоритма==
----
=== Особенности реализации последовательного алгоритма===
=== Локальность данных и вычислений===
=== Возможные способы и особенности параллельной реализации алгоритма===
=== Масштабируемость алгоритма и его реализации===
=== Динамические характеристики и эффективность реализации алгоритма===
=== Выводы для классов архитектур===
=== Существующие реализации алгоритма===

----
'''Параллельные''' реализации:
*PARMETIS
*JOSTLE
*PT-SCOTCH
*ZOLTAN

'''Последовательные''' реализации:
*METIS
*JOSTLE
*SCOTCH
*CHACO
*PARTY

== Литература==
----
[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

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

2016-10-15T21:21:23Z

Юлия Жосан: /* Свойства и структура алгоритмов */

Автор: [[User:Юлия Жосан|Юлия Жосан]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
----
'''Декомпозиция графа''' - это задача его разбиения на непересекающиеся подмножества доменов, для их последующей параллельной обработки группой процессоров. Основная сложность использования параллельных методов состоит в поиске оптимальной декомпозиции, которая дает сбалансированное распределение доменов по процессорам. Выделяют два основных свойства оптимальной декомпозиции, которые должны выполняться одновременно:
*минимизация максимального веса исходящих из домена ребер
*равномерное распределение по доменам суммарного веса узлов/ребер

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

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

Выделяют следующие '''достоинства''' данного алгоритма:
*высокая скорость работы
*низкий уровень дисбаланса распределения вершин между доменами
*экономичность по памяти
===Математическое описание алгоритма===
----
Пусть на '''вход''' алгоритму подаются следующие данные:
*неориентированный граф <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>

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

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

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

=== Последовательная сложность алгоритма===
----
Пусть в графе <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.5
#Параллельные вызовы алгоритма для каждого процессора
#*вызов локальной координатной бисекции по доменам

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

----

'''Вход алгоритма:'''
*неориентированный граф <math>G=(V, E)</math>, где <math>V</math> - множество вершин, <math>E</math> - множество ребер
*Требуемое число доменов <math>p</math>

'''Выход алгоритма:'''
*<math>p</math> доменов <math>\{S_{p}\}</math>, задающих декомпозицию графа
=== Свойства алгоритма===
----
*Низкий уровень дисбаланса распределения вершин между доменами. Т.е. количество вершин в доменах примерно одинаковое.
*Алгоритм детерминирован в случае использования устойчивой сортировки вершин.
*Алгоритм достаточно прост в реализации.

==Программная реализация алгоритма==
----
=== Особенности реализации последовательного алгоритма===
=== Локальность данных и вычислений===
=== Возможные способы и особенности параллельной реализации алгоритма===
=== Масштабируемость алгоритма и его реализации===
=== Динамические характеристики и эффективность реализации алгоритма===
=== Выводы для классов архитектур===
=== Существующие реализации алгоритма===

----
'''Параллельные''' реализации:
*PARMETIS
*JOSTLE
*PT-SCOTCH
*ZOLTAN

'''Последовательные''' реализации:
*METIS
*JOSTLE
*SCOTCH
*CHACO
*PARTY

== Литература==
----
[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

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

2016-10-15T21:15:40Z

Юлия Жосан: /* Схема реализации последовательного алгоритма */

Автор: [[User:Юлия Жосан|Юлия Жосан]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
----
'''Декомпозиция графа''' - это задача его разбиения на непересекающиеся подмножества доменов, для их последующей параллельной обработки группой процессоров. Основная сложность использования параллельных методов состоит в поиске оптимальной декомпозиции, которая дает сбалансированное распределение доменов по процессорам. Выделяют два основных свойства оптимальной декомпозиции, которые должны выполняться одновременно:
*минимизация максимального веса исходящих из домена ребер
*равномерное распределение по доменам суммарного веса узлов/ребер

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

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

Выделяют следующие '''достоинства''' данного алгоритма:
*высокая скорость работы
*низкий уровень дисбаланса распределения вершин между доменами
*экономичность по памяти
===Математическое описание алгоритма===
----
Пусть на '''вход''' алгоритму подаются следующие данные:
*неориентированный граф <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>

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

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

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

=== Последовательная сложность алгоритма===
----
Пусть в графе <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.5
#Параллельные вызовы алгоритма для каждого процессора
#*вызов локальной координатной бисекции по доменам

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

----

'''Вход алгоритма:'''
*неориентированный граф <math>G=(V, E)</math>, где <math>V</math> - множество вершин, <math>E</math> - множество ребер
*Требуемое число доменов <math>p</math>

'''Выход алгоритма:'''
*<math>p</math> доменов <math>\{S_{p}\}</math>, задающих декомпозицию графа
=== Свойства алгоритма===
----

==Программная реализация алгоритма==
----
=== Особенности реализации последовательного алгоритма===
=== Локальность данных и вычислений===
=== Возможные способы и особенности параллельной реализации алгоритма===
=== Масштабируемость алгоритма и его реализации===
=== Динамические характеристики и эффективность реализации алгоритма===
=== Выводы для классов архитектур===
=== Существующие реализации алгоритма===

----
'''Параллельные''' реализации:
*PARMETIS
*JOSTLE
*PT-SCOTCH
*ZOLTAN

'''Последовательные''' реализации:
*METIS
*JOSTLE
*SCOTCH
*CHACO
*PARTY

== Литература==
----
[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

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

2016-10-15T21:11:27Z

Юлия Жосан: /* Ресурс параллелизма алгоритма */

Автор: [[User:Юлия Жосан|Юлия Жосан]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
----
'''Декомпозиция графа''' - это задача его разбиения на непересекающиеся подмножества доменов, для их последующей параллельной обработки группой процессоров. Основная сложность использования параллельных методов состоит в поиске оптимальной декомпозиции, которая дает сбалансированное распределение доменов по процессорам. Выделяют два основных свойства оптимальной декомпозиции, которые должны выполняться одновременно:
*минимизация максимального веса исходящих из домена ребер
*равномерное распределение по доменам суммарного веса узлов/ребер

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

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

Выделяют следующие '''достоинства''' данного алгоритма:
*высокая скорость работы
*низкий уровень дисбаланса распределения вершин между доменами
*экономичность по памяти
===Математическое описание алгоритма===
----
Пусть на '''вход''' алгоритму подаются следующие данные:
*неориентированный граф <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>

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

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

=== Схема реализации последовательного алгоритма===
----
Представим последовательную реализацию метода рекурсивной координатной бисекции с помощью псевдокода:
 <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}|>1 : BisectCoordRec\{V_{l},\frac{(iend-istart)*\frac{p+1}{2}}{p} , \frac{p+1}{2}, p\}</math>
 <math>if |V_{r}|>1 : BisectCoordRec\{V_{r}, (iend-istart) - \frac{(iend-istart)*\frac{p+1}{2}}{p} , p - \frac{p+1}{2}, p\}</math>
 }
=== Последовательная сложность алгоритма===
----
Пусть в графе <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.5
#Параллельные вызовы алгоритма для каждого процессора
#*вызов локальной координатной бисекции по доменам

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

----

'''Вход алгоритма:'''
*неориентированный граф <math>G=(V, E)</math>, где <math>V</math> - множество вершин, <math>E</math> - множество ребер
*Требуемое число доменов <math>p</math>

'''Выход алгоритма:'''
*<math>p</math> доменов <math>\{S_{p}\}</math>, задающих декомпозицию графа
=== Свойства алгоритма===
----

==Программная реализация алгоритма==
----
=== Особенности реализации последовательного алгоритма===
=== Локальность данных и вычислений===
=== Возможные способы и особенности параллельной реализации алгоритма===
=== Масштабируемость алгоритма и его реализации===
=== Динамические характеристики и эффективность реализации алгоритма===
=== Выводы для классов архитектур===
=== Существующие реализации алгоритма===

----
'''Параллельные''' реализации:
*PARMETIS
*JOSTLE
*PT-SCOTCH
*ZOLTAN

'''Последовательные''' реализации:
*METIS
*JOSTLE
*SCOTCH
*CHACO
*PARTY

== Литература==
----
[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

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

2016-10-15T21:10:38Z

Юлия Жосан: /* Ресурс параллелизма алгоритма */

Автор: [[User:Юлия Жосан|Юлия Жосан]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
----
'''Декомпозиция графа''' - это задача его разбиения на непересекающиеся подмножества доменов, для их последующей параллельной обработки группой процессоров. Основная сложность использования параллельных методов состоит в поиске оптимальной декомпозиции, которая дает сбалансированное распределение доменов по процессорам. Выделяют два основных свойства оптимальной декомпозиции, которые должны выполняться одновременно:
*минимизация максимального веса исходящих из домена ребер
*равномерное распределение по доменам суммарного веса узлов/ребер

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

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

Выделяют следующие '''достоинства''' данного алгоритма:
*высокая скорость работы
*низкий уровень дисбаланса распределения вершин между доменами
*экономичность по памяти
===Математическое описание алгоритма===
----
Пусть на '''вход''' алгоритму подаются следующие данные:
*неориентированный граф <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>

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

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

=== Схема реализации последовательного алгоритма===
----
Представим последовательную реализацию метода рекурсивной координатной бисекции с помощью псевдокода:
 <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}|>1 : BisectCoordRec\{V_{l},\frac{(iend-istart)*\frac{p+1}{2}}{p} , \frac{p+1}{2}, p\}</math>
 <math>if |V_{r}|>1 : BisectCoordRec\{V_{r}, (iend-istart) - \frac{(iend-istart)*\frac{p+1}{2}}{p} , p - \frac{p+1}{2}, p\}</math>
 }
=== Последовательная сложность алгоритма===
----
Пусть в графе <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.5
#Параллельные вызовы алгоритма для каждого процессора
##вызов локальной координатной бисекции по доменам

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

----

'''Вход алгоритма:'''
*неориентированный граф <math>G=(V, E)</math>, где <math>V</math> - множество вершин, <math>E</math> - множество ребер
*Требуемое число доменов <math>p</math>

'''Выход алгоритма:'''
*<math>p</math> доменов <math>\{S_{p}\}</math>, задающих декомпозицию графа
=== Свойства алгоритма===
----

==Программная реализация алгоритма==
----
=== Особенности реализации последовательного алгоритма===
=== Локальность данных и вычислений===
=== Возможные способы и особенности параллельной реализации алгоритма===
=== Масштабируемость алгоритма и его реализации===
=== Динамические характеристики и эффективность реализации алгоритма===
=== Выводы для классов архитектур===
=== Существующие реализации алгоритма===

----
'''Параллельные''' реализации:
*PARMETIS
*JOSTLE
*PT-SCOTCH
*ZOLTAN

'''Последовательные''' реализации:
*METIS
*JOSTLE
*SCOTCH
*CHACO
*PARTY

== Литература==
----
[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

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

2016-10-15T21:09:50Z

Юлия Жосан: /* Ресурс параллелизма алгоритма */

Автор: [[User:Юлия Жосан|Юлия Жосан]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
----
'''Декомпозиция графа''' - это задача его разбиения на непересекающиеся подмножества доменов, для их последующей параллельной обработки группой процессоров. Основная сложность использования параллельных методов состоит в поиске оптимальной декомпозиции, которая дает сбалансированное распределение доменов по процессорам. Выделяют два основных свойства оптимальной декомпозиции, которые должны выполняться одновременно:
*минимизация максимального веса исходящих из домена ребер
*равномерное распределение по доменам суммарного веса узлов/ребер

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

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

Выделяют следующие '''достоинства''' данного алгоритма:
*высокая скорость работы
*низкий уровень дисбаланса распределения вершин между доменами
*экономичность по памяти
===Математическое описание алгоритма===
----
Пусть на '''вход''' алгоритму подаются следующие данные:
*неориентированный граф <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>

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

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

=== Схема реализации последовательного алгоритма===
----
Представим последовательную реализацию метода рекурсивной координатной бисекции с помощью псевдокода:
 <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}|>1 : BisectCoordRec\{V_{l},\frac{(iend-istart)*\frac{p+1}{2}}{p} , \frac{p+1}{2}, p\}</math>
 <math>if |V_{r}|>1 : BisectCoordRec\{V_{r}, (iend-istart) - \frac{(iend-istart)*\frac{p+1}{2}}{p} , p - \frac{p+1}{2}, p\}</math>
 }
=== Последовательная сложность алгоритма===
----
Пусть в графе <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.5
#Параллельные вызовы алгоритма для каждого процессора
**вызов локальной координатной бисекции по доменам

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

----

'''Вход алгоритма:'''
*неориентированный граф <math>G=(V, E)</math>, где <math>V</math> - множество вершин, <math>E</math> - множество ребер
*Требуемое число доменов <math>p</math>

'''Выход алгоритма:'''
*<math>p</math> доменов <math>\{S_{p}\}</math>, задающих декомпозицию графа
=== Свойства алгоритма===
----

==Программная реализация алгоритма==
----
=== Особенности реализации последовательного алгоритма===
=== Локальность данных и вычислений===
=== Возможные способы и особенности параллельной реализации алгоритма===
=== Масштабируемость алгоритма и его реализации===
=== Динамические характеристики и эффективность реализации алгоритма===
=== Выводы для классов архитектур===
=== Существующие реализации алгоритма===

----
'''Параллельные''' реализации:
*PARMETIS
*JOSTLE
*PT-SCOTCH
*ZOLTAN

'''Последовательные''' реализации:
*METIS
*JOSTLE
*SCOTCH
*CHACO
*PARTY

== Литература==
----
[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

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

2016-10-15T21:01:54Z

Юлия Жосан: /* Ресурс параллелизма алгоритма */

Автор: [[User:Юлия Жосан|Юлия Жосан]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
----
'''Декомпозиция графа''' - это задача его разбиения на непересекающиеся подмножества доменов, для их последующей параллельной обработки группой процессоров. Основная сложность использования параллельных методов состоит в поиске оптимальной декомпозиции, которая дает сбалансированное распределение доменов по процессорам. Выделяют два основных свойства оптимальной декомпозиции, которые должны выполняться одновременно:
*минимизация максимального веса исходящих из домена ребер
*равномерное распределение по доменам суммарного веса узлов/ребер

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

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

Выделяют следующие '''достоинства''' данного алгоритма:
*высокая скорость работы
*низкий уровень дисбаланса распределения вершин между доменами
*экономичность по памяти
===Математическое описание алгоритма===
----
Пусть на '''вход''' алгоритму подаются следующие данные:
*неориентированный граф <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>

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

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

=== Схема реализации последовательного алгоритма===
----
Представим последовательную реализацию метода рекурсивной координатной бисекции с помощью псевдокода:
 <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}|>1 : BisectCoordRec\{V_{l},\frac{(iend-istart)*\frac{p+1}{2}}{p} , \frac{p+1}{2}, p\}</math>
 <math>if |V_{r}|>1 : BisectCoordRec\{V_{r}, (iend-istart) - \frac{(iend-istart)*\frac{p+1}{2}}{p} , p - \frac{p+1}{2}, p\}</math>
 }
=== Последовательная сложность алгоритма===
----
Пусть в графе <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.5
#вызов локальной координатной бисекции по доменам на конкретных процессорах

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

----

'''Вход алгоритма:'''
*неориентированный граф <math>G=(V, E)</math>, где <math>V</math> - множество вершин, <math>E</math> - множество ребер
*Требуемое число доменов <math>p</math>

'''Выход алгоритма:'''
*<math>p</math> доменов <math>\{S_{p}\}</math>, задающих декомпозицию графа
=== Свойства алгоритма===
----

==Программная реализация алгоритма==
----
=== Особенности реализации последовательного алгоритма===
=== Локальность данных и вычислений===
=== Возможные способы и особенности параллельной реализации алгоритма===
=== Масштабируемость алгоритма и его реализации===
=== Динамические характеристики и эффективность реализации алгоритма===
=== Выводы для классов архитектур===
=== Существующие реализации алгоритма===

----
'''Параллельные''' реализации:
*PARMETIS
*JOSTLE
*PT-SCOTCH
*ZOLTAN

'''Последовательные''' реализации:
*METIS
*JOSTLE
*SCOTCH
*CHACO
*PARTY

== Литература==
----
[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

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

2016-10-15T21:01:38Z

Юлия Жосан: /* Ресурс параллелизма алгоритма */

Автор: [[User:Юлия Жосан|Юлия Жосан]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
----
'''Декомпозиция графа''' - это задача его разбиения на непересекающиеся подмножества доменов, для их последующей параллельной обработки группой процессоров. Основная сложность использования параллельных методов состоит в поиске оптимальной декомпозиции, которая дает сбалансированное распределение доменов по процессорам. Выделяют два основных свойства оптимальной декомпозиции, которые должны выполняться одновременно:
*минимизация максимального веса исходящих из домена ребер
*равномерное распределение по доменам суммарного веса узлов/ребер

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

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

Выделяют следующие '''достоинства''' данного алгоритма:
*высокая скорость работы
*низкий уровень дисбаланса распределения вершин между доменами
*экономичность по памяти
===Математическое описание алгоритма===
----
Пусть на '''вход''' алгоритму подаются следующие данные:
*неориентированный граф <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>

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

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

=== Схема реализации последовательного алгоритма===
----
Представим последовательную реализацию метода рекурсивной координатной бисекции с помощью псевдокода:
 <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}|>1 : BisectCoordRec\{V_{l},\frac{(iend-istart)*\frac{p+1}{2}}{p} , \frac{p+1}{2}, p\}</math>
 <math>if |V_{r}|>1 : BisectCoordRec\{V_{r}, (iend-istart) - \frac{(iend-istart)*\frac{p+1}{2}}{p} , p - \frac{p+1}{2}, p\}</math>
 }
=== Последовательная сложность алгоритма===
----
Пусть в графе <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>
=== Информационный граф===
----
=== Ресурс параллелизма алгоритма===
----
Структура параллельного алгоритма:
#определение числа требуемых доменов
#вызов рекурсивной покоординатной бисекции по процессорам в соответствии с п.
#вызов локальной координатной бисекции по доменам на конкретных процессорах

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

----

'''Вход алгоритма:'''
*неориентированный граф <math>G=(V, E)</math>, где <math>V</math> - множество вершин, <math>E</math> - множество ребер
*Требуемое число доменов <math>p</math>

'''Выход алгоритма:'''
*<math>p</math> доменов <math>\{S_{p}\}</math>, задающих декомпозицию графа
=== Свойства алгоритма===
----

==Программная реализация алгоритма==
----
=== Особенности реализации последовательного алгоритма===
=== Локальность данных и вычислений===
=== Возможные способы и особенности параллельной реализации алгоритма===
=== Масштабируемость алгоритма и его реализации===
=== Динамические характеристики и эффективность реализации алгоритма===
=== Выводы для классов архитектур===
=== Существующие реализации алгоритма===

----
'''Параллельные''' реализации:
*PARMETIS
*JOSTLE
*PT-SCOTCH
*ZOLTAN

'''Последовательные''' реализации:
*METIS
*JOSTLE
*SCOTCH
*CHACO
*PARTY

== Литература==
----
[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

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

2016-10-15T20:57:29Z

Юлия Жосан: /* Программная реализация алгоритма */

Автор: [[User:Юлия Жосан|Юлия Жосан]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
----
'''Декомпозиция графа''' - это задача его разбиения на непересекающиеся подмножества доменов, для их последующей параллельной обработки группой процессоров. Основная сложность использования параллельных методов состоит в поиске оптимальной декомпозиции, которая дает сбалансированное распределение доменов по процессорам. Выделяют два основных свойства оптимальной декомпозиции, которые должны выполняться одновременно:
*минимизация максимального веса исходящих из домена ребер
*равномерное распределение по доменам суммарного веса узлов/ребер

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

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

Выделяют следующие '''достоинства''' данного алгоритма:
*высокая скорость работы
*низкий уровень дисбаланса распределения вершин между доменами
*экономичность по памяти
===Математическое описание алгоритма===
----
Пусть на '''вход''' алгоритму подаются следующие данные:
*неориентированный граф <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>

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

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

=== Схема реализации последовательного алгоритма===
----
Представим последовательную реализацию метода рекурсивной координатной бисекции с помощью псевдокода:
 <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}|>1 : BisectCoordRec\{V_{l},\frac{(iend-istart)*\frac{p+1}{2}}{p} , \frac{p+1}{2}, p\}</math>
 <math>if |V_{r}|>1 : BisectCoordRec\{V_{r}, (iend-istart) - \frac{(iend-istart)*\frac{p+1}{2}}{p} , p - \frac{p+1}{2}, p\}</math>
 }
=== Последовательная сложность алгоритма===
----
Пусть в графе <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>
=== Информационный граф===
----
=== Ресурс параллелизма алгоритма===
----

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

----

'''Вход алгоритма:'''
*неориентированный граф <math>G=(V, E)</math>, где <math>V</math> - множество вершин, <math>E</math> - множество ребер
*Требуемое число доменов <math>p</math>

'''Выход алгоритма:'''
*<math>p</math> доменов <math>\{S_{p}\}</math>, задающих декомпозицию графа
=== Свойства алгоритма===
----

==Программная реализация алгоритма==
----
=== Особенности реализации последовательного алгоритма===
=== Локальность данных и вычислений===
=== Возможные способы и особенности параллельной реализации алгоритма===
=== Масштабируемость алгоритма и его реализации===
=== Динамические характеристики и эффективность реализации алгоритма===
=== Выводы для классов архитектур===
=== Существующие реализации алгоритма===

----
'''Параллельные''' реализации:
*PARMETIS
*JOSTLE
*PT-SCOTCH
*ZOLTAN

'''Последовательные''' реализации:
*METIS
*JOSTLE
*SCOTCH
*CHACO
*PARTY

== Литература==
----
[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

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

2016-10-15T20:57:09Z

Юлия Жосан: /* Литература */

Автор: [[User:Юлия Жосан|Юлия Жосан]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
----
'''Декомпозиция графа''' - это задача его разбиения на непересекающиеся подмножества доменов, для их последующей параллельной обработки группой процессоров. Основная сложность использования параллельных методов состоит в поиске оптимальной декомпозиции, которая дает сбалансированное распределение доменов по процессорам. Выделяют два основных свойства оптимальной декомпозиции, которые должны выполняться одновременно:
*минимизация максимального веса исходящих из домена ребер
*равномерное распределение по доменам суммарного веса узлов/ребер

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

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

Выделяют следующие '''достоинства''' данного алгоритма:
*высокая скорость работы
*низкий уровень дисбаланса распределения вершин между доменами
*экономичность по памяти
===Математическое описание алгоритма===
----
Пусть на '''вход''' алгоритму подаются следующие данные:
*неориентированный граф <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>

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

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

=== Схема реализации последовательного алгоритма===
----
Представим последовательную реализацию метода рекурсивной координатной бисекции с помощью псевдокода:
 <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}|>1 : BisectCoordRec\{V_{l},\frac{(iend-istart)*\frac{p+1}{2}}{p} , \frac{p+1}{2}, p\}</math>
 <math>if |V_{r}|>1 : BisectCoordRec\{V_{r}, (iend-istart) - \frac{(iend-istart)*\frac{p+1}{2}}{p} , p - \frac{p+1}{2}, p\}</math>
 }
=== Последовательная сложность алгоритма===
----
Пусть в графе <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>
=== Информационный граф===
----
=== Ресурс параллелизма алгоритма===
----

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

----

'''Вход алгоритма:'''
*неориентированный граф <math>G=(V, E)</math>, где <math>V</math> - множество вершин, <math>E</math> - множество ребер
*Требуемое число доменов <math>p</math>

'''Выход алгоритма:'''
*<math>p</math> доменов <math>\{S_{p}\}</math>, задающих декомпозицию графа
=== Свойства алгоритма===
----

==Программная реализация алгоритма==
----
=== Особенности реализации последовательного алгоритма===
=== Локальность данных и вычислений===
=== Возможные способы и особенности параллельной реализации алгоритма===
=== Масштабируемость алгоритма и его реализации===
=== Динамические характеристики и эффективность реализации алгоритма===
=== Выводы для классов архитектур===
=== Существующие реализации алгоритма===
'''Параллельные''' реализации:
*PARMETIS
*JOSTLE
*PT-SCOTCH
*ZOLTAN

'''Последовательные''' реализации:
*METIS
*JOSTLE
*SCOTCH
*CHACO
*PARTY

== Литература==
----
[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

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

2016-10-15T20:56:55Z

Юлия Жосан: /* Литература */

Автор: [[User:Юлия Жосан|Юлия Жосан]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
----
'''Декомпозиция графа''' - это задача его разбиения на непересекающиеся подмножества доменов, для их последующей параллельной обработки группой процессоров. Основная сложность использования параллельных методов состоит в поиске оптимальной декомпозиции, которая дает сбалансированное распределение доменов по процессорам. Выделяют два основных свойства оптимальной декомпозиции, которые должны выполняться одновременно:
*минимизация максимального веса исходящих из домена ребер
*равномерное распределение по доменам суммарного веса узлов/ребер

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

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

Выделяют следующие '''достоинства''' данного алгоритма:
*высокая скорость работы
*низкий уровень дисбаланса распределения вершин между доменами
*экономичность по памяти
===Математическое описание алгоритма===
----
Пусть на '''вход''' алгоритму подаются следующие данные:
*неориентированный граф <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>

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

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

=== Схема реализации последовательного алгоритма===
----
Представим последовательную реализацию метода рекурсивной координатной бисекции с помощью псевдокода:
 <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}|>1 : BisectCoordRec\{V_{l},\frac{(iend-istart)*\frac{p+1}{2}}{p} , \frac{p+1}{2}, p\}</math>
 <math>if |V_{r}|>1 : BisectCoordRec\{V_{r}, (iend-istart) - \frac{(iend-istart)*\frac{p+1}{2}}{p} , p - \frac{p+1}{2}, p\}</math>
 }
=== Последовательная сложность алгоритма===
----
Пусть в графе <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>
=== Информационный граф===
----
=== Ресурс параллелизма алгоритма===
----

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

----

'''Вход алгоритма:'''
*неориентированный граф <math>G=(V, E)</math>, где <math>V</math> - множество вершин, <math>E</math> - множество ребер
*Требуемое число доменов <math>p</math>

'''Выход алгоритма:'''
*<math>p</math> доменов <math>\{S_{p}\}</math>, задающих декомпозицию графа
=== Свойства алгоритма===
----

==Программная реализация алгоритма==
----
=== Особенности реализации последовательного алгоритма===
=== Локальность данных и вычислений===
=== Возможные способы и особенности параллельной реализации алгоритма===
=== Масштабируемость алгоритма и его реализации===
=== Динамические характеристики и эффективность реализации алгоритма===
=== Выводы для классов архитектур===
=== Существующие реализации алгоритма===
'''Параллельные''' реализации:
*PARMETIS
*JOSTLE
*PT-SCOTCH
*ZOLTAN

'''Последовательные''' реализации:
*METIS
*JOSTLE
*SCOTCH
*CHACO
*PARTY

== Литература==
----
[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] Wikipedia.ru

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

2016-10-15T20:55:21Z

Юлия Жосан: /* Существующие реализации алгоритма */

Автор: [[User:Юлия Жосан|Юлия Жосан]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
----
'''Декомпозиция графа''' - это задача его разбиения на непересекающиеся подмножества доменов, для их последующей параллельной обработки группой процессоров. Основная сложность использования параллельных методов состоит в поиске оптимальной декомпозиции, которая дает сбалансированное распределение доменов по процессорам. Выделяют два основных свойства оптимальной декомпозиции, которые должны выполняться одновременно:
*минимизация максимального веса исходящих из домена ребер
*равномерное распределение по доменам суммарного веса узлов/ребер

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

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

Выделяют следующие '''достоинства''' данного алгоритма:
*высокая скорость работы
*низкий уровень дисбаланса распределения вершин между доменами
*экономичность по памяти
===Математическое описание алгоритма===
----
Пусть на '''вход''' алгоритму подаются следующие данные:
*неориентированный граф <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>

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

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

=== Схема реализации последовательного алгоритма===
----
Представим последовательную реализацию метода рекурсивной координатной бисекции с помощью псевдокода:
 <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}|>1 : BisectCoordRec\{V_{l},\frac{(iend-istart)*\frac{p+1}{2}}{p} , \frac{p+1}{2}, p\}</math>
 <math>if |V_{r}|>1 : BisectCoordRec\{V_{r}, (iend-istart) - \frac{(iend-istart)*\frac{p+1}{2}}{p} , p - \frac{p+1}{2}, p\}</math>
 }
=== Последовательная сложность алгоритма===
----
Пусть в графе <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>
=== Информационный граф===
----
=== Ресурс параллелизма алгоритма===
----

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

----

'''Вход алгоритма:'''
*неориентированный граф <math>G=(V, E)</math>, где <math>V</math> - множество вершин, <math>E</math> - множество ребер
*Требуемое число доменов <math>p</math>

'''Выход алгоритма:'''
*<math>p</math> доменов <math>\{S_{p}\}</math>, задающих декомпозицию графа
=== Свойства алгоритма===
----

==Программная реализация алгоритма==
----
=== Особенности реализации последовательного алгоритма===
=== Локальность данных и вычислений===
=== Возможные способы и особенности параллельной реализации алгоритма===
=== Масштабируемость алгоритма и его реализации===
=== Динамические характеристики и эффективность реализации алгоритма===
=== Выводы для классов архитектур===
=== Существующие реализации алгоритма===
'''Параллельные''' реализации:
*PARMETIS
*JOSTLE
*PT-SCOTCH
*ZOLTAN

'''Последовательные''' реализации:
*METIS
*JOSTLE
*SCOTCH
*CHACO
*PARTY

== Литература==
----
[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

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

2016-10-15T20:52:12Z

Юлия Жосан: /* Свойства и структура алгоритмов */

Автор: [[User:Юлия Жосан|Юлия Жосан]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
----
'''Декомпозиция графа''' - это задача его разбиения на непересекающиеся подмножества доменов, для их последующей параллельной обработки группой процессоров. Основная сложность использования параллельных методов состоит в поиске оптимальной декомпозиции, которая дает сбалансированное распределение доменов по процессорам. Выделяют два основных свойства оптимальной декомпозиции, которые должны выполняться одновременно:
*минимизация максимального веса исходящих из домена ребер
*равномерное распределение по доменам суммарного веса узлов/ребер

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

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

Выделяют следующие '''достоинства''' данного алгоритма:
*высокая скорость работы
*низкий уровень дисбаланса распределения вершин между доменами
*экономичность по памяти
===Математическое описание алгоритма===
----
Пусть на '''вход''' алгоритму подаются следующие данные:
*неориентированный граф <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>

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

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

=== Схема реализации последовательного алгоритма===
----
Представим последовательную реализацию метода рекурсивной координатной бисекции с помощью псевдокода:
 <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}|>1 : BisectCoordRec\{V_{l},\frac{(iend-istart)*\frac{p+1}{2}}{p} , \frac{p+1}{2}, p\}</math>
 <math>if |V_{r}|>1 : BisectCoordRec\{V_{r}, (iend-istart) - \frac{(iend-istart)*\frac{p+1}{2}}{p} , p - \frac{p+1}{2}, p\}</math>
 }
=== Последовательная сложность алгоритма===
----
Пусть в графе <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>
=== Информационный граф===
----
=== Ресурс параллелизма алгоритма===
----

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

----

'''Вход алгоритма:'''
*неориентированный граф <math>G=(V, E)</math>, где <math>V</math> - множество вершин, <math>E</math> - множество ребер
*Требуемое число доменов <math>p</math>

'''Выход алгоритма:'''
*<math>p</math> доменов <math>\{S_{p}\}</math>, задающих декомпозицию графа
=== Свойства алгоритма===
----

==Программная реализация алгоритма==
----
=== Особенности реализации последовательного алгоритма===
=== Локальность данных и вычислений===
=== Возможные способы и особенности параллельной реализации алгоритма===
=== Масштабируемость алгоритма и его реализации===
=== Динамические характеристики и эффективность реализации алгоритма===
=== Выводы для классов архитектур===
=== Существующие реализации алгоритма===
== Литература==
----
[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

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

2016-10-15T20:22:32Z

Юлия Жосан: /* Свойства и структура алгоритмов */

Автор: [[User:Юлия Жосан|Юлия Жосан]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
----
'''Декомпозиция графа''' - это задача его разбиения на непересекающиеся подмножества доменов, для их последующей параллельной обработки группой процессоров. Основная сложность использования параллельных методов состоит в поиске оптимальной декомпозиции, которая дает сбалансированное распределение доменов по процессорам. Выделяют два основных свойства оптимальной декомпозиции, которые должны выполняться одновременно:
*минимизация максимального веса исходящих из домена ребер
*равномерное распределение по доменам суммарного веса узлов/ребер

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

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

Выделяют следующие '''достоинства''' данного алгоритма:
*высокая скорость работы
*низкий уровень дисбаланса распределения вершин между доменами
*экономичность по памяти
===Математическое описание алгоритма===
----
Пусть на '''вход''' алгоритму подаются следующие данные:
*неориентированный граф <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>

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

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

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

=== Последовательная сложность алгоритма===
----
Пусть в графе <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}log_{2}p)</math>
=== Информационный граф===
----
=== Ресурс параллелизма алгоритма===
----

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

----

'''Вход алгоритма:'''
*неориентированный граф <math>G=(V, E)</math>, где <math>V</math> - множество вершин, <math>E</math> - множество ребер
*Требуемое число доменов <math>p</math>

'''Выход алгоритма:'''
*<math>p</math> доменов <math>\{S_{p}\}</math>, задающих декомпозицию графа
=== Свойства алгоритма===
----

==Программная реализация алгоритма==
----
=== Особенности реализации последовательного алгоритма===
=== Локальность данных и вычислений===
=== Возможные способы и особенности параллельной реализации алгоритма===
=== Масштабируемость алгоритма и его реализации===
=== Динамические характеристики и эффективность реализации алгоритма===
=== Выводы для классов архитектур===
=== Существующие реализации алгоритма===
== Литература==
----
[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

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

2016-10-15T20:04:54Z

Юлия Жосан: /* Макроструктура алгоритма */

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

2016-10-15T20:04:42Z

Юлия Жосан: /* Макроструктура алгоритма */

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

2016-10-15T20:01:20Z

Юлия Жосан: /* Вычислительное ядро алгоритма */

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

2016-10-15T19:56:37Z

Юлия Жосан: Новая страница: «Автор: User:Юлия Жосан| == Свойства и структура алгоритмов == === Общее описание алгоритма ===…»