Semestrální projekt PAR 2004/2005
Paralelní algoritmus pro řešení problému
Jaroslav
Šupolík
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
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
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.
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 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