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]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.