Semestrální projekt PAR 2004/2005

Paralelní algoritmus pro řešení problému

Jaroslav Šupolík
Jaroslav Nušl

5. ročník, obor počítače, K336 FEL CVUT, Karlovo nám.13, 121 35 Praha 2

10. ledna, 2005

 

 

1. Definice problému a popis sekvenčního algoritmu


Úloha SOP: součet podmnožiny

Vstupní data:

n = přirozené číslo představující mohutnost množiny S
S = množina n různých přirozených čísel (s1,..,sn)
c = přirozené číslo, c >= mini si

Úkol:

    Nalezení neprázdné podmnožiny T množiny S takové, že součet prvků podmnožiny T je největší možný a současně menší než c.

Vystup algoritmu:

     Konstatování, zda podmnožina T existuje. V případě pozitivní odpovědi výpis prvku podmnožiny T a jejího součtu.

Sekvenční algoritmus:

    Sekvenční algoritmus je typu BB-DFS s hloubkou prohledávaného prostoru omezenou na n. Přípustný koncový stav je situace, kdy máme neprázdnou podmnožinu T a součet jejích prvku je menší než c. Cena, kterou maximalizujeme, je součet prvků podmnožiny T. V koncovém stavu musíme aktualizovat cenu nejlepšího řešení, pokud je cena nalezeného řešení lepší než do té doby nejlepší známá cena. Algoritmus končí, když cena řešení koncového stavu je rovna c-1 , jinak algoritmus prohledává celý stavový prostor a na konci vypíše cenu do té doby nejlepšího řešení.

 

 

Implementace
 
    První sekvenční řešení jsme implementovali pomocí rekurze. Jelikož jsme si jako programovací jazyk zvolili C++, vytvořili jsme třídu reprezentující jedno možné řešení (CBag). Konkrétně se jedná o třídu obsahující dynamicky rostoucí pole čísel (int). Kromě dalších nezbytných údajů obsahuje také horní limit ceny pro jednoduché vyhodnocení kvality řešení. Pro jednoduché a přehledné využití této třídy jsou také velice vhodné přetížené operátory porovnání a přiřazení. Vstupní množinu jsme také realizovali jako třídu (CSet). Hlavní výkonný kód je obsažen v metodě find třídy CSOP. 
Rekurzivní řešení je realizováno následovně. Jako parametr metody je jedno možné řešení (na začátku výpočtu prázdné) a pořadové číslo prvku vstupní množiny. Funkce dvakrát volá sama sebe, jednou si předá řešení rozšířené o vstupní prvek a podruhé nerozšířené. Obě volání mají pořadové číslo vstupního prvku o jedna větší než volající funkce. Takto se algoritmus rekurzivně zanořuje dokud je možné přidávat další prvky nebo již nejsou další vstupní hodnoty. Řešení se porovná s nejlepším nalezeným a to se následně vrátí jako výsledek metody.
 
Zadaný problém vede na BB-DFS a stavový prostor se prohledává v závislosti na datech (DDE). Hloubka prohledávaného stavového prostoru je maximálně rovna velikosti vstupní množině dat.
 
POUŽITÍ:
 program uvažuje tyto parametry: 
               -n mohutnost vstupní množiny (kolik čísel se má načíst ze vstupního souboru)
               -c číslo větší než součet hledané podmnožiny
               -i jméno vstupního souboru
               -o jméno výstupního souboru
 
vstupní soubor je množina ascii integer čísel zapsaných každé na novém řádku
výstupní soubor obsahuje na každém řádku jeden prvek výsledné podmnožiny v ascii reprezentaci 

 

2. Popis paralelního algoritmu a jeho implementace v MPI


Paralelní algoritmus je typu G-PBB-DFS-D, hledání dárce algoritmem ACZ-AHD, dělení zásobníku pomoci D-ADZ.

 

    V zadání semestrální úlohy je doporučen algoritmus G-PBB-DFS-D. Tento algoritmu však nelze v tomto případě použít, neboť nikdy dopředu nevíme, ve kterém kroku nalezneme ideální řešení. Tedy informace o momentálně nejlepším řešení není pro výpočet nijak důležitá. Je tedy použit algoritmus L-PBB-DFS-D. Dělení zásobníku je dynamické. Princip rozdělení práce je jednoduchý. Proces který dostane žádost o práci, předá právě počítanou větev procesu, který o práci žádal a vrátí se ve stromu o úroveň výš. Zde začne pokračovat ve výpočtu stejným postupem, jako kdyby předcházející větev byla již vyřešena. Najde-li nějaký proces ideální řešení, ukončí se práce algoritmem ADUV.
3. Naměřené výsledky a jejich hodnocení

 

    Ethernet

 

CPU =  2

čas [s]

žádosti celkem

žádost na cpu

úspěšnost

m = 24

118,6

180

90,00

0,328

m = 25

237,2

357

178,50

0,331

m = 26

460,3

691

345,50

0,333

 

CPU =  3

čas [s]

žádostí celkem

žádost na cpu

úspěšnost

m = 24

184,9

520

173,33

0,281

m = 25

727,7

2112

704,00

0,313

m = 26

735,7

2127

709,00

0,309

 

CPU =  6

čas [s]

žádostí celkem

žádost na cpu

úspěšnost

m = 24

780

2573

428,83

0,314

m = 25

772

5075

845,83

0,241

m = 26

768,6

10302

1717,00

0,248

 

 

 

 

      Při výpočtu úlohy na více procesorech dochází naopak ke zpomalení. Je to zřejmě způsobeno velkými komunikačními náklady. Lze tedy s jistotou říci, že k super lineárnímu zrychlení nedochází.

 

Pzn.: Při řešení tohoto algoritmu vznikla i jiná varianta, kde strom byl v počátku rozdělen na určité množství symetrických podstromů a ty pak byly rozděleny pro jednotlivé procesory. Toto však nesplňovalo požadavky zadání, neboť komunikace byla na úrovni master – slave.

 


   Mirinet

 

prvků\CPU

2

3

6

24

116,3

223,6

694,5

25

242,8

560,3

736,2

26

457,1

651,2

757,1



 

 


   Efektivita algoritmu
:

      S každým zvýšením počtu čísel o 1 dostaneme problém o n větší. Sekvenční algoritmus má tedy složitost SU(n)=O(n!).

Při paralelním řešeni jsme se snažili problém rozdělit rovnoměrně mezi všechny procesy. Paralelní čas se tedy skládá z doby výpočtu Tv a komunikačních nakladu Tk. Komunikační náklady se stanovuji obtížně protože záleží na rovnoměrném rozdělení práce mezi procesory. Celkový vztah je tedy


a pro teoretickou práci a zrychlení

Uvedené vztahy předpokládají rovnoměrné rozdělení práce a platí pro ten nejhorší případ, tedy pro ten kdy neexistuje optimální řešení.

 

Příloha – Statistika posílaných zpráv

4. Literatura

[1] Tvrdík, P.: Slajdy na přednášky, 2004
[2] Tvrdík, P.: Paralelní systémy a algoritmy, 2003