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

Összetett függvény eredményének kiszámítása adatcsatornával 2. beadandó feladat Párhuzamos Programozás című tárgy Készítette: Pesti György Mail: pocixxx@inf.eltehu Budapest, 2002. december 19 Feladat: Határozzuk meg egy F: ZxL  ZxL függvény (függvényértékeit vektor reprezentálja) értékét, ahol: (n,1) ha n prím F ((n, l )) =  (n, 0) ha n nem prím Formális specifikáció: G = vector ([1.N],(Z,L)) A =G F B=G F (F = F’ ^ ∀i∈[1.N] F(i) = (F(i)1,1)) ∈ INITF’ ↑FP F’  ( F (i ).1,1) ha n prím  FP F’ ⇒  f’ és ∀i∈[1.N]: F(i) =   ( F (i ).1, 0) ha n nem prím   Legyen ∀i∈[1.N] fi: ZxL  ZxL függvény a következő: (n, l ) ha n nem osztható i − vel fi ((n, l )) =  (n, 0) ha n osztható i − vel Ekkor F((n,l)) = f2◦ f3◦◦fn((n,l)). Megvalósítás: A fenti specifikáció megfelel az adatcsatorna tételnek. Ezáltal arra visszavezethető: s0 :  F (i ) := ( F (i

).1,1) i =[1.N] S :{ =   F (i ) : (= F (i ).1, 0) ha  F (i )1/ j  * F (i ).1 F (i )1 j=[1.N] i =[1N] } Implementáció: A program C nyelven készült, felhasználva a PVM nyújtotta szolgáltatásokat. A megvalósításban egy főprogram (primek.c) és N darab alprogram (primektaskc) szerepel A főprogram első feladata az adatok (N értéke és N darab egész szám) bekérése, amelyek az egyszerűség és rövidség kedvéért az első 100 pozitív egész szám. Ezután elindítja az N darab alprogramot, átadva nekik a inicializáló értékeket (i. folyamat azonosítója vizsgálandó értékek mennyisége). Majd megvárja a végeredményt, amit kiír a képernyőre és a primekoutput nevű szöveges állományba is. A program biztosítja, hogy minden alprogram annak és csak annak a folyamatnak küld adatot, amelynek kell. Egy alprogram: vár egy bejövő adatra (szám, logikai érték). Megvizsgálja, hogy osztható-e a taszk sorszámával. (Hasonló az elv,

mint a gyakorlaton vett legnagyobb közös osztó program) Elküldi az aktuális értéket és a logikai változót a következő taszknak, hogy prím-e a vizsgált szám. Ezt addig végzi, amíg az N darab számot meg nem vizsgált, azután terminál Megjegyzés: Matematikailag lehetne redukáltabb programot írni, hiszen ha a legnagyobb szám n, akkor elég (½ n + 1 egész része) darab taszkon végigfuttatni a számokat, (konkrétan az első 100 számhoz elegendő lenne 51 darab taszk), de a megoldás így is helyes. 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