# Source pour le cache coloring

## À traiter
https://docs.google.com/presentation/d/1wv208Os2xcVHPXELBoFV2KKDBl70gx_EUzJ6INzkf2A/edit#slide=id.g2bb95571c60_0_72

https://en.wikipedia.org/wiki/Cache_coloring
https://docs.freebsd.org/en/articles/vm-design/#page-coloring-optimizations // Free BSD est open source, peut-être possible de trouver le code relatif à la coloration de pages.
https://www.lynx.com/embedded-systems-learning-center/what-is-cache-coloring
https://www.quora.com/How-can-I-implement-cache-partitioning-page-coloring-technique
https://en.wikipedia.org/wiki/Graph_coloring // ? Possible concepte matheux pour implémenter le cache coloring
https://yarchive.net/comp/linux/cache_coloring.html // opinions de Linus sur le cache coloring => négatif
https://github.com/chrisyy/coloris // Sources d'un module de coloration de pages pour linux ? A voir sur l'article
https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=4c078fd1f07b9e8b65e27ecd9790e9f4fc579af1 //Article qui parle de coloris => Exemple d'implémentation 2014
https://hal.science/hal-02359983/document // Partition de cache avec coloriage pour systèmes temps réel
https://www.reddit.com/r/compsci/comments/18yz65/can_someone_explain_cache_page_coloring_to_me/
https://cs.stackexchange.com/questions/32294/what-problem-does-cache-coloring-solve
https://course.ece.cmu.edu/~ece740/f10/lib/exe/fetch.php?media=740-fall10-lecture18-cachinginmulticore.pdf
https://liuyuhang.cc/wp-content/uploads/2022/06/Make_Page_Coloring_more_Efficient_on_Slice-Based_Three-Level_Cache-2.pdf // Date de 2019 aussi

## Notes générales
Le cache colouring (aka page colouring) est un mécanisme qui vise à exploiter pleinement les caches de niveaux LLC qui contiennent des (lignes de ?) pages physiques. Le CPU ne manipule que des adesses virtuelles contigues virtuellement. Or les pages physiques que référencent ces adresses virtuelles peuvent être en concurence pour des mêmes cases de cache. Le cache colouring impacte donc le mécanisme d'affectation de pages physiques aux espaces virtuels de manière a ce qu'il n'y ai le moins de conflicts possible.

Les recherches sur le cache coloring sont difficiles car les algos recherchés sont souvent dépassés par l'évolution du materiel. Il est donc difficile de trouver un algorithm générale, pérenne et performant.

=> utilisation dans cas général n'est pas simple à mettre en place ni même utile.

=> le cache coloring serait plus indiqué pour des systèmes embarqués temps reel utilisant des processeurs plus spécifiques.

## Notes sur Coloris

re-partitioning = recoloring => Refaire la table des pages en la copiant, tres couteux
[14, 29, 35] => exemple d'application
Les bit de couleur sont compris dans les bit d'index pour l'addresse physique.
cache slices pose un pb mais lequel ?

Coloris est en 2 partie:

- Page Color Manager : Le principe de base est que chaque coeur posséde sa couleur mémoire et que les processus sont assosié à un seul coeur (avec possibiliter de migrer de maniére couteuse).
- - Cache Utilization Monitor : Il utilise le pricipe de couleur chaude (partagé par beaucoup de resource) et froide. Son but est trouver une répartition permetant de pas dépaser un seuil. Il va réattribuet les couleur au processus de maniére dynamic. En plus d'inspectant les miss, il va aussi regarder les accés totaux au cache (si faible alors miss = 0 pour dire faible utilisation).
- - Recoloring Engine: Agrandit au retrecis les couleur attribuer au processus. le retrecissement est paresseux. Pour l'expension 2 méthode
- - - Selctive Moving : Prend en compte l'associativiter du cache ou l'on parcontre la table et recolre les pages nways + 1 de chaque couleur et evitant de casser les structuer de donné.
- - - Redistribution: Regarde les pages accéder resament et on les recolorie.

- Color aware Page Allocator : Listes de Page (chaque list posséde une couleur) libre donner Manager pour les donnése et le programe. Donne une page d'une des couleur du process demander en round robin. Si il y a plus de page d'une couleur ou qu'elle existe pas, il va prendre une autre couleur pour le process. Dans le cas aucune couleur est dispo alors il va alloué des pages d'une couleur alléatoire => necessite une grande pool de base pour fonctionner. Pour les code partagé la couleur est aléatoire

## Notes sur "A WCET-aware cache coloring technique for reducing interference in real-time systems"

- Systèmes temps réels on besoin de temps d'execution déterministes pour satisfaire leur conditions d'execution.

- Les problèmes d'interférences inter-processus dans des systèmes temps réel rend difficile l'estimation d'un "pire temps d'execution" d'un processus.

- Les recherches du papier ont pour but de minimiser les interférences inter-processus en coloriant les pages. Mais cela a un coup: augmentater les interférences intra-prrocessus. Les processus ont plus de miss de conflicts (capacité?) de leur propre fait et s'executent donc plus lentement. Cependant, leur comportement en pire scénario est beaucoup plus prévisible. Cela rend plus simple la satisfaction des contraintes de temps réel.

- Formalisation d'un système de taches sporadiques t(i){Ci, Di, Ti, Pi} a répétition infinies définies comme un successions de traveaux J(i,k) avec les propriétés suivantes (pour un tache):
- pire temps d'execution (Ci)
- temps minimum etre deux arrivées successives pour la meme tache (Ti)
- deadline a respecter sous peine d'erreur critique (Di)
- nombre de pages virtuelles necessaires a l'execution de la tache (Pi)
- expérience avec
- Un unique processeur
- Le système ne contient que des taches dont Ti >= Di
- L'ordonnanceur du système donne priorité aux taches dont Di est la plus proche
- Les taches ne partagent pas de pages

- In this paper we only focus on the instruction cache
- Nombre de couleurs max : [0, (Sinstructions / Nway) − (N − 1)]
- couleurs de toutes les pages en mémoire principale : κ(i,j) = index(Pi,j)mod (Sinstructions / Nway)
- Calcul du WCET basé sur des graphs de flow de control -> on peut voir que la selection des pages physiques a un impact direct sur le WCET.
- Chaque tâche dispose d'un nombre fini de couleurs et le nombre de couleur affecté total est inférieur ou égale au nombre de couleurs max du cache. On adapt le nombre de couleur de chaque tache de manière a avoir le meilleur WCET.

## On dit quoi
- Limitation des programmes informatique: les accès mémoires => caches indispensables
- Rappel sur allocation mémoire (mémoire virtuelle, MMU et collisions) et fonctionnment des Caches
- Explication simpliste du concept
- Implématation et leurs resultats: Coloris
- Implématation et leurs resultats: WCET-aware
- Props/Cons liés à l'implémentation

- De nos jours tous les systèmes informatiques disposent de mémoire virtuelle et de plusieurs niveaux de caches. La performance des cache est critique à la performance générale du système car les échanges mémoires sont le facteur limitant des programmes informatiques. Les caches sont remplis avec des données référencées par des adresses physiques. Une autre partie critique est donc la correspondance physique / virtuelle lors de l'allocation de pages d'un processus.

https://hal.science/hal-02359983/document
## Slide 1 système temps réel
- La coloration de cache peut avoir un intéret dans les systèmes temps réel tel que l'aviation ou la santé.
- Dans ces systèmes, les tâches qui s'executent doivent satisfaire des contraites de temps prédéfines sous peine d'avarie du système.
- Il est donc très important pour les concepteurs de systèmes temps réel de pouvoir borner l'execution de certaine tâches en toutes conditions.
- En temps normal, Les caches permettent d'accélérer le temps d'execution typique des tâches
- Cependant, ils rendent difficile la determination du temps d'execution dans le pire cas (WCET).
- Ils introduisent des interférnces inter-taches.
- La mise en cache de données d'une tache peut chasser les données d'une autre en fonction des pages physiques qui leur ont été allouées. C'est un problème.
- La coloration de page peut être utilisée pour limiter voir totalement éviter les interférences inter-cache

## Slide 2 modèle d’exécution en temps réel
- Dans les systèmes temps réel, on peut modéliser l'execution de taches tel que:
- On a un ensemble de taches sporadiques qui doivent s'executer en respectant des contraintes temporelles.
- Chaque tache est un enchainement infini de travaux qui doivent être terminées avant une certaine deadline
- Toutes les tâches du système sont ordonnancées de manière préemptive avec priorité aux taches ayant un travail avec la deadline la plus proche

## Slide 3 découpage du cache et coloration de pages
- Cache d'instruction set-associatif
- On partitionne le cache
- Le nombre de couleur maximum dépend de la topologie du cache: **formule**
- On cherche donc une méthode pour allouer les bonnes pages physiques aux bonnes adresses virtuelles.
- Le but étant que les tâches partagent le moins de couleurs possible, idéalement 0.
- Avec pour hypothèse que la mémoire primaire est divisiable par la taille du cache et que la taille du cache est divisible par la taille d'une page, on peut déterminer la couleur de chaque page en mémoire primaire: **formule**

## Slide 4 WCET et Heurisitques
- deux méthodes pour calculer le WCET:
- meseures
- statique à l'aide d'un CFG
- Les meusures ne sont pas assez précises car ne peuvent pas prendre en compte toutes les possibilités.
- Statique est plus sûr
- //**explication du graph**
- Le wcet dépend donc de la configuration des pages physiques allouées au programme
- Deux parties du problème:
- A) Déterminer le nombre de couleurs à assigner à chaque tâche
- B) Comment répartir les pages sur ces couleurs

## Slide 5 Répartition des pages sur les couleurs
- Deux heuristiques:
- Répartition juste: formule
- Répartion "fédérée"
- La répartition juste répartie le plus également possible les pages sur les couleurs disponibles : **formules**
- La répartition fédérée organise les pages par rapport a leur importance pour la tâche
- Chaque page posséde un score **formule**
- le score est calculé avec
- psy indique
- Les pages sont alors réparties en fonction de leur score: **figure**
- Après répartition en utilisant l'une des heuristiques, on calcul le WCET.

## Slide 6 Attribution des couleurs aux taches
- L'attribution des couleurs aux différentes taches peut être modélisée comme les problème du sac à dos:
- Sac à dos de taille limitée (contraintes d'ordonnancement)
- Ensemble d'objets (les taches) de plusieurs catégories (configuration de couleurs avec WCET correspondant)
- Il faut choisir un et seulement un objet de chaque catégorie
- la fonction cible est le nombre de couleur utilisées (qu'il faut minimiser)

## Slide 7 résultats
ez