Changes between Initial Version and Version 1 of 2011CaoTme9

Timestamp:

May 6, 2011, 12:21:41 AM (14 years ago)

Author:

jpc

Comment:

--

2011CaoTme9

@@ +1 @@
+{{{
+#!html
+<h1>TME 7 : Simulation logico-temporelle</h1>
+}}}
+[[PageOutline]]
+
+= Objectif =
+
+On  souhaite réaliser  dans  ce TME  un  petit simulateur  logico-temporel, permettant  de
+simuler un réseau  Booléen temporisé, où les expressions  Booléennes sont représentées par
+des arbres EBM (voir TME3).
+
+Les  simulateurs  à événements  discrets  permettent  de  simuler des  systèmes  matériels
+constitués d'un  ensemble de  composants matériels interconnectés  par des  signaux.  Dans
+notre cas, les  signaux véhiculent fondamentatement deux tensions  VSS et VDD représentant
+respectivement les  valeurs Booléennes  0 et 1,  mais le  simulateur doit traiter  plus de
+valeurs pour  gérer les cas  spéciaux comme les  signaux en haute impédance,  les conflits
+électriques, ou  les valeurs indéfinies.   A titre indicatif,  le VHDL standard  utilise 9
+valeurs pour  les signaux.  Pour  simplifier, nous nous  limiterons dans ce TME  aux trois
+valeurs logiques 0, 1, et U (Undefined).
+
+Dans le cas général, chaque composant est modélisé par un processus, et tous les processus
+s'exécutent en parallèle.   Chaque processus utilise les valeurs  de ses signaux d'entrées
+pour calculer les valeurs  de ses signaux de sortie.  Un signal  possède un seul émetteur,
+mais  peut  avoir  plusieurs  destinataires.    On  définit,  pour  chaque  processus,  un
+sous-ensemble  des  signaux  d'entrée, appelé  liste  de  sensibilité  du processus  :  un
+changement de valeur sur un signal appartenant à la liste de sensibilité peut entraîner un
+changement de  valeur sur un signal  de sortie du  processus. Un processus doit  donc être
+évalué à chaque fois que l'un des signaux de la liste de sensibilité change de valeur. Par
+exemple,  la liste  de sensibilité  d'un processus  représentant un  automate de  Moore ne
+comporte qu'un seul signal, qui est le signal d'horloge.
+
+On  s'intéresse  dans  ce TME  au  cas  particulier  des  réseaux Booléens:  un  processus
+correspond à une expression Booléenne multi-niveaux. Dans ce cas particulier, un processus
+possède donc un  seul signal de sortie,  et la liste de sensibilité  du processus contient
+tous les  signaux d'entrée. Cette liste de  sensibilité est tout simplement  le support de
+l'EBM, tel que  vu au TME3. Un réseau  Booléen peut être représenté par  un graphe biparti
+orienté comportant  deux types  de noeuds: des  '''processus''' et des  '''signaux'''. Les
+noeuds à la périphérie du réseau sont toujours des signaux.
+
+En  d'autres termes,  un processus  a toujours  au moins  un signal  entrant et  un signal
+sortant.  Les  signaux qui n'ont pas d'arc  entrant sont les entrées  primaires du réseau,
+les signaux qui n'ont pas d'arc sortant  sont les sorties primaires du réseau.  Les autres
+signaux sont appelés signaux internes.
+
+[[Image(reseau_booleen.png, nolink)]]
+
+On  appelle événement  le  changement  de valeur  d'un  signal à  un  certain instant.  Un
+événement est donc défini par un triplet (signal, date, valeur).
+
+Simuler le  fonctionnement d'un  circuit consiste  donc à calculer  pour chaque  signal la
+succession des  événements, appelée forme d'onde.   L'ensemble des formes  d'ondes de tous
+les signaux constitue un chronogramme.
+
+La simulation suppose que l'on possède  une fonction d'évaluation qui calcule la valeur du
+signal de sortie  du processus en fonction  de la valeur des signaux  d'entrée. Dans notre
+cas, nous utiliserons  la méthode {{{Ebm::eval()}}} qui gère les  trois valeurs de signaux
+(0,1,U).
+
+Créez un  répertoire de travail  TME5, et  copiez dans ce  répertoire les fichiers  qui se
+trouvent  dans {{{/users/enseig/jpc/M1-CAO/TME/5.public}}}.  Vous  pouvez aussi  récupérer
+l'archive suivante: [attachment:TME5-public.tar.bz2].
+
+
+= A) Structures de données =
+
+On utilise deux structures de données pour représenter :
+
+ * Le réseau Booléen ({{{BoolNet}}}), c'est à  dire le graphe biparti des processus et des
+   signaux.
+
+ * L'échéancier ({{{Scheduler}}}), c'est à dire l'ensemble ordonné des événements.
+
+
+== A1) réseau Booléen ==
+
+Un réseau  booléen est représenté par un graphe  orienté biparti. Il est donc  constitué de
+deux types de noeuds et d'arcs orientés reliants les noeuds entre eux.
+
+Les deux types de noeuds sont les ''signaux'' et les ''processus''.
+
+Un arc  orienté relie  un noeud source  à un noeud  cible. Notez  que comme le  graphe est
+biparti, les noeuds  sources et destination sont toujours de types  différents.  On ne va
+pas créer d'objet spécifique pour représenter  un arc. Plus simplement, les noeuds sources
+contiendront une liste de noeuds cible.
+
+ * Un ''Signal'' considéré  comme source, peut être utilisé dans  un nombre quelquonque de
+   processus.  il aura donc une liste de ''Processus'' cibles.
+
+ * Un ''processus''  considéré comme source aura  une unique cible: le  ''signal'' dont il
+   calcule la valeur. Il n'est donc pas  nécessaire de gérér une liste, un simple pointeur
+   suffira. 
+
+'''La classe {{{BoolNet}}}'''
+
+Elle contient un ensemble de signaux et un ensemble de processus.
+
+En plus des accesseurs triviaux, elle fourni une fonction de recherche d'un signal par son
+nom {{{getSignal(const std::string&  )}}} ainsi que deux méthodes  pour la construction du
+réseau booléen. Le réseau booléen est initialisé vide.
+
+ * Méthode {{{addSignal()}}}:  ajoute au  réseau Booléen un  noeud de type  ''signal''. On
+   donne  le   nom  du  signal  ainsi   que  son  type  (parmis   {{{In}}},  {{{Out}}}  et
+   {{{Internal}}}.  La  liste des cibles du  noeud représentant le  signal est initialisée
+   vide.
+
+ * Méthode {{{addProcess()}}}:  ajoute au réseau  Booléen un noeud de  type ''processus''.
+   On  donne respectivement  comme arguments,  le  nom du  ''signal'' cible,  l'expression
+   booléenne  qu'il  représente  (sous forme  textuelle)  et  le  délai  de calcul  de  ce
+   processus.
+
+'''Importante remarque''': les arcs (liste de  cibles attachée à chaque noeud source) sont
+construits  lors de  la  création  des processus.   Il  est donc  impératif  que tous  les
+''signaux'' aient été créés avant de commencer à créer les ''processus''.
+
+La  méthode {{{toDot()}}}  crée une  représentation  graphique du  réseau booléen.   Cette
+fonction vous est fournie.
+
+{{{
+#!cpp
+class BoolNet {
+  private:
+    std::string            _name;
+    std::vector<Signal*>   _signals;
+    std::vector<Process*>  _processes;
+  public:
+                                  BoolNet      ( const std::string& );
+    inline std::string&           getName      ();
+           Signal*                getSignal    ( const std::string& );
+    inline std::vector<Signal*>&  getSignals   ();
+    inline std::vector<Process*>& getProcesses ();
+           Signal*                addSignal    ( const std::string&, SignalType );
+           Process*               addProcess   ( const std::string&, const std::string&, unsigned int delay );
+           void                   toDot        ( std::ostream& );
+           void                   toDot        ();
+};
+}}}
+
+'''La classe {{{Signal}}}'''
+
+Attributs:
+
+ * {{{_network}}} : le réseau booléen auquel elle appartient.
+ * {{{_variable}}} :  l'{{{EbmVar}}} qu'elle encapsule.  Le contructeur devra  créer cette
+   {{{EbmVar}}} à la contruction.
+ * {{{_type}}} : le type du signal (parmis {{{In}}}, {{{Out}}} et {{{Internal}}}).
+ * {{{_processes}}}  : la représentation  des arcs.  On choisi  un {{{set<>}}}  pour gérer
+   automatiquement l'unicité.
+
+Méthode non triviale:
+
+ * {{{addProcess()}}}  : ajoute une  nouvelle cible  à l'ensemble  des cibles.  Equivaut à
+   créer un arc dans le graphe.
+ * {{{setValue()}}}  : modifie la valeur logique de la variable associée au signal.
+
+{{{
+#!cpp
+class Signal {
+  private:
+    BoolNet*            _network;
+    EbmVar*             _variable;
+    SignalType          _type;
+    std::set<Process*>  _processes;
+  public:
+                               Signal       ( BoolNet*, const std::string&, SignalType );
+    inline std::string         getName      ();
+    inline SignalType          getType      ();
+    inline ValueType           getValue     ();
+    inline std::set<Process*>& getProcesses ();
+    inline void                addProcess   ( Process* );
+    inline void                setValue     ( ValueType );
+};
+}}}
+
+'''La classe {{{Process}}}'''
+
+Attributs:
+
+ * {{{_network}}} : le réseau booléen auquel elle appartient.
+ * {{{_signal}}} : le signal qu'elle calcule. C'est la représentation de l'unique arc issu
+   d'un noeud de type ''processus''.
+ * {{{_expression}}} :  l'{{{EbmExpr}}} de  calcul. On  la créera à  l'aide de  la méthode
+   {{{Ebm::parse()}}} qui vous est fournie.
+ * {{{_delay}}} : le temps nécessaire au calcul de la nouvelle valeur. Représente le temps
+   de propagation entre un événement sur une entrée quelconque et la sortie du circuit.
+
+Méthodes non triviales:
+
+ * {{{Process()}}} : le  constructeur du processus en plus de sa tâche  d'initialisation des membres de
+   l'objet  devra créer  les  ''arcs'' entre  les  ''signaux'' appartenant  au support  de
+   l'expression et le processus courant.
+ * {{{eval()}}}  et {{{display()}}}  sont des  encapsulations des  méthodes  identiques de
+   la classe {{{Ebm}}}.
+
+{{{
+#!cpp
+class Process {
+  private:
+    BoolNet*      _network;
+    Signal*       _signal;
+    Ebm*          _expression;
+    unsigned int  _delay;
+  public:
+                         Process       ( BoolNet*, Signal*, const std::string& expression, unsigned int delay=0 );
+           ValueType     eval          ();
+    inline Ebm*          getExpression ();
+    inline Signal*       getSignal     ();
+    inline unsigned int  getDelay      ();
+           void          display       ( std::ostream& );
+           std::string   toString      ();
+};
+}}}
+
+== A2) échéancier ==
+
+Le rôle  de l'échéancier  (''scheduler'' en anglais)  est d'enregistrer et  d'ordonner les
+évènements  dans le  temps.   Pour le  réaliser nous  avons  besoin de  définr les  objets
+suivants:
+
+ * Une date  (classe {{{Date}}})  contenant deux informations  : le temps  physique écoulé
+   depuis le  début de la  simulation, et un  temps logique permettant de  distinguer deux
+   événements X  et Y  possédant le  même temps physique,  mais reliés  entre eux  par une
+   relation de causalité : ceci se produit quand on veut représenter des processus dont le
+   temps de propagation est nul.
+
+ * Un événement  (classe {{{Event}}}),  comportant la date  ({{{Date}}}) à laquelle  il se
+   produit, Le signal qu'il affecte et la nouvelle valeur que va prendre ce signal.
+
+ * Une structure  permettant de stocker  les d'évenements et  de trier ces  événements par
+   dates croissantes.  Nous  allons pour cela utiliser une  {{{map<>}}} de {{{vector<>}}}.
+   C'est à dire,  une {{{map<>}}} dont chaque élément  sera un {{{vector<>}}} d'évènements
+   et la  clé une date  ({{{Date}}}).  Deux événements  sont synchrones s'ils ont  le même
+   temps physique '''et''' le même temps logique. L'ordre est sans importance au sein d'un
+   ensemble  d'événements  synchrones,  puisqu'il ne  peut  pas  y  avoir de  relation  de
+   causalité entre deux événements synchrones.
+
+'''Propriérés remarquables de la {{{map<>}}} de {{{vector<>}}}'''
+
+'''Syntaxe:'''
+{{{
+#!cpp
+map<Date, vector<Event*> >  _events;
+}}}
+
+La  clé de tri  est un  objet de  type {{{Date}}}  et la  valeur associée  à cette  clé un
+{{{vector<Event*>}}}.  Il  faudra définir  pour  la  classe  {{{Date}}} une  surcharge  de
+l'operateur   ''strictement   inférieur''   ({{{operator<()}}})   qui   définira   l'ordre
+chronologique.
+
+'''Accès et itérateurs'''
+{{{
+#!cpp
+map<Date, vector<Event*> >            _events;
+map<Date, vector<Event*> >::iterator  istate = _events.begin();
+
+for ( ; istate != _events.end() ; ++istate ) {
+  const Date&     date   = (*istate).first;
+  vector<Event*>& events = (*istate).second;
+
+// Do something here.
+}
+}}}
+
+ * Lors d'un parcours  de la {{{map<>}}} avec des itérateurs,  les éléments sont parcourus
+   ''dans l'ordre défini par la relation d'ordre de la clé'', c'est à dire dans notre cas,
+   l'ordre chronologique des dates croissantes.
+
+ * Cet ordre  est maintenu automatiquement lors  d'ajout ou de retrait  d'élements dans la
+   {{{map<>}}}.
+
+ * Les itérateurs pointant sur des éléments de la {{{map<>}}} restent valides même si l'on
+   ajoute ou retire des éléments pendant  le parcours (une seule exception: si l'on retire
+   l'élement sur lequel l'itérateur pointe...).
+
+ * Les éléments  d'une {{{map<>}}}  sont des paires  {{{(clé,valeur)}}}, pour y  accéder à
+   partir  de l'itérateur,  il faut  utiliser les  attributs public  {{{first}}}  (clé) et
+   {{{second}}} (valeur).
+
+'''La classe {{{Date}}}'''
+
+{{{
+#!cpp
+class Date {
+  private:
+    unsigned int  _time;
+    unsigned int  _delta;
+  public:
+    inline               Date      ( unsigned int time, unsigned int delta );
+    inline unsigned int  getTime   () const;
+    inline unsigned int  getDelta  () const;
+    friend bool          operator< ( const Date& lhs, const Date& rhs );
+};
+}}}
+
+
+'''La classe {{{Event}}}'''
+
+L'attribut  {{{_value}}}   contient  la  ''prochaine''   valeur  du  signal.   La  méthode
+{{{Event::updateSignalValue()}}} est chargé de faire la mise à jour effective de la valeur
+du signal. Elle sera appelée dans l'étape de mise à jour du simulateur.
+
+{{{
+#!cpp
+class Event {
+  private:
+    Signal*    _signal;
+    ValueType  _value;
+    Date       _date;
+  public:
+    inline             Event             ( Signal*, ValueType, Date& );
+    inline  Signal*    getSignal         ();
+    inline  ValueType  getValue          ();
+    inline  Date&      getDate           ();
+    inline  void       updateSignalValue ();
+};
+}}}
+
+
+'''La classe {{{Scheduler}}}'''
+
+Méthodes non triviales:
+
+ * {{{addEvent(Signal*,...)}}} : ajoute un nouvel évènement à l'échéancier. Pour donner la
+   date  on ne  passe  pas d'objet  {{{Date}}},  mais ses  deux  composants {{{time}}}  et
+   {{{delta}}}.
+
+ * {{{addEvent(const std::string&,...)}}}  : une surcharge  de la fonction  précédente qui
+   prend comme premier  argument un nom de ''signal'' au lieu  du pointeur sur ''signal''.
+   Cette méthode sera utilisée préférentiellement pour initialiser l'échéancier.
+
+ * {{{simulate()}}} : effectue la simulation.
+
+ * {{{toPatterns()}}} : écrit dans le flot  donné en argument le résultat de la simulation
+   dans un  format lisible par l'outil  {{{xpat}}}.  Cette fonction vous
+   est fournie.
+
+ * {{{_reset()}}}  : remet  toutes les  variables  (entrées, sorties,  internes) à  l'état
+   indéfini (U).
+
+ * {{{_header()}}} et {{{_display()}}} :  utilitaires vous permettant d'afficher l'état de
+   la simulation à un instant donné.
+
+{{{
+#!cpp
+class Scheduler {
+  private:
+    BoolNet*                              _network;
+    std::map<Date, std::vector<Event*> >  _events;
+  public:
+           Scheduler  ( BoolNet* );
+    Event* addEvent   ( const std::string& variable, ValueType, unsigned int time, unsigned int delta=0 );
+    Event* addEvent   ( Signal*, ValueType, unsigned int time, unsigned int delta=0 );
+    void   simulate   ();
+    void   toPatterns ( std::ostream& );
+    void   toPatterns ();
+  private:
+    void   _reset     ();
+    void   _header    ();
+    void   _display   ( const Date& );
+};
+}}}
+
+
+= C) Travail à réaliser =
+
+Dans  un premier  temps  vous  devrez utiliser  le  simulateur qui  vous  est fourni  dans
+l'ensemble des fichiers {{{.o}}}.
+
+Dans  un second  temps,  il vous  est  demandé de  progressivment  remplacer les  fichiers
+{{{.o}}} fournis par les objets résultant de la compilation de votre propre code.
+
+
+== C1) simulation du circuit ''And Or'' ==
+
+Le  fichier {{{AndOr.c}}}  contient un  tout petit  réseau Booléen  ne contenant  que deux
+noeuds, et 4 signaux. Compilez ce fihier, et exécutez la simulation.
+
+Vous pouvez visualiser le réseau Booléen avec la commande:
+{{{
+> eog AndOr.png
+}}}
+Vous pouvez visualiser le chronogramme résulat de la simulation avec la commande:
+{{{
+> xpat -l AndOr
+}}}
+
+
+== C2) Simulation d'un additionneur 2 bits ==
+
+On se propose de simuler le schéma suivant, qui réalise un additionneur 2 bits. 
+A chaque porte est associé une expression Booléenne représentée par un EBM.
+
+[[Image(schema_portes.png, nolink)]]
+
+
+== C2.1) Construction réseau Booléen de l'additionneur ==
+
+En vous inspirant du fichier {{{AndOr.c}}}, écrivez le fichier {{{Adder.c}}} qui construit
+en  mémoire  le  réseau  Booléen  correspondant  au circuit  additionneur  2  bits  décrit
+ci-dessus.   On   utilisera  pour   cela  les  fonctions   {{{BoolNet::addProcess()}}}  et
+{{{BoolNet::addSignal()}}}.  On prendra une valeur de 1 ns pour le temps de propagation de
+la porte {{{NAND2}}}, et de 2 ns  pour la porte {{{XOR2}}}.  Pour vérifier la structure du
+réseau  Booléen, on  utilisera la  fonction {{{toDot()}}}.   Cette fonction  construit une
+représentation graphique  du réseau Booléen,  et la sauvegarde  dans un fichier  au format
+{{{.gif}}} ou {{{.ps}}}.
+
+Modifiez le Makefile permettant de compiler ce programme ''Adder.c'', et exécutez-le. 
+
+
+== C2.2) Construction et initialisation de l’échéancier ==
+
+Compléter le fichier {{{Adder.c}}} {{{main()}}} pour créer l’échéancier et initialiser les
+événements  sur les  signaux d’  entrée a0,  b0,  c0, a1  et b1  de façon  à respecter  le
+chronogramme ci-dessous.   On utilisera la fonction  Scheduler::addEvent() et add_event().
+Attention  : le  passage de  la valeur  U (indéfinie)  à une  valeur 0  ou 1  constitue un
+événement : Dans ce  chronogramme, il y a donc un événement  sur tous les signaux d’entrée
+au temps {{{T = 0}}}.
+
+[[Image(chronogramme.png,nolink)]]
+
+Pour vérifier que l’échéancier est correctement initialisé, on pourra utiliser la fonction
+''Scheduler::drive()''.  Cette  fonction peut être  utilisée avant même l'exécution  de la
+fonction de simulation, pour générer un  fichier au format .pat qui décrit le chronogramme
+des signaux d'entrée. Vous pouvez visualiser ce chronogramme avec l’outil {{{xpat}}}.
+
+== C2.3) Simulation effective du circuit additionneur ==
+
+Introduisez  dans  le fichier  {{{Adder.c}}}  la  méth