Semestrální projekt PAR 2005/2006

Definice:

n

přirozené číslo představující počet uzlů grafu, n ≥ 5

k

přirozené číslo řádu jednotek představující maximální stupeň uzlů grafu

G

jednoduchý neorientovaný neohodnocený souvislý graf o n uzlech a stupni nejvýše k

Graf G(V,E) je bipartitní jestliže můžeme rozdělit množinu uzlů na disjunktní podmnožiny U a W tak, že každá hrana v G spojuje uzel z U s uzlem z W. Bipartitní graf je možné uzlově obarvit dvěma barvami.

Úkol:

Graf G(V,E) je definován množinou uzlů V a množinou hran E. Úkolem je nalézt maximální podmnožinu hran F takovou, ze graf G(V,F) je bipartitní (viz obrázek).

Vstupní data:

Program se spouští z příkazové řádky: bpg graph, kde soubor graph má následující strukturu:

Na prvním řádku je počet uzlů grafu. Na následujících řádcích je vypsána matice sousednosti, 1 znamená, že uzly i a j jsou spojeny hranou, 0 znamená, že nejsou. Čísla musí být oddělena právě jednou mezerou.

Výstupní data:

Program vypíše počet zachovaných hran, které hrany byly použity a které ne. Seznam byl tvořen z horní trojúhelníkové matice matice sousednosti. A matici sousednosti výsledného grafu.

Sekvenční algoritmus je typu BB-DFS (branch and bound deep first search) s hloubkou stavového stromu omezenou na |E|.

Algoritmus končí po prohledání všech přípustných stavů. Přípustný mezistav je podmnožina hran F, která tvoří bipartitní podgraf G(V,F). Cena, kterou maximalizujeme, je počet hran v F. Pokud je graf G bipartitní, pak triviálně F = E, jinak F je podmnožinou E. K problému lze přistoupit dvěma způsoby. Buď lze do prázdného grafu přidávat hrany tak, aby byl vznikající podgraf bipartitní (budování množiny F inkrementálně z prázdné množiny) nebo lze z množiny E postupně odebírat hrany, dokud nevznikne bipartitní graf (budování množiny F dekrementálně z množiny E). Pro tuto úlohu je výhodnější druhý způsob, který jsme v našem algoritmu použili, protože prohledávání se může navracet v mezistavech s |F|=|V|-1 (strom je triviálně bipartitní, proto musí existovat řešení s |F|=|V|-1). Jedná se tedy o úplné prohledávání stavového prostoru do hloubky |E|-|V|. Toto platí pouze pokud je graf souvislý. Je li graf nesouvislý je minimální počet hran výsledného bipartitního grafu |F|=|V|-1-k, kde k je počet komponent souvislosti.

Vždy když nalezneme přípustné řešení, zkontrolujeme, jestli je lepší než zatím dosud nalezené.

Paralelní řešení je rozšíření sekvenčního řešení o možnost spolupráce více procesů pomocí knihovny MPI. Paralelní algoritmus je typu G-PBB-DFS-V, hledaní dárce algoritmem ACZ-AHD, dělení zásobníku pomoci D-ADZ.

Obecný algoritmus

Na počátku procesor P₀ zná počet procesorů p, na kterých se úloha bude řešit. Provede dostatečný počet expanzí počátečního stavu, rozdělí svůj zásobník na p částí a rozešle jednotlivé části ostatním procesorům. Všechny procesory začnou prohledávat svůj přidělený podprostor a přitom realizuji programovou smyčku naznačenou na tomto obrázku.

Aktivní procesor, který vyčerpá svůj přidělený díl práce, se stane nečinný a pomoci algoritmu pro hledání dárce AHD vybere dárce a pošle mu žádost o práci. Pokud mu dárce práci pošle, přepne se zpět do stavu aktivní. Pokud se mu vrátí odmítnutí, vše se opakuje. Procesor ve stavu nečinný také periodicky kontroluje, zda nemá ve frontě žádosti o práci, na které odpovídá odmítnutím, zprávy o nalezení řešení jiným procesorem, nebo detekce ukončení.

Aktivní procesor provádí fixní objem práce nad lokálním zásobníkem (expanduje určitý daný počet stavů na lokálním zásobníku) a pak kontroluje frontu zpráv. V té mohou být žádosti o práci, informace o nalezení řešení jiným procesorem a žádosti o ukončení výpočtu apod.

Strategie průchodu a ukončení G-PBB-DFS-V

Je naším rozšířením PPB-DFS-V, prohledávání do hloubky s vždy úplným prohledáváním stavového prostoru. Všechny procesory se dozvědí hodnotu horní meze ceny řešení. Když najde procesor řešení lepší než je doposud známe, rozešle ostatním procesorům hodnoty nové horní meze ceny řešení. Po vyprázdnění všech zásobníků se provede distribuované ukončení výpočtu pomocí algoritmu ADUV. Procesor P₀ si vyžádá nejlepší řešení od procesoru, který ho našel.

Hledání dárce ACZ-AHD

Každý procesor si udržuje lokální čítač D, kde 0 <= D <= p-1, označující potenciálního dárce. Na začátku inicializované na náhodné číslo z intervalu 0 až p-1. Procesor s prázdným zásobníkem pošle žádost o práci procesoru P_D a inkrementuje čítač D mod p. Může se stát, že jeden a tentýž procesor obdrží několik žádostí o práci.

Dělení zásobníku D-ADZ

Dárce rozděluje stavy pouze na dně zásobníku.

Algoritmus pro distribuované ukončení výpočtu ADUV

Typ paralelního algoritmu PBB-DFS-V znamená, že výpočet končí až ve stavu, kdy mají všechny procesory prázdný lokální zásobník. K identifikaci stavu, že všem procesům došla práce se používá metoda ADUV.

Každý procesor může být obarven dvěma barvami: B nebo W. Na počátku mají procesory barvu W. Pro zjištění, zda může celý výpočet skončit, cirkuluje mezi procesory pešek (token), který může být také dvou barev, B a W. Algoritmus ukončení funguje takto:

• Jakmile se první procesor P₀ stane idle, nastaví svou barvu na W a pošle peška barvy W procesoru P₁
• Jestliže procesor P_i pošle práci procesoru P_j, kde i > j, pak P_i nastaví svou barvu na B
• Jestliže P_i obdrži peška, pak má-li P_i barvu B, nastaví barvu peška na B. Jakmile se P_i stane idle, pošle peška po kružnici procesoru P_i+1 a nastaví svoji barvu na W
• Pokud P₀ obdrži zpět peška barvy W, je možné výpočet ukončit. Pokud má pešek barvu B, P₀ zahájí nové kolo vysláním barvy W procesoru P₁
• Ukončení je detekováno, jakmile P₀ obdrží zpět peška v barvě W

Sekvenční algoritmus

V nejhorším možném případě prohledáváme celý stavový prostor. Každá hrana do výsleduku buď patří nebo nepatří a probíráme všechny takové možné kombinace, tedy 2^|E|. Každou kombinaci hran zkoumáme na bipartitu, která má složitost |V|². Nejhorší možná časová složitost je tedy

SU(|E|,|V|) = O(2^|E||V|²).

V nejlepším možném případě je již zadaný graf bipartitní a pokud zanedbáme čas potřebný pro načtení, inicializaci a podobně, vlastní algotimus má nejlepší možnou časovou složitost O(|V|²).

Paralelní algoritmus

Úlohu můžeme rozdělit rovnoměrně na p částí. Paralelní čas se tedy skládá z doby výpočtu T_v a komunikačních nakladu T_k. Komunikační náklady se stanovuji obtížně, protože záleží na rovnoměrném rozdělení práce mezi procesory. Výsledný vztah je tedy:

T(|E|,|V|,p) = T_v(|E|,|V|,p) + T_k(|E|,p) = O(2^|E||V|² / p) + T_k(|E|,p)

Pro teoretickou paralelní cenu, efektivnost a zrychlení vychází:

C(|E|,|V|,p) = p*T(|E|,|V|,p) = O(2^|E||V|²) + p*T_k(|E|,p)

E(|E|,|V|,p) = SU(|E|,|V|) / C(|E|,|V|,p) = O(2^|E||V|²) / (O(2^|E||V|²) + p*T_k(|E|,p))

S(|E|,|V|,p) = SU(|E|,|V|) / T(|E|,|V|,p) = |při zanedbání komunikační režie| = O(p)

Naměřené časy v sekundách

Počet procesorů	1	2	4	8	12	hran/uzlů
Ethernet	571	320	153	98	72	32/12
	374	359	125	44	37	30/11
	53.2	7.6	5.2	4.4	4.2	27/10
Myrinet	373	197	76	58	45	32/12
	233	193	66	26	20	30/11
	32	4.1	2.7	2.4	2.2	27/10

Naměřené zrychlení

Počet procesorů	1	2	4	8	12	hran/uzlů
Ethernet	1	1.8	3.7	5.8	7.9	32/12
	1	1	3	8.5	10.1	30/11
	1	7	10.2	12.1	12.7	27/10
Myrinet	1	1.9	4.9	6.4	8.3	32/12
	1	1.2	3.5	9	11.7	30/11
	1	7.8	11.9	13.3	14.5	27/10

Zhodnocení

U této úlohy velmi záleží na průběhu vyhledávání - jak dobrá řešení nalézáme a na následném ořezávání prohledáváného stavového prostoru. To je vidno i z grafu, kdy přiblíží-li se dostatečně nějaký procesor hledanému řešení brzo, celkový čas drasticky klesá. Naměřených vzorků je příliš málo, aby se dalo usoudit něco obecného o algoritmu jako celku, ale pokusíme se.

Pro třetí instanci problému došlo k superlineárnímu zrychlení z důvodů popsaných výše - problém byl rozdělen tak, že jeden z procesorů našel (nebo se přiblížil) řešení brzo po spuštění výpočtu natolik, že většina stavů nemusela být prohledávána.

Škálovatelnost algoritmu není příliš dobrá, jak plyne z grafu. S rostoucím počtem procesorů, efektivita klesá.

Velmi také záleží na vyladění poměru mezi dobou věnovanou pro komunikaci a pro dobu věnovanou vlastnímu hledání řešení.

Algoritmus pro dělení zásobníku se zdá být optimální. V našem provedení by šla vylepšit implementace.

Algoritmus hledání dárce příliš efektivní není. Šel by vylepšit například rozesláním dotazu na velikost zásobníku a vybrat dárce s největším zásobníkem.

• https://star.felk.cvut.cz/
• Prof. Ing. Pavel Tvrdík, CSc., Paralelní systémy and algoritmy, ČVUT, Praha 2005