Skojarzenia doskonałe

W drodze ku przepływom

Autorzy: Maciej

Chróśniak

Jakub

Dworniczak

Karol Ziarko

Projekt wykonywany w ramach
przedmiotu

Programowanie równoległe 420 na
UAM

Prowadzący zajęcia: dr Marcin
Paprzycki

Cel projektu

Implementacja probabilistycznego algorytmu
równoległego znajdowania skojarzeń doskonałych w
grafach.

Pierwotnie – wykorzystanie algorytmu dla grafów
dwudzielnych jako etap pośredni w rozwiązaniu
problemu maksymalnego przepływu.

Zastosowanie algorytmu

Równoległy algorytm znajdowania skojarzenia
doskonałego znajduje zastosowanie w wielu
problemach:

• maksymalnego przepływu

• największego skojarzenia

• skojarzenia o maksymalnej wadze

Schemat algorytmu

1) Losowy dobór liczb w

i

z zakresu [1,...,2*|E|] dla każdej

krawędzi e

i

(zastosowanie biblioteki GMP (GNU Multiple

Precision) operującej na liczbach o dużych rozmiarach)

2) Utworzenie zmodyfikowanej macierzy przyległości A z

przypisanymi wagami 2

wi

3) Wyliczenie det(A) oraz macierzy dopełnień algebraicznych

D

4) Analiza otrzymanych wartości w celu odnalezienia

krawędzi tworzących skojarzenie doskonałe

Znalezienie skojarzenia doskonałego w grafie G=(V,E)

Modyfikacja algorytmu

Istnieje wiele teoretycznych rozważań na temat
przytoczonego algorytmu (klasy RNC, Monte Carlo) –
rozwiązującego podany problem w polilogarytmicznym
czasie (O(log

2

n)) przy wykorzystaniu wielomianowej

liczby procesorów.

Najbardziej pracochłonną częścią procedury jest
obliczanie wyznaczników dla A i macierzy dopełnień
algebraicznych D (n

2

wyznaczników macierzy o

rozmiarach (n-1)x(n-1)).

Proponowane rozwiązania są czasochłonne.

Dlatego też postanowiliśmy zmodyfikować algorytm.

Modyfikacja algorytmu

Obliczenie wyznacznika i macierzy dopełnień
algebraicznych wykonywane jest za pomocą eliminacji
Gaussa (O(n

3

))

• proste wyliczenie det(A) po dekompozycji macierzy
• wyznaczenie macierzy odwrotnej A

-1

w celu utworzenia

D

D =det(A)* (A

-1

)

T

Problem: eliminacja wykorzystuje operację dzielenia i
wylicza przybliżone wartości

Rozwiązanie: wykorzystanie biblioteki pozwalającej
działać na liczbach wymiernych - uzyskanie dokładnych
wyników

Techniczne aspekty
implementacji równoległej

Wykorzystanie wątków POSIX-owych.

Rozwiązanie narzucone przez wykorzystanie wspomnianej
biblioteki GMP (liczby o dużych rozmiarach).

Zalety:

• wspólna pamięć – wszystkie wątki mają dostęp
wspólnego obszaru danych (brak konieczności ich
wymiany)

• uniknięcie kosztownej komunikacji (występującej przy
zastosowaniu procesów)

Techniczne aspekty
implementacji równoległej

Wady:

• konieczność organizacji dostępu do wspólnych danych,
utrudniona synchronizacja (np. za pomocą
mutex-ów) zwłaszcza przy dynamicznym przydziale prac

• trudność w pomiarze czasu (wykorzystanie czasu
dziennego) zwłaszcza dla obciążonej maszyny
obliczeniowej

• ograniczenie implementacji do architektury z pamięcią wspólną

Analiza wyników
(czas)

Implementacja algorytmu dla grafów dwudzielnych
Wykorzystanie grafów rzadkich – ze względu na
czasochłonność

Czas dla różnych rozmiarów grafów

liczba

wierzchołków

0

5

10

15

20

25

30

1

2

3

4

5

6

7

8

9

10

11

12

liczba procesorów

min.

80
120
160

Analiza wyników
(przyspieszenie)

Aby uwidocznić korzyści zrównoleglenia algorytmu badamy
przyspieszenie S(p)=T

1

/ T

p

T

1

- czas wykonania na 1 procesorze

T

p

- czas wykonania na p procesorach

Przyspieszenie dla różnych rozmiarów grafów

5,6

liczba

wierzchołków

1

2

3

4

5

6

1

2

3

4

5

6

7

8

9

10

11

12

liczba procesorów

S(p)

80
120
160
S(p)=p

Analiza wyników
(wykorzystanie pamięci)

Pomiar używanej pamięci obrazuje wzrost rozmiaru
liczb
w czasie dokonywania obliczeń

0

10

20

30

40

50

MB

80 (156)

120 (241)

160 (303)

liczba wierzchołków (liczba krawędzi)

Wykorzystanie pamięci

min
max

Analiza wyników
Liczby

Jest to liczba wymierna. Tylko jej część!

....................674602546050935116431143246410575830063931872876890411797621054435231064696663350721484558921712911230290767049
8208428327691843415164930434334722312428903360217527217709719335080471719322638243288262240038428246811206125795336577693
4685606051548454913702993009065903583909741771087035317822276808033657667204591590802510388800398518034834242552219752265
1682925204289128803672957894331233461597695150988112883357437865390858215631535113417490008214267612554161505679325697588
5979797099051541593245357691468370192157251880439818403580892067494788095447211581764474140914764612639477218335588057104
2037022765793621971952980338700996877931865558572995532640563123297868247848808910608218762136984580138549080105102175203
5022861409987726036689901496567068822961641696794478430596721748965154767711224718351404778326782611447240027932113249695
8263551385075427574870216258713666529067604379785275768543090275081068058839411107613409022304699861876948572282844600054
1541849111340345153205491428623811805856367903759885394483414471218406827015168542560350997957908973802132862690580584015
7138313481930458955148578485772933110447632047372678091478006627518561545863107956572670217997083414712860090350079277729
3052233643956743492686615577062498514469607698065852390537794660467280786656656656762838790671223903431435852780492013083
9822450234504218463618088628534054959263777405468012823206630904757195819935632396499735765486538727294864381378047260664
3325356575073235342230658884712956968511623069128520112632840389688202582172899600407152412414637169373929958249622943196
5764946284217020572243157695071482293217308785881568522102619930657820316535505476621576137540706366363673767946358556969
5536061746551235235419113760135702849253415831547726509834477193281996759006903054098304607405261067943154950396002689228
4869103532513069459277337071411450391345802385059713877283588536071356596644815348328714893944335149771336331469898876160
626388253768826790436346013076181628245021257

/

3921991716748007706015782321286393715338155312351046529968924269828282974222

9302169708146406017845386001355530220892904954465113728131761062812940882577776270704859265696065170916616057448315059674
1166652356181428832978352118479589138710974790208032890315431482954818668636746497070855656214826456969423026809663857751
4032636038068904248935878452360555776082286016320385774494459570107253505285498506235482461531969239796949868757806630548
9547977343367957228864575531278870643791358916885921180365900565416108925675456560995056432112901767390249812769549817413
1460914444932759228768398286448583155306968717530970949804969362222223412209207472634967740539152788547199065411901419061
1684543998257125578128340454985081695626007755175259520978910150203612961776703218765416290063381151896313693781921700126
8920421488946454045099841806696866447346995280500713837549052168081272426661793688174982310661974992567663167102077001927
3559948317931518000508201301697530772990160787702271549468581565707636793791697717595573057934171861326071236762544728957
5330794139826105411589934435328956509152970521759934969561185739175489173196280863905962711619446021946833692370043532999
6923980648253218450800593597567052035368802625346407856881556714049212630126605888692615746659752087098599675307700488709
0665919889951531522062896329905703096190493339626485537969420120419578269577807544131626663145163975183746694652553511318
9522915848575049186120499937481646853730829665454867355635274051979393981149671435956955471380115178493944763954409641540
6391509193557441284926826502118033682538121920273045948719888683619559747546493353872105644221532749063562260045750809894
6416770228766160022349836597278322190381634208813452578126931637642701471415556659167726978589388487105039174106452216733
8345575650345661531636050612486369627744598017919386954765801370760470123791723973756012732229567205723772563723206876987
3445946890971316834629091177831207566443404577957570843526184602444352505104183064789955887188606502092398407188229573407
3543603467322498118854659242474405141614953708930907786921828311768770698329355798361544294600851207134794567146428733975
5931587108914101113035355273032600753920445927693566916864185520237163530293741890765509694569371947288549903430328003339
5454253694125682309550235363068466382090282504519863830423675294489202933920952684216377032822050505014404462741828984858
5778467164122320575432291569634880253102877638163088885417879670938177587785321525753455370001091599456103418496041007748
2742374687033688520909912006074314126115427217468463678080228104633715767156745843820292687767955083084020639429368254624
0855172294066317558162569335481713127993059417567036289264930168797456110265603887772986248557976717139463994367153915739
1662226114023265545928952298382313403203573456814056628876316795918569164794970515735351230209500694153002786859983999933
0893136431245208066405480913135673703050163259473697671447828067352183172806394454072413321021530090304507330214335429539
681848451677982283311301479....................

Czas na prawdę

Algorytm równoległy kontra sekwencyjny - metoda
węgierska (O(n

3

))

0,05s

0,26s

0,91s

0

5

10

15

20

25

30

min.

80

120

160

liczba wierzchołków (graf dwudzielny)

Porównanie czasu

równoległy (1 proc.)
równoległy (min)
sekwencyjny

Analiza wyników
Operacje na liczbach

Porównanie czasu dla operacji dokonywanych na
liczbach wymiernych oraz zmiennoprzecinkowych
(long double - 8B) pokazuje skalę zróżnicowania.
Czas dla 10 000 operacji najczęściej występujących w
algorytmie – dzielenia i odejmowania (w sek.):

• 0,014 - liczby
zmiennoprzecinkowe

• 183,4 - liczby wymierne

Próba wykorzystania algorytmu dla
znajdowania maksymalnych przepływów

Algorytm ten może być etapem pośrednim w celu
rozwiązania problemu znajdowania maksymalnych
przepływów.
Możliwości zastosowania:

• prawdopodobieństwo, że algorytm odnajdzie
skojarzenie doskonałe jest większe niż 1/2
(gdy brak skojarzenia procedura zawsze da odpowiedź
prawdziwą)

• przejście do problemu odnajdywania przepływów
wymaga wykonania log

2

|V| czasochłonnych operacji

znajdowania skojarzenia i gwarantuje, że
prawdopodobieństwo poprawności działania całej
procedury jest większe niż 1/|V|.

Algorytm dla dowolnych
grafów

Algorytm również można wykorzystać dla grafów
dowolnych.
Wymaga to przekształcenia danych (macierzy
przyległości) prostego w realizacji, lecz modyfikacja ta
wpływa na efektywność.

Czas (80 wierzchołków)

0

1

2

3

4

5

6

7

1

2

3

4

5

6

7

8

9

10

11

12

liczba procesorów

min.

dowolny
(156 krawędzi)

dwudzielny
(158 krawędzi)

Próba zwiększenia
„prawdomówności”

Na prawdopodobieństwo P wygenerowania poprawnego
wyniku ma wpływ wielkość wykorzystywanych wag dla
krawędzi.
Krawędzi e

i

przypisujemy wagę 2

wi

, gdzie w

i

to losowa

liczba z zakresu [1,...,C*|E|].

P można zwiększyć poprzez:

• zwiększenie wartości C

• kilkakrotne wykonanie procedury

Próba zwiększenia
„prawdomówności”
(analiza czasu i wykorzystania
pamięci)

Badania wykonywane dla grafu dwudzielnego
posiadającego 80 wierzchołków

0

3

6

9

12

15

MB

8

4

2

1

C

Wykorzystanie pamięci

min
max

Metoda zwiększenia prawdopodobieństwa: P7/8

• zwiększenie C: C=8

• 3-krotne wywołanie procedury (dla C=2)
Druga metoda działa krócej.

6,82

P>=7/8

0,88

P>=1/2

0

1

2

3

4

5

6

7

min.

8

4

2

1

C

Czas

Próba zwiększenia
„prawdomówności”
Optymistyczny akcent

Testy prawdopodobieństwa (100 prób) dają wyniki
znacznie lepsze niż oszacowanie (P1/2 dla C=2).

C

P

2

0,98

1/4

0,81

1/16

0,51