Exploitation de la prédiction de branchement

 Recherche simultanée du minimum et du maximum

Nous avons vu dans le chapitre 3 le problème de la recherche du minimum et du maximum dans une séquence. Pour rappel, nous avons en entrée une séquence d’éléments comparables stockée dans un tableau T. Le problème consiste à obtenir les éléments minimum et maximum de ce tableau. Par exemple, si T = h7, 5, 2, 4, 14, 9i, la sortie sera donnée par le couple (2, 14) car 2 et 14 sont respectivement le minimum et le maximum de T. 5.1.1 Un premier algorithme naïf Données : Une séquence T de taille n. Résultat : min(T), max(T) 1 min ← max ← T[1] 2 pour i ← 2 à n faire 3 a ← T[i] 4 si a < min alors 5 min ← a 6 si a > max alors 7 max ← a Algorithme 8 : Algorithme de recherche du minimum et du maximum par la méthode naïve. Par la suite, nous nommons cet algorithme NaiveMinmax. Une première méthode que l’on nomme NaiveMinmax est décrite par l’algorithme 8. L’algorithme procède en faisant un parcours de tous les éléments de la séquence. Le minimum et le maximum des éléments parcourus sont gardés en mémoire. Lorsque tous les éléments sont parcourus, nous obtenons ainsi le minimum et le maximum qui correspondent aux valeurs gardées en mémoire. Nous initialisons à la ligne 1 le minimum et le maximum par la valeur T[1] qui est forcément le minimum et le maximum des éléments parcourus. Le parcours des éléments se fait par la boucle ligne 2 en partant du deuxième et en allant jusqu’au dernier. L’élément que l’on est en train de parcourir est alors comparé aux deux éléments gardés en mémoire. Si l’élément est le plus petit rencontré jusqu’à présent, il faut alors mettre à jour le minimum que l’on a gardé en mémoire. De la même façon, il faut mettre à jour le maximum si l’élément est le plus grand. Comme l’algorithme consiste en un balayage linéaire des n−1 éléments restants après l’initialisation, et qu’il fait deux comparaisons par itération, le coût total de l’algorithme est 2(n − 1). La Figure 5.1 montre un exemple d’exécution de l’algorithme pour une entrée choisie arbitrairement. 5.1.2 Un algorithme optimisé pour le nombre de comparaisons Nous avons vu lors du chapitre 3, un argument d’adversaire qui nous donne une borne inférieure au problème de la recherche du minimum et du maximum qui est de 3n 2 . Nous allons à présent voir un algorithme qui atteint cette borne Figure 5.1 – Cette figure représente une exécution de l’algorithme de recherche naïve du minimum et du maximum pour la séquence d’entrée h5, 6, 1, 7, 3, 2, 9, 8, 4i. À l’initialisation à la première ligne, le premier élément, dont la case est remplie en jaune, est à la fois le minimum et le maximum temporaires. Les lignes suivantes représentent les itérations correspondant à la boucle de parcours des éléments. Pour chacune de ces lignes, l’élément dont la case est remplie en rouge est le maximum temporaire, l’élément dont la case est remplie en vert est le minimum temporaire, les cases en bleu ne sont, ni le maximum ni le minimum et ont déjà été parcourues aux itérations précédentes. et qui, par conséquence, est optimal. Cet algorithme est une variante de l’algorithme naïf vu précédemment. Nous l’appelons 3 2 -Minmax et il est décrit par l’Algorithme 9. L’idée consiste toujours à garder en mémoire le minimum et le maximum des éléments déjà explorés, mais la façon dont nous parcourons ces éléments est différente. Dans l’algorithme naïf précédent, nous parcourions chaque élément un par un, cette fois nous allons parcourir deux éléments x et y simultanément par itération de la boucle principale. Soit m et M respectivement les éléments minimum et maximum que l’on connaît de la séquence à une itération. Nous faisons une première comparaison entre x et y. Si x < y, nous savons alors que x ne peut pas être le maximum de la séquence et il n’est donc pas nécessaire de comparer x à M. Respectivement, y ne peut pas être le minimum de la séquence et il n’est donc pas nécessaire de comparer y à m. Il nous reste alors deux comparaisons à faire, la première entre x et m, la deuxième entre y et M. Si x < m alors nous affectons x à m et respectivement si y > M nous affectons y à M. Dans le cas où x > y, nous faisons les mêmes remarques et les mêmes comparaisons supplémentaires en remplaçant x par y et y par x. Pour résumer, pour chaque itération, nous faisons une première comparaison entre x et y, une comparaisons entre min(x, y) et m, puis une comparaisons entre max(x, y) et M. Pour chaque itération nous faisons donc au total 3 comparaisons. À l’initialisa107 Données : Une séquence T de taille n. Résultat : min(T), max(T) 1 min ← max ← T[n] 2 pour i ← 1 à b n 2 c faire 3 a ← T[2i − 1] 4 b ← T[2i] 5 si a < b alors 6 si a < min alors 7 min ← a 8 si b > max alors 9 max ← b 10 sinon 11 si b < min alors 12 min ← b 13 si a > max alors 14 max ← a Algorithme 9 : Algorithme de recherche du minimum et du maximum par une méthode optimale. Par la suite nous nommons cet algorithme 3 2 -Minmax. tion, nous choisissons d’affecter m = M = T[n], et nous parcourons les éléments de la séquence dans l’ordre avec un compteur i initialisé à 1 que nous incrémentons de 2 après chaque itération. Cette affectation nous permet de faire le même parcours sans avoir à considérer la parité de n. En contrepartie, si n est pair, nous parcourons deux fois l’élément T[n]. Dans tous les cas, le nombre d’itérations effectuées par le parcours est de b n 2 c. Le nombre total de comparaisons effectuées par l’algorithme 3 2 -Minmax est ainsi 3b n 2 c = 3n 2 + O(1). En comparaison avec NaiveMinmax, nous faisons de l’ordre de 25% de comparaisons en moins avec 3 2 -Minmax. Nous donnons un exemple de trace d’exécution pour la même séquence d’entrée que pour l’exemple précédent dans la Figure 5.2. 

Un résultat inattendu

Nous avons implanté ces deux algorithmes afin de pouvoir mesurer leurs performances en temps sur une machine. Les listings 8 et 9, disponibles en Annexe B, donnent des extraits du code source de nos implantations en langage C. Nous avons ensuite compilé ce fichier avec le logiciel gcc sur un environnement gnu/linux. Nous avons utilisé l’option -O0 qui permet de compiler le code source sans optimisation. Ce choix nous permet d’obtenir une version de notre code en langage machine qui devrait être assez proche de notre code source initial. La machine utilisée pour faire ces tests fonctionne avec un microprocesseur Intel(R) Celeron(R) CPU 1037U @ 1.80GHz. Le listing 10 de l’annexe B donne le code assembleur que l’on obtient sur cette machine après compilation du fichier avec les options -O0 et -S. Ce dernier nous permet de vérifier la proximité qu’a le fichier exécutable avec le code source en C. Les résultats obtenus sur cette machine ne sont pas isolés. Des résultats similaires ont été obtenus sur 108 5 Figure 5.2 – Cette figure représente une exécution de l’algorithme de recherche optimisée du minimum et du maximum pour la séquence d’entrée h5, 6, 1, 7, 3, 2, 9, 8, 4i. À l’initialisation à la première ligne, le dernier élément, dont la case est remplie en jaune, est à la fois le minimum et le maximum temporaire. Les lignes suivantes représentent les itérations de la boucle principale. Pour chacune de ces lignes, l’élément dont la case est remplie en rouge est le maximum temporaire, l’élément dont la case est remplie en vert est le minimum temporaire, les cases en bleu ne sont, ni le maximum ni le minimum et ont déjà été parcourues aux itérations précédentes. d’autres machines suffisamment récentes pour avoir des caractéristiques basées sur les dernières avancées en architecture. Pour générer le tableau en entrée, nous le remplissons initialement de valeurs entières avec la fonction standard random() qui a un comportement proche d’une loi uniforme sur l’intervalle [0, RAND_MAX], avec RAND_MAX qui est une valeur particulière dépendant de l’environnement. 1 À chaque nouveau test, le tableau est ensuite mélangé avec un algorithme de type Knuth Shuffle afin d’obtenir un mélange uniforme. Le tableau obtenu est alors utilisé en entrée pour les deux algorithmes. Lorsque nous exécutons ce programme, nous obtenons sur la sortie standard les temps pris par les implantations de ces deux algorithmes pour des tableaux de tailles allant de 1000 à 1000×2 18, la taille étant doublée à chaque itération. Pour chaque taille, nous avons exécuté ces deux implantations 10 fois afin d’obtenir une mesure moyenne des temps. La Figure 5.3 montre les résultats ainsi obtenus sous forme de courbes de performances. Lorsque nous observons ces deux courbes, nous pouvons être surpris du résultat. En effet, nous observons que la courbe de l’algorithme optimal en nombre de comparaisons est située en tous points au-dessus de la courbe de l’algorithme naïf. En d’autres termes, l’algorithme naïf s’avère être en pratique plus efficace que l’algorithme optimisé. Si nous considérons que notre machine est basée sur le modèle RAM, ce résultat est surprenant car les deux algorithmes font les mêmes opérations, exceptées pour les comparaisons. Or, nous avons vu que 3 2 -Minmax fait moins de comparaisons que NaiveMinmax. Pour ces deux opérations l’algorithme optimisé fait moins de travail que l’algorithme naïf et devrait par conséquent être le plus rapide des deux. Il nous est donc nécessaire de remettre en question l’hypothèse du modèle RAM.