Parallel random access machine
En informatique, 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 :
- 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à.
- 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.
- ERCW : Exclusive Read, Concurrent Write : chaque processeur peut écrire à n'importe quel endroit de la mémoire à tout instant, mais aucune lecture simultanée de deux processeur à un même endroit n'est possible.
- CRCW : Concurrent Read, Concurrent Write : chaque processeur peut lire et écrire n'importe où dans la mémoire à tout moment.
Pour la variante CRCW, il existe également trois sous-variantes, distinguées par le comportement à suivre si plusieurs processeurs tentent d'écrire au même emplacement mémoire :
- CRCW-P : Priorité : seul le processeur le plus prioritaire emportera le droit d'écrire à cet emplacement
- CRCW-A : Arbitraire : seul un des processeurs emportera le droit d'écriture à cet emplacement
- CRCW-C : Commun : les processeurs peuvent écrire au même emplacement mémoire, à condition qu'ils écrivent la même valeur.
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équentiel (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 tient 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.