PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Materialintegrierte Sensorische Systeme

Mit Labor @home

PD Stefan Bosse

Universität Bremen - FB Mathematik und Informatik

1 / 91

PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Eingebettete Systeme und Datenverarbeitung

Wie kann die Datenverarbeitung unter Randbedingungen von material-integrierten Systemen erfolgen?

Vom Mikrocomputer zum Nanocomputer

Virtualisierung auch im Material!

Programmierung

2 / 91

Rechnerarchitektur PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Rechnerarchitektur

Computersystemarchitekturen. Implementierungsebenen kommunizieren vertikal über die gezeigten Schnittstellen. (Nach Glenford Myers, 1982

3 / 91

Materialinformatik PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Materialinformatik

Bedeutung:

  1. Rechnen in Materialien (Verteilte Datenverarbeitung in Materialien)
  2. Rechnen von Materialien (Data Science, KI, .., um neue Materialien zu entwickeln)
  • Normalerweise wird die Berechnung von Sensorerfassung und Steuerung getrennt

  • Smarte Materialien stellen die enge Verbindung zwischen

    • Berechnung,
    • Kommunikation,
    • Sensorerfassung und
    • Steuerung mit lose gekoppelten Nano-Computern dar.
4 / 91

Materialinformatik PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Materialinformatik

  • Algorithmische Skalierung und Verteilung sind erforderlich

    • Verteilte Systeme können als eine große Maschine behandelt werden
  • Mooresches Gesetz sagte starke Miniaturisierung voraus

  • Jedoch die Informatik und deren Methoden konnten nicht immer folgen → Lücke zwischen Hardware und Software

5 / 91

Materialinformatik PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Materialinformatik

Eine normalisierte Recheneffizienz eines Computers (nur unter Berücksichtigung der Datenverarbeitungseinheit) kann definiert werden durch:

ϵC=CAP

A
Chipfläche in mm2
C
Rechenleistung in Mega Instructions per Second (MIPS) - oder besser in Kilo Dhrystones/s (KDS)!
P
Elektrische Leistungsaufnahme in W
6 / 91

Materialinformatik PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Die Recheneffizienz kann verwendet werden, um verschiedene Computer und Geräte zu vergleichen, d.h. einen Skalierungsfaktor anzugeben:

s=ϵ1ϵ2

7 / 91

Materialinformatik PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Materialinformatik

  • Neben der reinen Rechenleistung sind noch Speicher und Kommunikationsfähigkeit einer Rechneranlage wichtige Kenngrößen, so dass sich zwei weitere normierte Recheneffizienzen ergeben:

ϵCM=CMAP

ϵCMD=CMDAP

M
Gesamter Speicher in Mega Bytes (MB), beinhaltet RAM, ROM, Register
D
Gesamte Kommunikationsfähigkeit als Datendurchsatz (Mega Bit/s)!
8 / 91

Materialinformatik PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Materialinformatik

Maßzahlen der Rechenleistung

  • Einfachste Maßzahl ist die Anzahl der Integer- oder Fliesskommaoperationen pro Zeiteinheit (MIPS/FLOPS)
    • Aber nur der eigentliche Kern des Mikroprozessors wird dabei erfasst - Speicher, Speicherhierarchie und Kommunikationsfähigkeit fehlen
  • Ein Programm besteht i.A. aus den folgenden High-level Operationen:
    • Berechnung (skalar, vektoriell)
    • Speicherallokation, Objekterzeugung (Code und Daten)
    • Funktionsaufrufe
    • Erzeugung, Zugriff, und Freigabe verschiedener Objekte mit unterschiedlichen "Speicherabdruck": Arrays, Strings, Records, Funktionen, Methodische Objekte mit Prototypen (Klassen)

Dhrystone Benchmark umfasst alle oben genannten Operationen!

9 / 91

Materialinformatik PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Materialinformatik

Chip Fläche

H Normierte Maßzahlen für die Chip Fläche (A/rbe)

10 / 91

Materialinformatik PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Materialinformatik

Chip Fläche

H Normierte Maßzahlen für die Chip Fläche von Speicher (A/rbe)

11 / 91

Materialinformatik PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Materialinformatik

Chip Fläche

H Normierte Maßzahlen für die Chip Fläche von Prozessoren (A/rbe)

12 / 91

Materialinformatik PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Materialinformatik

Chip Fläche

H Normierte Maßzahlen für die Chip Fläche von FPGAs (A/rbe)

13 / 91

Materialinformatik PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

H Zusammenhang der Technologiegröße -math[f] (Fertigungsauflösung/Transistordimension) mit der normierten Fläche A

14 / 91

Materialinformatik PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Materialinformatik

  • Hitachi entwickelte bereits 2006 einen 0.15 x 0.15 Millimeter großen, 7.5 μm dicken Microchip der:
    • Drahtlose Kommunikation und Energieversorgung via RFID → (2.45 GHz Mikrowelle) ermöglichtet, einen
    • 128 Bit ROM Speicher, und einen
    • einfachen Mikroprozessor enthielt.

Es geht noch kleiner → Smart Dust reloaded (by Hitachi)

15 / 91

Materialinformatik PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Materialinformatik

Aufgabe

  1. Mache eigene Messungen mit dem dhrstone benchmark Test auf verschiedenen Rechnern und Virtuellen Maschinen.

  2. Stelle eine Tabelle zusammen mit gängigen Computern (mobil, Desktop, Server, eingebettete Rechner, Nanorechner) mit den Daten MIPS/DPS, Speicher, Kommunikation (abgeschätzt) sowie Chip Fläche und el. Leistungsbedarf

  3. Berechne die verschiedenen ε Parameter und vergleiche ...

16 / 91

Entwurf Eingebetteter Systeme PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Entwurf Eingebetteter Systeme

Softwareentwurf

Entwurfsebenen von Eingebetteten Systemen auf Softwareebene

17 / 91

Entwurf Eingebetteter Systeme PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Entwurf Eingebetteter Systeme

  • Der Entwurf Eingebetteter Systeme geht immer mehr Richtung Hardware-Software Co-Design und System-on-Chip Architekturen

Entwurfsebenen von Eingebetteten Systemen auf Hardwareebene

18 / 91

Rechnersysteme PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Rechnersysteme

  • Man unterscheidet folgende Kategorien von Rechnern:
    1. Stationäre Geräte: Server
    2. Stationäre Geräte: Desktop
    3. Mobile Geräte: Notebook
    4. Mobile Geräte: Smartphone
    5. Stationäre und mobile Eingebettete Systeme: Einplatinencomputer und Microcontroller
    6. System-on-Chip Geräte: Einchipcomputer und Microcontroller
19 / 91

Rechnertechnologien PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Rechnertechnologien

Existierende "Nano"-Computer:

  • Smart Dust → Vision Millionen lose gekoppelter Nano-Computer
    • Eingebettet in Materialien
    • Auf Oberflächen verstreut
    • Dispergiert in Flüssigkeiten, Folien, ..
    • ungefähr 10mm3 Volumen

Micro Mote M3

ELM System

20 / 91

Rechnertechnologien PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Rechnertechnologien

Existierende Kleinstrechner für Sensornetzwerke mit Drahtloskommunikation (WLAN, Bluetooth)

Raspberry PI Zero

  • 32-bit RISC ARM Prozessor
  • 512MB RAM, 16GB ROM
  • 1W
  • 70x30mm

ESP8266

  • 32-bit RISC Tensilica Xtensa Diamond Standard
  • 128kB RAM, 16MB ROM
  • 0.15W
  • 30x20 mm

21 / 91

Rechnertechnologien PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Rechnertechnologien

Micro Mote (M3 ) ELM System Atmel Tiny 20 Freescale KL03 ARM Cortex Smart Phone
Processor Arm Cortex M0 C8051F990 (SL) AVR Arm Cotex M0+ Arm Cortex A9
Clock 740kHz max. 32kHz - 48MHz 1GHz
CPU Chip Area 0.1mm2 9mm2 1mm2 4mm2 7mm2/ROM
Memory 3-4kB 0.5kB/2-8kB - 2kB/40kB 512MB/4GB
Sensors Temperature - - - Temp, Light, Sound, Accel., Press., Magn.
Communication 900MHz radio, optical optical electrical - 3G/4G, WLAN, USB, Bluetooth, NFC
Harvester, Battery Solar cell, Thin film Solar cell, Coin - - -
Power Consumption 70mW / CPU 160mW / CPU 20mW 3mW @ 48MHz 100mW avg., 2W peak @ 1.5GHz
Manufacturing 180nm CMOS - - - 40nm CMOS
Package Wire bonded Silicon Stack PCB Single Chip Single Chip , PCB
Computing Eff. εC 150 0.02 0.6 4.0 0.53
22 / 91

Rechnertechnologien PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Rechnertechnologien

Smart Dust

  • Kommunikation: Optisch, Laser, LED
  • Energieversorgung: Optisch, Fotozelle
  • Energiespeicher: Dünnfilmbatterie
  • Sensorik: Temperatur, Licht

Smart Dust: Warneke et al., 2001 Aufbau einer Smart Dust Mote

23 / 91

Rechnernetzwerke PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Rechnernetzwerke

Von großen Computern zu großen Netzwerken ...

  • Ursprünglich wurden Software- und Betriebssysteme auf Computern mit hoher Rechenleistung und Speicherkapazität ausgeführt.
  • Die Integration von Berechnung in technische Strukturen oder Geräte erfordert das Herunterskalieren von Algorithmen und Methoden in Richtung auf verteilte Verarbeitungsnetzwerke mit Plattformen mit geringen Ressourcen.

Skalierung und Miniaturisierung [Smart Dust: Warneke et al., 2001]

24 / 91

Rechnertypen PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Rechnertypen

  • Rechner und Mikroprozessoren unterscheiden sich u.A. durch die Art und Weise der Maschinenbefehlsausführung
  • Man unterscheidet: Reduced Instruction Set Computer (RISC) und Complex Instruction Set Computer (CISC)
    • RISC: Maschinenbefehle arbeiten häufig mit Registern (Anzahl Register groß)
    • CISC: Maschinenbefehle arbeiten häufig mit dem Speicher (Anzahl der Register klein)
    • Eingebettete Systeme verwenden i.A. RISC (Aufgabe: Warum?)
  • Es gibt Maschinenbefehle mit einer unterschiedlicher Anzahl von Operanden (0,1,2,3,..)
  • Neben register- und speicherbasierten Rechnern gibt es reine stackbasierte Rechner (Nulloperandenbefehle)
    • Alle Operationen werden über den Stapelspeicher ausgeführt
25 / 91

Rechnertypen PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Rechnertypen

Rechnereinteilung nach Adressanzahl: gezählt wird die Anzahl Operanden eines dyadischen Operators (z.B. einer Addition) [C]

26 / 91

Programmierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Programmierung

Randbedingungen

Die Programmierung eingebetteter Systeme stellt aufgrund folgender Randbedingung eine Herausforderung dar:

  1. Geringe Rechnenleistung pro Netzknoten

  2. Geringe Speicherkapazität von Daten

  3. Bei energieautarken Systemen gibt es eingeschränkte Laufzeit

  4. Geringe Kommunikationsleistung

  5. Fehleranfälligkeit

  6. Schlechte Wartbarkeit (Softwareupdates usw.)

  7. Eingeschränkte Möglichkeiten der Fehlersuche

27 / 91

Programmierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Programmierung

Programmiersprachen

  • Assembler → Maximale Performanz, minimalste Zuverlässigkeit/Korrektheit (Fehler), minimalster Speicherbedarf, kein automatisches Speichermanagement
  • C/C++ → Sehr gute Performanz, geringer Speicherbedarf, und mittlere Zuverlässigkeit/Korrektheit (Fehler), kein oder minimales automatisches Speichermanagement → Prozedurale Programmierung
  • JAVA → Mittlere Performanz, hoher Speicherbedarf, gute Zuverlässigkeit/Korrekheit (Fehler), automatisches Speichermanagement → Objektorientierte Programmierung
  • Skriptsprachen → Unterschiedliche Performanz, wird durch Interpreter bestimmt, automatisches Speichermanagement
    • Python (schlechte Performanz)
    • JavaScript (mittlere oder gute Performanz, evtl. hoher Speicherbedarf)
    • Lua (mittlere oder gute Performanz, niedriger Speicherbedarf)
28 / 91

Programmierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Programmierung

Performanz und Speicherbedarf bei Skriptsprachen hängen vom Interpreter ab!

  • JavaScript: Google V8 (Bytecode+Just-in-time native code Compiler), Jerryscript (Bytecode)
  • Lua (Bytecode) und Luajit (Bytecode+Just-in-time native code Compiler)

Bytecode. Der Bytecode ist eine Sammlung von Befehlen für eine virtuelle Maschine.

  • Bei der Kompilierung eines Quelltextes mancher Programmiersprachen oder Umgebungen, wie beispielsweise Java, wird nicht direkt Maschinencode, sondern ein Zwischencode, der Bytecode, erstellt.
  • Dieser Code ist in der Regel unabhängig von realer Hardware. Er entsteht als Resultat einer semantischen Analyse des Quelltexts und ist im Vergleich zu diesem oft relativ kompakt und wesentlich effizienter interpretierbar als der originale Quelltext [Wikipedia].
29 / 91

Programmierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Programmierung

  • Reine Bytecode Interpreter haben geringe oder mittlere Performanz bei niedrigen Speicherbedarf

    • Der Bytecode wird entweder vollständig aus dem Quelltext beim Start eines Programms erzeugt, oder
    • Der Bytecode wird stückweise nach Bedarf aus dem Quelltext zur Laufzeit erzeugt
  • Ein JIT Compiler übersetzt häufig vorkommende Bytecode Abschnitte zur Ausführungszeit in nativen Maschinencode

    • Das ergibt erhöhte Ausführungsperformanz, benötigt aber mehr Speicher
  • Vorteile von Skriptsprachen gegenüber kompilierten Programmen: Schneller Test, ausführliche und genaue Rückmeldung vom Interpreter bei Fehlern, bessere Laufzeitüberwachung von Fehlern, ...

30 / 91

Programmierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Programmierung

Ausführungsplattform für Eingebettete Systeme

  • Daher ist eine zweistufige Architektur sinnvoll:
    • Virtuelle Maschine programmiert in C (hohe Portabilität) und ggfs. Assembler, mit integrierten Compiler, die Bytecode ausführt und bei Bedarf Bytecode in nativen Maschinenkode umwandelt (JIT)
    • Skriptsprache (in diesem Kurs Lua) die im Quelltext von der virtuellen Maschine ausgeführt wird
  • Virtualisierung durch die VM von:
    • Prozessor (Instruction Set Architecture, ISA)
    • Speicher, automatisches Speichermanagement
    • Ein- und Ausgabegeräten (Geräte)
    • Kommunikation
31 / 91

Programmierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

  • Warum nicht JAVA?
    • Hoher Speicherbeadarf
    • Nur objektorientierte Programmierung, nicht immer effizient
    • Kein Interpreter: Compiler und VM sind getrennt
32 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Virtualisierung

Eine prozessvirtuelle Maschine, die Programme ausführen kann, die für ein anderes Betriebssystem und eine andere ISA entwickelt wurden: Die Virtualisierungssoftware bildet eine Plattform auf eine andere ab, und übersetzt eine Reihe von Betriebssystem- und Benutzerebenenbefehlen. [A]

33 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Virtualisierung

Compiler

http://doc.gold.ac.uk Klassischer Softwareentwurf mit Compiler und Linker (C)

34 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Virtualisierung

Interpeter

Edit - Compile - Execute Zyklus bei einem Interpreter

35 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Virtualisierung

Bytecode Interpreter

  • Die Übersetzung des Quelltextes in Bytecode kann vor und während der Ausführung des Programms erfolgen!

Vergleich Interpreter mit Bytcode Compiler-Interpreter System

36 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Virtualisierung

Serialisierung

  • Da Bytecode unabhängig von der Hostplattform sein sollte, kann Bytecode einfach von einer Maschine zu einer anderen übertragen und ausgeführt werden

  • Dazu ist eine Serialisierung von Daten und Code erforderlich (Flache Liste von Bytes), mit anschließender Deserialisierung (Wiederherstellung der Daten- und Codestruktur)

  • Neben vollständig binär kodierten Bytecode ist Text eine Unterklasse. Beispiel: JavaScript, JSON

37 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Peter Cawley Serialisierung in einer Bytecode VM

38 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Virtualisierung

JIT Compiler

  • Neben der Bytecode Ausführung kann während der Laufzeit des Programms der Bytecode stückweise optimiert werden → Erzeugung von Maschinencode durch einen Just-in-Time Compiler (JIT)

Vergleich Interpreter mit JIT Compiler-Interpreter Systeme

39 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Virtualisierung

Aufgabe

  1. Überlegen Sie sich die Vor- und Nachteile von

    • Compilern
    • Interpretern
    • Bytecode Interpretern
    • JIT Compiler und Interpreter
  2. Was sind die Bewertungskriterien?

  3. Welche Ausführungsarchitekturen könnten für Eingebettete Systeme geeignet sein?

40 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Virtualisierung

  • Rechenleistung, Speicherbedarf, und Ein-Ausgabe Durchsatz/Latenz sind wichtige Metriken für den Einsatz in Eingebetteten Systemen

B Typische Datenverarbeitungsebenen in Eingebetteten Systemen und Virtualisiering

41 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Virtualisierung

Perfomanz von Interpretern

Dhrystone Benchmark (Kombination aus Berechnung, Objekten, Arrays, Strings, Funktionen)

VM/OS-ARCH Linux-i686 Linux-armv6l (PI-3B) Linux-armv6l (PI Zero)
python2.71 105k/s 23k/s 4k/s
lua 5.12 140k/s 36k/s -
luajit 2.0.5X/lvm2 660k/s 108k/s 40k/s
jerryscript 1.1.7X3 45k/s - -
nodejs/V8-43 6300k/s 879k/s 40k/s
C/gcc 18000k/s 3700k/s ?

(1: Python, 2: Lua, 3: JavaScript)

42 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Virtualisierung

Speicherbedarf von Interpretern

Dhrystone Benchmark (Kombination aus Berechnung, Objekten, Arrays, Strings, Funktionen)

VM/OS-ARCH Linux-i686 Linux-armv6l (PI-3B) Linux-armv6l (PI Zero)
python2.7 - - -
lua 5.1 - - -
luajit 2.0.5X/lvm 2MB 2MB -
jerryscript 1.1.7X 2MB - -
nodejs 4/10 24MB 32MB -
C/gcc 1MB ? ?
43 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Virtualisierung

Automatisches Speichermanagement

  • In C/C++ muss für jedes zur Laufzeit dynamisch erzeugte Datenobjekt (Array, String, Record, ..) immer explizit Speicherplatz im Hauptspeicher angefragt werden (malloc) und wieder frei gegeben werden wenn das Datenobjket nicht mehr benötigt wird (free)

  • In Skriptsprachen gibt es i.A. ein automatisches Speichermanagement mit einem sog. Garbage Collector und Objektreferenzierung

  • Jedes Datenobjekt welches verwendet wird (z.B. in Variablen oder Funktionen) besitzt eine Referenz

  • Es muss eine Wurzeltabelle geben von der aus alle Referenzen auf verwendete Objekte auffindbar sind

44 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

var o1 = { a=1, b={1,2,3,4} }
var o2 = { op = o1, index=2 }
function show () print (o2.op.a } end; show()

Beispiel von Objektreferenzierungen in Lua: Wo existieren Referenzen?

45 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Virtualisierung

Verschiedene Objekte: Objekte die nicht mehr referenziert sind, werden freigegeben

46 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Virtualisierung

Speicherarchitektur von Programmen

  • Code: Enthält nur Programmcode (aber auch mit statischen Daten)
  • Heap: Datenobjekte mit längerer Lebensdauer (Tabellen- oder Listenstruktur) → Benötigt Speichermanagement
  • Stack: Datenobjekte mit kurzer Lebensdauer (Stapelstruktur) → Benötigt kein Speichermanagement

Speicherarchitektur von Rechnern

  • Speicherhirarchie durch Cache Systeme
47 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Speicherhierarchie von Programmen und Zusammenhang mit Maschinenanweisungen

48 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Virtualisierung

Speicherorganisation von Virtuellen Maschinen

49 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Virtualisierung

Speicher

  • Die meisten Objekte in Programmiersprachen benötigen Speicher

    • Lokale, temporäre, und globale Variablen
    • Objekte
    • Arrays
    • Zeichenketten
    • Funktionen (!)
  • Der Kontext von Speicherobjekten ist wichtig:

    • Modul → limitierte Programmsichtbarkeit
    • Lokal → stark limitierte Programmsichtbarkeit
    • Global → uneingeschränkte Sichtbarkeit
50 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Virtualisierung

  • Beispiele: Die globale Variable Xglobal ist überall, auch außerhalb des Definitionsmoduls, sichtbar, die Variable xlokal ist im gesamtem Modul und den Funktionen f1 und f2 sichtbar, wo hingegen xlokal1 und xlokal2 jeweils nur ihrem Funktionskontext sichtbar sind.
Xglobal = 1
local xloakal = 2
function f1 ()
local xlokal1 = 3
end
function f2 ()
local xlokal2 = 3
end
  • Nur wenn Variablen bei der Ausführung sichtbar sind belegen sie Speicher!
51 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Virtualisierung

  • Ein Teil des Speicher ist vorbelegt:

    • Globale Variablen
    • Funktionen, ausführbarer Code, ...
  • Ein anderer Teil des Speichers wird zur Laufzeit auf dem Stack und Heap belegt und benötigt Verwaltung:

    • Lokale und temporäre Variablen, ..
    • Funktionen, ausführbarer Code, ...
  • Achtung: Bei Programmiersprachen bei denen Funktionen Werte erster Ordnung sind befindet sich auch Code im Heap oder auf dem Stack

52 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Virtualisierung

Speicherverwaltung

Listen
Freie und belegte Speicherbereiche werden durch Listen (einfach- oder doppelt verkettet) verwaltet
Tabellen
Tabellen (Hashtabellen) werden zur Speicherverwaltung verwendet
Manuelle Verwaltung
Speicherbelegung explizit vom Programmierer und teils vom Compiler auszuführen

Vorteile

  • Optimale Speicherbelegung (tatsächlich naiv und falsch) und Performanz/Effizienz
53 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Nachteile

  • Speicherlecks (nicht mehr benötigter Speicher wird nicht frei gegeben)
  • Mehrfachfreigabe (Inkonsistenz der Speicherverwaltung)
  • Benutzung von Speicherobjekten nach Freigabe
54 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Virtualisierung

Automatische Verwaltung
Die Freigabe von Speicherbereichen wird automatisch durch einen Garbage Collector durchgeführt. Dieser bestimmt auch automatisch ob Speicherobjekte noch benötigt werden.

Vorteile

  • Speicherlecks werden vermieden
  • Keine Mehrfachfreigabe (Inkonsistenz der Speicherverwaltung)
  • Keine Benutzung von Speicherobjekten nach Freigabe

Nachteile

  • Nicht optimale Speicherbelegung und schlechtere Performanz/Effizienz
55 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Garbage Collection

  • Wie soll der GC heraus finden ob ein Objekt noch benötigt wird?
    1. Referenzzähler wird jedem Objekt hinzugefügt und bei jeder neuen Referenzierung erhöht (Allokation). Ein Objekt mit Referenzwert Null kann frei gegeben werden.
  1. Der GC rechnet Objektabhängkeiten aus und markiert Objekte die freigegeben werden können
  • Beispiel von Referenzen und Sichtbarkeit (Programmkontext)
local o1 = { x=100,y=200 }e1 [e1.ref=1(o1)]
local o2 = { pos=o1, color="red" }e2 [e1.ref=2(o2,o1)]
function draw (o)
local o3 = { pos=o.pos, color="white" }e3 [e3.ref=1(o3), e1.ref=4(o3,..)]
local o4 = { pos={x=o.pos.x,y=o.pos.y}e4, color="black" } [e1.ref=5(o4,o4,..)]
draw(o3)
draw(o4)
→ [e3.ref=0, e4.ref=0, e1.ref=3, e2.ref=2]
end
draw(o2) [e2.ref=2(o,o2), e1.ref=3(o,o2,o1)]
o2=nil [e2.ref=0, e1.ref=1(o1)]
o1=nil [e1.ref=0]
56 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

  • Wichtig: Referenzzähler beziehen sich auf Werte (ei), nicht auf die Variablen selber (die nur Zeiger auf Werte besitzen)
    • D.h. wenn ein Wert als Referenz an eine weitere Variable zugewiesen wird erhöht sich der Referenzzähler!
57 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Virtualisierung

GC: Referenzzählung

  • Wenn ein Objekt erzeugt wird, wird der Referenzzähler auf Null gesetzt
  • Jede weitere Referenzierung erhöht den Zähler um eins (also bereits das zuweisen eines Objektes an eine variable!)
  • Wird eine Referenzierung vom Objekt entfernt (explizit → =null, oder implizit durch Entfernen des referenzierenden Objektes), dann wird der Zähler um eins erniedrigt
  • Ist der Zähler wieder Null, dann wird der Speicher freigegeben

Nachteile

  1. Zyklische Referenzen können nicht aufgelöst werden:
local o1 = { x=100,y=100 }
local o2 = { prev=o1 }
o1.next = o2
58 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Virtualisierung

  1. Daher werden u.U. nicht alle Objekte freigegeben → Speicherlecks
  2. Der Referenzzähler belegt selber Speicher (gehört zum Objekt). Bei low-resource Plattformen wird z.B. eine Datenwortbreite von 16 Bit für den Zähler verwendet, und der maximale Referenzwert ist 65536 (jerryscript ist so ein Kandidat)!
  3. Allokation ist langsamer (verlangsamt Zuweisung)

Vorteile

  1. Einfach zu implementieren
  2. Freigabe ist effizient (wenig Rechenaufwand)
59 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

GC: Mark & Sweep

  • Bestimmte Objekte sind direkt zugänglich, und es muss herausgefunden werden welche Objekte erreichbar sind → Graphensuche

  • Es gibt einen Stammsatz von Speicherplätzen im Programm, dessen Objekte bekanntermaßen erreichbar sind.

60 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Virtualisierung

Mark-and-Sweep verläuft in zwei Phasen

Markierungsphase

  • Erreichbare Objekte suchen:
    • Der Stammsatz wird zu einer Arbeitsliste hinzugefügt
    • Solange die Arbeitsliste nicht leer ist wird ein Objekt von der Liste entfernt. Wenn es nicht markiert ist, markiere es als erreichbar und alle Objekte die davon aus erreichbar sind werden zur Arbeitsliste hinzugefügt.

Sweepphase

  • Für alle belegten Objekte:
    • Ist das Objekt nicht markiert so lösche es (Speicher freigeben)
    • Ist das Objekt markiert, lösche die Markierung
61 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Virtualisierung

Vorteile

  1. Auch zyklische Referenzen können über die Arbeitsliste aufgelöst werden
  2. Alle Objekte können frei gegeben werden
  3. Allokation schnell

Nachteile

  1. Rechenintensiv und langsam!!
62 / 91

Virtualisierung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Beispiel eines M&S Durchlaufes mit anschließender Freigabe von nicht mehr erreichbaren == benötigten Objekten

63 / 91

Multitasking PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Multitasking

  • Auf einem Rechnerknoten gibt es eine Vielzahl von Aufgaben die bearbeitet werden müssen:

    • Sensorverarbeitung
    • Kommunikation
    • Steuerung
  • Zum Teil müssten Aufgaben parallel verarbeitet werden → Multitasking → Parallelisierung → Nur bedingt möglich → Task Scheduling

64 / 91

Echtzeitverarbeitung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Echtzeitverarbeitung

  • Echtzeitverarbeitung bedeutet die Ausführung eines Tasks innerhalb eines vorgegebenen Zeitintervalls [t0,t1]
    • Soft Realtime: Zeitüberschreitung bei weicher Echtzeitanforderung → Tolerierbar
    • Hard Realtime: Zeitüberschreitung bei harter Echtzeitanforderung → Systemfehler

B Echtzeitspektrum: Wiche und harte Echtzeitanforderungen bei unterschiedlichen Applikationen

65 / 91

Echtzeitverarbeitung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Echtzeitverarbeitung

B Periodische, sporadische, und aperiodische Tasks

66 / 91

Echtzeitverarbeitung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Echtzeitverarbeitung

Preemption

  • Wenn schon nicht alles Tasks gleichzeitig verarbeitet werden können, dann wenigstens die wichtigsten vorrangig ausführen

  • Das erfordert aber:

    • Festlegung einer Priorität
    • Bei Echtzeitanforderungen die Unterbrechung von unterlegenen (kleiner Priorität) Tasks
67 / 91

Echtzeitverarbeitung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

B Unterschied preemptive und nicht preemptive Ausführung von Tasks

68 / 91

Parallele Datenverarbeitung und Prozesse PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Parallele Datenverarbeitung und Prozesse

Ebenen der parallelen Datenverarbeitung

69 / 91

Parallele Datenverarbeitung und Prozesse PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Parallele Datenverarbeitung und Prozesse

  • Ein Prozess ist die dynamische Ausführung eines Programms
  • Der Zustand (Mikrobene) eines Prozesses ist durch den Datenzustand aller (privaten) Prozessvariablen, globaler Variablen, und dem Kontrollzustand (Instruktion) bestimmt

Man unterscheidet folgende Prozessklassen:

Task
Ein Task T ist die kleinste Einheit und i.A. ein Teil einer Berechnung und eines Prozesses. Man unterscheidet fein und grob granulierte Tasks. Wenige Anweisungen und wenig Rechenlast bedeuten feine Granularität. Parallele Datenverarbeitung wird durch konkurrierende Ausführung von Tasks auf verschiedenen Prozessoren erreicht.
Prozesse
Der eigentliche Prozesse ist von allen anderen Prozessen stark entkoppelt und gesichert (lose Kopplung). Die Erzeugung eines Prozesses ist rechenintensiv → schwergewichtige Prozesse. Prozesse können parallel ausgeführt werden.
70 / 91

Parallele Datenverarbeitung und Prozesse PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Parallele Datenverarbeitung und Prozesse

Threads
Leichtgewichtige Subprozesse eines Prozesses mit mittlerer Kopplung (Datenaustausch zwischen Threads ist direkt möglich). Die Erzeugung eines Threads ist weniger rechen- und speicherintensiv. Threads können parallel ausgeführt werden.
Fibers
Sehr leichtgewichtige Prozesse mit starker Kopplung die in Threads oder Prozessen ausgeführt werden. Die Erzeugung von Fibers ist optimal. Fibers werden i.A. nicht parallel ausgeführt und daher sequenzielle und verschachtelt ausgeführt.
71 / 91

Parallele Datenverarbeitung und Prozesse PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Scheduling

Die Ausführung von Prozessen (Threads) kann parallel auf mehreren Datenverarbeitungseinheiten (Prozessoren) geschehen → Parallele Datenverarbeitung

  • Häufig ist aber die Anzahl der Prozess N größer als die Anzahl der Prozessoren P
72 / 91

Parallele Datenverarbeitung und Prozesse PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Parallele Datenverarbeitung und Prozesse

  • Dann müssen Prozesse die rechenbereit sind hintereinander ausgeführt werden → Scheduling
  • Ein Prozess kann mittels der Operationen suspend und resume blockiert oder wieder lauffähig gemacht werden

C Grobe Sicht des zeitlichen Ablaufs (Ein- und Multiprozessorsystem)

73 / 91

Parallele Datenverarbeitung und Prozesse PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Parallele Datenverarbeitung und Prozesse

Sequenzielle und parallele Ausführung

C Darstellung paralleler Abläufe (Beispiele)

74 / 91

Parallele Datenverarbeitung und Prozesse PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Parallele Datenverarbeitung und Prozesse

C Varianten der Software-Parallelität mit Prozessen, Threads, und Fibers

75 / 91

Parallele Datenverarbeitung und Prozesse PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Parallele Datenverarbeitung und Prozesse

  • Bei der parallelen (und verteilten) Datenverarbeitung soll es eine Beschleunigung der Rechenzeit im Vergleich zum rein sequenziellen Verarbeiten geben
  • Aber es gibt auch in parallelen Systemen immer sequenzielle Anteile die die Beschleunigung S reduzieren

Begrenzung der maximalen Beschleunigung eines parallelen Systems bei einem bestimmten sequenziellen Anteil (in %): Amdahlsches Gesetz (N: Anzahl der Prozesse und Prozessoren)

76 / 91

Prozesse PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Prozesse

Prozesszustände

Ein Prozess kann sich in verschiedenen Ausführungszuständen (Makroebene) befinden:

New
Ein Prozess wird erzeugt und der Code und Daten aus einer Datei gelesen
Ready/Ready Suspended
Der Prozess ist rechenbereit (ausführungsbereit), aber wird noch nicht vom Prozessor ausgeführt
Running
Der Prozess wird von einem Prozessor ausgeführt (Ein Prozessor oder Prozessorkern kann immer nur einen Prozess ausführen)
Waiting/Blocked/Suspended
Der Prozess wartet auf ein Ereignis (Daten, Zeitintervall, Ressource frei, usw.). Man unterscheidet u.U. Blockierung und Suspendierung (Details: Art und Weise der Blockierung)
77 / 91

Prozesse PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Prozesse

C Grundmodell mit drei Zuständen

78 / 91

Prozesse PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Prozesse

Übergangsdiagramm von Prozesszuständen (Details)

79 / 91

Prozesse PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Prozesse

Prozessblockierung

  • Ein rein sequenzielles Programm wird solange schrittweise ausgeführt bis die letzte Anweisung verarbeitet wurde

  • Prozessblockierung bedeutet das Anhalten eines Prozesses an einer bestimmten Stelle im Programmfluss mit späterer Ausführung an genau dieser unterbrochenen Stelle!

80 / 91

Parallele Datenverarbeitung und VMs PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Parallele Datenverarbeitung und VMs

  • Da Virtuelle Maschine i.A. ein automatisches Speichermanagement besitzen ist schwierig oder ineffizient eine VM mit einem gemeinsamen Heap und VM Zustand zwischen Threads zu teilen

    • Gefahr der Dateninkonsistenz
    • Alternativ Schutz durch Mutualen Ausschluss bei jeglicher Art der Speicherverwaltung → Aber: Ständig wird Speicher verwaltet (in jeder Anweisung!)
  • Daher wird folgendes parallele Ausführungsmodell bei VMs gewählt:

    • Jeder Thread führt eine eigen VM aus (mit eignen GC, Heap, und Zustand)
    • Kommunikation zwischen Threads über einen seriallisierten gemeinsamen Speicher (Store), über den Daten ausgetauscht werden können
81 / 91

Parallele Datenverarbeitung und VMs PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Parallele Datenverarbeitung und VMs

Das parallele Ausführungsmodell der LUAJIT UV VM (lvm)

82 / 91

Asynchrone Ereignisverarbeitung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Asynchrone Ereignisverarbeitung

  • Neben der Parallelisierung der reinen Datenverarbeitung (Berechnung) kann auch eine Partitionierung von Ein- und Ausgabe bzw. der Ereignisverarbeitung erfolgen

  • Bekanntes Beispiel: Geräteinterrupts mit einfachen Foreground-Background System mit zwei Prozessen:

    • P1: Hohe Priorität (Ereignisverarbeitung → Interrupthandler → Foreground Prozess)
    • P2: Niedrige Priorität (Berechnung → Hauptprogramm → Background Prozess) mit Preemption durch Ereignisverarbeitung
  • Ein- und Ausgabeoperationen eines Programms können synchron (blockierend) oder asynchron (im Hintergrund verarbeitet und nicht blockierend) ausgeführt werden.

83 / 91

Asynchrone Ereignisverarbeitung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Asynchrone Ereignisverarbeitung

Beispiel Lua

  • Synchrone Operationen liefern das Ergebnis in einer Datenanweisung zurück die solange blockiert wird bis das Ereignis eintritt(Ergebnisdaten verfügbar sind). Dabei werden zwei aufeinander folgende Operationen sequenziell ausgeführt, und eine folgende Berechnung (nicht ereignisabhängig) erste nach den Ereignissen ausgeführt:
x = IO1(arg1,arg2,..)
y = IO2(arg1,arg2,..)
z = f(x,y)
84 / 91

Asynchrone Ereignisverarbeitung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

  • Bei der asynchronen (nebenläufigen) Ausführung von ereignisabhängigen Operationen wird das Ergebnis über eine Callback Funktion verarbeitet. Die IO Operation blockiert nicht. Vorteil: Folgende Berechnungen können unmittelbar ausgeführt werden.
IO1(arg1,arg2,..,function (res) x=res end)
IO2(arg1,arg2,..,function (res) y=res end)
z = f(x,y) -- Problem?
85 / 91

Asynchrone Ereignisverarbeitung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Asynchrone Ereignisverarbeitung

Ereignisbasierte Verarbeitung von asynchronen Operationen in node.js/jxcore: Ein JS Thread verbunden über die Eventloop mit N IO Threads

86 / 91

Asynchrone Ereignisverarbeitung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Asynchrone Ereignisverarbeitung

Synchronisation

  • Asynchrone Ereignisverarbeitung mit preemptiven Verhalten benötigt explizite Synchronisation (Locks...) zur Atomarisierung von kritischen Bereichen

  • Asynchrone Ereignisverarbeitung spaltet den Datenfluss auf und benötigt Daten- und Ergebnissynchronisation über Prädikatsfunktionen oder explizite Synchronisation:

local x,y,z
function P(f,x,y,z)
if x = nil and y = nil then
return f(x,y)
else return z end
end
IO1(arg1,arg2,..,function (res) x=res; z=P(f,x,y,z) end)
IO2(arg1,arg2,..,function (res) y=res; z=P(f,x,y,z) end)
```
87 / 91

Digitale Signalverarbeitung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Digitale Signalverarbeitung

Digitalisierung als erste Stufe der Signalverarbeitung

  • Die AD-Wandlung setzt i.A. ein Frequenzfilter (Tiefpass) am Eingang voraus, mit dem der zu erfassende Spektralbereich des Signals begrenzt wird. In der sog. Sample&Hold-Schaltung wird das analoge Signal zeitdiskretisiert, und anschließend mit dem eigentlichen AD-Wandler in einen diskreten i.A. binärkodierten Digitalwert umgesetzt.

Digitale Signalverarbeitung als zweite Stufe

  • Die Eingangsdaten stehen als kontinuierlicher Datenstrom für die weitere Verarbeitung zur Verfügung. Ein Eingangsdatenstrom wird in einen Ausgangsdatenstrom transformiert.
88 / 91

Digitale Signalverarbeitung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Erzeugung analoger Signale als dritte Stufe

  • Die DA-Wandlung kann nur ein quasi-analoges Signal (immer noch zeit- und wertdiskret!) erzeugen. Eine ”Zeit- und Wertglättung” findet hier ebenfalls unter Verwendung eines Tiefpass-Frequenzfilters statt
89 / 91

Digitale Signalverarbeitung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Digitale Signalverarbeitung

DSP Architektur

90 / 91

Zusammenfassung PD Stefan Bosse - MISS - Modul A: Eingebettete Systeme und Datenverarbeitung

Zusammenfassung

Bei der Materialintegration von Berechnung (Materialinformatik) findet ein Übergang von Mikro- zu Nanorechnern mit starken Einschärnkung hinsichtlich Rechenleistung und Speicher statt

Bei der Bewertung von Rechnern sind jetzt auch Chipfläche und Energiebedarf zu berücksichtigen

Virtualisierung kann auf vielen Ebenen erfolgen und ist auch in einem Sensorknoten und Netzwerk wünschenswert

Aber eine Virtuelle Maschine erzeugt einen "Overhead": Erhöhter Rechenbedarf (gerade Speichermanagement) und Speicherbedarf

Ein- und Ausgabeoperationen können synchron (blockierend) oder asynchron (und parallel) ausgeführt werden. Letztere Methode bedarf besonderere Programmierung mit Prädikatfunktionen.

91 / 91