Entwurf und Validierung paralleler Systeme

Fragen & Lösung

Anforderungen und Anforderungsanalyse

1.

Beschreiben Sie den Zweck der Analysephase.

  • Aufwand abschätzen
  • benötigte Komponenten/Dienste ermitteln
  • Spezifikation
  • Machbarkeitsanalyse

2.

Welchen Zwecken kann die Machbarkeitsstudie (feasability analysis) dienen? Geben Sie ein technisches und ein nichttechnisches Argument an.

  • Lohnt sich das Projekt bzw. Vergleich Aufwand/Gewinn
  • techn. : vorhandene Teillösungen (bestehende Hardware)
  • ökono. : Fertigungskosten

3.

Worin unterscheiden sich die Verhaltensbeschreibungen die in der Analyse und der Entwurfsphase erstellt werden?

  • in der Analysephase:
    • meist textuell
    • nich sehr detailiert
    • HW und SW nicht getrennt
  • Entwurfsphase
    • Benutzung von speziellen Werkzeugen (FSM, State-Charts usw.)
    • Problembezogen
    • Einteilung der Teillösungen auf HW und SW

4.

Beschreiben Sie die typischen Anforderungen an die Steuerung eines Dampferzeugers.

  • eher langsamer Prozeß
  • nicht unbedingt EZ-fähig (außer für komplexe Optimierung)
  • Sensoren für den Ablauf benötigt
  • stark analoger Prozeß
  • geringe Abtastraten
  • eventuell komplexe Berechnungen

5.

Beschreiben Sie die typischen Anforderungen an ein ABS-System.

  • sollte Ausfallsicher und Fehlerresistent sein
  • eher digitaler Prozeß
  • sollte EZ-fähig sein
  • hohe Abtastraten
  • wenig Rechenaufwand

Verhaltensbeschreibungen

1.

Spezifizieren Sie die Bearbeitung eines Finite Impulse Response (FIR)-Filters gegeben durch die Funktion out(n) = c1 * in(n) + c2 * in(n-1) + c3 * in(n-2) durch einen Datenflussgraphen (DFG). Skizzieren Sie eine mögliche direkte Realisierung in Hardware (Register-Transfer-Ebene) mit maximaler Parallelität. Bestimmen Sie die nötigen Taktzyklen für die Berechnung eines Ausgangswertes unter der Annahme, dass eine Multiplikation fünf Zeiteinheiten und eine Addition eine Zeiteinheit benötigt.

  • 5+1=6 Taktzyklen für einen Durchlauf

2.

Beschreiben Sie dasselbe Problem durch ein Programm (Pseudo-Code). Bestimmen Sie die nötigen Taktzyklen unter den selben Annahmen wie oben, d.h. den gegebenen Taktzyklen für Multiplikation und Addition.

  • Load&Store vernachlässigt
  • jede Operation hat max. 2 Operatoren
  • Größe der einzelnen Werte vernachlässigt
Schritt Takte (gesamt) Takte (einzeln) Befehl
1 0 5 MUL_1: A=c1*in(n)
2 5 5 MUL_2: B=c2*in(n-1)
3 10 5 MUL_3: C=c3*in(n-2)
4 15 1 ADD: D=A+B
5 16 1 ADD: D=D+C
17

3.

Identifizieren Sie die Mechanismen für Kommunikation zwischen Prozessen und vergleichen Sie diese.

  • Bedingungen
    • Bool Typ, für Verzweigungen
  • Timeouts
    • Bool Typ, für Verzweigungen
  • Signale
    • für Verzweigungen, kann verschiedene Werte haben
  • RPC
    • kann Daten beinhalten
  • Exception Handling
  • FIFO
  • Rendez-Vous (CSP, Communicating Sequential Processes)
  • Shared memory
    • non desructive reads

4.

Wozu dient Nichtdeterminismus von Automaten bei der Spezifikation von Systemen und ihrer Umgebung?

  • einfache Modellierung unbekannter Zustände (bzw. Systemen mit unbekannten Zuständen)
  • Vereinfachung komplexer Systeme

5.

Ermitteln Sie den DFG für eine gegebene Funktion (z.B. f(x,y,z) = (6y + 7) + 4y (z + 4x)).

6.

Skizzieren Sie die wichtigsten Unterschiede zwischen Statecharts und SDL.

Statecharts SDL
immer Taktgesteuert
Änderungen in verschiedenen Tiefen immer zur selben Zeit
Zeitlich unterschiedliche Änderungen
nur Zustandsbasiert kann auch einzelne Befehle/Codezeilen veranschaulichen

7.

Wozu dienen Message Sequence Charts (MSC)? In welchen Phasen des Entwicklungsprozesses werden MSCs eingesetzt.
Begründen Sie ihre Antworten.

  • Datenaustausch und beteiligte Komponenten kennzeichenen
  • Analyse, Entwurf, Validierung
    • Details der SDL

8.

Beschreiben Sie den Unterschied zwischen reaktiven und transformatorischen Systemen.

reaktiv
  • eingebettetes System reagiert auf äußere Signale der Umwelt (bzw. des übergeordnetten Systems)
  • sollte in EZ geschehen
  • übergeordnettes System gibt die Geschwindigkeit vor
  • fast alle Embedded Systems
transformatorisch
  • von der Laufzeit entkoppelt
  • z.B. Numerische Berechnungen

9.

Spezifizieren Sie verschiedene Zustandsautomaten mit Statecharts (z.B. aus den Praktikas bekannte Automaten wie Spindelsteuerung, Kassenautomat, Kreuztisch, etc.).

10. SystemC

  • a. Beschreiben Sie kurz den Design-Flow mit SystemC.
  • b. Nennen Sie die SystemC-Prozesstypen und vergleichen Sie diese.
  • c. Erstellen Sie eine Header-Datei eines Moduls mit Ein-/Ausgabeports, 2 Signalen und einem der möglichen Prozesse in SystemC-Syntax.
a.
  1. System Spezifikationen
    SystemC
  2. Hardware- Software Partitionierung
  3. Hardwareentwurf durch schrittweise Verfeinerung der Spezifikation
    Softwareentwurf
  4. Hardwaresynthese (Place and Route)
    Softwareentwurf (Kompilation)
  5. Hardware
    Software
b.
  • Method
    • tritt immer bei bestimmten Ereignissen ein
    • vollständige Bearbeitung des Prozesses
  • Thread
    • eventgetriggert
    • mehrere Zustände innerhalb des Prozesses
  • Clocked Thread
    • Wie Thread, aber Triggerung durch Takt
c.
#include "system.h"
struct dff: sc_module {
  sc_in<bool>  din;
  sc_in<bool>  clock;
 
  sc_out<bool> dout;
 
  sc_signal<int> signal_1;
  sc_signal<int> signal_2;
 
  void doit();
 
  struct dff: sc_ctor {
    struct doit : sc_method;
    sensetive_pos<<clock;
  }
}

11. VHDL

  • a. Benennen Sie die Grundelemente einer VHDL-Beschreibung?
  • b. Welches Sprachkonstrukt wird für parallele Beschreibungen verwendet?
    Erläutern Sie die prinzipielle Syntaxstruktur dieser Anweisung.
  • c. Benennen Sie die Haupteigenschaften der VHDL-Erweiterung AMS? Beschreiben Sie die damit verbundenen neuen Sprachelemente.
a.
  • Librarys
  • Port/Schnittstellenbeschreibung
  • Architecture
    • Prozessen
b.
  • process <name> begin <Anweisungen> end process
    • <name> - Prozessname
    • <Anweisungen> - Sequentielle VHDL Anweisungen im Process
c.
  • Analog Mixes Signals
  • neue Sprachelemente:
    • Terminals
      • contribution
        Fluß in Komponente als Quantity wiedergeben
      • reference
        Differenzgröße bezogen zur Referenz der Natur
    • Nature
    • Branch Quantities
    • Quantities
    • Simultaneous Statements

Funktionale Validierung

1.

Worin unterscheidet sich die Validierung durch Simulationen von der Validierung durch Tests?

  • bei einer Simulation wird ein Modell des kompletten Systemes mit Testwerten gefüttert und ausgewertet
  • bei einem Test wird das reale System mit Testwerten geprüft

2.

Erläutern Sie die Begriffe Vollständigkeit und Widerspruchsfreiheit.

  • Vollständig heißt, dass alle eintretenden Zustände und Zustandswechsel definiert sind
  • bei Widerspruchsfreiheit gibt es nicht für gleiche Zustände verschiedene Wechsel

3.

Worin unterscheidet sich die Validierung mittels Model Checking von der Validierung der Vollständigkeit.

Model Checking
  • ist das System Bestandteil der Defenition
  • Semantik
  • Techniken, die
    • verifizieren ob ein gegegenes System eine gegebene Spezifikation erfüllt
    • automatisch arbeiten
    • entweder die Korrektheit des Systems bzgl der Spezifikation feststellen oder ein Gegenbeispiel liefern, d.h. eine Ausführung , die die Spezifikation verletzt
Vollständigkeit

4.

Spezifizieren Sie Zustandsautomaten mit SMV (z.B. aus den Praktikas bekannte Automaten für Spindelsteuerung, Kassenautomat, Kreuztisch, etc.). Formulieren Sie mittels CTL verschiedene Bedingungen an das System.

CTL
  • Computation Tree Logic

FIXME

Validierung temporaler Eigenschaften

1.

Erläutern Sie das Prinzip der Schedulability-Analyse von periodischen Systemen mit unterbrechenden Prioritäten mittels der Analyse der Antwortzeiten.

Schedulability-Analyse von periodischen Systemen
  • preemtive (Tasks mit niedriger Priorität werden unterbrochen)
  • je kürzer die Periode, desto höher die Priorität
  • best case
Analyse der Antwortzeiten
  • Verarbeitungszeit wird mit einbezogen
  • worst case

2.

Erläutern Sie die Vor- und Nachteile der simulativen Leistungsbewertung.

Vorteile
  • kann bereits im Entwurf benutzt werden
  • wenig Kosten, da virtuell
  • worst- und best-case
Nachteile
  • eventuell fehlende Events beim Input
  • wenn das Modell zu abstrakt ist fehlen vielleicht wichtige Eigenschaften

3.

Welche Leistungsbewertungsansätze eignen sich besonders für Systeme mit deterministischen bzw. mit exponentiell verteilten Ankünften und Bedienzeiten.

FIXME

4.

Spezifizieren Sie die Markov-Kette für ein Bediensystem mit 2 Bedieneinheiten und einer gemeinsamen Warteschlange mit 3 Warteplätzen. Die Ankunftsrate λ und die Bedienzeiten µ der beiden Server sind jeweils exponentiell verteilt.
Skizzieren Sie die Lösung der Markov-Kette für den stationären (eingeschwungenen) Fall.

Zustand Rechner 1 Rechner 2 Queue
0 frei frei frei
1 belegt frei frei
2 belegt belegt frei
3 belegt belegt 1
4 belegt belegt 2
5 belegt belegt 3

5.

Warum liefern Verfahren zur Bestimmung von Antwortzeiten in der Regel weniger genaue Ergebnisse als Verfahren zur Bestimmung der Auslastung?

Antwortzeit
  • ungenaue Vorhersage der Antwortzeiten (durch Unterbrechung usw.)
Auslastung
  • wie viele Prozesse werden gerade bearbeitet

6.

Nennen Sie Argumente zur Bewertung von Leistungsaspekten in den frühen Entwurfsphasen.

  • Aufwand/Nutzen Abschätzungen (event. reichen langsamere Realisierungen)
  • ist die Aufgabe überhaupt lösbar
  • eventuell auftretende Nebenbedingungen

7.

Prüfen Sie die Einhaltung der Deadlines für folgende Menge von auf einem Prozessor betriebenen voneinander unabhängigen, periodischen Prozessen (Deadlines entsprechen den Perioden) unter den zwei angegebenen Prioritätsschemata

Prozess Periode T Rechenzeit C a) Priorität b) Priorität
0 7 3 3 1
1 12 3 2 2
2 20 3 1 3

Bestimmen Sie die Schedulability soweit möglich mit verschiedenen Methoden (utility- based und response-time-based).

Seite 22-24, Evaluation of Temporal and Performance Aspects

utility- based
  • ist der Prozessor überlastet?
response-time- based
  • wird in der Periode der Prozess fertig

Optimierungsverfahren

1.

Ermitteln Sie den Taskgraphen (DFG) für eine gegebene Funktion (z.B. f(x,y,z) = (6y + 7) + 4y (z + 4x)) (siehe oben). Bestimmen Sie die Ablaufpläne (Mapping und Schedule) für den obigen Taskgraphen nach den in der Vorlesung besprochenen Listenschedulingverfahren (HLFET, SCFET). Gehen Sie davon aus, dass 2 “Prozessoren” zur Verfügung stehen, die beliebige Operationen durchführen können. Die Addition dauert eine Zeiteinheit, die Multiplikation 4 Zeiteinheiten.

DFG

Ablaufpläne
process co-levels priority estimated time
MUL_4 3 4
MUL_3 7 4
MUL_2 5 4
MUL_1 4 4
ADD_3 1 1
ADD_2 2 1
ADD_1 6 1

FIXME

  • HLFET (highest level first with estimated times)
Schedule
P1 MUL_3 ADD_1 MUL_4 ADD_3
P2 MUL_2 MUL_1 ADD_2
t 0 1 2 3 4 5 6 7 8 9 10
  • SCFET (smallest co-level first with estimated times)
Schedule
P1 MUL_3 ADD_1 MUL_4 ADD_3
P2 MUL_2 MUL_1 ADD_2
t 0 1 2 3 4 5 6 7 8 9 10

2.

Lösen Sie dasselbe Problem mit einem Verfahren zur sukzessiven Verbesserung einer Anfangslösung, z.B. Tabu Search.

FIXME

3.

Konstruieren Sie zwei Taskgraphen so, dass bei einem Taskgraphen HLFET und beim anderen SCFET die besseren Ergebnisse liefert.

FIXME

4.

Skizzieren Sie einen Vorschlag zur Erweiterung von Listenscheduling bei nicht vernachlässigbaren Kommunikationskosten zwischen Tasks, die auf verschiedene Prozessoren zugeordnet sind.

FIXME

5.

Konstruieren Sie Beispiele für die Ablaufplanung bei denen Listenschedulingverfahren zu keiner gültigen Lösung führen.
Hinweis: Betrachten Sie HW-Architekturen, bei denen die Prozessoren nicht vollständig verbunden sind.

FIXME

6.

Skizzieren Sie die Anwendung der folgenden Verfahren zur HW/SW-Partitionierung:

  • a. Hill Climbing
  • b. Genetische Algorithmen
  • c. Simulated Annealing
  • d. Tabu Search
  • e. Clusteringverfahren
  • f. Branch-and-Bound

Ziel der Optimierung ist die Minimierung der Antwortzeit als auch der Kosten der Hardwarekomponenten.

FIXME

7.

Mit welchen Mittel lösen die verschiedenen besprochenen heuristischen Optimierungsverfahren das Problem lokaler Optimas?

FIXME

High-level Synthese

1.

Beschreiben Sie die Unterschiede zwischen high-level Synthese und der RTL-Synthese.

high-level
  • Realisierungsmöglichkeit egal (egal, welche Bausteine benutzt werden)
  • abstrakte Sicht (nur die Funktion ist von Intresse)
  • Taktunabhängig
  • RTL kann durch Compiler/Generatoren erzeugt werden
RTL
  • Register bezogen
    • Datenpfad
      • DFG
    • Sequence-Pfad
      • CFG
  • Taktbezogen

2.

Ermitteln Sie den DFG für eine gegebene Funktion (s.o.). Bestimmen Sie die Ablaufpläne (Mapping und Schedule) nach den verschiedenen in der Vorlesung besprochenen Strategien (ASAP, ALAP, Varianten für List Scheduling) unter verschiedenen Annahmen für die Allokation (d.h. die Anzahl der verfügbaren Resourcen (Multiplizierer, Addierer) und deren Taktzyklen).

Mapping

FIXME

Schedule

FIXME

 
wiki/study/evps.txt · Last modified: 2005/09/22 16:28 (external edit)
 
Except where otherwise noted, content on this wiki is licensed under the following license:CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki