Parallel tilfældig adgangsmaskine

I datalogi er PRAM til Parallel Random Access Machine en abstrakt maskinmodel beregnet til at designe algoritmer til parallelle maskiner af MIMD- modellen eller til sjældnere tilfælde af SIMD- modellen .

PRAM modellerer en maskine, der er parallel med en RAM- hukommelse, der deles af et sæt processorer . Disse processorer synkroniseres af hver instruktion. Vi definerer derefter flere varianter af denne model, afhængigt af hukommelsesadgangsbegrænsninger:

• EREW: Eksklusiv  læsning , eksklusiv skrivning : hver processor kan kun læse eller skrive til et hukommelsessted, hvis ingen anden processor har adgang til det på det tidspunkt.
• CREW: Samtidig  læsning , eksklusiv skrivning : hver processor kan til enhver tid læse i hukommelsen, men det er ikke muligt at skrive to processorer samtidig på samme sted.
• ERCW: Exclusive Read, Concurrent Write  : hver processor kan skrive til et hvilket som helst sted i hukommelsen til enhver tid, men ingen samtidig læsning af to processorer på samme sted er mulig.
• CRCW: Concurrent Read, Concurrent Write  : Hver processor kan til enhver tid læse og skrive hvor som helst i hukommelsen.

For CRCW-varianten er der også tre undervarianter, der adskiller sig fra den adfærd, der skal følges, hvis flere processorer forsøger at skrive til den samme hukommelsesplacering:

• CRCW-P: Prioritet  : kun processoren med den højeste prioritet har ret til at skrive til dette sted
• CRCW-A: Vilkårlig  : kun én af processorerne vil bære skrive ret til dette sted
• CRCW-C: Almindelig  : Processorer kan skrive til den samme hukommelsesplacering, så længe de skriver den samme værdi.

Man definerer på en sådan maskine kompleksiteten i tid sammenlignet med størrelsen på input på samme måde som for en sekventiel algoritme (se: Algoritmisk kompleksitet ) og også kompleksiteten i antallet af anvendte processorer, altid i henhold til indgangsstørrelsen.

PRAM tager dog ikke hensyn til omkostningerne ved dataudveksling mellem forskellige maskiner. Især vil repræsentationen af ​​PRAM af en klynge af computere, hvor den tilgængelige hukommelse i virkeligheden deles mellem hver computer, forsømme adgangstiden for en processor til en del af hukommelsen, som ikke er fysisk lokal for den.

Relaterede artikler

• Maskine til tilfældig adgang
• LogP