Tri PRAM

On considère l'algorithme de tri, décrit informellement comme suit. Soit \[l=(l_1,\ldots,l_n)\] une liste de n entiers distincts. On construit une grille d'entiers n fois n, où l'entrée (i,j) est égale à 1 si \[l_i > l_j\] comme indiqué sur l'exemple ci-dessous pour la liste l=(7,8,3,1): \[ \begin{array}{r|rrrr} & 7 & 8 & 3 & 1 \\ \hline 7 & 0 & 0 & 1 & 1 \\ 8 & 1 & 0 & 1 & 1 \\ 3 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ \end{array} \] Ensuite, on somme les entrées par ligne, pour obtenir une liste d'entiers \[r=(r_1,\ldots,r_n)\] Ainsi pour notre exemple, r=(2,3,1,0). On définit maintenant une nouvelle liste l' à partir de l, en la réordonnant par r: \[l'_{r_i+1}=l_i, \mbox{ } i=1,\ldots,n\] Ainsi, on obtient l'=(1,3,7,8), qui est l triée.

Question 1

On suppose que l'on dispose d'une machine PRAM CREW (voir le poly section 2.1 page 23) et que dans sa mémoire partagée on ait stocké l. Ecrire l'algorithme de tri correspondant. Quelle est la complexité de l'algorithme?

Question 2

Prouver que pour toute liste de taille n, ce procédé opère un tri.

Question 3

Quelle est l'efficacité de l'algorithme (voir le poly section 2.4 page 31) de la question 1? Peut-on améliorer celle-ci? Que se passe t-il si on n'a plus qu'une machine EREW?

Récurrences linéaires

Le problème qui nous préoccupe dans cette section est de calculer efficacement, en parallèle, des suites récurrentes linéaires d'ordre m > 0, de la forme (pour i > -1): $$\begin{array}{lcl} y_0 & = & a_{0,0} \\ \cdots & \cdots & \cdots \\ y_{m-1} & = & a_{m-1,0} \\ y_{m+i} & = & a_{m+i,m} y_{m+i-1} + \cdots + a_{m+i,1} y_{i} + a_{m+i,0} \\ \end{array}$$ Comme applications visées, on a par exemple:

l'évaluation d'un polynôme \[p(x)=a_0+a_1x+\cdots+a_k x^k\] par la méthode de Horner: on fait \[y_0=a_k, \mbox{ puis } y_{i+1}=x y_i+a_{k-i-1}\] (récurrence linéaire d'ordre 1); alors \[p(x)=y_k\]
la résolution de systèmes linéaires par bandes: soit par exemple \[A=\left(\begin{array}{ccccccc} a_{1,1} & 0 & 0 & 0 & \cdots & \cdots & 0 \\ a_{2,1} & a_{2,2} & 0 & 0 & \cdots & \cdots & 0 \\ a_{3,1} & a_{3,2} & a_{3,3} & 0 & & & \vdots \\ 0 & a_{4,2} & a_{4,3} & a_{4,4} & & & \vdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ & & & 0 & a_{n,n-2} & a_{n,n-1} & a_{n,n} \\ \end{array}\right)\] La solution de l'équation Ax=b peut être trouvée par la récurrence suivante: \[\begin{array}{rcl} x_1 & = & \frac{b_1}{a_{1,1}} \\ x_2 & = & \frac{1}{a_{2,2}}(b_2-a_{2,1} x_1) \\ \ldots & & \\ x_i & = & \left(\sum_{j=i-m}^{i-1} -\frac{a_{i,j}}{a_{i,i}} x\right)+\frac{b_i}{a_{i,i}} \end{array}\]

Récurrences d'ordre 1

On se place dans le cas de récurrences linéaires d'ordre 1 (m=1): c'est à dire, \[\begin{array}{lcl} y_0 & = & a_{0,0} \\ y_{i+1} & = & a_{i+1,1} y_{i} + a_{i+1,0} \\ \end{array}\] et on veut calculer \[y_i, \mbox{ } 0 \leq i \leq n-1\] (pour un n donné, que l'on pourra supposer être une puissance de 2).

Question 1

On suppose que $$a_{i,1}=1$$ Comment calculer efficacement les n premiers éléments de la suite y sur une machine PRAM EREW, CREW, CRCW? Quelle sera l'efficacité de l'algorithme?

Question 2

On se place maintenant dans le cas d'une récurrence linéaire d'ordre 1 générale, c'est à dire que les coefficients sont maintenant quelconques. Donner la formule générale pour la nième entrée de la suite en fonction des coefficients \[a_{i,1} \mbox{ et } a_{i,0}\]

Question 3

A l'aide de la question précédente, comment modifier l'algorithme de la question 1 pour calculer efficacement \[y_n, \mbox{ pour un } n \mbox{ fixé}\] sur une machine PRAM CREW, en utilisant la technique de saut de pointeur?

Question 4

Quelle est l'efficacité de cet algorithme? Justifier brièvement.

Question 5

Programmer l'algorithme de la question 3 en Java. On écrira donc successivement:

Une class Multred qui effectue une multiplication parallèle par saut de pointeurs :
```
public class Multred extends Thread {
  int k;
  int pos;
  int a[][];

  Multred(...) { ... }
 
  public void run() {
    // multiplication parallèle par saut de pointeurs
    ...
  }
```
Dans le code plus haut k représente le nombre d'étapes du saut de pointeurs et le tableau a est de type a[n][k] où $$n=2^k$$ et a[i][j] représente la ième valeur à l'étape j du saut de pointeurs. Au début, les éléments à multiplier sont stockés dans a[i][0]. La variable pos représente le numéro du processus, qui s'occupe donc d'updater l'entrée a[pos][i] avec le numéro d'étape i entre 1 et k. On écrira donc successivement le constructeur adéquat et la méthode run correspondante. On fera comme à la section 2.2 page 26 du poly et on simulera les sauts de pointeurs par une attente active.
Déposez Multred.java
Une classe Localconvol chargée d'effectuer un produit parallèle de deux tableaux a[][k] et b[], élément par élément, à l'indiçage près, dans un tableau t[][0] par la formule $$t[pos][0]=a[pos][k] b[2^k-pos-1]$$ pour un k donné et pour pos entre 0 et deux puissance k (égal à n comme plus haut) moins un. Le processus numéro pos est chargé de faire cette multiplication, pour tout pos entre 0 et n-1 :
```
public class Localconvol extends Thread {
  int k;
  int pos;
  int t[][];
  int a[][];
  int b[];

  Localconvol(...) { ... }

  public void run() { ... }
```
Déposez Localconvol.java
Une class Plusred qui effectue une addition parallèle par saut de pointeurs :
```
public class Plusred extends Thread {
  int k;
  int pos;
  int t[][];

  Plusred(...) { ... }

  public void run() { ... }
```
Dans le code plus haut t[i][j] représente la ième valeur à l'étape j du saut de pointeurs et pos représente le numéro du processus, qui s'occupe donc d'updater l'entrée t[pos][i] avec le numéro d'étape i entre 1 et k. Au début, les éléments à additionner sont stockés dans a[i][0]. On écrira donc successivement le constructeur adéquat et la méthode run correspondante et de même que pour Multred on fera comme à la section 2.2 page 26 du poly et on simulera les sauts de pointeurs par une attente active.
Déposez Plusred.java

On écrira enfin une classe Recurrence.java qui prend à la ligne de commande k (le logarithme en base 2 de la taille de la récurrence à considérer) et on testera la récurrence avec les cas suivants:

import java.util.*;

public class Recurrence {
  public static void main(String[] args) {
    int k = Integer.parseInt(args[0]):
    ...

    // test somme de n entiers tirés aléatoirement
    Random r = new Random();
    // on tire un nouvel élément entre 0 et n-1 par r.nextInt(n)
    ...

    // test y(i+1)=2y(i)+a(i) où a est un tableau aléatoire
    ...

Déposez Recurrence.java.

Solution récursive

On constate que la solution précédente est lourde, lente et n'est pas générale. Une autre façon de faire est de construire un algorithme diviser pour régner parallèle, plus général que le saut de pointeurs, en une étape, comme dans la question suivante.

Question 6

Exprimer \[y_{i} \mbox{ en fonction de } y_{i-2}\]

Question 7

En déduire un algorithme récursif permettant de calculer toutes les n première entrées de la suite y (pour n une puissance de 2).

Récurrence linéaire d'ordre supérieur

On se place maintenant dans le cas général m > 0, et on suppose disposer d'un algorithme PRAM permettant de faire la multiplication de deux matrices carrées m fois m en temps O(log(m)), et utilisant O(M(m)) opérations. On pourra supposer par exemple $$M(m)=O(m^{2.376})$$ sur de l'ordre de m au cube processeurs.

Question 8

Comment améliorer l'algorithme de la question 3 afin de calculer les n premières entrées de la suite y, sur une PRAM, dans le cas d'une récurrence d'ordre m? Quelle est l'efficacité de l'algorithme sur une PRAM CREW? Justifier brièvement.

Threads récursifs: Fibonacci

Ecrire un calcul de la fonction f de Fibonacci, définie par la récurrence,

f(0)=1,
f(1)=1,
f(n+2)=f(n+1)+f(n).

en utilisant des threads JAVA. L'idée est de paralléliser l'algorithme récursif naturel permettant de calculer f. Mais pour calculer f(n+2), au lieu de s'appeler soi-même deux fois pour calculer f(n+1) et f(n), on créera un thread pour calculer f(n+1) et un autre pour calculer f(n). Ainsi, on définira une classe Fibon dont la méthode run() sera en charge de calculer la fonction f. On construira la classe Fibon contenant un champ argument, et un champ résultat de type int comme plus bas :

public class Fibon extends Thread {
    private final int x;
    int result;

    public Fibon(int x) { ... }

    public void run() { ... }

On programmera donc,

un constructeur Fibon(int x),
la méthode public void run() du thread.
le main de la classe: public static void main(String[] args). On pourra tester le calcul de la suite en appelant le calcul de la suite de Fibonacci sur les entiers 0 à 14 inclus.

Déposez Fibon.java.