Exploitation de la prédiction de branchement

Dans ce chapitre, nous allons nous intéresser à l’influence de la prédictionde branchement sur les performances de divers algorithmes. Rappelons que le sujet de la prédiction de branchements relève du domaine de l’architecture qui a été abordé au cours du chapitre 3. Il s’agit également d’une première occasion pour nous d’affiner le modèle RAM qui fait des simplifications concernant le coût des instructions de branchement. Nous allons, en plus des coûts d’opéra- tions basiques comme les comparaisons, nous intéresser à un nouveau type de coût, à savoir le nombre d’erreurs de prédiction. Nous distinguons donc de cette façon les coûts des opérations classiques du modèle RAM et les coûts issus de la prédiction de branchement. Le sujet de la prédiction de branchement a déjà été brièvement étudié par le passé mais principalement d’un point de vue pratique. Un premier travail expérimental est celui de Biggar et ses co-auteurs [12] qui ont mis en avant l’influence de la prédiction de branchements sur divers algorithmes de tri. Pour obtenir leurs résultats, les auteurs ont utilisé la librairie PAPI [2] que nous utilisons également pour nos expérimentations. Des analyses théoriques d’algorithmes de tri sur le nombre d’erreurs de prédiction ont également été ef- fectuées par Brodal, Fagerberg et Moruz.

Ces derniers ont cherché à étudier les compromis entre le nombre de comparaisons et le nombre d’erreurs de pré- diction pour le problème du tri [16]. À l’aide d’utilisations d’arbres de décision comme ceux que nous avons vu au cours du chapitre précédent, ils montrent par exemple que si un algorithme trie une séquence de taille n en O(dn log n) com-n). Ce théorème est vrai quel que soit le modèle de prédicteur utilisé. Ces mêmes auteurs [14] ont également étudié l’influence du nombre d’inversions sur le nombre d’erreurs de prédiction générées à l’exécution de QuickSort. Ces travaux sont à notre connaissance les premiers pour lesquels une analyse théorique a été effectuée dans le cadre de l’utilisation de prédicteurs statiques. Sanders et Winkel [40] ont quant à eux proposé une variante de l’algorithme de tri SampleSort qui dis- socie les comparaisons de la prédiction par l’utilisation d’instructions spécifiques au microprocesseur. Ces instructions peuvent s’apparenter à des instructions de mouvement conditionnelle CMOV. Similairement, Elmasry, Katajainen et Sten- mark ont proposé une variante de MergeSort[22] qui essaye de contourner au maximum l’utilisation des instructions de branchements.

Kaligosi et Sanders [28] ont publié des travaux sur une analyse poussée du nombre d’erreurs de prédiction produites en moyenne par des prédicteurs dy- namiques locaux. Cette étude a été faite dans le cadre de l’étude de QuickSort. Dans ce papier, les auteurs exploitent le fait que ces prédicteurs vont se com- porter comme une chaîne de Markov avec de bonnes propriétés qui convergent rapidement vers une unique distribution stationnaire. Par la suite, dans ce cha- pitre, nous utilisons des raisonnements similaires. Au moment où sont écrites ces lignes, la dernière version de Java utilise en plus de l’algorithme TimSort, une version de QuickSort a deux pivots qui, contre toutes attentes, a de bonnes performances en pratique. Les travaux de Martinez, Nebel et Wild [34] ont cependant montré que l’influence de la prédiction de branchements n’est pas suffisante pour expliquer ces bonnes performances.

Brodal et Moruz ont conduit une étude expérimentale [17] sur des arbres bi- naires de recherches déséquilibrés, mettant en évidence qu’il était possible pour des structures non équilibrées d’être plus efficaces en pratique par rapport au cas où ces structures sont bien équilibrées. Il s’agit ici d’un des premiers travaux à notre connaissance qui essaye de guider les prédicteurs de branchement. Notrecontribution s’approche de ces travaux mais se concentre sur les algorithmes plutôt que sur la structure des données. Nos travaux ont été publiés dans la conférence STACS 2016 [10]. Ce chapitre présente une version détaillée des tra- vaux qui ont été publiés. Les algorithmes étudiés sont principalement composés de quelques instructions de branchement qui sont exécutées à plusieurs reprises par l’action d’une boucle. C’est par exemple le cas de l’exponentiation rapide qui permet de calculer pour un réel x et un entier naturel n la valeur x. En plus de fournir une analyse de ces algorithmes sur le nombre d’erreurs de prédic- tion, nous avons proposé des modifications peu coûteuses de ces derniers afin de guider la prédiction de branchement. Une contribution que nous avons apportée avec ces travaux concerne la prédiction globale. Nous avons proposé une analyse du nombre d’erreurs de prédiction pour la recherche dichotomique dans le cas où la prédiction est effectuée par un prédicteur global. Nous y sommes arrivés en exploitant des propriétés de l’algorithme, mais il s’agit à notre connaissance du premier cas où une analyse a été faite sur ce type de prédicteur.