Лабораторная работа 2 (Поиск минимального оставного дерева (Машеров))

Посмотреть архив целиком

Национальный исследовательский институт

Московский Энергетический Институт (Технический Университет)

Институт автоматики и вычислительной техники

Кафедра Прикладной математики









Лабораторная работа №2

по дисциплине «Параллельные системы и параллельное программирование»

тема: «Поиск минимального оставного дерева.»



Выполнил:

Машеров Д.Е.



Проверил:

Панков Н.А.













Москва

2012 г.

Постановка задачи

Дана граф, требуется найти минимальное оставное дерева этого графа.

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

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

Используется алгоритм Прима.

Алгоритм начинает работу с произвольной вершины графа, выбираемой в качестве корня дерева, и в ходе последовательно выполняемых итераций расширяет конструируемое дерево до МОД. Пусть есть множество вершин, уже включенных алгоритмом в МОД, а величины , 1<= <=n, характеризуют дуги минимальной длины от вершин, еще не включенных в дерево, до множества , т.е.

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

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

  • определяются значения величин di для всех вершин, еще не включенных в состав МОД;

  • выбирается вершина t графа G, имеющая дугу минимального веса до множества ;

  • вершина t включается в VT.

После выполнения n-1 итерации метода МОД будет сформировано. Вес этого дерева может быть получен при помощи выражения

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

Итерации метода должны выполняться последовательно и, тем самым, не могут быть распараллелены. С другой стороны, выполняемые на каждой итерации алгоритма действия являются независимыми и могут реализовываться одновременно.

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

  • набор вершин

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

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

,есть s-ый стольбец матрицы А

  • общую часть набора Vj и формируемого в процессе вычислений множества вершин .



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

  1. Количество вершин графа: 1 000

Число исполнителей

Время решения

Ускорение

1

5,547534


2

2,791276

1,91

3

1,88332

2,98

4

1,433112

4,02

8

0,774494

8,03

12

0,556577

11,28

16

0,418985

13,79

20

0,367053

15,22

24

0,326834

16,40

28

0,299249

17,41

32

0,266754

18,56

36

0,277727

11,41

40

0,346345

14,27

44

0,323366

12,07

48

0,296411

13,43

52

0,295205

11,27

56

0,31282

8,62

60

0,285301

7,52

64

0,242074

17,69





  1. Количество вершин графа: 5 000

Число исполнителей

Время решения

Ускорение

1

902,03109


2

342,68127

2,63

3

232,899105

3,93

4

175,10955

5,14

8

90,308224

10,24

12

47,578303

15,07

16

39,038579

19,43

20

32,30373

23,46

24

27,843325

27,85

28

25,298673

31,91

32

22,473695

36,01

36

20,695048

39,49

40

18,728376

43,14

44

17,164971

46,54

48

16,130638

49,27

52

15,016155

51,99

56

13,954162

55,59

60

13,285935

57,88

64

10,253616

61,45





  1. Количество вершин графа: 10 000

Число исполнителей

Время решения

2

2774,1043

3

1882,915374

4

1416,6679

8

713,6579

12

482,27567

16

368,15783

20

294,24421

24

250,46335

28

214,14437

32

188,42947

36

171,45674

40

152,31577

44

140,24903

48

129,80971

52

120,93132

56

112,64522

60

105,99757

64

100,04801



  1. Количество вершин графа: 20 000

Число исполнителей

Время решения

8

5698,3759

12

3838,5841

16

2909,7297

20

2333,4545

24

1962,7721

28

1698,1574

32

1486,6888

36

1347,5227

40

1206,1265

44

1101,3858

48

1021,4873

52

942,69882

56

888,52427

60

829,63986

64

771,18603





  1. Количество вершин графа: 30 000

Число исполнителей

Время решения

24

6444,4012

28

5578,5286

32

4897,1726

36

4381,5045

40

3946,59

44

3647,9182

48

3344,2485

52

3089,6803

56

2862,2789

60

2680,8999

64

2549,2176




Случайные файлы

Файл
18600-1.rtf
106714.rtf
184082.doc
175992.rtf
37843.doc




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.