Changes between Initial Version and Version 1 of CaoCourseTme7

Timestamp:

Mar 22, 2007, 11:47:47 AM (18 years ago)

Author:

alain

Comment:

--

CaoCourseTme7

@@ +1 @@
+{{{
+#!html
+<h1>TME 7 : Simulation logici-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 permette de simuler des systèmes matériels constitués d'un ensemble 
+de composants matériels interconnectés par des signaux. Les signaux électriques 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  0, 1, et U (indéfini).
+
+Dans le cas général, Chaque composant est modélisé par un processus séquentiel, 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. 
+Les signaux sont donc orientés, et 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, où un processus correspond à une expression Booléenn 
+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. Un 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. 
+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).
+
+Il faut évidemment respecter le principe de causalité, c'est-à-dire qu'il ne peut y avoir d'événement sur le signal de sortie  d'un processus que 
+s'il y a eu préalablement au moins un événement sur un signal d'entrée du processus. Simuler le fonctionnement d'un circuit consiste donc 
+à calculer pour chaque signal la succession des événements pour chaque signal, 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).
+ 
+== B) Structures de données
+On utilise deux structures de données :
+ * structure représentant le réseau Booléen, c'est à dire le graphe biparti des processus et des signaux, 
+ * structure représentant l'échéancier, c'est à dire l'ensemble ordonné des événements.
+ 
+= B1) Le 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
+struct 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
+struct process_t        * NEXT;         // processus suivant
+} process_t
+}}}
+
+B2) L’é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. 
+ 
+typedef struct event_t {
+signal_t                * SIGNAL;               // signal modifié 
+unsigned                  VALUE;                // nouvelle valeur
+long                      DATE;         // date de la modification
+struct event_t  * PREV ;                // événement précédent dans l’echéancier
+struct event_t  * NEXT;         // événement suivnt 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. 
+
+ typedef struct scheduler_t {
+ long             TC;                   // Temps Courant 
+ event_t        * CURRENT;              // pointeur sur le premier événement à TC
+ event_t        * FIRST;                // pointeur sur le premier événement de la liste
+ } scheduler_t
+
+C/ Fonctions d'accès aux structures de données
+
+Ce paragraphe définit 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.
+
+C1) Création d'un réseau Booléen "vide"
+
+boolnet_t * cons_boolnet (char * name)
+
+Les pointeurs sur les listes de signaux et de processus sont initialisés à NULL.
+  
+C2) Création d’un signal 
+
+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.
+   
+C3) Création d’un processus
+  
+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. Cette fonction vérifie 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.
+   
+C4) Création d’un échéancier « vide »
+ 
+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.
+
+C5) Création d’un événement
+
+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.
+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).
+ 
+C6) Insertion d’un événement
+
+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.
+    
+C7) Récupération des événements au temps TC
+
+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).
+
+C8) Progression du temps simulé
+
+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.
+
+C9) Mise à jour des signaux
+
+bip_t * update_signals ( bip_t * events)
+
+Cette fonction prend pour argument un pointeur sur une liste de signaux (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 faudra également libérer quand ils ne seront plus utilisés).
+
+C10) Récupération des processus à évaluer
+
+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).
+
+C11) Evaluation d’un process
+
+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).
+
+ D/ Travail à réaliser
+
+On se propose de simuler le schéma suivant, qui réalise un additionneur 2 bits. 
+A chaque porte est associé un processus modélisé par un arbre ABL.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+D1) Construction du réseau Booléen
+
+Utiliser les fonctions cons_boolnet(), cons_process() et cons_signal() pour construire en mémoire le réseau Booléen correspondant au circuit-ci-dessus. On prendra une valeur de 1 ns pour le temps de propagation de la porte NAND2, et de 2 ns pour la porte XOR2. Ecrire, compiler et exécuter le programme main() qui construit le réseau Booléen. Pour vérifier la structure du réseau Booléen, on pourra utiliser la fonction :
+
+void drive_boolnet(dotfmt_t format, boolnet_t *bn)
+
+Cette fonction construit une représentation graphique du réseau Booléen, et la sauvegarde dans un fichier au format .gif ou .ps.
+
+enum dotfmt_t { GIF , PS }
+
+D2) Construction et initialisation de l’échéancier
+
+Complêter le programme main() de la question D1 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 suivant . 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.
+
+
+Pour vérifier que l’échéancier est correctement initialisé, on pourra utiliser la fonction:
+
+void drive_scheduler (boolnet_t * bn, scheduler_t * sch)
+
+Cette fonction génére un fichier au format .pat que vous pouvez visualiser avec l’outil XPAT que vous connaissez déjà.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+D3) Ecriture de la boucle de simulation
+
+Ecrire la boucle fonction principale de simulation qui enchaîne les phases “update” et “exécute” présentées 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 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.
+
+D4) Ecriture des fonctions d’accès
+
+Ecrivez vous-même le code des 11 fonctions d’accès aux structures de données du simulateur décrites dans la section C, et introduire progressivement votre code à la place des fichiers .o qui vous ont été fournis.