Programozás | Programozás-elmélet » Pesti György - Asszociatív függvény eredményének kiszámítása

Asszociatív függvény eredményének kiszámítása 1. beadandó feladat Párhuzamos Programozás című tárgy Készítette: Pesti György Mail: pocixxx@inf.eltehu Budapest, 2002. november 29 Feladat: Határozzuk meg egy f: {1.N} N függvény (függvényértékeit vektor reprezentálja) „maximumát”. Egy olyan g: {1N} N függvény meghatározása a feladat, amelyre a következő tulajdonsággal bír: ∀i∈[1.N]-re igaz, hogy g(i) = max{f(1), ,f(i)} Ki kell számolni egy N hosszúságú vektor minden elemére az adott elemig vett részvektor maximumát. Formális specifikáció: G = vector ([1.N],N) A =G xG f g B=G f (f = f ’)∈ INITf’ ↑FP f’ FP f’ ⇒ (f’ és ∀i∈[1.N]: g(i) = f (<< f1,fi>>)) f megfelel a max függvénynek. Ez asszociatív, azaz teljesül a következő állítás: max(max(a,b),c) = max(a, max(b,c)) Megvalósítás: A fenti specifikáció megfelel az asszociatív függvény eredményének kiszámításáról

szóló tételnek. Ezáltal arra visszavezethető: s0 : i =[1.N] gs (i,0), t (i ), k (i ) := ai ,1,0 gs(i, k (i) + 1), t (i), k (i) := S :{ i =[1.N] max( gs(i, k (i)), gs(i − t (i), k (i))),2 ⋅ t (i), k (i) + 1 ha(i − 2 ⋅ t (i) ≥ 0)és( k (i − t (i) ≥ k (i ))   max( gs(i, k (i )), gs(i − t (i ), k (i − t (i )))),2 ⋅ t (i ), k (i ) + 1, ha(i − t (i ) ≥ 1)és(i − 2 ⋅ t (i ) < 0)és(k (i − t (i )) = log(i − t (i )) i =[1.N] } g (i ) := gs (i, k (i )), ha (k (i ) = log(i ) Implementáció: A program C nyelven készült, amely erősen támaszkodik a pvm könyvtár(ak)ra. A megvalósításban egy főfolyamat(assmax.c) és N darab gyermekfolyamat(assmaxtaskc) szerepel. A főfolyamat első feladata az adatok (N értéke és N darab egész szám) bekérése, amelyek a data nevű fájlban megadott állományban helyezkednek el. Ezután elindítja az N darab gyermekfolyamatot, átadva nekik a kezdőértékeket (i.

folyamat kapja az i számot) Majd megvárja a végeredményt, amit kiír az out nevű állományba. A program biztosítja, hogy minden gyermekfolyamat annak és csak annak a folyamatnak küld adatot, amelynek kell. Ezt a kettőhatványú távolság megválasztásával érhető el. Gyermekfolyamatok: Elküldi az aktuális értéket és ha vár valakitől értéket, akkor megvárja a további számoláshoz szükséges új értéket, majd számol. Ez lesz számára az új maximum, amit a folyamat, ha kell tovább fog küldeni. Ez egy olyan megoldást tükröz, amelyben a számok és a maximum tömb a fő folyamat változójaként jelenik meg. A gs mátrix i sorának éppen aktuális eleme az i folyamat value változójával egyenlő. A t és k vektorok i elemei az i folyamat t és k változóit jelentik Az i folyamat végeredménye log(i) lépésben áll elő. A ciklusnak azonban mégis log(N) –ig kell futnia, mert a folyamatoknak szükség esetén tovább kell küldeniük az értéket

az arra váró folyamatnak. Tesztelés: A tesztelés a Lovardából elérhető nyelvi labor által biztosított clusteren történt. Itt számos gép (Max: 25) áll rendelkezésre. A program különböző értékmennyiség mellett, különböző számú processzoron került tesztelésre. Az eredményeket az alábbi táblázat mutatja: Értékek száma 25 50 75 100 Idő Processzorok száma 1 2 4 8 1 2 4 8 1 2 4 8 1 2 4 8 1,3605929 0,5535840 0,1318426 0,1075771 3,1048481 2,1814960 1,6905424 1,1215293 5,1146585 4,1757464 3,4252801 2,3815200 8,1837870 7,1184190 4,1142404 2,1772583