La Fig. 1 illustre le concept de “défaut pur” de cache à partir de cinq accès mémoire différents, chacun d’entre eux coûtant au minimum trois cycles pour les accès réussis. S’il s’agit d’un défaut de cache, un nombre inconnu de cycles de pénalités est ajouté. Les accès 1, 2 et 5 sont des accès réussis tandis que les accès 3 et 4 provoquent des défauts de cache. L’accès 3 engendre trois cycles de pénalités et l’accès 4 un seul cycle de pénalité. Lorsqu’on considère les accès simultanés, seul l’accès 3 engendre deux cycles dus à des défauts purs. Bien que l’accès 4 provoque un défaut de cache sur un cycle, il n’est pas pur car il se superpose avec l’accès 5 qui est un accès réussi.

Par conséquent le taux de défauts purs de cache sur l’ensemble des cinq accès est, selon notre nouvelle définition du taux de défauts (purs) d’accès simultanés au cache, de 0,2 alors qu’il est de 0,4 selon la méthode classique sans notion d’accès concurrents. La raison pour laquelle on ignore les défauts de cache pour lesquels les cycles se superposent avec ceux des accès réussis tient au fait que ces défauts ne suspendent pas l’exécution du processeur. Ce dernier peut en effet continuer à travailler avec les données provenant des accès réussis au cache. Selon l’Eq. 2, C-AMAT comptabilise 8 cycles sur les 5 accès, soit 1,6 cycle par accès, alors que selon l’Eq. 1, AMAT compte 3 + 0,4 × 2, soit 3,8 cycles par accès. La différence entre C-AMAT et AMAT tient à la prise en compte des accès concurrents. Dans cet exemple, les accès simultanés ont permis de doubler la performance mémoire.

La Fig. 2 montre comment est structuré C-AMAT. Le HCD (Hit Concurrency Detector) comptabilise les cycles des accès réussis au cache et enregistre chacune de ces phases afin de calculer la moyenne des accès concurrents réussis. HCD indique aussi au MCD (Miss Concurrency Detector) si le cycle courant contient un accès réussi au cache ou non. MCD est une unité de contrôle qui compte le nombre total de cycles dus aux défauts purs de cache et enregistre, lui aussi, chacune de ces phases afin de calculer au final la moyenne de défauts des accès concurrents au cache, le taux de défauts purs ainsi que les pénalités afférentes. Grâce aux informations fournies par HCD, MCD est en mesure de dire si un cycle est un cycle dû à un défaut pur de cache et, a priori donc, si un défaut de cache est pur ou non. Grâce à ces informations, le taux de défauts purs et les pénalités associées peuvent être calculés. Ces métriques sont obtenues à chacun des niveaux de la hiérarchie mémoire. Ce faisant, C-AMAT peut être appliqué à chacun des niveaux de cette hiérarchie.

Il faut bien noter que la contribution de C-AMAT ne réside pas dans la mesure, qui peut être obtenue directement par APC [6]. La mesure que réalise C-AMAT ne dépend pas de ses cinq paramètres. La valeur des paramètres est calculée à partir de l’analyse des performances et des optimisations. La valeur essentielle de C-AMAT se trouve dans la formulation mathématique qui associe l’impact, en termes de performance, de la localité des accès et de leur concurrence. C-AMAT est basé sur AMAT comme cas particulier qui ne tient pas compte des accès mémoire concurrents. Il offre une méthode pour évaluer et optimiser les cinq paramètres de performance cités précédemment, et ce de manière individuelle ou combinée. Il est en quelque sorte un outil d’aide pour optimiser la conception.

Les lecteurs familiers d’AMAT se souviendront que le taux moyen de défauts de cache calculé par AMAT peut être propagé récursivement aux niveaux supérieurs de la hiérarchie mémoire. Cette récursivité est également possible avec C-AMAT. L’Eq. 3 donne la relation de récursivité entre C-AMAT₁ et C-AMAT₂ pour propager les résultats du niveau de cache L1 à celui L2. Remarquez l’introduction d’un nouveau paramètre, ɳ₁, et la contribution de C-AMAT₂ vers la valeur finale C-AMAT₁ qui est basée sur pMR₁ et pMR₂. pMR₁ x ɳ₁ représente la contribution des accès simultanés. Elle réduit finalement la latence moyenne des accès au cache L1. ɳ₁ ne possède qu’un seul paramètre, C_m, les défauts d’accès concurrents au cache. Remarquez également que nous utilisons C_M (avec un “M” majuscule) pour représenter les défauts purs d’accès concurrents au cache et C_m (avec un “m” minuscule) pour les défauts d’accès simultanés. ɳ₁ est un paramètre de mesure qui a une signification physique. Le nombre de défauts du cache L2 est C_m tandis que ceux relatifs à L1 est C_M. Nous appliquons cette même convention pAMP et AMP. De façon similaire à Eq. 3, C-AMAT peut être étendu aux niveaux supérieurs de la hiérarchie mémoire.

Eq. 3 – \(C{-}AMAT_{1} = \frac{H_{1}}{C_{H_{1}}} + pMR_{1} \times ɳ_{1} \times C{-}AMAT_{2}\)

où

\(C{-}AMAT_{1} = \frac{H_{1}}{C_{H_{1}}} + pMR_{1} \times \frac{pAMP_{1}}{C_{M_{ 1}}}\) ,

\(C{-}AMAT_{2} = \frac{H_{2}}{C_{H_{2}}} + pMR_{2} \times \frac{pAMP_{2}}{C_{M_{ 2}}}\) ,

\(ɳ_{1} = \frac{pAMP_{1}}{AMP_{1}} \times \frac{C_{m{1}}}{C_{M{1}}}\)

APC est une métrique de performance dont la valeur est l’inverse de C-AMAT [1]. La justesse et la mesure d’APC sont bien étudiées dans [6], ce qui garantit son exactitude. A première vue, APC (Access Per Cycle) semble très similaire à IPC (Instruction Per Cycle) mais en réalité les cycles utilisés dans APC sont complètement différents de ceux utilisés dans IPC. Ils sont différents à la fois dans leur définition et dans leur mesure. Dans APC, les cycles sont des cycles mémoire et non des cycles CPU comme dans IPC. Ainsi, APC peut également être désigné sous le nom de APMAC (Access Per Memory Active Cycle). En outre, APC tient compte du recouvrement mémoire pour comptabiliser les cycles des accès mémoire. Autrement dit, si deux accès ou plus se produisent simultanément, le nombre de cycles n’est augmenté que d’une seule unité. Ces deux différences entre APC et IPC sont essentielles. La distinction entre cycles CPU et cycles mémoire dissocie la mesure APC des performances du processeur. Elle permet d’appliquer APC à chacun des niveaux de la hiérarchie mémoire et conduit de fait à une meilleure compréhension de la relation entre systèmes informatiques et systèmes mémoire. Cette différence représente finalement une évolution du mode de pensée des systèmes mémoire, d’un modèle traditionnel centré sur les calculs à un modèle centré sur les données. Le recouvrement est un concept présent dans les accès aux données parallèles. C-AMAT introduit ce concept de systèmes mémoire parallèles et fournit un outil pour évaluer et concevoir de tels systèmes, matériels et logiciels.

Nous conclurons avec l’idée que C-AMAT amène à repenser la conception des systèmes de calcul et des systèmes mémoire. Simple et efficace, il se fonde sur une expression mathématique découlant d’une preuve analytique rigoureuse, qui considère à la fois la localité des données et les accès concurrents. C-AMAT introduit les accès concurrents à la mémoire dans la mesure globale de performance, et offre ainsi la possibilité de les optimiser. De ce fait, il appelle à une refonte de la conception de l’architecture des systèmes informatiques et des algorithmes pour qu’y soient intégrées les interactions entre localité des données et accès concurrents. C-AMAT devrait logiquement avoir une influence importante sur la prochaine génération d’ordinateurs et le développement des applications et algorithmes qu’ils exécuteront.

C-AMAT est un projet conjoint du Dr Dawei Wang et de l’auteur de cet article. Les réalisations de C-AMAT sont un travail commun du Dr Yuhang Liu et de l’auteur. Le Dr Yuhang Liu a par ailleurs fourni une aide précieuse à la rédaction de cet article.

Le Dr Xian-He Sun est Distinguished Professor et Chairman du Département d’informatique de l’Illinois Institute of Technology (IIT). Il est par ailleurs IEEE Fellow, Guest Faculty de la Division Informatique et Mathématiques du laboratoire Argonne et Directeur du laboratoire Scalable Computing Software à l’IIT. Il contribue activement à plus de huit revues professionnelles internationales et siège au comité de programme de nombreux ateliers et conférences internationales. Ses travaux de recherche portent actuellement sur le calcul parallèle et distribué, les systèmes mémoire et d’entrées / sorties, les systèmes logiciels pour les applications Big Data et l’évaluation de la performance et optimisations. Il est l’auteur de plus de deux cents articles de recherche en informatique et communication.