Carine Pivoteau (LIGM, Marne-la-Vallée)

La plupart des processeurs modernes sont très fortement parallélisme et utilisent des prédicteurs pour deviner la direction des branchements conditionnels dans les programmes, afin d’éviter de coûteux retards dans leur « pipeline ».

Nous proposons des variantes adaptées à ces prédicteurs pour deux algorithmes classiques :l’exponentiation rapide et la recherche dichotomique. En utilisant des arguments combinatoires et des résultats simples sur les chaînes de Markov, nous montrons que les améliorations proposées conduisent à moins d’erreurs de prédiction en moyenne, au prix d’un petit accroissement du nombre d’opérations basiques. Ces résultats théoriques sont confirmés par des tests en pratique qui montrent que nos algorithmes sont sensiblement plus rapides que les algorithmes standards, pour des types de données primitifs.