1.
Detektor felépítése
A detektor Sziliciumlapok
150 100 50 0 -50 -100 -150
0
20
40
60
80
150 100-250 -50 -100 -150 -200 100 50 0
1. ábra. A detekor A proton nyaláb a targettel ill. a szilikonlapok atomjaival történő kölcsönhatás következtében több elemirészecskére bomlik vagy külső mágneses tér következtében ill. az ütközések során a megmaradó mennyiségek (energia, impulzus, impulzus momentum) következtében a keletkezett új részecskék ill. az eredeti proton nyaláb pályája eltérhet az eredeti belőtt nyalábegyenesétől. Ezért fontossá vált, hogy a részecske pályák görbületét is meghatározzuk. A detektor - ahogy az 1 képen is látható, további képek a 9- egy csonka alapú kúp. A kúp magassága 1 méter. A proton és a target ütközésekor keletkezett részecskék pályáinak a mérésére 9 db szilícium lapot használunk, a targettől 5cm, 10cm, 15cm, 20cm, 40cm, 60cm, 80cm, 90cm, 100cm távolságra. Ezekből a szilícium lapokból az első 4 olyan, amely egyszerre képes meghatározni az X,Y koordináta szerinti értékeket. Míg az utolsó 5 párba rakott koordináta szerinti meghatározott szilícium lap.
2.
A szimuláció
A szimuláció egy korábbi fizikai kisérlet keretein belül szimulált detektor által generált adatokra épül. 1 3 2212 1 4 -1.35209 -23.2242 9 0.934413
0.938272 0 0 0 115.242 227.707 815.001 -0.327185 0.318123 1.21314 1.32213 5.00509 -2.68609 2.64209 10.0051 -5.3006 5.28334 20.0051 25.7855 100.01 101.093 403 2.59657 102.936 409 4.26055 104.796 415 1
55.8907 162.765 603.001 57.5509 164.601 609.001 59.223 166.438 615.001 111.847 224.036 803.001 113.541 225.878 809.001 115.242 227.707 815.001 Ahol, A fenebb említett okokból (ide egy hivatkozást kell tenni, de mivel nem 1 3 2212 vagyis proton 1 vagyis pozitív 0.938272 (X,Y,Z) (X,Y,Z) (X,Y,Z) 4 (X,Y,Z) – tovább nem tudom -
Az adott esemény száma Az eseményben keletkezett részecske sorszáma A részecske típusa A részecske töltése A részecske tömege (0.938272)??? A részecske keletkezési helyének X,Y,Z koordinátája ????? A momentum X,Y,Z koordinátája ??? a részecske beütéseinek száma A beütések X,Y,Z koordinátái
akartam inkonzisztensé tenni a doksit, ezért nem az eredetibe írtam) a generált állomány részecskeközpontú leírást ad a részecskéről ellentétben a valós detektorokkal, amelyek szilícium központú leírást adnak, ezért a fentebb említett hit.cpp át kell konvertálni a megfelelő alakra, majd a részecskemeghatározó programmal felparaméterezni az adatokat. Megjegyzendő, hogy ebben a feladatban használt hit.cpp és a részecskemeghatározó program apró részleteiben eltér a fentebb definiált programtól (már csak a kezdeti adatok eltéréséből fakadóan is). De mivel a dolgozat célja nem az, hogy mások eredményeit tüzetesen bemutassa és a következő algoritmusok a nem veszik vigyelembe a két programfolyamat közötti különbséget.
3.
A nem tudom, hogy milyen tiggerelő algoritmus
Az algoritmus két részből áll • Egy a fentebb említett paraméterek szerint szétválogató algoritmusból, és • Ezen szelektált adatokon végzett pálya meghatározásból
4.
Szelektáló algoritmus - Corridor.cpp
A Corridor.cpp egyik fontos része, a hitObject.h, amely a feladatunk megoldásához nyújt segítséget a részecske 1-1 beütésekor keletkezett adatok egységesített kezelése révén.
2
4.1.
hitObject.h
#ifndef HH_HITOBJECT_HH #define HH_HITOBJECT_HH #include
#include class hitObject { public: hitObject(int traee, int jj, int kk, float xxin, float yyin, float zzin, float pmoo, float ptrr, int cellnumm); hitObject(){}; friend std::ostream& operator<< (std::ostream& s, hitObject& obj); void printX (std::ostream& s); void printY (std::ostream& s); friend std::istream& operator>> (std::istream& s, hitObject& obj); int getLayer(); float getPtr(); float getXin(); float getYin(); float getZin(); int getTrae(); float getPmo(); private: int trae, j, k; float xin, yin, zin, pmo, ptr; int cellnum; }; #endif A hitObject osztály használatával a Corridor.cpp program egy pszeudó kódra átírt változatát ismertetjük, melynek keretén belül kitérünk a fentebb említett - a hit.cpp és a részecskemeghatározó különbségéből adódó - eltérések kiküszöböléséből. cin >> hit_or_not; ciklus (amig tudunk olvasni a bementr\H{o}l) ha (hit_or_not == -1) akkor átolvassuk a nem használt adatokat egyébként ha (hit_or_not == 1) akkor cin >> hitobjektum; multiMap.insert(hitobjektum.mozaik, hitobjektum); 3
egyébként counter++; ha (counter % npile == 0) akkor counter = 0; ciklus (amely bejárja mozaik értékeit) ciklus (amely bejárja az adott mozaik értéken lév\H{o} beütéseket) set.insert(hitobject.szilikon_szám); ha (set.count > 8) akkor pálya meghatározása meghívása az adott mozaik értékekre; cin >> hit_or_not; Ahogy látható az algoritmus az algoritmus a standard inputról - azért használtunk standard inputot, hogy a hit.cpp és a részecskemeghatározó programok kimenetét egyszerűen át tudjuk irányítani a corridor.cpp bemenetelévé - beolvassa a kapott adatokat és a mozaik szám szerint szelektálja szét őket. A rákövetkező esemény előtt az algoritmus minden egyes mozaik értéket megvizsgál, hogy a bennük szereplő beütések legalább 8 db szilícium lapot érintettek-e. Ha igen, akkor meghívja az adott mozaik értékekre a pálya meghatározó algoritmust. Ha nem akkor folytatja a következő elemekkel.
5.
Pálya meghatározás
Mivel, ahogy a fenti részből is kitűnik, egy-egy mérési helyhez több érték, több pont is tartozhat, ezért a pálya meghatározás előtt meg kell határozni, hogy mely 14 esetleg 13 db beütésre próbáljuk elvégezni az algoritmust. ???????????????????????? A megvizsgált beütések magas száma a targettől távol lévő szilícium lapok hibájából adódik, mivel az 5. szilíciumlaptól kezdve a felhasznált lapok különkülön mérik meg az X koordináta és Y koordináta szerinti értékeket. Mivel egyértelműen nem tudjuk meghatározni hogy, mely X koordinátához, mely Y koordináta tartozik, ezért az keletkezett bütéseket kétszer kell venni és így kell meghatározni a lehetséges variációkat. A meghatározott variációkon a kövekező feltételeknek kell teljesülni, hogy elmondhassuk, hogy az adott variáció meghatározza az általunk kívánt részecskének a pályátját. A feltételek: 1. Az első 4 (esetleg 3) elem egy egyenesre esik-e. A kritérium ponthalmaza A1 = {2, 3, 4} vagy A1 = {1, 2, 3, 4} attól függően, hogy létezik-e első szilíciumlapos beütés. A v i = 2. beütéshez tarozó helyvektor illetve v j = 4. beütéshez tartozó helyvektor 2. Az utolsó 3 szilikon lapon lévő elem egy egyenesre esik-e XZ és YZ koordinátákra nézve. A kritérium ponthalmaza az A2 = {9, 11, 13} illetve A2 = {10, 12, 14} attól függően, hogy XZ síkon vagy az YZ síkon végezzük el a feltételnek megfelelő algoritmust. A v i = 9. (10.) beütéshez tarozó helyvektor illetve v j = 13. (14.) beütéshez tartozó helyvektor 4
Beütés száma 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.
A beütés helye szilíciumlap sorszáma 1. 2. 3. 4. 5. 5. 6. 6. 7. 7. 8. 8. 9. 9.
Felhasználható adatok koordinátában mért adatok X,Y X,Y X,Y X,Y X Y X Y X Y X Y X Y
1. táblázat. A megvizsgált beütések 3. Az YZ sík szerint az előbbi 7 (esetleg 6) pont egy egyenesre esik-e, azaz az 1., 2., 3., 4., 10., 12., 14. beütés egy egyenesre esik-e. Ekkor a kritérimnak megfelelő ponthalmaz A3 = {1, 2, 3, 4, 10, 12, 14}. A v i = 2. beütéshez tarozó helyvektor illetve v j = 4. beütéshez tartozó helyvektor 4. Az első 4 (esetleg 3) pont és az (xcc, zcc) ponttal kiegészülve egy egyenesre esik-e az XZ síkban. Ekkor a kritériumnak megfelelő ponthalmaz A4 = {1, 2, 3, 4, (xcc, ycc, zcc)} illetve A4 = {2, 3, 4, (xcc, ycc, zcc)}. A v i = 2. beütéshez tarozó helyvektor illetve v j = 4. beütéshez tartozó helyvektor 5. Az utolsó 3 pont és az (xcc, zcc) ponttal kiegészülve egy egyenesre esike az XZ síkban, azaz a 9, 11, 13 beütések. A kritériumnak megfeleő ponthalmaz A5 = {9, 11, 13, (xcc, ycc, zcc)}. A v i = 9. beütéshez tarozó helyvektor illetve v j = 13. beütéshez tartozó helyvektor 6. Az YZ és XZ síkban lévő görbe görbülete egy előre meghatározott tartományban van-e. 7. Az 5., 6. szilíciumlapocskákban mért beütések egy adott pont előre meghatározott környezetében fekszenek-e külön az XZ és külön az YZ síkban. Természetesen azokon a helyeken, ahol a feltételeket csak egy adott síkban kell megvizsgálni, nem vizsgáljuk meg a teljes tér komponenseire, hanem csak a sík komponenseire.
5
6.
Az egyenesek meghatározása
Az egyenesek meghatározását az egyik legegyszerűbb módszerrel végeztük el. Veszünk 2 előre, a kritériumok szerint meghatározott pontot. Ekkor a két pontra illeszkedő egyenest tudunk meghatározni. A feltételekben meghatározott pontok egy előre definiált távolságra kell lenniük a meghatározott egyenestől. Azaz Ha
v i = (xi , yi , zi ) és
v j = (xj , yj , zj )
p. kritériumnak megfelelő,
előre meghatározott pontok, ahol p = 1..5 ⇒ e=
(v j − v i ) zj − zi
⇒
∀v k ∈ Ap , ahol p egy adott kritérium:
k v i + e(zk − zi ) − v k k<
7.
Görbületi tényezők
Az XZ sík szerinti görbületi tényező meghatározása az egyenesek meghatározásához képest egyszerűbb és gyorsabb. Adott v2 , v4 , v9 , v11 pontok, ekkor x11 − x9 x4 − x2 < 0.0110 − z11 − z9 z4 − z2
illetve
7.0.1.
Adott v2 , v4 , v10 , v12 pontok, ekkor y12 − y10 y4 − y2 z12 − z10 − z4 − z2 < 0.0015
Az 5. és a 6. szilíciumlapban mért pontok meghatározása Adott v2 , v4 , v9 , v11 , v5 , v7 pontok, ekkor
(z9 + z11 ) − (z2 + z4 ) (x2 + x4 + x9 + x11 ) , xAB = 2 4 (x9 + x11 − (x2 − x4 ) mxAb = 2∗s s x4 − x2 x11 − x9 ∗ − newF if thX = xAB + mxAB ∗ (z5 − zcc) − z11 − z9 z4 − z2 8 s x4 − x2 x11 − x9 ∗ − newSixthX = xAB + mxAB ∗ (z7 − zcc) − z11 − z9 z4 − z2 8 s=
és |newF if thX − x5 | < illetve |newSixthX − x7 | <
6
A képlet hasonló YZ síkban is Adott v2 , v4 , v10 , v12 , v6 , v8 pontok, ekkor (z10 + z12 ) − (z2 + z4 ) (y2 + y4 + y10 + y12 ) , yAB = 2 4 (y10 + y12 − (y2 − y4 ) myAb = 2∗s y12 − y10 y4 − y2 s − newF if thY = yAB + myAB ∗ (z5 − zcc) − ∗ z12 − z10 z4 − z2 8 s y4 − y2 y12 − y10 ∗ − newSixthY = yAB + myAB ∗ (z7 − zcc) − z12 − z10 z4 − z2 8 s=
és |newF if thY − y5 | < illetve |newSixthY − y7 | <
8.
Az algoritmus értékelése, vizsgálata
Az algoritmus értékelésénél általában három féle műveleti igényt tartanak számon. • A legoptimálisabb esetben végrehajtott lépések száma • A legrosszabb esetben végrehajtott lépések száma • Átlagos esetben végrejatott lépések száma Ezekből a legoptimálisabb és a legrosszabb esetet vesszük számon.
8.1.
Legoptimálisabb eset
A legoptimálisabb esetet bontsuk két részre, attól függően, hogy létezik-e egy megfelelő pálya meghatározás, vagy sem. Ha létezik, akkor a legoptimálisabb esetben már az első variációban megtaláljuk azt, ezért egy konstans időegység alatt lefut az algoritmusunk. Ha nem létezi, akkor a legoptimálisabb esetben, már az első 4 esetleg 3 pontnál mérési hibahatáron kívüli eredmények születtek, amely segítségével az algoritmus Θ(n3 ) végrehajtási lépést kíván.
8.2.
A legrosszabb eset
A legrosszabb eset akkor fordul elő, ha a variációkban szereplő értékekről csak az utolsó feltételben derül ki, hogy nem megfelelő. Ekkor az algoritmus 14 esetleg „csak” 13 db ciklust kénytelen bejárni és ellenőrizni az összes variációra a feltételeket. Ez O(n14 ) végrehajtási lépést kíván.
7
Az adatokat megvizsgálva a legoptimálisabb esetekben is viszonylag nagy végrehajtási időt kapunk. De, a korridorok megfelelő paraméterezésével elérhetjük, hogy egy-egy korridoron belülo pontok, beütések száma viszonylag alacsony maradjon, amely lehetővé teszi a tényleges futási idő lecsökkentését. Igaz, ennek a módszernek a hátránya, hogy a korridorok méretének a csökkenésével a korridorok száma növekszik meg. Gyorsítási lehetőségek A számítástechnikai jelen körülményei között jó pár lehetőséget kínál az algoritmusok futási idejének lecsökkentésének. A teljesség igénye nélkül • Szuperszámítógép • Grid • Az alkalmazásnak megfelelő célgép • ... Ezen lehetőségek közül az első variációt fogjuk részletesen megvizsgálni, összehasonlítva az egy processzoros megoldással, bemutatva az esetleges javulást vagy a kommunikációs költségek miatti romlást.
9.
Szuperszámítógép
A párhuzamosítás egyik leggyakrabban használt változata, amely a gépek ára miatt igen költséges.
9.1.
A teszt környezet
Rendszer neve Rendszer telephelye Szuperszámítógép model Szállító Teljes Memória Üzembe helyezésének éve Operációs rendszer Processzorok Maximális processzorszám Felhasznált processzorszám
ASTRAL Cranfield University HP DL140 G3 Cluster Hewlett-Packard 1712 GB 2007 RedHat Enterprise 4 Intel EM64T Xeon 51xx (Woodcrest) 3000 MHz 856 15 - hozzáférési okokból
2. táblázat. Hardver környezet A program a processzorok közti kommunikációt az MPI programcsomagot használja, amely lehetővé teszi a futási idők mérését is.
8
9.2.
A párhuzamos program konstrukciója
A program által használt processzorok két féle csoportba oszthatók • Vezérlő processzor - amely felelős az input beolvasásáért és azok „szétosztásáért” a többi processzor között • Műveletvégző processzor - amely felelős a vezérlő processzortól kapott inputokon végzett pálya meghatározásért A programnál két féle tényezőt fogunk vizsgálni. • A futás helyességét - ennek az eredményét helytakarékossági okokból a mellékelt CD-n helyezzük el, illetve • A futási idő változását a processzorok számának növelésével.
9.3.
Mérési eredmények
A mérést egy csökkentett méretű inputon végeztük el, hely és időtakarékossági okokból. Egy-egy adott számú processzorra legalább 15 futtatást végeztünk el. Az eredmény: A 2. grafikon az X tengely szerint az algoritmus során felhasznált 1 "Osszes_meres.txt"
0.8
0.6
0.4
0.2
0 0
2
4
6
8
10
12
14
16
2. ábra. Az eredmény processzor számot mutatja be - természetesen az 1 processzoros változat nem a 9.2 bekezdés szerinti párhuzamos program, hanem a szekvenciális kód mért változata -, míg az Y kooridnáta a futási időt adja meg. A kapott eredmény három részre bontható • Az első két osztlop közötti emelkedésre 9
• A második és a hetedik oszlop közötti egyenletes csökkenésre • A nyolcadik oszloptól vett szélsőséges futási eredményekre Az első szakaszban kapott eredmény érhető, hiszen a két processzoros futáskor, a vezérlő processzor szinkronizálva küldi az adatokat a végrehajtó processzornak, ezért a tényleges párhuzamos futás csak a vezérlő processzor un. „előkészítő” része és a végrehajtó processzor pálya meghatározása között alakul ki. De ez a megtakarított idő, kisebb mint az adattovábbitás költsége. A második szakaszban a processzorok számának növelésével az program futási ideje csökken. Ezt a folyamatot jól mutatja a 3. grafikon. A harmadik sza1 "Osszes_meres.txt" a*x**3+b*x**2+c*x+d
0.8
0.6
0.4
0.2
0 0
1
2
3
4
5
6
7
3. ábra. Az eredény átlagos alakulása az első 7 processzorig kaszban megfigyelhető a futási idő elég széles spektrumú szóródáa. Ezt a jelenséget több ok külön-külön vagy esetleg együttesen befolyásolhatja. • Mivel egy szuperszámítógép egyes processzorai nincsennek közvetlen kapcsolatban az összes többi processzorral, ezért a processzorok számának a növelésével lépcsőzetesen növekszik a maximális távolság a kiválasztott processzorok között, amely a kommunkiációs idő növekedését okozhatja. Ez a feltételezés csak akkor helytálló, ha feltételezzük, hogy a processzor kiosztását egy inteligens mechanizmus hajtja végre, amely megpróbálja az egymáshoz közeli processzorokat kiosztani a feladat gyors végrehajtása céljából. • A processzor számának növelésével növekszik annak a valószínűsége, hogy egy adott processzort egyszerre több folyamat futtatására használnak fel.
10
Ez alapjában véve nem csak az aktuális műveletvégző processzor lassulását eredményezheti, hanem - a szinkronizált adatátvitel miatt - a teljes párhuzamos programunkét is. Ábra mellékletbe szánt rész: 100 Reszecske utja Szilicium lapok
80
60
40
20
0 0
20
40
60
80
100
4. ábra. A részecske pályája az XZ kooridináta szerint
11
100 Reszecske utja Szilicium lapok Elso kriterium
80
60
40
20
0 0
20
40
60
80
100
5. ábra. Az első kritérium az XZ koordináta szerint
100 Reszecske utja Szilicium lapok Masodik kriterium
80
60
40
20
0 0
20
40
60
80
100
6. ábra. A második kritérium az XZ koordináta szerint
12
100 Reszecske utja Szilicium lapok Negyedik kriterium
80
60
40
20
0 0
20
40
60
80
100
7. ábra. A negyedik kriterium az XZ kooridnáta szerint
100 Reszecske utja Szilicium lapok Negyedik kriterium Otodik kriterium 80
60
40
20
0 0
20
40
60
80
100
8. ábra. Az ötödik kritérium az XZ koordináta szerint
13
A detektor Sziliciumlapok
150 100 50 0 -50 -100 -150
0
20
40
60
80
100-250 -200 -150 -100 -50 050
9. ábra. További kép a detektorról
14
