Ugrás a tartalomhoz

Algoritmikus váz

Ellenőrzött
A Wikipédiából, a szabad enciklopédiából

A számítástechnikában az algoritmikus váz magas szintű programozási sablont jelent a párhuzamos és elosztott számításokhoz.

Az algoritmikus vázak alkalmazzák a kollektív programozási mintapéldányokat azért, hogy leplezzék a párhuzamos és elosztott működtetések nehézségét. A kulcsponti mintakészletből (vázakból) bonyolultabb minták gyárthatók az alapminták összevonásával.

Áttekintés

[szerkesztés]

Az algoritmikus vázak legfigyelemfelkeltőbb paramétere, mely különbséget tesz köztük és a többi magas szintű párhuzamos programozási modell között, hogy a párhuzamos cselekvések összehangolását rejtett módon a vázminták determinálják. A fejlesztőknek nem feladata, az applikációk szekvenciáinak összehangolása. Két következménye van: Mindenek előtt, mivel a konzultációs példák előzetesen ismertek, költségmodellek applikálhatók a vázprogramok időzítésére. Másodízben, az algoritmikus vázprogramozás a tévedések gyakoriságát mérsékeli a szokványos elvárt szinttől alacsonyabb párhuzamos programozási modellekhez (Threads, MPI) viszonyítva.

Példaprogramok

[szerkesztés]

A következő példa a Java Skandium könyvtár mintájára épül párhuzamos fejlesztéshez.

A végcél a QuickSort műveletsor algoritmikusváz-eredetű párhuzamos verziójának megvalósítása a Divide and Conquer mintával. Vegyük figyelembe, hogy a magas szintű megközelítés elrejti a szálkezelést a programozó elől. 

// 1. Define the skeleton program
Skeleton<Range, Range> sort =   new DaC<Range, Range>(
    new ShouldSplit(threshold, maxTimes),
    new SplitList(),
    new Sort(),
    new MergeList());
		
// 2. Input parameters
Future<Range> future = sort.input(new Range(generate(...)));
	
// 3. Do something else here.
// ...
	
// 4. Block for the results
Range result = future.get();
  1. Az első lépés az algoritmikus váz definiálása a mintának megfelelő kóddal (ShouldSplit, SplitList, Sort, MergeList). A végső kód párhuzamossági gondok nélkül lesz így megírva.
  2. A második lépés a számítást elindító adatok bevitele. Ebben az esetben a Range egy tömböt és két indexet tartalmazó osztály, amelyek lehetővé teszik az alrész ábrázolását. A keretrendszerbe bevitt minden adat számára egy új Future objektum jön létre. Egynél több Future is megadható egyidőben a vázba.
  3. A Future lehetővé teszi az aszinkron számítást, így több feladatot is el lehet végezni az eredmény számítása közben.
  4. Megkaphatjuk a számítás eredményét, végezhetünk blokkolást szükség szerint (vagyis az eredmények még nem állnak rendelkezésre).

A példában szereplő funkcionális kódok négy típusnak felelnek meg: Condition (feltétel), Split (felosztás), Execute (futtatás, végrehajtás) és Merge (összefésülés, egyesítés).

public class ShouldSplit implements Condition<Range>{

  int threshold, maxTimes, times;
  
  public ShouldSplit(int threshold, int maxTimes){
    this.threshold = threshold;
    this.maxTimes  = maxTimes;
    this.times     = 0;
  }
	
  @Override
  public synchronized boolean condition(Range r){
    return r.right - r.left > threshold &&
    	   times++ < this.maxTimes;
  }
}

A ShouldSplit osztály a Condition interface-t alkotja meg. A függvényhez hozzárendelnek egy bemeneti részt, ebben az esetben az r tartományt, és igaz vagy hamis értéket kapunk meg. A Divide and Conquer szövegkörnyezetben, ahol ezt a függvényt használni fogják, ez eldönti, hogy egy altömböt újra fel kell-e osztani vagy sem. A SplitList osztály a Split interface-t valósítja meg, amely ebben az esetben egy (al)tömböt kisebb résztömbökre oszt. Az osztály egy segítő partition(...) függvényt használ, amely megvalósítja a jól ismert QuickSort pivot és swap sémát.

public class SplitList implements Split<Range, Range>{

 @Override
 public Range[] split(Range r){
        
    int i = partition(r.array, r.left, r.right);
        
    Range[] intervals = {new Range(r.array, r.left, i-1), 
                         new Range(r.array, i+1, r.right)};
        
    return intervals;
 }
}

A Sort osztály megvalósítja és végrehajtja az interface-t, és felelős az r tartomány által megadott résztömb rendezéséért. Ebben az esetben egyszerűen meghívjuk a Java alapértelmezett (Arrays.sort) módszerét az adott altömbhöz.

public class Sort implements Execute<Range, Range> {

  @Override
  public Range execute(Range r){
		
    if (r.right <= r.left) return r;
		
    Arrays.sort(r.array, r.left, r.right+1);
		
    return r;
  }
}

Végül, ha az altömbök halmaza rendeződik, akkor az altömb részeit egy nagyobb tömbbe egyesítjük a MergeList osztállyal, amely Merge felületet hoz létre.

public class MergeList implements Merge<Range, Range>{

  @Override
  public Range merge(Range[] r){
		
    Range result = new Range(r[0].array, r[0].left, r[1].right);
		
    return result;
  }
}

Keretrendszerek és könyvtárak

[szerkesztés]

ASSIST

[szerkesztés]

Az ASSIST egy programozási közeg, amely strukturált koordinációs nyelvet biztosít a programozók számára. A koordinációs nyelv kifejezheti a párhuzamos programokat a szoftver modulok tetszőleges grafikonjaként. A moduldiagram leírja, hogy egy modulkészlet hogyan hat egymással a jellemezett adatfolyamok segítségével. A modulok lehetnek szekvenciálisak vagy párhuzamosak. A szekvenciális modulok C, C++ vagy Fortran nyelven írhatók; és a párhuzamos modulokat egy sajátos ASSIST párhuzamos modullal (parmod) programozhatjuk

AdHoc, rangsorolt és hibatűrő elosztó megosztott memória (DSM) rendszert használnak az adatfolyamok összekapcsolására a feldolgozó elemek között azáltal, hogy egy tárolót biztosítanak: kapni/ tenni / eltávolítani / alkalmazni műveletekkel. Az AdHoc körüli kutatások az adatraktár átláthatóságára, méretezhetőségére és hibatűrésére összpontosítottak

Noha nem halhatatlan vázkeret, abban az értelemben, hogy nincsenek vázak, az ASSIST általános parmodja olyan jellegzetes vázakra specializálható, mint például: farm, térkép stb. Ez pedig a felhasznált erőforrások számának dinamikus adaptálásával valósítható meg.

CO2P3S

[szerkesztés]

A CO2P3S (Correct Object-Oriented Pattern-based Parallel Programming System) egy mintázatorientált fejlesztői környezet,[1] amely a Java szálainak felhasználásával éri el a párhuzamosságot.

A CO2P3S egy párhuzamos applikáció maradéktalan korszerűsítési folyamatával foglalkozik. A programozók egy programozási grafikus felületen keresztül lépnek kapcsolatba a minta és annak konfigurációs opcióinak kiválasztásával. Ezután a programozók kitöltik a mintához szükséges kampókat, és egy új kód jön létre a Java keretrendszerében az alkalmazás párhuzamos végrehajtásához. A létrehozott keretrendszer három szintet használ, az elvonatkoztatás csökkenő sorrendjében: mintaréteg, köztes kódréteg és natív kódréteg. Így a fejlett programozók több szinten is beavatkozhatnak a létrehozott kódba alkalmazásaik teljesítményének hangolása érdekében. A generált kód többnyire biztonságos, a programozó által biztosított típusok használatával, amelyek nem igénylik a szuperosztály kiterjesztését, de nem teljesen típusbiztonságosak, mint például a hálóminta redukciós (..., Object reducer) módszerében.

A CO2P3S-ben támogatott minták összessége eleget tesz a metódussorrendnek, az elosztónak, a hálónak és a hullámfrontnak. A sokrétű alkalmazások úgy építhetők fel, hogy kereteket állítanak össze tárgy-referenciáikkal. Mindazonáltal, ha egyetlen minta sem megfelelő, a MetaCO2P3S grafikus eszköz a bővíthetőséggel foglalkozik, lehetővé téve a programozók számára, hogy módosítsák a minták tervét és új mintákat vezessenek be a CO2P3S-be.

A szétosztott memória struktúráinak finanszírozása később került bevezetésre a CO2P3S-ben. Elosztott memória minta használatához a programozóknak meg kell változtatniuk a minta memória opcióját megosztottról megosztottra, és elő kell állítaniuk az új kódot. A használat szempontjából a kód elosztott memóriájú verziója távoli kivételek kezelését igényli.

Calcium és Skandium

[szerkesztés]

A Calcium fő motivációi a Lithium és a Muskel volt. Mint ilyen, algoritmikusváz-programozást biztosít Java könyvtárként. Mind a feladat, mind az adatpárhuzamos vázak teljesen beágyazhatók; és paraméteres vázobjektumokon keresztül, nem pedig öröklődés útján példázzák.

A Calcium nagyban hozzájárul a vázprogramok kivitelezéséhez a ProActive közegre épülve a szétosztott fürtre hajazó kiépítettséghez. Ezenkívül a kalciumnak három megkülönböztető jellemzője van az algoritmikusváz-programozáshoz. Először egy teljesítményhangoló modell, amely segít a programozóknak azonosítani a teljesítményhibákért felelős kódot.[2] Másodszor, egy olyan típusú rendszer a beágyazható vázak számára, amely bizonyítottan garantálja az alanyok csökkentési tulajdonságait, és a Java Generics segítségével valósul meg.[3] Harmadszor, egy átlátszó algoritmikus vázfájlhozzáférési modell, amely lehetővé teszi a vázakat adatigényes alkalmazásokhoz.[4]

A Skandium a calciumnak hiánytalan újra installálása a többmagos számításhoz. A Skandiumra írt programok kihasználhatják a megosztott memóriát a párhuzamos programozás egyszerűsítése érdekében.[5]

Eden

[szerkesztés]

Az Eden [6] egy párhuzamos fejlesztői lingua a megfelezett memóriahelyek részére, mely által szétbontódik a Haskell. A metódusokat célzatosan determináljuk a párhuzamos fejlesztés érdekében, miközben kommunikációjuk implicit marad. A folyamatok egyirányú csatornákon keresztül kommunikálnak, amelyek egy írót pontosan egy olvasóhoz kötnek. A programozóknak csak meg kell adniuk, hogy a folyamat mely adatoktól függ. Eden folyamatmodellje közvetlen irányítást biztosít a folyamat részletessége, az adatelosztás és a kommunikációs topológia felett.

Az Eden nem mondható vázidiómának átvitt értelemben, ugyanis a vázak nem nyújtanak nyelvi konstrukciókat. Ellenben a vázakat az Eden alacsonyabb szintű procedúra elvonatkoztatásának tetőpontján definiálják, szponzorálva a tevékenység és adatok párhuzamosságát egyaránt. Ennek okán, ellenben a legtöbb más megközelítéssel, Eden hagyja, hogy a vázak ugyanazon a nyelven és ugyanazon a szinten legyenek meghatározva, a váz példánya meg van írva: maga Éden. Mivel az Eden egy funkcionális nyelv kiterjesztése, az Eden vázak magasabb rendű funkciók. Eden bevezeti a megvalósítási váz fogalmát, amely egy architektúrától független séma, amely egy algoritmikus váz párhuzamos megvalósítását írja le.

eSkel

[szerkesztés]

Az Edinburgh-i váz Könyvtár (eSkel) C-ben íródott, és az MPI-re épül. Az eSkel első verzióját itt írták le,[7] míg egy későbbi verziót itt mutatják be.[8]

[9] A vázak értelmezése beágyazási és interakciós módban határozták meg. A beágyazási metódus megeshet ideiglenesen vagy hosszútávon, míg az interakciós mód lehet közvetett vagy közvetlen. Az ideiglenes beágyazás azt jelenti, hogy a beépült váz minden egyes meghívásakor látványos lesz, és utána darabokra hull, míg az időtálló azt, hogy a vázat egy alkalommal létrehozzák, és ugyanazon vázpéldányt hívják meg az alkalmazás során. Az implicit kölcsönhatás azt jelenti, hogy a vázak közötti adatáramlást teljesen meghatározza a vázösszetétel, míg az explicit azt jelenti, hogy az adatok a vázösszetétel által nem meghatározott módon generálhatók vagy távolíthatók el az áramlásból. Például egy váz, amely kimenetet állít elő anélkül, hogy valaha is bemenetet kapna, kifejezetten kölcsönhatásba lép.

Az ütemterv és kapacitás megbecsülése, mindenekelőtt a csatornák teljesítményének előrejelzését Benoit és mtsai.[10][11][12][13] Minden egyes leképezéshez rendelkezésre bocsátottak egy teljesítménymodellt, a folyamat algebra alapján, és a modell eredményei alapján meghatározták a legjobb ütemezési stratégiát.

Modernebb tevékenységek vesződtek a strukturált párhuzamos programozás adaptációjának problémájával ,[14] különös tekintettel a csővázra.[15][16]

FastFlow

[szerkesztés]

A FastFlow egy váz-párhuzamos fejlesztési keretszerkezete, amely egyenesen a streamelés és az információ-párhuzamos programok korszerűsítésére irányul. Eleinte a többmagos weboldalak megpályázására generáltál ki, majd kibővítették az eltérő weboldalakra, amelyek elosztott memória weboldalak csoportjaiból épülnek fel, esetleg számítógépes gyorsítókkal, például NVidia GPGPU-kkal, Xeon Phivel, Tilera TILE64-gyel. A FastFlow fő tervezési filozófiája, hogy megfelelő párhuzamos programozási absztrakciókkal és gondosan megtervezett futásidejű támogatással nyújtsa az alkalmazás-tervezőknek a párhuzamos programozás kulcsfontosságú jellemzőit (pl. Piacra jutási idő, hordozhatóság, hatékonyság és teljesítmény-hordozhatóság). A FastFlow egy általános célú C++ programozási keretrendszer heterogén párhuzamos platformokhoz. A többi magas szintű programozási kerethez hasonlóan, mint például az Intel TBB és az OpenMP, ez is egyszerűsíti a hordozható párhuzamos alkalmazások tervezését és tervezését. Mindazonáltal egyértelmű előnnyel rendelkezik az expresszivitás és a teljesítmény tekintetében a többi párhuzamos programozási keretrendszerrel szemben, speciális alkalmazási szcenáriókban, ideértve többek között: finomszemcsés párhuzamosság gyorsítótár-koherens megosztott memória platformokon; Streaming alkalmazások; többmagos és gyorsítók együttes használata. Más esetekben a FastFlow általában összehasonlítható (és néhány esetben valamivel gyorsabb is) a korszerű párhuzamos programozási keretekkel, mint például az Intel TBB, az OpenMP, a Cilk stb.[17]

HDC

[szerkesztés]

A Higher-order Divide and Conquer (HDC) [18] a Haskell működésbeli idióma részhalmaza. A működésbeli terveket sokalakú, feljebb való függvényekként szemléltet, amelyek összekombinálhatók C / MPI-be, és összekapcsolhatók a váz megvalósításával. A nyelv a divide and conquer paradigmára összpontosít, és a divide and conquer váz általános jellegéből kiindulva konkrétabb megoldásokat eredményeznek hatékony megvalósítással. A konkrét esetek a következőknek felelnek meg: rögzített rekurziós mélység, állandó rekurziós fok, többszörös blokk rekurzió, elemenkénti műveletek és megfelelő kommunikáció [19]

A HDC kivételes odafigyelést fektet a mellékhatások jól kidolgozottságára és annak kötődésére a megközelíthető CPU-k mennyiségével. A processzorok teljes száma kulcsfontosságú paraméter a vázprogram teljesítményében, mivel a HDC arra törekszik, hogy megbecsülje a processzorok megfelelő hozzárendelését a program minden részéhez. Így az alkalmazás teljesítménye szorosan kapcsolódik a processzorok becsült számához, amely vagy meghaladja az alproblémák számát, vagy pedig nincs elég párhuzamosság a rendelkezésre álló processzorok kihasználásához.

HOC-SA

[szerkesztés]

A HOC-SA egy Globus inkubátor projekt. A HOC-SA a Higher Order Components-Service Architecture abbreviációja. A magasabb rendű alkatrészek (HOC) célja a Grid alkalmazás fejlesztésének egyszerűsítése. A HOC-SA célja, hogy olyan Globus felhasználóknak, akik nem akarnak tudni a Globus köztes szoftver minden részletéről (GRAM RSL dokumentumok, webszolgáltatások, erőforrás-konfiguráció stb.), Olyan HOC-kat biztosítsanak, amelyek magasabb szintű interfészt biztosítanak a rács, mint az alap Globus Toolkit. A HOC-k Grid-kompatibilis vázak, amelyeket a Globus Toolkit tetején komponensként valósítanak meg, távolról elérhető módon a Web Services segítségével.[20]

JaSkel

[szerkesztés]

A JaSkel [21] egy Java alapú vázkeret, amely olyan vázakat biztosít, mint a farm, a pipe és a heartbeat. A vázak szakterülete az öröklés. A programozók az abszolút módszereket az egyes vázakra alkalmazzák, hogy megadják alkalmazás-specifikus kódjukat. A JaSkel vázai szekvenciális, egyidejű és dinamikus változatban egyaránt rendelkezésre állnak. Például az egyidejű farm használható megosztott memóriakörnyezetekben (szálak), de nem elosztott környezetekben (fürtök), ahol az elosztott farmot kell használni. Az egyik verzióról a másikra való váltáshoz a programozóknak meg kell változtatniuk osztályuk aláírását, hogy egy másik vázból származzanak. A vázak beágyazása az alap Java Object osztályt használja, ezért a vázkompozíció során semmilyen típusú rendszert nem hajtanak végre.

A számítás elosztási szempontjait a JaSkel kezeli az AOP, pontosabban az AspectJ megvalósítás segítségével. Így a JaSkel telepíthető mind a fürtön, mind a Grid-szerű infrastruktúrákon.[22] Ennek ellenére a JaSkel megközelítés hátránya, hogy a váz beágyazása szigorúan a telepítési infrastruktúrához kapcsolódik. Így a gazdaság kettős beágyazása jobb teljesítményt nyújt, mint egyetlen farm hierarchikus infrastruktúrán. Ez kiküszöböli az AOP használatának célját a vázprogram eloszlásának és funkcionális problémáinak elkülönítésére.

Lithium & Muskel

[szerkesztés]

A Lithium [23][24][25] és az utódja, a Muskel az olaszországi Pisai Egyetemen kifejlesztett vázkeret. Mindkettő beágyazható vázakat biztosít a programozó számára Java könyvtárként. A vázalkalmazás értékelése az operatív szemantika hivatalos meghatározását követi, amelyet Aldinucci és Danelutto vezetett be [26][27] amely képes kezelni a feladatok és az adatok párhuzamosságát is. A szemantika a váznyelv funkcionális és párhuzamos viselkedését egyaránt jelöli átmeneti rendszer segítségével. Ezenkívül számos teljesítményoptimalizálást alkalmaznak, mint például: vázátírási technikák [18, 10], feladat-keresés és szerver-szerver lusta kötés.[28]

A megvalósítás szintjén a lithium a makro-adatáramlást [29][30] ki a párhuzamosság elérése érdekében. Amikor a bemeneti adatfolyam új paramétert kap, a vázprogramot feldolgozzuk makro-adatfolyam grafikon előállításához. A grafikon csomópontjai makro-adatfolyam utasítások (MDFi), amelyek a programozó által biztosított szekvenciális kódrészleteket képviselik. A feladatokat több MDFi csoportosítására használják, és a tétlen feldolgozási elemek fogyasztják a feladatkészletből. Amikor a grafikon kiszámítása befejeződött, az eredmény a kimeneti adatfolyamba kerül, és így visszakerül a felhasználóhoz.

A Muskel nem funkcionális szolgáltatásokat is nyújt, mint például a szolgáltatásminőség (QoS);[31] biztonság a feladatkészlet és a tolmácsok között;[32][33] és erőforrás-felderítés, terheléselosztás és hibatűrés a Java / Jini Párhuzamos Keretrendszerrel (JJPF) való összekapcsoláskor,[34] elosztott végrehajtási keretrendszer. A Muskel támogatást nyújt a strukturált és a strukturálatlan programozás kombinálásához is [35] és a legújabb kutatások a bővíthetőséggel foglalkoztak.[36]

Mallba

[szerkesztés]

A Mallba [37] egy kombinatorikus optimalizálási könyvtár, amely pontos, heurisztikus és hibrid keresési stratégiákat támogat.[38] Minden stratégia a Mallba-ban általános vázként valósul meg, amelyet a szükséges kód megadásával lehet használni. A pontos keresési algoritmusokon a Mallba ághoz kötött és dinamikus optimalizáló vázakat biztosít. A helyi keresési heurisztikához a Mallba támogatja: hegymászás, metropolisz, szimulált izzítás és tabu keresés; és az evolúciós algoritmusokból, például genetikai algoritmusokból, evolúciós stratégiából és másokból (CHC) származó populációalapú heurisztikák is. A hibrid vázak olyan stratégiákat ötvöznek, mint: a GASA, a genetikai algoritmus és a szimulált hőkezelés keveréke, valamint a CHCCES, amely egyesíti a CHC-t és az ES-t.

A vázak C++ könyvtárként vannak ellátva, és nem beágyazhatók, de típusbiztosak. Egyéni MPI absztrakciós réteget használnak, a NetStream-et, amely gondoskodik a primitív adattípusok rendezéséről, szinkronizálásáról stb. A váznak lehet több alacsonyabb szintű párhuzamos megvalósítása a cél architektúrától függően: szekvenciális, LAN és WAN. Például: központosított master-slave, elosztott master-slave stb.

Mallba olyan állapotváltozókat is kínál, amelyek megtartják a keresési váz állapotát. Az állam összeköti a keresést a környezettel, és hozzáférhető ahhoz, hogy megvizsgálja a keresés alakulását és eldöntse a jövőbeni intézkedéseket. Például az állapot felhasználható az eddig talált legjobb megoldás, vagy az elágazó és kötött metszés α, β értékeinek tárolására.[39]

A többi keretrendszerhez képest a Mallba vázkoncepcióinak használata egyedülálló. A vázak paraméteres keresési stratégiák, nem pedig paraméteres párhuzamosítási minták.

Marrow

[szerkesztés]

A Marrow [40][41] egy C++ algoritmikus vázkeret az OpenCL-számítások hangszereléséhez, esetleg heterogén, multi-GPU környezetekben. Mind a feladat-, mind az adatpárhuzamos vázakat biztosítja, amelyek beágyazás útján összetett számítások készítéséhez állíthatók össze. Az eredményül kapott kompozíciós fák levélcsomópontjai a GPU számítási magjait képviselik, míg a többi csomópont a beágyazott részfára alkalmazott vázat jelöli. A keretrendszer magára vállalja a fák heterogén multi-GPU környezetekben történő helyes végrehajtásához szükséges teljes gazdagépoldali hangszerelést, ideértve az adatátvitel és a végrehajtási kérelmek megfelelő rendezését, valamint a fa csomópontjai közötti kommunikációt.

A Marrow legjobban megkülönböztethető tulajdonságai közé tartozik a GPU kontextusában korábban nem elérhető vázak, mint például a Pipeline és a Loop, valamint a váz beágyazási képessége – ez a funkció ebben az összefüggésben szintén újdonság. Ezenkívül a keretrendszer olyan optimalizálásokat vezet be, amelyek átfedik a kommunikációt és a számítást, így elfedik a PCIe busz által előidézett késleltetést.

A Marrow összetételű fa több GPU általi párhuzamos végrehajtása egy adat-párhuzamos lebontási stratégiát követ, amely egyidejűleg alkalmazza a teljes számítási fát a bemeneti adatkészlet különböző partícióira. A programozó teljesen kivonul az alapul szolgáló multi-GPU architektúrától azon kívül, hogy kifejtené, mely kernelparaméterek bonthatók, és szükség esetén meghatározhatja a részeredmények egyesítésének módját.

További információk, valamint a forráskód megtalálható a Marrow weboldalon

Muesli

[szerkesztés]

A Muenster Skeleton Library Muesli [42][43] egy C++-sablonkönyvtár, amely újra megvalósítja a Skilben bevezetett számos ötletet és koncepciót, például a magasabb rendű függvényeket, a curry-t és a polimorf típusokat [1]. Az MPI 1.2 és az OpenMP 2.5 tetejére épül, és sok más vázkönyvtárral ellentétben támogatja mind a feladat-, mind az adatpárhuzamos vázat. A vázak beágyazása (összetétele) hasonló a P3L kétszintű megközelítéséhez, vagyis a feladat-párhuzamos vázak tetszőlegesen beágyazódhatnak, míg az adatpárhuzamos vázak nem, de a feladatpárhuzamosan beágyazó fa leveleinél használhatók.[44] A C++-sablonokat használják a vázak polimorf jellegűvé tételére, de semmilyen típusú rendszert nem hajtanak végre.[45] által inspirált automatizált sorosítási mechanizmust valósít meg, amely a standard MPI adattípusok mellett tetszőleges, felhasználó által definiált adattípusokat is felhasználhat a vázakon belül. A támogatott feladat-párhuzamos vázak [46] a Branch & Bound,[47] Divide & Conquer,[48][49] Farm,[50][51] és a Pipe, a kiegészítő vázak Filter, Final és Initial. Az adatokkal párhuzamos vázak, mint például a hajtogatás (kicsinyítés), leképezés, permute, zip és ezek variánsai az elosztott adatstruktúra magasabb rendű tagfüggvényeként valósulnak meg. Jelenleg a Muesli támogatja a tömbök, mátrixok és ritka mátrixok elosztott adatstruktúráit.[52]

Egyedülálló tulajdonságként a Muesli párhuzamos adatvázai automatikusan skálázódnak mind egy-, mind többmagos, többcsomópontos fürt architektúrákon.[53][54] Itt a csomópontok és magok közötti skálázhatóság az MPI és az OpenMP egyidejű alkalmazásával biztosított. Ez a szolgáltatás azonban opcionális abban az értelemben, hogy a Muesli segítségével írt program továbbra is egymagos, több csomópontot tartalmazó fürt számítógépen fordít és fut a forráskód megváltoztatása nélkül, vagyis garantált a visszamenőleges kompatibilitás. Ezt egy nagyon vékony OpenMP absztrakciós réteg biztosítja, amely lehetővé teszi a többmagos architektúrák támogatásának be- és kikapcsolását az OpenMP fordító jelzőjének egyszerű megadásával / kihagyásával a program fordításakor. Ezzel gyakorlatilag semmiféle rezsi nem kerül bevezetésre futás közben.

P3L, SkIE, SKElib

[szerkesztés]

A P3L[55] (Pisa Parallel Programming Language) egy vázalapú koordinációs nyelv. A P3L olyan vázkonstrukciókat biztosít, amelyek a C-kód párhuzamos vagy szekvenciális végrehajtásának koordinálására szolgálnak. A nyelvhez egy [56] nevű fordító tartozik. Anacleto implementációs sablonok segítségével fordítja össze a P3 L kódot egy célarchitektúrába. Így egy váznak több sablonja lehet, amelyek mindegyike különböző architektúrára optimalizált. A sablon egy vázat valósít meg egy adott architektúrán, és paraméteres folyamatdiagramot nyújt teljesítménymodellel. A teljesítménymodell ezután felhasználható a program-átalakítások eldöntésére, amelyek a teljesítmény optimalizálásához vezethetnek.[57]

A P3L modul megfelel egy megfelelően definiált vázkonstrukciónak, bemeneti és kimeneti adatfolyamokkal, valamint más almodulokkal vagy szekvenciális C kóddal. A modulok beágyazhatók a kétszintű modell alkalmazásával, ahol a külső szint párhuzamos feladat vázakból áll, míg a belső szinten adat párhuzamos vázak használhatók. A típusellenőrzést az adatfolyam szintjén hajtják végre, amikor a programozó kifejezetten meghatározza a bemeneti és kimeneti adatfolyam típusát, valamint az almodulok közötti adatáramlás megadásával.

A SkIE [58] (vázalapú integrált környezet) meglehetősen hasonlít a P3L-re, mivel szintén koordinációs nyelven alapul, de olyan fejlett funkciókat kínál, mint a hibakereső eszközök, a teljesítményelemzés, a vizualizáció és a grafikus felhasználói felület. A koordinátor nyelv közvetlen használata helyett a programozók egy grafikus eszközzel lépnek kapcsolatba, ahol vázakra épülő párhuzamos modulok állíthatók össze.

A SKELib [59] a P3L és a SkIE hozzájárulására épít, többek között a sablonrendszer öröklésével. Különbözik tőlük, mert a koordinációs nyelvet már nem használják, ehelyett a vázakat könyvtárként biztosítják a C-ben, hasonló teljesítményűek, mint a P3L-ben. A Skil-lel ellentétben, egy másik C-hez hasonlóan a vázkerethez, a típusbiztonsággal nem foglalkoznak az SKELib-ek.

PAS és EPAS

[szerkesztés]

A PAS (Parallel Architectural Skeletons) a váz programozásának kerete, amelyet C++-ban és MPI-ben fejlesztettek ki.[60][61] A programozók a C++ kiterjesztését használják vázalkalmazásaik megírásához. A kódot ezután egy Perl szkripten keresztül továbbítják, amely kibővíti a kódot tiszta C++ szintre, ahol a vázak öröklődés révén specializálódtak.

A PAS-ben minden váz rendelkezik egy képviselő (Rep) objektummal, amelyet a programozónak kell megadnia, és ő felel a váz végrehajtásának koordinálásáért. A vázak hierarchikus módon beágyazódhatnak a Rep objektumokon keresztül. A váz végrehajtása mellett a Rep kifejezetten kezeli a magasabb szintű váz adatainak fogadását és az adatok továbbítását az alvázakhoz. Paraméterezett kommunikációs / szinkronizálási protokoll használható adatok küldésére és fogadására a szülő és az alvázak között.

A SuperPas [62] majd később EPAS [63] címkével ellátott PAS kiterjesztése foglalkozik a váz nyújthatóságával kapcsolatos problémákkal. Az EPAS eszközzel új vázak adhatók a PAS-hoz. A vázleíró nyelv (SDL) a vázminta leírására szolgál a topológia megadásával egy virtuális processzorrács vonatkozásában. Az SDL ezután összeállítható natív C++ kódba, amely bármely más vázként használható.

SBASCO

[szerkesztés]

Az SBASCO (Skeleton-BAsed Scientific COmponents) a párhuzamos és elosztott numerikus alkalmazások hatékony fejlesztésére orientált programozási környezet.[64] Az SBASCO célja két programozási modell integrálása: a vázak és az egyedi kompozíciós nyelvű alkatrészek. Az összetevő alkalmazásnézete leírja annak interfészeit (bemeneti és kimeneti típus); míg a konfigurációs nézet ezen felül leírja az alkatrész belső felépítését és a processzor elrendezését. Az alkatrész belső felépítése három váz segítségével határozható meg: farm, pipe és multi-block.

Az SBASCO több-blokkos vázán keresztül foglalkozik a tartomány lebomló alkalmazásával. A tartományokat tömbökön keresztül adják meg (főként kétdimenziósak), amelyeket résztömbökre bontanak, esetleges egymást átfedő határokkal. Ezután a számítás iteratív BSP-szerűen történik. Az első szakasz helyi számításokból áll, míg a második szakasz határcseréket hajt végre. A reakció-diffúziós probléma felhasználási esetét mutatjuk be.[65]

Kétféle komponenst mutatunk be.[66] A funkcionális kódot biztosító tudományos alkatrészek (SC); és a kommunikációs aspektus komponensei (CAC), amelyek olyan nem funkcionális viselkedést foglalnak magukba, mint a kommunikáció, az elosztó processzor elrendezése és a replikáció. Például az SC komponensek egy CAC komponenshez vannak csatlakoztatva, amely futás közben menedzserként működhet azáltal, hogy dinamikusan újratérképezi az SC-hez rendelt processzorokat. A CAC-összetevők használatakor jobb teljesítményt mutató felhasználási esetet mutat be.[67]

A strukturált koordinációs nyelv (SCL : Structured Coordination Language) [68] az egyik legkorábbi váz programozási nyelv volt. Koordinációs nyelvi megközelítést biztosít a váz programozásához a szoftverkomponensek felett. Az SCL alapnyelvnek számít, és úgy tervezték, hogy integrálható legyen egy gazdanyelvvel, például a Fortrannal vagy a C-vel, amelyet szekvenciális szoftverkomponensek fejlesztésére használnak. Az SCL-ben a vázakat három típusba sorolják: konfigurációs, elemi és számítási. A konfigurációs vázak absztrakt mintákat mutatnak be az általánosan használt adatstruktúrákhoz, például az elosztott tömbökhöz (ParArray). Az elemi vázak olyan adatokkal párhuzamos vázaknak felelnek meg, mint a térkép, a beolvasás és a hajtás. Számítási vázak, amelyek elvonják a szabályozási folyamatot, és főként a párhuzamos feladatoknak felelnek meg, mint például a farm, az SPMD és az iterateUntil. A koordinációs nyelvi megközelítést a teljesítmény-modellekkel együtt alkalmazták a hagyományos párhuzamos gépek, valamint a párhuzamosan heterogén gépek programozásához, amelyek mindegyik feldolgozási csomóponton különböző magokkal rendelkeznek.[69]

SkePU

[szerkesztés]

SkePU [70] SkePU egy vázprogramozási keretrendszer többmagos CPU-khoz és több GPU-rendszerek számára. Ez egy C++ sablonkönyvtár, amely hat adat-párhuzamos és egy feladat-párhuzamos vázzal, két konténertípussal rendelkezik, és támogatja a végrehajtást több GPU-s rendszereken, mind CUDA-val, mind OpenCL-lel. A közelmúltban a hibrid végrehajtás, a teljesítménytudatos dinamikus ütemezés és a terheléselosztás támogatását fejlesztették ki az SkePU-ban a StarPU futtató rendszer háttérprogramjának megvalósításával. A SkePU-t kiterjesztik a GPU-fürtökre.

SKIPPER & QUAFF

[szerkesztés]

A SKiPPER egy tartományspecifikus vázkönyvtár [71] amely vázakat biztosít a CAML-ben, és így a CAML-re támaszkodik a típusbiztonság szempontjából. A vázakat kétféleképpen mutatják be: deklaratív és operatív. A deklaratív vázakat a programozók közvetlenül használják, míg operatív verzióik architektúra-specifikus célmegvalósítást biztosítanak. A futásidejű környezetből, a CAML váz specifikációiból és az alkalmazásspecifikus funkciókból (amelyeket a programozó C-ben biztosít) az új C-kódot generálják és lefordítják, hogy az alkalmazás fusson a célarchitektúrán. A SKiPPER egyik érdekessége, hogy a vázprogram sorozatosan futtatható a hibakereséshez.

Különböző megközelítéseket kutattak a SKiPPER-ben az operatív vázak írásához: statikus adatfolyam-grafikonok, paraméteres folyamathálózatok, hierarchikus feladatdiagramok és tagged-token adatfolyam-grafikonok.[72]

A QUAFF [73] egy újabb vázkönyvtár, amelyet C++ és MPI formátumban írtak. A QUAFF sablon alapú meta-programozási technikákra támaszkodik a futásidejű általános költségek csökkentésére, valamint a váz bővítésére és optimalizálására a fordítás idején. A vázak beágyazhatók, és a szekvenciális funkciók állapotok. A típusellenőrzés mellett a QUAFF a C++ sablonok előnyeit kihasználva új C / MPI kódot állít elő fordítási időben. A QUAFF a CSP-modellen alapul, ahol a vázprogramot folyamathálózatként és gyártási szabályként írják le (single, serial, par, join).[74]

SkeTo

[szerkesztés]

A SkeTo [75] projekt egy C++ könyvtár, amely párhuzamosítást ér el az MPI használatával. Az SkeTo különbözik a többi vázkönyvtártól, mert az egymásba ágyazható párhuzamossági minták helyett a SkeTo párhuzamos vázakat biztosít párhuzamos adatszerkezetekhez, például: listákhoz, fákhoz,[76][77] és mátrixokhoz.[78] Az adatszerkezetek sablonok segítségével vannak beírva, és több párhuzamos művelet is meghívható rajtuk. Például a listaszerkezet párhuzamos műveleteket biztosít, például: leképezés, kicsinyítés, szkennelés, zip, eltolás stb...

Az SkeTo körül végzett további kutatások az átalakítással történő optimalizálási stratégiákra és az újabban tartományspecifikus optimalizálásokra is összpontosítottak.[79] Például az SkeTo fúziós transzformációt biztosít [80] amely két egymást követő függvényhívást egyesít egyetlen eggyé, ezáltal csökkentve a függvényhívás általános költségeit és elkerülve a függvények között áthaladó közbenső adatstruktúrák létrehozását.

Skil

[szerkesztés]

A Skil[81] a váz programozásának elengedhetetlen nyelve. A vázak nem közvetlenül a nyelv részét képezik, hanem együtt vannak velük. A Skil a C nyelv egy részhalmazát használja, amely funkcionális nyelvhez hasonló funkciókat biztosít, mint például a magasabb rendű függvények, a soros és a polimorf típusok. A Skil fordításakor az ilyen funkciók megszűnnek, és szabályos C kód jön létre. Így Skil átalakítja a polimorf magas rendű függvényeket monomorf első rendű C függvényekké. A Skil nem támogatja a vázak beágyazható összetételét. Az adatok párhuzamosságát speciális adatpárhuzamos struktúrák segítségével érik el, például tömbök elterjesztésére az elérhető processzorok között. Szűrővázak használhatók.

STAPL vázkeretrendszer

[szerkesztés]

A STAPL vázkeretrendszerben [82][83] a vázakat paraméteres adatfolyam-grafikonként definiálják, lehetővé téve számukra, hogy meghaladja a 100 000 magot. Ezenkívül ez a keret a vázak összetételével foglalkozik, mint a megfelelő adatfolyam-grafikonok pont-pont összetétele a portok fogalmán keresztül, lehetővé téve az új vázak könnyű hozzáadását a kerethez. Ennek eredményeként ez a keretrendszer kiküszöböli az újrabeépítés és a globális szinkronizálás szükségességét az összeállított vázakban. A STAPL Skeleton Framework támogatja a beágyazott kompozíciókat, és a beágyazás minden szintjén válthat a párhuzamos és a szekvenciális végrehajtás között. Ez a keretrendszer profitál a STAPL párhuzamos konténerek [84] skálázható megvalósításából, és különböző konténereken futtathatja a vázakat, beleértve a vektorokat, a többdimenziós tömböket és a listákat.

T4P

[szerkesztés]

A T4P volt az első rendszerek bevezetése a vázprogramozáshoz.[85] A rendszer nagyban támaszkodott a funkcionális programozási tulajdonságokra, és öt vázat határoztak meg magasabb rendű funkcióként: Divide-and-Conquer, Farm, Map, Pipe és RaMP. Egy programnak több megvalósítása is lehet, amelyek mindegyike különböző vázak kombinációját használja. Ezenkívül minden váz különböző párhuzamos megvalósítással rendelkezhet. A vázak teljesítménymodelljein alapuló funkcionális programtranszformációkra épülő módszertant választották ki a programhoz legmegfelelőbb vázra, valamint a váz legmegfelelőbb megvalósítására.[86]

Keretrendszerek összehasonlítása

[szerkesztés]
  • Az aktív évek az ismert tevékenységi évek. Az ebben az oszlopban feltüntetett dátumok megegyeznek egy tudományos folyóirat vagy konferencia folyóirat kapcsolódó cikkének első és utolsó megjelenési dátumával. Vegye figyelembe, hogy egy projekt továbbra is aktív lehet a tevékenységi időn túl, és hogy a megadott dátumon túl nem sikerült kiadványt találnunk hozzá.
  • A programozási nyelv az a felület, amellyel a programozók kölcsönhatásban vannak a vázalkalmazásaik kódolásához. Ezek a nyelvek sokfélék, olyan paradigmákat ölelnek fel, mint: funkcionális nyelvek, koordinációs nyelvek, jelölő nyelvek, imperatív nyelvek, objektumorientált nyelvek, sőt grafikus felhasználói felületek is. A programozási nyelv belsejében a vázak nyelvi konstrukciókként vagy könyvtárakként kerültek rendelkezésre. A vázak nyelvi konstrukcióként való ellátása magában foglalja az egyedi tartományspecifikus nyelv és annak fordítójának fejlesztését. A vázkutatás kezdetén egyértelműen ez volt az erősebb tendencia. A legújabb trend az, hogy a vázakat könyvtárakként kínálják, különösen olyan objektumorientált nyelvekkel, mint a C++ és a Java.
  • A végrehajtási nyelv az a nyelv, amelyen a vázalkalmazásokat futtatják vagy lefordítják. Nagyon korán felismerték, hogy a programozási nyelvek (különösen a funkcionális esetekben) nem voltak elég hatékonyak a vázprogramok végrehajtásához. Ezért a vázprogramozási nyelveket leegyszerűsítették a vázalkalmazás más nyelveken történő végrehajtásával. Transzformációs folyamatokat vezettek be a vázalkalmazások (a programozási nyelven definiált) ekvivalens alkalmazássá konvertálására a cél végrehajtási nyelven. Különböző transzformációs folyamatokat vezettek be, például kódgenerálást vagy az alacsonyabb szintű vázak (esetenként operatív vázak) példányosítását, amelyek képesek voltak kölcsönhatásba lépni egy könyvtárral a végrehajtási nyelven. Az átalakított alkalmazás lehetőséget adott arra is, hogy a transzformált alkalmazásba a teljesítményre szabott célarchitektúra kódot vezessen be. Az 1. táblázat azt mutatja, hogy a végrehajtási nyelv egyik kedvence a C nyelv volt.
  • A terjesztési könyvtár biztosítja a párhuzamos / elosztott számítások elérésének funkcionalitását. A nagy kedvenc ebben az értelemben az MPI volt, ami nem meglepő, mivel jól integrálódik a C nyelvvel, és valószínűleg a fürtszámítás párhuzamosságának leggyakrabban használt eszköze. A terjesztési könyvtárral való közvetlen programozás veszélyei természetesen biztonságosan el vannak rejtve azoktól a programozóktól, akik soha nem lépnek kapcsolatba a terjesztési könyvtárral. A közelmúltban az a tendencia volt, hogy olyan vázkeretrendszereket fejlesztenek ki, amelyek képesek egynél több terjesztési könyvtárral kölcsönhatásba lépni. Például a CO2 P3 S használhatja szálakat, RMI-t vagy aljzatokat; Mallba használhatja a Netstreamet vagy az MPI-t; vagy JaSkel, amely az AspectJ segítségével futtatja a váz-alkalmazásokat különböző vázkereteken.
  • A típusbiztonság a típus inkompatibilitási hibák észlelésének képességére utal a vázprogramban. Mivel az első vázkeretek funkcionális nyelvekre épültek, mint például a Haskell, a típusbiztonság egyszerűen öröklődött a gazdagép nyelvéből. Mindazonáltal, mivel az egyedi nyelveket a váz programozásához fejlesztették ki, a fordítókat meg kellett írni, hogy figyelembe vegyék a típusellenőrzést; ami nem volt olyan nehéz, mert a vázak beágyazása nem volt teljesen támogatott. A közelmúltban azonban, amikor objektumorientált nyelveken kezdtünk el vázkeretrendszereket üzemeltetni teljes beágyazással, a típusbiztonsági probléma újból felmerült. Sajnos a típusellenőrzést többnyire figyelmen kívül hagyták (a QUAFF kivételével), különösképpen a Java alapú vázkeretrendszerekben.
  • A váz beágyazása a vázminták hierarchikus összetételének képessége. A váz beágyazását már a kezdetektől fogva fontos tulajdonságként határozták meg a váz programozásában, mert ez lehetővé teszi az összetettebb minták összetételét az egyszerűbb minták alapkészletétől kezdve. Ennek ellenére a közösségnek hosszú időbe telt, hogy teljes mértékben támogassa a vázak önkényes beágyazását, főként az ütemezés és a típusellenőrzés nehézségei miatt. A tendencia egyértelmű, hogy a legújabb vázkeretek támogatják a vázak teljes beágyazását.
  • A fájlhozzáférés az a képesség, amely egy alkalmazásból hozzáférhet és kezelheti a fájlokat. A múltban a vázprogramozás főleg számításigényes alkalmazásoknál bizonyult hasznosnak, ahol kis mennyiségű adat nagy mennyiségű számítási időt igényel. Ennek ellenére sok elosztott alkalmazás nagy mennyiségű adatot igényel vagy állít elő számításuk során. Ez a helyzet az asztrofizika, a részecskefizika, a bioinformatika stb. Így a váz programozással integrált fájlátviteli támogatás nyújtása kulcsfontosságú kérdés, amelyet többnyire figyelmen kívül hagytak.
  • A vázkészlet a támogatott vázminták listája. A vázkészletek egyik keretről a másikra nagyon eltérnek, és megdöbbentőbb, hogy néhány azonos nevű váz különböző szemantikával rendelkezik különböző keretek között. Az irodalomban a leggyakoribb vázminták valószínűleg a farm, a pipa és a térkép.
Nem objektumorientált algoritmikusváz-keretrendszerek
Aktív évek Programozási nyelv Végrehajtási nyelv Kiterjesztési könyvtár Biztonsági típus Vázbeágyazás Fájlhozzáférés Vázkészlet
ASSIST 2004–2007 Custom control language C++ TCP/IP + ssh/scp Igen Nem explicit seq, parmod
SBSACO 2004–2006 Custom composition language C++ MPI Igen Igen Nem farm, pipe, multi-block
eSkel 2004–2005 C C MPI Nem ? Nem pipeline, farm, deal, butterfly, hallowSwap
HDC 2004–2005 Haskell subset C MPI Igen ? Nem dcA, dcB, dcD, dcE, dcF, map, red, scan, filter
SKELib 2000-2000 C C MPI Nem Nem Nem farm, pipe
SkiPPER 1999–2002 CAML C SynDex Igen limited Nem scm, df, tf, intermem
SkIE 1999-1999 GUI/Custom control language C++ MPI Igen limited Nem pipe, farm, map, reduce, loop
Eden 1997–2011 Haskell extension Haskell PVM/MPI Igen Igen Nem map, farm, workpool, nr, dc, pipe, iterUntil, torus, ring
P3L 1995–1998 Custom control language C MPI Igen limited Nem map, reduce, scan, comp, pipe, farm, seq, loop
Skil 1995–1998 C subset C ? Igen Nem Nem pardata, map, fold
SCL 1994–1999 Custom control language Fortran/C MPI Igen limited Nem map, scan, fold, farm, SPMD, iterateUntil
T4P 1990–1994 Hope+ Hope+ CSTools Igen limited Nem D&C (Divide-and-Conquer), Map, Pipe, RaMP
Objektumorientált algoritmikusváz-keretrendszerek
Aktív évek Programozási nyelv Végrehajtási nyelv Kiterjesztési könyvtárak Biztonsági típusa Vázbeágyazás Fájlhozzáférés Vázkészlet
Skandium 2009–2012 Java Java Threads Igen Igen Nem seq, pipe, farm, for, while, map, d&c, fork
FastFlow 2009– C++ C++11 / CUDA / OpenCL C++11 threads / Posix threads / TCP-IP / OFED-IB / CUDA / OpenCL Igen Igen Igen Pipeline, Farm, ParallelFor, ParallelForReduce, MapReduce, StencilReduce, PoolEvolution, MacroDataFlow
Calcium 2006–2008 Java Java ProActive Igen Igen Igen seq, pipe, farm, for, while, map, d&c, fork
QUAFF 2006–2007 C++ C MPI Igen Igen Nem seq, pipe, farm, scm, pardo
JaSkel 2006–2007 Java Java/AspectJ MPP / RMI Nem Igen Nem farm, pipeline, heartbeat
Muskel 2005–2008 Java Java RMI Nem Igen Nem farm, pipe, seq, + custom MDF Graphs
HOC-SA 2004–2008 Java Java Globus, KOALA Nem Nem Nem farm, pipeline, wavefront
SkeTo 2003–2013 C++ C++ MPI Igen Nem Nem list, matrix, tree
Mallba 2002–2007 C++ C++ NetStream / MPI Igen Nem Nem exact, heuristic, hybrid
Marrow 2013– C++ C++ plus OpenCL (none) Nem Igen Nem data parallel: map, map-reduce. task parallel: pipeline, loop, for
Muesli 2002–2013 C++ C++ MPI / OpenMP Igen Igen Nem data parallel: fold, map, permute, scan, zip, and variants. task parallel: branch & bound, divide & conquer, farm, pipe. auxiliary: filter, final, initial
Alt 2002–2003 Java/GworkflowDL Java Java RMI Igen Nem Nem map, zip, reduction, scan, dh, replicate, apply, sort
(E)PAS 1999–2005 C++ extension C++ MPI Nem Igen Nem singleton, replication, compositional, pipeline, divideconquer, dataparallel
Lithium 1999–2004 Java Java RMI Nem Igen Nem pipe, map, farm, reduce
CO2P3S 1999–2003 GUI/Java Java (generated) Threads / RMI / Sockets Részlegesen Nem Nem method-sequence, distributor, mesh, wavefront
STAPL 2010– C++ C++11 STAPL Runtime Library (MPI, OpenMP, PThreads) Igen Igen Igen map, zip<arity>, reduce, scan, farm, (reverse-)butterfly, (reverse-)tree<k-ary>, recursive-doubling, serial, transpose, stencil<n-dim>, wavefront<n-dim>, allreduce, allgather, gather, scatter, broadcast

Operators: compose, repeat, do-while, do-all, do-across

Jegyzetek

[szerkesztés]
  1. ↑ 'S. MacDonald, J. Anvik, S. Bromling, J. Schaeffer, D. Szafron, and K. Tan.' "From patterns to frameworks to parallel programs." Parallel Comput., 28(12):1663–1683, 2002.
  2. ↑ D. Caromel and M. Leyton. "Fine tuning algorithmic skeletons." In 13th International Euro-Par Conference: Parallel Processing, volume 4641 of Lecture Notes in Computer Science, pages 72–81. Springer-Verlag, 2007.
  3. ↑ D. Caromel, L. Henrio, and M. Leyton. "Type safe algorithmic skeletons." In Proceedings of the 16th Euromicro Conference on Parallel, Distributed and Network-based Processing, pages 45–53, Toulouse, France, Feb. 2008. IEEE CS Press.
  4. ↑ D. Caromel and M. Leyton. "A transparent non-invasive file data model for algorithmic skeletons." In 22nd International Parallel and Distributed Processing Symposium (IPDPS), pages 1–8, Miami, USA, March 2008. IEEE Computer Society.
  5. ↑ Mario Leyton, Jose M. Piquer. "Skandium: Multi-core Programming with algorithmic skeletons", IEEE Euro-micro PDP 2010.
  6. ↑ Rita Loogen and Yolanda Ortega-Mallén and Ricardo Peña-Marí. "Parallel Functional Programming in Eden", Journal of Functional Programming, No. 15(2005),3, pages 431–475
  7. ↑ Murray Cole. "Bringing skeletons out of the closet: a pragmatic manifesto for skeletal parallel programming." Parallel Computing, 30(3):389–406, 2004.
  8. ↑ A. Benoit, M. Cole, S. Gilmore, and J. Hillston. "Flexible skeletal programming with eskel." In J. C. Cunha and P. D. Medeiros, editors, Euro-Par, volume 3648 of Lecture Notes in Computer Science, pages 761–770. Springer, 2005.
  9. ↑ A. Benoit and M. Cole. "Two fundamental concepts in skeletal parallel programming." In V. Sunderam, D. van Albada, P. Sloot, and J. Dongarra, editors, The International Confer-ence on Computational Science (ICCS 2005), Part II, LNCS 3515, pages 764–771. Springer Verlag, 2005.
  10. ↑ A. Benoit, M. Cole, S. Gilmore, and J. Hillston. Evaluating the performance of skeleton-based high level parallel programs. In M. Bubak, D. van Albada, P. Sloot, and J. Dongarra, editors, The International Conference on Computational Science (ICCS 2004), Part III, LNCS 3038, pages 289–296. Springer Verlag, 2004.
  11. ↑ A. Benoit, M. Cole, S. Gilmore, and J. Hillston. "Evaluating the performance of pipeline structured parallel programs with skeletons and process algebra." Scalable Computing: Practice and Experience, 6(4):1–16, December 2005.
  12. ↑ A. Benoit, M. Cole, S. Gilmore, and J. Hillston. "Scheduling skeleton-based grid applications using pepa and nws." The Computer Journal, Special issue on Grid Performability Modelling and Measurement, 48(3):369–378, 2005.
  13. ↑ A. Benoit and Y. Robert. "Mapping pipeline skeletons onto heterogeneous platforms." In ICCS 2007, the 7th International Conference on Computational Science, LNCS 4487, pages 591–598. Springer Verlag, 2007.
  14. ↑ G. Yaikhom, M. Cole, S. Gilmore, and J. Hillston. "A structural approach for modelling performance of systems using skeletons." Electr. Notes Theor. Comput. Sci., 190(3):167–183,2007.
  15. ↑ H. Gonzalez-Velez and M. Cole. "Towards fully adaptive pipeline parallelism for heterogeneous distributed environments." In Parallel and Distributed Processing and Applications, 4th International Symposium (ISPA), Lecture Notes in Computer Science, pages 916–926. Springer-Verlag, 2006.
  16. ↑ H. Gonzalez-Velez and M. Cole. "Adaptive structured parallelism for computational grids." In PPoPP '07: Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 140–141, New York, NY, USA, 2007. ACM.
  17. ↑ Aldinucci, M.. Efficient Smith-Waterman on Multi-core with Fast Flow, 2010 18th Euromicro Conference on Parallel, Distributed and Network-based Processing. IEEE, 195. o.. DOI: 10.1109/PDP.2010.93 (2010). ISBN 978-1-4244-5672-7 
  18. ↑ C. A. Herrmann and C. Lengauer. "HDC: A higher-order language for divide-and-conquer." Parallel Processing Letters, 10(2–3):239–250, 2000.
  19. ↑ C. A. Herrmann. The Skeleton-Based Parallelization of Divide-and-Conquer Recursions. PhD thesis, 2000. ISBN 3-89722-556-5.".
  20. ↑ J. Dünnweber, S. Gorlatch. "Higher-Order Components for Grid Programming. Making Grids More Usable.". Springer-Verlag, 2009. ISBN 978-3-642-00840-5
  21. ↑ J. F. Ferreira, J. L. Sobral, and A. J. Proenca. "Jaskel: A java skeleton-based framework for structured cluster and grid computing". In CCGRID '06: Proceedings of the Sixth IEEE International Symposium on Cluster Computing and the Grid, pages 301–304, Washington, DC, USA, 2006. IEEE Computer Society.
  22. ↑ J. Sobral and A. Proenca. "Enabling jaskel skeletons for clusters and computational grids." In IEEE Cluster. IEEE Press, 9 2007.
  23. ↑ M. Aldinucci and M. Danelutto. "Stream parallel skeleton optimization." In Proc. of PDCS: Intl. Conference on Parallel and Distributed Computing and Systems, pages 955–962, Cambridge, Massachusetts, USA, Nov. 1999. IASTED, ACTA press.
  24. ↑ Aldinucci (2003). „An advanced environment supporting structured parallel programming in Java”. Future Generation Computer Systems 19 (5), 611. o. DOI:10.1016/S0167-739X(02)00172-3. 
  25. ↑ M. Danelutto and P. Teti. "Lithium: A structured parallel programming environment in Java." In Proc. of ICCS: International Conference on Computational Science, volume 2330 of LNCS, pages 844–853. Springer Verlag, Apr. 2002.
  26. ↑ M. Aldinucci and M. Danelutto. "An operational semantics for skeletons." In G. R. Joubert, W. E. Nagel, F. J. Peters, and W. V. Walter, editors, Parallel Computing: Software Technology, Algorithms, Architectures and Applications, PARCO 2003, volume 13 of Advances in Parallel Computing, pages 63–70, Dresden, Germany, 2004. Elsevier.
  27. ↑ Aldinucci (2007). „Skeleton-based parallel programming: Functional and parallel semantics in a single shot☆”. Computer Languages, Systems & Structures 33 (3–4), 179. o. DOI:10.1016/j.cl.2006.07.004. 
  28. ↑ M. Aldinucci, M. Danelutto, and J. Dünnweber. "Optimization techniques for implementing parallel skeletons in grid environments." In S. Gorlatch, editor, Proc. of CMPP: Intl. Workshop on Constructive Methods for Parallel Programming, pages 35–47, Stirling, Scotland, UK, July 2004. Universität Munster, Germany.
  29. ↑ M. Danelutto. Efficient support for skeletons on workstation clusters. Parallel Processing Letters, 11(1):41–56, 2001.
  30. ↑ M. Danelutto. "Dynamic run time support for skeletons." Technical report, 1999.
  31. ↑ M. Danelutto. "Qos in parallel programming through application managers." In PDP '05: Proceedings of the 13th Euromicro Conference on Parallel, Distributed and Network-Based Processing (PDP'05), pages 282–289, Washington, DC, USA, 2005. IEEE Computer Society.
  32. ↑ M. Aldinucci and M. Danelutto. "The cost of security in skeletal systems." In P. D'Ambra and M. R. Guarracino, editors, Proc. of Intl. Euromicro PDP 2007: Parallel Distributed and network-based Processing, pages 213–220, Napoli, Italia, February 2007. IEEE.
  33. ↑ M. Aldinucci and M. Danelutto. "Securing skeletal systems with limited performance penalty: the muskel experience." Journal of Systems Architecture, 2008.
  34. ↑ M. Danelutto and P. Dazzi. "A Java/Jini framework supporting stream parallel computations." In Proc. of Intl. PARCO 2005: Parallel Computing, Sept. 2005.
  35. ↑ M. Danelutto and P. Dazzi. "Joint structured/non-structured parallelism exploitation through data flow." In V. Alexandrov, D. van Albada, P. Sloot, and J. Dongarra, editors, Proc. of ICCS: International Conference on Computational Science, Workshop on Practical Aspects of High-level Parallel Programming, LNCS, Reading, UK, May 2006. Springer Verlag.
  36. ↑ M. Aldinucci, M. Danelutto, and P. Dazzi. "Muskel: an expandable skeleton environment." Scalable Computing: Practice and Experience, 8(4):325–341, December 2007.
  37. ↑ E. Alba, F. Almeida, M. J. Blesa, J. Cabeza, C. Cotta, M. Diaz, I. Dorta, J. Gabarro, C. Leon, J. Luna, L. M. Moreno, C. Pablos, J. Petit, A. Rojas, and F. Xhafa. "Mallba: A library of skeletons for combinatorial optimisation (research note)." In Euro-Par '02: Proceedings of the 8th International Euro-Par Conference on Parallel Processing, pages 927–932, London, UK, 2002. Springer-Verlag.
  38. ↑ E. Alba, F. Almeida, M. Blesa, C. Cotta, M. Diaz, I. Dorta, J. Gabarro, C. Leon, G. Luque, J. Petit, C. Rodriguez, A. Rojas, and F. Xhafa. Efficient parallel lan/wan algorithms for optimization: the mallba project. Parallel Computing, 32(5):415–440, 2006.
  39. ↑ E. Alba, G. Luque, J. Garcia-Nieto, G. Ordonez, and G. Leguizamon. "Mallba a software library to design efficient optimisation algorithms." International Journal of Innovative Computing and Applications, 1(1):74–85, 2007.
  40. ↑ "Ricardo Marques, Hervé Paulino, Fernando Alexandre, Pedro D. Medeiros." "Algorithmic Skeleton Framework for the Orchestration of GPU Computations." Euro-Par 2013: 874–885
  41. ↑ "Fernando Alexandre, Ricardo Marques, Hervé Paulino." "On the Support of Task-Parallel Algorithmic Skeletons for Multi-GPU Computing." ACM SAC 2014: 880–885
  42. ↑ H. Kuchen and J. Striegnitz. "Features from functional programming for a C++ skeleton library". Concurrency – Practice and Experience, 17(7–8):739–756, 2005.
  43. ↑ Philipp Ciechanowicz, Michael Poldner, and Herbert Kuchen. "The Muenster Skeleton Library Muesli – A Comprehensive Overview." ERCIS Working Paper No. 7, 2009
  44. ↑ H. Kuchen and M. Cole. "The integration of task and data parallel skeletons." Parallel Processing Letters, 12(2):141–155, 2002.
  45. ↑ A. Alexandrescu. "Modern C++ Design: Generic Programming and Design Patterns Applied". Addison-Wesley, 2001.
  46. ↑ Michael Poldner. "Task Parallel Algorithmic Skeletons." PhD Thesis, University of Münster, 2008.
  47. ↑ Michael Poldner and Herbert Kuchen. "Algorithmic Skeletons for Branch and Bound." Proceedings of the 1st International Conference on Software and Data Technology (ICSOFT), 1:291–300, 2006.
  48. ↑ Michael Poldner and Herbert Kuchen. "Optimizing Skeletal Stream Processing for Divide and Conquer." Proceedings of the 3rd International Conference on Software and Data Technologies (ICSOFT), 181–189, 2008.
  49. ↑ Michael Poldner and Herbert Kuchen. "Skeletons for Divide and Conquer." Proceedings of the IASTED International Conference on Parallel and Distributed Computing and Networks (PDCN), 181–188, 2008.
  50. ↑ Michael Poldner and Herbert Kuchen. "Scalable Farms." Proceedings of the International Conference on Parallel Processing (ParCo) 33:795–802, 2006.
  51. ↑ Michael Poldner and Herbert Kuchen. "On Implementing the Farm Skeleton." Parallel Processing Letters, 18(1):117–131, 2008.
  52. ↑ Philipp Ciechanowicz. "Algorithmic Skeletons for General Sparse Matrices." Proceedings of the 20th IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS), 188–197, 2008.
  53. ↑ Philipp Ciechanowicz, Philipp Kegel, Maraike Schellmann, Sergei Gorlatch, and Herbert Kuchen. "Parallelizing the LM OSEM Image Reconstruction on Multi-Core Clusters." Parallel Computing: From Multicores and GPU's to Petascale, 19: 169–176, 2010.
  54. ↑ Philipp Ciechanowicz and Herbert Kuchen. "Enhancing Muesli's Data Parallel Skeletons for Multi-Core Computer Architectures". International Conference on High Performance Computing and Communications (HPCC), 108–113, 2010.
  55. ↑ Bacci (1995). „P3L: A structured high-level parallel language, and its structured support”. Concurrency: Practice and Experience 7 (3), 225. o. DOI:10.1002/cpe.4330070305. 
  56. ↑ S. Ciarpaglini, M. Danelutto, L. Folchi, C. Manconi, and S. Pelagatti. "ANACLETO: a template-based p3l compiler." In Proceedings of the Seventh Parallel Computing Workshop (PCW '97), Australian National University, Canberra, August 1997.
  57. ↑ M. Aldinucci, M. Coppola, and M. Danelutto. Rewriting skeleton programs: How to evaluate the data-parallel stream-parallel tradeoff. In S. Gorlatch, editor, Proc of CMPP: Intl. Workshop on Constructive Methods for Parallel Programming, pages 44–58. Uni. Passau, Germany, May 1998.
  58. ↑ B. Bacci, M. Danelutto, S. Pelagatti, and M. Vanneschi. "Skie: a heterogeneous environment for HPC applications." Parallel Comput., 25(13–14):1827–1852, 1999.
  59. ↑ M. Danelutto and M. Stigliani. "Skelib: Parallel programming with skeletons in C." In Euro-Par '00: Proceedings from the 6th International Euro-Par Conference on Parallel Processing, pages 1175–1184, London, UK, 2000. Springer-Verlag.
  60. ↑ D. Goswami, A. Singh, and B. R. Preiss. "From design patterns to parallel architectural skeletons." J. Parallel Distrib. Comput., 62(4):669–695, 2002.
  61. ↑ D. Goswami, A. Singh, and B. R. Preiss. "Using object-oriented techniques for realizing parallel architectural skeletons." In ISCOPE '99: Proceedings of the Third International Symposium on Computing in Object-Oriented Parallel Environments, Lecture Notes in Computer Science, pages 130–141, London, UK, 1999. Springer-Verlag.
  62. ↑ M. M. Akon, D. Goswami, and H. F. Li. "Superpas: A parallel architectural skeleton model supporting extensibility and skeleton composition." In Parallel and Distributed Processing and Applications Second International Symposium, ISPA, Lecture Notes in Computer Science, pages 985–996. Springer-Verlag, 2004.
  63. ↑ M. M. Akon, A. Singh, D. Goswami, and H. F. Li. "Extensible parallel architectural skeletons." In High Performance Computing HiPC 2005, 12th International Conference, volume 3769 of Lecture Notes in Computer Science, pages 290–301, Goa, India, December 2005. Springer-Verlag.
  64. ↑ M. Diaz, B. Rubio, E. Soler, and J. M. Troya. "SBASCO: Skeleton-based scientific components." In PDP, pages 318–. IEEE Computer Society, 2004.
  65. ↑ M. Diaz, S. Romero, B. Rubio, E. Soler, and J. M. Troya. "Using SBASCO to solve reaction-diffusion equations in two-dimensional irregular domains." In Practical Aspects of High-Level Parallel Programming (PAPP), affiliated to the International Conference on Computational Science (ICCS), volume 3992 of Lecture Notes in Computer Science, pages 912–919. Springer, 2006.
  66. ↑ M. Diaz, S. Romero, B. Rubio, E. Soler, and J. M. Troya. "An aspect oriented framework for scientific component development." In PDP '05: Proceedings of the 13th Euromicro Conference on Parallel, Distributed and Network-Based Processing, pages 290–296, Washington, DC, USA, 2005. IEEE Computer Society.
  67. ↑ M. Diaz, S. Romero, B. Rubio, E. Soler, and J. M. Troya. "Dynamic reconfiguration of scientific components using aspect oriented programming: A case study." In R. Meersman And Z. Tari, editors, On the Move to Meaningful Internet Systems 2006: CoopIS, DOA, GADA, and ODBASE, volume 4276 of Lecture Notes in Computer Science, pages 1351–1360. Springer-Verlag, 2006.
  68. ↑ J. Darlington, Y. ke Guo, H. W. To, and J. Yang. "Parallel skeletons for structured composition." In PPOPP '95: Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 19–28, New York, NY, USA, 1995. ACM.
  69. ↑ John Darlinton (1996), "Guided Resource Organisation in Heterogeneous Parallel Computing", Journal of High Performance Computing 4 (1): 13–23
  70. ↑ http://www.ida.liu.se/~chrke/skepu
  71. ↑ J. Serot, D. Ginhac, and J. Derutin. "SKiPPER: a skeleton-based parallel programming environment for real-time image processing applications." In V. Malyshkin, editor, 5th International Conference on Parallel Computing Technologies (PaCT-99), volume 1662 of LNCS,pages 296–305. Springer, 6–10 September 1999.
  72. ↑ J. Serot and D. Ginhac. "Skeletons for parallel image processing : an overview of the SKiPPER project". Parallel Computing, 28(12):1785–1808, Dec 2002.
  73. ↑ J. Falcou, J. Serot, T. Chateau, and J. T. Lapreste. "Quaff: efficient c++ design for parallel skeletons." Parallel Computing, 32(7):604–615, 2006.
  74. ↑ J. Falcou and J. Serot. "Formal semantics applied to the implementation of a skeleton-based parallel programming library." In G. R. Joubert, C. Bischof, F. J. Peters, T. Lippert, M. Bcker, P. Gibbon, and B. Mohr, editors, Parallel Computing: Architectures, Algorithms and Applications (Proc. of PARCO 2007, Julich, Germany), volume 38 of NIC, pages 243–252, Germany, September 2007. John von Neumann Institute for Computing.
  75. ↑ K. Matsuzaki, H. Iwasaki, K. Emoto, and Z. Hu. "A library of constructive skeletons for sequential style of parallel programming." In InfoScale '06: Proceedings of the 1st international conference on Scalable information systems, page 13, New York, NY, USA, 2006. ACM.
  76. ↑ K. Matsuzaki, Z. Hu, and M. Takeichi. "Parallelization with tree skeletons." In Euro-Par, volume 2790 of Lecture Notes in Computer Science, pages 789–798. Springer, 2003.
  77. ↑ K. Matsuzaki, Z. Hu, and M. Takeichi. "Parallel skeletons for manipulating general trees." Parallel Computation, 32(7):590–603, 2006.
  78. ↑ K. Emoto, Z. Hu, K. Kakehi, and M. Takeichi. "A compositional framework for developing parallel programs on two dimensional arrays." Technical report, Department of Mathematical Informatics, University of Tokyo, 2005.
  79. ↑ K. Emoto, K. Matsuzaki, Z. Hu, and M. Takeichi. "Domain-specific optimization strategy for skeleton programs." In Euro-Par, volume 4641 of Lecture Notes in Computer Science, pages 705–714. Springer, 2007.
  80. ↑ K. Matsuzaki, K. Kakehi, H. Iwasaki, Z. Hu, and Y. Akashi. "A fusion-embedded skeleton library." In M. Danelutto, M. Vanneschi, and D. Laforenza, editors, Euro-Par, volume 3149 of Lecture Notes in Computer Science, pages 644–653. Springer, 2004.
  81. ↑ G. H. Botorog and H. Kuchen. "Efficient high-level parallel programming." Theor. Comput. Sci., 196(1–2):71–107, 1998.
  82. ↑ Zandifar, Mani. Composing Algorithmic Skeletons to Express High-Performance Scientific Applications, 415–424. o.. DOI: 10.1145/2751205.2751241 (2015. december 8.). ISBN 9781450335591 
  83. ↑ Zandifar, Mani.szerk.: Brodman: Languages and Compilers for Parallel Computing, Lecture Notes in Computer Science (angol nyelven). Springer International Publishing, 176–190. o.. DOI: 10.1007/978-3-319-17473-0_12 (2014. szeptember 15.). ISBN 9783319174723 
  84. ↑ "G. Tanase, et.al." "STAPL Parallel Container Framework" Proceeding PPoPP '11 Proceedings of the 16th ACM symposium on Principles and practice of parallel programming Pages 235–246
  85. ↑ J. Darlington, A. J. Field, P. G. Harrison, P. H. J. Kelly, D. W. N. Sharp, and Q. Wu. "Parallel programming using skeleton functions." In PARLE '93: Proceedings of the 5th International PARLE Conference on Parallel Architectures and Languages Europe, pages 146–160, London, UK, 1993. Springer-Verlag.
  86. ↑ J. Darlinton; M. Ghanem & H. W. To (1993), "Structured Parallel Programming", In Programming Models for Massively Parallel Computers. IEEE Computer Society Press. 1993: 160–169

Fordítás

[szerkesztés]

Ez a szócikk részben vagy egészben az Algorithmic skeleton című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Algoritmikus_váz&oldid=27154847”