source: trunk/doc/rapport.tex

\documentclass [12pt, a4paper, twoside] {report}


\usepackage{lettrine}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{palatino}
\usepackage{fancyhdr}
\usepackage{float}
\usepackage{subfigure}
\usepackage{wrapfig}
\usepackage{graphicx}
\usepackage[french]{babel}
\usepackage{amsmath}   %

% correct bad hyphenation here
\hyphenation{}

\setlength{\topmargin}{0cm}
\setlength{\headheight}{1cm}
\setlength{\textheight}{23cm}
\setlength{\textwidth}{16cm}
\setlength{\oddsidemargin}{0cm}
\setlength{\evensidemargin}{0cm}
\setlength{\columnsep}{0.125in}
\setlength{\columnseprule}{0.5pt}
\setlength{\footskip}{1cm}

\sloppy
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\begin{titlepage}  
        {\begin{center} \huge \textsf {Université Pierre et Marie Curie} \end{center}}
        \vspace{0.4cm}
        {\begin{center} \huge \textsf {MastÚre de sciences et technologies} \end{center}}
        \vspace{0.4cm}
        {\begin{center} \large \textbf{Mention Informatique - Spécialité STL\\2008 -- 2009} \end{center}}
        \vspace{0.4cm}
        {\begin{center} \huge \textsf {Spécialité : APR } \end{center}}
        \vspace{0.4cm}
        {\begin{center} \Huge \textbf{Simulation d'architectures multic\oe urs pour la parallélisation et l'optimisation de programmes} \end{center}}
        \vspace{0.4cm}
        {\begin{center} \huge \textsc{Rapport de Présoutenance} \end{center}}
        \vspace{0.4cm}
        {\begin{center} \large \textsf {date exposé 2009 } \end{center}}
        \vspace{0.4cm}
        {\begin{center} \Large \textsc{Présenté Par} \end{center}}
        {\begin{center} \huge \textsc{Guillaume Bau} \end{center}}
        \vspace{0.4cm}
        {\begin{center} \Large \textsc{Encadrants} \end{center}}
        {\begin{center} \Large \textsc{Karine Heydemann} \end{center}}
        {\begin{center} \Large \textsc{Nathalie Drach} \end{center}}
        {\begin{center} \large \textsf{Laboratoire d'accueil : LIP6 - Département SystÚmes embarqués sur puce } \end{center}}
\end{titlepage}

\author{}

%\pagestyle{plain}


\newpage
\pagestyle{headings}
%\fancyhf{}
%\fancyhead[R]{\slshape \thepage}

\setcounter{page}{1}
\pagenumbering{Roman}
\tableofcontents

\newpage

\listoffigures

\newpage

\setcounter{page}{1}
\pagenumbering{arabic} 



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Définition et analyse du problÚme
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Introduction}
\section{Présentation}
Les nouvelles architectures de microprocesseurs sont de plus en plus complexes
et de plus en plus variées.  L'approche des limites physiques, notamment en
fréquence, des microprocesseurs a poussé les concepteurs a créer des
architectures multic\oe urs, afin de délivrer plus de puissance, et ce, non
seulement dans les PC, mais de plus en plus dans les systÚmes embarqués tels
que les téléphones récents, baladeurs multimédia, etc. 

Ces architectures multic\oe urs peuvent adopter des structures différentes, par
exemple, différents niveaux de cache, certains caches partagés entre les c\oe
urs\ldots  

Afin de tirer parti des performances, les compilateurs doivent
intégrer ces différences, et proposer des algorithmes d'optimisations adaptés à 
ces architectures. De même, les programmeurs pourront désirer optimiser leurs
applications pour un micro-processeur en particulier.

La simulation du \textit{CPU} permet de résoudre ce problÚme, puisqu'elle
permet un \textit{profiling} trÚs avancé, en simulant le fonctionnement de
toute l'architecture, en recueillant des statistiques d'utilisation, un
diagnostic aussi complet que le souhaite l'utilisateur.

Cependant, la simulation d'une architecture complÚte est trÚs lente, et source
de nombreuses approximations, voire d'erreurs, du fait de l'impossibilité de
simuler un processeur transistor par transistor.  En effet, les résultats
expérimentaux de simulateurs précis au cycle (\textit{cycle accurate}) montrent
que la simulation est trÚs approximative.  Les simulateurs les plus répandus,
lorsqu'ils permettent de simuler une architecture multic\oe ur, se montrent
d'autant plus lents que le nombre de c\oe urs à simuler est élevé.

Afin de palier aux défauts de ce type de simulation, on se propose de ne
simuler qu'un modÚle trÚs simplifié d'architecture, dans laquelle on se
focalise sur la hiérarchie mémoire. On peut ainsi étudier le comportement de la
mémoire pour optimiser cet aspect indépendamment des autres.

\section{État de l'art}
Les simulateurs sont des logiciels extrémement complexes et sont trÚs longs
à développer. Parmi les plus connus, SimpleScalar est assez rapide mais
est incapable, sans extension de simuler un systÚme multiprocesseur. C'est,
de plus, un logiciel monolithique et donc difficile à modifier.
Au contraire, unisim est conçu autour d'un framework trÚs ouvert, il facilite
la réutilisation de code et la modularité, et peut simuler un systÚme 
multi-processeur. Cependant, c'est un simulateur \textit{cycle accurate} qui
simule tous les aspects documentés d'une architecture, ce qui ne correspond
pas à nos attentes, et aurait requis des modifications importantes.
Enfin, Simics est réputé trÚs rapide, est capable de gérer de nombreuses
architectures y compris des architectures multic\oe ur, mais c'est un logiciel
propriétaire que nous n'avons pas à disposition.


\section{Objectifs}
Les objectifs de ce projet sont de créer un simulateur pour une architecture
multic\oe ur, reposant sur un modÚle trÚs simplifié dans lequel la hiérarchie
mémoire sera prédominante.

Le simulateur doit prendre en charge une hiérarchie de cache entiÚrement
paramétrable :
\begin{itemize}
\item on pourra définir une hiérarchie de deux, trois, \ldots \ niveaux de caches. 
\item on pourra choisir de partager les cache d'un niveau entre plusieurs c\oe urs
ou bien les séparer.
\item les latences induites par le chargement d'une donnée dans un cache seront
spécifiées manuellement, et donc la gestion électronique sous-jancente ne
sera pas simulées. 
\end{itemize}

Étant donné un programme séparé en plusieurs sous-programmes,
chacun s'exécutant sur un c\oe ur, on estimera le nombre de hits et miss
obtenus dans chacun des niveaux de cache, ainsi qu'une estimation du temps
total d'exécution du programme.


On évaluera ensuite la pertinence des informations obtenues par cette
simulation en tant que mesure approximative des performances du programme
simulé.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Proposition d'une solution de principe
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Solution de principe}
\section{Présentation}
La modélisation du cache s'effectue avec des modules SystemC. Un module
représentant le micro-processeur est chargé d'éxécuter un programme exécutable
ou plusieurs programmes exécutables.

Le modÚle simplifié ne comprendra pas de directives internes permettant le 
lancement de thread et de verrous. Il ne tiendra pas compte des dépendances
entre instructions.

Le modÚle simplifié ne tiendra compte que du cache de données; on ne prendra
donc pas compte du cache d'instruction, on n'effectuera pas de prédiction de
branchement.

On cherche à se limiter au strict minimum au niveau de la gestion des
instructions, cependant, il n'est pas envisageable de ne simuler que les
instructions \textit{load} et \textit{store} : il faut simuler le comportement
correct du programme.

Différentes stratégies pour résoudre ce problÚme seront étudiées durant
la seconde période du stage, parmi celles-ci, on peut suivre les pistes 
suivantes :
\begin{itemize}
\item une instrumentation d'un exécutable natif existant, d'une maniÚre
similaire à \textit{Valgrind}.
\item une émulation des autres instructions d'un processeur déterminé.
\item \ldots
\end{itemize}

L'implémentation sera effectuée en SystemC, tout en essayant de limiter
les fonctionnalités de SystemC qui sont les plus coûteuses en temps d'exécution

\section{Détails}
Le simulateur est décomposé en plusieurs module SystemC :
\begin{itemize}
\item un module représentant un processeur qui traite les instructions et
envoie des requêtes au cache qui lui est connecté
\item un module représentant un cache L1 qui doit être connecté au processeur
et à un autre cache ou la mémoire
\item un module représentant un cache L2 ou L3, qui doit être connecté 
a un autre cache (L1 ou autre), et à la mémoire
\end{itemize}

Chacun des caches gÚre une file d'attente de requêtes en entrée et en sortie :
la file limite le nombre de requêtes en cours de traitement dans le cache de 
niveau supérieur.

Une liste interne, la \textit{ProcessingQueue} permet de simuler le délai de
chargement d'une donnée dans le cache.

\begin{figure}[!h]
\center
\includegraphics[scale=0.4]{rapport/intern_communication.png}
\caption{Module représentant un cache L1}
\end{figure}



Un exemple de modélisation de cache pourrait être celui-ci :

\begin{figure}[!h]
\center
\includegraphics[scale=0.5]{rapport/config_sample.png}
\caption{Exemple de configuration de cache}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Identification des taches à accomplir 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Tâches à accomplir et Planning}
\section{Tâches à accomplir}

Les principales tâches à accomplir sont essentiellement l'étude précise du cadre
de simulation du processeur et une implémentation.

Les pistes envisagées sont le développement d'une instrumentation d'exécutable
d'une maniÚre similaire à valgrind et l'émulation. L'instrumentation d'exécutable
demande d'avoir à sa disposition le processeur que l'on simule, ce qui limite
légÚrement l'intérêt d'une simulation. L'autre solution est l'émulation, mais
elle requiert de se concentrer sur un jeu d'instruction particulier pour être
réalisée en un temps raisonnable.



\section{Planning}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Procedure de recette
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Procédure de recette}
\section{Validation du simulateur}
Les résultats seront partiellement validés automatiquement : une petite suite
de tests permet de valider des petits programmes afin de vérifier les données
recueillies par le simulateur, afin de les confronter à des résultats obtenus
par le calcul, par exemple :
\begin{itemize}
\item le nombre de \textit{hits} et de \textit{miss}
\item le temps d'éxecution total estimé d'un programme.
\end{itemize}
\


Plusieurs configurations possibles seront testées :
\begin{itemize}
\item les différentes associativités (mapping direct, associativité complÚte,
N-Way )
\item différents niveaux de caches, qui pourront être partagés entre plusieurs
c\oe urs ou bien indépendants.
\end{itemize}

\section{Validation des résultats}
Des comparaisons des résultats et des performances avec d'autres simulateurs 
comme unisim permettront d'une part de mesurer le gain en performance de
ce simulateur, mais aussi d'estimer la précision des mesures se focalisant sur
l'aspect mémoire, et de constater dans quelle mesure les performances
d'une application sont représentées par l'utilisation optimale ou non de
l'aspect mémoire.

\end{document}