source: trunk/IPs/systemC/processor/Morpheo/Documentation/Source/Documents/article-morpheo-share_architectural_ressources_between_hardware_context/fr/root.tex @ 23

\begin{abstract}
Dans ce document nous allons étudier l'incidence du partage par les contextes matériels d'un processeur, de ces caches de niveau 1, de sa partie opérative et de sa partie exécutive. 
Il s'agit d'une étude de performance, en terme d'exécution, utilisant les benchmarks SPECINT2000.
Nous montrons que le partage de la partie exécutive n'a que peu d'incidence sur les performances, alors que le partage des caches fait perdre 10\% de performances et que le partage de la partie opérative fait tomber les performances d'un facteur de 2,7 entre un CMP de degré 4 et un SMT de même degré. 

\end{abstract}

%------------------------------------------------------------------------- 
\Section{Introduction}

De nos jours, la capacité d'intégration augmente. 
Un concepteur possède un ``tas'' de transistors toujours plus grand à sa disposition. 
L'objectif des vingts dernières années était d'avoir un processeur monolithique pouvant extraire des programmes le plus d'ILP (Instruction Level Parallelism) possible. 
Les études de David W. Wall \cite{1991_wall} montre que l'ILP moyen dans un programme est de 3-5 instructions.
Les mono-processeurs de la fin du XX ème siècles comme le MipsR10000 \cite{1996_yeager}, l'Alpha 21264 \cite{1998_kessler}, le Pentium 4 \cite{2001_hinton} ou encore l'Itanium 1 et 2 d'Intel (\cite{2000_sharangpani}, \cite{2003_mcnairy}) exploitent tous fortement l'ILP. 

Dans le même laps de temps des systèmes CMP (Chip Multi Processors) firent leur apparition. 
De telles puces peuvent exécuter plusieurs tâches simultanément. 
Ces CMP exploitent le TLP (Thread Level Parallelism). 
Dans cette catégorie nous pouvons citer le piranha de Compaq \cite{2000_barroso}, l'Hydra de Stanford \cite{2000_hammond}. 
On peut également citer le Power4 \cite{2002_tendler} ou l'Alpha 21364 \cite{2002_mukherjee} qui sont des processeurs monolithiques mais conçus pour être intégrés dans un environnement multiprocesseur. 

L'exploitation de l'ILP de manière aggressive, (prédiction de branchement, lancement désynchronisé) entraine une sous exploitation des ressources internes des processeurs. 
Une technique consiste en l'éxecution de plusieurs contextes par coeur de processeur en exploitant le TLP. 
Ceci est la technique du Multi-threading et de sa principale variante le SMT (Simultaneous multi threading).
C'est l'objet des travaux de recherches de l'équipe de Tullsen \cite{1996_tullsen}, \cite{1998_tullsen}. 
Pour un ajout minime en surface (une duplication de quelques registres d'état, ajout de multiplexeurs pour sélectionner un contexte... ), nous pouvons avoir des processeurs mono-coeur multi-thread. 
Cette technique est exploitée dans le Pentium 4 Hyper-Threading d'Intel \cite{2003_koufaty} (ajout de 5\% en surface pour un gain de performance de 30\%). 
 
Il y a deux grands axes de recherches : 
\begin{enumerate}
\item le CMP où chaque thread s'execute sur un coeur spécifique. 
 L'intégralité des ressources d'un coeur est mit à la disposition d'un thread. 
 Les ressources internes du coeur sont dédiées à un thread. 

\item le SMT où tous les threads s'éxecutent dans un unique coeur. 
 Tous les threads entrent en compétition pour l'obtention des ressources d'un coeur. 
 Les ressources internes du coeur sont partagées entre plusieurs threads
\end{enumerate}
Entre ces deux axes, il y a une multitude de variation du degré de partage des ressources entre les tâches. 
Ceci a pour conséquence l'émergence de CMP de SMT (plusieurs coeurs multi contexte). 
Le POWER 5 \cite{2004_kalla} est un bi-coeurs où chaque coeur est SMT de degré 2. 
De même pour le montecito d'Intel \cite{2005_mcnairy}. 
Alors que le Niagara de Sun intègre 8 coeurs de CMT (Corse Grain Multi Threading) de degré 4 \cite{2005_kongetira}. 

L'objectif de ce papier est d'analyser les performances d'exécution entre plusieurs partages des ressources d'un processeur. 
Pour cela, nous allons voir dans la section \ref{experimentations} les expérimentations que nous avons réalisées, ainsi que celles qui ont déjà été effectuées. 
Dans la section \ref{methodologie} nous allons montrer nos hypothèses de travail. 
Enfin une section où nous allons interpréter les résultats. 

%------------------------------------------------------------------------- 
\Section{Expérimentations}\label{experimentations}
Le SMT est une solution faible-coût pour obtenir un processeur MT (multi-thread). 
Les ressources sont intégralement partagées, dans le cas où il n'y a qu'un seul thread à exécuter, ce dernier pourra utiliser l'intégralité des ressources du processeur. 
 
Malheureusement cette solution à deux problèmes importants. 
 
Le premier est que la rapidité d'exécution d'un thread dépend des autres threads. 
Ceci est dut à la compétition entre les threads pour obtenir les ressources. 
Par exemple si tous les threads font des accès mémoires fréquents, l'unité mémoire va rapidement saturer. 
 
Le deuxième problème est la pollution des ressources partagées.
Les meilleurs exemples sont les caches et le Buffer des destinations de branchement (BTB). 
La gestion du SMT peut être gérer de manière très simple en concaténant le numéro du thread l'adresse de l'instruction ou de la donnée.
Dans ce cas, le cache peut évincer des lignes très utiles d'un thread au profit de lignes d'autres threads.
 %De plus les actions comme le prefetch ou la prédiction de branchement risque de priver des threads de lignes utiles contre une hypothétique ligne utile pour le thread bénéficiaire. 

Nous allons faire varier le degré de partage des ressources. 
Des travaux équivalents ont été réalisés. 
Dans \cite{2004_dolbeau}, ils étudient l'influence du partage des unités à latence longue (multiplication, division...), du prédicteur de branchement, ainsi que des caches Instructions et Données. 
Pour ce faire, ils ont implémentés l'architecture {\bf CASH} (CMP And SMT Hybrid) qui consiste en 4 coeurs ce partageant les ressources cités. 
Dans un autre article, \cite{2004_kumar}, il y a une étude en terme de performance d'exécution mais également en terme de surface. 
Les blocs concernés sont les unités flottantes, les caches de premiers niveaux, et enfin les ports du crossbar reliant les Caches à la mémoire.  
Ici l'équipe de Tullsen à validée leurs hypothèses sur un système à 8 coeurs. 
Le partage des ressources ce fait entre deux coeurs voisins. 

Leurs résultats ainsi que ceux que nous obtenons sont compatibles entre eux. 

Notre approche consiste à tester l'incidence du partage des caches, des Unités d'exécutions et de la partie opérative. 

Nous nommons les partages comme suit :
\begin{description}
\item[Cluster            :] Les clusters ce partage les caches de niveaux 2 et les unités d'exécutions. 
\item[Unité de lancement :] Les unités de lancement ce partage les ports des caches de niveaux 1 et les unités d'exécutions. 
\item[Contexte           :] Les contextes se partagent l'accès au décodeur, au Icache et au prédicteur de branchement. 
\end{description}

L'expérimentation ce fait avec le générateur de processeur Morpheo (acronyme de ``Multi ORganisation for a Processor HEterogeneous and Open''). 
Une vue d'ensemble de l'architecture résultante est donnée dans la figure \ref{MORPHEO_overview}. 

\begin{figure}[h] 
  \begin{center}
    \resizebox{8cm}{!}{
      \includegraphics{\dirschema/MORPHEO_overview.eps}}
    \caption{\label{MORPHEO_overview}MORPHEO - Vue d'ensemble}
  \end{center} 
\end{figure}

Notre allons analyser l'incidence du partage des ressources au niveau Cluster, UL et Contexte dans un système à 4 Threads, pouvant lancer à chaque cycle 8 instructions. 
Trois tableaux résument les caractéristiques communes de chaque instance ainsi que les paramètres spécifiques pour les configurations avec 1,2 et 4 coeurs. 
(nous définissons un coeur étant équivalent à une UL). 
Le troisième tableau résume le système mémoire. 

\begin{table}[h]
\begin{center}
\begin{tabular}{|l|c|}
  \hline
  Unité d'exécutions                           & 8              \\
  Profondeur des Stations de Réservations      & 4              \\
  Nombre de branchements spéculés              & 8              \\
  Return Address Stack                         & 16             \\
  Réseau de by-pass                            & Complet        \\
  Nombre de port de lecture                    & 12             \\
  Nombre de port d'écriture                    & 8              \\
  \hline
\end{tabular}
\end{center}
 \caption{Caractéristiques communes}
\end{table}

\begin{table}[h]
\begin{center}
\begin{tabular}{|l|ccc|}
  \hline
                                               & 1 coeur        & 2 coeurs      & 4 coeurs      \\
  \hline
  Largeur du pipeline                          & 8              & 4             & 2             \\
  Taille-Ifetch\_queue                         & 8              & 4             & 2             \\
  Taille-Issue queue                           & 32             & 16            & 8             \\
  Taille-ReOrder Buffer                        & 128            & 64            & 32            \\
  Taille-Autres files                          & 16             & 8             & 4             \\
  Largeur des fenêtres                         & 16             & 8             & 4             \\
  Branch Target Buffer                         & 256            & 128           & 64            \\
  Méta prédicteur                              & 16k            & 8k            & 4k            \\
  Banc de Registres                            & 256            & 128           & 64            \\
  \hline
\end{tabular}
\end{center}
    \caption{Caractéristiques spécifiques}
\end{table}

\begin{table}[h]

\begin{center}
\begin{tabular}{|l|cc|}
  \hline
                             & L1          & L2             \\
                             & I/D séparé  & unifié         \\
        \hline
        Taille               & 8 ko \footnote{divisé par le nombre de cluster}  & 2 Mo           \\
        Nombre de lignes     & 128  \footnote{divisé par le nombre de cluster}  & 16k            \\
        Nombre de mots/ligne & 16          & 32             \\
        Associativité        & 4 voies     & 4 voies        \\
        Latence - Hit        & 2 cycles    & 6 cycles       \\
        Pénalités - Miss     & 4 cycles    & 100 cycles     \\
  \hline
\end{tabular}
\end{center}
 \caption{Caractéristiques du système mémoire}
\end{table}

%(Le nombre de lignes du premier niveau de cache est divisé par le nombre de cluster). 


%------------------------------------------------------------------------- 
\Section{Méthodologie}\label{methodologie}

\subSection{Charge de travails}

Dans un premier temps, nous avons sélectionné 6 benchmarks parmi les SPECINT2000 (164.gzip, 175.vpr, 181.mcf, 255.vortex, 256.bzip2, 300.twolf). 
 %Nous ne les avons pas tout sélectionnés afin de ne pas avoir trop de simulations à effectuer et car tous les benchmarks ne fonctionnes pas (problème de compatibilité avec gcc 4 et avec notre modèle). 

Chaque archtecture est soumise à une charge de travails composée de 15 simulations (Le nombre de simulations est décrit par la combinaison $C_{nb\_benchmarks}^{nb\_threads}$). 

Pour les librairies standard (libc et libm) ainsi que les fonctions bas niveaux (read, write, open, close ...) qu'un système d'exploitation se doit d'offrir, nous utilisons la librairie {\it Newlib}. 

\subSection{Simulation}

Pour les simulations, nous avons pris 14 instances de notre modèle. 
Elles sont déterminées par le nombre de cluster (A), le nombre d'ULs de chaque cluster (B) et le nombre de contexte de chaque UL (C). 
De plus chaque UL n'a accès qu'a un sous-ensemble distinct d'ALUs. 
Ce nombre définit la taille du groupe (D). 
Nous nommons une instance X$E$\_$A$\_$B$\_$C$-$D$ avec E=A*B*C. 

%Le tableau suivant récapitules toutes les instances que nous avons sélectionnées. 

%
%\begin{table}[h]
%\begin{center}
%\begin{tabular}{ccccc}
%Nom          & Cluster & UL & Contexte & Taille groupe d'ALUs\\
%X4-1\_1\_4-8 & 1       & 1  & 4        & 8\\
%X4-1\_2\_2-8 & 1       & 2  & 2        & 8\\
%X4-1\_2\_2-4 & 1       & 2  & 2        & 4\\
%X4-1\_4\_1-8 & 1       & 4  & 1        & 8\\
%X4-1\_4\_1-2 & 1       & 4  & 1        & 2\\
%X4-2\_1\_2-8 & 2       & 1  & 2        & 8\\
%X4-2\_1\_2-4 & 2       & 1  & 2        & 4\\
%X4-2\_2\_1-8 & 2       & 2  & 1        & 8\\
%X4-2\_2\_1-4 & 2       & 2  & 1        & 4\\
%X4-2\_2\_1-2 & 2       & 2  & 1        & 2\\
%X4-4\_1\_1-8 & 4       & 1  & 1        & 8\\
%X4-4\_1\_1-4 & 4       & 1  & 1        & 4\\
%X4-4\_1\_1-2 & 4       & 1  & 1        & 2\\
%\end{tabular}
%\end{center}
% \caption{Instances sélectionnées}
%\end{table}

Chaque simulation ce fait sur 110 millions de cycles. 
Les 10 premiers millions sont ignorés afin de chauffer les caches et les unités de prédictions. 
Pour chaque instance, nous prenons le nombre d'instructions exécutées des 15 simulations. 
Ce résultat est comparé à la moyenne des 6 benchmarks exécutés dans la version Single Thread du processeur (exécution séquentielle des 6 benchmarks avec la même instance). 

Nous pouvons remarquer que les instances ne vont pas être comparées avec une instance de référence, mais seront comparées avec l'accéllération de la version MT par rapport à la version ST. 
Ceci à la bonne propriété d'avoir une borne maximale à l'accélération qui est le nombre de thread (ici 4). 

%------------------------------------------------------------------------- 
\Section{Résultat}\label{resultat}

La simulation nous fournit le graphe \ref{simulation_all}

\begin{figure}[h] 
  \begin{center}
    \resizebox{8cm}{!}{
      \includegraphics{\dirschema/simulation_all}}
    \label{simulation_all}
  \end{center} 
\end{figure}

Première constatation simple : plus on dédit les ressources, plus on approche de l'accélération maximale. 
La version du X4\_4\_1\_1-2 ne partage que les caches de niveau L2, et est donc une version CMP pure, atteint une accélération de 3,92. 
Alors que la version X4-1\_1\_4-8 qui est un SMT pur à une accélération de 1,46. 
 
En terme de performance, il y a une accélération de 2,7 entre la version CMP et la version SMT. 
Attention dans l'interprétation des résultats, car ici nous ne comparons qu'en terme de performances l'incidence du partage des ressources matérielles. 
Pour que l'étude soit complète, nous devons aussi ajouter l'augmentation de la surface entre la version MT et la version ST. 
Ensuite il faudrait comparer le rapport entre l'augmentation de la performance sur le coût matériel. 
Nous pouvons néanmoins faire une étude abstraite du coût en surface. 
Le rapport de surface entre la version MT et ST de l'instance X4-4\_1\_1-2 est de 4. 
Ceci donne un rapport performance/surface pour la version CMP de degré 4 de 0,98. 
Pour le SMT, nous réutilisons les estimations d'Intel pour le Pentium 4 HT \cite{2003_koufaty}.
Trois contextes de plus nous amène à 15\% de surface en plus. 
Ce qui donne un rapport de surface entre la version MT et ST de l'instance X4\_1\_1\_4-8 de 1,15. 
Dans ce cas, le rapport performance/surface pour la version SMT de degré 4 nous donne 1,27. 
Ce qui donne l'avantage à une implémentation SMT. 

Pour le partage du cache, nous analyserons les 3 instances suivantes :
\begin{itemize}
\item X4-4\_1\_1-2 avec 4 Icaches et Dcaches L1 de 2k chacun et accessible par un seul thread . L'accélération de 3,92. 
\item X4-2\_2\_1-2 avec 2 Icaches et Dcaches L1 de 4k chacun et accessible par deux    threads. L'accélération de 3,63. 
\item X4-1\_4\_1-2 avec 1 Icache  et Dcache  L1 de 8k chacun et accessible par quatre  threads. L'accélération de 3,27. 
\end{itemize}

Le partage du cache induit des conflits d'accès au port. 
Dans le premier cas, il y a 4 ports d'accès au Icache de largeur de deux instructions. 
Alors que dans le troisième cas, il n'y a qu'un port de largeur de 8 instructions. 
Les paquets de 8 instructions permettent de mieux exploiter l'ILP mais moins le TLP : chaque contexte accède au cache tous les 4 cycles. 
Nous notons aussi que le partage du cache entraîne un effet de bord qui est le pourrissement du contenu du cache par les autres threads. 
Ainsi qu'un allongement du temps de réponses des échecs d'accès au cache du au plus grand nombre de miss et à la plus grande longueur des lignes. 
Le cache, optimisé pour tirer parti de la localité spatiale et temporelle d'un flot d'instructions ou de données se retrouve maintenant confrontés à plusieurs flots. 

Pour le partage de la partie exécutive, nous pouvons observer les instances suivantes :
\begin{itemize}
\item X4-2\_2\_1-2 où il y a 4 groupes de 2 ALUs et chacune est accessible par 1 Threads. L'accélération est de 3,63. 
\item X4-2\_2\_1-4 où il y a 2 groupes de 4 ALUs et chacune est accessible par 2 Threads. L'accélération est de 3,41. 
\item X4-2\_2\_1-8 où il y a 1 groupe  de 8 ALUs et         est accessible par 4 Threads. L'accélération est de 3,38. 
\end{itemize}

Le partage des unités d'exécutions n'influe que légèrement sur les performances. 
Les ressources sont mieux utilisées. 
Or il y a une augmentation de la sensibilité du aux erreurs de routages (envoie vers une ALUs surchargés alors que d'autres ALUs sont en famine). 
Ceci est également du à notre politique de routage actuel qui est un round robin classique. 
Notons que dans le cas où il y aurait plus d'un contexte par coeur, le partage des unités d'exécutions est favorable. 
Par exemple X4-1\_2\_2-8 et X4-1\_2\_2-4 qui ont une accélération de 2,37 alors que les instances X4-2\_1\_2-8 et X4-2\_1\_2-4 ont respectivement une accélération de 2,51 et 2,4. 
Ceci est la conséquece d'une meilleur exploitation du TLP. 
La fenêtre de lancement est mieux utilisé et le réseau de routage à plus d'instructions à sa disposition. 

% Il y a aussi une hétérogénéité des instructions longues. 

Pour le partage opérative, voyons les instances suivantes :
\begin{itemize}
\item X4-1\_1\_4-8, 1 cluster  possédant chacun 1 UL  avec 4 contextes chacun. L'accélération est de 1,46. 
\item X4-1\_2\_2-8, 1 cluster  possédant chacun 2 ULs avec 2 contextes chacun. L'accélération est de 2,37. 
\item X4-1\_4\_1-8, 1 cluster  possédant chacun 4 ULs avec 1 contexte  chacun. L'accélération est de 2,94. 
\item X4-2\_1\_2-8, 2 clusters possédant chacun 1 UL  avec 2 contextes chacun. L'accélération est de 2,51. 
\item X4-2\_2\_1-8, 2 clusters possédant chacun 2 ULs avec 1 contexte  chacun. L'accélération est de 3,38. 
\item X4-4\_1\_1-8, 4 clusters possédant chacun 1 UL  avec 1 contexte  chacun. L'accélération est de 3,94. 
\end{itemize}

Le partage de la partie opérative donne des résultats très disparates et demande une analyse plus poussée des résultats. 
Nous pouvons néanmoins dire qu'il y a une augmentation de la sensibilité des instructions de synchronisation et d'accès aux registres spéciaux (nous imposons qu'avant d'accèder au registre spéciaux, le pipeline doit être vide). 
Il y a également une augmentation des miss de spéculations du au partage du prédicteur de branchement. 
Ceci implique qu'il y a une augmentation des instructions inutiles dans le pipeline. 
Elles représentent 6,12\% des instructions dans X4-1\_1\_4-8, alors qu'elles ne représentent que 2,17\% dans l'instance X4-4\_1\_1-8. 
Ceci est aussi du à la largeur du pipeline et donc à la sous exploitation de L'ILP. 
Lors du décodage, nous choisissons de manière round robin la fetch queue contenant un paquet. 
Dans l'instance X4-4\_1\_1-8, 4 décodeurs décodent chacun en moyenne 1,63 instructions sur des paquets de 2 instructions (soit un total de 6,52 instructions), alors que dans l'instance X4-1\_1\_4-8, 1 décodeur prend un paquet de 8 instructions et décode en moyenne 3,7 instructions.
La cause venant à des paquets d'instructions devant être alignés et à la présence de branchements. 

%------------------------------------------------------------------------- 
\Section{Conclusion}

Cette étude à démontrer un fait déjà acquis, que l'accélération entre la version MT et la version ST d'un processeur diminue avec l'augmentation du partage des ressources. 
Notre modèle de processeur étant encore en cours de développement, nous nous destinons à fournir un modèle VHDL synthétisable. 
Ainsi la prochaine étude portera sur le coût surfacique du partage des ressources matérielles et ainsi déterminer quel degré de partage apporte le meilleur rapport performance/surface. 

\bibliography{\dircommon/bibliographie}