Matthias Bernauer - Freiburg im Breisgau
      Start > Skript-Sammlung > Rechnerarchitektur > Simulationstechniken >>







Simulationstechniken

Aufgabe von Simulationsalgorithmen: Abbilden von HW-Funktionalität (Hardwarebeschreibung z.B. in Verilog) auf eine Zielarchitektur (PC oder Workstation, z.B. von Neumann Rechner)
Problem: hoher Grad an Parallelität muss auf eine sequentielle Maschine ¬Ąprojiziert¬ď werden


Arten der HW-Simulation
Analogsimulation (Spice, ...) Ströme, Spannungen
- werte- und zeitkontinuierlich
- nichtlineare Differentialgleichungen

  • Digitalsimulation (VSS, Modelsim, ...) nur 0 und 1
    - werte- und zeitdiskret
    - boolesche Algebra oder auf höheren Abstraktionsebene, z.B. Mit Fließkommazahlen


    • Mixed-Mode/Simulatorkopplung (Saber,...)
      - analog/digital-Simulation
    • Logiksimulationsalgorithmen:

      • Streamline Code Simulation (auch 'Compiled Mode'): Schaltkreise, vollsynchrone Schaltwerke, es wird direkt ausführbarer Code auf der Zielplattform generiert.
        Einschränkungen:
        - kombinatorische oder strikt synchrone Schaltwerke
        - keine Zeitinformationen
        - Simulation bei synchronen Schaltwerken nur ¬Ązyklengenau¬ď
        Kombinatorischer Schaltkreis wird als gerichteter azyklischer Graph notiert:

        => Topologische Sortierung: Knoten des azyklischen Graphes werden halbgeordnet (levelizing)

        int a, b, c, d, e;
        int x1, x2, x3;
        int o1, o2;
        x1 = b & c; //lev1
        x2 = d & e; //lev1
        x3 = x1 | x2; //lev2
        o1 = a & x3; //lev3
        o2 = x2 | x3; //lev3
        | bitweises Oder

        Eigenschaften des Graphen:
        - Knoten auf einer höheren Ebene können Knoten auf niedrigeren Ebenen nicht beeinflussen
        - Knoten auf derselben Ebene beeinflussen sich gegenseitig nicht
        - Knoten auf niedrigeren Ebenen beeinflussen Knoten auf höheren Ebenen
        Codegenerierung:
        - Level werden nacheinander implementiert
        - Reihenfolge der Operationen in den Levels ist beliebig
        - Gatter werden durch Operatoren der Zielmaschine realisiert
        - Verbindungen (Signale) werden durch Variablen der Zielmaschine implementiert
        Da int aus z.B. 32 Bits besteht, können mit dieser Technik 32 Simulationen gleichzeitig durchgeführt werden -> wortparallele Simulation mit Beschleunigungsfaktor 32. 32 mögl. Eingangsvektoren:
        a = (a0, a1, ..., a31)
        b = (b0, b1, ..., b31) => o1 = (o1_0, o1_1, ..., o1_31)
        ... o2 = (o2_0, o2_1, ..., o2_31)
        e = (e0, e1, ..., e31)
        Vorteile:
        - es wird auf der Ziel-
        Maschine comilierter
        Code erzeugt, d.h.
        Schnelle Abarbeitung
        - wortparalleles
        Arbeiten

        Betrachte StreamlineCodeSimulation ohne paralelles Arbeiten:
        - das Verfahren ist linear in der Anzahl der Gatter!
        - Verbesserung durch die EventDrivenSimulation


    Event Driven Simulation, Critical Event Scheduling:
    Schaltungen auf unterschiedlichen Abstraktionsebenen und mit Zeitinformation
    Die Idee ist es, algorithmische Blöcke durch Threads zu verwalten. Nur die Systemteile werden neu berechnet, deren Eingaben sich verändert haben (anstehende Ereignisse=Events). globale Datenstruktur: EventQueue, Scheduler übernimmt die Verwaltung
    - Hier: Spezialfall einer Event Driven Simulation für Schaltkreise
    - Ereignisse/Events sind änderungen von Signalwerten zu bestimmten Zeitpunkten
    - Ein Event in der Form (s, v, t), wobei (Signal, Signalwert ∈ {0, 1}, Zeitpunkt ∈ N)
    Die Event-Queue speichert eine nach Zeitpunkten sortierte Liste
    der anstehenden Ereignisse. Beispiel einer Event-Queue:




    - Um bei Eintreten eines Events (s, v, t) die Simulation weitertreiben zu können, muss man
    wissen, welche Gatter gerade auf das Event warten.
    - Das sind alle Gatter, die s als Eingang haben. Diese Gatter warten sensitiv auf Events auf s.
    - Zu jedem Signal s gibt es also eine Liste waiting(s) aller Gatter, die s als Eingang haben.
    - Ein Event auf s löst evtl. Events auf den Ausgangssignalen der Gatter aus waiting(s) aus.
    While (time <= endtime AND Eventqueue != empty) {
    time = min({timestamps in Eventqueue})
    while ( Eventqueue != empty AND (s,v,time) = e aus Eventqueue) {
    entferne e aus Eventqueue
    führe e aus, d.h. Weise Wert v an Signal s zu
    if (dadurch Signalwert geändert) {
    trage alle Gatter aus waiting(s) in Gatteraktivierungsliste ein}
    }
    while (Gatteraktivierungsliste != empty) {
    entferne erstes Element g aus Gatteraktivierungsliste
    führe Gatterberechung durch (berechne v(g), Ausgangssignal s(g) mit Verzögerung d(g)
    füge (s(g), v(g), time + d(g)) in Eventqueue ein
    }
    }

    Annahme:
    Anfangs haben alle Signale des Wert X (d.h. Unbekannt).
    Alle Und-Gatter haben Verzögerung von einer Zeiteinheit.
    Simuliere Eingangsvektor (0, 0, 0, 0, 0, 0) zum Zeitpunkt 0,
    - d.h. initialisiere Eventqueue E = {(a, 0, 0), (b, 0, 0), ..., (f, 0, 0)}
    - time = min({timestamps in E}) = min({t | (s,v,t) aus E}) = 0
    - Gatteraktivierungsliste G = {g1, g2, g3}
    - Eventqueue E = {(j,0,1), (g,0,1), (h,0,1)}
    - time = 1
    - G = {g4, g5}
    - E = {(o,0,2), (k,0,2)}
    - time = 2
    - G = {g5}
    - E = {(o,0,3)}
    - E = G = {}

    Beispiel2: Simuliere nun Eingangsvektor (1, 1, 0, 0, 0, 0) zum Zeitpunkt 5,
    - E = {(a, 1, 5), (b, 1, 5), (c, 0, 5), (d, 0, 5), (e, 0, 5), (f, 0, 5)}
    - time = 5
    - G = {g1}
    - E = {(j,1,6)}
    - time = 6
    - G = {g5}
    - E = {(o,0,7)}
    - G = {}

    Beobachtungen:
    - Event Driven Simulation hat den Vorteil, dass unnötige Gatterauswertungen vermieden werden (Beispiel 2).
    - Gatter werden aber evtl. auch mehrmals ausgewertet (Beispiel 1: g5).
    - Das ist interessant bei der Analyse von Spikes (siehe übung).
    - Evtl. uninteressant bei Simulation für synchrone Schaltwerke. In dem Fall interessiert man sich nur für die resultierende stabile Belegung.⇒ hier evtl. doch Streamline Code Simulation
    - Warum Trennung zwischen Abarbeitung der Eventqueue und Gatteraktivierungsliste in jedem
    Simulationszyklus?
    1. Gatter können in einem Zyklus mehrfach zur Aktivierungsliste hinzugefügt werden (effizienz)
    2. Es wird erzwungen, dass gerade erst ausgelöster events erst im nächsten Zyklus abgearbeitet
    werden, also in topologischer Reihenfolge (auch bei Delay 0)
    - Event Driven Simulation kann auch mit Gatterverzögerung 0 durchgeführt werden.
    - In aufeinanderfolgende Simulationszyklen können dann Events mit gleichen Zeitpunkten
    abgearbeitet werden.
    - Hierbei ergeben sich zwei Zeitachsen: Simulationszeit, Deltazeit (delta delay)
    Events der gleichen Simulationszeit, die in unmittelbar aufeinanderfolgenden Simulationzyklen
    abgearbeitet werden, sind ¬Ądurch ein delta delay voneinander getrennt¬ď.
    Durch diese ereignisbasierte Simulationstechnik ergeben sich zwei Zeitachsen, welche?
    Simulationszeit, Delatzeit: Enstehehen weil mehrere Ereignisse zur gleichen Simulationszeit ablaufen
    - Event Driven Simulation lässt sich verallgemeinern von Schaltkreissimulation auf allgemeinere
    Szenarien, z.B. Simulation von Hardwarebeschreibungssprachen wie VHDL mit



    Google MSN Suche
    << Start | Studium | Poolmgr | Tanzen | GPG | Impressum >>
    Matthias Bernauer