Informatika | Hálózatok » Párhuzamos számítási rendszerek, klaszterek, szuperszámítógépek

Budapesti Műszaki és Gazdaságtudományi Egyetem Villamosmérnöki és Informatikai Kar Automatizálási és Alkalmazott Informatika Tanszék Juhász Sándor, Czuczor Szabolcs, Aszódi Barnabás Párhuzamos számítási rendszerek – Klaszterek, SMP és szuperszámítógépek – elektronikus jegyzet a Szoftver architektúrák című tárgyhoz 2004 I Tartalomjegyzék 1. BEVEZETÉS 1 1.1 TÖRTÉNETI ÁTTEKINTÉS 1 1.2 SZÁMÍTÁSI KAPACITÁS NÖVELÉSÉNEK MÓDSZEREI 3 1.21 TÖBBET DOLGOZNI 3 1.22 OKOSABBAN DOLGOZNI 3 1.23 SEGÍTSÉGET SZEREZNI 4 2. MAI PÁRHUZAMOS RENDSZEREK 6 2.1 ARCHITEKTÚRÁK 6 2.11 PC 6 2.12 SZUPER SZÁMÍTÓGÉP (MASSZÍVAN PÁRHUZAMOSÍTÁS) 6 2.13 SMP (SZIMMETRIKUS MULTI PROCESSZOR) 8 2.131 UMA (Uniform Memory Access) 8 2.132 NUMA (Non Uniform Memory Access) 9 2.133 CC-NUMA vs NC-NUMA 10 2.134 UMA vagy CC-NUMA 11 2.14 KLASZTER 12 2.141 A klaszter összeköttetési hálózatának biztonsága 12 2.142 Érvek a klaszter mellett és ellene 14

2.2 ARCHITEKTÚRÁK ÖSSZEHASONLÍTÁSA 15 3. KLASZTER 18 3.1 PÉLDÁK KLASZTEREKRE 18 3.11 GYŰRŰTOPOLÓGIÁBA SZERVEZETT KLASZTER 18 3.12 WEB SZOLGÁLTATÁS 20 3.13 EGYÉB PÉLDÁK 21 3.14 EGYEDI KOMPAKT KLASZTEREK 24 3.15 TELJES KLASZTER RENDSZEREK 24 3.151 DEC OpenVMS klaszter 24 3.2 MEMÓRIAKEZELÉS 27 3.21 CACHE 28 3.211 Cache koherencia 33 3.212 Cache koherencia problémának megoldásai 33 3.22 CACHE TRÜKKÖK 37 3.3 KLASZTER ARCHITEKTÚRÁK 38 4. IRODALOM JEGYZÉK 41 II 1. BEVEZETÉS 1.1 TÖRTÉNETI ÁTTEKINTÉS A számítástechnika születésének hajnalán a felhasználók boldogak voltak, hogy született egy eszköz, mely az egyszerű matematikai műveletek elvégzését képes volt meggyorsítani számukra. Idővel egyre több és összetettebb feladatok elvégzését bízták rá, mígnem a számítási teljesítmény már kezdett kevésnek bizonyulni. Így nem volt mit tenni, tovább kellett fejleszteni a számítógépek processzorait, hogy

képesek legyenek megbirkózni a rájuk nehezedő feladatokkal. A fejlesztések során mindig egyre nagyobb és nagyobb teljesítménnyel rendelkező processzorok jelentek meg a piacon. Ez a fejlődés napjainkig is tart, és nagy valószínűséggel, míg ember él a Földön, tartani is fog. Igen ám, de a processzor teljesítmény-növelésénekének fizikai, hőtani, gyártási korlátai vannak. Fizikai korlátai közé tartozik a pillanatnyi gyártási technika által biztosítható integráltsági fok: hány tranzisztor építhető be egy processzor foglalatába, hány kimeneti lábat tudnak elhelyezni a tokon, mennyi memória építhető be egy foglalatba, milyen vékonyra tudják készíteni a vezetékeket a foglalaton belül. A hőtani korlát is rendkívül fontos Nem elég a sok tranzisztort egy „tető” alá hozni, azok működésük során igen nagy mennyiségű hőt termelnek, amit valamilyen módon ki kell tudni vezetni a tok külső felületére és onnan tovább a

levegőbe. A hőátadás hatékonysága arányos a processzor tokjának felületével A processzoron belüli vezetékeknek minél rövidebbeknek kell lenniük, így tudnak csak gyorsan adatot átvinni, de minél kisebb a tok, annál nehezebb kivezetni belőle a hőt. A gyártás is rendkívül fontos, hisz nem elég megtervezni egy elméletileg jól működő processzort, hanem azt le is kell tudni gyártani. A gyártósorok pedig nem képesek minden legyártott darabot azonos minőségben előállítani. Gyártás után tesztelni kell, hogy az jött-e le a futószalagról, amit szerettünk volna. Ha igen, akkor az egy jó processzor, ha nem, akkor selejt, nem eladható. A jó és rossz processzorok arányát nevezik a gyártósorok kihozatalának A ráfordítások és a kihozatal alapján kiderül, hogy gyártható-e az a termék, vagy egyszerűen nem lehet piacra dobni, mert túl drága lenne a tudásához képest. Tehát az egy processzortokba besűríthető „erő” mindig

véges. A számítástechnika fejlődésében azért van ekkora lendület, mert képes egyre több embert meggyőzni arról, hogy szüksége van rá, használata megkönnyíti az életét, és egyre több felhasználási területet talál magának. Tegyük hozzá, ez nem is olyan nagy baj, hisz tényleg hasznos. Nagyon sok munkát képes levenni a vállunkról Az idők során a rábízott feladatok mennyisége mindig gyorsabban növekedett, mint az egy processzorba sűríthető számítási teljesítmény. Kezdetben csak egyszerű számítások elvégzése volt a feladat, de mostanra eljutottunk hatalmas adatbázisok komplett feldolgozásáig, hogy azokból statisztikai adatokat nyerjünk ki. Mindeközben a meglévő számítási teljesítmény növelésének igénye mellett megjelentek egyéb, addig még nem látott kívánalmak is, mint megbízhatóság, rendelkezésre állás, szervizelhetőség. Ezen új feladatok némelyikének már csak nehezen lehet megfelelni egyetlen

processzorral (ha egyáltalán meglehet). Így már nem csak a számításteljesítmény növelése, hanem a többi kívánalom teljesítése is nélkülözhetetlenné tette, hogy áttörjünk az egyetlen processzor használata által felállított korlátokon. Nincs más választás, mint egyszerre több processzorral dolgozni Ha sok processzor egymás mellett, de egymástól teljesen függetlenül dolgozik, akkor nem sokat javul a helyzet. Ha azonban kommunikációt biztosítunk közöttük, akkor már képesek együtt, egymást segítve egy közös feladaton dolgozni. A számítási teljesítmény növekedésén kívül a megbízhatóságot és rendelkezésre állást is nagyban javítja, ha nem csak egy processzort, hanem kettőt vagy még többet használunk. Ekkor, ha az egyik meghibásodik, akkor a másik átveheti annak feladatait. 1 Eljutottunk tehát a többprocesszoros rendszerek nélkülözhetetlenségéig. Ezek olyan előnyös plusz tulajdonságokkal rendelkeznek,

melyek miatt megéri a többlet energia befektetést létrehozásukra áldozni. Többféle többprocesszoros rendszert különböztetünk meg Mindegyiknek megvan az egyedi jellemzője, ami miatt mindnek van létjogosultsága. A későbbiekben ezt a témakört vizsgáljuk meg alaposabban. 2 1.2 SZÁMÍTÁSI KAPACITÁS NÖVELÉSÉNEK MÓDSZEREI Ha adott egy feladat és annak megoldását szeretnénk valamilyen módon meggyorsítani, akkor három fő alternatíva között választhatunk. Ezek: • • • Többet dolgozni Okosabban dolgozni Segítséget szerezni Mit is jelentenek ezek valójában? Többet dolgozni nem más, mint több időt szánni a feladat megoldására, vagy ami ezzel egyenértékű, a használt eszköz teljesítményét növelni, hogy adott idő alatt több munkát (számítást) tudjon végezni. Ez a legegyszerűbb módja a feladat megoldásának felgyorsításának. De sajnos ez nem mindig elég Általában jobb eredményt ad, ha több munka befektetése

helyett inkább újra átgondoljuk a probléma megközelítését és egyszerűbb, jobb módszert választunk annak megoldására. Ez nem más, mint az okosabban dolgozás. De sajnos van olyan eset is, mikor már a több munka, és az okosabb módszerek használata sem segítenek, ekkor már nem tehetünk mást, mint segítséget szerzünk és többen, csapatot alkotva dolgozunk ugyanazon a problémán. Ha elég nagy a csapattagok létszáma, akkor egy-egy ember kiesése nem rontja jelentősen a csapat hatékonyságát. Feltéve, hogy a kiesett embernek nem volt kiemelkedő szerepe, vagy valamilyen téren nélkülözhetetlen tudása. Beláthatjuk tehát, hogy a fenti három módszer közül a csapatmunka tűnik a leghatékonyabbnak. Persze azt azért el kell ismerni, hogy a csapatmunkánál is gyorsabb lenne egyetlen nagyon okos, gyors kezű ember, hisz neki nem kellene a munkatársaival megbeszélni, egyeztetni a részleteket, és jobb lenne a hatékonysága is. Azonban ha kiesne a

munkából, akkor teljesen leállna a munkavégzés. Mit jelent mindez a számítástechnikában? Ha a feladat megoldásának felgyorsítását több dolgozással szeretnénk elérni, akkor nagyobb számítási teljesítményű processzort kell munkába állítanunk. Ha okosabban szeretnénk dolgozni, akkor a jelenleginél hatékonyabb algoritmust kell találnunk a feladat megoldásához. Ha segítségszerzéssel szeretnénk gyorsabbak lenni, akkor a feladatot szét kell osztani több feldolgozó egység között, hogy azok párhuzamos feldolgozást végezhessenek. 1.21 TÖBBET DOLGOZNI Többet dolgozni nem jelent mást, minthogy a számítógép alkatrészeit rendszeresen nagyobb teljesítményűekre, gyorsabbakra cseréljük. Ez általában az egyes alkatrészek órajel frekvenciájának és sávszélességének növelését jelenti (gyorsabb és nagyobb sávszélességű processzor, memória, busz). A processzorfejlesztők (Hewlett-Packard, MIPS, IBM, SUN stb) minden 18 hónapban

megkétszerezik az általuk gyártott rendszerek teljesítményét és ezt a tendenciát egyes gyártók már több, mint egy évtizede képesek fenntartani. Ez a fejlődési ütem egyedülálló az emberiség történetében. Nincs semmilyen más emberi alkotás, mely képes lett volna ilyen hosszú távon ilyen nagymértékű növekedést fenntartani. Az alkatrészek sebességének változása meghatározó szerepű, de nem ez a legfontosabb. 1.22 OKOSABBAN DOLGOZNI Ennek jelentése: ha egy adott feladat megoldásához többféle út vezet, célszerű azt választani, ami a legkevésbé időigényes. Vagyis, használjuk a legoptimálisabb algoritmust! Vegyünk például egy egyszerű telefonkönyvbeli név szerinti keresést. Ha az algoritmusunk a névsor legelejéről kezdi a keresést, és egyesével minden néven végigmegy a keresettig, akkor a 3 keresés átlagos hossza 100 névnél 50 lesz, 2000 névnél 1000, 200000 névnél 100000. Ami megengedhetetlen, lineáris

futásidő növekedést okoz az adathalmaz növekedésével. Ha a neveket indexszel látjuk el, akkor a keresési idő már csak a nevek azonosításához használt számjegyek számával lesz arányos, így 999 névhez elég 3 keresési lépés 999999 név esetén is csak 6 lépés szükséges. Hisz elég a keresett index számát megkeresni, nem kell az abc betűi alapján keresni. Az adott feladathoz a helyes algoritmus megválasztása nagyságrendekkel csökkentheti a megoldásának bonyolultságát. Így ez az egyik legfontosabb feladat 1.23 SEGÍTSÉGET SZEREZNI A számítástechnikában ez a párhuzamos, vagy más néven konkurens feldolgozást jelenti. A párhuzamos feldolgozás meglétéről némely esetben nem is tudunk, hiszen az a processzor mélyén is megbújhat, ezzel is növelve annak teljesítményét. Az ilyen támogatású processzorokat szupercsővezeték, szuperskalár (superpipelined, superscalar) jelzőkkel szokás jellemezni. Ezt kisléptékű párhuzamos

feldolgozásnak nevezik Ellenben ha a futtatott szoftver párhuzamos szálakat alkalmaz, azaz egyszerre több szálon fut a végrehajtása, az már nagyléptékű párhuzamos feldolgozás. Mostantól párhuzamos feldolgozás alatt ezt a többszálút (nagyléptékűt) értjük. Már az első számítógép megalkotásakor felmerült a párhuzamosítás ötlete, amikor Neumann János 1940-ben megalkotta azt. Akkor azonban ezt még elvetették, de a Neumann architektúra korunkig meghatározó szerepű maradt. A számítástechnika fejlődésével ez az architektúra lassan szűk keresztmetszetűvé vált, így ezeket a szűk keresztmetszetű részeket a már említett rejtett és nem rejtett párhuzamosításokkal próbálták szélesíteni. A későbbiekben ezt példákkal is szemléltetjük. Már az 1960-as évek végén megjelentek a több célra is használható párhuzamos feldolgozást végző rendszerek, mint például az ILLIAC IV az Illinois-i egyetemen [BBK68]. Ez már

tömeges „massive” párhuzamos feldolgozást végzett. Természetesen katonai alkalmazásra tervezték, olyan számítások elvégzésére, amely más akkori, hagyományos számítógépen már nem lett volna elvégezhető. Jóllehet az ILLIAC IV a párhuzamos feldolgozás úttörője volt, nem volt tökéletes. Ennek ellenére a 70-es évek elejéig életképes maradt, sőt a tudománynak új, máig fejlődésben lévő területeit nyitotta meg. A 70-es évek végén és a 80-as évek elején az átlagos számítógépekbe szánt processzorok ár/teljesítmény aránya kezdett annyira lecsökkenni, hogy az már összehasonlítható volt a nagy, speciális számítógépekével és ezt a párhuzamos feldolgozás fejlesztői is észrevették. Igaz a processzorok külön-külön nem voltak túl gyorsak, azonban már akkor felismerték annak a lehetőségét, hogy több processzor összekötésével elérhető a nagygépek számítási teljesítménye. Ez a feladat, a processzorok

összekötése könnyűnek hangzott, de nagy nehézségeket okozott, és okoz mind a mai napig is. Hiszen sokkal nagyobb feladat számos különálló egység munkáját összehangolni, hogy azok egy egységet alkossanak, mint egynek megmondani, mit tegyen. Több egységben több a hibalehetőség, nehezebb koordinálni őket, és a programozásuk is sokkal többe kerül, mint egyetlen egység esetén. Végül is, amit a hardveren spórolni lehetett, azt a szoftverfejlesztésre kellett szánni, és ez így nem volt túl jó üzlet. A 90-es évek elején is tovább szárnyalt a processzorok fejlődése. Olyan processzor halmazok alakultak ki, melyek összteljesítménye már elérte a nagygépekét, míg áruk azok ára alatta 4 maradt. A folytonosan növekvő processzor számuknak köszönhetően még a legeslegnagyobb számítógépeket is lekörözték teljesítményükkel. Ekkor már a programozásuk nehézsége sem tudta háttérbe szorítani őket. Most már megfelelő

számú ember volt, kinek megérte a többletköltség az elérhető legnagyobb számítási kapacitás miatt. Ilyenek voltak például: • • • • • Tudósok, akiknek fontos volt mihamarabb elvégezni a munkájukat, így világelsőként igazolni, vagy megcáfolni elméleteket, hogy elsőként publikálhassák azt Mérnökök, akiknek fontos volt a minél részletesebb, aprólékosabb szimuláció elvégzése, hogy a hibákat még a tervezőasztalon kiszűrhessék, a változtatásokat ne az elkészült drága prototípuson – vagy ami még rosszabb, a kész gyártósoron – kelljen elvégezniük Kereskedők, akik az eladási mutatók részletes elemzése után még tökéletesebb stratégiát építhettek a pénztárcáink könnyítésére Repülőtársaságok, a jegyfoglaló rendszerükhöz Pénzügyi szakértők, a vetélytársak megelőzéséhez 5 2. MAI PÁRHUZAMOS RENDSZEREK 2.1 ARCHITEKTÚRÁK Az architektúra nem más, mint a számítógépet alkotó egységek

(pl.: memória, processzor, „ki-/ bemeneti”, azaz I/O egység) és az ezeket összekötő buszrendszer összessége és maga a logika is, amivel összekötjük őket. Az architektúrákat az alapján különböztetjük meg egymástól, hogy milyen módon kapcsoljuk benne össze az egyes komponensek, és mit tekintünk benne egy komponensnek, építőelemnek. Egy építőelem lehet a processzor egymaga is, van eset, mikor egy processzor és egy memória összekapcsolva alkot egy építőelemet és van olyan eset is, mikor egy komplett számítógép egy elem. De nézzük végig, manapság milyen jól megkülönböztethető architektúrák léteznek! 2.11 PC Egy teljesen átlagos, minden háztartásban megtalálható számítógép. Egyetlen processzorral, egy memóriaegységgel, egy I/O rendszerrel. Ezek az elemek egy közös rendszerbuszra csatlakoznak. A rendszerben csak rejtett párhuzamosítás van, azaz párhuzamos feldolgozás csak a processzoron belül van. Ez a Neumann

architektúra legegyszerűbb megvalósítása Természetesen a nagyobb számítási teljesítmény elérésére a szuperszámítógépekhez kifejlesztett technológiákat is, és cache-t is használ. Itt minden kis rész egy-egy külön építőelem (pl. processzor, memória, I/O egység) Ennek az architektúrának a közös rendszerbusz a sebességbeli korlátja. Hisz minden adatmozgásnak ezen át kell mennie. Nagy előnye az „egyszerűsége”, kiforrottsága és az egyes elemek egyesével történő cserélhetősége. Persze az interfészek és a kompatibilitás megtartása mellett. 1. ábra: Egy PC topológiája 2.12 SZUPER SZÁMÍTÓGÉP (MASSZÍVAN PÁRHUZAMOSÍTÁS) A masszívan párhuzamos rendszerek esetén a nagyobb számítási kapacitás létrehozását úgy oldják meg, hogy sok azonos funkciójú építőelemeket tesznek egymás mellé és összekötik őket. Így sokan hajtják végre egyszerre (egymással párhuzamosan) ugyan azt a műveletet különböző

változókkal. Természetesen nem szükséges, hogy az összes építőelem teljesen azonos legyen. Lehetnek elemek, melyeknek speciális funkciójuk van a rendszerben, de az egy időben azonos feladatot végrehajtó elemek mind azonosak, vagy legalábbis azonosnak tűnnek a feladat végrehajtása szempontjából. Egy építőkocka egy processzort és egy memóriát tartalmaz. Az építőkockák (az egyes processzor - memória párosítások) egymással párhuzamosan tudnak feladatot végrehajtani, ők alkotják a rendszer csomópontjait. Ezeket a csomópontokat a nagy darabszámuk miatt igen sokféle módon lehet összekapcsolni. Az egyes összekapcsolási módok a szomszédok számát, a gyűrűalkotás lehetőségét is definiálják. Igen 6 bonyolult, egyedi célokra specializált számítógépet tudnak létrehozni az összeköttetések megfelelő megtervezésével. Miután egyedileg kell megtervezni, minden egyes speciális esetre a rendszert és az igen sok elemből áll,

ezért igen drága az előállítása. Speciális feladat lehet például nagyméretű mátrixokon való gyors műveletvégzés. Az egyes csomópontokat speciális hálózat köti össze. A kész rendszer általában nem bővíthető, csak akkor, ha összeállításakor nem töltötték fel benne az összes csomópontot processzor és memória elemmel. Az egyes építőelemek darabonként nem fejleszthetőek, esetleg egyszerre az összes egyidejű cseréjével. Idővel, a technológia fejlődésével az egészet, az alapjaitól kell újratervezni. Az új processzorok új összeköttetési módokat követelhetnek maguknak. A rendszer processzorainak száma elérheti a több százat is Ennek a megvalósításnak hatalmas előnye, hogy nincs előre definiált rendszerbusz, ami korlátozhatná a sávszélességet. A rendszer tulajdonságai nagymértékben igazíthatóak a teljesítendő igényekhez, hiszen egyedileg kell tervezni. Persze ez sok pluszmunkával és borsos árral jár. De

bizonyos esetekben elkerülhetetlen Miután a rendszert egyedi feladatok megoldására élezik ki, ezért nem lesz univerzális. Azaz amire tervezték, azt nagyon gyorsan fogja végrehajtani, de ettől még bizonyos feladatokat lehet, hogy egy asztali PC-nél is lassabban fog elvégezni. Az egyes csomópontok felhasználásának két fő lehetősége van, vagy mindegyik csomópont azonos feladatot lát el, vagy soros feldolgozást végeznek, azaz egy csomópont a végrehajtás egy fázisáért felel csak, annak végrehajtása után továbbadja a következő csomópontnak további végrehajtásra. A rendszer topológiája (a csomópontok összekapcsolása) különböző lehet: - sor: a csomópontok a közvetlen (síkban vett) szomszédjaikkal vannak összekötve. Lásd 2-es ábra! 2. ábra: Egy soros- és egy gyűrű kapcsolású (jobbra) szuperszámítógép topológiai csomópont elrendezése - gyűrű: nem más, mint a széleinél összekötött sorkapcsolás, itt minden

csomópontnak 4 szomszédja van. Pl: összekötjük a képen az 1-3, 1-7, 2-8, 3-9, 4-6, 7-9 csomópontokat. Lásd 2-es ábra! - kocka: a sorkapcsolás térbeli megfelelője, ahol egy csomópontnak már 6 szomszédja lesz maximum - hiperkocka: a kocka olyan változata, ahol minden csomópontnak azonos számú szomszédja van - tórusz: a kocka kapcsolás egy továbbfejlesztése, mely a gyűrű felépítés jellemzőit is magában hordozza 7 2.13 SMP (SZIMMETRIKUS MULTI PROCESSZOR) Az SMP (szimmetrikus multiprocesszor) párhuzamosan kapcsolt processzorokból áll, melyek egy közös rendszerbuszra csatlakoznak. A párhozamosan kapcsolt processzorok egyenrangúak, nincs semmilyen különbség közöttük. A rendszerben lévő összes erőforrás közös. Mindegyik processzor képes hozzáférni és vezérelni mindegyik erőforrást Az egész rendszernek egy közös I/O egysége és memória egysége van. Ezért a processzoroknak osztozniuk kell rajtuk. Az erőforrások használati

jogának megszerzését arbitrációval oldják meg. Így az operációs rendszer egy teljesen közönséges egyprocesszoros gép képét is tudja mutatni a futtatott alkalmazások számára, ha az az előnyösebb számukra, de ha az alkalmazás képes kihasználni a párhuzamosan több processzoron való futtatás előnyeit, akkor, azt is képes biztosítani. Így már valósan futtatható többszálú program is Ebben az esetben a több processzor csak a számítási kapacitást növeli meg. A memória és az I/O sávszélességét el kell osztaniuk egymás között, mert közösen használják őket. Így az egy processzorra jutó keresztmetszet, sávszélesség kisebb lesz, mint egy egyprocesszoros gép esetén. Ezért maximum 16 processzoros rendszert érdemes ezzel az architektúrával készíteni Mert ekkora már annyira leszűkül a sávszélesség, hogy a processzorok mindig csak adatokra várnának. A sok processzoron egyetlen közös operációs rendszer fut Nem

szükségszerű, hogy minden többprocesszoros rendszer egyben szimmetrikus is legyen. Ha a processzorok nem képesek ugyanazt a feladatkört ellátni, akkor aszimmetrikus processzorokról, aszimmetrikus feldolgozásról van szó. Ilyen lehet például az I/O társprocesszor mely a kommunikációs feladatok elvégzéséért felelős, vagy a matematikai társprocesszor, mely a bonyolultabb matematikai feladatokat láthatja el. Így a rendszerben működő egy vagy több további processzornak ennyivel is kevesebb feladata marad. Egy ilyen rendszerben, ha a fő processzornak I/O műveletre van szüksége, akkor azt tovább adja a társprocesszornak, amit az elvégez helyette. 2.131 UMA (Uniform Memory Access) Az SMP tulajdonságai érvényesek rá, azaz minden erőforrás mindenki által látható és hozzáférhető. Ebben az architektúrában a memóriához való hozzáférés, mindenki számára azonos feltételű, azonos módú, és azonos késleltetésű. A válasz természetesen

igen! Hiszen az SMP csak kevés processzor párhuzamos összekapcsolását képes elvégezni, általában négyet, de maximum is csak nyolcat, míg CCNUMA rendszerekben nem ritka a 32 processzoros változat sem. A CC-NUMA esetén, egy csoporton belüli működést vizsgálva a rendszer késleltetése közel azonos az SMP-jével, míg csoportok közötti adatcsere esetén általában 1,47 körüli szorzótényezővel nő a rendszer késleltetése. 3. ábra: Egy UMA SMP topológiai elrendezése 8 2.132 NUMA (Non Uniform Memory Access) A NUMA a „Non-Uniform Memory Access” rövidítése, ami nem azonos memória hozzáférést jelent. [wNUM] Ez a rendszer is megtartja az SMP szabályait, azaz minden processzor számára minden memóriához biztosítja a hozzáférést. Ekkor azonban még csak UMA-ról beszélünk. A NUMA ettől annyiban különbözik, hogy a processzorok memóriához történő hozzáférése nem lesz egyenrangú. Azaz késleltetési időben nem lesz mindegy, hogy

melyik processzorból próbáljuk melyik memóriát elérni. A rendszer skálázhatóságában is van eltérés Itt sok száz, vagy akár több ezer processzor is összekapcsolódhat, ami egy közönséges SMP esetén ez elképzelhetetlen lenne. Az UMA-val ellentétben itt minden processzornak van saját gyors hozzáférésű memóriája (cache). Lásd 4 ábra! A gyakran használt megosztott adatokhoz egy külön közös memóriát használnak a processzorok. Minden processzor melletti cache-hez hozzáférhet minden más processzor is. 4. ábra: Egy NUMA SMP topológiai elrendezése A NUMA típusú rendszereken belül két altípust különböztetünk meg: az egyik a CC-NUMA, mely cache koherens NUMA, a másik a NC-NUMA, amely nem cache koherens NUMA. Utóbbira remek példa lehet a klaszter. Mindkét altípus kész SMP-kből építkezik, melyeket a memóriabuszon keresztül kapcsolunk össze. Lásd 5 ábrát! A memóriák egy nagy, folytonos, globális címrendszert alkotnak, így

mindig egyértelmű a címzés. 5. ábra: Egy NUMA A két rendszer (CC-NUMA és NC-NUMA) közötti különbség a memóriabuszokat összekapcsoló egység működésében rejlik. Ezek az egységek tudják, melyik memóriacím melyik processzor csoporthoz tartozik. Ezért bentről, a csoporton belülről induló kéréseket 9 szükség esetén továbbítani tudják a címzett processzor csoportjának egységének, és a kintről jövő kéréseket is képesek fogadni, majd továbbadni a memóriabuszukra kapcsolt többi belső egység számára. Tehát kétféle szerepet töltenek be Egyrészt memóriaként működnek, mert a csoporton kívüli kéréseket fogadják, és azokra válaszolnak. Másrészt – a csoporton belülről nézve pedig – processzorként működnek, mert a kívülről hozzájuk érkező kéréseket feldolgozásra továbbadják és választ várnak rá. A NUMA nevében az N tehát onnan származik, hogy a saját csoporton belüli memória másképp van

kezelve, mint a másik csoportéban lévő. 2.133 CC-NUMA vs NC-NUMA Lássuk, hogyan működik mindez a valóságban (5. ábra)! Vegyünk egy példát: a jobboldali „B” csoport egyik processzora (4. Proc) olvasni szeretne egy adatot, mely jelen esetben a másik „A” csoport memóriájában (0. Memória) található Ekkor a processzor (4 Proc) kiadja a csoportjának közös szimatoló buszára, hogy olvasni szeretné a kívánt adatot. Ezt mindenki megkapja az adott buszon, még a csoportokat összekötő egység (D, B csop.) is A lokális, csoporton belüli memóriák keresik, de természetesen nem találják. Az összekötő egység (D, B csop.) ellenben tudja, hogy az adat a másik csoportban lesz Ezért küld egy kérést a másik csoport összekötő egységének (D, A csop.), az veszi és feldolgozza azt Ez az egység (D, A csop.) a saját csoportjában lévő szimatoló buszra kiadja a kérést, mintha ő maga keresné az adatot. A baloldali csoportban lévő memóriák a

keresésük során megtalálják az aktuális értéket (akár a főmemória (0. Memória), akár valamelyik cache) és visszaküldik az eredményt a saját összekötő egységüknek (D, A csop.) Ez az egység újra felveszi a kapcsolatot az eredeti kezdeményező összekötő egységgel (D, B csop.) és megválaszolja neki a kérését Végül az eredeti összekötő egység (D, B csop.) kiszolgálja a kérést, és a processzor (4 Proc) megkapja a kérésére a választ (persze némi várakozás után). Mi történik, ha ugyanezt az adatot ezek után egy másik processzor is megpróbálja elérni? Legyen a kezdeményező processzor, például az eredeti példányt tároló csoporton belüli processzor (1. Proc) A kiadott kérésre azonnal válaszol a saját csoportjában lévő memória (0 Memória), hiszen ő már tárolja a kért adat egy régebbi változatát, amely azóta meg is változhatott a másik csoportban lévő processzor (4. Proc) működése révén Ennek a helyzetnek

a lekezelésében tér el élesen egymástól a CC-NUMA és NC-NUMA. A NC-NUMA nem törődik az esetleges hibás példánnyal, és azt adja tovább a processzor kérésére válaszként. A memóriát nem a szokványos értelemben használja, hanem, csak, mint csomagokat küldő csatornát. A DEC memória csatorna megvalósítása is ilyen A CC-NUMA teljesen hétköznapi memóriaként használja a memóriát. Így az összekötő egységnek tudnia kell arról, hogy kinek milyen adatot továbbított. Vissza kell tudnia keresni, kitől kell visszakérnie a legfrissebb példányt. És ettől a tárolási funkciójától lesz olyan, mintha maga is egy processzor lenne a saját csoportján belül. A visszakérési folyamat a fent részletezett lépések fordítottja lesz. Ha több mint két csoportot kapcsolunk össze, akkor a következő események teljesen hétköznapinak számítanak. Egy processzor beolvasna egy adatot, ami történetesen egy másik csoportban van tárolva. Ezt a

processzor csoportjának összekötője elkéri az adatot tároló csoport összekötőjétől, de ő tudja, hogy már korábban elkérték tőle. Ezért az előbb visszakéri 10 az adat aktuális példányát a harmadik csoporttól, ahol épp használták, és csak utána szolgálja ki az eredeti kérést. Mindezt képzeljük el, hogyan nézhet ki egy több száz, vagy több ezer processzoros rendszerben! Előfordulhat az is, hogy egy adatról sok kint lévő példány létezik, amit sok processzor olvas egyszerre. Egyszer csak az egyik processzor megváltoztatja az adat értékét, erről értesíti az eredeti összekötőt, mely ismeri az összes többi példány helyét. Az összekötőnek ekkor értesítenie kell minden olyan processzort, ami ezzel az adattal dolgozik, hogy az adat megváltozott, kérjék el a legfrissebbet. Ez egy több száz elemből álló rendszerben elég nagy fejfájást okozhatna az összekötő számára. Erre két megoldás létezik Az egyik a DASH

(Directory Architecture for Shared memory) változat, mely egy bitvektorban tárolja azt az információt, hogy a kérdéses adatból szerepel-e példány az adott csoportban, vagy sem. Sajnos a bitvektor csak véges hosszú lehet, azonban hatalmas előnye, hogy az adat frissítése így egy szempillantás alatt megtörténhet. A másik lehetőség az SCI (Scalable Coherent Interconnect) változat, mely csak egy láncot tárol, és a frissítés a láncszemek között terjed szét. Ennek előnye, hogy az elemek száma nincsen maximalizálva 2.134 UMA vagy CC-NUMA Vajon mi a különbség az SMP (UMA) és a CC-NUMA között? Vajon mindkettőnek megvan a létjogosultsága? A válasz természetesen igen! Hiszen mindkettőnek megvan a maga vitathatatlan előnye, és persze hátránya is. Lássunk rájuk példákat! Az SMP csak kevés processzor párhuzamos összekapcsolását képes elvégezni, általában négyet, de maximum is csak nyolcat, míg CC-NUMA rendszerekben nem ritka a 32

processzoros változat sem. Az SMP előnye, hogy minden processzor minden memóriához azonos késleltetéssel fér hozzá, míg a CC-NUMA esetén ez nem igaz. A CC-NUMA esetén egy csoporton belüli működést vizsgálva a rendszer késleltetése közel azonos az SMP-jével, míg a csoportok közötti adatcsere esetén általában 1,47 körüli szorzótényezővel nő a rendszer késleltetése. Ezért általában nagyobb késleltetésű lesz a CC-NUMA egy sima SMP-hez képest. Mindkettőn egyetlen egy operációs rendszer fut, így egyszerűbb az adminisztráció, a feladatelosztás is egy kézben összpontosul. Hátránya, hogy a rendszer minden további fejlesztésekor mindig meg kell küzdeni az egy operációs rendszer alá való beépíthetőséggel. Minden alkalommal ki kell bővíteni az operációs rendszer képességeit, feladatkörét. Egy másik igen nagy kérdés a rendelkezésre állás. Egy sokprocesszoros rendszertől egyértelműen elvárható, hogy ne kelljen soha

leállítani, a hibákat is képes legyen lokalizálni, és a meghibásodott részeket is könnyen el lehessen szeparálni. Sajnos e kritériumoknak sem az UMA, sem a CC-NUMA nem felel meg. Ha csak egyetlen processzor is meghibásodik a rendszerben, annak hibája továbbterjed (akár hibás memóriabejegyzés olvasása miatt, akár egy kölcsönös kizárás soha fel nem szabadítása miatt kialakult végtelen sorbaállás miatt), és előbb-utóbb a teljes rendszer használhatatlanná válik, majd leáll. Akkor lesz csak újra használható, ha a hibát kijavítják, és a teljes rendszert újraindítják. Ez egy igen nagy hátránya az egy nagy közös operációs rendszernek. Persze egy NC-NUMA esetében – mint amilyen egy klaszter, ahol sok operációs rendszer van, melyek együtt de mégis szeparáltan dolgoznak – az összes utoljára említett probléma könnyűszerrel megoldható. Még a szándékos leállások 11 esetére sem kell a teljes rendszert leállítani, csak

azokat a gépeket, melyeket szerelni, tesztelni szeretnénk. Egy UMA, CC-NUMA rendszernél ez nem lehetséges Ott vagy minden teljes gőzzel megy, vagy a teljes rendszer leáll. 2.14 KLASZTER A rendszer minden csomópontja egy-egy önállóan is működőképes számítógép. A csomópontok szabványos kommunikációs hálózattal vannak összekötve. Ez a szabványos hálózat akár egy switch is lehet. Mivel a rendszer szokványos elemekből építhető, ezért az egységnyi számítási kapacitásért itt kell legkevesebbet fizetni. [wCLA] A szabványos elemekből való építkezés másik előnye a könnyű építhetőség és a rendszer méretének jó skálázhatósága. A rendszer az alkalmazások felé egy nagy erőforrás képét mutatja A programoknak nem kell feltétlenül támogatniuk a klaszteren való futtatást. Ha más architektúrára lettek optimalizálva, akkor is futni fognak, igaz nem olyan sebességgel, mint az eredeti célrendszeren. Ha egy csomópont

meghibásodik, akkor annak feladatait, - a hiba detektálása után - a rendszerbe kapcsolt másik gép átveheti. A rendszerben nem egyetlen operációs rendszer van, hanem annyi, ahány különálló számítógép. Lásd még bővebben a 3 fejezetben! 6. ábra: Egy klaszter topológiája 2.141 A klaszter összeköttetési hálózatának biztonsága A klaszterek csomópontjait összekötő hálózatokat biztonsági szintjük alapján két különböző csoportra bontjuk. Az egyik a nyílt hálózat, ez a külvilág felé teljesen szabad, megfelel a szabványos protokolloknak. Ez azt jelenti, hogy a klaszterek nyilvános és épp ezért szabványos kommunikációs csatornán tartják a kapcsolatot egymással. A másik a zárt hálózat, melyhez csak a klaszter elemei férnek hozzá, a külvilág felől láthatatlan. Ezért nagy biztonságú. Lásd a 7-as ábrát! 12 7. ábra: Nyílt és zárt klaszter hálózat A nyílt rendszerben a szabványos mindenki által elfogadott

protokoll miatt üzenetekkel kell kommunikálni, ezért nagyobb az overhead, maga a kommunikációs csatorna sem biztonságos, ellenben nagyon egyszerűen építhető, olcsó. Itt gondoskodni kell a titkosításról, és a megfelelő szintű biztonság eléréséről. A zárt rendszert a fejlesztők a klaszter kívánalmainak legmegfelelőbben fejleszthetik ki, saját, csak az adott klaszter által látható hálózatot építenek. Magának a kommunikációs hálózatnak sokféle megvalósítása lehet. Kisebb az overhead, hisz maguknak tervezték, optimalizálták és teljesen biztonságos, hisz kívülről nem lehet hozzáférni a hálózathoz. Ezért nem kell bajlódni a titkosítással. De ez a zárt rendszer önmagában általában nem elég, mert így teljesen szeparált a külvilág felől. Nem képes vele semmilyen kommunikációra Így általában az ilyen zárt rendszer is rendelkezik egy másik külső külvilág felé menő kapcsolattal, melyen át kívülről is

hozzáférhető. Természetesen ez védett és szabványos 13 2.142 Érvek a klaszter mellett és ellene Érvek mellette: - Manapság már elég nagy teljesítményű processzorokból lehet építkezni, így megéri megküzdeni az összeköttetési hálózat okozta bonyodalmakkal - Nagy sebességű kommunikációs hálózatok fejlődtek ki, melyek meggyorsítják a csomópontok közötti kommunikációt, ilyenek például: o Fibre Channel Standard (üvegszál) o ATM (Aszinkron Átviteli Mód) o SCI (Skálázható Koherens Összekapcsolás) o gigabit Ethernet - A kezdeti szoftver ellátottság hiánya kezd enyhülni, és olyan szoftverek eszközök látnak napvilágot, melyekkel megoldható a klaszterek kényelmes menedzselése Érvek ellene: - Hiányoznak a klasztereket egy egységes rendszerként kezelő szoftverek. Az elemeket egyesével kell beszerezni, nem lehet egy egységes „kulcsrakész” rendszert vásárolni - Rossz kihasználtság, manapság még kevesen

éreztek rá a klaszter által nyújtható lehetőségek előnyeire (skálázhatóság, nagy rendelkezésre állás). De természetesen léteznek már olyan területek, melyeken előszeretettel alkalmazzák őket. Ilyenek, pl: adatbázisok, Web szolgáltatás, tranzakció kezelő rendszerek, bejelentkezések kezelése 14 2.2 ARCHITEKTÚRÁK ÖSSZEHASONLÍTÁSA Miután már átfogó képet szereztünk a lehetséges architektúrákról, azok sajátosságairól és hasonlóságairól. Lássunk egy összefoglaló táblázatot (8 ábra), melyben a legfontosabb jellemzők alapján összehasonlítjuk különböző típusokat. PC Szuper SMP közepes (memória, I/O korlátoz) Teljesítmény egységnyi nagy Skálázhatóság nincs rossz (rugalmatlan) Elérhetőség egységnyi jó Adminisztráció egységnyi egységes, egyszerű egységes, egyszerű Licence-k száma 1 darab speciális 1 darab Biztonság hagyományos jó hagyományos SW ellátottság sok speciális

sok (PC) Számítási teljesítmény ára 1 >>1 >1 korlátozott (HW kiépítés) egységnyinél rosszabb Klaszter nagy (a hálózat és a kommunikáció korlátoz) kiváló (SW kell csak hozzá) kiváló speciális program kell hozzá minden gépre külön kell hagyományos + titkosítás (speciális megoldások) speciális (Web serv, DB) ~1 8. ábra: Az architektúrák összehasonlítása Teljesítmény: az adott architektúrával elérhető legnagyobb számítási kapacitás. Ha egy átlagos PC-hez hasonlítjuk a többi rendszer teljesítményét, akkor a szuperszámítógép teljesítménye kimagaslóan nagy lesz, hisz az adott feladatra optimalizálták. Az SMP a PC-hez képest nagyobb teljesítményt mutat, de az elosztott erőforrásokon való osztozkodás a rendszer teljesítményét korlátozza. A klaszterben az egyes gépek jól tudnak egymás mellett dolgozni, csak a közös kommunikációs rendszer használata okoz korlátokat. Skálázhatóság: Egy PC-t

csak alacsony szinten lehet skálázni. Mert nem építhető plusz új elem bele, csak a meglévőket lehet gyorsabbakra cserélni, de így is meg kell tartani az interfészeket és a kompatibilitást a meglévő elemekkel. A szuperszámítógép korlátozottan bővíthető. Csak az előre megtervezett és megvalósított bővítési lehetőségeket lehet kihasználni. Például a még be nem töltött helyekre újabb processzorokat szerelni Az SMP csak korlátozottan bővíthető, mert előre rögzített a hardver struktúrája, maximális processzorszám, rendszer memória méret. A klaszter tetszőlegesen bővíthető újabb rendszerbe 15 kapcsolt számítógépekkel, szinte folytonos skálán, csak megfelelő szoftver kell hozzá, mely irányítja, kézben tartja a rendszert és elosztja a feladatokat. Elérhetőség: PC esetén, miután minden alkatrészből csak egy van. Itt nincs külön hibajavítás és védelmi rendszer. De épp ezért csak kevés minden romolhat el

Szuper számítógép esetén jó a hibatűrő képesség, hisz ha megfelelően lett tervezve, akkor ellen kell tudjon állni. SMPnél a PC-hez hasonló a hibatűrés, de azért annyival rosszabb, hogy itt több hibalehetőséget rejt magában a több processzor, bonyolultabb HW. A sok processzor közül elég, ha egy elromlik. Miután minden erőforrás közös, az a többi működését is előbb-utóbb lehetetlenné teszi. A klaszter esetén a hibatűrés kiváló, hisz teljesen elosztott a rendszer, az egyes elemek nem szűkítik egymás sávszélességét, hiba esetén átvehetik egymás feladatát. Természetesen ehhez szoftveres, hardveres támogatás is kell. Mint például: rendszer-adminisztrációs támogatás és folytonos monitorozás. Adminisztráció: PC, SMP esetén nincs semmilyen különleges feladat. A szuperszámítógép és a klaszter speciális támogatást igényel, mert a feladatok elosztását nyomon kell követni, egyenletes teherelosztást kell biztosítani,

és az egyes feladatok elvégzését is nyilván kell tartani. Licence-k száma: A PC és SMP esetén egy darab kell, hisz csak egy operációs rendszer fut és a futtatott programokból is elég egyetlen példány. A szuper számítógépre természetesen speciális licence kell. A klaszter esetén viszont minden egyes gépre külön-külön kell egy licence, hisz minden gép független operációs rendszert futtat. Biztonság: A PC és SMP esetén miután önálló gépek a külső rendszerből való támadás, lehallgatás nehézkes. Elegendő a megszokott biztonsági előírásokat betartani A védelmet jelszó és tűzfal biztosíthatja. A szuperszámítógép biztonsága egyedi, jól tervezett A klaszterben viszont komoly problémát okoz az egyes gépek közötti távolság, és a szabványos kommunikációs vonalak használata. Mindemellett a klaszterben sok kommunikáció folyik a hálózaton, ezért azt mindenképp titkosítani kell az átküldött adatokat. Szoftver

ellátottság: A PC-hez rengeteg szoftver kapható, vagy akár fejleszthető is. A szuperszámítógép speciális szoftvereket igényel, hisz egyedisége miatt rá kell szabni az optimális működéshez. Az SMP képes futtatni a PC-s szoftvereket, igaz ekkor nem használják ki a képességeit teljesen. De speciálisan rá fejlesztettekkel ez megtehető Klaszterre már kaphatóak Web szerver, adatbázis kezelő szoftverek. A lehetőségek tárháza még igen szűk, de dinamikusan bővül a kínálat. Számítási teljesítmény ára: A szuperszámítógép egyedisége miatt nagyon drága az egységnyi számítási kapacitása, igaz cserébe robosztus teljesítményt ad. Persze csak az adott feladatkörben. Az SMP esetén néhányszor többe kerül egy sima PC-nél a működéséhez szükséges speciális kialakítások miatt. De itt is nagyobb a kapott teljesítmény A klaszter ára viszont erősen függ a becsatlakozó gépek számától. De, ha ezek a gépek már adottak, és csak

össze kell őket kötni, akkor egész olcsó is lehet. Persze klaszter esetén nem kell minden géphez monitor és billentyűzet. Ha nem akarunk felhasználói felületet az adott géphez, akkor megspórolható. 16 Mindebből kitűnik, hogy minden rendszernek megvan a maga létjogosultsága, az a feladatköre, melyben a legjobban alkalmazható. Ha igazán nagy teljesítményre van szükségünk, akkor csak a szuperszámítógép és a klaszter jöhet szóba. Ha a rendszerrel szemben a rendelkezésre állás biztonságát is megköveteljük, akkor a klaszter jön ki győztesen. Persze ez nem jelenti azt, hogy minden problémára a klaszter a megoldás De nagy teljesítmény, stabilitás, rendelkezésre állás megkövetelése esetén egyértelmű az előnye. Ilyen igényeket a Web szolgáltatásokkal, az adatbázis rendszerekkel szemben támasztunk. Hasonló követelményeket támasztanak a kutatások, fejlesztések területe is (különböző szimulációk, elemzések). Igazán

jó teljesítményt csak akkor lehet elérni a klaszterrel, ha a feladatok egymástól jól szeparálhatóak, így párhuzamosan végrehajthatóak és kevés csomópontok közötti kommunikáció is elég a végrehajtásukhoz. Nem kell nagy adatmennyiségeket átvinni a hálózaton. A kommunikációs hálózat fejlődésével az egész klaszter rendszer összteljesítménye is javul. 17 3. KLASZTER 3.1 PÉLDÁK KLASZTEREKRE Miután megismerkedtünk a klaszterek elméleti felépítésével és működésével, lássunk néhány példát, már megvalósított klaszterekre. A példák nem egy-egy egyedi esetre, hanem egy-egy alkalmazási területre próbálnak rávilágítani. 3.11 GYŰRŰTOPOLÓGIÁBA SZERVEZETT KLASZTER A 9. ábrán egy egyszerű klaszter struktúra látható mely például egy nagy alkatrészgyártó cégnél képzelhető el. A klaszter három egymással kommunikáló nagyszámítógépből áll, melyeket párhuzamosan használnak. A cégnek egyszerre három fő

feladatot kell ellátnia A gyártás zavartalan biztosítását, a szállítmányozás megszervezését, és az adminisztratív teendőket elvégzését. 9. ábra: Feladat elosztást végző klaszter Mitől válik mindez klaszterré? A gépek közötti kapcsolattól, mely a rendszert kívülről nézve egyetlen nagy hibatűrő gépként láttatja. A rendszerbe kötött gépek „életjelet” szolgáltatnak egymásnak, és ha leáll egy fontos feladatú gép, akkor annak feladatát átveszi egy másik és félbehagyja addigi munkáit. A megosztott lemezegységek az adatok megosztását biztosítják A feladatok között prioritási sorrendet állítottak fel, mely szerint a gyártás a legfontosabb, a szállítmányozás koordinálása kevésbé fontos, és az egyéb ügyintézés a legkisebb prioritású. Ezek alapján, ha a gyártásért felelős gép valamely hiba folytán leáll, akkor az összes feladatát 18 azonnal az addig adminisztrációval foglalkozó gép veszi át,

és az addig folytatott adminisztratív munkáit felfüggeszti. Ugyanez történik a szállítmányozás koordinálását végző gép meghibásodása esetén is. Ez a két feladat nem tűr semmilyen leállást, időbeli késlekedést Az adminisztrációt - legkisebb prioritású feladatot - végző gép meghibásodása esetén a másik két gép zavartalanul végzi tovább a megszokott feladatait és nem törődnek a hibával. Ezen gép hibájának kijavítása nem túl sürgős feladat, így emberi beavatkozást is igényelhet. Az ügyintézést végző gép meghibásodásának egyedüli veszélye, hogy a másik két gépnek így már tartalék nélkül maradt. Egy második hiba esetén a szállítmányozás ellenőrzését is le kell állítani (ha nem pont az romlott el), és már csak a gyártás ellenőrzése folytatódhat. Ebből következik, hogy az igazán fontos gyártási folyamat ellenőrzésének leállásához már egyszerre mindhárom gépnek meg kellene hibásodnia, ami

a szimpla egy nagygépes rendszerhez képest jóval nagyobb biztonságot ad. [wRIN] Ebben az esetben nem a párhuzamos adatfeldolgozás a legfőbb előny, hisz minden feladatkör jól elszeparálható a többitől és egy feladatkört jól el tud látni önmagában is egy gép. Ekkor feladatelosztásos párhuzamosítást végez a rendszer. Természetesen nem lehet minden feladatot szétosztani a gépek között. Vannak olyanok, melyeket minden gépen, egymástól függetlenül kell futtatni, mert a rendszer működéséhez nélkülözhetetlenek. Ilyen például a már említett „életjel” figyelés, mely megvalósítható például rendszeres üzenetküldéssel. A gyártással foglalkozó nagyobbacska cégek esetén ez a struktúra nem teljesen szokatlan. Minimum két gépet igényel: egyet a gyártás ellenőrzéséhez, egyet az ügyintézéshez, esetleg további egyet a főgép tartalékának. Hasonló megvalósítás létezhet egy közepes méretű könyvelő irodában is, ahol

a dolgozók feladatuk folytán sok adatrögzítést, szövegszerkesztést végeznek. Számukra az a legfontosabb, hogy a munkát sose kelljen megszakítaniuk, a szabványos dokumentum formátumok és sablonok mindig rendelkezésre álljanak, azaz mindenképpen működjön a központi számítógépük. Ennek eléréséhez egy, az alkatrészgyártónál bemutatott klaszternél is egyszerűbb rendszert használnak (Lásd a 10. ábrát!) 10. ábra: Feladat kritikus szövegszerkesztés 19 A rendszer két fájl szerverből és több kliensből áll. A két fájl szerver közül egy időben csak az egyik aktív, azaz a kéréseket csak az egyik szolgálja ki. A másik csendben figyeli az aktív szerver adatállományán végzett változtatásokat és másolja őket a sajátjára, hogy azok mindig konzisztens állapotban legyenek. Az aktív szerver meghibásodása esetén a másik szerver azonnal át tudja venni a feladatokat, és a munka zavartalanul folyhat tovább. Mindebből

természetesen a felhasználók semmit nem vesznének észre. A szerverek kihasználtsága egy ilyen egyszerű felépítésnél igen rossz, hisz az egyik mindig készenléti állapotban van, hasznos munkát nem végez, jóllehet a rendelkezésre állás biztonsága nagymértékben megnőtt. A rendszer legnagyobb előnye az egyszerűsége 3.12 WEB SZOLGÁLTATÁS Az egyedüli dolog, melyet egyetlen Web szolgáltató sem szeretne látni, mikor egyszerre több ezer ügyfelének szeme (vagy inkább böngészője) előtt omlik össze a szervere, vagy lesz túl kicsi a kapacitása a beérkező kérések feldolgozásához. A szolgáltatás éles versenyében az ügyfél diktál. Márpedig az ő számára az adott szolgáltató vetélytársai csupán egyetlen egérkattintásnyira vannak. Azok a cégek, amelyek a fenti hibalehetőségeket szeretnék mindenképpen kiküszöbölni, a 11. ábrán látható rendszert alkalmazzák. 11. ábra: Web szolgáltatás Ez egy igen leegyszerűsített

ábrája a valós rendszernek, de a működés bemutatásához éppen megfelelő. A főbb elemek: a router, a diszpécser és a szervercsoport 20 Az alapötlet az, hogy csak a diszpécser (dispatcher) látható az Internet oldaláról, az összes kérés – mely az ő címére (pl.: http://wwwvalamihu) érkezik – hozzá fut be, de ő maga egyetlen kérést sem szolgál ki. Helyette a befutott kérést továbbítja egy szervernek a hozzá tartozó csoporton belül, mely feldolgozza azt, és választ küld a kérésre a diszpécser további beavatkozása nélkül. A diszpécser feladata még a szervercsoport szervereinek egyenletes terhelésének vezérlése és nyomon követése valamilyen visszajelzés alapján. Általában a válasz összeállítása (beleértve az esetleges adatbázis lekérdezéseket is) sokkal nagyobb feladat, és maga az adatcsomag is nagyobb, mint egy kérés, így egy választ nagyobb feladat lekezelni, mint magát a kérést. Ezért van az, hogy több

tíz szerver kérésekkel történő ellátását csupán egyetlen diszpécser végzi. A felhasználó mindebből semmit sem tapasztal, ő csak elégedett a kért honlap szépségével és a kicsi válaszidővel. Minden kérést minden szerver képes feldolgozni a közös, elosztott adattároló rendszerük (általában elosztott adatbázis) alapján. A válaszban küldendő adatról a szerverek helyi másolatot készítenek. Így több azonos kérést gyorsabban tudnak kiszolgálni Egy nagyobb és bonyolultabb rendszerben létezhet egy külön szervercsoport, melynek egyedüli feladata az adatbázishoz való hozzáférések kiszolgálása. Ekkor első lépésként a kérés feldolgozása és a kiszolgálásához tartozó adatbázis-lekérdezés történik meg. Második lépésként az adatbázis kezelő kikeresi a kért adatokat és visszaadja őket. Harmadik lépésként a kikeresett adatokból formázással összeállítja a kívánt honlapot. Majd legvégül visszaküldi a már

kívánt formára hozott honlapot a kérést küldőjének. A rajz és az eddigi működési leírás alapján nyilvánvaló, hogy az egyes szerverek meghibásodását a diszpécsernek kell figyelni. A hibás szervernek nem küld több feldolgozandó kérést, így az nem okoz további fennakadást. A rajz alapján gyenge pontnak a router és a diszpécser tűnhet, a valóságban azonban a diszpécserből több működik egymással párhuzamosan, amik között a terhelés egyenletesen oszlik el. [wWSE] Erre remek példa az IBM két nagy „produkciója”: az egyik az Atlantai Olimpia Web honlapjának szolgáltatása volt. A másik pedig az a géppark, amely megverte sakkban Kasparovot (Deep Blue). [wDBK] Az Atlantai Olimpián egy 53 csomópontos klaszter rendszer működött (minden csomópont külön gépet jelentett), ami napi 16 millió kérést szolgált ki. 3.13 EGYÉB PÉLDÁK A Watson Kutató Intézetben létrehoztak egy 22 csomópontos klasztert, melynek minden csomópontja

egy nagyteljesítményű munkaállomás volt. Ezen rendszer hivatalos neve Watson Research Central Compute Cluster. Ma már nem is létezik az eredeti formájában, ez csak egy kezdeményezés volt. A rendszer a felhasználóknak egyetlen gépnek mutatkozott. Bejelentkezni például külön az egyik gépére nem lehetett, csak az egész rendszerbe. Lásd a 12 ábrát! 21 12. ábra: Egyenletes terheléselosztású, alkalmazás kiszolgáló klaszter A felhasználó egy terminálon bejelentkezett, ezt a vezér munkaállomás fogadta és kiválasztotta a legkisebb terhelésű szervert a felhasználó kéréseinek feldolgozásához. Minden program képes volt futni minden szerveren, azaz minden program és adat hozzáférhető volt minden szerveren. Ezt úgy érték el, hogy minden felhasználói adat külön fájlszervereken volt tárolva, az adott szerveren csak a rendszer szoftverek, adat másolatok, és kisebb ideiglenes állományok voltak. A fájlszerverekhez közvetlenül csak

a munkaállomások férhettek hozzá saját privát hálózatukon. Egy másik példa a Fermi National Accelerator Laboratory [wFNL] által üzemeltetett igen nagy klaszter, mely 400 munkaállomásból áll. Ez a rendszer egy részecske gyorsító mérési adatainak feldolgozását végzi. Az előbbi klaszterekhez képest itt az egyes munkaállomások nem különálló gépek, hanem kisebb, egységes rekeszekbe épített (rack mounted) gépek. Ezekből többet egybeépítve egy nagy „fiókos szekrényt” kapunk eredményül. Ezzel csökkenteni lehet a rendszer összköltségét és nem utolsó sorban az elfoglalt méretét. A rendszer feladata szubatomi részecskék mozgásának elemzése, melyet hatalmas földalatti detektorokkal érzékeltek, majd rögzítettek szerfelett pontos megfigyeléssel. A rögzített nagyon sok adat közül csak kevés fontos, de ezek pontos lokalizálásához mindet ki kell elemezni. Az adatok egymástól függetlenek, ezért a vizsgálatok

párhuzamosan, egyszerre is végrehajthatóak. Az egyes független adatok vizsgálatához nem kell túl sok memória, vagy tárhely. Ezért az egyes gépeknek a klaszterben nem kell túl nagynak lenniük, csak gyorsan kell tudniuk számolni. Ezért használnak igen sok gyors kisgépet, melyek csak a lebegőpontos számításban jók, más feladatban gyengének bizonyulnának. 22 A párhuzamos feldolgozást végző gépekre igen nehéz megfelelő szoftvert írni. Ezért a FermiLab emberei sem írtak ilyet, hanem maga a rendszer lett úgy megépítve, hogy támogassa a párhuzamosságot. Ezt mutatja be az 13 ábra 13. ábra: Soros Program Párhuzamos Rendszer (SPPS) klaszteren A fizikusoknak csak egy átlagos soros feldolgozást végző programot kellett írniuk, mely elvégzi a kívánt elemzést egyetlen adaton. Ezt az eljárást aztán a FermiLab által kifejlesztett alrendszernek (CPS) a gondjaira. Ez az alrendszer biztosítja, hogy az eljárás sok gépen egyidőben

párhuzamosan fusson. A CPS önmagában egy párhuzamos feldolgozást végző program, mely egy külön erre specializálódott csoport munkája során született. Ennek segítségével az általa táplált soros működésű rész-szoftvereknek már nem kell annyira bonyolultnak lennie. Így ezek megalkotásához már nincs szükség ilyen szintű architektúra-közeli programozói ismeretekre. A bonyolult, párhuzamos, egyszer megírt szoftverek és egyszerű, mások által programozható, soros szoftverek szétválasztásának ezen módja máshol is megjelenik (pl.: adatbázis kezelő rendszerek, tranzakció ellenőrzés). Külön nevet is kapott ez a technika: SPPS – Serial Program Parallel (sub-) System, azaz soros program párhuzamos (al-) rendszeren. Ez a legelterjedtebben használt módszer a nagyléptékű párhuzamos rendszerekben (klaszter, szimmetrikus multiprocesszor, tömegesen párhuzamos rendszer). Gyakorlatilag el lehet így rejteni az átlagos felhasználó elől a

párhuzamos rendszer használatában rejlő nehézségeket. 23 3.14 EGYEDI KOMPAKT KLASZTEREK Az imént említett két klaszter igen eltérő a manapság használatban lévőktől. Ezek a kezdet nagy úttörői voltak! Akkor építettek először nagyteljesítményű munkaállomásokból egy egységet, ezért az összes használt szoftvert maguknak, a rendszerfejlesztőknek kellett megírniuk. Manapság már sokkal egyszerűbb klasztert építeni A különböző feladatokat ellátó szoftvereket is már készen lehet kapni, mint klaszter szintű feladatok elosztásának kezelése, interaktív bejelentkezés és párhuzamosság. A megfelelő rendszeradminisztráció azért még mindig hagy kívánnivalót maga után, hisz egy gépen sokkal egyszerűbb az adminisztrációt elvégezni, mint tíz vagy annál több gépen. A szoftvergyártóknak még van bőven mit javítaniuk az amúgy sem túl bőséges palettájukon klaszter adminisztráció terén. Sokan külön hardver és külön

szoftver elemekből építik meg a saját klaszterüket, de már léteznek polcról levehető, előre összeállított megoldások is. Ezek a csomagban árult klaszterek gyakorlatilag az egyes gyártók legjobb szerverei kisebb módosításokkal. Mindezek mellé külön az adott hardverhez gyártott szoftvereket is adnak. Az így egy egységben vett hardver és szoftver eszközök olcsóbbak (egy minimális darabszám fölött), mintha különkülön gépeket venne az ember. 3.15 TELJES KLASZTER RENDSZEREK Az egybeépített szoftver és hardver elemek vásárlása sem az utolsó lehetőség klaszter építéséhez. Léteznek olyan rendszerek, melyet a gyártójuk a legkisebb építőelemekből aprólékosan rakott össze csak azért, hogy klasztert alkothasson belőlük. Ezek a rendszerek a teljes klaszter összes elemét átfogják és az alapjaiból, jól átgondoltan építik fel. Ilyenre példa a: DEC OpenVMS klasztere [wVMS], IBM System/390 Parallel Sysplex [wPSY] klasztere és a

Tandem Himalaya sorozata [wPTH]. 3.151 DEC OpenVMS klaszter A Digital Equipment Corporation ma OpenVMS-ként ismert klaszterét 1984-ben mutatták be. Ezen rendszer nagy, kicsi, egyprocesszoros, szimmetrikus multiprocesszoros munkaállomások tetszőleges kombinációjából állhat. [Gil96] Az OpenVMS operációs rendszerben beépített támogatás van klaszter rendszer építéshez. Ha csak egy gépes rendszert veszünk OpenVMS-sel, akkor is jelen van ez a támogatás, de csak akkor válik használhatóvá, ha legalább két gépet összekapcsolunk. [wVMS] Az OpenVMS klaszterben a gépek gyakran valamilyen elosztott egységen keresztül kapcsolódnak össze. Ilyen kapcsolat lehet például egy megosztott lemezegység, vagy szalagos egység, melyet mindenki tud kezelni. Ezért szükség van egy olyan egységre, mely felügyeli a kölcsönös kizárást a megosztott egységeken (egyszerre csak egy valaki tudjon vele műveletet végrehajtani). Az OpenVMS szoftvere pont erre való és

ennek a hardveres eszköze a Digital által gyártott Star Coupler (Csillagkapcsoló) és a CI Interconnect. Az OpenVMS klasztereket elosztott egységek nélkül is meg lehet valósítani, ekkor szabványos LAN-on keresztül (Ethernet vagy FDDI) lehet az egységeket összekapcsolni. Az utóbb említettekkel a csomópontok 40 kilométer távolságra is lehetnek egymástól, így jelentősen megnőhet a rendszer katasztrófa elleni védelme. Az összeköttetésnek rendkívül alacsony az overhead-je, azaz az átviteli sávszélességből keveset szán adminisztratív információk (paritás stb.) hozzáadására. 24 A hozzáférési módok tetszőlegesen ötvözhetőek ebben a rendszerben, mint ahogy ez a 14. ábrán is látszódik. A képen néhány munkaállomás, Ethernet-re csatlakozó terminál látható A klaszter csomópontjai CI Interconnect-en és Star Coupler-en keresztül közös, elosztott erőforrásokhoz kapcsolódnak. Ráadásul az egész rendszer kívülről egyetlen

gépnek mutatkozik, ami azt jelenti, hogy amikor bejelentkezik a felhasználó, nem tudja megállapítani hol kapott erőforrást, egészen addig, amíg közvetlenül rá nem kérdez. Éppen ezért az ábrán látható terminálok nem közvetlenül valamely géphez kapcsolódnak, hanem a klaszterhez, mint egészhez. Mikor kiadunk a terminálon egy feladatot, nem tudjuk, hogy az a rendszer mely részén hajtódik majd végre, de ez nem is érdekes, hisz minden gépen, minden feladatnak azonos futtatási körülmény biztosított. Az I/O egységeknek egyedieknek kell lenniük az egész klaszterben az egyértelmű azonosíthatóság miatt. A teljes klaszter egy nagy gép képét mutatja a szoftvertelepítés, az adminisztráció, biztonság és minden más szempontból. 14. ábra: Digital OpenVMS klaszter 25 Az OpenVMS klaszter egy igen sikeres termék volt több szempontból is. Először is nagyon sokat adtak el belőle, több mint 25000 darabot. Ez a klaszter piacon igen nagynak

számított Másodszor a klaszter bonyolultságát egyetlen gép képe mögé rejtő technika továbbterjedt. Ezzel a használata és az SPPS-sel (soros program párhuzamos rendszer) karöltve a programozása is sokkal egyszerűbbé vált. Emellett pedig a Digital Alpha AXP processzor alapú szimmetrikus multiprocesszorok az OpenVMS rendszerrel karöltve akkoriban világelsőkké emelte a Digital-t. 26 3.2 MEMÓRIAKEZELÉS A mai számítógépes architektúrák teljesítményét sokkal inkább a memóriakezelés módszere határozza meg, mintsem a processzor sebessége. Ezért most mi is ezt fogjuk megvizsgálni A processzorok és memóriák között szoros, közvetlen kapcsolatnak kell lennie, mert a processzor az adatait, utasításait és a számításainak eredményét jórészt a memóriában tárolja. A köztük lévő kapcsolatban mostanra komoly probléma alakultak ki, ugyanis a processzorok sebessége messze meghaladja a nagy kapacitású memóriák sebességét. Így a

memória képtelen a processzor nagyszámú információ kéréseinek időben eleget tenni. Sokkal lassabb nála. Egy processzor ciklusra átlagosan 3 memória hozzáférés (kérés) adódik A processzornak minden ciklusában szüksége van új végrehajtandó utasításra, és az utasítás végrehajtása során általában adatot is kér be, vagy visz ki a memóriába. A korszerű memóriakezelő rendszerek virtuális memóriakezelést is végeznek, melynek lényege, hogy a rendelkezésre álló valós fizikai memóriánál nagyobbnak tünteti fel a felhasználható memóriaterületet. Hátránya az, hogy ezt csak úgy képes megoldani, hogy dinamikusan változatja a memóriában lévő adatok pozícióját, azaz a processzor első memória hozzáférésekor nem közvetlenül a kért adatot, utasítást kapja vissza, hanem csak a címet, ahol épp aktuálisan a kívánt információ van. Ezzel az új címmel megint csak a memóriához kell fordulnia. Így az egy lépés helyett

kettőt kell várnia arra, hogy a memória a kért információt szolgáltathassa számára. Mindezek mellett még meg sem említettünk olyan rendszereket, amikben a processzor egyszerre nem csak egy, hanem esetleg több utasítást is képes végrehajtani. Ekkor a processzor és a memória közötti sebesség arány még tragikusabb lesz Szembesültünk egy olyan komoly problémával, ami mellett nem mehetünk el! Valamilyen módon meg kell tudnunk oldani, hogy a processzorunkat ellássuk a szükséges utasításokkal és adatokkal. Hisz nem megengedhető, hogy a processzor kivárja a lassú memória válaszát. Akkor minek vennénk gyors processzort Mi lenne, ha felgyorsítanánk a memóriákat a processzorok sebességére. Ez már egy létező módszer, aminek természetes előnye, hogy a memóriák az előbb említett lassú társaikhoz képest sokkal rövidebb válaszidőre lesznek képesek. Hátránya, hogy az ilyen memóriaegység nagyon drága, és épp ezért csak kis

méretűeket (kis kapacitásúakat) érdemes gyártani belőlük. Ha a magas áruk önmagában még nem lenne kellően zavaró, akkor van még egy sokkal nagyobb problémájuk: mint azt az előbb már kiszámítottuk, egy processzor ciklusra a legoptimálisabb esetben is 3 memória hozzáférés esik. Ez azt jelenti, hogy még az sem elég, ha a memória azonos sebességű a processzorral, hanem annál még legalább háromszor gyorsabbnak kellene lennie. Igen ám, de ha képesek lennének a gyártók a leggyorsabb processzornál háromszor gyorsabb memóriát építeni, akkor a processzort is ugyan azzal a technológiával készítenék, hiszen úgy gyorsabb és ezért versenyképesebb is lenne az. De ekkor megint csak visszakanyarodtunk az azonos sebességű memória és processzor esetére. Így a processzornak megint csak várnia kellene. Tehát, nem oldhatjuk meg a problémát egyedül a memória sebességének növelésével. A megoldás a programok futási jellegzetességének

vizsgálatából adódik. A programok többsége nem összefüggéstelenül, véletlen helyen ír és olvas a memóriában, hanem vagy egy fix területre, vagy egy nagyságrendileg jól megjósolható változó helyzetű fix tartományú memóriaterületre hivatkozik. A jellegzetes fix memóriaterület használata a programok ciklikusságának és a változók fix helyének következménye. Az egyenletesen változó cím, 27 pedig a szekvenciális programfutásból ered. Ezt a sajátosságot használjuk ki a cache memóriánál (gyorsítótár). 3.21 CACHE A cache memória egy kis kapacitású, igen gyors memória, amiben mindig a legutoljára használt néhány adatot és utasítást tároljuk. Ezt a memóriát a processzor és a főmemória közé építjük. Lásd 15-ös ábrát! Arra használjuk, hogy a processzor számára meggyorsítsuk a főmemóriából való adatfelhozatalt. Mikor a processzor a memóriához fordul, akkor a cím alapján történő keresést elsőként a

gyors cache memóriában futtatjuk le, mely találat esetén kis válaszidővel megadja a kért információt. Ha itt nincs találat, akkor kezdünk csak el keresni a lassú főmemóriában. Amikor a főmemóriában megtaláltuk a kívánt információt, akkor azt nem csak a processzornak adjuk át, hanem a cache memóriába is bemásoljuk. Így ha a közeljövőben még egyszer ugyanazt az adatot keresnénk, az már biztosan bent lesz a cacheben. A főmemóriában mindig biztosan megtaláljuk a keresett adatot, vagy utasítást, míg a cache-ben csak valamekkora valószínűséggel. Hisz nem fér el benne a főmemória összes adata egyszerre. Ha tehát a gyors cache memória elég jó szervezésű, akkor nagy a találati aránya, azaz a kérések nagy részében megtalálható benne a keresett adat, és csak ritkán kell a lassú főmemóriához fordulnunk a kiszolgálásért. A találati arány akkor elfogadható, ha az 90% feletti. Ennek segítségével az átlagos adat felhozatali

idő jelentősen lecsökken 15. ábra: A cache memória Mint már említettük a gyors memória mindig drága, a cache-nek pedig gyorsnak kell lennie, ezért nem gazdaságos nagyot építeni belőle. Tehát valamilyen algoritmus, szervezés kell ahhoz, hogy jósolható legyen a cache-be betöltendő és a bent tartandó adatállomány. Ha ezt tökéletesen meg tudjuk oldani, még akkor is csak maximum a processzor sebességét érhetjük el a cache memóriával, és mint ismert, 3 hozzáférést kellene lekezelnünk egy processzor órajel alatt. Valamit még mindig tenni kellene! A legkézenfekvőbb megoldás a következő: legyen három független cache, és a processzor egyszerre tudja kezelni őket! Lásd 16. ábrát! Külön cache-be kerülnek az utasítások, az adatok és a virtuális memória eltolását tároló ofszet-értékek („translation lookaside buffer”). 28 16. ábra: Különböző feladatú cache-ek alkalmazása A gyakorlatban a főmemória és a cache

sebességkülönbsége olyan nagy, hogy egy, a cachebe be nem hozott adat elővétele a főmemóriából megengedhetetlen várakozási időigénnyel járna. Ezt el lehet kerülni a cache méretének drasztikus növelésével, miáltal növekszik a találati arány is. De még így sincs tökéletesen kizárva a hibázás esélye, és egy ponton túl a cache méretének növelése már nem okoz számottevő találati arány növekedést. A megoldás az, hogy beépítünk még egy cache-t a meglévő cache és a főmemória közé. A processzorhoz közelebb esőt elsőszintű cache-nek nevezzük. Ez egy igen kis kapacitású, de nagyon gyors cache. A másikat, – a főmemóriához közelebb esőt – másodszintű cache-nek nevezzük [BW89] Lásd 17. ábrát! A másodszintű cache sebessége valahol a főmemória és az elsőszintű cache között középen van. Ezért ez már egy sokkal olcsóbb memóriafajta, így ebből arányaiban sokkal nagyobb memóriát lehet építeni, mintha a

sima egyszintű cache méretét növeltük volna meg ugyanakkora értékben. Így már nagyobb programok igényeit is kielégítő cache méret áll rendelkezésre. Összegzésként tehát elmondhatjuk, hogy a sebesség a válaszidő miatt, a méret pedig a találati arány magasan tartása miatt kritikus. 17. ábra: Többszintű cache alkalmazása 29 Még nem említettük a gyorsítótárak (cache) működtetésével járó problémákat. Például: mekkora legyen az egyszerre egy csomagban bemásolt adattömb mérete? Hiszen az egyértelmű, hogy nem csak a kért adatot kell bemásolni, hanem annál valamennyivel többet, hogy a következő kérés találati aránya is jobb legyen. Az egyszerre, egy csomagban bemásolandó adatot nevezzük cache sor-nak. Ez a legkisebb egysége a memória és cache közötti útvonalon szállítható adatmennyiségnek. A helyes sor méret kiválasztása nem is olyan egyszerű. A minél nagyobb méret mellett szól az, hogy a programok

utasításai általában egymás után helyezkednek el a memóriában, így egyszerre többet is bemásolhatunk belőlük a cache-be. Ezzel megnöveljük a találat valószínűségét Az ellenérv azonban az, hogy előfordulhat olyan eset, mikor a processzor csak egyetlen egy bájtot használ fel egy bemásolt csomagból, és ekkor feleslegesen töltöttünk időt az egész nagy csomag bemásolásával. Ezért nem egyszerű a megfelelő sorméret meghatározása. Most már értjük az alapjait a cache működésének. Ássunk kicsit mélyebbre! Maga a cache egyszerre több cache sor tárolására képes. Egy cache sor tartalmaz egy főmemória-címet és egy vagy több adattagot. Kereséskor az azonosítás a cím alapján történik A cache csak a számítógép elindulásakor üres, onnantól kezdve mindig csak másolunk bele, és ha már elfogyott az üres hely (sor), akkor valamilyen módon felszabadítunk egy sor-t, de nem többet. Tehát a cache mindig adatokkal van teli A

főmemória nagyon lassú, de nem csak az olvasása, hanem az írása is. Ezért, ha a processzor elvégezte a bekért adaton a számítását, akkor az eredményt átmenetileg csak a cache-be helyezzük el, nem írjuk ki azonnal a főmemóriába annak óriási időigénye miatt. Ennek eredményeként természetes az a szituáció, amikor az azonos címmel rendelkező cache- és memóriasor eltérő adattartalommal rendelkezik. De ez nem okoz fennakadást, mert mikor a processzor legközelebb erről a címről kér adatot, akkor a cache-ben lesz az aktuális érvényes érték. A processzor nem látja azt, hogy a memória ettől eltérő adatot tartalmaz ugyanazon a címen. Lásd 18 ábrát! 30 18. ábra: Egy új cache sor beolvasása és az adat felülírása, majd újra hasznosítása Ha a processzor sokszor hivatkozik egy címre, újra és újra megváltoztatja egyazon adat értékét, akkor jelentős mennyiségű idő megspórolható azzal, hogy nem írjuk ki mindig a

főmemóriába az aktuális értéket. Igaz, így azzal a luxussal élünk, hogy a főmemória tartalma nem lesz érvényes azon az adott címen. A cache bizonyos helyeken már módosított, de a főmemóriában még nem aktualizált adatokat fog tartalmazni (és ez a későbbiekben még sok problémát fog okozni!). Az aktualizálás azonban csak azokra a sorokra fog bekövetkezni, amiknek a helyére új adatokat szeretnénk betölteni, ezért azok helyét fel kell szabadítani a cache-ben. Így a módosítás és az aktualizálás között előre nem megjósolható idő – akár egyetlen ciklus, de akár egy egész hét is eltelhet. Azonban a cache kiürítendő sorát is csak akkor kell visszaírni a főmemóriába, ha annak értéke megváltozott. Ha nincs semmilyen változás, akkor elegendő egyszerűen törölni a bejegyzést a cache-ből. Létezik olyan utasítás is, aminek eredményeként a processzorból kiírandó adat nem csak a cache-be, hanem a főmemóriába is azonnal

beíródik. Ez a keresztülírás (write through) Használatának előnye, hogy azonos marad a két memória tartalma, hátránya, a végrehajtásának időigénye (lassú főmemória). A kiürítendő sor kiválasztására teljesen véletlenszerű Természetesen lehetne olyan intelligens algoritmust használni, mely a cache-ben legrégebben bent lévő sort, vagy rá legrégebben hivatkozottat másolja ki a főmemóriába és szabadítja fel a helyét, de miután a cache több ezer sort képes egyszerre tárolni, ezért nagyon kicsi az esélye annak, hogy a véletlen kiválasztás eredményeként pont a soron következőt, vagy a hamarosan következőt válasszuk ki. Természetesen azért ezt az esetet sem lehet teljesen kizárni 31 Eddig csak egyetlen processzor esetéről beszéltünk, most nézzük meg, mi történik, ha még egy processzort építünk a rendszerbe! Lásd 19. ábrát! 19. ábra: Egy többprocesszoros rendszer cache-el Az első szembetűnő probléma a

közös memória. A főmemóriának képesnek kell lennie egyszerre több processzort is kiszolgálni. Egyszerre több kérés is érkezhet, ezért még lassabb lesz a processzorok adattal való ellátása. A szituáció teljesen reménytelen lenne cache nélkül Ha elég nagyra választjuk a cache méretét, akkor a processzor képes úgy dolgozni, hogy az adatait mindig a cache-ből olvassa és oda is írja. Így nem zavarja, hogy gyakran a másik (többi) processzor használja a főmemóriát. Leszögezhetjük tehát, hogy annál nagyobbra kell választanunk a cache méretét, minél több processzorból állítunk össze egy rendszert. A főmemória terheltségén még így is csökkentenünk kell valamilyen módon. A probléma az, hogy minden kérést ugyanannak a memória egységnek kell megválaszolnia. A kérések forrásának növekedésével arányosan csökken az egy kérőre eső erőforráshányad (csökkenő sávszélesség). Ennek megoldása, ha nem csak egy, hanem több

egységből áll a főmemória Ezek az egységek egy folytonos memóriatérképet adnak. Minden processzor látja őket és képes is kezelni őket. Az előnye, ha a processzorok más-más memória egységet szólítanak meg, akkor egyszerre is ki lehet őket szolgálni, nem kell egymásra várniuk. Lásd 20 ábrát! 20. ábra: Egy többprocesszoros rendszer több főmemória modullal és cache-el A memória-vezérlő gondoskodik a processzorok kiszolgálásáról, ami minden memória modulhoz egyszerre csak egy hozzáférést engedélyez. Ha egyhez több kérés is érkezik egyszerre, akkor azokat csak sorrendben teljesíti. 32 3.211 Cache koherencia Miután sikerült megoldanunk, hogy minden processzor megfelelően kis késleltetéssel, megfelelően nagy sávszélességgel kapja meg az adatokat a rendszerünk még mindig nem üzemképes. Vajon mi lehet még a baj? Mit érünk a teljesítménnyel, ha hibás adatokkal dolgozunk? Hisz nem is olyan rég tárgyaltuk, hogy a

processzor által megváltoztatott adatokat nem rögtön a főmemóriába, hanem csak a cache-be írjuk vissza. A főmemóriába történő visszaírás csak akkor hajtódik végre, ha a cache-ben a kiürítés véletlen kiválasztása pont az adott memóriasorra esik, ami előre nem megjósolható. Így a főmemóriában nagyon sokáig és nagyon sok helyen lehet elavult adat Ez nem probléma mindaddig, amíg csak egy processzorunk van, azonban amint beépítünk még egy processzort, máris komoly gonddal állunk szemben, hisz az új processzor a memóriában lévő adatokról azt feltételezheti, hogy azok mindig aktuálisak. Nem tudhatja, hogy azokat egy másik processzor megváltoztatta, és az aktuális értéküket csak annak cache-e tartalmazza. Ez nem más, mint a cache koherencia probléma. Máris fontossá vált, hogy nyomon kövessük az adatok értékének változását, és valamiképp tudtára adhassuk a processzoroknak, hogy a memóriában lévő egyes értékek már

nem aktuálisak, azokat valamelyik processzor cache-ében kell keresniük. A koherens memóriatérkép még egy, eddig nem említett feltétele az SMP építésének. Ez azt jelenti, hogy nem lehet a rendszerben olyan memória, amit nem tud kezelni az összes processzor. Ennek eredményeként az összes processzornak hozzá kell tudnia férni az összes cache-hez. Vajon milyen esetekben szükséges, hogy a processzorok hozzáférjenek egymás cache memóriájához? Az egyik lehetőség, mikor a processzorok egy alkalmazás futtatását adják át egymás között. Vegyük például azt az esetet, amikor az egyik processzor futtat egy alkalmazást, ami futása során I/O művelet végrehajtását kezdeményezi, így a processzort hosszú ideig, (az I/O művelet végrehajtásáig) munka nélkül hagyná. Az I/O művelet végrehajtásának (előre nem ismert) idejére ez a processzor egy másik alkalmazás futtatásába kezd. Mikor az első alkalmazás I/O művelete végrehajtódik, az

eredeti őt futtató processzor javában dolgozik valamely más alkalmazás végrehajtásán. Egy másik processzor, aki ekkor épp csak pihen, észleli, hogy van egy futásra váró alkalmazás és elkéri azt futtatásra. Ekkor a jelentkező processzornak az összes olyan adatot át kell vennie az első processzor cache-éből, amik a megszakított futású alkalmazás végrehajtásából származnak. Egy másik lehetőség, amikor magát a programot több processzoros gépre, párhuzamos végrehajtásra írták. Ekkor a processzorok egymás közötti kommunikációjának egyetlen lehetősége, ha egymás memóriáját olvassák. Ha nem ezt tennék, akkor az alkalmazások szálai csupán párhuzamosan futtatott, egymástól teljesen független, szimpla programok lennének. 3.212 Cache koherencia problémának megoldásai A cache koherencia problémájának megoldására legegyszerűbbnek a szoftveres megoldás tűnik, mely esetben két új utasítást kell bevezetnünk. Az egyik

hatására a cache egy sora kimásolódik a főmemóriába és kitörlődik a cache-ből. A másik segítségével pedig, 33 egyszerűen csak törlünk egy sort a cache-ből, de nem írjuk vissza a főmemóriába. Ennek a megoldásnak több hátránya is van. Ha az alkalmazás futtatását át kívánjuk tenni az egyik processzorról a másikra, akkor a megfelelő utasításokat minden egyes felhasznált memória sorra ki kell adni. Az utasítás kiadása nem automatikus, hanem a programozóra van bízva, ami – valljuk be – komoly kockázati tényező. Egy másik lehetőség, mikor egy központi címtárban tároljuk minden memória minden adatának címét, azaz az összes processzor összes cache-ének minden sorát, valamint a főmemória adatait. Ebből a tárból – megadva a keresett címet – megtudhatjuk, hogy honnan kell kiolvasnunk a keresett adat legfrissebb aktuális értékét. (Vajon a főmemóriából, vagy esetleg az egyik processzor cache-éből?) Lásd 21.

ábrát! Ennek a keresésnek igen gyorsnak kell lennie, mert minden memóriacím-kérés átfut rajta. A processzorok a kéréseiket nem a memóriához intézik, hanem közvetlenül ehhez a tárhoz. A tár az adatai alapján kiválasztja a keresett forrást, és már szállítja is a kívánt adatot a kezdeményezőnek. Az összes processzor akár egyszerre is kezdeményezhet kérést, hiszen a tár képes őket egyszerre, egymással párhuzamosan is kiszolgálni. 21. ábra: Cache koherencia probléma megoldása központi címtárral Egy másik lehetőség a szimatoló, vagy „snoopy” busz, ami egy üzenetszóró csatornaként a főmemóriát köti össze az összes többi cache-sel. Itt nem egy központi címtár működik, hanem ezen a közös csatornán keresztül értesül mindenki az összes adatmozgásról. Ez a jelenleg legelterjedtebben használt megoldás. [wSNO] A működése a következő: ha valakinek szüksége van valamilyen adatra, akkor a csatornán elkiáltja

magát, „Kinél van X?” ezt mindenki meghallja, és őrülten elkezdi keresni a saját tárjában. A cache-ek természetüknél fogva gyorsabbak a főmemóriánál, ezért, ha valamelyiküknél létezik a saját lokális cache-ben egy példány, akkor biztosan az szól elsőként, hogy megtalálta, és egyben szolgáltatja is az eredményt. Így bizonyos, hogy mindig a legfrissebb verziója lesz felhasználva az adatnak Ha egyetlen cache sem jelez, hogy nála lenne a kért adat, akkor a főmemória fogja szolgáltatni az egyedüli példányt, de ez több időbe telik. Ha azonban egy cache észleli, hogy processzorának kiszolgálása miatt lekéste a választ és a főmemória hibás adattal hamarabb válaszolt nála, akkor egy hibajelzés után azonnal újraküldi az adat helyes változatát. A kérést kezdeményező egység ezt észleli, az első, hibásnak kikiáltott választ eldobja, és csak a másodikat használja fel. Miután minden módosításnak ezen a buszon kell

átfutnia nagyon-nagy a telítettsége 34 A csatorna kihasználtsága javulhat, ha csak azok a módosítások kerülnek rá, melyek több cache-t is érintenek. Ehhez tudni kell, hogy egy adott adat csak egy példányban él-e a cacheek között, vagy van belőle több példány is Ez megoldható egy plusz adattaggal, mely jelzi, hogy kizárólagos példányról, közös, módosított, vagy érvénytelen adatról van szó. Csak akkor kell a közös szimatoló buszt használni, ha közös sor módosításáról van szó. Ellenkező esetben csak a főmemóriában kell az adott sort módosítani. A szimatoló „snoopy” busz egy javítási lehetősége, ha egy kapcsolóval (switch) egészítjük ki. Ekkor a szimatoló busz gondoskodik a cache koherenciáról és az adatszórásról, a kapcsoló pedig az adó és vevő közötti adatátvitelről. Így leválasztható a szimatoló buszról az olyan adatforgalom, mely nem igényli, hogy egy adónál és egy vevőnél több szereplő is

részt vegyen benne. Összességében tehát elmondható, hogy a szimatoló buszon mennek a kérések és a kapcsolón át jönnek a kért adatok. Lásd 22 ábrát! 22. ábra: Cache koherencia probléma megoldása szimatoló busszal és kapcsolóval A kapcsoló képes egyszerre több kérést is párhuzamosan kiszolgálni. Így minél több processzort alkalmazunk, annál nagyobb lesz az össz átviteli sebesség, hiszen egyszerre több kapcsolat létesülhet egyszerre. Ha az SMP-t igazán nagy adatbázisokhoz használják, akkor igen nagy cache kell az adatok megfelelő felhozatalához. Ekkor már a szimatoló busz forgalmának legnagyobb részét a cache-cache adatátvitel fogja okozni. Ez lesz a rendszer átviteli sebességének korlátja is, amire egy lehetséges megoldás, ha több processzor osztozik egy cache-en. Lásd 23 ábrát! Így tehát, ha a processzorok főleg csak egymás (közös cache-ben lévő) adatait használják, a kérések nagy része nem jut ki a szimatoló

buszig. A közös cache fogja kiszolgálja őket Ennek persze megvan a hátránya is: a processzorok a közös cache-használat miatt gyakran várakozni kényszerülnek. Így az egyes processzorok feldolgozási sebessége csökken ugyan, de a teljes rendszeré nő. 35 23. ábra: Processzorok között megosztott cache 36 3.22 CACHE TRÜKKÖK Avagy az SMP helyes működéshez betartandó szabályok! Miután leküzdöttük a processzorok adatokkal való, minden igényt kielégítő ellátottságát, joggal gondolhatjuk, hogy most már hátradőlhetünk és élvezhetjük munkánk gyümölcsét. Pedig sajnos nem így van. A szimmetrikus multiprocesszor processzorai által végrehajtott utasítások egymásutániságára is oda kell figyelnünk. Egy hagyományos, sorosan megírt program utasításai egyprocesszoros rendszerben biztosan sorrendben fognak végrehajtódni. Ugyanezt a programot SMP-n futtatva is biztosak lehetünk a sikerben, ha csak egy processzort vizsgálunk.

Felmerülhet azonban a kérdés, hogy futás közben mindebből mit lát az SMP egy másik processzora? Ha nem történik semmilyen rendellenesség, akkor teljesen szabályos futást. Még azok a futásban észlelhető egyenetlenségek (akadozások, várakozások) sem okoznak problémát, amik például memória laphiba, vagy valamely egységre történő várakozás miatt alakulnak ki. Ellenben amit mindenképpen meg kell oldani, az az, hogy a rendszer összes processzora utasítás sorrendhelyes végrehajtásként érzékelje a futást. Semmiképp sem fordulhat elő, hogy valaki az utasítások végrehajtása során azok felcserélődését érzékelhesse. További megoldásra váró feladat még a közösen használt adatokra a kölcsönös kizárás biztosítása. Ez azt jelenti, hogy egy adatot egy időben csak egy processzor változtathat meg Hatalmas káosz alakulhatna ki, ha mindenki akkor férhetne hozzá egy adathoz, amikor csak akarna. Szabály, hogy az erőforrásért való

versengésnek mindig van győztese, mindig csak egy győztese van, és előbb-utóbb mindenki sorra kerül. Ha a fenti két szabályt betartjuk, akkor egy kis trükk segítségével még nagyobb teljesítményt tudunk előcsalni a rendszerünkből. Ugyanis van két utasítás, melyek gátolják a processzor futását és melyeknek végrehajtási idejét egyetlen processzorral sem lehet felgyorsítani, ezek a letárolás (store) és a betöltés (load). Mikor a végrehajtás ezek valamelyikéhez ér, akkor a processzor kénytelen memóriaműveletet végrehajtani, mely alatt nem tud más hasznos tevékenységet végezni. Természetesen a betöltés nem odázható el, hiszen ez valamely soron következő művelet végrehajtásának előfeltétele, mely majd hivatkozni fog rá. De mi a helyzet a letárolással? E művelet végrehajtásának késleltetése nem okoz problémát mindaddig, amíg a tárolni kívánt adatot nem akarjuk ismét beolvasni. Ezért a letárolási utasításokat egy

külön listába gyűjtjük addig, míg a processzor már nem használja a memóriát (hasznos számítást végez) és akkor a processzortól függetlenül automatizálva kiírjuk az adatokat a cache-be. Ennek segítségével a programkód gyorsabban végrehajtható. Míg kívülről nem látni különbséget. 37 3.3 KLASZTER ARCHITEKTÚRÁK A rendszer több független számítógépből épül fel, melyek egy kommunikációs alrendszeren keresztül vannak összekötve. Ezt az összekapcsolást többféle topológiával is meg lehet valósítani. Ilyenek a hierarchikus busz, fa, hiperkocka, pillangó, gyűrű, háló, tórusz, teljes crossbar, virtuális crossbar (ilyen az Internet is). A kommunikációs rendszerek csoportosítására lehetőség a kommunikációs csatorna típusa szerinti felosztás. Milyen eszközt használunk a csomópontok közötti kommunikációhoz Egy másik szempont a kommunikáció fontossága, intenzitása szerinti csoportosítás. Csak kevés, kis

méretű adatot szeretnénk-e továbbítani, vagy gyakori, esetleg nagyméretű adatforgalomra kell-e számítani. 24. ábra: A klaszter architektúrák összehasonlítása 38 Tehát a csomópontok összekapcsolódásának típusa szerint megkülönböztetünk I/O csatolt és Memória csatolt klasztereket. Az I/O csatolás egyszerűbb, szabványos összeköttetést valósít meg, a független rendszereknek nem kell egymást túlzottan „ismerniük”, elég csak a közös I/O felületet. Éppen ezért ezt könnyebb megvalósítani. Ez az egyetlen lehetőség, hogy heterogén gépekből állítsunk össze egy klasztert. A kapcsolat kezeléséért általában az operációs rendszer a felelős Természetesen így kisebb az elérhető sávszélesség. Ha hiba lép fel a rendszer egy gépében, akkor kisebb a valószínűsége a hiba továbbterjedésének. A memória csatolás memória buszokat köt össze. Ez jóval nehezebb feladat, de nagyobb lesz az elérhető teljesítmény,

sávszélesség. Ennek megvalósításához a rendszerbusz teljes működésével tisztában kell lenni, és a rajta folyó kommunikációba kell tudni becsatlakozni. Ezért itt mélyebb szintű rendszer ismeretre van szükség egy új csomópont beillesztéséhez. Miután az egyes csomópontok a rendszerbuszukon át kommunikálnak egymással, nem térhetnek el jelentősen egymástól működésükben. A kommunikációt a processzor végzi load és store (tárolás, betöltés) utasításokkal. A rendszerbusz ezeket tudja fogadni és továbbküldeni. Különleges szoftvert és hardvert (speciális architektúra) igényel A memória kezelése kritikus az egész rendszer szempontjából (pl.: hozzáférés védelme, szegmentálás, virtuális memóriakezelés, cache). A felosztás másik szempontja a csomópontok közötti kommunikáció mikéntje. Ez lehet Üzenet alapú és Közös erőforrás alapú. Az üzenet alapú kommunikáció platform függetlenséget biztosít. Nem szükséges

minden gépnek, minden operációs rendszernek azonosnak lennie. Ez hatalmas nagy előny! Elég értelmezni tudni egymás üzeneteit, reagálni rájuk, és persze szükség esetén választ küldeni. Az üzenetek a csomópontokhoz egy várakozási sorba (FIFO) érkeznek meg, és onnan kerülnek feldolgozásra. Így, ha azonnal nem is képes a csomópont feldolgozni a bejövő üzenetet, attól még nem vész el, csak várakozik. Az üzenet alapú kommunikációnál nincs cache probléma, nem is lehet. A rendszerek nem kapcsolódnak annyira szorosan egymáshoz Ez a módszer jól használható például, ha az egyes csomópontok bizonyos események bekövetkeztéről szeretnék egymást tájékoztatni. Jól skálázható Közös erőforrás (memória, megosztott meghajtó) használata esetén a használt adatok nagyobb hatékonysággal oszthatóak meg, ha egy adatra mindenkinek szüksége van, akkor nem kell mindenkinek elküldeni, csak a címet, ahol mindenki elérheti szükség

esetén. A közösen használt adatokat a közös erőforrásra másolják, így már mindenki elérheti. Ebben az esetben már figyelni kell a cache problémára, mert nem biztos, hogy az utolsó érvényes változat van lokálisan letárolva. Ezt ellenőrizni kell felhasználás előtt A közös erőforráshoz való hozzáférésnél pedig a kölcsönös kizárásra kell figyelmet fordítani. Egyszerre csak egyvalaki tudjon módosítani a közös tárban. Épp ezért a versengési helyzetet is fel kell tudni oldani valamilyen módon. Ez az eljárás a megszokottabb, könnyebben programozható Az általánosításokat a konkrét felosztásunkra levetítve: I/O csatolt, üzenet alapú kommunikáció esetén (24. ábra bal felső része) nincs cache koherencia probléma (üzenet alapú kommunikáció miatt), nincs kölcsönös kizárásra szükség (I/O miatt). Ilyenek a leggyakoribb, legegyszerűbb klaszterek. Ezek egy egyszerű LAN-al vannak összekötve Így a kommunikációs

rendszer nem lesz nagyon gyors, de jól elszeparáltak egymástól az egyes csomópontok és a megvalósítás sem túl bonyolult. 39 I/O csatolt, közös erőforrásos esetben (24. ábra jobb felső része) leggyakrabban a közös erőforrás egy megosztott diszk. Ekkor a diszk vezérlője két, vagy több helyről is elfogad utasításokat. Ilyen például a DEC OpenVMS Claster-je és az IBM Sysplex-je [wIPS] Ekkor viszont már fontos kezelni az egyes lemezterületek (szegmensek) tulajdonosi jogait és a kölcsönös kizárást is a biztonság miatt. Memória csatolt, közös erőforrás esetén (24. ábra jobb alsó része) két különböző módszert különböztetünk meg. Az egyikben a közös erőforrás a klaszter minden elemében megtalálható. Például mindenhol van egy megosztott kis diszk A másik lehetőség, hogy a megosztott erőforrás egy független csomópontban van, és mindenki hozzá fordul, ha elosztott adatokhoz akar hozzáférni. Ilyen például a DEC

„Memory Channel” [wDMC] technikája és az IBM POWER/4 RPQ-ja. Memória csatolt, üzenet alapú esetben (24. ábra bal alsó része) nincs konkrét, fizikailag megvalósított architektúra. Csak szoftveresen emulált létezik Kivételt jelenthet, ha a DEC „Memory Channel”-je, ha a csatornát csak üzenettovábbításra alkalmazzuk. Ennek előnye a kis adminisztrációs igény, és, hogy nem kell a cache koherencia probléma miatt aggódnunk. 40 4. IRODALOM JEGYZÉK [BBK68] George H. Barnes, Richard M Brown, Maso Kato, David J Kuck, Daniel L Slotnick, and Richard A. Stokes The ILLIAC IV computer 1968 [BGN62] A.W Burke, H H Goldstine, and J von Neumann: Preliminary dicsussion of the logical design os an electronic compting instrunemt 1962 [BW89] J. L Bear and W H Wang Multilevel cache hierarchies: Organizations, protocols and performance. Jurnal of Parallel and Distributed Computing 1989 [Gil96] R. Gillett Memory channel network for PCI: An Optimized Cluster Interconnect

IEEE Micro 1996 [wCLA] http://www.clustercomporg [wDBK] http://www.ebetcomcom/deep-blue-kasparovhtm [wDMC] http://www.hpcom/techservers/systems/symchtml [wFNL] http://www.fnalgov [wIPS] http://www-1.ibmcom/servers/eserver/zseries/pso [wNUM] http://lse.sourceforgenet/numa/faq/indexhtml [wPSY] http://www.discoveryvipcom/Courseware/OS390/Parallel Sysplex OS390asp [wPTH] http://www.aprilse/english/tandemasp [wRIN] http://www.lofarorg/archive/presentations/CCGrid2001pdf [wSNO] http://www.csberkeleyedu/~randy/Courses/CS252S96/Lecture30pdf [wVMS] http://www2.hmcedu/www common/ovms073/indexhtml [wWSE] http://www.csumdedu/Library/TRs/CS-TR-4516/CS-TR-4516pdf 41