Parallel Random Access Machine

Als Parallel Random Access Machine, kurz PRAM, bezeichnet man in der Informatik einen Automaten zur Analyse paralleler Algorithmen. Es handelt sich um eine Registermaschine, die um die Möglichkeit zur parallelen Verarbeitung von Befehlen erweitert wurde. Wie bei allen Registermaschinen-Modellen gibt es verschiedene Variationen der PRAM. Die allen Modellen gemeinsame Vorstellung besteht darin, dass mehrere Register gleichzeitig Berechnungen ausführen und das Ergebnis in Speicherzellen ablegen können. Die PRAM dient u. a. in der Komplexitätstheorie zur Definition der Klasse NC der effizient parallel entscheidbaren Probleme.