Проект по Системи за Паралелна Обработка Паралелен Алгоритъм за



Дата09.01.2017
Размер63.48 Kb.
#12341
Проект

по Системи за Паралелна Обработка


Паралелен Алгоритъм за

Обхождане на граф в дълбочина


Изготвил:

Румшна Колева, Фн:61342, СИ, 4 група, 3 курс

Ръководител:

ас. Христо Христов

Проверил: ........................

(ас. Христо Христов)

Дата:25.06.2012г.
Съдържание:


  1. Условие на проекта..................................................3

  2. Общо описание на представения алгоритъм.........4

  3. Тестови измервания и анализ на метричните показатели………......................................................5

1.Условие на проекта

(Граф – обхождане в дълбочина)

Разглеждаме графа G(V,E). Графа може да бъде ориентиран или неориентиран, свързан или слабо свързан. За представянето на графа ще използваме матрица на съседство. Да се напише програма, която реализира обхождане на графа G в дълбочина. Обхождането не извършваме спрямо определен връх. Като начална стъпка на обхождането имаме всички върхове на графа. По този начин реализираме покриващо дърво (ако графа е свързан) или гора (ако графа не е). Работата на алгоритъма да се раздели по подходящ начин на две или повече нишки (задачи). Изискванията към програмата са следните:

(o) Чете размерността на графа (броя на върховете му) от подходящо избран команден параметър – например “-n 10240”; Ребрата на графа генерираме произволно с помощта на Math.random() или класа java.util.Random;

(о) Втори команден параметър задава максималния брой нишки (задачи) на които разделяме работата по обхождането на графа – например “–t 1” или “–tasks 3”; (о) Извежда подходящи съобщения на различните етапи от работата си, както и времето отделено за обхождането;

(o) Да се осигури възможност за „quiet “ режим на работа на програмата, при който се извежда само времето отделено за обхождане на графа, отново чрез подходящо избран друг команден параметър – например “-q”;
ЗАБЕЛЕЖКА: (о) При желание за направата на подходящ графичен потребителски интерфейс (GUI) с помощта на класовете от пакета javax.swing задачата може да се изпълни от двама души;
NOTE(s): (о) В условието на задачата се говори за разделянето на работата на две или повече нишки. Работата върху съответната задача на една нишка ще служи за еталон, по който да измерваме евентуално ускорение. Тоест в кода реализиращ решенията на задачите трябва да се предвиди и тази възможност – задачата да бъде решавана от единствена нишка (процес); Пускайки програмата да работи върху задачата с помощта на единствена нишка, ще считаме че използваме серийното решение на задачата; Измервайки времето за работа на програмата при работа с „p“ нишки - Tp, изчисляваме Sp. Представените на защитата данни за работата на програмата, трябва да отразят и ефективността от работата и, тоест да се

изчисли и покаже Ep.

(о) Командните аргументи (параметри) на терминална (конзолна) Java програма,

получаваме във масива String args[] на main() метода, на стартовия клас. За „разбирането“ им (анализирането им) може да ползвате и външни библиотеки писани специално за тази цел . Един добър пример за това е: Apache Commons CLI (http://commons.apache.org/cli/).

2.Общо описание на представения алгоритъм

Приложението за обхождане на граф в дълбочина е осъществено, посредством употребата на езика за програмиране JAVA (Java SE-1.7 ) и срествата, които той предоставя за многонишково програмиране( multithreaded programming). За целта представеният алгоритъм е реализиран чрез два отделни класа – Test.java и Worker.java.

Основната идея, която следва самото алгоритмично решение е реализирано посредством класа Worker.java. Тя е свързана с това приложението да се създаде матрица на съседство, която да реализира произволен граф,който да бъде обходен многонишково. В класа Worker.java имаме четири метода: Worker – конструктор, в който инициализирам нашата нишка; Run – методът за задвижване на нашите нишки. Обхождаме нашия произволен граф реализиран с класа java.util.Random, където с while цикъл проверяваме дали има необходен връх и ако имаме такъв, то го обхождаме, като ги изпринтираме съответно за всяка от нишките, която ги е обходила; dfs – съдържа алгоритъма за обхождане в дълбочина. За реализацията му използваме стек. Създаваме стек, в който обхождaме всички върхове с цикъл for и оператор if. allVisited е методът, който проверява дали всички върхове са обходени. Както и името на класа Test.java подсказва, че тoй е главен, и че съдържа в себе си метода public static void main(String[] args). Той хвърля exception, принтира необходимото съобщени за некоректно въведени данни. В него създаваме нашите нишки, като отчитаме времето, за което те обхождат графа и го принтираме на екрана. В класа Test.java имаме още два метода: generateAdjacencyMatrix() – създаването на произволна матрица на съседство чрез класа java.util.Random; parseArguments(String[] args) – метода, с който въвеждаме аргументите –n за броя върхове на графа и –t за брой нишки, който да го обходят и осигуряваме „quiet” режима -q. Алгоритъмът работи за произволен граф, което ще рече, че го обхожда в дълбочина независимо от това дали той е обикновено дърво, дали е ориентиран или неориентиран граф, или пък е свързан или не. За да няма застъпване на нишките и да обхождат едни и същи върхове ако едната обходи нейните върхове и има необходени такива, то другата ги обхожда.Целта е да се постигни по-добро ускорение.


  1. Тестови замервания и анализ на метричните показатели

Разработено е приложение на JAVA и е тествано на 12 ядрен мултипроцесор с цел да се оценят ускорението S (забързване, speed-up) и ефективността Е (efficiency) на описания алгоритъм, където ако T(p) е времето необходимо за завършване на работата на алгоритъм с p на брой нишки то:


S(p) = T(1)/T(p)

E(p) = S(p)/p


Замерванията са направени за произволен граф с 10000 върха.


Граф - обхождане в дълбочина



Брой върхове (-n)

Брой нишки (-t)

Изчислено време T(p) [ms]

Изчислено ускорение S(p)

Изчислена ефективност E(p)

1

10 000

1

955

 

 

2

10 000

2

500

1.91

0.96

3

10 000

3

355

2.69

0.90

4

10 000

4

285

3.35

0.84

5

10 000

5

248

3.85

0.77

6

10 000

6

214

4.46

0.74

7

10 000

7

197

4.85

0.69

8

10 000

8

155

6.16

0.77

9

10 000

9

191

5.00

0.56

10

10 000

10

157

6.08

0.61

11

10 000

11

139

6.87

0.62

12

10 000

12

165

5.79

0.48










Каталог: docs -> example.projects -> not.so.bad
docs -> Опит в група чрез психодрама, социометрия и групова терапия
docs -> Дв бр. 103 от 2 Декември 2008г., изм дв бр. 24 от 31 Март 2009г
docs -> Фондация «Гъривер клиринг хауз» (c/o Център за култура и дебат „Червената къща”)
docs -> Иван (Ванчо) Флоров и м а г и н е р н о с т а
docs -> Соу „СВ. Св. Кирил и методий
docs -> Рискови фактори на тютюнопушенето
not.so.bad -> Проект по Системи за Паралелна Обработка Паралелен Алгоритъм за пресмятане на Детерминанта на матрица


Сподели с приятели:




©obuch.info 2024
отнасят до администрацията

    Начална страница