Stockage NRC et Cache

Bonsoir,

Que signifie exactement NRC ?

La représentation mémoire d'un stockage NRC est-elle bien la suivante ?

Code:

---

1 2 3 4 5 6

int** matrix = new int*[height]; matrix[0] = new int[height*width]; for(int i = 0; i < height; ++i) matrix[i] = matrix[i-1] + width ;

---

L'avantage est-il bien que le cache tire parti de la localité spatiale du tableau en matrix[0] ?

Quel que soit i,j, des appels successifs à matrix[i][j] sont forcément des caches hits ?

Quelle est la différence (du point de vue du cache) entre le stockage NRC et int* matrix = new int[width*height] ?

Merci

Numerical Recipes in C (un bouquin) et oui c'est ça.

(pour le reste pas le temps j'éditerais plus tard )

Citation:

---

Envoyé par Agoudard

Quel que soit i,j, des appels successifs à matrix[i][j] sont forcément des caches hits ?

---

Non.

Citation:

---

Envoyé par Agoudard

Quelle est la différence (du point de vue du cache) entre le stockage NRC et int* matrix = new int[width*height] ?

---

l'interet est d'elimine les calculs d'index polynomiaux en laissant le compilo inliner/pipeliner le calcul d'adresse en [i][j]. Ca simplifie aussi les acces par blocking ou dans des zones memoires de formes arbitraires totu en conservant la localite.

Citation:

---

l'interet est d'elimine les calculs d'index polynomiaux en laissant le compilo inliner/pipeliner le calcul d'adresse en [i][j]. Ca simplifie aussi les acces par blocking ou dans des zones memoires de formes arbitraires totu en conservant la localite.

---

Joel F, je sais que tu n'es aucunement là pour dispenser un cours sur le C++, mais je t'assure que même avec la meilleure volonté du monde, et après avoir lu en long en large et en travers tes liens et tes post, j'ai un mal fou à comprendre ce dont tu parles.

Je comprend (je crois) la deuxième partie :
Puisqu'on accède en général à des index adjacents dans la mémoire, lors du premier accès, un block mémoire contenant l'index demandé ainsi que les zones mémoires adjacentes et envoyé dans le cache. Ainsi les appels successifs aux index adjacent sont des caches hits. C'est ça ?

EDIT : Oh punaise, j'ai compris la première partie aussi (je crois), tu veux dire que le calcul d'index i,j dans le cas d'un tableau unidimensionnel implique un calcul polynomial pour trouver l'index dans le tableau unidimensionnel ?

Citation:

---

Envoyé par Agoudard

Joel F, je sais que tu n'es aucunement là pour dispenser un cours sur le C++, mais je t'assure que même avec la meilleure volonté du monde, et après avoir lu en long en large et en travers tes liens et tes post, j'ai un mal fou à comprendre ce dont tu parles.

---

si je suis pas clair dis moi je reexplique

Citation:

---

Envoyé par Agoudard

Je comprend (je crois) la deuxième partie :
Puisqu'on accède en général à des index adjacents dans la mémoire, lors du premier accès, un block mémoire contenant l'index demandé ainsi que les zones mémoires adjacentes et envoyé dans le cache. Ainsi les appels successifs aux index adjacent sont des caches hits. C'est ça ?

---

oui

Citation:

---

Envoyé par Agoudard

EDIT : Oh punaise, j'ai compris la première partie aussi (je crois), tu veux dire que le calcul d'index i,j dans le cas d'un tableau unidimensionnel implique un calcul polynomial pour trouver l'index dans le tableau unidimensionnel ?

---

oui le fameux i + j*w qui devient vite un i +j*w +k*h*w en 3D etc ..

Pour moi, la technique s'appelle vecteur de Iliffe vecteur de Iliffe. On précalcule simplement une partie du calcul d'adresse que l'on stocke le résultat. C'est le genre de transformations dont l'intérêt dépend du contexte; augmenter la mémoire pour gagner en perf n'est pas toujours gagnant.

Citation:

---

Envoyé par Joel F

oui le fameux i + j*w qui devient vite un i +j*w +k*h*w en 3D etc ..

---

En passant, quelqu'un d'attentif aux perfs ne va pas écrire i +j*w +k*h*w. Soit il écrit i + w*(j+h*k), soit il précalcule h*w. Et dans des boucles, il va chercher à ne faire que des additions en conservant des résultats intermédiaires (ou vérifier que l'optimiseur effectue lui-même cette transformation).

Citation:

---

Envoyé par Jean-Marc.Bourguet

Pour moi, la technique s'appelle vecteur de Iliffe vecteur de Iliffe. On précalcule simplement une partie du calcul d'adresse que l'on stocke le résultat. C'est le genre de transformations dont l'intérêt dépend du contexte; augmenter la mémoire pour gagner en perf n'est pas toujours gagnant.

---

Oh je note le nom.

Pour nous ca a permis de rendre recursif et facilement extensible la gestion de tableau a nD, n arbitraire. Quant a la surconsomamtion memoire, elle est relativement facile a maitriser. Asymptotiquement, l'overhead est proportionelle a 1/W.

Citation:

---

Envoyé par Jean-Marc.Bourguet

En passant, quelqu'un d'attentif aux perfs ne va pas écrire i +j*w +k*h*w. Soit il écrit i + w*(j+h*k), soit il précalcule h*w. Et dans des boucles, il va chercher à ne faire que des additions en conservant des résultats intermédiaires (ou vérifier que l'optimiseur effectue lui-même cette transformation).

---

Il le fait mais apparement pas au dela de 3 dimension :/
Sinon oui, on passera plutot par un Horner ou un Estrin pour evaluer l'addressage.

La page wikipedia est neanmoins fausse, le surcout du dereferencement des pointeurs dans le cadre d'un nid de boucle est negligeable.

Citation:

---

si je suis pas clair dis moi je reexplique

---

J'apprécie beaucoup, et malgré mes difficultés de compréhension, les réponses sur ce forum mon fait avancer d'avantage que mes 3 années de licence info...
Donc merci à tous...

Pour en revenir au vecteur de Iliffe, et aux matrice...
La meilleur optimisation pour l'implémentation d'une matrice et l'utilisation d'un vecteur de Iliffe couplé à un blocking lors des opérations mathématiques entres grandes matrices.... C'est ça ?

Comment utiliser un vecteur de Iliffe avec un accesseur [][] sans avoir les données publiques. Faut-il créer un objet intermédiaire dont la donnée serait un pointeur dans le vecteur de Iliffe ? Si oui pourquoi cela n'a pas d'impact sur les performances ?

J'ai encore du mal avec les caches... j'ai trouvé plusieurs documents mais il s'agit uniquement de supports de cours je crois. Donc beaucoup de déduction.
Par exemple je ne vois pas de différence entre :
i +j*w +k*h*w et i + w*(j+h*k) hormis le fait qu'il n'y a que 4 opérations dans la deuxième forme.

Citation:

---

Envoyé par Agoudard

Pour en revenir au vecteur de Iliffe, et aux matrice...
La meilleur optimisation pour l'implémentation d'une matrice et l'utilisation d'un vecteur de Iliffe couplé à un blocking lors des opérations mathématiques entres grandes matrices.... C'est ça ?

---

Le bvecteur de Iliffe permet d'ecrire simplement le blocking et autre acces non triviaux du a des optimisations de nids de boucles (strip mining, unrolling,etc) sans a gerer des idnexages compliqué. Le blocking n'a d'interet si ton operation a besoin d'une localité spatiale. Par exemple a+b n'a pas besoin de blocking, a*b matricielle par contre en a besoin.

cf http://boost.codepad.org/PPN6uRYy :

Citation:

---

Envoyé par Agoudard

Comment utiliser un vecteur de Iliffe avec un accesseur [][] sans avoir les données publiques. Faut-il créer un objet intermédiaire dont la donnée serait un pointeur dans le vecteur de Iliffe ? Si oui pourquoi cela n'a pas d'impact sur les performances ?

---

Tu mets la paire de pointeur dans un classe. le constructeur prend h,w et effectue l'allcoation, le destructeur la liberation. Ensuite, un operateur()(i,j) fait l'acces. Je dosi avoir ca dans mes cours, je te le copie/colle un peu plus tard. En utilisant std::vector au lieu d'un pointeur nu, tu gagen aussi un resize trivial a ecrire.

Citation:

---

Envoyé par Agoudard

J'ai encore du mal avec les caches... j'ai trouvé plusieurs documents mais il s'agit uniquement de supports de cours je crois. Donc beaucoup de déduction.
Par exemple je ne vois pas de différence entre :
i +j*w +k*h*w et i + w*(j+h*k) hormis le fait qu'il n'y a que 4 opérations dans la deuxième forme.

---

Ce calcul n'impacte pas le cache mais la complexité du calcul d'adresse.

Bonjour,

en ce qui concerne les caches, j'avais bien apprécié la lecture du livre : Computer Organization and Design: The Hardware/Software Interface, de Patterson et Hennessy :
http://books.google.fr/books?id=3b63...page&q&f=false

Citation:

---

Envoyé par Joel F

La page wikipedia est neanmoins fausse, le surcout du dereferencement des pointeurs dans le cadre d'un nid de boucle est negligeable.

---

Je dirai plutot qu'elle oublie les caches... Si tu dois aller indexer dans la memoire principale avec un temps d'acces de l'ordre de 150 cycles, c'est pas avantageux. Mais on a des caches et les temps d'acces de l'ordre de 3 cycles du L1 sont clairement avantageux, sur le L2 on doit dependre beaucoup d'autres facteurs. Les caches faisant du prefech pour les acces sequentiels, en etant prudent on doit pouvoir rester tres proches des temps du L1.

Citation:

---

Envoyé par Aleph69

Bonjour,

en ce qui concerne les caches, j'avais bien apprécié la lecture du livre : Computer Organization and Design: The Hardware/Software Interface, de Patterson et Hennessy :
http://books.google.fr/books?id=3b63...page&q&f=false

---

Je n'ai pas lu cet ouvrage, mais Computer Architecture: A Quantitative Approach des memes auteurs est la reference en la matiere. Si j'ai bonne memoire, les annexes de la troisieme edition sont en ligne et il y en a une sur les caches. Mais je ne suis pas sur que ca aide a les utiliser. Ulrich Drepper a ecrit quelque chose sur le sujet: http://www.akkadia.org/drepper/cpumemory.pdf correspondant peut-etre mieux aux attentes de l'OP.

Citation:

---

Envoyé par Jean-Marc.Bourguet

Je dirai plutot qu'elle oublie les caches... Si tu dois aller indexer dans la memoire principale avec un temps d'acces de l'ordre de 150 cycles, c'est pas avantageux. Mais on a des caches et les temps d'acces de l'ordre de 3 cycles du L1 sont clairement avantageux, sur le L2 on doit dependre beaucoup d'autres facteurs. Les caches faisant du prefech pour les acces sequentiels, en etant prudent on doit pouvoir rester tres proches des temps du L1.

---

Exactement. Dans nos benhcs, la methode Iliffe est a +/- 3% de la methode lineaire

Citation:

---

Envoyé par Jean-Marc.Bourguet

Je n'ai pas lu cet ouvrage, mais Computer Architecture: A Quantitative Approach des memes auteurs est la reference en la matiere. Si j'ai bonne memoire, les annexes de la troisieme edition sont en ligne et il y en a une sur les caches. Mais je ne suis pas sur que ca aide a les utiliser.

---

Merci pour la référence, je ne connaissais pas ce livre. Sinon, pour se faire une première idée sur l'impact des caches sur les performances et sur les techniques de transformation de programme, il y a la thèse de David Parello qui a le mérite d'être écrite en français :
http://perso.univ-perp.fr/david.pare...ello_these.pdf

Citation:

---

Merci pour la référence, je ne connaissais pas ce livre. Sinon, pour se faire une première idée sur l'impact des caches sur les performances et sur les techniques de transformation de programme, il y a la thèse de David Parello qui a le mérite d'être écrite en français :
http://perso.univ-perp.fr/david.pare...ello_these.pdf

---

Super doc, merci :)