IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C++ Discussion :

Stockage NRC et Cache


Sujet :

C++

  1. #1
    Membre du Club
    Profil pro
    Inscrit en
    Avril 2010
    Messages
    96
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2010
    Messages : 96
    Points : 47
    Points
    47
    Par défaut Stockage NRC et Cache
    Bonsoir,

    Que signifie exactement NRC ?

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

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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

  2. #2
    Membre chevronné
    Avatar de Goten
    Profil pro
    Inscrit en
    Juillet 2008
    Messages
    1 580
    Détails du profil
    Informations personnelles :
    Âge : 33
    Localisation : France

    Informations forums :
    Inscription : Juillet 2008
    Messages : 1 580
    Points : 2 205
    Points
    2 205
    Par défaut
    Numerical Recipes in C (un bouquin) et oui c'est ça.

    (pour le reste pas le temps j'éditerais plus tard )
    "Hardcoded types are to generic code what magic constants are to regular code." --A. Alexandrescu

  3. #3
    Membre chevronné
    Avatar de Joel F
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Septembre 2002
    Messages
    918
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Service public

    Informations forums :
    Inscription : Septembre 2002
    Messages : 918
    Points : 1 921
    Points
    1 921
    Par défaut
    Citation Envoyé par Agoudard Voir le message
    Quel que soit i,j, des appels successifs à matrix[i][j] sont forcément des caches hits ?
    Non.

    Citation Envoyé par Agoudard Voir le message
    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.

  4. #4
    Membre du Club
    Profil pro
    Inscrit en
    Avril 2010
    Messages
    96
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2010
    Messages : 96
    Points : 47
    Points
    47
    Par défaut
    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 ?

  5. #5
    Membre chevronné
    Avatar de Joel F
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Septembre 2002
    Messages
    918
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Service public

    Informations forums :
    Inscription : Septembre 2002
    Messages : 918
    Points : 1 921
    Points
    1 921
    Par défaut
    Citation Envoyé par Agoudard Voir le message
    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 Voir le message
    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 Voir le message
    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 ..

  6. #6
    Expert éminent

    Inscrit en
    Novembre 2005
    Messages
    5 145
    Détails du profil
    Informations forums :
    Inscription : Novembre 2005
    Messages : 5 145
    Points : 6 911
    Points
    6 911
    Par défaut
    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 Voir le message
    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).
    Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.

  7. #7
    Membre chevronné
    Avatar de Joel F
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Septembre 2002
    Messages
    918
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Service public

    Informations forums :
    Inscription : Septembre 2002
    Messages : 918
    Points : 1 921
    Points
    1 921
    Par défaut
    Citation Envoyé par Jean-Marc.Bourguet Voir le message
    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 Voir le message
    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.

  8. #8
    Membre du Club
    Profil pro
    Inscrit en
    Avril 2010
    Messages
    96
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2010
    Messages : 96
    Points : 47
    Points
    47
    Par défaut
    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.

  9. #9
    Membre chevronné
    Avatar de Joel F
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Septembre 2002
    Messages
    918
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Service public

    Informations forums :
    Inscription : Septembre 2002
    Messages : 918
    Points : 1 921
    Points
    1 921
    Par défaut
    Citation Envoyé par Agoudard Voir le message
    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 Voir le message
    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 Voir le message
    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.

  10. #10
    Membre expérimenté
    Homme Profil pro
    Chercheur
    Inscrit en
    Mars 2010
    Messages
    1 218
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Chercheur

    Informations forums :
    Inscription : Mars 2010
    Messages : 1 218
    Points : 1 685
    Points
    1 685
    Par défaut
    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

  11. #11
    Expert éminent

    Inscrit en
    Novembre 2005
    Messages
    5 145
    Détails du profil
    Informations forums :
    Inscription : Novembre 2005
    Messages : 5 145
    Points : 6 911
    Points
    6 911
    Par défaut
    Citation Envoyé par Joel F Voir le message
    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.
    Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.

  12. #12
    Expert éminent

    Inscrit en
    Novembre 2005
    Messages
    5 145
    Détails du profil
    Informations forums :
    Inscription : Novembre 2005
    Messages : 5 145
    Points : 6 911
    Points
    6 911
    Par défaut
    Citation Envoyé par Aleph69 Voir le message
    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.
    Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.

  13. #13
    Membre chevronné
    Avatar de Joel F
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Septembre 2002
    Messages
    918
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Service public

    Informations forums :
    Inscription : Septembre 2002
    Messages : 918
    Points : 1 921
    Points
    1 921
    Par défaut
    Citation Envoyé par Jean-Marc.Bourguet Voir le message
    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

  14. #14
    Membre expérimenté
    Homme Profil pro
    Chercheur
    Inscrit en
    Mars 2010
    Messages
    1 218
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Chercheur

    Informations forums :
    Inscription : Mars 2010
    Messages : 1 218
    Points : 1 685
    Points
    1 685
    Par défaut
    Citation Envoyé par Jean-Marc.Bourguet Voir le message
    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

  15. #15
    Membre du Club
    Profil pro
    Inscrit en
    Avril 2010
    Messages
    96
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2010
    Messages : 96
    Points : 47
    Points
    47
    Par défaut
    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

Discussions similaires

  1. lieu de stockage des objets cachés pat Ehcache
    Par root76 dans le forum Hibernate
    Réponses: 3
    Dernier message: 12/02/2009, 11h08
  2. [Projet Java] Serveur de stockage ou Proxy-cache Web
    Par Yann39 dans le forum Général Java
    Réponses: 3
    Dernier message: 15/05/2007, 13h33
  3. Répertoire caché
    Par KUBITUS dans le forum Delphi
    Réponses: 30
    Dernier message: 13/04/2007, 08h19
  4. Ouvrir (fopen) un fichier caché
    Par shef dans le forum C
    Réponses: 2
    Dernier message: 09/09/2002, 10h06
  5. Webbrowser : Comment ne pas prendre la page en cache
    Par cedm78 dans le forum Web & réseau
    Réponses: 3
    Dernier message: 30/08/2002, 12h17

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo