{{{
#!html
<h1>TMEs 9 &amp; 10 : Simulation logico-temporelle</h1>
}}}
[[PageOutline]]

= Attention =

'''L'archive TME9.tar.bz2 a été mise à jour, elle est maintenant compatible avec !LogicValue.'''

'''Nouvelle mise à jour le 11 décembre 2012 (13h).'''

= 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 l'archive suivante: [attachment:TME5.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}}}.
 * {{{toString()}}} renvoie, dans une {{{string}}}, l'expression booléenne associée au
   {{{Process}}}.

{{{
#!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éthode ``Scheduler.simulate()``, déterminez
à priori,  les chronogrammes des sorties,  puis vérifiez que ceux  obtenus par simulation
correspondent.