Algoritmiskt skelett

Inom beräkningar är algoritmiska skelett, eller parallellismmönster, en parallell programmeringsmodell på hög nivå för parallell och distribuerad beräkning.

Algoritmiska skelett drar fördel av vanliga programmeringsmönster för att dölja komplexiteten i parallella och distribuerade applikationer. Utgående från en grundläggande uppsättning mönster (skelett), kan mer komplexa mönster byggas genom att kombinera de grundläggande.

Översikt

Den mest framstående egenskapen hos algoritmiska skelett, som skiljer dem från andra parallella programmeringsmodeller på hög nivå, är att orkestrering och synkronisering av de parallella aktiviteterna implicit definieras av skelettmönstren. Programmerare behöver inte specificera synkroniseringarna mellan applikationens sekventiella delar. Detta ger två implikationer. För det första, eftersom kommunikations-/dataåtkomstmönstren är kända i förväg, kan kostnadsmodeller användas för att schemalägga skelettprogram. För det andra minskar den algoritmiska skelettprogrammeringen antalet fel jämfört med traditionella parallellprogrammeringsmodeller på lägre nivå (Threads, MPI).

Exempel på program

Följande exempel är baserat på Java Skandium -biblioteket för parallell programmering.

Målet är att implementera en algoritmisk skelettbaserad parallellversion av QuickSort -algoritmen med hjälp av Divide and Conquer-mönstret. Lägg märke till att tillvägagångssättet på hög nivå döljer trådhantering från programmeraren.


        
      
     
     
     
		

    
	


	

    // 1. Definiera skelettprogrammet  Skeleton  <  Range  ,  Range  >  sort  =  new  DaC  <  Range  ,  Range  >  (  new  ShouldSplit  (  threshold  ,  maxTimes  ),  new  SplitList  (),  new  Sort  (),  new  MergeList  ());  // 2. Inmatningsparametrar  Future  <  Range  >  future  =  sort  .  input  (  nytt  intervall  (  generera  (...)));  // 3. Gör något annat här.  // ...  // 4. Blockera för resultaten  Range  result  =  future  .  få  ();

Det första är att definiera en ny instans av skelettet med den funktionella koden som fyller mönstret (ShouldSplit, SplitList, Sort, MergeList). Den funktionella koden skrivs av programmeraren utan problem med parallellitet.
Det andra steget är inmatningen av data som utlöser beräkningen. I detta fall är Range en klass som innehåller en array och två index som tillåter representation av en subarray. För varje data som matas in i ramverket skapas ett nytt Future-objekt. Mer än en framtid kan skrivas in i ett skelett samtidigt.
Framtiden tillåter asynkron beräkning, eftersom andra uppgifter kan utföras medan resultaten beräknas.
Vi kan hämta resultatet av beräkningen, blockera vid behov (dvs. resultat som ännu inte är tillgängliga).

Funktionskoderna i detta exempel motsvarar fyra typer Condition, Split, Execute och Merge.

    

     
  
      
      
       
          0
  
	
  
      
          
    	     
  
 public  class  ShouldSplit  implementerar  Condition  <  Range  >  {  int  threshold  ,  maxTimes  ,  times  ;  public  ShouldSplit  (  int  threshold  ,  int  maxTimes  ) {  this  .  tröskel  =  tröskel  ;  detta  .  maxTimes  =  maxTimes  ;  detta  .  gånger  =  ;  } @  Åsidosätt  offentligt  synkroniserat  booleskt  tillstånd  (  Räckvidd  r  ){  return  r  .  höger  -  r  .  vänster  >  tröskel  &&  gånger  ++  <  detta  .  maxTimes  ;  }  }

Klassen ShouldSplit implementerar Condition-gränssnittet. Funktionen tar emot en indata, Range r i detta fall, och returnerar sant eller falskt. I samband med Divide and Conquer där denna funktion kommer att användas, kommer detta att avgöra om en sub-array ska delas upp igen eller inte.

Klassen SplitList implementerar det delade gränssnittet, som i det här fallet delar upp en (sub-)array i mindre sub-arrayer. Klassen använder en hjälparfunktionspartition (...) som implementerar det välkända QuickSort-pivot- och växlingsschemat.

     

 
    
        
         
        
           
                            
        
     
 
 public  class  SplitList  implementerar  Split  <  Range  ,  Range  >  {  @Override  public  Range  []  split  (  Range  r  ) {  int  i  =  partition  (  r  .  array  ,  r  .  left  ,  r  .  right  );  Intervall för  intervall  []  =  {  new  Range  (  r  .  array  ,  r  .  left  ,  i  -  1  ),  new  Range  (  r  .  array  ,  i  +  1  ,  r  .  right  )};  returintervaller  ;  _  }  }

Klassen Sorter implementerar och Execute-gränssnittet och är ansvarig för att sortera sub-arrayen som specificeras av Range r . I det här fallet anropar vi helt enkelt Javas standardmetod (Arrays.sort) för den givna undermatrisen.

      

  
     
		
         
		
      
		
     
  
 public  class  Sortera  implementerar  Execute  <  Range  ,  Range  >  {  @Override  public  Range  execute  (  Range  r  ){  if  (  r  .  right  <=  r  .  left  )  return  r  ;  Arrayer  .  sortera  (  r  .  array  ,  r  .  left  ,  r  .  right  +  1  );  returnera  r  ;  }  }

Slutligen, när en uppsättning underarrayer är sorterade slår vi samman underarraydelarna till en större array med MergeList-klassen som implementerar ett Merge-gränssnitt.

     

  
     
		
         0 0 
		
     
  
 public  class  MergeList  implementerar  Merge  <  Range  ,  Range  >  {  @Override  public  Range  merge  (  Range  [ ]  r  ) {  Range  result  =  new  Range  (  r  [  ]  .  array  ,  r  [  ]  .  left  ,  r  [  1  ]  .  right  );  returnera  resultat  ;  }  }

Ramar och bibliotek

HJÄLPA

ASSIST är en programmeringsmiljö som ger programmerare ett strukturerat koordinationsspråk. Koordinationsspråket kan uttrycka parallella program som en godtycklig graf av mjukvarumoduler. Moduldiagrammet beskriver hur en uppsättning moduler interagerar med varandra med hjälp av en uppsättning typdataströmmar. Modulerna kan vara sekventiella eller parallella. Sekventiella moduler kan skrivas i C, C++ eller Fortran; och parallella moduler programmeras med en speciell ASSIST parallellmodul ( parmod ).

AdHoc, ett hierarkiskt och feltolerant Distributed Shared Memory (DSM) system används för att koppla samman dataströmmar mellan bearbetningselement genom att tillhandahålla ett arkiv med: get/put/remove/exekvera operationer. Forskning kring AdHoc har fokuserat på transparens, skalbarhet och feltolerans för dataförrådet.

Även om det inte är ett klassiskt skelettramverk, i den meningen att inga skelett tillhandahålls, kan ASSIST:s generiska parmod specialiseras på klassiska skelett såsom: farm , map , etc. ASSIST stöder också autonom kontroll av parmods och kan vara föremål för ett prestationskontrakt genom att dynamiskt anpassa antalet resurser som används.

CO2P3S

CO2P3S (Correct Object-Oriented Pattern-based Parallel Programming System), är en mönsterorienterad utvecklingsmiljö, som uppnår parallellism med hjälp av trådar i Java.

CO2P3S handlar om hela utvecklingsprocessen av en parallell applikation. Programmerare interagerar genom ett programmeringsgränssnitt för att välja ett mönster och dess konfigurationsalternativ. Sedan fyller programmerare de krokar som krävs för mönstret, och ny kod genereras som ett ramverk i Java för parallell exekvering av applikationen. Det genererade ramverket använder tre nivåer, i fallande abstraktionsordning: mönsterlager, mellankodlager och inbyggt kodlager. Således kan avancerade programmerare ingripa den genererade koden på flera nivåer för att ställa in prestandan för sina applikationer. Den genererade koden är för det mesta typsäker , med hjälp av de typer som tillhandahålls av programmeraren som inte kräver förlängning av superklass, men som inte är helt typsäker som i reducer(..., Object reducer)-metoden i mesh-mönstret.

Uppsättningen mönster som stöds i CO2P3S motsvarar metodsekvens, distributör, mesh och vågfront. Komplexa applikationer kan byggas genom att komponera ramverk med deras objektreferenser. Icke desto mindre, om inget mönster är lämpligt, adresserar MetaCO2P3S grafiska verktyg utökbarhet genom att tillåta programmerare att modifiera mönsterdesignerna och introducera nya mönster i CO2P3S.

Stöd för distribuerade minnesarkitekturer i CO2P3S introducerades senare. För att använda ett distribuerat minnesmönster måste programmerare ändra mönstrets minnesalternativ från delat till distribuerat och generera den nya koden. Ur ett användningsperspektiv kräver den distribuerade minnesversionen av koden hantering av avlägsna undantag.

Kalcium & Skandium

Kalcium är mycket inspirerat av Litium och Muskel. Som sådan tillhandahåller den algoritmisk skelettprogrammering som ett Java-bibliotek. Både uppgifts- och dataparallella skelett är fullt kapslingsbara; och instansieras via parametriska skelettobjekt, inte arv.

Kalcium stöder exekvering av skelettapplikationer ovanpå ProActive- miljön för distribuerad klusterliknande infrastruktur. Dessutom har kalcium tre utmärkande egenskaper för algoritmisk skelettprogrammering. Först, en prestandajusteringsmodell som hjälper programmerare att identifiera kod som är ansvarig för prestandabuggar. För det andra, ett typsystem för kapslingsbara skelett som har visat sig garantera ämnesreducerande egenskaper och implementeras med Java Generics. För det tredje, en transparent algoritmisk skelettfilåtkomstmodell, som möjliggör skelett för dataintensiva applikationer.

Skandium är en komplett omimplementering av Calcium för multi-core computing. Program skrivna på Skandium kan dra fördel av delat minne för att förenkla parallell programmering.

Eden

Eden är ett parallellt programmeringsspråk för distribuerade minnesmiljöer, vilket utökar Haskell. Processer definieras explicit för att uppnå parallell programmering, medan deras kommunikation förblir implicit. Processer kommunicerar genom enkelriktade kanaler, som kopplar en skribent till exakt en läsare. Programmerare behöver bara specificera vilka data en bearbetning är beroende av. Edens processmodell ger direkt kontroll över processgranularitet, datadistribution och kommunikationstopologi.

Eden är inte ett skelettspråk i den meningen att skelett inte tillhandahålls som språkkonstruktioner. Istället definieras skelett ovanpå Edens processabstraktion på lägre nivå, vilket stöder både uppgifts- och dataparallellism . Så, i motsats till de flesta andra tillvägagångssätt, låter Eden skeletten definieras på samma språk och på samma nivå skrivs skelettinstanseringen: Eden själv. Eftersom Eden är en förlängning av ett funktionellt språk, är Eden-skelett funktioner av högre ordning . Eden introducerar konceptet implementeringsskelett, som är ett arkitekturoberoende schema som beskriver en parallell implementering av ett algoritmiskt skelett.

eSkel

Edinburgh Skeleton Library ( eSkel ) tillhandahålls i C och körs ovanpå MPI. Den första versionen av eSkel beskrevs i, medan en senare version presenteras i.

I, kapslingsläge och interaktionsläge för skelett definieras. Kapslingsläget kan vara antingen övergående eller beständigt, medan interaktionsläget kan vara antingen implicit eller explicit. Övergående kapsling innebär att det kapslade skelettet instansieras för varje anrop och förstörs efteråt, medan persistent betyder att skelettet instansieras en gång och samma skelettinstans kommer att anropas under hela applikationen. Implicit interaktion innebär att dataflödet mellan skelett är helt definierat av skelettets sammansättning, medan explicit innebär att data kan genereras eller tas bort från flödet på ett sätt som inte specificeras av skelettets sammansättning. Till exempel, ett skelett som producerar en utdata utan att någonsin ta emot en input har explicit interaktion.

Prestandaprediktion för schemaläggning och resurskartläggning, främst för rörledningar, har utforskats av Benoit et al. De tillhandahöll en prestandamodell för varje mappning, baserad på processalgebra, och bestämmer den bästa schemaläggningsstrategin baserat på resultaten av modellen.

Nyare arbeten har tagit upp problemet med anpassning av strukturerad parallell programmering, särskilt för rörskelettet.

Snabbt flöde

FastFlow är ett skelettparallellt programmeringsramverk specifikt inriktat på utveckling av streaming- och dataparallella applikationer. Ursprungligen utvecklad för att rikta in sig på flerkärniga plattformar, har den successivt utökats till att rikta in sig på heterogena plattformar som består av kluster av plattformar med delat minne, möjligen utrustade med datoracceleratorer som NVidia GPGPU, Xeon Phi, Tilera TILE64. FastFlows huvudsakliga designfilosofi är att förse applikationsdesigners med nyckelfunktioner för parallell programmering (t.ex. time-to-market, portabilitet, effektivitet och prestandaportabilitet) via lämpliga parallellprogrammeringsabstraktioner och ett noggrant designat runtime-stöd. FastFlow är ett generellt C++-programmeringsramverk för heterogena parallella plattformar. Liksom andra högnivåprogrammeringsramverk, som Intel TBB och OpenMP, förenklar den designen och konstruktionen av bärbara parallella applikationer. Den har dock en tydlig kant i termer av uttrycksfullhet och prestanda med avseende på andra parallella programmeringsramverk i specifika tillämpningsscenarier, inklusive bland annat: finkornig parallellism på cache-koherenta plattformar för delat minne; streamingapplikationer; kopplad användning av multi-core och acceleratorer. I andra fall FastFlow vanligtvis jämförbar med (och är i vissa fall något snabbare än) toppmoderna parallella programmeringsramverk som Intel TBB, OpenMP, Cilk, etc.

HDC

Higher-order Divide and Conquer ( HDC ) är en delmängd av det funktionella språket Haskell . Funktionella program presenteras som polymorfa funktioner av högre ordning, som kan kompileras till C/MPI och kopplas till skelettimplementeringar. Språket fokuserar på söndra och erövra paradigm, och med utgångspunkt från en allmän typ av söndra och erövra skelett, härleds mer specifika fall med effektiva implementeringar. De specifika fallen motsvarar: fast rekursionsdjup, konstant rekursionsgrad, multipelblocksrekursion, elementvisa operationer och korrespondentkommunikation

HDC ägnar särskild uppmärksamhet åt delproblemets granularitet och dess samband med antalet tillgängliga processorer. Det totala antalet processorer är en nyckelparameter för skelettprogrammets prestanda eftersom HDC strävar efter att uppskatta en adekvat tilldelning av processorer för varje del av programmet. Sålunda är applikationens prestanda starkt relaterad till det uppskattade antalet processorer, vilket antingen leder till ett överskridande av antalet delproblem eller inte tillräckligt med parallellitet för att utnyttja tillgängliga processorer.

HOC-SA

HOC-SA är ett Globus Incubator-projekt . HOC-SA står för Higher-Order Components-Service Architecture. Higher-Order Components ( HOCs ) har som syfte att förenkla Grid-applikationsutveckling. Målet med HOC-SA är att förse Globus-användare, som inte vill veta om alla detaljer i Globus-mellanvaran (GRAM RSL-dokument, webbtjänster och resurskonfiguration etc.), med HOC:er som tillhandahåller ett gränssnitt på högre nivå för att Grid än kärnan Globus Toolkit. HOC är Grid-aktiverade skelett, implementerade som komponenter ovanpå Globus Toolkit, fjärråtkomliga via webbtjänster.

JaSkel

JaSkel är ett Java-baserat skelettramverk som tillhandahåller skelett som farm, pipe och heartbeat. Skelett är specialiserade med hjälp av arv. Programmerare implementerar de abstrakta metoderna för varje skelett för att tillhandahålla sin applikationsspecifika kod. Skelett i JaSkel tillhandahålls i både sekventiella, samtidiga och dynamiska versioner. Till exempel kan den samtidiga gården användas i delade minnesmiljöer (trådar), men inte i distribuerade miljöer (kluster) där den distribuerade gården ska användas. För att byta från en version till en annan måste programmerare ändra sina klassers signatur för att ärva från ett annat skelett. Byggandet av skelett använder den grundläggande Java Object-klassen, och därför tillämpas inget typsystem under skelettsammansättningen.

Distributionsaspekterna av beräkningen hanteras i JaSkel med hjälp av AOP, mer specifikt AspectJ-implementeringen. Således JaSkel distribueras på både kluster- och Grid-liknande infrastrukturer. Ändå är en nackdel med JaSkel -metoden att häckningen av skelettet strikt relaterar till utbyggnadsinfrastrukturen. Således ger en dubbel häckning av gård bättre prestanda än en enskild gård på hierarkisk infrastruktur. Detta motverkar syftet med att använda AOP för att separera distributions- och funktionsproblemen för skelettprogrammet.

Litium & Muskel

Litium och dess efterföljare Muskel är skeleton frameworks utvecklade vid University of Pisa, Italien. Båda tillhandahåller kapslingsbara skelett till programmeraren som Java-bibliotek. Utvärderingen av en skelettapplikation följer en formell definition av operativ semantik introducerad av Aldinucci och Danelutto, som kan hantera både uppgifts- och dataparallellism. Semantiken beskriver både funktionellt och parallellt beteende hos skelettspråket med hjälp av ett märkt övergångssystem. Dessutom tillämpas flera prestandaoptimeringar, såsom: omskrivningstekniker för skelett [18, 10], framtida uppgift och server-till-server lat bindning.

På implementeringsnivån utnyttjar Lithium makrodataflödet för att uppnå parallellitet. När ingångsströmmen tar emot en ny parameter, bearbetas skelettprogrammet för att erhålla en makrodataflödesgraf. Noderna i grafen är makrodataflödesinstruktioner (MDFi) som representerar de sekventiella kodbitarna som tillhandahålls av programmeraren. Uppgifter används för att gruppera flera MDFi och konsumeras av inaktiva bearbetningselement från en uppgiftspool. När beräkningen av grafen är avslutad, placeras resultatet i utgångsströmmen och levereras därmed tillbaka till användaren.

Muskel tillhandahåller även icke-funktionella funktioner som Quality of Service (QoS); säkerhet mellan uppgiftspoolen och tolkarna; och resursupptäckt, lastbalansering och feltolerans vid gränssnitt med Java / Jini Parallel Framework (JJPF), ett distribuerat exekveringsramverk. Muskel ger också stöd för att kombinera strukturerad med ostrukturerad programmering och nyare forskning har tagit upp utbyggbarhet.

Mallba

Mallba är ett bibliotek för kombinatoriska optimeringar som stöder exakta, heuristiska och hybrida sökstrategier. Varje strategi implementeras i Mallba som ett generiskt skelett som kan användas genom att tillhandahålla den nödvändiga koden. På de exakta sökalgoritmerna tillhandahåller Mallba gren-och-bundna och dynamiska optimeringsskelett. För lokal sökheuristik stöder Mallba: bergsklättring , metropol, simulerad glödgning och tabusökning ; och även populationsbaserad heuristik härledd från evolutionära algoritmer såsom genetiska algoritmer , evolutionsstrategi och andra (CHC). Hybridskeletten kombinerar strategier, såsom: GASA, en blandning av genetisk algoritm och simulerad annealing, och CHCCES som kombinerar CHC och ES.

Skeletten tillhandahålls som ett C++-bibliotek och är inte kapslingsbara utan typsäkra. Ett anpassat MPI-abstraktionslager används, NetStream, som tar hand om primitiv datatypsrangering, synkronisering, etc. Ett skelett kan ha flera parallella implementeringar på lägre nivå beroende på målarkitekturerna: sekventiell, LAN och WAN. Till exempel: centraliserad master-slave, distribuerad master-slave, etc.

Mallba tillhandahåller även tillståndsvariabler som håller sökskelettets tillstånd. Staten kopplar sökningen till miljön och kan nås för att inspektera utvecklingen av sökningen och besluta om framtida åtgärder. Tillståndet kan till exempel användas för att lagra den bästa lösningen som hittats hittills, eller α, β-värden för gren- och bunden beskärning.

Jämfört med andra ramverk är Mallbas användning av skelettkoncept unik. Skelett tillhandahålls som parametriska sökstrategier snarare än parametriska parallelliseringsmönster.

Märg

Marrow är ett C++ algoritmiskt skelettramverk för orkestrering av OpenCL -beräkningar i, möjligen heterogena, multi- GPU -miljöer. Den tillhandahåller en uppsättning av både uppgifts- och dataparallella skelett som kan komponeras, genom kapsling, för att bygga sammansatta beräkningar. Bladnoderna i de resulterande sammansättningsträden representerar GPU-beräkningskärnorna, medan de återstående noderna betecknar skelettet som appliceras på det kapslade underträdet. Ramverket tar på sig hela värdsidans orkestrering som krävs för att korrekt exekvera dessa träd i heterogena multi-GPU-miljöer, inklusive korrekt ordning av dataöverföringen och exekveringsförfrågningarna, och den kommunikation som krävs mellan trädets noder.

Bland Marrows mest utmärkande funktioner är en uppsättning skelett som tidigare inte var tillgängliga i GPU-sammanhang, såsom Pipeline och Loop, och skelettkapslingsförmågan – en funktion som också är ny i detta sammanhang. Dessutom introducerar ramverket optimeringar som överlappar kommunikation och beräkning, vilket maskerar latensen som påläggs av PCIe -bussen.

Den parallella exekveringen av ett Marrow-kompositionsträd av flera GPU:er följer en dataparallell nedbrytningsstrategi, som samtidigt applicerar hela beräkningsträdet på olika partitioner av indatauppsättningen. Förutom att uttrycka vilka kärnparametrar som kan dekomponeras och, vid behov, definiera hur de delresultaten ska slås samman, är programmeraren helt abstraherad från den underliggande multi-GPU-arkitekturen.

Mer information, såväl som källkoden, finns på Marrows webbplats

Mysli

Muenster Skeleton Library Muesli är ett C++-mallbibliotek som återimplementerar många av idéerna och koncepten som introducerades i Skil , t.ex. funktioner av högre ordning, currying och polymorfa typer [1] . Den är byggd ovanpå MPI 1.2 och OpenMP 2.5 och stöder, till skillnad från många andra skelettbibliotek, både uppgifts- och dataparallella skelett. Skelettkapsling (sammansättning) liknar metoden med två nivåer av P3L , dvs. uppgiftsparallella skelett kan kapslas godtyckligt medan dataparallella skelett inte kan, utan kan användas vid bladen av ett uppgiftsparallellt häckande träd. C++-mallar används för att göra skelett polymorfa, men inget typsystem tillämpas. Biblioteket implementerar dock en automatiserad serialiseringsmekanism inspirerad av sådan att, förutom de vanliga MPI-datatyperna, godtyckliga användardefinierade datatyper kan användas inom skeletten. De parallella uppgiftsskeletten som stöds är Branch & Bound, Divide & Conquer, Farm och Pipe, hjälpskelett är Filter, Final och Initial. Dataparallella skelett, såsom vik (förminska), map, permute, zip och deras varianter implementeras som högre ordningsmedlemsfunktioner i en distribuerad datastruktur. För närvarande stöder Muesli distribuerade datastrukturer för arrayer, matriser och glesa matriser.

Som en unik funktion skalas Mueslis dataparallella skelett automatiskt både på en- och på multi-core, multi-nod klusterarkitekturer. Här säkerställs skalbarhet över noder och kärnor genom att samtidigt använda MPI respektive OpenMP. Den här funktionen är dock valfri i den meningen att ett program skrivet med Muesli fortfarande kompilerar och körs på en enkelkärnig, multi-nod klusterdator utan ändringar i källkoden, dvs bakåtkompatibilitet garanteras. Detta säkerställs genom att tillhandahålla ett mycket tunt OpenMP-abstraktionslager så att stödet för flerkärniga arkitekturer kan slås på/av genom att helt enkelt tillhandahålla/utelämna OpenMP-kompilatorflaggan när programmet kompileras. Genom att göra det introduceras praktiskt taget ingen overhead under körning.

P3L, SKIE, SKElib

P3L (Pisa Parallel Programming Language) är ett skelettbaserat koordinationsspråk. P3L tillhandahåller skelettkonstruktioner som används för att koordinera parallell eller sekventiell exekvering av C-kod. En kompilator som heter Anacleto tillhandahålls för språket. Anacleto använder implementeringsmallar för att kompilera P3 L-kod till en målarkitektur. Således kan ett skelett ha flera mallar var och en optimerad för en annan arkitektur. En mall implementerar ett skelett på en specifik arkitektur och tillhandahåller en parametrisk processgraf med en prestandamodell. Prestandamodellen kan sedan användas för att bestämma programtransformationer som kan leda till prestandaoptimeringar.

En P3L- modul motsvarar en korrekt definierad skelettkonstruktion med in- och utströmmar och andra undermoduler eller sekventiell C-kod. Moduler kan kapslas med hjälp av tvånivåmodellen, där den yttre nivån består av parallella uppgiftsskelett, medan dataparallella skelett kan användas på den inre nivån [64]. Typverifiering utförs på dataflödesnivå, när programmeraren uttryckligen specificerar typen av in- och utströmmar, och genom att specificera dataflödet mellan undermoduler.

SkIE (Skeleton-based Integrated Environment) är ganska lik P3L , eftersom den också bygger på ett koordinationsspråk, men ger avancerade funktioner som felsökningsverktyg, prestandaanalys, visualisering och grafiskt användargränssnitt. Istället för att direkt använda koordinationsspråket interagerar programmerare med ett grafiskt verktyg, där parallella moduler baserade på skelett kan komponeras.

SKELib bygger på bidragen från P3L och SkIE genom att ärva bland annat mallsystemet. Det skiljer sig från dem eftersom ett koordinationsspråk inte längre används, utan istället tillhandahålls skelett som ett bibliotek i C, med prestanda liknande den som uppnås i P3L . Till skillnad från Skil , en annan C-liknande skelettram, tas typsäkerhet inte upp i SKELib .

PAS och EPAS

PAS (Parallel Architectural Skeletons) är ett ramverk för skelettprogrammering utvecklat i C++ och MPI. Programmerare använder en förlängning av C++ för att skriva sina skelettapplikationer1. Koden skickas sedan genom ett Perl-skript som utökar koden till ren C++ där skelett är specialiserade genom arv.

I PAS har varje skelett ett Representativt (Rep) objekt som måste tillhandahållas av programmeraren och som ansvarar för att koordinera skelettets exekvering. Skelett kan kapslas på ett hierarkiskt sätt via Rep-objekten. Förutom skelettets exekvering, hanterar representanten också explicit mottagningen av data från skelettet på högre nivå och sändningen av data till underskeletten. Ett parametriserat kommunikations-/synkroniseringsprotokoll används för att skicka och ta emot data mellan föräldra- och underskelett.

En förlängning av PAS märkt som SuperPas och senare som EPAS tar itu med skelettets utvidgningsproblem. Med EPAS- verktyget kan nya skelett läggas till PAS . Ett Skeleton Description Language (SDL) används för att beskriva skelettmönstret genom att specificera topologin med avseende på ett virtuellt processornät. SDL kan sedan kompileras till inbyggd C++-kod, som kan användas som vilket annat skelett som helst.

SBASCO

SBASCO ( Skeleton-Based Scientific Components ) är en programmeringsmiljö inriktad mot effektiv utveckling av parallella och distribuerade numeriska applikationer. SBASCO strävar efter att integrera två programmeringsmodeller: skelett och komponenter med ett anpassat kompositionsspråk. En applikationsvy av en komponent ger en beskrivning av dess gränssnitt (in- och utgångstyp); medan en konfigurationsvy dessutom ger en beskrivning av komponentens interna struktur och processorlayout. En komponents inre struktur kan definieras med hjälp av tre skelett: gård, rör och multiblock.

SBASCO: s adresserar domännedbrytbara applikationer genom dess flerblocksskelett. Domäner specificeras genom arrayer (främst tvådimensionella), som sönderdelas till sub-arrayer med möjliga överlappande gränser. Beräkningen sker sedan på ett iterativt BSP-liknande sätt. Det första steget består av lokala beräkningar, medan det andra steget utför gränsväxlingar. Ett användningsfall presenteras för ett reaktionsdiffusionsproblem i.

Två typer av komponenter presenteras i. Scientific Components (SC) som tillhandahåller den funktionella koden; och Communication Aspect Components (CAC) som kapslar in icke-funktionellt beteende såsom kommunikation, distributionsprocessorlayout och replikering. Till exempel är SC-komponenter anslutna till en CAC-komponent som kan fungera som en hanterare vid körning genom att dynamiskt ommappning av processorer som tilldelats en SC. Ett användningsfall som visar förbättrad prestanda vid användning av CAC-komponenter visas i.

SCL

The Structured Coordination Language ( SCL ) var ett av de tidigaste skelettprogrammeringsspråken. Den tillhandahåller en koordinerande språkansats för skelettprogrammering över mjukvarukomponenter. SCL anses vara ett basspråk och designades för att integreras med ett värdspråk, till exempel Fortran eller C, som används för att utveckla sekventiella programvarukomponenter. I SCL klassificeras skelett i tre typer: konfiguration , elementär och beräkning . Konfigurationsskelett abstrakta mönster för vanliga datastrukturer som distribuerade arrayer (ParArray). Elementära skelett motsvarar dataparallella skelett som karta, skanna och vik. Beräkningsskelett som abstraherar kontrollflödet och motsvarar huvudsakligen uppgift parallella skelett som farm, SPMD och iterateUntil. Koordinationsspråksmetoden användes i samband med prestandamodeller för programmering av traditionella parallella maskiner såväl som parallella heterogena maskiner som har olika flera kärnor på varje bearbetningsnod.

SkePU

SkePU SkePU är ett skelettprogrammeringsramverk för flerkärniga processorer och multi-GPU-system. Det är ett C++-mallbibliotek med sex dataparallella och ett uppgiftsparallella skelett, två containertyper och stöd för exekvering på multi-GPU-system både med CUDA och OpenCL. Nyligen har stöd för hybridexekvering, prestandamedveten dynamisk schemaläggning och lastbalansering utvecklats i SkePU genom att implementera en backend för StarPU runtime-systemet. SkePU utökas för GPU-kluster.

SKiPPER & QUAFF

SKiPPER är ett domänspecifikt skelettbibliotek för visionapplikationer som tillhandahåller skelett i CAML, och därför förlitar sig på CAML för typsäkerhet. Skelett presenteras på två sätt: deklarativa och operativa. Deklarativa skelett används direkt av programmerare, medan deras operativa versioner ger en arkitekturspecifik målimplementering. Från runtime-miljön, CAML-skelettspecifikationer och applikationsspecifika funktioner (tillhandahålls i C av programmeraren) genereras och kompileras ny C-kod för att köra applikationen på målarkitekturen. En av de intressanta sakerna med SKiPPER är att skelettprogrammet kan köras sekventiellt för felsökning.

Olika tillvägagångssätt har utforskats i SKiPPER för att skriva operativa skelett: statiska dataflödesgrafer, parametriska processnätverk, hierarkiska uppgiftsgrafer och taggade dataflödesgrafer.

QUAFF är ett nyare skelettbibliotek skrivet i C++ och MPI. QUAFF förlitar sig på mallbaserade metaprogrammeringstekniker för att minska runtime overheads och utföra skelettexpansioner och optimeringar vid kompilering. Skelett kan kapslas och sekventiella funktioner är tillståndsbestämda. Förutom typkontroll utnyttjar QUAFF C++-mallar för att generera, vid kompilering, ny C/MPI-kod. QUAFF bygger på CSP-modellen, där skelettprogrammet beskrivs som ett processnätverk och produktionsregler (enkel, seriell, par, join).

SkeTo

SkeTo - projektet är ett C++-bibliotek som uppnår parallellisering med hjälp av MPI. SkeTo skiljer sig från andra skelettbibliotek eftersom istället för att tillhandahålla kapslingsbara parallellismmönster, tillhandahåller SkeTo parallella skelett för parallella datastrukturer som: listor, träd och matriser. Datastrukturerna skrivs med hjälp av mallar och flera parallella operationer kan anropas på dem. Till exempel ger liststrukturen parallella operationer som: mappa, reducera, skanna, zippa, shift, etc...

Ytterligare forskning kring SkeTo har också fokuserat på optimeringsstrategier genom transformation, och på senare tid domänspecifika optimeringar. Till exempel SkeTo en fusionstransformation som slår samman två på varandra följande funktionsanrop till en enda, vilket på så sätt minskar funktionsanropskostnaderna och undviker skapandet av mellanliggande datastrukturer som skickas mellan funktioner.

Skil

Skil är ett imperativt språk för skelettprogrammering. Skelett är inte direkt en del av språket utan implementeras med det. Skil använder en delmängd av C-språk som tillhandahåller funktionella språkliknande funktioner som funktioner av högre ordning, curring och polymorfa typer. När Skil kompileras elimineras sådana funktioner och en vanlig C-kod produceras. Således Skil polymorfa högordningsfunktioner till monomorfa första ordningens C-funktioner. Skil stöder inte nestbar sammansättning av skelett. Dataparallellism uppnås med hjälp av specifika dataparallella strukturer, till exempel för att sprida arrayer mellan tillgängliga processorer. Filterskelett kan användas.

STAPL Skeleton Framework

I STAPL Skeleton Framework definieras skelett som parametriska dataflödesgrafer, vilket låter dem skalas över 100 000 kärnor. Dessutom behandlar detta ramverk sammansättning av skelett som punkt-till-punkt sammansättning av deras motsvarande dataflödesgrafer genom begreppet portar, vilket gör att nya skelett enkelt kan läggas till ramverket. Som ett resultat eliminerar detta ramverk behovet av omimplementering och globala synkroniseringar i sammansatta skelett. STAPL Skeleton Framework stöder kapslad komposition och kan växla mellan parallell och sekventiell exekvering på varje nivå av kapsling. Detta ramverk drar nytta av skalbar implementering av STAPL parallella behållare och kan köra skelett på olika behållare inklusive vektorer, flerdimensionella arrayer och listor.

T4P

T4P var ett av de första systemen som introducerades för skelettprogrammering. Systemet förlitade sig mycket på funktionella programmeringsegenskaper, och fem skelett definierades som funktioner av högre ordning: Divide-and-Conquer, Farm, Map, Pipe och RMP. Ett program kan ha mer än en implementering, var och en med en kombination av olika skelett. Dessutom kan varje skelett ha olika parallella implementeringar. En metodik baserad på funktionella programtransformationer styrda av prestationsmodeller av skeletten användes för att välja det mest lämpliga skelettet som skulle användas för programmet samt den lämpligaste implementeringen av skelettet.

Ramverk jämförelse

Aktivitetsår är det kända aktivitetsåren. Datumen som representeras i denna kolumn motsvarar det första och sista publiceringsdatumet för en relaterad artikel i en vetenskaplig tidskrift eller konferensrapport. Observera att ett projekt fortfarande kan vara aktivt efter aktivitetsperioden och att vi inte har hittat en publikation för det efter det angivna datumet.
Programmeringsspråk är det gränssnitt med vilket programmerare interagerar för att koda sina skelettapplikationer. Dessa språk är olika och omfattar paradigm som: funktionella språk, koordinationsspråk, märkningsspråk, imperativa språk, objektorienterade språk och till och med grafiska användargränssnitt. Inuti programmeringsspråket har skelett tillhandahållits antingen som språkkonstruktioner eller bibliotek. Att tillhandahålla skelett som språkkonstruktion innebär utveckling av ett anpassat domänspecifikt språk och dess kompilator. Detta var helt klart den starkare trenden i början av skelettforskningen. Den nyare trenden är att tillhandahålla skelett som bibliotek, särskilt med objektorienterade språk som C++ och Java.
Exekveringsspråk är det språk som skelettapplikationerna körs eller kompileras på. Man insåg mycket tidigt att programmeringsspråken (speciellt i de funktionella fallen) inte var tillräckligt effektiva för att exekvera skelettprogrammen. Därför förenklades skelettprogrammeringsspråk genom att köra skelettapplikationer på andra språk. Transformationsprocesser introducerades för att konvertera skelettapplikationerna (definierade i programmeringsspråket) till en likvärdig applikation på målexekveringsspråket. Olika transformationsprocesser introducerades, såsom kodgenerering eller instansiering av skelett på lägre nivå (ibland kallade operativa skelett) som kunde interagera med ett bibliotek på exekveringsspråket. Den transformerade applikationen gav också möjlighet att introducera målarkitekturkod, anpassad för prestanda, i den transformerade applikationen. Tabell 1 visar att en favorit för exekveringsspråk har varit C-språket.
Distributionsbiblioteket tillhandahåller funktionaliteten för att uppnå parallella/distribuerade beräkningar. Den stora favoriten i denna mening har varit MPI, vilket inte är förvånande eftersom det integrerar bra med C-språket, och förmodligen är det mest använda verktyget för parallellism i klusterberäkningar. Farorna med att direkt programmera med distributionsbiblioteket är naturligtvis säkert gömda från programmerarna som aldrig interagerar med distributionsbiblioteket. På senare tid har trenden varit att utveckla skelettramverk som kan interagera med mer än ett distributionsbibliotek. Till exempel kan CO2 P3 S använda trådar, RMI eller uttag; Mallba kan använda Netstream eller MPI; eller JaSkel som använder AspectJ för att exekvera skelettapplikationerna på olika skelettramverk.
Typsäkerhet hänvisar till förmågan att upptäcka typinkompatibilitetsfel i skelettprogram. Eftersom de första skelettramverken byggdes på funktionella språk som Haskell, ärvdes typsäkerhet helt enkelt från värdspråket. Ändå, eftersom anpassade språk utvecklades för skelettprogrammering, måste kompilatorer skrivas för att ta hänsyn till typkontroll; vilket inte var så svårt eftersom skelett häckning inte var helt understödd. Men nyligen, när vi började hantera skelettramverk på objektorienterade språk med full kapsling, har typsäkerhetsproblemet dykt upp igen. Tyvärr har typkontroll mestadels förbisetts (med undantag för QUAFF), och speciellt i Java-baserade skelettramverk.
Skelettkapning är förmågan till hierarkisk sammansättning av skelettmönster. Skeleton Nesting identifierades som en viktig funktion i skelettprogrammering från allra första början, eftersom det tillåter sammansättningen av mer komplexa mönster med utgångspunkt från en grundläggande uppsättning enklare mönster. Ändå har det tagit lång tid för samhället att fullt ut stödja godtycklig häckning av skelett, främst på grund av svårigheterna med schemaläggning och typverifiering. Trenden är tydlig att nya skelettstomme stödjer fullständig häckning av skelett.
Filåtkomst är möjligheten att komma åt och manipulera filer från ett program. Tidigare har skelettprogrammering visat sig vara användbar mest för beräkningsintensiva applikationer, där små mängder data kräver stora mängder beräkningstid. Ändå kräver eller producerar många distribuerade applikationer stora mängder data under sin beräkning. Detta är fallet för astrofysik, partikelfysik, bioinformatik, etc. Att tillhandahålla filöverföringsstöd som integreras med skelettprogrammering är därför ett nyckelproblem som för det mesta har förbisetts.
Skelettuppsättning är listan över stödda skelettmönster. Skelettuppsättningar varierar mycket från ett ramverk till ett annat, och mer chockerande, vissa skelett med samma namn har olika semantik på olika ramverk. De vanligaste skelettmönstren i litteraturen är förmodligen gård, pipa och karta.

Icke-objektorienterade algoritmiska skelettramar
	Aktivitetsår	Programmeringsspråk	Exekveringsspråk	Distributionsbibliotek	Typ säker	Skelett häckande	Filåtkomst	Skelett set
HJÄLPA	2004–2007	Anpassat kontrollspråk	C++	TCP/IP + ssh/scp	Ja	Nej	explicit	seq, parmod
SBSACO	2004–2006	Anpassat kompositionsspråk	C++	MPI	Ja	Ja	Nej	gård, rör, multiblock
eSkel	2004–2005	C	C	MPI	Nej	?	Nej	pipeline, gård, affär, fjäril, hallowSwap
HDC	2004–2005	Haskell delmängd	C	MPI	Ja	?	Nej	dcA, dcB, dcD, dcE, dcF, map, red, scan, filter
SKELib	2000-2000	C	C	MPI	Nej	Nej	Nej	gård, rör
Skeppare	1999–2002	CAML	C	SynDex	Ja	begränsad	Nej	scm, df, tf, interm
SKIE	1999-1999	GUI/Anpassat kontrollspråk	C++	MPI	Ja	begränsad	Nej	pipe, farm, map, reduce, loop
Eden	1997–2011	Haskell förlängning	Haskell	PVM/MPI	Ja	Ja	Nej	karta, gård, arbetspool, nr, dc, rör, iterUntil, torus, ring
P3L	1995–1998	Anpassat kontrollspråk	C	MPI	Ja	begränsad	Nej	map, reduce, scan, comp, pipe, farm, seq, loop
Skil	1995–1998	C delmängd	C	?	Ja	Nej	Nej	pardata, karta, vik
SCL	1994–1999	Anpassat kontrollspråk	Fortran/C	MPI	Ja	begränsad	Nej	map, scan, fold, farm, SPMD, iterateUntil
T4P	1990–1994	Hope+	Hope+	CSTools	Ja	begränsad	Nej	D&C (Dela-och-härska), Karta, Rör, RAMP

Objektorienterade algoritmiska skelettramar
	Aktivitetsår	Programmeringsspråk	Exekveringsspråk	Distributionsbibliotek	Typ säker	Skelett häckande	Filåtkomst	Skelett set
Skandium	2009–2012	Java	Java	Trådar	Ja	Ja	Nej	seq, pipe, farm, for, while, map, d&c, gaffel
Snabbt flöde	2009–	C++	C++11 / CUDA / OpenCL	C++11 trådar / Posix trådar / TCP-IP / OFED-IB / CUDA / OpenCL	Ja	Ja	Ja	Pipeline, Farm, ParallelFor, ParallelForReduce, MapReduce, StencilReduce, PoolEvolution, MacroDataFlow
Kalcium	2006–2008	Java	Java	Proaktiv	Ja	Ja	Ja	seq, pipe, farm, for, while, map, d&c, gaffel
QUAFF	2006–2007	C++	C	MPI	Ja	Ja	Nej	seq, pipe, farm, scm, pardo
JaSkel	2006–2007	Java	Java/AspectJ	MPP / RMI	Nej	Ja	Nej	gård, pipeline, hjärtslag
Muskel	2005–2008	Java	Java	RMI	Nej	Ja	Nej	gård, rör, seq, + anpassade MDF-grafer
HOC-SA	2004–2008	Java	Java	Globus, KOALA	Nej	Nej	Nej	gård, pipeline, vågfront
SkeTo	2003–2013	C++	C++	MPI	Ja	Nej	Nej	lista, matris, träd
Mallba	2002–2007	C++	C++	NetStream / MPI	Ja	Nej	Nej	exakt, heuristisk, hybrid
Märg	2013–	C++	C++ plus OpenCL	(ingen)	Nej	Ja	Nej	dataparallell: map, map-reduce. uppgift parallell: pipeline, loop, för
Mysli	2002–2013	C++	C++	MPI / OpenMP	Ja	Ja	Nej	dataparallell: vikning, karta, permutering, scan, zip och varianter. uppgift parallell: förgrena & binda, dela & erövra, gård, rör. hjälpmedel: filter, slutlig, initial
Alt	2002–2003	Java/GworkflowDL	Java	Java RMI	Ja	Nej	Nej	map, zip, reducering, scan, dh, replikera, applicera, sortera
(E)PAS	1999–2005	C++ tillägg	C++	MPI	Nej	Ja	Nej	singleton, replikering, sammansättning, pipeline, divideconquer, dataparallell
Litium	1999–2004	Java	Java	RMI	Nej	Ja	Nej	röra, kartlägga, gård, reducera
CO2P3S	1999–2003	GUI/Java	Java (genererad)	Gängor / RMI / Uttag	Partiell	Nej	Nej	metod-sekvens, distributör, mesh, vågfront
STAPL	2010–	C++	C++11	STAPL Runtime Library (MPI, OpenMP, PThreads)	Ja	Ja	Ja	karta, zip , reducera, skanna, gård, (omvänd-)fjäril, (omvänd-)träd , rekursiv-dubblering, seriell, transponera, stencil , vågfront , allreduce, allgather, samla, strö, sända Operatörer: komponera, upprepa, gör-medan, gör-allt, gör-över

Se även