TD3

Théorème de simulation

Comme il y a plusieurs modèles de PRAM, une question récurrente est de savoir quel modèle est plus puissant qu’un autre. Dans cet exercice, nous allons nous limiter aux PRAM CRCW (en mode consistant) et CREW.

  1. Rappelez les définitions de ces PRAM.
  2. Nous souhaitons simuler le fonctionnement d’une CRCW en utilisant une CREW. Quelle opération de la CRCW va être problématique?
  3. Supposons qu’un processeur Pi de la CRCW écrive la donnée xi en mémoire à l’adresse li. Pour éviter tout conflit avec un autre processeur, nous allons rediriger cette écriture dans un tableau intermédiaire A[i] = (li,xi). Pourquoi le tableau contient bien toutes les écritures effectuées à un cycle donné par tous les processeurs ?
  4. Nous disposons d’un algorithme magique (en O(log(p))) qui va nous permettre de trier le tableau sur notre CREW. Proposez une nouvelle étape de calcul, basée sur le tableau trié, permettant de s’assurer de l’exclusivité de l’écriture.
  5. En déduire qu’il est possible de simuler une CRCW sur une CREW pour un surcout de O(log(p)).
  6. En déduire qu’un algorithme sur une PRAM CRCW ne peut pas être plus de O(log(p)) fois plus rapide que le meilleur algorithme PRAM CREW à p processeurs pour le même problème.

Préfixe

Il existe un algorithme de préfixe en parallèle basé sur la technique du divide’n’conquer dont le principe est le suivant. Le tableau x1,....,xn (n = 2m) est découpé en deux sous tableaux (x1,....,xn/2) et (xn/2 +1,....,xn )qui sont traités en parallèle pour donner les préfixes (p'1,...,p'n/2) et (p'n/2 +1,...,p'n). Il suffit ensuite de traiter ces deux tableaux pour obtenir les préfixes

  1. Exécutez cet algorithme sur l’exemple 1, 2, 3, 4, 5, 6, 7, 8
  2. Quel type de PRAM cet algorithme nécessite-t-il ?
  3. Proposez une modification pour qu’il puisse s’exécuter sur une machine
  4. EREW (hint : utilisez un tableau intermédiaire pour la valeur problématique).
  5. Comment faire pour créer ce tableau de la manière la plus efficace possible?