Real-Time and Embedded Systems

Seminar Synchrone Sprachen

Sinn dieses Seminars ist es, sich mit einem Themengebiet intensiv und selbständig wissenschaftlich auseinanderzusetzen. Das Thema ist in einem mündlichen Vortrag und einer schriftlichen Ausarbeitung zusammenzufassen. Ein weiterer Sinn dieses Seminars ist es, das Arbeiten in strukturierten zeitlichen Abläufen zu praktizieren, wie es z.B. für Workshops/Tagungen üblich ist. Beide Aspekte sind erfahrungsgemäß eine gute Vorbereitung auf die Anfertigung einer Abschlussarbeit.

 

Dieses Seminar wird in zwei Varianten angeboten, als Bachelor-Modul (Inf-Sem-Echtz, Univis-Eintrag, Modulbeschreibung) und als Master/Diplom-Modul (MSS1101, Univis-Eintrag, Modulbeschreibung). Im Vergleich zum Bachelorseminar erwartet das Masterseminar eine größere Einbeziehung von verwandten Arbeiten, und dementsprechend eine umfangreichere Ausarbeitung und Präsentation (siehe unten).

Voraussetzungen:

Eine Teilnahme an der Vorlesung Synchrone Sprachen (zuletzt gehalten im WS 2011/12) ist von Vorteil, aber nicht zwingend erforderlich. Papiere, welche auch ohne Teilnahme an der Vorlesung Synchrone Sprachen zugänglich sein sollten, sind in der Liste unten entsprechend gekennzeichnet.

Für Diplomstudierende ist das Vordiplom Voraussetzung für die Teilnahme am Seminar.

Dozenten:

Reinhard v. Hanxleden (rvh), Christian Motika (cmot)

Termine (vorläufig):

Di, 14.2. 12:00 Uhr, R1118 Erste Vorbesprechung
Do, 12.4. 9:50 Uhr, R1304b Zweite Vorbesprechung, Kick-Off
Mi, 18.04. 12:00 Uhr Frist für Themenauswahl (per Mail an Dozenten)
Do, 19.4. 10:00 Uhr, R1118 LaTeX / GIT Kurzeinführung
Mo, 30.4. 12:00 Uhr Abgabe Ausarbeitungsgerüst (Abstract, Einleitung, Gliederung, Stichworte, Bibliographie)
Do, 3.5. R1117 Individualtermine, für Terminabsprache bitte Dozenten ansprechen
Di, 29.05. 12:00 Uhr Abgabe Erstversion der vollständigen Ausarbeitung
Do, 31.5. R1117 Individualtermine, für Terminabsprache bitte Dozenten ansprechen
Mo, 11.06. 12:00 Uhr Abgabe Vortragsfolien und Handoutfolien (siehe unten)
Do, 14.6. R1113 Individualtermine, für Terminabsprache bitte Dozenten ansprechen
Mo, 18.6. 12:00 Uhr Abgabe der Review-Version der Ausarbeitung
Mo, 18.6. 18:00 Uhr Zuordnung Ausarbeitungen/Reviewer (per E-Mail)
Mo, 25.6. 12:00 Uhr Abgabe der Reviews
Mo, 9.7.
verlängert
12:00 Uhr

Abgabe der Endversion der Vortragsfolien und der Ausarbeitung, anschließend Druck der Proceedings (incl. Ausarbeitungen und Vortragsfolien).
Mi, 18.7. 9:00 Uhr Blockseminar mit Vorträgen im Ü2


Agenda des Workshops - Mittwoch, 18.07.2012, Ort: Ü2

>>> Proceedings <<<

9:00 - 9:10

Begrüßung

9:10 - 9:55

Protothreads: Simplifying Event-Driven Programming of Memory-Constrained
Embedded Systems (Sven Oliver Reimers) 
9:55 - 10:40


Effiziente Ausführung von Kahn Prozessnetzwerken auf Mehrprozessorsystemen
durch Nutzung von Protothreads und Windowed FIFOs (Tibor Toepffer)

10:40 - 11:00
 
Kaffeepause

11:00 - 11:30      Logical Time: Spezifikation vs. Implementierung (Markus Waurisch) 
11:30 - 12:15 Compiling Esterel for Multi-Core Execution (Wahbi Haribi) 

12:15

 Mittagessen

 

Seminarthema

In diesem Seminar werden wir uns, in Fortführung der Vorlesung "Synchrone Sprachen" im Wintersemester 11/12, mit aktuellen Forschungsarbeiten zur synchronen Programmierung beschäftigen. Die synchronen Programmiersprachen Esterel und Lustre werden dazu eingesetzt, reaktive Programme für eingebettete und/oder Echtzeitsysteme zu schreiben. Ein wichtiges Merkmal dieser Sprachen ist eine klare, formal definierte Semantik. Diese erleichtert sowohl die Verifikation von Programmen, als auch die weitergehende automatische Verarbeitung von Programmen.

Nachfolgend ist eine Liste von Papieren, welche jeweils als individuelle Grundlage einer Seminarteilnahme genommen werden können. Insbesondere bei Diplom-/Masterstudierenden und bei weniger umfangreichen Papieren wird erwartet, dass noch eine begrenzte Zahl weiterer, thematisch verwandter Papiere hinzugezogen wird.

Für die Themenvergabe gilt first come, first served. Bereits vergebene Themen sind mit einem entsprechenden Hinweis versehen.

BITTE BEACHTEN: Einige Paper sind nur aus dem Institutsnetz frei zugänglich!

Papiere, welche auch ohne Besuch der Vorlesung "Synchrone Sprachen" zugänglich sein sollten:

The clock constraint specification language for building timed causality models - Application to synchronous data flow graphs
Frédéric Mallet, Julien DeAntoni, Charles André, Robert de Simone,
Innovations in Systems and Software Engineering (ISSE) 6(1-2):99-106 (2010)

SystemJ: A GALS language for system level design. Computer Languages
Avinash Malik, Zoran Salcic, Partha S. Roop, Alain Girault,
Systems & Structures (CL) 36(4):317-344 (2010)

Logical time: specification vs. implementation
Frédéric Mallet, Charles André, Robert de Simone,
ACM SIGSOFT Software Engineering Notes (SIGSOFT) 36(1):1-8 (2011)
Vergeben an: Markus Waurisch (mwa)

Efficient execution of Kahn process networks on multi-processor systems using protothreads and windowed FIFOs
Wolfgang Haid, Lars Schor, Kai Huang, Iuliana Bacivarov, Lothar Thiele,
Proceedings of the 7th IEEE/ACM/IFIP Workshop on Embedded Systems for Real-Time Multimedia 2009:35-44
Vergeben an: Tibor Toepffer (tit)

Predictable multithreading of embedded applications using PRET-C
Sidharta Andalam, Partha S. Roop, Alain Girault,
8th ACM/IEEE International Conference on Formal Methods and Models for Codesign 2010:159-168


Protothreads: simplifying event-driven programming of memory-constrained embedded systems
Adam Dunkels, Oliver Schmidt, Thiemo Voigt, Muneeb Ali,
Proceedings of the 4th International Conference on Embedded Networked Sensor Systems 2006:29-42
Vergeben an: Sven Oliver Reimers (sor)

GALS-JOP: A Java Embedded Processor for GALS Reactive Programs
Muhammad Nadeem, Morteza Biglari-Abhari, Zoran Salcic,
IEEE Ninth International Conference on Dependable, Autonomic and Secure Computing (DASC), 2011

LibGALS: a library for GALS systems design and modeling
Wei-Tsun Sun, Zoran Salcic, Avinash Malik,
Proceedings of the 15th Asia South Pacific Design Automation Conference (ASP-DAC) 2010:107-112 

Papiere, für welche sich ein vorheriger Besuch der Vorlesung "Synchrone Sprachen" empfiehlt:

The Coroutine Model of Computation (PDF on request)
Chris Shaver,
EECS 219D Class Project,  Department of Electrical Engineering & Computer Sciences, UC Berkeley (2011)

From Concurrent Multi-clock Programs to Deterministic Asynchronous Implementations
Dumitru Potop-Butucaru, Yves Sorel, Robert de Simone, Jean-Pierre Talpin,
Fundam. Inform. (FUIN) 108(1-2):91-118 (2011)

Compiling Esterel for Multi-core Execution
Simon Yuan, Li Hsien Yoong, Partha S. Roop,
14th Euromicro Conference on Digital System Design (DSD)  2011:727-735
Vergeben an: Wahbi Haribi (wah)

Schizophrenia and causality in the context of refined clocks
Mike Gemunde, Jens Brandt, Klaus Schneider,
Forum on Specification & Design Languages (FDL) 2011:1-8

On relational interfaces
Stavros Tripakis, Ben Lickly, Thomas A. Henzinger, Edward A. Lee,
International Conference on Embedded Software (EMSOFT) 2009:67-76

Proposal for a Dynamic Synchronous Language
Pejman Attar, Frédéric Boussinot, Louis Mandel, Jean-Ferdy Susini,
INRIA, Research Proposal, 2011

Static analysis of synchronous programs in signal for efficient design of multi-clocked embedded systems
Abdoulaye Gamatié, Laure Gonnord,
Conference on Languages, compilers, and tools for embedded systems (ACM SIGPLAN/SIGBED), LCTES 2011:71-80

Synchronous control of reconfiguration in fractal component-based systems: a case study
Tayeb Bouhadiba, Quentin Sabah, Gwenaël Delaval, Éric Rutten,
International Conference on Embedded Software (EMSOFT) 2011:309-318

A hybrid synchronous language with hierarchical automata: static typing and translation to synchronous code
Albert Benveniste, Timothy Bourke, Benoît Caillaud, Marc Pouzet,
Proceedings of the 11th International Conference on Embedded Software (EMSOFT) 2011:137-148

Grundlagen:

Ein Teil der Seminararbeit ist eine eigenständige Literaturrecherche, die folgenden Quellen dienen somit nur als Einführung in das entsprechende Thema:

  • Nicolas Halbwachs, Synchronous programming of reactive systems, a tutorial and commented bibliography, Tenth International Conference on Computer-Aided Verification, CAV'98, Vancouver (B.C.), LNCS 1427, Springer Verlag, June 1998
  • Gerard Berry, The Foundations of Esterel, Proof, Language and Interaction: Essays in Honour of Robin Milner, G. Plotkin, C. Stirling and M. Tofte, editors, MIT Press, Foundations of Computing Series, 2000
  • Reinhard v. Hanxleden, Modellierung Reaktiver Systeme - Statecharts und Synchrone Sprachen, in: Peter Liggesmeyer and Dieter Rombach (Hrsg.), Software Engineering für Eingebettete Systeme, Spektrum Akademischer Verlag, 2005
  • Lokale Webseite zur Esterel-Programmierumgebung


Ausarbeitung, Vortrag, Review

Das Seminar beinhaltet die Erstellung einer Ausarbeitung, eines Vortrags, und zweier Reviews. Gute Vorbilder für Ausarbeitung und Vortragsfolien sind in den Proceedings der früheren Seminare zu finden.

Die Ausarbeitung soll eine Übersicht über das behandelte Themengebiet darstellen. Sie sollte so verfasst sein, dass sie von einen fortgeschrittenen Bachelor-Informatikstudenten gut verstanden werden kann. Die Ausarbeitung soll 6 (Master/Diplom) bzw. 4 (Bachelor) Seiten umfassen, nicht mehr und nicht weniger, und den ACM Style verwenden. Für mögliche Vorlagen zu den Ausarbeitungen siehe die Proceedings der früheren Seminare. Auch empfehlenswert ist ein Blick in die Hinweise für die Anfertigung einer Abschlussarbeit.

Der Vortrag soll 40 Minuten (Master/Diplom) bzw. 25 Minuten (Bachelor) lang sein. Das Vortragsprogramm wird etwas zusätzliche Zeit für Fragen (5 min) einplanen. Zu dem Vortrag sollen aussagekräftige Folien erstellt werden, mit LateX Beamer (siehe unten). Die Vortragsfolien sollten Seitennummern enthalten. Sollte das Thema auch eine konkrete Implementierung behandeln, ist eine entsprechende kurze Tool-Demo im Rahmen des Vortrages sinnvoll. Die Arbeitsgruppe bietet jedem/r Vortragenden an, eine Videoaufnahme des Vortrags zu erstellen und dem/r Vortragenden anschließend zur Verfügung zu stellen.

Ein Review einer Ausarbeitung besteht aus einer elektronisch (z.B. mit Xournal) annotierten PDF-Version der Review-Version der Ausarbeitung. Die Annotationen bestehen aus:

  1. Generellen Anmerkungen (mind. 1/2 Seite) - was gefällt Ihnen/gefällt Ihnen nicht, zu Inhalt, Gliederung, Lesbarkeit, sowie generellen Verbesserungsvorschläge etc., z.B. als Textbox am Anfang des PDFs eingefügt, und
  2. Detaillierteren Korrekturen.

Ein eingescannter, handschriftlich annotierter Ausdruck der Ausarbeitung ist notfalls auch ok, sollte aber vermieden werden. Sollten Sie einen Scanner benötigen und keinen zur Verfügung haben, wenden Sie sich bitte an das Sekretariat der Arbeitsgruppe. Die Zuordnung Paper/Reviewer geschieht kurzfristig nach dem Abgabetermin für die Review-Versionen der Ausarbeitungen, basierend auf den dann abgegebenen Ausarbeitungen.

Namenskonventionen

Auch wenn das Einchecken von generierten Binärdateien generell eher vermieden werden sollte, sind für dieses Seminar auch die folgenden pdfs einzuchecken, um unnötige Compilierungsschwierigkeiten bei Dozenten und Reviewern zu vermeiden. Das Review zu einer Ausarbeitung soll direkt im Zielordner des Autors der Ausarbeitung abgelegt werden. Grafiken sollten in einem Unterordner (z.B. "images") abgelegt werden. Grafiken sollten weiterhin möglichst skalierbare  Verktorgrafiken sein, die als PDF eingebunden werden können. Nicht einzuchecken sind temporäre Dateien (.aux etc.).

Die Namen für die Dateien, die im GIT abzulegen sind, sollen wie folgt (gleichartig) aufgebaut sein. Bitte halten Sie sich von Anfang an an diese Namenskonventionen. Das vermeidet unnötige Sucherei, bewahrt uns vor späteren Schwierigkeiten mit automatischen Skripten und macht umständliches Umbenennen überflüssig.

  • Ausarbeitung: .../teaching/sem/12ss-sync/<login>/sem12ss-<login>.[tex/pdf]
  • Vortragsfolien: .../12ss-sync/<login>/sem12ss-<login>-talk.[tex/pdf]
  • Handoutfolien - ohne Animationen, für Ausdrucke und die Proceedings: .../12ss-sync/<login>/sem12ss-<login>-handout.[tex/pdf]
  • Review: .../12ss-sync/<login>/sem12ss-<login>-review-<reviewer-login>.pdf

Anmerkung: Die Handoutfolien unterscheiden sich von den Vortragsfolien dadurch, dass die Handoutfolien keine Animationen für die Präsentation am Beamer enthalten. Beim Arbeiten mit der latex-beamer Klasse können Handoutfolien durch das Hinzufügen eines optionalen Argumentes bei der Deklaration der Dokumentenklasse generiert werden ("\documentclass[trans]{beamer}").

Weiterhin: Die Reviews sollten vom Autor der Reviews im Verzeichnis der begutachteten Ausarbeitung eingecheckt werden. Also, <reviewer-login> checkt das von <reviewer-login> erstellte Review für die Ausarbeitung von <login> in .../12ss-sync/<login>/sem12ss-<login>-review-<reviewer-login>.pdf ein, und schickt an <login> eine kurze E-Mail mit einem entsprechenden Hinweis, mit CC an den Dozenten.

Benotung

Das Seminar ist benotet. Es werden jeweils Teilnoten für die einzelnen Meilensteine (Versionen der Ausarbeitung, Reviews, Folien, Vortrag) vergeben, aus denen sich die Endnote zusammensetzt. Es werden jeweils die Qualität sowie die Rechtzeitigkeit (siehe Terminplanung) bewertet. Letztlich zählt für die Note also nicht nur das endgültige Resultat (Ausarbeitung/Vortrag) sondern auch der gesamte Prozess, aus dem jenes hervorgegangen ist.

Technisches

  • GIT Repository auschecken: git clone git@git.rtsys.informatik.uni-kiel.de:sem/12ss-sync.git 12ss-sync
  • Texlipse Latex Eclipse Plugin: http://texlipse.sourceforge.net/
    • URL kann direkt als Eclipse update site benutzt werden
    • Bei der Erstellung eines neuen Texlipse Projektes im New-Wizard auf pdf als Ausgabeformat umstellen und pdflatex benutzen (siehe unten)
  • ACM Style in deutscher oder englischer Version (innerhalb des rtsys-Netzwerks auch global verfügbar). Im GIT befinden sich in .../12ss-sync/init/ eine Reihe von Dateien (incl. README.txt), welche Sie als Template nehmen können.
  • Wir benutzen pdflatex (erstellt PDF Dateien) und nicht direkt latex (erstellt DVI Dateien)
    • sind im Prinzip gleich zu benutzen
    • Hauptunterschied ist die Einbindung von Grafiken. In pdflatex siehe z.B. http://latex.mschroeder.net/#grafiken (Es sollte immer eine komplette figure Umgebung mit caption, label und Referenz im Text benutzt werden!)
    • Texlipse unterstützt ein sehr ausführliches "figure" template (irgendwo figure tippen und Strg-Leertaste drücken)
    • Von der Kommandozeile aus kann ein pdf mit "rubber -d sem12ss-<login>" erstellt werden (rubber ruft automatisch pdflatex und bibtex auf).
  • Bibliographie: Siehe ACM Beispiel (hier werden die Bibliographielemente in eine eigene *.bib Datei ausgelagert). Manuell wird dann einmal pdflatex dokument.tex aufgerufen. Dies erzeugt eine dokument.aux Datei. Darauf wird bibtex dokument.aux aufgerufen und dann nochmal zweimal pdflatex dokument.tex. Erst dann sind die Bibliographieelemente richtig im pdf-file.

    • Texlipse ruft pdflatex und bibtex in den richtigen Reihenfolgen automatisch auf.
    • Texlipse unterstützt sehr schöne Templates und Autovervollständigung für Bibliographie: Im *.bib file "@" tippen und Strg+Leertaste drücken, dann bekommt man eine Auswahl aller möglichen Bibliographielemente angezeigt. Entsprechend im .tex-File "\cite{}" Tippen, dort öffnet die Autovervollständigung eine Liste aller vorhandenen bib-Einträge

     

Weiterführende Hinweise / Links