8.1.2001
Semestrální projekt PAR 00/01
Paralelní
algoritmus pro řešení problému:
TRS1
– trojúhelníkový kolíčkový solitér
Josef Beran
Martin Čadík
Definice problému a popis sekvenčního algoritmu
Vstupní data:
p = počet procesorů
n = délka strany rovnostranného trojúhelníka, n>=5
Z = přirozené číslo, 1<= Z <= M, kde M=n(n-1)/2
Pravidla a cil hry: herní deska je trojúhelníková o n
řádcích, v i-tém řádku je i políček. Políčka jsou číslována po řádcích
shora dolu od 0 do M-1. Jeden tah je přeskok kolíčku, za kterým
je volno v 1 ze 3 směrů rovnoběžných se stranou trojúhelníka a odstranění přeskočeného
kolíčku.
Pocatecni stav X0: vsechny pozice
jsou obsazeny kolíčky, kromě Z-tého políčka, viz obrázek
Cil hry: přeskočením odstranit všechny kolíčky
až na poslední.
Každé políčko x, 0<=x<=M-1, na herní desce má 2<=s(x)<=6 sousedních políček. Nechť m je počet kolíčků na herní desce a X[1..m] stav popsaný jako množina pozic obsazených kolíčky. Pak k(X[i]) je počet obsazených sousedních políček kolem X[i]. Izolovaný kolíček X[i] má k(X[i])=0.
Heuristická funkce: kompaktnost stavu X na
herní desce budeme kvantifikovat funkcí
m m
C(X) = (SUMA k(X[i])) / (SUMA s(X[i]))
i=1 i=1
Koncový stav X, který se skládá pouze z izolovaných
kolíčků, má tedy C(X)=0.
Sekvencni algoritmus je typu BB-DFS
s omezenou hloubkou prohledávání M-2. Cena řešení, kterou
minimalizujeme, je počet izolovaných kolíčků koncového stavu. Protože není známo,
zda pro každé n a Z existuje řešení s 1 zbylým kolíčkem, prohledávání
stavového prostoru je úplné v závislosti na vstupních datech. Buď existuje řešení
s 1 kolíčkem nebo se prohledá celý stavový prostor.
Zásobník je realizován spojovým seznamem záznamů typu STAV, který má následující strukturu:
typedef struct STAV
{
int HraciPole[MAX_POLI];
int Tahy [2*MAX_POLI-1];
float Cena;
STAV *Next;
}STAV;
Každý stav na zásobníku tedy obsahuje aktuální obsazení hracího pole (HraciPole), posloupnost tahů vedoucí k tomuto stavu (Tahy), cenu stavu (Cena) a odkaz na další stav zásobníku (*Next).
Parametry programu: první parametr je povinný a udává
jméno načítaného vstupního souboru s instancí problému. Velikost instance
je dána strukturou souboru. Druhý parametr udává počet spouštěných potomků.
Tento parametr je nepovinný a v případě jeho absence je použita implicitní
hodnota p=5.
Vstupní soubor je jednoduchý textový soubor, který obsahuje na začátku přirozené číslo n, které udává délku strany rovnostranného trojúhelníka (rozměr herní desky), za kterým následuje k=n*(n+1)/2 nul resp. jedniček oddělených od sebe mezerami, jenž udávají prázdné resp. obsazené herní políčko.Načtení dat zajišťuje funkce nactiZadani.
Výstup programu je formou výpisu na obrazovku, je „graficky“ zobrazen dosažený výsledek, jeho cena i posloupnost tahů, které do cílového stavu (řešení nebo stavu s minimálním počtem zbylých kolíčků) vedou z počátečního stavu.
Výpočet: při výpočtu se udržuje doposud nejlepší dosažené řešení v proměnné nejlepsiStav, k výpočtu ceny stavu slouží funkce cenaStavu, která vrací „cenu stavu“ vypočtenou pomocí výše uvedené heuristické funkce. Vlastní BB-DFS prohledávání zajišťuje metoda trs, která v cyklu dokud není prázdný zásobník expanduje vždy stav na vrcholu (struktura stavu viz výše), vygeneruje jeho následníky, ohodnotí je a výsledek umístí zpět na vrchol zásobníku.
Popis paralelního algoritmu a jeho implementace v PVM3
Paralelní algoritmus je typu L-PBB-DFS-D, hledání dárce je algoritmem ACZ-AHD, dělení zásobníku pomocí R-ADZ.
Struktura programu: Aplikace je zkompilována ze čtyř zdrojových souborů – dvou hlavičkových souborů trs.h, trsproc.h, souboru s výpočetními funkcemi trsproc.cpp a souboru s komunikačními fukncemi a hlavní smyčkou programu trs.cpp.
Paralelní řešení si vyžádalo přidání proměnné Level do struktury zásobníku, která udává hloubku daného stavu v zásobníku, neboli počet tahů od daného stavu k počátečnímu stavu.
Většina funkcí modulu trsproc je obdobných sekvenčnímu řešení, změny zaznamenala výpočetní funkce, která byla nahrazena funkcí trsKrok, která umožňuje provádět výpočet po krocích.
Vytvoření potomků: existuje pouze jeden spustitelný soubor – jak pro mastera tak pro jeho potomky. Master nejprve provede potřebnou inicializaci a načte instanci problému ze souboru zadaného na příkazové řádce. Poté vytvoří p potomků, které spustí s prvním parametrem slave pro odlišení od úvodního spuštění programu a rozešle jim tid ostatních procesů, čímž vlastně realizuje přímou propojovací síť paralelního počítače. Následuje hlavní smyčka programu, která je shodná pro procesy potomků i mastera.
Hlavní smyčka programu: na počátku mají potomci prázdný zásobník a začnou tedy pomocí ahd okamžitě žádat o práci. Žádosti zprvu může uspokojit pouze jediný proces – „bývalý master“, který má na vrcholu zásobníku počáteční stav načtený ze vstupního souboru, a proto provádí výpočet. Prakticky je smyčka implementována následovně (zjednodušeno):
while(!COMMAND_EXIT){
OBSLUZ CEKAJICI ZPRAVY,
EXISTUJI-LI
{
case
POZADAVEK:
if(!AKTIVNI)
posli(ODMITNUTI);
else
{
if(PORADI>poradi(sender))
barvaProcesu=BLACK;
rozdelZasobnik;
posliStavy;
}
break;
case
ODMITNUTI:
stavProcesu=NECINNY;
break;
case
PRACE:
stavProcesu=AKTIVNI;
break;
case
PESEK_B:
case
PESEK_W:
//UPDATE NEJLEPSIHO STAVU
if((PORADI==0)&&(PESEK_W))
konecVypoctuOptimum();
if(barvaProcesu==BLACK)
barvaPeska=PESEK_B;
break;
}//prijal jsem zpravu
//PROVED URCITE MNOZSTVI
PRACE
if(AKTIVNI){
case
ZASOBNIK_NE_PRAZDNY:
//zustaneme
aktivni
break;
case
ZASOBNIK_PRAZDNY:
stavProcesu=NECINNY;
break;
case
OPTIMALNI_RESENI:
konecVypoctuOptimum();
break;
}//aktivni
//VYBER DARCE A POZADEJ HO
O PRACI
if(NECINNY){
if(mamPeska)
barvaProcesu=WHITE;
if(PORADI==0) posliPeska(1,PESEK_W);
else
posliPeska((PORADI+1)%(P+1),barvaPeska);
posli(ahd(),
POZADAVEK);
stavProcesu=WAITING;
}//necinny
}//while !COMMAND_EXIT
Algoritmus hledání dárce: jedná se o asynchronní
cyklické žádosti, prakticky je realizován funkcí ahd:
//ACZ-AHD
int ahd(){
static int D=((mtid+1)%(P+1));
D=++D%(P+1);
return(D);
}//ahd
Dělení zásobníku: Pro dělení zásobníku je použit algoritmus R-ADZ s možností nastavení řezné výšky. Algoritmus je realizován funkcí rozdelZasobnik, jejímž výstupem je počet stavů určených k poslání. Funkce nejprve v zásobníku nalezne počátek řezné hladiny, poté zjistí počet stavů nacházejících se v této hladině. Následně již jen ze seznamu vyjme stavy určené k poslání - polovina stavů nacházejících se v řezné hladině.
int rozdelZasobnik(STAV **stack,STAV **poslat, int
H) {
STAV
*POM_stack=*stack,*POM_poslt=*poslat;
int
i,ven,rezna_hladina=0,pocet=0;
STAV
*PS1=*stack;
STAV
*POCATEK;
if(PS1==NULL) return -1;
rezna_hladina=POM_stack->Level-H;
if(rezna_hladina<=0) return -1;
while((PS1->Next!=NULL)&&(ven!=1)&&(PS1->Level>=rezna_hladina))
{
if(PS1->Next->Level==rezna_hladina) ven=1;
else PS1=PS1->Next;
}
if(PS1==NULL) return -1;
POCATEK=PS1;
PS1=POCATEK->Next;
if(PS1==NULL) return -1;
while((PS1->Next!=NULL)&&(PS1->Level==rezna_hladina))
{
//spocita to pocet stavu v
rezne hladine
pocet++;
PS1=PS1->Next;
}
pocet=pocet/2;
if(pocet==0) { //je pouze jeden
stav v rezne hladine
*poslat=NULL;
return 0;
}
PS1=POCATEK;
for(i=0;i<=pocet;i++) PS1=PS1->Next;
if(PS1==NULL) return -1;
if(POCATEK==POM_stack) {
*stack=PS1->Next;
PS1->Next=NULL;
*poslat=POM_stack;
}else {
*poslat=POCATEK->Next;
POCATEK->Next=PS1->Next;
PS1->Next=NULL;
*stack=POM_stack;
}
return
pocet;
}
Škálovatelnost algoritmu: je zajištěna možností zvolit řeznou výšku zásobníku, viz naměřené výsledky a vyhodnocení.
Analýza složitosti paralelního řešení
Celkový počet políček na herní desce:
Sekvenční složitost algoritmu:
Analytický odhad paralelního času:
Analytický odhad paralelní ceny: 
Analytický odhad paralelního zrychlení:
Analytický odhad paralelní efektivnosti:
Nameřené výsledky
Závěr
Jak je vidět z přiloženého grafu zrychlení S(n,p), nedošlo v našem případě k superlineárnímu zrychlení, naše implementace nemá ani kýžené lineární zrychlení, nicméně se zvyšujícím se počtem procesorů se paralelní čas podle očekávání zmenšuje a paralelní zrychlení zvětšuje.
Experimenty s řeznou hladinou ukazují, že největšího paralelního zrychlení se dosahuje pro řeznou hladinu H=0, tzn. pro dělení zásobníku na vrcholu a posílání poloviny z počtu stavů v této hladině. Stejná je situace v případě reálného času, ale v případě požadavku minimalizace virtuálního času vychází lépe hodnota řezné hladiny H=5.