RAM parallèle

informatique , une machine à accès aléatoire parallèle ( RAM parallèle ou PRAM ) est une machine abstraite à mémoire partagée . Comme son nom l'indique, la PRAM est conçue comme l'analogue, pour le calcul parallèle, de la machine à accès aléatoire (RAM) (à ne pas confondre avec la mémoire vive ). De la même manière que la RAM est utilisée par les concepteurs d'algorithmes séquentiels pour modéliser les performances algorithmiques (telles que la complexité temporelle), la PRAM est utilisée par les concepteurs d'algorithmes parallèles pour modéliser les performances algorithmiques parallèles (telles que la complexité temporelle, le nombre de processeurs étant généralement précisé). À l'instar du modèle RAM qui néglige certains aspects pratiques, comme le temps d'accès à la mémoire cache par rapport à la mémoire principale, le modèle PRAM néglige des aspects tels que la synchronisation et la communication , mais permet d'utiliser un nombre quelconque de processeurs (dépendant de la taille du problème). Le coût de l'algorithme, par exemple, est estimé à l'aide de deux paramètres : O(temps) et O(temps × nombre_de_processeurs).

de réduction de tableau comme SOMME, ET logique ou MAX.

Plusieurs hypothèses simplificatrices sont formulées lors de l'élaboration d'algorithmes pour la PRAM. Les voici :

Le nombre de processeurs dans la machine est illimité.
Toute zone mémoire est accessible de manière uniforme depuis n'importe quel processeur.
La quantité de mémoire partagée dans le système est illimitée.
Il n'y a pas de conflit de ressources .
Les programmes écrits sur ces machines sont, en général, de type SIMD .

Ces types d'algorithmes sont utiles pour comprendre l'exploitation de la concurrence, en divisant le problème initial en sous-problèmes similaires et en les résolvant en parallèle. L'introduction du modèle formel « P-RAM » dans la thèse de Wyllie de 1979 visait à quantifier l'analyse des algorithmes parallèles d'une manière analogue à la machine de Turing . L'analyse s'est concentrée sur un modèle MIMD de programmation utilisant un modèle CREW, mais a montré que de nombreuses variantes, y compris l'implémentation d'un modèle CRCW et l'implémentation sur une machine SIMD, étaient possibles avec un surcoût constant.

Mise en œuvre

Les algorithmes PRAM ne peuvent pas être parallélisés avec la combinaison d' un processeur et d'une mémoire vive dynamique (DRAM) car la DRAM ne permet pas un accès concurrent à une seule banque (même pas à des adresses différentes dans la banque) ; mais ils peuvent être implémentés dans le matériel ou en lecture/écriture dans les blocs de mémoire vive statique (SRAM) internes d'un réseau de portes programmables (FPGA), cela peut être fait en utilisant un algorithme CRCW.

Cependant, la pertinence pratique des algorithmes PRAM (ou RAM) dépend de leur capacité à fournir une abstraction efficace d'un ordinateur ; la structure de cet ordinateur pouvant être très différente du modèle abstrait. La connaissance des couches logicielles et matérielles à insérer dépasse le cadre de cet article. Néanmoins, des articles comme du multithreading explicite (XMT), et des articles comme problème du flux maximal peut offrir des gains de vitesse significatifs par rapport au programme séquentiel le plus rapide pour ce même problème. L'article SystemVerilog qui trouve la valeur maximale d'un tableau en seulement deux cycles d'horloge. Il compare toutes les combinaisons possibles des éléments du tableau au premier cycle, puis fusionne les résultats au second. Il utilise une mémoire CRCW m[i] <= 1et maxNo <= data[i]les écritures sont effectuées simultanément. Cette concurrence ne génère aucun conflit car l'algorithme garantit que chaque valeur est écrite dans la même zone mémoire. Ce code peut être exécuté sur un FPGA .

Plus d articles de Worldlex Wiki

Revenez a l index pour explorer davantage de pages sur l histoire, la science, la culture, la geographie et la societe en francais.

Explorer l index