Exemples d'algorithmes de tri parallèles

Vincent Loechner

Tri PRAM

Ce tri n'appartient pas à la classe des tris basés sur la notion de comparaison-échange. On procède de la manière suivante : le vecteur de valeurs à trier est placé sur la première ligne d'une grille. Le même vecteur transposé est aussi disposé en colonne. Puis, on effectue les comparaisons entre chaque couple formé par une valeur ligne et une valeur colonne. Si la comparaison est vraie on met à l'emplacement correspondant de la grille, la valeur 1, sinon 0.

**Figure:** Exemple de tri sur la séquence de valeurs 7;8;3;1
$\begin{figure}\begin{center} \psfig{figure=pram.eps} \end{center} \end{figure}$

Cette phase terminée, on somme les éléments des lignes dans un nouveau vecteur. Ces sommes donnent la position de chacune des valeurs du vecteur initial dans le vecteur trié (figure 1).

Tri pair-impair

Ce tri est une variante du tri à bulle. L'algorithme séquentiel du tri à bulle a une complexité de ${\cal O}(n^2)$ pour éléments à trier. Il peut s'écrire :

procedure tri_a_bulle(a, n)
pour i:=n-2 à 0 par -1
     pour j:= 0 à i
        compare_echange(a[j],a[j+1])
     fpour
fpour
fin tri_a_bulle

Cependant cet algorithme fait apparaître une dépendance qui empêche sa parallélisation : un élément est comparé avec $a_{j-1}$ qui dépend lui-même de $a_{j-2}$ , etc. Une variante du tri à bulle est le tri pair-impair. La boucle interne est divisée en deux phases : une phase est consacrée à la comparaison des éléments d'indices pairs du tableau de valeurs avec les suivants, l'autre aux éléments d'indices impairs avec les suivants. L'algorithme est alors :

procedure tri_pair_impar(n)
pour i:=0 a n-1
     si i est pair 
     alors 
        pour j:=0 a n-1 par 2
             compare_echange(a[j],a[j+1]);
        fpour
     sinon
         pour j:=1 a n-1 par 2
              compare_echange(a[j],a[j+1]);
         fpour
     fsi       
fin tri_pair_impar

La figure 2 illustre le déroulement de l'algorithme sur un exemple.

**Figure:** Exemple de tri sur la séquence de valeurs 7;8;3;1
$\begin{figure}\begin{center} \psfig{figure=odd_even.eps} \end{center} \end{figure}$

Exercices

Programmer ces tris en parallèle.

Analysez leurs performances.

About this document ...

Exemples d'algorithmes de tri parallèles

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.70)

The command line arguments were:
latex2html -split 0 -local_icons tp

The translation was initiated by Vincent Loechner on 2006-11-16

Vincent Loechner 2006-11-16