Без темы
<<  Образовательный комплекс "Теория и практика параллельного программирования" Образовательный комплекс Введение в методы параллельного программирования  >>
Образовательный комплекс Введение в методы параллельного
Образовательный комплекс Введение в методы параллельного
Содержание
Содержание
Обработка графов…
Обработка графов…
Обработка графов…
Обработка графов…
Обработка графов…
Обработка графов…
Обработка графов
Обработка графов
Задача поиска всех кратчайших путей…
Задача поиска всех кратчайших путей…
Задача поиска всех кратчайших путей…
Задача поиска всех кратчайших путей…
Задача поиска всех кратчайших путей…
Задача поиска всех кратчайших путей…
Задача поиска всех кратчайших путей…
Задача поиска всех кратчайших путей…
Задача поиска всех кратчайших путей…
Задача поиска всех кратчайших путей…
Задача поиска всех кратчайших путей…
Задача поиска всех кратчайших путей…
Задача поиска всех кратчайших путей…
Задача поиска всех кратчайших путей…
Задача поиска всех кратчайших путей…
Задача поиска всех кратчайших путей…
Задача поиска всех кратчайших путей…
Задача поиска всех кратчайших путей…
Задача поиска всех кратчайших путей
Задача поиска всех кратчайших путей
Постановка задачи: Охватывающим деревом (или остовом)
Постановка задачи: Охватывающим деревом (или остовом)
Пример нахождения МОД
Пример нахождения МОД
Последовательный алгоритм Прима:… Пусть VT есть множество вершин, уже
Последовательный алгоритм Прима:… Пусть VT есть множество вершин, уже
Последовательный алгоритм Прима: Действия, выполняемые на каждой
Последовательный алгоритм Прима: Действия, выполняемые на каждой
Задача нахождения минимального охватывающего дерева…
Задача нахождения минимального охватывающего дерева…
Задача нахождения минимального охватывающего дерева…
Задача нахождения минимального охватывающего дерева…
Масштабирование и распределение подзадач по процессорам: Распределение
Масштабирование и распределение подзадач по процессорам: Распределение
Анализ эффективности: Общая оценка показателей ускорения и
Анализ эффективности: Общая оценка показателей ускорения и
Анализ эффективности (уточненные оценки):
Анализ эффективности (уточненные оценки):
Задача нахождения минимального охватывающего дерева…
Задача нахождения минимального охватывающего дерева…
Задача нахождения минимального охватывающего дерева
Задача нахождения минимального охватывающего дерева
Задача оптимального разделения графов…
Задача оптимального разделения графов…
Задача оптимального разделения графов…
Задача оптимального разделения графов…
Задача оптимального разделения графов…
Задача оптимального разделения графов…
Задача оптимального разделения графов…
Задача оптимального разделения графов…
Задача оптимального разделения графов…
Задача оптимального разделения графов…
Задача оптимального разделения графов…
Задача оптимального разделения графов…
Задача оптимального разделения графов…
Задача оптимального разделения графов…
Задача оптимального разделения графов:
Задача оптимального разделения графов:
Задача оптимального разделения графов…
Задача оптимального разделения графов…
Задача оптимального разделения графов…
Задача оптимального разделения графов…
Задача оптимального разделения графов…
Задача оптимального разделения графов…
Задача оптимального разделения графов…
Задача оптимального разделения графов…
Задача оптимального разделения графов…
Задача оптимального разделения графов…
Задача оптимального разделения графов…
Задача оптимального разделения графов…
Задача оптимального разделения графов…
Задача оптимального разделения графов…
Задача оптимального разделения графов
Задача оптимального разделения графов
Заключение
Заключение
Вопросы для обсуждения
Вопросы для обсуждения
Темы заданий для самостоятельной работы
Темы заданий для самостоятельной работы
Литература
Литература
Следующая тема
Следующая тема
Авторский коллектив
Авторский коллектив
О проекте
О проекте

Презентация на тему: «Образовательный комплекс Введение в методы параллельного программирования». Автор: Гергель В.П.. Файл: «Образовательный комплекс Введение в методы параллельного программирования.ppt». Размер zip-архива: 483 КБ.

Образовательный комплекс Введение в методы параллельного программирования

содержание презентации «Образовательный комплекс Введение в методы параллельного программирования.ppt»
СлайдТекст
1 Образовательный комплекс Введение в методы параллельного

Образовательный комплекс Введение в методы параллельного

программирования

Лекция 13. Параллельные методы обработки графов

Гергель В.П., профессор, д.т.н. Кафедра математического обеспечения ЭВМ

2 Содержание

Содержание

Обработка графов Задача поиска всех кратчайших путей Задача нахождения минимального охватывающего дерева Проблема оптимального разделения графов Заключение

2 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

3 Обработка графов…

Обработка графов…

Математические модели в виде графов широко используются при моделировании разнообразных явлений, процессов и систем Граф G есть пара:

V – набор вершин графа:

R – набор ребер графа:

В общем случае дугам графа могут приписываться некоторые числовые характеристики (веса):

3 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

4 Обработка графов…

Обработка графов…

Пример взвешенного ориентированного графа

4 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

5 Обработка графов…

Обработка графов…

При малом количестве дуг в графе целесообразно использовать для определения графов списки, перечисляющие имеющиеся в графах дуги Представление достаточно плотных графов, для которых почти все вершины соединены между собой дугами, может быть эффективно обеспечено при помощи матрицы смежности

5 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

6 Обработка графов

Обработка графов

Пример матрицы смежности

6 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

7 Задача поиска всех кратчайших путей…

Задача поиска всех кратчайших путей…

Постановка задачи: Дан граф G, каждому ребру которого приписан неотрицательный вес, Граф полагаем ориентированным, Для имеющегося графа G требуется найти минимальные длины путей между каждой парой вершин графа, В качестве метода, решающего задачу поиска кратчайших путей между всеми парами пунктов назначения, далее используется алгоритм Флойда (Floyd)

7 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

8 Задача поиска всех кратчайших путей…

Задача поиска всех кратчайших путей…

Последовательный алгоритм Флойда: Сложность алгоритма имеет порядок

// Алгоритм 11.1 // Последовательный алгоритм Флойда for (k = 0; k < n; k++) for (i = 0; i < n; i++) for (j = 0; j < n; j++) A[i,j] = min(A[i,j],A[i,k]+A[k,j]);

8 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

9 Задача поиска всех кратчайших путей…

Задача поиска всех кратчайших путей…

Разделение вычислений на независимые части: Эффективный способ организации параллельных вычислений состоит в одновременном выполнении нескольких операций обновления значений матрицы A, На итерации k не происходит изменения элементов Aik и Akj ни для одной пары индексов (i,j), Докажем это: Aij ? min (Aij, Aik + Akj) Для i=k получим: Akj ? min (Akj, Akk + Akj), но тогда значение Akj не изменится, т.к. Akk=0 Аналогично для j=k

9 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

10 Задача поиска всех кратчайших путей…

Задача поиска всех кратчайших путей…

Выделение информационных зависимостей:… Выполнение вычислений в подзадачах становится возможным только тогда, когда каждая подзадача (i,j) содержит необходимые для расчетов элементы Aij, Aik, Akj матрицы A, Каждый элемент Akj строки k матрицы A должен быть передан всем подзадачам (k,j), 1? j? n, а каждый элемент Aik столбца k матрицы A должен быть передан всем подзадачам (i,k), 1? i? n

10 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

11 Задача поиска всех кратчайших путей…

Задача поиска всех кратчайших путей…

Выделение информационных зависимостей: Информационная зависимость базовых подзадач (стрелками показаны направления обмена значениями на итерации k)

11 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

12 Задача поиска всех кратчайших путей…

Задача поиска всех кратчайших путей…

Масштабирование и распределение подзадач по процессорам: Возможный способ укрупнения вычислений состоит в использовании ленточной схемы разбиения матрицы A: обновление элементов одной или нескольких строк (горизонтальное разбиение), обновление элементов одной или нескольких строк (вертикальное разбиение) Далее будем рассматривать только разбиение матрицы A на горизонтальные полосы

12 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

13 Задача поиска всех кратчайших путей…

Задача поиска всех кратчайших путей…

Анализ эффективности: Общая оценка показателей ускорения и эффективности

Разработанный способ параллельных вычислений позволяет достичь идеальных показателей ускорения и эффективности

13 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

14 Задача поиска всех кратчайших путей…

Задача поиска всех кратчайших путей…

Анализ эффективности (уточненные оценки):

Общее время выполнения параллельного алгоритма составляет

- Время выполнения параллельного алгоритма, связанное непосредственно с вычислениями, составляет:

- Оценка трудоемкости выполняемых операций передачи данных может быть определена как:

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

14 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

15 Задача поиска всех кратчайших путей…

Задача поиска всех кратчайших путей…

Результаты вычислительных экспериментов:… Сравнение теоретических оценок Tp и экспериментальных данных Tp*

15 из 49

Количество вершин

Количество вершин

Количество вершин

Последовательный алгоритм

Последовательный алгоритм

Последовательный алгоритм

Последовательный алгоритм

Параллельный алгоритм

Параллельный алгоритм

Параллельный алгоритм

Параллельный алгоритм

Параллельный алгоритм

Параллельный алгоритм

2 процессора

2 процессора

4 процессора

4 процессора

8 процессоров

8 процессоров

1000

41,600

39,686

21,800

20,996

11,900

10,530

6,910

6,590

2000

317,000

306,228

159,000

166,219

80,500

83,468

41,400

48,796

3000

1070,000

1027,611

537,000

557,887

270,000

279,830

137,000

160,013

4000

2540,000

2445,473

1270,000

1320,205

639,000

661,641

323,000

336,713

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

16 Задача поиска всех кратчайших путей

Задача поиска всех кратчайших путей

Результаты вычислительных экспериментов: Ускорение вычислений

16 из 49

Количество вершин

Количество вершин

Количество вершин

Последовательный алгоритм

Последовательный алгоритм

Последовательный алгоритм

Параллельный алгоритм

Параллельный алгоритм

Параллельный алгоритм

Параллельный алгоритм

Параллельный алгоритм

Параллельный алгоритм

2 процессора

2 процессора

4 процессора

4 процессора

8 процессора

8 процессора

Время

Ускорение

Время

Ускорение

Время

Ускорение

1000

39,686

20,996

1,890

10,530

3,769

6,590

6,022

2000

306,228

166,219

1,842

83,468

3,669

48,796

6,276

3000

1027,611

557,887

1,842

279,830

3,672

160,013

6,422

4000

2445,473

1320,205

1,852

661,641

3,696

336,713

7,263

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

17 Постановка задачи: Охватывающим деревом (или остовом)

Постановка задачи: Охватывающим деревом (или остовом)

неориентированного графа G называется подграф T графа G, который является деревом и содержит все вершины из G, Определив вес подграфа для взвешенного графа как сумму весов входящих в подграф дуг, под минимально охватывающим деревом (МОД) T будем понимать охватывающее дерево минимального веса, Таким образом, для данного графа G требуется найти минимальное охватывающее дерево T

Задача нахождения минимального охватывающего дерева…

17 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

18 Пример нахождения МОД

Пример нахождения МОД

Задача нахождения минимального охватывающего дерева…

18 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

19 Последовательный алгоритм Прима:… Пусть VT есть множество вершин, уже

Последовательный алгоритм Прима:… Пусть VT есть множество вершин, уже

включенных алгоритмом в МОД, а величины di, 1?i?n характеризуют дуги минимальной длины от вершин, еще не включенных в дерево, до множества VT, т.е.

Задача нахождения минимального охватывающего дерева…

(если для какой-либо вершины i не существует ни одной дуги в VT, значение di устанавливается в ?) В начале работы алгоритма выбирается корневая вершина МОД s и полагается VT={s}, ds=0 .

19 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

20 Последовательный алгоритм Прима: Действия, выполняемые на каждой

Последовательный алгоритм Прима: Действия, выполняемые на каждой

итерации алгоритма Прима, состоят в следующем: определяются значения величин di для всех вершин, еще не включенных в состав МОД, выбирается вершина t графа G, имеющая дугу минимального веса до множества VT вершина t включается в VT Трудоемкость алгоритма Прима характеризуется квадратичной зависимостью от числа вершин графа

Задача нахождения минимального охватывающего дерева…

20 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

21 Задача нахождения минимального охватывающего дерева…

Задача нахождения минимального охватывающего дерева…

Разделение вычислений на независимые части:… Действия, выполняемые на каждой итерации алгоритма, являются независимыми и могут реализовываться одновременно, Каждый процессор j при равномерной загрузке должен содержать:

(?S есть s-ый столбец матрицы A) общую часть набора vj и формируемого в процессе вычислений множества вершин VT

Набор вершин

Соответствующий этому набору блок из k величин

Вертикальную полосу матрицы смежности графа G из k соседних столбцов

21 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

22 Задача нахождения минимального охватывающего дерева…

Задача нахождения минимального охватывающего дерева…

Выделение информационных зависимостей: Общая схема параллельного выполнения алгоритма Прима будет состоять в следующем: Определяется вершина t графа G, имеющая дугу минимального веса до множества VT; для выбора такой вершины необходимо осуществить поиск минимума в наборах величин di, имеющихся на каждом из процессоров, и выполнить сборку полученных значений на одном из процессоров, Номер выбранной вершины для включения в охватывающее дерево передается всем процессорам, Обновляются наборы величин di с учетом добавления новой вершины Таким образом, в ходе параллельных вычислений между процессорами выполняются два типа информационных взаимодействий - сбор данных от всех процессоров на одном из процессоров и передача сообщений от одного процессора всем процессорам вычислительной системы

22 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

23 Масштабирование и распределение подзадач по процессорам: Распределение

Масштабирование и распределение подзадач по процессорам: Распределение

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

Задача нахождения минимального охватывающего дерева…

23 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

24 Анализ эффективности: Общая оценка показателей ускорения и

Анализ эффективности: Общая оценка показателей ускорения и

эффективности

Задача нахождения минимального охватывающего дерева…

24 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

25 Анализ эффективности (уточненные оценки):

Анализ эффективности (уточненные оценки):

Задача нахождения минимального охватывающего дерева…

Общее время выполнения параллельного алгоритма составляет

- Время выполнения параллельного алгоритма, связанное непосредственно с вычислениями, составляет

- Оценка трудоемкости выполняемых операций передачи данных может быть определена как

25 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

26 Задача нахождения минимального охватывающего дерева…

Задача нахождения минимального охватывающего дерева…

Результаты вычислительных экспериментов:… Сравнение теоретических оценок Tp и экспериментальных данных Tp*

26 из 49

Количество вершин

Количество вершин

Количество вершин

Последовательный алгоритм

Последовательный алгоритм

Последовательный алгоритм

Последовательный алгоритм

Параллельный алгоритм

Параллельный алгоритм

Параллельный алгоритм

Параллельный алгоритм

Параллельный алгоритм

Параллельный алгоритм

2 процессора

2 процессора

4 процессора

4 процессора

6 процессоров

6 процессоров

7750

4,234

4,137

3,778

3,971

4,383

3,462

5,005

3,837

8000

4,512

4,498

3,971

4,148

4,560

3,621

5,190

3,976

8250

4,798

4,800

4,168

4,442

4,739

3,763

5,376

4,120

8500

5,094

5,206

4,369

4,680

4,920

3,992

5,564

4,241

8750

5,398

5,689

4,574

4,950

5,103

4,623

5,754

4,424

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

27 Задача нахождения минимального охватывающего дерева

Задача нахождения минимального охватывающего дерева

Результаты вычислительных экспериментов: Ускорение вычислений

27 из 49

Количество вершин

Количество вершин

Количество вершин

Последовательный алгоритм

Последовательный алгоритм

Параллельный алгоритм

Параллельный алгоритм

Параллельный алгоритм

Параллельный алгоритм

Параллельный алгоритм

Параллельный алгоритм

2 процессора

2 процессора

4 процессора

4 процессора

6 процессора

6 процессора

Время

Время

Ускорение

Время

Ускорение

Время

Ускорение

7750

4,137

3,971

1,042

3,462

1,195

3,837

1,078

8000

4,498

4,148

1,084

3,621

1,242

3,976

1,131

8250

4,800

4,442

1,081

3,763

1,276

4,120

1,165

8500

5,206

4,680

1,112

3,992

1,304

4,241

1,228

8750

5,689

4,950

1,149

4,623

1,231

4,424

1,286

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

28 Задача оптимального разделения графов…

Задача оптимального разделения графов…

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

28 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

29 Задача оптимального разделения графов…

Задача оптимального разделения графов…

Пример разделения нерегулярной сетки и соответствующий сетке граф:

29 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

30 Задача оптимального разделения графов…

Задача оптимального разделения графов…

Постановка задачи: Пусть дан взвешенный неориентированный граф G=(V,E), каждой вершине v и каждому ребру e которого приписан вес, Задача оптимального разделения графа состоит в разбиении его вершин на непересекающиеся подмножества с максимально близкими суммарными весами вершин и минимальным суммарным весом ребер, проходящих между полученными подмножествами вершин, Далее будем полагать веса вершин и ребер графа равными единице

30 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

31 Задача оптимального разделения графов…

Задача оптимального разделения графов…

Метод рекурсивного деления пополам: Для решения задачи разбиения графа можно рекурсивно применить метод бинарного деления, при котором на первой итерации граф разделяется на две равные части, далее на втором шаге каждая из полученных частей также разбивается на две части и т.д. В данном подходе для разбиения графа на k частей необходимо log2(k) уровней рекурсии и выполнение k-1 деления пополам. В случае, когда требуемое количество разбиений k не является степенью двойки, каждое деление пополам необходимо осуществлять в соответствующем соотношении

31 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

32 Задача оптимального разделения графов…

Задача оптимального разделения графов…

Пример разбиения графа на 5 частей методом рекурсивного деления пополам

32 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

33 Задача оптимального разделения графов…

Задача оптимального разделения графов…

Геометрические методы: Геометрические методы выполняют разбиение сетей, основываясь исключительно на координатной информации об узлах сети, Так как геометрические методы не принимают во внимание информацию о связности элементов сети, то они не могут явно привести к минимизации суммарного веса граничных ребер. Для минимизации межпроцессорных коммуникаций геометрические методы оптимизируют некоторые вспомогательные показатели (например, длину границы между разделенными участками сети), Геометрические методы работают исключительно быстро, Рассматриваемые геометрические методы: Покоординатное разбиение, Рекурсивный инерционный метод деления пополам, Деление сети с использованием кривых Пеано

33 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

34 Задача оптимального разделения графов…

Задача оптимального разделения графов…

Покоординатное разбиение: Общая схема выполнения метода: Вычисляются центры масс элементов сети, Полученные точки проектируются на ось, соответствующую наибольшей стороне разделяемой сети

34 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

35 Задача оптимального разделения графов:

Задача оптимального разделения графов:

Рекурсивный инерционный метод деления пополам: Рекурсивном инерционном методе деления пополам строит главную инерционную ось, считая элементы сети точечными массами, Линия бисекции, ортогональная полученной оси, как правило, дает границу наименьшей длины

35 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

36 Задача оптимального разделения графов…

Задача оптимального разделения графов…

Деление сети с использованием кривых Пеано: Кривые Пеано – это кривые, полностью заполняющие фигуры больших размерностей (например, квадрат или куб), После получения списка элементов сети, упорядоченного в соответствии с расположением на кривой, достаточно разделить список на необходимое число частей в соответствии с установленным порядком

36 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

37 Задача оптимального разделения графов…

Задача оптимального разделения графов…

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

37 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

38 Задача оптимального разделения графов…

Задача оптимального разделения графов…

Деление с учетом связности: На каждой итерации алгоритма происходит разделение графа на 2 части. Разделение графа на требуемое число частей достигается путем рекурсивного применения алгоритма Общая схема алгоритма: 1. Iteration = 0 2. Присвоение номера Iteration произвольной вершине графа 3. Присвоение ненумерованным соседям вершин с номером Iteration номера Iteration + 1 4. Iteration = Iteration + 1 5. Если еще есть неперенумерованные соседи, то переход на шаг 3 6. Разделение графа на 2 части в порядке нумерации

38 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

39 Задача оптимального разделения графов…

Задача оптимального разделения графов…

Пример работы алгоритма деления с учетом связности

39 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

40 Задача оптимального разделения графов…

Задача оптимального разделения графов…

Алгоритм Кернигана-Лина (общая схема):… Предполагается, что некоторое начальное разбиение графа уже существует. Далее имеющееся приближение улучшается в течение некоторого количества итераций: 1. Формирование множества пар вершин для перестановки Из вершин, которые еще не были переставлены на данной итерации, формируются все возможные пары (в парах должны присутствовать по одной вершине из каждой части имеющегося разбиения графа). 2. Построение новых вариантов разбиения графа Каждая пара, подготовленная на шаге 1, поочередно используется для обмена вершин между частями имеющегося разбиения графа для получения множества новых вариантов деления.

40 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

41 Задача оптимального разделения графов…

Задача оптимального разделения графов…

Алгоритм Кернигана-Лина (общая схема): 3. Выбор лучшего варианта разбиения графа Для сформированного на шаге 2 множества новых делений графа выбирается лучший вариант. Данный способ фиксируется как новое текущее разбиение графа, а соответствующая выбранному варианту пара вершин отмечается как использованная на текущей итерации алгоритма 4. Проверка использования всех вершин При наличии в графе вершин, еще неиспользованных при перестановках, выполнение итерации алгоритма снова продолжается с шага 1. Если же перебор вершин графа завершен, далее следует шаг 5. 5. Выбор наилучшего варианта разбиения графа Среди всех разбиений графа, полученных на шаге 3 проведенных итераций, выбирается (и фиксируется) наилучший вариант разбиения графа.

41 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

42 Задача оптимального разделения графов…

Задача оптимального разделения графов…

Пример работы алгоритма Кернигана-Лина: В приведенном примере переставляются 2 вершины (выделены серым)

42 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

43 Задача оптимального разделения графов

Задача оптимального разделения графов

Сравнительная таблица некоторых алгоритмов разделения графов

?

?

???

??

?

???

??

??

??

??

??

?

???

???

??

????

???

??

Необходимость координатной информации

Точность

Время выполнения

Возможности для распараллеливания

Покоординатное разбиение

Покоординатное разбиение

Да

Рекурсивный инерционный метод деления пополам

Рекурсивный инерционный метод деления пополам

Да

Деление с учетом связности

Деление с учетом связности

Нет

Алгоритм Кернигана-Лина

Алгоритм Кернигана-Лина

Алгоритм Кернигана-Лина

1 итерация

Нет

10 итераций

Нет

50 итераций

Нет

43 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

44 Заключение

Заключение

В разделе был рассмотрены ряд алгоритмов для решения типовых задач обработки графов: Алгоритм Флойда, Алгоритм Прима Был приведен обзор методов разделения графа: Геометрические методы: Покоординатное разбиение, Рекурсивный инерционный метод деления пополам, Деление сети с использованием кривых Пеано Комбинаторные методы: Деление с учетом связности, Алгоритм Кернигана-Лина

44 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

45 Вопросы для обсуждения

Вопросы для обсуждения

Приведите определение графа. Какие основные способы используются для задания графов? В чем состоит задача поиска всех кратчайших путей? Приведите общую схему алгоритма Флойда. Какова трудоемкость алгоритма? В чем состоит способ распараллеливания алгоритма Флойда? В чем заключается задача нахождения минимального охватывающего дерева? Приведите пример использования задачи на практике. Приведите общую схему алгоритма Прима. Какова трудоемкость алгоритма? В чем состоит способ распараллеливания алгоритма Прима? В чем отличие геометрических и комбинаторных методов разделения графа? Какие методы являются более предпочтительными? Почему? Приведите описание метода покоординатного разбиения и алгоритма разделения с учетом связности. Какой из этих методов является более простым для практической реализации?

45 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

46 Темы заданий для самостоятельной работы

Темы заданий для самостоятельной работы

Выполните реализацию параллельного алгоритма Флойда. Проведите вычислительные эксперименты. Постройте теоретические оценки с учетом параметров используемой вычислительной системы. Сравните полученные оценки с экспериментальными данными. Выполните реализацию параллельного алгоритма Прима. Проведите вычислительные эксперименты. Постройте теоретические оценки с учетом параметров используемой вычислительной системы. Сравните полученные оценки с экспериментальными данными. Разработайте программную реализацию алгоритма Кернигана – Лина. Дайте оценку возможности распараллеливания этого алгоритма.

46 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

47 Литература

Литература

Гергель В.П. (2007). Теория и практика параллельных вычислений. – М.: Интернет-Университет, БИНОМ. Лаборатория знаний. Cormen, T.H., Leiserson, C. E. , Rivest, R. L. , Stein C. (2001). Introduction to Algorithms, 2nd Edition. - The MIT Press. (русский перевод Кормен Т., Лейзерсон Ч., Ривест Р. (1999). Алгоритмы: построение и анализ. – М.: МЦНТО.) Schloegel, K., Karypis, G., Kumar, V. (2000). Graph Partitioning for High Performance Scientific Simulations.

47 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

48 Следующая тема

Следующая тема

Параллельные методы решения дифференциальных уравнений в частных производных

48 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

49 Авторский коллектив

Авторский коллектив

Гергель В.П., профессор, д.т.н., руководитель Гришагин В.А., доцент, к.ф.м.н. Сысоев А.В., ассистент (раздел 1) Лабутин Д.Ю., ассистент (система ПараЛаб) Абросимова О.Н., ассистент (раздел 10) Гергель А.В., аспирант (раздел 12) Лабутина А.А., магистр (разделы 7,8,9, система ПараЛаб) Сенин А.В. (раздел 11)

49 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

50 О проекте

О проекте

Целью проекта является создание образовательного комплекса "Многопроцессорные вычислительные системы и параллельное программирование", обеспечивающий рассмотрение вопросов параллельных вычислений, предусматриваемых рекомендациями Computing Curricula 2001 Международных организаций IEEE-CS и ACM. Данный образовательный комплекс может быть использован для обучения на начальном этапе подготовки специалистов в области информатики, вычислительной техники и информационных технологий. Образовательный комплекс включает учебный курс "Введение в методы параллельного программирования" и лабораторный практикум "Методы и технологии разработки параллельных программ", что позволяет органично сочетать фундаментальное образование в области программирования и практическое обучение методам разработки масштабного программного обеспечения для решения сложных вычислительно-трудоемких задач на высокопроизводительных вычислительных системах. Проект выполнялся в Нижегородском государственном университете им. Н.И. Лобачевского на кафедре математического обеспечения ЭВМ факультета вычислительной математики и кибернетики (http://www.software.unn.ac.ru). Выполнение проекта осуществлялось при поддержке компании Microsoft.

50 из 49

Н.Новгород, 2005 г.

Основы параллельных вычислений: Алгоритмы на графах © Гергель В.П.

«Образовательный комплекс Введение в методы параллельного программирования»
http://900igr.net/prezentacija/geometrija/obrazovatelnyj-kompleks-vvedenie-v-metody-parallelnogo-programmirovanija-223624.html
cсылка на страницу
Урок

Геометрия

40 тем
Слайды
900igr.net > Презентации по геометрии > Без темы > Образовательный комплекс Введение в методы параллельного программирования