Brevet FR3045183A1 (20170616)
REVENDICATIONS1. Procédé de prédiction d'une donnée à précharger dans une mémoire cache, ce procédé comportant : a) pour chaque instant t où un microprocesseur exécute une instruction de lecture d'une donnée nécessaire à l'exécution d'un programme, le calcul (104) d'un écart, appelé delta, entre l'adresse de la donnée à lire contenue dans cette instruction de lecture exécutée à l'instant t et l'adresse de la donnée à lire contenue dans cette même instruction de lecture lors de sa précédente exécution à un instant t-1, deux instructions de lecture étant les mêmes si elles correspondent toutes les deux à la même valeur du compteur ordinal du microprocesseur, b) la mémorisation (108) d'une séquence d'accès observée contenant uniquement les N deltas calculés successivement pour chaque instant t compris à l'intérieur d'une fenêtre glissante [t1 ; to], où les instants to et t1 sont égaux aux instants t, respectivement le plus récent et le plus ancien, pour lesquels a été calculé un delta de la séquence d'accès observée et le nombre N est un nombre entier prédéterminé supérieur ou égal à deux, caractérisé en ce que le procédé comporte aussi : c) l'acquisition (110 ;\n<CLM>\1\td'une distribution statistique, dite " modèle ", des deltas 20 d'une séquence d'accès modèle, cette distribution statistique modèle comportant : - des classes de valeurs possibles pour les deltas, et associé à chacune de ces classes, - un nombre fonction du nombre d'occurrence de cette classe dans la séquence d'accès modèle, 25 d) la construction (112 ;\n<CLM>\1\td'une distribution statistique, dite "observée", des deltas de la séquence d'accès observée, e) l'identification (114,\n<CLM>\1\tdans la distribution statistique observée, en la comparant avec la distribution statistique modèle, de la classe la plus déficitaire, c'est-à-dire de la classe pour laquelle la différence NoDSM - NoDSO est maximale, où NoDSM et 30 NoDSO sont les nombres d'occurrence de cette classe déduits, respectivement, de la distribution statistique modèle et de la distribution statistique observée, f) la fourniture (116) en tant que prédiction de la donnée à précharger dans la mémoire cache avant la prochaine exécution de la même instruction de lecture, d'au moins une adresse prédite où est contenue la donnée à précharger, cette adresse 35 prédite étant construite à partir de la classe la plus déficitaire identifiée lors de l'étape e).\n<CLM>\1\tProcédé selon la revendication 1, dans lequel, lors de l'étape c), l'acquisition de la 3045183 28 distribution statistique modèle comporte : - la mémorisation (108) d'une séquence d'accès modèle contenant uniquement les M derniers deltas successivement calculés pour chaque instant t compris à l'intérieur d'une fenêtre glissante [t3 ; t2] antérieure à la fenêtre glissante [t1 ; to], où les instants t2 5 et t3 sont égaux aux instants t, respectivement le plus récent et le plus ancien, pour lesquels a été calculé un delta de la séquence d'accès modèle, et le nombre de deltas calculés pour des instants t compris entre les instants t2 et t1 est une constante prédéterminée, et le nombre M est un nombre entier prédéterminé supérieur ou égal à deux, et 10 - à chaque fois qu'une nouvelle séquence d'accès modèle est mémorisée, la construction (110 ;\n<CLM>\1\tde la distribution statistique modèle à partir des deltas de cette séquence d'accès modèle mémorisée.\n<CLM>\1\tProcédé selon la revendication 2, dans lequel, systématiquement, il n'existe 15 aucun instant t compris entre les instants t2 et t1 pour lequel un delta est calculé de sorte que la séquence d'accès modèle précède immédiatement en permanence la séquence d'accès observée.\n<CLM>\1\tProcédé selon l'une quelconque des revendications précédentes, dans lequel le 20 procédé comporte : - le calcul (160) d'une métrique de similarité dont la valeur varie de façon monotone en fonction de l'importance des différences entre les distributions statistiques modèle et observée et/ou le calcul (164) d'une erreur de prédiction dont la valeur varie de façon monotone en fonction du nombre de fois où l'adresse prédite à partir de la 25 séquence d'accès observée pendant la fenêtre glissante [t1 ; to] est différente de l'adresse de la donnée à lire réellement contenue dans l'instruction de lecture exécutée à l'instant suivant to+1, et - en réponse au franchissement d'un seuil prédéterminé par la métrique de similarité calculée et/ou par l'erreur de prédiction calculée, la modification (168) du nombre N 30 de deltas contenus dans la séquence d'accès observée ou du nombre M de deltas contenus dans la séquence d'accès modèle.\n<CLM>\1\tProcédé selon l'une quelconque des revendications précédentes, dans lequel le procédé comporte : 35 - le calcul (160) d'une première métrique de similarité dont la valeur varie de façon monotone en fonction de l'importance des différences entre les distributions statistiques modèle et observée et/ou le calcul (164) d'une première erreur de prédiction dont la valeur varie de façon monotone en fonction du nombre de fois où 3045183 29 l'adresse prédite à partir de la distribution statistique modèle et de la séquence d'accès observée pendant la fenêtre glissante [t1 ; to] est différente de l'adresse de la donnée à lire réellement contenue dans l'instruction de lecture exécutée à l'instant suivant to+1, et 5 - la mémorisation (180) d'une séquence d'accès, dite " de prédiction ", contenant uniquement P deltas successivement calculés pour chaque instant t compris à l'intérieur d'une fenêtre glissante [t5; t4] antérieure à la fenêtre glissante [t1 ; to], où les instants t4 et t5 sont égaux aux instants t, respectivement le plus récent et le plus ancien, pour lesquels a été calculé un delta de la séquence d'accès de prédiction et 10 le nombre P est nombre entier prédéterminé différent du nombre M, - la construction (182) d'une distribution statistique dite " de prédiction ", à partir des deltas de la séquence d'accès de prédiction, - le calcul (184) d'une seconde métrique de similarité et/ou d'une seconde erreur de prédiction en utilisant la distribution statistique de prospection à la place de la 15 distribution statistique modèle, puis - si la seconde métrique de similarité calculée ou la seconde erreur de prédiction calculée est meilleure que, respectivement, la première métrique de similarité calculée ou la première erreur de prédiction calculée, alors le nombre M est pris égale (186) au nombre P pour l'itération suivante du procédé, sinon le nombre M reste inchangé.\n<CLM>\1\tProcédé selon l'une quelconque des revendications précédentes, dans lequel la séquence d'accès observée contient systématiquement le delta calculé à partir de l'adresse de la donnée à lire contenue dans l'instruction de lecture exécutée le plus 25 récemment.\n<CLM>\1\tProcédé selon l'une quelconque des revendications précédentes, dans lequel, à chaque itération de l'étape e), une seule adresse prédite est fournie. 30\n<CLM>\1\tProcédé d'exécution d'un programme, enregistré dans une mémoire principale, par un microprocesseur associé à une mémoire cache, ce procédé comportant : - l'exécution par le microprocesseur d'une instruction de lecture d'une donnée nécessaire à l'exécution du programme, cette instruction contenant l'adresse où est enregistrée cette donnée dans la mémoire principale, 35 - si la donnée correspondant à l'adresse contenue dans l'instruction de lecture à exécuter se trouve dans la mémoire cache, la lecture (56) de cette donnée dans la 3045183 30 mémoire cache, et sinon la lecture (58) de cette donnée dans la mémoire principale ou dans une autre mémoire différente de la mémoire cache, - avant que le microprocesseur exécute une nouvelle fois la même instruction de lecture, la prédiction (62) de la donnée à précharger dans la mémoire cache et le 5 préchargement de la donnée prédite dans la mémoire cache ou dans une mémoire tampon, caractérisé en ce que la prédiction (62) est réalisée conformément à l'une quelconque des revendications précédentes. lo\n<CLM>\1\tSupport d'enregistrement d'informations, caractérisé en ce qu'il comporte des instructions pour l'exécution d'un procédé conforme à l'une quelconque des revendications précédentes, lorsque ces instructions sont exécutées par un microprocesseur. 15\n<CLM>\1\tModule électronique (24) de prédiction d'une donnée à précharger dans une mémoire cache, ce module étant agencé pour: a) pour chaque instant t où un microprocesseur exécute une instruction de lecture d'une donnée nécessaire à l'exécution d'un programme, calculer un écart, appelé delta, entre l'adresse de la donnée à lire contenue dans cette instruction de lecture 20 exécutée à l'instant t et l'adresse de la donnée à lire contenue dans cette même instruction de lecture lors de sa précédente exécution à un instant t-1, deux instructions de lecture étant les mêmes si elles correspondent toutes les deux à la même valeur du compteur ordinal du microprocesseur, b) mémoriser une séquence d'accès observée contenant uniquement les N deltas calculés successivement pour chaque instant t compris à l'intérieur d'une fenêtre glissante [t1 ; to], où les instants to et t1 sont égaux aux instants t, respectivement le plus récent et le plus ancien, pour lesquels a été calculé un delta de la séquence d'accès observée et le nombre N est un nombre entier prédéterminé supérieur ou égal à deux, caractérisé en ce que le module électronique est aussi agencé pour : c) acquérir une distribution statistique, dite " modèle ", des deltas d'une séquence d'accès modèle, cette distribution statistique modèle comportant : - des classes de valeurs possibles pour les deltas, et associé à chacune de ces classes, - un nombre fonction du nombre d'occurrence de cette classe dans la séquence d'accès modèle, 3045183 31 d) construire une distribution statistique, dite "observée", des deltas de la séquence d'accès observée, e) identifier dans la distribution statistique observée, en la comparant avec la distribution statistique modèle, la classe la plus déficitaire, c'est-à-dire la classe pour 5 laquelle la différence NoDSM - NoDSO est maximale, où NoDSM et NoDSO sont les nombres d'occurrence de cette classe déduits, respectivement, de la distribution statistique modèle et de la distribution statistique observée, f) fournir en tant que prédiction de la donnée à précharger dans la mémoire cache avant la prochaine exécution de la même instruction de lecture, au moins une lo adresse prédite où est contenue la donnée à précharger, cette adresse prédite étant construite à partir de la classe la plus déficitaire identifiée lors de l'étape e).