Chapter 10.10 : Optimisation et prédicteur de branchements



Comme nous l'avons vu dans la section 11.2.2.3.6 les branchements perturbent l'efficacité du préchargement des instructions par le CPU. Cet exemple montre concrètement les différences de vitesses d'exécution typiques que l'on peut attendre en fonction de la présence d'un branchement ou non.

Exemple tiré de~[143]How to optimize computation with HPC, Pierre Aubert :

Soit, une fonction qui copie les valeurs d'un tableau x ou y dans un tableau z en fonction de la valeur d'une variable aléatoire :

$$\begin{eqnarray*} z_{i} & = & \begin{cases} x_{i} & \alpha_{i}
La fonction C++ associée à cette copie est : 
1
2
3
4
5
6
7
8
9
10
11
12

void dummyCopy(float* tabResult,
		const float * tabX, const float* tabY, const float * tabProba,
		long unsigned int nbElement, float proba)
	{
	for(long unsigned int i(0lu); i < nbElement; ++i){
		if(tabProba[i] < proba){
			tabResult[i] = tabX[i];
		}else{
			tabResult[i] = tabY[i];
		}
	}
}


Puisque aucun calcul n'est fait dans cette fonction, les variations de la performance ne seront dues qu'à la condition ligne $6$ .



Il existe aussi une manière d'écrire cette fonction sans if :

1
2
3
4
5
6
7
8
9

void dummyCopy(float* tabResult,
		const float * tabX, const float* tabY, const float * tabProba,
		long unsigned int nbElement, float proba)
	{
	for(long unsigned int i(0lu); i < nbElement; ++i){
		float cond(tabProba[i] < proba);
		tabResult[i] = tabX[i]*cond + (1.0f - cond)*tabY[i];
	}
}


Bien que ces deux fonctions produisent les mêmes résultats, leurs performances sont très différentes (voir figure 25).

Tout d'abord, on constate que les performances de la fonction avec le if dépendent de la valeur de la variable $\mathtt{proba}$ passée en paramètre, en dépit du fait que la quantité d'instructions exécutées n'en dépend pas.

La performance est la plus dégradée lorsque $\mathtt{proba} = 0.5$ .

On peut le comprendre en prenant en compte l'existence du prédicteur de branchement. Comme le branchement dépend d'une variable aléatoire uniforme, cela implique dans ce cas que le prédicteur de branchement a toujours une chance sur deux de se tromper.

Cela implique de vider le pipeline, opération qui coûte $300$ cycles. Bien que la version sans branchements (sans if) charge plus de données en entrée et effectue plus de calculs par itération de boucle, ces opérations sont loin d'avoir un tel coût. C'est la raison pour laquelle elle est $4$ à $10$ fois plus rapide.

De plus, l'absence de branchement facilite également la vectorisation (voir chapitre 11.3), ce qui augmente encore les performances (voir figure 26).

nothing

Figure 25 : Performances de la fonction avec le if en violet et vert, et sans le if en bleu et orange, en fonction du seuil $\mathtt{proba}$ passé en paramètre. Aucune fonction n'est vectorisée.



nothing

Figure 26 : Performances de la fonction avec le if en violet et vert, et vectorisée en bleu et orange, en fonction du seuil $\mathtt{proba}$ passé en paramètre.