Addition fausse dans un cas

**progfou** · 09/07/2007, 11h31

Bonjour tout le monde !
Je dois avoir la tête dans le c** car j'ai beau chercher je ne vois pas la différence entre ce code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
for (x=0 ; x<size ; x++)
{
  dst[x]+=src[x];
}

et celui-ci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
for (x=0 ; x<size/8 ; x+=8)
{
  dst[x]+=src[x];
  dst[x+1]+=src[x+1];
  dst[x+2]+=src[x+2];
  dst[x+3]+=src[x+3];
  dst[x+4]+=src[x+4];
  dst[x+5]+=src[x+5];
  dst[x+6]+=src[x+6];
  dst[x+7]+=src[x+7];
}

Je précise que dst et src sont deux tableaux de type short*, et que taille est bien entendu divisible par 8. Dans le premier cas, le résultat est bon, pas dans le second...

Merci d'avance !

**Jean-Marc.Bourguet** · 09/07/2007, 11h36

Pourquoi changes-tu la condition d'arret?

**progfou** · 09/07/2007, 11h39

Eh bien, je fais 8 additions successives, il y a 8 fois moins de tours dans la boucle, non ?

**Jean-Marc.Bourguet** · 09/07/2007, 11h39

Tu modifies deja ton pas.

**progfou** · 09/07/2007, 11h39

le boulet...
Merci !

**Médinoc** · 09/07/2007, 11h44

PS: Ton code ne marchera que si la taille est multiple de 8...

**r0d** · 09/07/2007, 11h45

J'en profites que le sujet est résolu pour poser une question.
Il semble qu'avec les processeurs actuels, il est inutile de dérouler les boucles (en terme d'optimisation). Cependant, je ne trouve rien de précis à ce sujet, ni sur la toile, ni dans les bouquins que j'ai à ma disposition.
Est-ce que quelqu'un aurait quelques infos?

**progfou** · 09/07/2007, 11h51

En général, sur les petites boucles, les compilateurs s'en sortent pas trop mal.
Mais il est possible de faire du cache blocking, en adaptant le déroulage de grosses boucles, pour améliorer la localité spatiale.

**Charlemagne** · 09/07/2007, 14h29

Envoyé par r0d

J'en profites que le sujet est résolu pour poser une question.
Il semble qu'avec les processeurs actuels, il est inutile de dérouler les boucles (en terme d'optimisation). Cependant, je ne trouve rien de précis à ce sujet, ni sur la toile, ni dans les bouquins que j'ai à ma disposition.
Est-ce que quelqu'un aurait quelques infos?

C'est pas tant la boucle développée qui fait améliorer la vitesse (ça joue quand même), mais plutôt les instructions utilisées à l'intérieur de la boucle. Il faudrait voir comment les compilos codent la boucle développée précédente (ça dépend des compilos de toute façon), mais je ne crois pas qu'il le fasse aussi bien qu'avec la boucle suivante.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
for (int i=0; i<n; i+=8)
{
  int *px=&x[i], *py=y[i];
  py[0]=px[0];
  py[1]=px[1];
  py[2]=px[2];
  py[3]=px[3];
  py[4]=px[4];
  py[5]=px[5];
  py[6]=px[6];
  py[7]=px[7];
}

La grosse différence c'est que les index sont constants, et que le compilo peut utiliser des instructions assembleurs plus rapides (les décalages sont précalculés).
C'est l'une des 3-4 techniques de base pour améliorer les boucles.

Envoyé par progfou

Mais il est possible de faire du cache blocking, en adaptant le déroulage de grosses boucles, pour améliorer la localité spatiale.

Le cache blocking n'a pas de rapport direct avec le développement des boucles. Une boucle non développée peut très bien utiliser la mémoire cache.

**progfou** · 09/07/2007, 14h51

Le cache blocking a un rapport tout de même, puisque c'est diviser une boucle en deux (ou plus) pour améliorer la localité spatiale.

Ceci dit, dans les techniques d'optimisation de boucles, quelqu'un voit comment améliorer le problème suivant ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
for (j=0 ; j<sizeY ; j++)
{
  for (i=0 ; i<sizeX ; i++)
  {
    px[i] = py[j+stride];
  }
}

Où stride est un décalage en mémoire du nombre d'octets correspondant ?
C'est un cas "d'école" de transposition, mais c'est quelque chose que l'on peut rencontrer dans le cas de filtres en image (où l'on utilise les pixels des lignes et des colonnes en même temps)...
Comment, donc, éviter le saut ?

**Charlemagne** · 09/07/2007, 15h02

C'est bien ce que je dit: Y'a pas de rapport direct. Diviser une boucle en 2 (ou plus...)ne nécessite pas de développer cette boucle. Ton exemple divise bien une boucle en créant 2 boucles imbriquées...

Un stride, c'est un facteur multiplicatif sur l'index. Ce que tu décrit est un offset / décalage.
Rien de plus facile pour ôter un offsset:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
float *p=py[offset];
for (j=0 ; j<sizeY ; j++)
{
  for (i=0 ; i<sizeX ; i++)
  {
    px[i] = p[j];
  }
}

**progfou** · 09/07/2007, 15h09

Oups, effectivement, problème mal décrit...
Je vais donner le vrai cas :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
for( UInt y = 0; y < uiSizeY; y++)
{
	for( UInt x = 0; x < uiSizeX; x++)
	{
		Int iTempX;
		iTempX  = SrcX[x - 0];
		iTempX += SrcX[x + 1];
		iTempX  = iTempX << 2;
		iTempX -= SrcX[x - 1];
		iTempX -= SrcX[x + 2];
		iTempX += iTempX << 2;
		iTempX += SrcX[x - 2];
		iTempX += SrcX[x + 3];
 
		Int iTempY;
		iTempY  = SrcY[x - 0*iSrcStride];
		iTempY += SrcY[x + 1*iSrcStride];
		iTempY  = iTempY << 2;
		iTempY -= SrcY[x - 1*iSrcStride];
		iTempY -= SrcY[x + 2*iSrcStride];
		iTempY += iTempY << 2;
		iTempY += SrcY[x - 2*iSrcStride];
		iTempY += SrcY[x + 3*iSrcStride];
 
		Dest[x] = (iTempX + iTempY + 1) >> 1;
	}
}

Pour info, c'est un code qui fait de l'interpolation de mouvement. Dans mon cas, j'utilise les instructions SSE2, mais avant cela, j'aimerais réduire la complexité des accès.

**Charlemagne** · 09/07/2007, 15h15

J'ai pas regardé ton code. Un stride ne se laisse pas ôter facilement , voir pas du tout. Essaye de le remplacer par des constantes, à la façon que j'expose plus haut, mais je suis pas convaincu du tout que ce soit possible.

Si par "interpolation de mouvement" tu entends "Motion Estimation", on pourra peut-être comparer les perfs avec mon implémentation...

**progfou** · 09/07/2007, 15h23

C'est l'interpolation quart de pixel de h.264.

**Charlemagne** · 09/07/2007, 15h29

ah ok. Je n'ai qu'une implémentation sur les pixels entiers.
Il paraît que ça n'apporte pas grand chose ces interpolations. (déjà pour pour les 1/2 pixels). Et puis ça ne peut se faire qu'autour de l'estimation à pixels entiers. Tu confirmes?

**progfou** · 09/07/2007, 15h37

Je vais peut-être ouvrir un autre topic...

.

Ca apporte, car ça réduit quand même beaucoup les résidus après compensation de mouvement.

Envoyé par Charlemagne

Et puis ça ne peut se faire qu'autour de l'estimation à pixels entiers

Ca je n'ai pas compris

.

**Charlemagne** · 09/07/2007, 15h46

Ca apporte, mais in fine ça apporte beaucoup sur la qualité/taille de la vidéo?

Et puis ça ne peut se faire qu'autour de l'estimation à pixels entiers

Je veux dire que j'imagine que pour des raisons de performances on ne peut faire les interpolations que raisonablement dans le voisinage d'une première estimation, non?

**progfou** · 09/07/2007, 15h51

La référence :
http://www.rgu.ac.uk/files/h264_interpred.pdf

C'est court, mais suffisant. Je n'ai pas les chiffres quand à l'intérêt, mais il me semble que c'est pas mal du tout, comparé à ce qu'il se faisait jusque là.

**Charlemagne** · 09/07/2007, 16h00

Je sais pas maintenant, mais y'a 2-3 ans, H264 était aussi un champion de la lenteur. Du genre, il fallait le PC dernier cri pour lire une vidéo.

**progfou** · 09/07/2007, 17h43

Le codec x264 est particulièrement meilleur, il suffit d'avoir 800MHz pour décoder un flux...
Disons que les techniques de codage mises en oeuvre dans H.264 permettent un gain (en terme de débit) de 50% à qualité égale (en HD 1080i).

Ceci explique aussi cela...

.

Addition fausse dans un cas

C++

Discussions similaires

Partager

Partager