Spatiale vs Temporelle de la localité

Je comprends les définitions des termes, mais je vais avoir de la difficulté à appliquer les concepts de code. Pour un exercice, on nous demande de décrire si le code suivant est spatial ou temporel:

for (int i=0; i<10; i++) {
    printf(some_array[i]);
}

J'ai l'impression que c'est spatiale localité parce que quand un indice du tableau est accessible, le prochain indice de l'emplacement de la mémoire sera accessible dès que itération de la boucle. Est-ce la bonne façon de le regarder? Qu'est ce qui détermine si le code est temporal et spatiale? D'autres exemples seraient grands.

double possible de l'analyse de code spatiale et temporelle de la localité
L'utilisation de "printf" d'un exemple pour le sujet de la nouvelle mise en mémoire cache et les accès à la mémoire est un très mauvais choix. La surcharge de printf est énorme par rapport à l'endroit où les éléments de some_array sont. En outre, il est vraiment une mauvaise idée de printf à partir d'un non const chaîne de format. Ce qui se passe si some_array[0] = "%s"? De mieux à faire printf("%s",some_array[i]) ou puts(some_array[i]).

OriginalL'auteur raphnguyen | 2011-08-31

  1. 11

    C'est un peu un exercice ridicule, vraiment. Le Code n'est pas temporelle ou spatiale.

    Mais localité temporelle implique que vous allez accéder à la même adresse à de multiples reprises, relativement étroite dans le temps. Vous n'êtes pas le faire ici (sauf si vous comptez accéder à i, je suppose), donc par un processus d'élimination, vous pouvez en conclure que ce doit être spatiale de la localité.

    Plus précisément, vous avez accès some_array[0], puis some_array[1], etc. etc. Ces sont proches dans l'espace d'adresse, donc oui, cela peut être "s'appuyant" sur spatiale localité.

    Merci pour les précisions!
    n'est-ce pas le code bénéficié de localité temporelle dans la boucle ?
    OMI, pas. Voir mon commentaire à dario_ramos de réponse.
    je veux dire le "code" désigne le code machine bénéficieront de localité temporelle, comme la section de la boucle opcodes est utilisé à plusieurs reprises, si elles sont portées dans le cache d'instructions, et n'est pas supprimée jusqu'à ce qu'une période (déterminée par le cache de politiques en matière de remplacement).
    Oh, je vois. Oui, vous avez raison; j'étais seulement compte tenu du cache de données.

    OriginalL'auteur Oliver Charlesworth

  2. 5

    Dans le contexte de matériel à la mémoire cache, qui est l'endroit où ces concepts viennent généralement, l'analyse n'est pas fait généralement sur une adresse de mémoire de base, pour ainsi dire. La localité est analysé par l'accès à des blocs de mémoire, ceux qui sont transférées entre le cache et la mémoire principale.

    Si vous pensez que de cette façon, votre code est à la fois temporelle et spatiale de la localité. Lorsque votre code lit some_array[0], si son adresse n'est pas trouvée dans le cache, il est lu à partir de la mémoire principale et l'ensemble du bloc qui le contient est copié dans la mémoire cache. Il remplace les unes des autres bloc suivant une certaine politique: MRU, par exemple.

    Ensuite, lorsque vous accédez à some_array[1] un peu de temps plus tard, son bloc est déjà dans le cache, de sorte que le temps de lecture sera plus petite. Notez que vous avez accédé à la même bloc, et dans une petite quantité de temps. Donc, vous avez à la fois spatiale et temporelle de la localité.

    Mémoire Cache prend avantage de la répartition spatiale et temporelle de la localité afin de fournir un meilleur accès à la mémoire. D'autre part, si votre code peut prendre avantage de cela est une toute autre question, tout à fait. Néanmoins, le compilateur va faire la plupart des optimisations pour vous, alors vous ne devez vous préoccuper de cette après la découverte d'un goulot d'étranglement dans un profil de session. Dans les environnements Linux, Cachegrind est excellent pour cela.

    Merci de prendre le temps de le décomposer!
    Je ne suis pas sûr de ce qui est temporel de la localité. Par définition, il serait impossible d'avoir spatiale de la localité sans gagnent aussi de la localité temporelle (c'est à dire les deux seraient inséparables). Pour moi, temporelle localité se réfère à l'accès à l' adresse plusieurs fois, indépendamment des caractéristiques de cache. Cela ne se produit pas dans le cas des OP code.
    Que faire si vous accédez à la même bloc de mémoire toutes les 20 minutes? (Par exemple, l'interrogation de la mémoire partagée pour le contrôle de certaines ressources). C'est juste spatiale, et non temporelle. Il ne serait probablement pas bénéficier de la cache si, dans ces 20 minutes, d'autres processus d'accès mémoire et avait le bloc supprimé
    Mais par définition, l'organisation spatiale de la localité n'est jamais utile sur son propre!

    OriginalL'auteur dario_ramos

  3. 2

    Ce code a temporelles de la localité dans le cache d'instructions parce que vous êtes à répéter le code à chaque boucle (en supposant que votre optimiseur de ne pas dérouler la boucle). Il a également spatiales de la localité dans le cache de données parce que si vous accédez à l'élément de tableau, je vous aurez bientôt accès à des éléments de i+1, i+2, etc. Si votre cache de données en ligne de la taille est de 16 octets, et votre tableau est en entiers 32 bits, alors votre cache de données également chargé éléments 1, 2, et 3 si vous avez demandé l'élément 0 (en supposant que notre tableau commencé à une limite de ligne de cache).

    OriginalL'auteur Phil Harbison

  4. 1

    Le code a seulement spatiale de la localité, mais pas de localité temporelle - dans le contexte de la cache d'accès à la mémoire.

    Pendant le chargement des données dans le cache, toute une ligne/bloc est chargé - d'où les demandes d'accès à l'exact le même emplacement de mémoire ainsi que les adresses qui font également partie du même bloc dans le cache aurait accès rapide à la fois.

    Il y a des façons d'optimiser votre code, tels que le montant de lit sont de la cache au lieu de le faire directement à partir de la mémoire principale:
    1. Si vous pouvez accéder à tous les voisins de la mémoire des adresses en prenant avantage de la première cache-miss, et avant ce bloc est supprimé du cache - puis vous faites usage de la localité spatiale.
    2. Si vous avez accès au même emplacement de mémoire autant de fois que nécessaire pour votre programme avant le bloc dans le cache expulsés - ensuite, vous prenez avantage de la localité temporelle.

    Exemples comme la multiplication de matrice aurait à la fois temporelle et spatiale de la localité.

    OriginalL'auteur Tuxdude