Parallelle willekeurige toegangsmachine
In de informatica is een parallelle random access machine , of kortweg PRAM , een machine voor het analyseren van parallelle algoritmen . Het is een registratiemachine die is uitgebreid met de mogelijkheid om opdrachten parallel te verwerken. Zoals bij alle modellen kassamachines, zijn er verschillende varianten van het PRAM. Het idee dat alle modellen gemeen hebben, is dat meerdere registers tegelijkertijd berekeningen kunnen uitvoeren en het resultaat in geheugencellen kunnen opslaan . Het PRAM bedient onder meer. in complexiteitstheorie om de klasse NC van efficiënt parallelle beslisbare problemen te definiëren .
Voorbeeld van een realisatie
Zelfs als registermachines in engere zin slechts een zeer eenvoudige set instructies ondersteunen , kunnen equivalente registermachines worden gedefinieerd waarvan de programma's kunnen worden gespecificeerd in een programmeertaal op hoog niveau . De parallelle verwerking van commando's kan nu worden gedaan door een nieuwe instructie in te voeren die er ongeveer zo uitziet:
- voor <voorwaarde> pardo <instructies>
pardo staat voor parallel doen . Een voorbeeld:
- voor i = 1 tot 100 pardo x i : = 0
Deze instructie initialiseert 100 geheugenlocaties tegelijkertijd met de waarde 0. X kan bijvoorbeeld worden gezien als een array met velden die zijn geïndexeerd van 1 tot 100. De meer algemene notatie x i bevat dergelijke implementatiedetails niet . Het gegeven voorbeeld is natuurlijk niet van bijzonder groot praktisch belang. Daarom is hier een nuttiger voorbeeld dat de mogelijkheden van een PRAM-put laat zien:
Er wordt een lijst met n verschillende waarden gegeven, die ongesorteerd worden opgeslagen in de geheugencellen x 1 t / m x n . We zoeken die x i die de grootste waarde bevat. Verrassend genoeg kan deze zoekopdracht parallel worden uitgevoerd op een PRIORITY-CRCW-PRAM (zie hieronder), waarvoor geen activering van de processors nodig is, voor n van elke grootte in constante tijd :
for i=1 to n pardo
bi := 1
for i,j=1 to n pardo
if xj > xi
then
bi := 0
fi
for i=1 to n pardo
if bi = 1
then
m := i
fi
Na de tweede for-lus heeft b i alleen de waarde 1 als x i het maximum is. Alle andere b j met j ≠ i hebben de waarde 0. De i met b i = 1 is dus de gezochte index en is te vinden in na het uitvoeren van het programma m. Het maximum in een ongesorteerde lijst van elke lengte n kan daarom met constante inspanning worden berekend , d.w.z. in O (1) tijd.
Verschillende PRAM-modellen
SIMD- en MIMD-PRAM's
De hierboven beschreven pardo-instructie maakt de gelijktijdige uitvoering van een bepaalde instructie op verschillende variabelen binnen een tijdcyclus mogelijk . Dergelijke parallelle modellen worden single-instruction multiple datamodellen of kortweg SIMD genoemd . Als verschillende opdrachten binnen een tijdcyclus zijn toegestaan, wordt dit een multiple instruction multiple data model ( MIMD ) genoemd. De pardo-verklaring is te eng gedefinieerd voor een dergelijk model.
Gelijktijdige lees- en schrijftoegang tot identieke geheugencellen
Er moet worden bepaald of gelijktijdige lees- en schrijftoegang tot identieke geheugencellen moet worden toegestaan of niet. Het bovenstaande algoritme voor maximaal zoeken vereist beide: Binnen de tweede pardo-instructie worden identieke geheugencellen x i gelijktijdig benaderd door verschillende processors om ze met elkaar te vergelijken, en wordt geheugencel b i gelijktijdig benaderd om te schrijven . Dergelijke vrijheden wil je niet altijd toestaan. Er wordt daarom onderscheid gemaakt tussen:
- CRCW PRAM: Gelijktijdig lezen, Gelijktijdig schrijven - gelijktijdige lees- en schrijftoegang mogelijk
- CREW PRAM: Gelijktijdig lezen, Exclusief schrijven - gelijktijdige leestoegang, maar alleen exclusieve schrijftoegang toegestaan
- EREW PRAM: Exclusief lezen, exclusief schrijven - alleen exclusieve lees- en schrijftoegang toegestaan
In het geval van een EREW kan bijvoorbeeld slechts één processor lees- of schrijftoegang hebben tot een specifieke geheugencel. Anders wordt het programma beëindigd .
Schrijftoegang tot CRCW's
In het geval van een CRCW-PRAM moet nog worden verduidelijkt wat er moet gebeuren in het geval van gelijktijdige schrijftoegang wanneer verschillende processoren verschillende waarden naar de geheugencel willen schrijven. Er zijn 3 modi:
- common: Alleen het schrijven van identieke waarden is toegestaan.
- arbitrair: er wordt een willekeurige waarde geselecteerd en geschreven.
- prioriteit: de processor met het laagste adres krijgt schrijftoegang.
Met specifieke algoritmen leiden de verschillende variaties van PRAM tot verschillende complexiteiten in het verbruik van hulpbronnen. Het bovengenoemde algoritme voor maximaal zoeken is bijvoorbeeld afhankelijk van gelijktijdige lees- en schrijftoegang, d.w.z. op een CRCW PRAM, zoals beschreven. Een oplossing in constante tijd zou niet mogelijk zijn op een PRAM dat dit niet toelaat. Welk PRAM-model u kiest voor een specifiek onderzoek, hangt dus af van de analysedoelen die u ermee nastreeft.
