Changes between Initial Version and Version 1 of 2009/CaoCourseTme7

Timestamp:

Jan 11, 2010, 12:03:37 AM (15 years ago)

Author:

franck

Comment:

--

2009/CaoCourseTme7

@@ +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 ABL (voir TME5).
+
+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. 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 (indéfini).
+
+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, représentée par un arbre ABL. Dans ce cas particulier, un processus possède donc un seul signal de sortie, 
+et la liste de sensibilité contient tous les signaux d'entrée. Le réseau Booléen peut être représenté par un graphe biparti 
+comportant deux types de noeuds : des processus et des signaux. Les noeuds à la périphérie du réseau sont toujours des signaux. 
+
+[[Image(reseau_booleen.png, nolink)]]
+
+En d'autres termes, un processus a toujours au moins un signal entrant et un signal sortant.  Les signaux qui n'ont pas d'arrête 
+entrante sont les entrées primaires du réseau, les signaux qui n'ont pas d'arrête sortante 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, il faudra disposer d’une fonction eval_abl() capable de traiter les trois valeurs (0,1,U).
+
+Créez un répertoire de travail TME7, et copiez dans ce répertoire tous les fichiers et répertoires utiles pour ce TME.
+{{{
+cp -rp /users/enseig/encadr/cao/tme7 .
+}}}
+
+= A) Structures de données =
+
+On utilise deux structures de données pour représenter :
+ * le réseau Booléen, c'est à dire le graphe biparti des processus et des signaux, 
+ * l'échéancier, c'est à dire l'ensemble ordonné des événements.
+
+'''A1) réseau Booléen'''
+
+Le réseau Booléen est constitué d'un ensemble de signaux et d'un ensemble de processus. 
+Les signaux sont regroupés dans trois sous-ensembles disjoints suivant leur type (IN, OUT, INTERNAL).
+{{{
+typedef struct boolnet_t {
+char            * NAME;         // nom du circuit modélisé
+signal_t        * IN ;          // ensemble des signaux IN
+signal_t        * OUT ;         // ensemble des signaux OUT
+signal_t        * INTERNAL;     // ensemble des signaux INTERNAL
+process_t       * PROCESS;      // ensemble des proceessus
+} boolnet_t;
+}}}
+L’ordre dans les listes des signaux et des processus n'est pas significatif. Ils sont chaînés dans l'ordre de leur création.
+
+Un signal possède un type, un pointeur sur une variable Booleenne (var_t), qui définit son nom et sa valeur (0,1 ou U). 
+Il possède également un pointeur sur le processus dont il est la sortie, et un pointeur sur la liste chaînée des processus dont il est une entrée.
+{{{
+typedef struct signal_t {
+boolnet_t       * BOOLNET;      // pointeur sur le réseau Booléen
+sigtype_t         TYPE;         // type du signal
+var_t           * VAR;          // variable Booléenne associée 
+bip_t           * TO_PROCESS;   // liste des process destinataires
+process_t       * FROM_PROCESS; // process source
+signal_t        * NEXT;         // signal suivant de même type
+} signal_t;
+}}} 
+Le type pourra prendre une des valeurs du type enuméré suivant :
+{{{
+enum sigtype_t {
+IN              = 0, 
+OUT             = 1, 
+INTERNAL        = 2};
+}}}            
+Un processus est une expression Booléenne qui définit la valeur du signal de sortie, en fonction des valeurs des signaux d’entrée. 
+Il est caractérisé par un temps de propagation qui est le retard entre un événement sur une entrée et l'événement sur la sortie 
+qui en est la conséquence. Dans le cas général, les temps de propagation dépendent de l'entrée qui commute, 
+mais pour simplifier le simulateur, on suppose que le temps de propagation ne dépend pas de l'entrée qui commute.
+{{{ 
+typedef struct process_t {
+boolnet_t       * BOOLNET;      // pointeur sur le réseau Booléen
+signal_t        * SIGNAL;       // pointeur sur le signal de sortie
+bip_t           * ABL;          // pointeur sur l’arbre ABL associé
+long            DELAY;          // retard entrée -> sortie (en ps)
+bip_t           * SUPPORT;      // liste des signaux d’entrée
+process_t       * NEXT;         // processus suivant
+} process_t
+}}}
+
+'''A2) échéancier'''
+
+L'échéancier permet d'enregistrer  et d'ordonner les événements dans le temps. 
+Ceux-ci sont donc rangés dans une liste doublement chaînée, par dates croissantes. 
+Un événement représente une affection de valeur à un signal à une certaine date. 
+{{{
+#!c
+typedef struct event_t {
+  signal_t      * SIGNAL;       // signal modifié 
+  unsigned        VALUE;        // nouvelle valeur
+  long            DATE;         // date de la modification
+  event_t       * PREV ;        // événement précédent dans l’echéancier
+  event_t       * NEXT;         // événement suivant dans l’echéancier
+} event_t;
+}}}
+L'échéancier peut contenir plusieurs événements à la même DATE, mais portant sur des signaux différents. 
+Ces événements synchrones sont rangés consécutivement dans la liste chaînée, 
+mais l'ordre entre ces événements synchrones n'est pas  significatif. 
+L'échéancier représente la liste ordonnée des événements passés, présents, et futurs. 
+Il contient donc en particulier la variable TC qui représente la date courante. 
+{{{
+#!c
+typedef struct scheduler_t {
+  long            TC;           // Temps Courant 
+  event_t       * CURRENT;      // pointeur sur le premier événement à a date TC
+  event_t       * FIRST;        // pointeur sur le premier événement de l'échéancier
+} scheduler_t;
+}}}
+
+= B) Fonctions d'accès aux structures de données =
+
+On présente ici les différentes fonctions permettant d’accéder aux structures de données définies ci-dessus. 
+
+Dans un premier temps le code binaire exécutable de ces fonction vous est fourni, 
+et vous pourrez utiliser ces fonctions pour construire en mémoire le réseau Booléen, 
+construire et initialiser l’échéancier, et écrire la boucle principale de simulation qui a été présentée en cours.
+
+Dans un deuxième temps, il vous sera demandé d’écrire vous-même le code de ces fonctions.
+
+'''B1) construction réseau Booléen'''
+
+{{{
+boolnet_t * cons_boolnet (char * name)
+}}}
+Cette fonction construit un réseau Booléen "vide" de nom ''name''.
+Les pointeurs sur les listes de signaux et de processus sont initialisés à NULL.
+{{{
+signal_t * cons_signal (boolnet_t * bn, sigtype_t type, var_t * var)
+}}}
+Cette fonction prend pour argument une variable Booléenne préalablement créée. 
+Elle crée un signal et l’insère dans la liste des signaux du réseau correspondant à son type. 
+Elle initialise à NULL les pointeurs FROM_PROCESS et TO_PROCESS. La valeur de la variable Booléenne est forcée à U.
+{{{ 
+process_t * cons_process (boolnet_t * bn, signal_t * sig, char * abl, long delay)
+}}}
+Cette fonction prend pour argument un pointeur sur le signal de sortie, un pointeur sur un arbre ABL préalablement créé 
+(en utilisant par exemple  la fonction parse_abl du TME5), et la valeur du temps de propagation.
+Elle crée une structure process_t, calcule le support de l'abl (sous forme d’une liste de signaux d’entrée), 
+et met à jour les pointeurs contenus dans les structures représentant les signaux impliqués. 
+
+'''Attention :''' La fonction support_abl du TME5 retourne une liste de variables, mais le champs SUPPORT de l'objet
+process_t doit pointer sur une liste de signaux!
+
+Cette fonction doit  vérifier le typage des signaux, c'est-à-dire qu'un signal de type IN ne peut avoir de processus générateur 
+et qu'un signal de type OUT ne peut apparaître dans le support d'une fonction.
+
+'''B2) construction échéancier'''
+{{{ 
+scheduler_t * cons_scheduler()
+}}}
+Cette fonction fabrique un échéancier « vide ». 
+La date courante  TC est initialisée à une valeur négative, et les pointeurs FIRST et CURRENT sont initialisés à NULL.
+{{{
+event_t * cons_event(scheduler_t * sch, signal_t * sig, long date, unsigned val)
+}}}
+Cette  fonction construit un événement  sur le signal sig, à un certaine date, 
+avec la valeur val, et introduit cet événement dans l’échéancier. 
+Cette fonction met à jour les deux pointeurs FIRST et CURRENT dans l’échéancier, si cela est nécessaire.
+'''Attention''' : Cette fonction ne doit être utilisée que dans la phase d’initialisation, pour introduire dans l’échéancier 
+les événements portant sur les signaux d’entrée du circuit (stimuli).
+
+'''B3) simulation'''
+{{{
+void add_event (scheduler_t * sch, signal_t * sig, long delta, unsigned val)
+}}}
+Cette fonction construit un événement portant sur le signal sig, à la date TC + delta, avec la valeur val, et le range dans l'échéancier. 
+A la différence de la précédente, cette fonction utilise un temps relatif (delta), et ne modifie pas le les pointeurs FIRST et CURRENT. 
+C’est cette fonction qui doit être utilisée dans la boucle de simulation. 
+Dans le cas général, cette fonction doit en principe vérifier qu’il n’existe pas un autre événement postérieur sur le même signal, 
+et retirer cet événement parasite s’il y a lieu. Dans notre cas, cela n’est pas nécessaire. 
+Cette importante simplification est dûe à l'hypothèse qu'un processus est caractérisé par un unique temps de propagation, 
+qui ne dépend pas de l'entrée qui commute. Avec cette hypothèse, tous les événements prévus se produisent effectivement.
+{{{    
+bip_t * get_events (scheduler_t * sch)
+}}}
+Cette fonction recherche dans l'échéancier les événements prévus au temps TC. 
+Il peut y avoir plusieurs événements à la même date. Elle renvoie ces événements sous forme d'une liste chaînée de bi-pointeurs 
+(qu'il faut penser à libérer quand ils ne sont plus utiles).
+{{{
+unsigned update_tc(scheduler_t * sch)
+}}}
+Cette fonction modifie la valeur de la variable TC en lui donnant la valeur de la date du premier événement strictement postérieur au temps courant. 
+Elle met à jour le pointeur CURRENT de l’échéancier. 
+Cette fonction renvoie la valeur 0 quand elle ne trouve pas d’événement postérieur au temps courant, 
+ce qui correspond à la fin de la simulation. Cette valeur doit donc être testée à chaque itération de la boucle de simulation.
+{{{
+bip_t * update_signals ( bip_t * events)
+}}}
+Cette fonction prend pour argument un pointeur sur une liste d'événements (liste de bipointeurs). 
+Elle modifie la valeur des variables Booléennes associées à chacun des signaux pour lesquels il existe un événement. 
+Elle rend la liste des signaux qui ont été modifiés (une autre liste de bipointeurs, qu’il faut également libérer quand ils ne sont plus utilisés).
+{{{
+bip_t * get_processes (boolnet_t * bn, bip_t * signals)
+}}}
+Cette fonction prend comme argument un pointeur sur le réseau Booléen, et une liste de signaux, 
+et elle renvoie un pointeur sur une autre liste contenant l’ensemble de tous les processus ayant 
+au moins un signal d’entrée appartenant à l’ensemble ''signals''.
+(ici encore, il faut penser à libérer la mémoire occupée par les bi-pointeurs quand ils ne sont plus utiles).
+{{{
+void eval_processes( scheduler_t * sch, bip_t * p)
+}}}
+Cette fonction prend pour argument une liste de processus, ainsi qu’un pointeur sur le scheduler, 
+et évalue la valeur du signal de sortie pour chacun des processus de la liste,  en fonction des valeurs des signaux d’entrée. 
+Elle utilise pour cela une version de la fonction eval_abl() modifiée pour traiter une logique à trois valeurs (0,1,U). 
+Elle compare la valeur future du signal de sortie à sa valeur présente, et insère un événement dans  l’échéancier 
+si cette valeur change (en utilisant la fonction add_event).
+
+= C) Travail à réaliser =
+
+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 arbre ABL.
+
+[[Image(schema_portes.png, nolink)]]
+
+== C1) simulation du circuit ''etou'' ==
+
+Le fichier ''etou.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.
+{{{
+> make
+}}}
+Lancez l'exécution duprogramme (construction du réseau Booléen et simulation).
+{{{
+> ./etou
+}}}
+Vous pouvez visualiser le réseau Booléen avec la commande:
+{{{
+> xv etou.gif
+}}}
+Vous pouvez visualiser le chronogramme résulat de la simulation avec la commande:
+{{{
+> xpat -l etou
+}}}
+
+== C2) Construction réseau Booléen de l'additionneur ==
+
+En vous inspirant du fichier ''etou.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 cons_boolnet(), cons_process() et cons_signal().
+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 ''drive_boolnet()''.
+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. 
+
+== C3) 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 les fonctions cons-scheduler() 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 ''drive_scheduler ()''.
+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.
+
+== C4) Simulation effective du circuit additionneur ==
+
+Introduisez dans le fichier ''adder.c'' la fonction ''simulate()'' qui effectue la simulation du réseau Booléen, 
+jusqu'à ce qu'il n'y ait plus aucun événement à traiter dans l'échéancier. Compilez ce programme,
+et analysez le chronogramme résultant
+
+== C5) Ecriture de la boucle de simulation ==
+
+Ecrire en langage C la fonction ''simulate()''. Cette fonction contient une boucle ''while'' qui enchaîne les 
+deux phases “update” et “exécute” de l'algorithme de simulation ''event-driven'' présenté en cours. 
+{{{
+void simulate (boolnet_t * bn, scheduler_t * sch)
+}}}
+On utilisera pour cela les fonctions get_events(), update_tc(), update_signals(), get_process() et eval_process(). 
+On sauvera sur disque le contenu de l’échéancier en sortie de la boucle de simulation en utilisant la fonction drive_scheduler(), 
+de façon à visualiser le chronogramme avec l’outil XPAT.
+
+== C6) Ecriture des fonctions d’accès ==
+
+Bien que le texte de cette question soit très court, cette question est  évidemment la plus importante du TME :
+Ecrivez vous-même le code des 11 fonctions d’accès aux structures de données du simulateur décrites 
+dans la section B, et introduire progressivement votre code à la place des fichiers .o qui vous ont été fournis.
+
+= Compte-Rendu =
+
+Il ne vous est pas demandé de compte-rendu écrit pour ce TME, mais vous devrez faire une démonstration
+de votre code au début du prochain TME.
+