TMEs 9 & 10 : Simulation logico-temporelle

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.

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: 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.

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.

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.

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:

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

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

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.

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é.

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.

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.

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.