Parallel random access machine

PRAM, pour Parallel Random Access Machine, est un modèle abstrait de machine destiné à concevoir des algorithmes pour machines parallèles de modèle MIMD, ou pour de plus rares cas de modèle SIMD.

PRAM modélise une machine parallèle à une mémoire RAM partagée par un ensemble de processeurs. Ces processeurs sont synchronisés par chaque instruction. On définit alors plusieurs variantes de ce modèle, en fonction des restrictions d'accès mémoire :

• CRCW : Concurrent Read, Concurrent Write : chaque processeur peut lire et écrire n'importe où dans la mémoire à tout moment.
• CREW : Concurrent Read, Exclusive Write : chaque processeur peut lire n'importe quel endroit de la mémoire à tout instant, mais aucune écriture simultanée de deux processeur à un même endroit n'est possible.
• EREW : Exclusive read, Exclusive Write : chaque processeur ne peut lire ou écrire à un endroit de la mémoire que si aucun autre processeur n'y accède à ce moment-là.

On définit sur une telle machine la complexité en temps par rapport à la taille de l'entrée de la même manière que pour un algorithme séquenciel (voir : Complexité algorithmique), et aussi la complexité en nombre de processeurs utilisés, toujours en fonction de la taille de l'entrée.

PRAM ne tiens toutefois aucun compte des coûts d'échanges de données entre différentes machines. Notamment, la représentation par PRAM d'une grappe d'ordinateurs, où la mémoire disponible est en réalité partagée entre chaque ordinateur, négligera le temps d'accès d'un processeur à une partie de la mémoire qui ne lui est pas physiquement locale.