\section{Introduction}

\frame
    {
      \frametitle{Introduction}

      Chip MultiProcessors (CMP) et le Simultaneous Multi-Threading (SMT) sont 2 approches opposée qui résolves le même problème : éxècuter sur un même chip plusieurs threads.

      \begin{description}
      \item[CMP :] Chaque thread dispose de l'ensemble des ressources d'un core\\(Hydra, Piranha, Opteron)
      \item[SMT :] Chaque thread partage les ressources d'un core avec toutes les autres\\(MARS-M, 21464, Pentium4 HyperThreading)
      \item[CMP de SMT : ] il s'agit de plusieurs core de processeurs où chaque core est multi-threadé\\(Niagara, Power5, Montecito)
      \end{description}
    }

\frame
    {
      \frametitle{Approche grain fin}

      Entre le tout partagé et le tout dédié, nous pouvons faire varier dégré de partage de certaines ressources.

      Ces objectif sont :
      \begin{itemize}
      \item Economiser de la surface%(Pour une même structure on compare sa duplication avec le contrôle nécessaire pour permettre son partage)
      \item Augmenter leur taux d'utilisation en profitant du Thread Level Parallelism
      \item Avoir le maximum de ressource disponible en éxècution ST (Single Thread), tout en minimisant la dégradation des performances en éxècution MT (Multi Thread)
      \end{itemize}
    }

\frame
    {
      \frametitle{Travaux liés}

      \begin{description}
      \item[CASH : Revisiting hardware sharing in single-chip parallel processor]~\\2004 - Dolbeau et Seznec\\Partage entre les threads des unités à latence longue (multiplication, division ...), Prédicteur de branchement, Icache et Dcache.
      \item[Conjoined-core Chip Multiprocessing]~\\2004 - Kumar, Jouppi et Tullsen\\Partage des unités flottantes, ports du crossbar (Cache à la mémoire), Icache et Dcache.
      \end{description}
    }

\section{Expérimentation}
\frame
    {
      \frametitle{Expérimentation}
      Nous allons déterminer l'incidence du partage des ressources suivantes :

      \begin{itemize}
	\item I/Dcache
	\item Front et Back end
	\item Unités d'executions
      \end{itemize}
    }

\subsection{Charge de travails}
\frame
    {
      \frametitle{Charge de travails}

      \begin{itemize}
	\item Sélection des benchmarks parmit les SPECINT2000 (164.gzip, 175.vpr, 181.mcf, 255.vortex, 256.bzip2, 300.twolf)
	\item Le nombre de software soumit au architecture est décrite par la combinaison $C_{\text{nb\_benchmarks}}^{\text{nb\_threads}}$
	  Une charge de travail est donc composée de 4 benchmarks qui vont être éxecuter par l'un des 4 contextes disponibles.
        \item Utilisation de {\it Newlib} pour d'avoir les librairies standard (libc, libm et fonction de bas niveau (read, write, open, close ...))
      \end{itemize}
    }

\subsection{Architecture de référence}
\frame
    {
      \frametitle{Architecture de référence - Core}

      \begin{tabular}{l|c}
	                                             & Commun		\\
	\hline
	\hline
	nb\_ue                                       & 8                \\
	\hline
	taille - select\_queue                       & 4		\\
	taille - reservation\_station                & 4		\\
	taille - execute\_queue                      & 4		\\
	\hline
	Nombre de branchements spéculé               & 8 		\\
	Return Address Stack                         & 16		\\
	\hline
	Réseau de bypass                             & Complet          \\
	\hline
	nb\_data\_access                             & 4*		\\ 
	\hline
	nb\_gpr\_reader                              & 12		\\
	nb\_gpr\_writer                              & 8		\\
	nb\_memory\_write                            & 3		\\
	nb\_execute\_write                           & 6		\\
	nb\_spr\_reader                              & 2		\\
	nb\_spr\_writer                              & 2		\\
      \end{tabular}
      }

\frame
    {
      \begin{tabular}{l|ccc}
	                                             & 1 Core           & 2 Cores       & 4 Cores       \\
	\hline
	\hline
	largeur                                      & 8 		& 4 		& 2 		\\
	largeur des fenêtres                         & 16		& 8 		& 4 		\\
	\hline
	taille - ifetch\_queue                       & 8 		& 4 		& 2 		\\
	taille - decod\_queue                        & 16		& 8 		& 4  		\\
	taille - rename\_queue                       & 32		& 16 		& 8 		\\
	taille - Re Order Buffer                     & 128		& 64 		& 32  		\\
	\hline
	Branch Target Buffer                         & 256	        & 128 	        & 64 	        \\
	nb compteur 2bits (predicteur meta)          & 128              & 64            & 32            \\
	nb compteur 2bits (predicteur global)        & 1K		& 512		& 256		\\
	nb compteur 2bits (predicteur local)         & 16k		& 8k		& 4k		\\
	\hline
	nb\_branch\_complete                         & 4		& 2		& 1		\\
	nb\_memory\_complete                         & 4		& 2		& 1		\\
	\hline
	nb\_gpr\_phy                                 & 128+128         	& 64+64       	& 32+32      	\\
	nb\_gpr\_free                                & 8		& 4		& 2		\\
	nb\_spr\_phy                                 & 64		& 32		& 64		\\
	nb\_spr\_free                                & 8                & 4             & 2             \\   
      \end{tabular}
    }

\frame
    {
      \frametitle{Architecture de référence - Système mémoire}

      \begin{tabular}{l|ll}
	                     & L1          & L2             \\
	                     & I/D séparé  & unifié         \\
	\hline
	Taille               & 8 ko        & 2 Mo           \\
	Nombre de lignes     & 128*        & 16k            \\
	Nombre de mots/ligne & 16          & 32             \\
	Associatif           & 4 voies     & 4 voies        \\
	Latence - Hit        & 2 cycles    & 6 cycles       \\
	Pénalités - Miss     & 4 cycles    & 100 cycles     \\
      \end{tabular}

      \vspace{\stretch{1}}

      Les caches IL1 et DL1 sont dupliqués NB\_CLUSTER fois, de plus chacun ont leur nombre de lignes divisé par NB\_CLUSTER. De même pour les ports du Dcache (nb\_data\_access).
    }

\frame
    {
      \frametitle{Méthodologie}

      Pour chaque instance
      \begin{itemize}
      \item On réalise autant de simulations qu'il y a de charge de travail (soit 15).
      \item Une execution se fait en 11 millions de cycles dans lequel 1 millions ne sera pas prit en compte
      \item Nous prenons le temps moyen sur ces 15 simulations et on le compare à la moyenne de ces 6 benchmarks exécuter dans la version ST du processeur
      \item La comparaison donne le speedup de la version MT par rapport à la version ST
      \end{itemize}
    }

\section{Résultat}

\frame
    {
      \frametitle{Résultat}

	\begin{center}
	  \printgraph{simulation_all}{0.8}
	\end{center}

    }

\frame
    {
      \begin{minipage}{0.45\textwidth}
	\begin{center}
	  \printgraph{simulation_cachel1}{0.8}
	\end{center}
      \end{minipage}
      \begin{minipage}{0.45\textwidth}
	Partage du cache induit :
	\begin{itemize}
	  \item un conflit d'accès au port
	  \item un pourrissement des données par les autre contextes
	  \item 
	\end{itemize}
      \end{minipage}
    }

\frame
    {
      \begin{minipage}{0.45\textwidth}
	\begin{center}
	  \printgraph{simulation_operative}{0.8}
	\end{center}
      \end{minipage}
      \begin{minipage}{0.45\textwidth}
	Partage de la partie opérative induit 
	\begin{itemize}
	  \item Une augmentation de l'influence des instructions mal prédite
	  \item Une augmentation de la sensiblité au évenement peu courant (synchronisation, ...)
	\end{itemize}
      \end{minipage}
    }

\frame
    {
      \begin{minipage}{0.45\textwidth}
	\begin{center}
	  \printgraph{simulation_ue}{0.8}
	\end{center}
      \end{minipage}
      \begin{minipage}{0.45\textwidth}
	Partage des unités d'exécutions
	\begin{itemize}
	  \item Augmente leur taux d'utilisations
	  \item Augmente la sensiblité dut au erreur de routage (envoye vers une unité surchargé alors que d'autre sont en famine d'instructions)
	\end{itemize}
      \end{minipage}
    }

\section{Réalisation VHDL}

\frame
    {
      \frametitle{Réalisation VHDL}
      
      Les modèles vont être générés par des méthodes du modeles SystemC afin d'obtenir du VHDL classique
    }

\subsection{Regroupement d'instruction}
\frame
    {
      \frametitle{Regroupement d'instruction}

      Les processeurs à contrôle dynamique (superscalaire classique) ou à contrôle statique (VLIW) résolvent différemment le problème du lancement multiple d'instructions. 

      L'avantage principal du VLIW étant sa simplicité de ses unités de contrôles : les instructions sont dans des slots précaractérisés.
    }

\frame
    {
      \frametitle{Nouvel étage : {\it Group}}

      \begin{itemize}
      \item Entrée : A paquets contenant N éléments
      \item Sortie : B paquets contenant M éléments
      \item 1 élément soit un paquet d'éléments soit une instruction
      \item Algorithme de paquétisation libre
      \item Simplification : M est un multiple de N paquets
      \end{itemize}
    }
    
\frame
    {
      \frametitle{Etage {\it Group1}}

      Situé après l'étage de décodage
      
      \begin{itemize}
      \item Les paquets sont formée d'instructions consécutive (car non encore inséré dans le ReOrder Buffer)
      \item Un paquet contient des instructions indépendants
      \item Les paquets suivent des règles de Types (Suivant les routages possibles et des types des unités d'éxecutions)
      \end{itemize}
    }

\frame
    {
      \begin{itemize}
      \item + Simplification de la logique de gestion des dépendances RAW et WAW proche (comparaison sur les numéros de registres logiques)
      \item + Une potentiel simplification du RAT si l'algorithme prends en compte de définir un seuil maximum du nombre de lecture/écriture
      \item + ReOrder Buffer simplifié, les requêtes d'insertion et de retirement sont sur des paquets
      \item - Insertion de Nop
      \item - Paquetisation dans l'ordre du programme (Peu ou pas de liberté dans l'algo de paquétisations)
      \end{itemize}
    }

\frame
    {
      \frametitle{Etage {\it Group2}}

      Situé après l'insertion dans le ReOrder Buffer
      
      \begin{itemize}
      \item + L'algorhtme de paquétisations à de plus grand degré de liberté (Car peut prendre les paquets dans le désordre)
      \item + Diminution du contrôle pour les étages de sélection
      \item - Encore plus de Nop inséré
      \item - Performance de la paquetisation lié au nombre d'instruction en attente dans la rename\_queue et à la fenêtre d'instruction
      \end{itemize}
    }

\frame
    {
      \printgraph{MORPHEO_paquetisation}{0.5}
    }

\frame
    {
      \frametitle{Incidence}

      \begin{enumerate}
      \item L'accès au banc de registres en lecture se fait sur un paquet entier? Si une des instructions n'a pas ses opérandes?
      \item L'écriture dans le banc de registres se fait sur un paquet entier?
      \item Plusieurs niveaux de dispatch, clusterisation implicite des unités fonctionnelles
      \item Attendre la fin d'un paquet de niveau 2, alors que l'étage Commit n'a besoin que de paquet de niveau 1?
      \end{enumerate}
    }


\subsection{Partage des ensembles associatifs}
\frame
    {
      \frametitle{Partage des ensembles associatifs}

      Soit une structure associative par ensemble (par exemple le cache ou la Branch Target Buffer)

      Posons :
      \begin{itemize}
      \item E le nombre d'entité accédant à cette structure
      \item P le nombre de port nécessaire pour chaque entité (on posera P identique pour chaque E)
      \item N le degré d'associativité de la structure
      \end{itemize}
    }

\frame
    {
      \frametitle{Structure complémentement partagée}

      La structure est ici entièrement partagé entre toutes les entités.

      \printgraph{MORPHEO_structure_associative_full_share}{0.8}

      \begin{center}
	$P_{total1} = E*N*P$
      \end{center}
    }

\frame
    {
      \frametitle{Structure partiellement partagée}

      Nous allons maintenant décomposer la structure en deux parties : 
      \begin{enumerate}
	\item une première qui est accessible par toutes les entités et sera associative de degré M
	\item la seconde est accessible par X sous-ensemble d'entité. Chaque groupe sont disjoint 2 à 2 et contient E' élément (donc $X=\frac{E}{E'}$). Dans chaque groupe il y a une structure associative de degré K
	\item Pour simplifier : $N=M+X*K$ avec E' et K et constant pour chaque groupe
      \end{enumerate}
    }

\frame
    {
      \printgraph{MORPHEO_structure_associative_semi_share}{0.8}
      \begin{center}
	$P_{total2} = E*(M+K)*P$
      \end{center}
    }

\frame
    {
      \frametitle{Gain}
      \begin{center}
	$P_{total1} - P_{total2} = E*(\frac{E}{E'}-1)*K*P$
      \end{center}

      Soit dans les deux exemples précédents :

      \begin{center}
      \begin{tabular}{l|cc}
	      & Full shared  & Semi shared       \\
	\hline				         
	N     & 8            & $M+X*K = 8$       \\
	M     & -            & 4                 \\
	K     & -            & 2                 \\
	E     & 6            & 6                 \\
	E'    & -            & 3                 \\
	\hline
	Total & $E*N*P$      & $E*(M+K)*P$       \\
	      & $48*P$       & $36*P$            \\
	\hline
	Gain  & \multicolumn{2}{c}{$E*(\frac{E}{E'}-1)*K*P$}\\
	      & \multicolumn{2}{c}{$12*P$}                  \\
      \end{tabular}
      \end{center}
    }

\frame
    {
      \frametitle{Incidence}

      \begin{itemize}
	\item + Gain en nombre de port
	\item + Moins de pourrisement des structures dut au partage des ressources
	\item - Perte de performance en execution ST, et potentiellement en execution MT
      \end{itemize}
    }


\subsection{Clusterisation des Unités d'éxecution - Cache de banc de registres}
\frame
    {
      \begin{minipage}{0.55\textwidth}
      \frametitle{Partie exécutive \dots}
      \printgraph{MORPHEO_Partie_executive-schema_de_principe}{0.65}
      \end{minipage}
      \begin{minipage}{0.40\textwidth}
	Posons : 
	\begin{itemize}
	  \item $N = \sum_{i=1}^{k} n_{i}$
	  \item $M = \sum_{i=1}^{k} m_{i}$
	  \item W : Nb reg dest
	  \item R : Nb reg src
	  \item D : Profondeur SR
	\end{itemize}
      \end{minipage}
    }

\frame
    {
      \frametitle{\dots ~ avec un réseaux de bypass complet}

      \begin{center}
	\printgraph{MORPHEO_Partie_executive-bypass_complet}{0.6}
      \end{center}
    }

\frame
    {
      \frametitle{\dots ~ avec clusterisation}

      \begin{minipage}{0.48\textwidth}
	\begin{center}
	  \printgraph{MORPHEO_Partie_executive-cluster}{0.6}
	\end{center}
      \end{minipage}
      \begin{minipage}{0.48\textwidth}
	En posant : 

	\begin{itemize}
	  \item V  : le nombre de voisin
	  \item M' : le nombre de résultat circulant entre les clusters
	\end{itemize}
      \end{minipage}
    }

\frame
    {
      \frametitle{\dots ~ avec cache de banc de registres}

      \begin{center}
	\begin{minipage}{0.48\textwidth}
	  \printgraph{MORPHEO_Partie_executive-cluster_avec_cache1}{0.6}
	\end{minipage}
	\begin{minipage}{0.48\textwidth}
	  \printgraph{MORPHEO_Partie_executive-cluster_avec_cache2}{0.6}
	\end{minipage}
      \end{center}
    }

%\frame
%    {
%      \frametitle{Comparaison}
%
%      Posons S le nombre de registres physiques.
%
%      Avec :
%      \begin{center}
%	\begin{tabular}{lc}
%	  sff2 & 34 transistors\\
%	  nmx2 & 12 transistors\\
%	\end{tabular}
%      \end{center}
%
%      Avec : 
%      \begin{itemize}
%	\item R = 2
%	\item W = 1
%	\item $\forall i,j \in [1:k[ ~ n_{i}=n_{j}$, avec M = 12
%	\item $\forall i,j \in [1:k[ ~ m_{i}=m_{j}$, avec N = 8
%	%\item $\forall i   \in [1:k[ ~ D_{i}=D$
%      \end{itemize}
%	
%      Taille du Banc de registres : $S * Size_{sff2} + ((W_{RF}-1)*S + R_{RF}*(S-1)) * Size_{nmx2}$
%
%
%     }

\frame
    {      
      \frametitle{Comparaison}

      \begin{center}
	\begin{tabular}{l|c}
	              & nb bypass       \\
	  \hline
	  Complete    & $(W*M)*(R*D*N)$ \\
	  Clusterisé  & $\sum_{i=1}^{k} ((W*m_{i} + V*B) * R*D*m_{i})$\\
	  Cache 1     & $\sum_{i=1}^{k} (W*m_{i} * R*D*m_{i})$\\
	  Cache 2     & $0$\\
	\end{tabular}

	\begin{tabular}{l|c}
	              & Banc de registres \\
	  \hline
	  Complete    & $(W*M)$ port d'écriture, $(R*N)$ de lecture\\
	  Clusterisé  & Bonne cible pour le multi banc      \\
	  Cache 1     & 1 port de lecture, 1 port d'écriture\\
	  Cache 2     & 1 port de lecture, 1 port d'écriture\\
	\end{tabular}

      \end{center}


    }


\section{Planning}
\frame
    {
      \frametitle{Tâche à réaliser}

      \begin{enumerate}
      \item Réecriture complete du code SystemC 
	\begin{itemize}
	\item Compatibilité avec SystemCass
	\item Optimisation du code et des algorithmes
	\item Mise en forme pour l'exportation du projet
	\item Définition d'un format pour la configuration
	\item Définition d'un format pour les statistiques
	\end{itemize}
      \item Ecriture systématique de la documentation pour chaque composant
	\begin{itemize}
	\item Structure interne
	\item Incidence des paramètres sur la structure (Surface et Temps d'execution)
	\item Choix architecturaux pour le passage au VHDL
	\end{itemize}
      \item Ecriture des modèles VHDL et synthèse sur FPGA
      \end{enumerate}
    }

\frame
    {
      \frametitle{Tâche déléguée}

      \begin{enumerate}
      \item Ecriture d'un cache de donnée en SystemC/VHDL
      \item Ecriture d'un cache d'instruction en VHDL
      \item Automatisation du processus d'optimisation de la configuration en fonction des statistiques et de contraintes
      \item Synthèse des modèles VHDL avec Coriolis
      \end{enumerate}
    }