Algoritmisch skelet - Algorithmic skeleton

In de informatica zijn algoritmische skeletten of parallellismepatronen een parallel programmeermodel op hoog niveau voor parallel en gedistribueerd computergebruik.

Algoritmische skeletten maken gebruik van gemeenschappelijke programmeerpatronen om de complexiteit van parallelle en gedistribueerde toepassingen te verbergen. Uitgaande van een basisset van patronen (skeletten), kunnen complexere patronen worden gebouwd door de basispatronen te combineren.

Overzicht

Het meest opvallende kenmerk van algoritmische skeletten, dat ze onderscheidt van andere parallelle programmeermodellen op hoog niveau, is dat de orkestratie en synchronisatie van de parallelle activiteiten impliciet wordt bepaald door de skeletpatronen. Programmeurs hoeven de synchronisaties tussen de opeenvolgende delen van de applicatie niet op te geven. Dit levert twee implicaties op. Ten eerste, aangezien de communicatie/datatoegangspatronen van tevoren bekend zijn, kunnen kostenmodellen worden toegepast om skeletprogramma's te plannen. Ten tweede vermindert die algoritmische skeletprogrammering het aantal fouten in vergelijking met traditionele parallelle programmeermodellen op een lager niveau (Threads, MPI).

Voorbeeld programma

Het volgende voorbeeld is gebaseerd op de Java Skandium- bibliotheek voor parallel programmeren.

Het doel is om een ​​op Algorithmic Skeleton gebaseerde parallelle versie van het QuickSort- algoritme te implementeren met behulp van het Divide and Conquer-patroon. Merk op dat de benadering op hoog niveau Threadbeheer verbergt voor de programmeur.

// 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. Het eerste is om een ​​nieuwe instantie van het skelet te definiëren met de functionele code die het patroon vult (ShouldSplit, SplitList, Sort, MergeList). De functionele code wordt door de programmeur geschreven zonder zorgen over parallellisme.
2. De tweede stap is de invoer van gegevens die de berekening in gang zetten. In dit geval is Range een klasse met een array en twee indexen die de weergave van een subarray mogelijk maken. Voor elke gegevens die in het framework worden ingevoerd, wordt een nieuw Future-object gemaakt. Er kunnen meerdere Futures tegelijkertijd in een skelet worden ingevoerd.
3. De toekomst maakt asynchrone berekening mogelijk, omdat andere taken kunnen worden uitgevoerd terwijl de resultaten worden berekend.
4. We kunnen het resultaat van de berekening ophalen, eventueel blokkeren (dwz resultaten nog niet beschikbaar).

De functionele codes in dit voorbeeld komen overeen met vier typen Condition, Split, Execute en Merge.

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;
  }
}

De klasse ShouldSplit implementeert de interface Condition. De functie ontvangt een invoer, in dit geval Range r, en retourneert waar of onwaar. In de context van de Verdeel en heers waar deze functie zal worden gebruikt, zal deze beslissen of een sub-array opnieuw moet worden onderverdeeld of niet.

De klasse SplitList implementeert de split-interface, die in dit geval een (sub-)array opdeelt in kleinere subarrays. De klasse gebruikt een helperfunctie partition(...)die het bekende QuickSort pivot- en swapschema implementeert.

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;
 }
}

De klasse Sort implementeert en Execute-interface en is verantwoordelijk voor het sorteren van de subarray die is gespecificeerd door Range r. In dit geval roepen we eenvoudig Java's standaardmethode (Arrays.sort) op voor de gegeven subarray.

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;
  }
}

Ten slotte, als een set subarrays is gesorteerd, voegen we de subarray-onderdelen samen tot een grotere array met de MergeList-klasse die een Merge-interface implementeert.

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;
  }
}

Frameworks en bibliotheken

HELPEN

ASSIST is een programmeeromgeving die programmeurs voorziet van een gestructureerde coördinatietaal. De coördinatietaal kan parallelle programma's uitdrukken als een willekeurige grafiek van softwaremodules. De modulegrafiek beschrijft hoe een reeks modules met elkaar interageren met behulp van een reeks getypte gegevensstromen. De modules kunnen sequentieel of parallel zijn. Sequentiële modules kunnen worden geschreven in C, C++ of Fortran; en parallelle modules zijn geprogrammeerd met een speciale ASSIST parallelle module ( parmod ).

AdHoc, een hiërarchisch en fouttolerant Distributed Shared Memory (DSM)-systeem, wordt gebruikt om gegevensstromen tussen verwerkingselementen met elkaar te verbinden door een opslagplaats te bieden met: get/put/remove/execute-bewerkingen. Onderzoek rond AdHoc heeft zich gericht op transparantie, schaalbaarheid en fouttolerantie van de gegevensopslag.

Hoewel het geen klassiek skeletraamwerk is , in de zin dat er geen skeletten worden geleverd, kan de generieke parmod van ASSIST worden gespecialiseerd in klassieke skeletten zoals: boerderij , kaart , enz. ASSIST ondersteunt ook autonome controle van parmods , en kan onderworpen zijn aan een prestatiecontract door het aantal gebruikte middelen dynamisch aan te passen.

CO2P3S

CO2P3S (Correct Object-Oriented Pattern-based Parallel Programming System), is een patroongeoriënteerde ontwikkelomgeving die parallellisme bereikt met behulp van threads in Java.

CO2P3S houdt zich bezig met het volledige ontwikkelproces van een parallelle applicatie. Programmeurs communiceren via een programmeer-GUI om een ​​patroon en de bijbehorende configuratie-opties te kiezen. Vervolgens vullen programmeurs de haken die nodig zijn voor het patroon en wordt nieuwe code gegenereerd als een raamwerk in Java voor de parallelle uitvoering van de toepassing. Het gegenereerde raamwerk gebruikt drie niveaus, in aflopende volgorde van abstractie: patronenlaag, tussenliggende codelaag en native codelaag. Zo kunnen geavanceerde programmeurs de gegenereerde code op meerdere niveaus ingrijpen om de prestaties van hun applicaties af te stemmen. De gegenereerde code is meestal type safe , waarbij de typen worden gebruikt die door de programmeur worden geleverd en die geen uitbreiding van de superklasse vereisen, maar niet volledig type safe zijn, zoals in de methode reduce(..., Object reducer) in het mesh-patroon.

De reeks patronen die in CO2P3S wordt ondersteund, komt overeen met methodereeks, distributeur, mesh en golffront. Complexe applicaties kunnen worden gebouwd door frameworks samen te stellen met hun objectreferenties. Desalniettemin, als geen patroon geschikt is, biedt de grafische tool MetaCO2P3S uitbreidbaarheid door programmeurs in staat te stellen de patroonontwerpen aan te passen en nieuwe patronen in CO2P3S te introduceren.

Later werd ondersteuning voor gedistribueerde geheugenarchitecturen in CO2P3S geïntroduceerd. Om een ​​gedistribueerd geheugenpatroon te gebruiken, moeten programmeurs de geheugenoptie van het patroon wijzigen van gedeeld in gedistribueerd en de nieuwe code genereren. Vanuit het gebruiksperspectief vereist de gedistribueerde geheugenversie van de code het beheer van externe uitzonderingen.

Calcium & Skandium

Calcium is sterk geïnspireerd door Lithium en Muskel. Als zodanig biedt het algoritmische skeletprogrammering als een Java-bibliotheek. Zowel taak- als gegevensparallelle skeletten zijn volledig nestbaar; en worden geïnstantieerd via parametrische skeletobjecten, niet via overerving.

Calcium ondersteunt de uitvoering van skelettoepassingen bovenop de ProActive- omgeving voor gedistribueerde clusterachtige infrastructuur. Bovendien heeft Calcium drie onderscheidende kenmerken voor algoritmische skeletprogrammering. Ten eerste een prestatieafstemmingsmodel dat programmeurs helpt bij het identificeren van code die verantwoordelijk is voor prestatiefouten. Ten tweede, een typesysteem voor nestbare skeletten waarvan bewezen is dat het eigenschappen van subjectreductie garandeert en geïmplementeerd is met behulp van Java Generics. Ten derde, een transparant algoritmisch model voor toegang tot skeletbestanden, dat skeletten mogelijk maakt voor data-intensieve toepassingen.

Skandium is een complete herimplementatie van Calcium voor multi-core computing. Programma's die op Skandium zijn geschreven, kunnen gebruikmaken van gedeeld geheugen om parallel programmeren te vereenvoudigen.

Eden

Eden is een parallelle programmeertaal voor gedistribueerde geheugenomgevingen, die Haskell uitbreidt. Processen worden expliciet gedefinieerd om parallelle programmering te bereiken, terwijl hun communicatie impliciet blijft. Processen communiceren via unidirectionele kanalen, die één schrijver met precies één lezer verbinden. Programmeurs hoeven alleen aan te geven van welke gegevens een proces afhankelijk is. Het procesmodel van Eden biedt directe controle over procesgranulariteit, gegevensdistributie en communicatietopologie.

Eden is geen skelettaal in de zin dat skeletten niet worden geleverd als taalconstructies. In plaats daarvan worden skeletten gedefinieerd bovenop Eden's procesabstractie op een lager niveau, wat zowel taak- als gegevensparallellisme ondersteunt . Dus, in tegenstelling tot de meeste andere benaderingen, laat Eden de skeletten in dezelfde taal en op hetzelfde niveau definiëren, de skeletconstantiatie wordt geschreven: Eden zelf. Omdat Eden een uitbreiding is van een functionele taal, zijn Eden-skeletten functies van een hogere orde . Eden introduceert het concept van implementatieskelet, een architectuuronafhankelijk schema dat een parallelle implementatie van een algoritmisch skelet beschrijft.

eSkel

De Edinburgh Skeleton Library ( eSkel ) wordt geleverd in C en draait bovenop MPI. De eerste versie van eSkel werd beschreven in, terwijl een latere versie wordt gepresenteerd in.

In, nesting-modus en interactie-modus voor skeletten zijn gedefinieerd. De nesting-modus kan tijdelijk of persistent zijn, terwijl de interactiemodus impliciet of expliciet kan zijn. Tijdelijke nesting betekent dat het geneste skelet voor elke aanroep wordt geïnstantieerd en daarna wordt vernietigd, terwijl persistent betekent dat het skelet één keer wordt geïnstantieerd en dezelfde skeletinstantie in de hele toepassing wordt aangeroepen. Impliciete interactie betekent dat de gegevensstroom tussen skeletten volledig wordt bepaald door de skeletsamenstelling, terwijl expliciet betekent dat gegevens kunnen worden gegenereerd of verwijderd uit de stroom op een manier die niet wordt gespecificeerd door de skeletsamenstelling. Een skelet dat een uitvoer produceert zonder ooit een invoer te ontvangen, heeft bijvoorbeeld expliciete interactie.

Prestatievoorspelling voor planning en resourcetoewijzing, voornamelijk voor pijpleidingen, is onderzocht door Benoit et al. Ze leverden een prestatiemodel voor elke mapping, gebaseerd op procesalgebra, en bepaalden de beste planningsstrategie op basis van de resultaten van het model.

Meer recente werken hebben het probleem van de aanpassing aan gestructureerd parallel programmeren aangepakt, in het bijzonder voor het pijpskelet.

FastFlow

FastFlow is een skeletachtig parallel programmeerraamwerk dat specifiek is gericht op de ontwikkeling van streaming- en dataparallelle toepassingen. In eerste instantie ontwikkeld om multi-core platformste targeten, is het achtereenvolgens uitgebreid naar heterogene platforms die zijn samengesteld uit clusters van platforms met gedeeld geheugen, mogelijk uitgerust met computerversnellers zoals NVidia GPGPU's, Xeon Phi, Tilera TILE64. De belangrijkste ontwerpfilosofie van FastFlow is om applicatieontwerpers te voorzien van belangrijke functies voor parallel programmeren (bijv. time-to-market, portabiliteit, efficiëntie en prestatieportabiliteit) via geschikte parallelle programmeerabstracties en een zorgvuldig ontworpen runtime-ondersteuning. FastFlow is een algemeen C++ programmeerraamwerk voor heterogene parallelle platforms. Net als andere programmeerframeworks op hoog niveau, zoals Intel TBB en OpenMP, vereenvoudigt het het ontwerp en de engineering van draagbare parallelle toepassingen. Het heeft echter een duidelijke voorsprong op het gebied van expressiviteit en prestaties ten opzichte van andere parallelle programmeerframeworks in specifieke toepassingsscenario's, waaronder onder meer: ​​fijnkorrelig parallellisme op cache-coherente platforms met gedeeld geheugen; streaming-applicaties; gekoppeld gebruik van multi-core en accelerators. In andere gevallen is FastFlow doorgaans vergelijkbaar met (en is het in sommige gevallen iets sneller dan) geavanceerde parallelle programmeerframeworks zoals Intel TBB, OpenMP, Cilk, enz.

HDC

Verdeel en heers van hogere orde ( HDC ) is een subset van de functionele taal Haskell . Functionele programma's worden gepresenteerd als polymorfe functies van een hogere orde, die kunnen worden gecompileerd in C/MPI en gekoppeld aan skeletimplementaties. De taal focus op verdeel en heers paradigma, en uitgaande van een algemeen soort verdeel en heers skelet, worden meer specifieke gevallen met efficiënte implementaties afgeleid. De specifieke gevallen komen overeen met: vaste recursiediepte, constante recursiegraad, meervoudige blokrecursie, elementgewijze bewerkingen en corresponderende communicatie

HDC besteedt speciale aandacht aan de granulariteit van het subprobleem en de relatie met het aantal beschikbare processors. Het totale aantal processors is een belangrijke parameter voor de prestaties van het skeletprogramma, aangezien HDC ernaar streeft om voor elk onderdeel van het programma een adequate toewijzing van processors te schatten. De prestatie van de applicatie hangt dus sterk samen met het geschatte aantal processors, wat leidt tot ofwel een groter aantal subproblemen, ofwel niet genoeg parallellisme om de beschikbare processors te benutten.

HOC-SA

HOC-SA is een Globus Incubator-project .
HOC-SA staat voor Higher-Order Components-Service Architecture. Higher-Order Components ( HOC's ) hebben als doel de ontwikkeling van Grid-applicaties te vereenvoudigen.
Het doel van HOC-SA is om Globus-gebruikers, die niet alle details van de Globus-middleware (GRAM RSL-documenten, webservices en resourceconfiguratie enz.) willen weten, te voorzien van HOC's die een interface op een hoger niveau bieden voor the Grid dan de kern Globus Toolkit.
HOC's zijn Grid-enabled skeletten, geïmplementeerd als componenten bovenop de Globus Toolkit, op afstand toegankelijk via Web Services.

JaSkel

JaSkel is een op Java gebaseerd skeletraamwerk dat skeletten biedt zoals boerderij, pijp en hartslag. Skeletten zijn gespecialiseerd met behulp van overerving. Programmeurs implementeren de abstracte methoden voor elk skelet om hun applicatiespecifieke code te leveren. Skeletten in JaSkel worden geleverd in zowel sequentiële, gelijktijdige als dynamische versies. De concurrent farm kan bijvoorbeeld worden gebruikt in omgevingen met gedeeld geheugen (threads), maar niet in gedistribueerde omgevingen (clusters) waar de gedistribueerde farm moet worden gebruikt. Om van de ene versie naar de andere te gaan, moeten programmeurs de handtekening van hun klassen wijzigen om ze van een ander skelet te erven. Het nesten van skeletten maakt gebruik van de standaard Java Object-klasse, en daarom wordt er geen typesysteem afgedwongen tijdens het samenstellen van het skelet.

De distributieaspecten van de berekening worden afgehandeld in JaSkel met behulp van AOP, meer specifiek de AspectJ-implementatie. Zo kan JaSkel worden ingezet op zowel cluster- als grid-achtige infrastructuren. Desalniettemin is een nadeel van de JaSkel- aanpak dat het nesten van het skelet strikt verband houdt met de inzet-infrastructuur. Een dubbele nesting van boerderijen levert dus betere prestaties op dan een enkele boerderij op hiërarchische infrastructuren. Dit gaat voorbij aan het doel van het gebruik van AOP om de distributie en functionele zorgen van het skeletprogramma te scheiden.

Lithium & Muskel

Lithium en zijn opvolger Muskel zijn skeletraamwerken die zijn ontwikkeld aan de Universiteit van Pisa, Italië. Beide bieden nestbare skeletten aan de programmeur als Java-bibliotheken. De evaluatie van een skelettoepassing volgt een formele definitie van operationele semantiek geïntroduceerd door Aldinucci en Danelutto, die zowel taak- als gegevensparallellisme aankan. De semantiek beschrijft zowel functioneel als parallel gedrag van de skelettaal met behulp van een gelabeld overgangssysteem. Daarnaast worden verschillende prestatie-optimalisaties toegepast, zoals: skeleton herschrijftechnieken [18, 10], taak-lookahead en server-to-server lazy binding.

Op implementatieniveau maakt Lithium gebruik van de macrogegevensstroom om parallellisme te bereiken. Wanneer de invoerstroom een ​​nieuwe parameter ontvangt, wordt het skeletprogramma verwerkt om een ​​macrogegevensstroomgrafiek te verkrijgen. De knooppunten van de grafiek zijn macro-gegevensstroominstructies (MDFi) die de opeenvolgende stukjes code vertegenwoordigen die door de programmeur worden geleverd. Taken worden gebruikt om verschillende MDFi te groeperen en worden verbruikt door niet-actieve verwerkingselementen uit een takenpool. Wanneer de berekening van de grafiek is voltooid, wordt het resultaat in de uitvoerstroom geplaatst en dus teruggeleverd aan de gebruiker.

Muskel biedt ook niet-functionele functies zoals Quality of Service (QoS); beveiliging tussen taakpool en tolken; en resource discovery, load balancing en fouttolerantie bij interface met Java / Jini Parallel Framework (JJPF), een gedistribueerd uitvoeringsraamwerk. Muskel biedt ook ondersteuning voor het combineren van gestructureerd met ongestructureerd programmeren en recent onderzoek heeft zich gericht op uitbreidbaarheid.

Mallba

Mallba is een bibliotheek voor combinatorische optimalisaties die exacte, heuristische en hybride zoekstrategieën ondersteunt. Elke strategie wordt in Mallba geïmplementeerd als een generiek skelet dat kan worden gebruikt door de vereiste code te verstrekken. Voor de exacte zoekalgoritmen biedt Mallba branch-and-bound en dynamische optimalisatieskeletten. Voor lokale zoekheuristieken ondersteunt Mallba: heuvelklimmen , metropool, gesimuleerd gloeien en tabu-zoeken ; en ook populatiegebaseerde heuristieken afgeleid van evolutionaire algoritmen zoals genetische algoritmen , evolutiestrategie en andere (CHC). De hybride skeletten combineren strategieën, zoals: GASA, een mengsel van genetisch algoritme en gesimuleerd gloeien, en CHCCES dat CHC en ES combineert.

De skeletten worden geleverd als een C++-bibliotheek en zijn niet nestbaar maar typeveilig. Er wordt een aangepaste MPI-abstractielaag gebruikt, NetStream, die zorgt voor het rangschikken van primitieve gegevenstypes, synchronisatie, enz. Een skelet kan meerdere parallelle implementaties op een lager niveau hebben, afhankelijk van de doelarchitecturen: sequentieel, LAN en WAN. Bijvoorbeeld: gecentraliseerde master-slave, gedistribueerde master-slave, enz.

Mallba biedt ook toestandsvariabelen die de toestand van het zoekskelet bevatten. De staat verbindt de zoektocht met de omgeving en is toegankelijk om de evolutie van de zoekopdracht te inspecteren en te beslissen over toekomstige acties. De status kan bijvoorbeeld worden gebruikt om de beste oplossing die tot nu toe is gevonden op te slaan, of α, β-waarden voor tak- en gebonden snoeien.

In vergelijking met andere frameworks is het gebruik van skeletconcepten door Mallba uniek. Skeletten worden geleverd als parametrische zoekstrategieën in plaats van parametrische parallellisatiepatronen.

Merg

Marrow is een C++ algoritmisch skeletraamwerk voor de orkestratie van OpenCL- berekeningen in, mogelijk heterogene, multi- GPU- omgevingen. Het biedt een set van zowel taak- als gegevensparallelle skeletten die kunnen worden samengesteld, door middel van nesten, om samengestelde berekeningen te bouwen. De bladknooppunten van de resulterende compositiebomen vertegenwoordigen de GPU-computerkernen, terwijl de overige knooppunten het skelet aangeven dat op de geneste subboom is toegepast. Het framework neemt de volledige orkestratie aan de hostzijde op zich die nodig is om deze bomen correct uit te voeren in heterogene multi-GPU-omgevingen, inclusief de juiste volgorde van de gegevensoverdracht en de uitvoeringsverzoeken, en de vereiste communicatie tussen de knooppunten van de boom.

Tot de meest opvallende kenmerken van Marrow behoren een reeks skeletten die voorheen niet beschikbaar waren in de GPU-context, zoals Pipeline en Loop, en de mogelijkheid om skeletten te nesten - een functie die ook nieuw is in deze context. Bovendien introduceert het raamwerk optimalisaties die communicatie en berekening overlappen, waardoor de latentie die door de PCIe- bus wordt veroorzaakt , wordt gemaskeerd .

De parallelle uitvoering van een Marrow-samenstellingsboom door meerdere GPU's volgt een data-parallelle decompositiestrategie, die tegelijkertijd de volledige rekenboom toepast op verschillende partities van de invoergegevensset. Behalve het uitdrukken welke kernelparameters kunnen worden ontleed en, indien nodig, definiëren hoe de gedeeltelijke resultaten moeten worden samengevoegd, is de programmeur volledig geabstraheerd van de onderliggende multi-GPU-architectuur.

Meer informatie, evenals de broncode, is te vinden op de Marrow-website

Muesli

De Muenster Skeleton Library Muesli is een C++-sjabloonbibliotheek die veel van de ideeën en concepten die in Skil zijn geïntroduceerd opnieuw implementeert , bijv. functies van een hogere orde, currying en polymorfe typen [1] . Het is gebouwd op MPI 1.2 en OpenMP 2.5 en ondersteunt, in tegenstelling tot veel andere skeletbibliotheken, zowel taak- als gegevensparallelle skeletten. Het nesten van skeletten (compositie) is vergelijkbaar met de tweeledige benadering van P3L , dat wil zeggen dat taakparallelle skeletten willekeurig kunnen worden genest, terwijl gegevensparallelle skeletten dat niet kunnen, maar kunnen worden gebruikt aan de bladeren van een parallelle taakboom. C++-sjablonen worden gebruikt om skeletten polymorf te maken, maar er wordt geen typesysteem afgedwongen. De bibliotheek implementeert echter een geautomatiseerd serialisatiemechanisme dat erop is geïnspireerd, zodat, naast de standaard MPI-gegevenstypen, willekeurige door de gebruiker gedefinieerde gegevenstypen kunnen worden gebruikt binnen de skeletten. De parallelle skeletten van de ondersteunde taak zijn Branch & Bound, Divide & Conquer, Farm en Pipe, hulpskeletten zijn Filter, Final en Initial. Gegevensparallelle skeletten, zoals vouwen (verkleinen), kaart, permute, zip en hun varianten worden geïmplementeerd als lidfuncties van hogere orde van een gedistribueerde gegevensstructuur. Momenteel ondersteunt Muesli gedistribueerde datastructuren voor arrays, matrices en schaarse matrices.

Als unieke functie schalen Muesli's parallelle dataskeletten automatisch zowel op single- als op multi-core, multi-node clusterarchitecturen. Hier wordt schaalbaarheid over knooppunten en kernen verzekerd door gelijktijdig respectievelijk MPI en OpenMP te gebruiken. Deze functie is echter optioneel in die zin dat een programma dat met Muesli is geschreven nog steeds compileert en draait op een single-core, multi-node clustercomputer zonder wijzigingen in de broncode, dat wil zeggen dat achterwaartse compatibiliteit gegarandeerd is. Dit wordt gewaarborgd door een zeer dunne OpenMP-abstractielaag aan te bieden, zodat de ondersteuning van multi-core-architecturen kan worden in-/uitgeschakeld door simpelweg de OpenMP-compilervlag te voorzien/weg te laten bij het compileren van het programma. Hierdoor wordt tijdens runtime vrijwel geen overhead geïntroduceerd.

P3L, SkIE, SKElib

P3L (Pisa Parallel Programming Language) is een op een skelet gebaseerde coördinatietaal. P3L biedt skeletconstructies die worden gebruikt om de parallelle of sequentiële uitvoering van C-code te coördineren. Een compiler met de naam Anacleto is voorzien voor de taal. Anacleto gebruikt implementatiesjablonen om P3 L-code te compileren in een doelarchitectuur. Een skelet kan dus verschillende sjablonen hebben die elk zijn geoptimaliseerd voor een andere architectuur. Een sjabloon implementeert een skelet op een specifieke architectuur en levert een parametrische procesgrafiek met een prestatiemodel. Het prestatiemodel kan vervolgens worden gebruikt om programmatransformaties te bepalen die kunnen leiden tot prestatie-optimalisaties.

Een P3L- module komt overeen met een goed gedefinieerde skeletconstructie met invoer- en uitvoerstromen en andere submodules of sequentiële C-code. Modules kunnen worden genest met behulp van het tweelaagsmodel, waarbij het buitenste niveau is samengesteld uit parallelle taakskeletten, terwijl gegevensparallelle skeletten op het binnenste niveau kunnen worden gebruikt [64]. Typeverificatie wordt uitgevoerd op gegevensstroomniveau, wanneer de programmeur expliciet het type invoer- en uitvoerstromen specificeert, en door de gegevensstroom tussen submodules te specificeren.

SkIE (Skeleton-based Integrated Environment) lijkt veel op P3L , omdat het ook is gebaseerd op een coördinatietaal, maar biedt geavanceerde functies zoals debugging-tools, prestatie-analyse, visualisatie en grafische gebruikersinterface. In plaats van direct de coördinatietaal te gebruiken, werken programmeurs samen met een grafische tool, waarmee parallelle modules op basis van skeletten kunnen worden samengesteld.

SKELib bouwt voort op de bijdragen van P3L en SkIE door onder meer het sjabloonsysteem over te nemen. Het verschilt van hen omdat er geen coördinatietaal meer wordt gebruikt, maar in plaats daarvan worden skeletten geleverd als een bibliotheek in C, met vergelijkbare prestaties als die in P3L . In tegenstelling tot Skil , een ander C-achtig skeletraamwerk, wordt typeveiligheid niet behandeld in SKELib .

PAS en EPAS

PAS (Parallel Architectural Skeletons) is een raamwerk voor skeletprogrammering ontwikkeld in C++ en MPI. Programmeurs gebruiken een extensie van C++ om hun skelettoepassingen te schrijven1. De code wordt vervolgens door een Perl-script geleid dat de code uitbreidt naar pure C++ waar skeletten zijn gespecialiseerd door overerving.

In PAS heeft elk skelet een representatief (Rep) object dat door de programmeur moet worden aangeleverd en dat verantwoordelijk is voor de coördinatie van de uitvoering van het skelet. Skeletten kunnen hiërarchisch worden genest via de Rep-objecten. Naast de uitvoering van het skelet, beheert de Rep ook expliciet de ontvangst van gegevens van het skelet op een hoger niveau en het verzenden van gegevens naar de subskeletten. Een geparametriseerd communicatie-/synchronisatieprotocol wordt gebruikt om gegevens tussen ouder en subskeletten te verzenden en te ontvangen.

Een uitbreiding van PAS met het label SuperPas en later als EPAS pakt de problemen met de uitbreidbaarheid van het skelet aan. Met de EPAS- tool kunnen nieuwe skeletten aan PAS worden toegevoegd . Een Skeleton Description Language (SDL) wordt gebruikt om het skeletpatroon te beschrijven door de topologie te specificeren met betrekking tot een virtueel processorraster. De SDL kan vervolgens worden gecompileerd tot native C++-code, die als elk ander skelet kan worden gebruikt.

SBASCO

SBASCO ( Skelet-Based Scientific COmponents ) is een programmeeromgeving gericht op een efficiënte ontwikkeling van parallelle en gedistribueerde numerieke toepassingen. SBASCO streeft naar het integreren van twee programmeermodellen: skeletten en componenten met een aangepaste compositietaal. Een applicatieweergave van een component geeft een beschrijving van zijn interfaces (invoer- en uitvoertype); terwijl een configuratieweergave bovendien een beschrijving geeft van de interne structuur en de processorlay-out van de component. De interne structuur van een component kan worden gedefinieerd met behulp van drie skeletten: farm, pipe en multi-block.

SBASCO 's adresseert domein-decomposable applicaties door middel van zijn multi-block skelet. Domeinen worden gespecificeerd via arrays (voornamelijk tweedimensionaal), die worden ontleed in subarrays met mogelijk overlappende grenzen. De berekening vindt dan plaats op een iteratieve BSP-achtige manier. De eerste fase bestaat uit lokale berekeningen, terwijl de tweede fase grensuitwisselingen uitvoert. Er wordt een use case gepresenteerd voor een reactie-diffusieprobleem in.

Er worden twee soorten componenten gepresenteerd in: Scientific Components (SC) die de functionele code leveren; en Communication Aspect Components (CAC) die niet-functioneel gedrag inkapselen, zoals communicatie, indeling van de distributieprocessor en replicatie. SC-componenten zijn bijvoorbeeld verbonden met een CAC-component die tijdens runtime als manager kan fungeren door processors die aan een SC zijn toegewezen, dynamisch opnieuw toe te wijzen. Een use-case met verbeterde prestaties bij het gebruik van CAC-componenten wordt getoond in.

SCL

De Structured Coordination Language ( SCL ) was een van de eerste programmeertalen voor skeletten. Het biedt een coördinatietaalbenadering voor skeletprogrammering via softwarecomponenten. SCL wordt beschouwd als een basistaal en is ontworpen om te worden geïntegreerd met een hosttaal, bijvoorbeeld Fortran of C, die wordt gebruikt voor het ontwikkelen van sequentiële softwarecomponenten. In SCL worden skeletten ingedeeld in drie typen: configuratie , elementair en berekening . Configuratieskeletten abstracte patronen voor veelgebruikte datastructuren zoals gedistribueerde arrays (ParArray). Elementaire skeletten komen overeen met gegevensparallelle skeletten zoals kaart, scan en vouw. Berekeningsskeletten die de controlestroom abstraheren en voornamelijk overeenkomen met taakparallelle skeletten zoals farm, SPMD en iterateUntil. De coördinatietaalbenadering werd gebruikt in combinatie met prestatiemodellen voor het programmeren van traditionele parallelle machines en parallelle heterogene machines met verschillende kernen op elk verwerkingsknooppunt.

SkePU

SkePU SkePU is een skeletprogrammeerraamwerk voor multicore-CPU's en multi-GPU-systemen. Het is een C++-sjabloonbibliotheek met zes gegevensparallelle en één taakparallelle skeletten, twee containertypen en ondersteuning voor uitvoering op multi-GPU-systemen, zowel met CUDA als OpenCL. Onlangs is in SkePU ondersteuning voor hybride uitvoering, prestatiebewuste dynamische planning en taakverdeling ontwikkeld door een backend voor het StarPU-runtimesysteem te implementeren. SkePU wordt uitgebreid voor GPU-clusters.

SCHIPPER & QUAFF

SKiPPER is een domeinspecifieke skeletbibliotheek voor vision-toepassingen die skeletten in CAML levert en dus vertrouwt op CAML voor typeveiligheid. Skeletten worden op twee manieren gepresenteerd: declaratief en operationeel. Declaratieve skeletten worden direct gebruikt door programmeurs, terwijl hun operationele versies een architectuurspecifieke doelimplementatie bieden. Vanuit de runtime-omgeving, CAML-skeletspecificaties en applicatiespecifieke functies (geleverd in C door de programmeur), wordt nieuwe C-code gegenereerd en gecompileerd om de applicatie op de doelarchitectuur uit te voeren. Een van de interessante dingen van SKiPPER is dat het skeletprogramma achtereenvolgens kan worden uitgevoerd voor het debuggen.

In SKiPPER zijn verschillende benaderingen onderzocht voor het schrijven van operationele skeletten: statische datastroomgrafieken, parametrische procesnetwerken , hiërarchische taakgrafieken en tagged-token datastroomgrafieken.

QUAFF is een recentere skeletbibliotheek geschreven in C++ en MPI. QUAFF vertrouwt op op sjablonen gebaseerde meta-programmeertechnieken om runtime-overhead te verminderen en skeletuitbreidingen en optimalisaties uit te voeren tijdens de compilatie. Skeletten kunnen worden genest en sequentiële functies zijn stateful. Naast typecontrole maakt QUAFF gebruik van C++-templates om tijdens het compileren nieuwe C/MPI-code te genereren. QUAFF is gebaseerd op het CSP-model, waarbij het skeletprogramma wordt beschreven als een procesnetwerk en productieregels (single, serial, par, join).

SkeTo

Het SkeTo- project is een C++-bibliotheek die parallellisatie bereikt met behulp van MPI. SkeTo verschilt van andere skeletbibliotheken omdat SkeTo in plaats van nestbare parallellismepatronen te bieden, parallelle skeletten voor parallelle gegevensstructuren zoals: lijsten, bomen en matrices. De gegevensstructuren worden getypt met behulp van sjablonen en er kunnen verschillende parallelle bewerkingen op worden aangeroepen. De lijststructuur biedt bijvoorbeeld parallelle bewerkingen zoals: map, reduce, scan, zip, shift, etc...

Aanvullend onderzoek rond SkeTo heeft zich ook gericht op optimalisatiestrategieën door transformatie en meer recentelijk op domeinspecifieke optimalisaties. Bijvoorbeeld SkeTo verschaft een fusie transformatie die twee opeenvolgende functies aanroepen overgaat in een enkele, dus het verminderen van de functieaanroep kosten en voorkomen dat er intermediaire gegevensstructuren die tussen functies.

Skill

Skil is een imperatieve taal voor skeletprogrammering. Skeletten maken niet direct deel uit van de taal, maar worden ermee geïmplementeerd. Skil gebruikt een subset van C-taal die functionele taalachtige functies biedt, zoals functies van een hogere orde, curring en polymorfe typen. Wanneer Skil wordt gecompileerd, worden dergelijke functies geëlimineerd en wordt een reguliere C-code geproduceerd. Aldus Skil transformeert polymorfe hogere orde functies tot monomorfe eerste orde C functies. Skil ondersteunt geen nestbare samenstelling van skeletten. Dataparallellisme wordt bereikt met behulp van specifieke dataparallelle structuren, bijvoorbeeld om arrays over beschikbare processors te verspreiden. Filterskeletten kunnen worden gebruikt.

STAPL-skeletraamwerk

In STAPL Skeleton Framework worden skeletten gedefinieerd als parametrische gegevensstroomgrafieken, waardoor ze verder kunnen schalen dan 100.000 kernen. Bovendien behandelt dit raamwerk de samenstelling van skeletten als een punt-tot-punt-samenstelling van hun corresponderende gegevensstroomgrafieken via het begrip poorten, waardoor nieuwe skeletten gemakkelijk aan het raamwerk kunnen worden toegevoegd. Als gevolg hiervan elimineert dit raamwerk de noodzaak voor herimplementatie en globale synchronisaties in samengestelde skeletten. STAPL Skeleton Framework ondersteunt geneste compositie en kan schakelen tussen parallelle en sequentiële uitvoering op elk niveau van nesting. Dit framework profiteert van de schaalbare implementatie van STAPL parallelle containers en kan skeletten uitvoeren op verschillende containers, waaronder vectoren, multidimensionale arrays en lijsten.

T4P

T4P was een van de eerste systemen die werd geïntroduceerd voor skeletprogrammering . Het systeem was sterk afhankelijk van functionele programmeereigenschappen en vijf skeletten werden gedefinieerd als functies van hogere orde: Verdeel-en-heers, Boerderij, Kaart, Pijp en RaMP. Een programma kan meer dan één implementatie hebben, elk met een combinatie van verschillende skeletten. Bovendien kan elk skelet verschillende parallelle implementaties hebben. Een methodologie gebaseerd op functionele programmatransformaties geleid door prestatiemodellen van de skeletten werd gebruikt om het meest geschikte skelet voor het programma te selecteren, evenals de meest geschikte implementatie van het skelet.

Kaders vergelijking

• Activiteitsjaren zijn de bekende activiteitsjaren. De data in deze kolom komen overeen met de eerste en laatste publicatiedatum van een gerelateerd artikel in een wetenschappelijk tijdschrift of congres. Houd er rekening mee dat een project na de activiteitsperiode nog steeds actief kan zijn en dat we er na de opgegeven datum geen publicatie voor hebben gevonden.
• Programmeertaal is de interface waarmee programmeurs communiceren om hun skelettoepassingen te coderen. Deze talen zijn divers en omvatten paradigma's zoals: functionele talen, coördinatietalen, opmaaktalen, imperatieve talen, objectgeoriënteerde talen en zelfs grafische gebruikersinterfaces. Binnen de programmeertaal zijn skeletten geleverd als taalconstructies of bibliotheken. Het aanbieden van skeletten als taalconstructie impliceert de ontwikkeling van een aangepaste domeinspecifieke taal en zijn compiler. Dit was duidelijk de sterkere trend aan het begin van het skeletonderzoek. De meer recente trend is om skeletten als bibliotheken aan te bieden, in het bijzonder met objectgeoriënteerde talen zoals C++ en Java.
• Uitvoeringstaal is de taal waarin de skelettoepassingen worden uitgevoerd of gecompileerd. Het werd al heel vroeg erkend dat de programmeertalen (vooral in de functionele gevallen) niet efficiënt genoeg waren om de skeletprogramma's uit te voeren. Daarom werden skeletprogrammeertalen vereenvoudigd door skelettoepassing op andere talen uit te voeren. Transformatieprocessen werden geïntroduceerd om de skeletapplicaties (gedefinieerd in de programmeertaal) om te zetten in een equivalente applicatie op de doeluitvoeringstaal. Er werden verschillende transformatieprocessen geïntroduceerd, zoals het genereren van code of het maken van skeletten op een lager niveau (soms operationele skeletten genoemd) die in staat waren om te communiceren met een bibliotheek in de uitvoeringstaal. De getransformeerde applicatie bood ook de mogelijkheid om doelarchitectuurcode, aangepast voor prestaties, in de getransformeerde applicatie te introduceren. Tabel 1 laat zien dat een favoriet voor uitvoeringstaal de C-taal was.
• Distributiebibliotheek biedt de functionaliteit om parallelle/gedistribueerde berekeningen te realiseren. De grote favoriet in deze zin was MPI, wat niet verwonderlijk is omdat het goed integreert met de C-taal, en waarschijnlijk het meest gebruikte hulpmiddel is voor parallellisme in clustercomputing. De gevaren van rechtstreeks programmeren met de distributiebibliotheek zijn natuurlijk veilig verborgen voor de programmeurs die nooit interactie hebben met de distributiebibliotheek. Onlangs is de trend geweest om skeletraamwerken te ontwikkelen die in staat zijn om te interageren met meer dan één distributiebibliotheek. CO2 P3 S kan bijvoorbeeld gebruikmaken van Threads, RMI of Sockets; Mallba kan Netstream of MPI gebruiken; of JaSkel die AspectJ gebruikt om de skelettoepassingen op verschillende skeletkaders uit te voeren.
• Typeveiligheid verwijst naar het vermogen om type-incompatibiliteitsfouten in het skeletprogramma te detecteren. Aangezien de eerste skeletframeworks werden gebouwd op functionele talen zoals Haskell, werd typeveiligheid eenvoudigweg overgenomen van de hosttaal. Desalniettemin, aangezien er aangepaste talen werden ontwikkeld voor skeletprogrammering, moesten compilers worden geschreven om rekening te houden met typecontrole; wat niet zo moeilijk was als het nestelen van skeletten niet volledig werd ondersteund. Onlangs echter, toen we begonnen met het hosten van skeletframeworks voor objectgeoriënteerde talen met volledige nesting, is het probleem met de typeveiligheid weer opgedoken. Helaas wordt typecontrole meestal over het hoofd gezien (met uitzondering van QUAFF), en vooral in op Java gebaseerde skeletframeworks.
• Skelet nesten is het vermogen van hiërarchische samenstelling van skeletpatronen. Skelet nesten werd vanaf het begin geïdentificeerd als een belangrijk kenmerk in het programmeren van skeletten, omdat het de samenstelling van complexere patronen mogelijk maakt, beginnend met een basisset van eenvoudigere patronen. Desalniettemin heeft het lang geduurd voordat de gemeenschap het willekeurig nesten van skeletten volledig heeft ondersteund, voornamelijk vanwege de problemen met de planning en typeverificatie. De trend is duidelijk dat recente skeletraamwerken volledige nesting van skeletten ondersteunen.
• Bestandstoegang is de mogelijkheid om bestanden vanuit een toepassing te openen en te manipuleren. In het verleden is skeletprogrammering vooral nuttig gebleken voor rekenintensieve toepassingen, waar kleine hoeveelheden gegevens grote hoeveelheden rekentijd vereisen. Niettemin vereisen of produceren veel gedistribueerde toepassingen grote hoeveelheden gegevens tijdens hun berekening. Dit is het geval voor astrofysica, deeltjesfysica, bio-informatica, enz. Het bieden van ondersteuning voor bestandsoverdracht die integreert met skeletprogrammering is dus een belangrijke zorg die meestal over het hoofd wordt gezien.
• Skeletset is de lijst met ondersteunde skeletpatronen. Skeletsets variëren sterk van het ene raamwerk tot het andere, en meer schokkend, sommige skeletten met dezelfde naam hebben verschillende semantiek op verschillende raamwerken. De meest voorkomende skeletpatronen in de literatuur zijn waarschijnlijk boerderij, pijp en kaart.

Zie ook

• Halide (programmeertaal)
• Spijkerschrift (programmeertaal)
• Parallel programmeermodel

Referenties