Les Modèles de calcul parallèle (PRAM), ou Parallel Random Access Machine en anglais, sont des modèles théoriques utilisés pour concevoir et analyser des algorithmes parallèles. Ils représentent une abstraction d'un ordinateur parallèle idéal composé de plusieurs processeurs partageant une mémoire commune.
Dans le contexte de la programmation parallèle, les PRAM servent à :
- Évaluer la complexité des algorithmes parallèles
- Comparer l'efficacité de différentes approches parallèles
- Concevoir de nouveaux algorithmes parallèles
Les PRAM se déclinent en plusieurs variantes selon les règles d'accès à la mémoire partagée :
- EREW (Exclusive Read Exclusive Write) : un seul processeur peut lire ou écrire dans une cellule mémoire à la fois
- CREW (Concurrent Read Exclusive Write) : plusieurs processeurs peuvent lire simultanément, mais un seul peut écrire
- CRCW (Concurrent Read Concurrent Write) : plusieurs processeurs peuvent lire et écrire simultanément
Exemple pratique :
# Algorithme PRAM pour la somme de n nombres
def pram_sum(numbers, p):
n = len(numbers)
for i in range(log2(n)):
for j in range(n) in parallel:
if j + 2**i < n:
numbers[j] += numbers[j + 2**i]
return numbers[0]Ce modèle, bien que théorique, aide les programmeurs à développer une intuition pour la conception d'algorithmes parallèles efficaces, tout en fournissant un cadre pour l'analyse de leur performance.
