Real-Time and Embedded Systems

Kiel Reactive Processors

Reactive ProcessorsEmbedded real-time systems must react continuously to stimuli from their environment. Therefore, their control-flow patterns differ from those of traditional systems that transform a given input to an output at their own pace. Reactive processors provide direct hardware support for reactive control flow, which keeps executables fast and compact and results in lower power consumption compared to traditional architectures.

The Kiel Esterel Processor (KEP) is a reactive processor that has an instruction set architecture closely resembling the Esterel language, and has direct support for reactive control flow patters such as concurrency and preemption. The following annotated bibliography sketches the evolution of the KEP processor series towards a highly efficient execution platform with predictable real-time behavior for reactive embedded applications. The Kiel Lustre Processor (KLP) is a reactive processor that uses the synchronous dataflow language klp as an input language.

Downloads

  • strl2kasm: the Compiler from Esterel to KEP assembler written by Marian Boldt (See [3] below).
  • kep: the Esterel description of the KEP, written by Malte Tiedje (See [2] below). Note that this is a reimplementation of the KEP, not the original  implementation by Xin Li.
  • kasm2lste: small compiler, to generate opcode from KEP assembler, written by Malte Tiedje.
  • klp: This is an early test stage of the KLP.

 

Links

 

Annotated References

For BibTeX entries and other publications, see the publications page.

  1. Xin Li and Reinhard von Hanxleden. Multi-Threaded Reactive Programming—The Kiel Esterel Processor. IEEE Transactions on Computers, vol. 61, issue 3, pages 337 - 349, March 2012. (pdf)
    The suggested primary reference for the KEP. Expanded, revised from the ASPLOS'06 paper listed below.
  2. Claus Traulsen and Reinhard von Hanxleden. Reactive Parallel Processing for Synchronous Dataflow. In Proceedings of the 25th Symposium On Applied Computing (SAC’10), Special Track Embedded Systems: Applications, Solutions, and Techniques, Sierre, Switzerland, March 2010.
    A description of the Kiel Lustre Processor (KLP), which supports Lustre and SCADE.
  3. Reinhard von Hanxleden and Michael Mendler and Claus Traulsen. WCRT Algebra and Scheduling Interfaces for Esterel-style Synchronous Multi-threading. Technical Report 0807, Christian-Albrechts-Universität Kiel, Department of Computer Science, June 2008. (pdf) An abridged version appeared in the Proceedings of the Design, Automation and Test in Europe (DATE’09), Nice, France, April 2009. (pdf)
    An algebraic framework for formulating the WCRT problem. Reports improved results on the SLAP'07 paper (Boldt et al., see below).
  4. Falk Starke and Claus Traulsen and Reinhard von Hanxleden. Executing Safe State Machines on a Reactive Processor. Technical Report 0907, Christian-Albrechts-Universität Kiel, Department of Computer Science, Kiel, Germany, March 2009. (pdf)
    An approach to directly compile SSMs (a.k.a. SyncCharts) on the KEP.
  5. Malte Tiedje and Claus Traulsen. Designing a Reactive Processor with Esterel v7. In Proceedings of the Workshop on Model-driven High-level Programming of Embedded Systems (SLA++P08), Budapest, Hungary, April 2008. (pdf)
    An extended abstract of Malte Tiedje's diploma thesis, see below.
  6. Malte Tiedje, Beschreibung des Kiel Esterel Prozessors in Esterel. Diploma thesis, Christian-Albrechts-Universität zu Kiel, Department of Computer Science, January 2008. (pdf)
    This documents the Esterel implementation of a slightly modified and trimmed-down version of the KEP. The point of this exercise was 1. to experiment with Esterel v7 for hardware design, in particular processor design, 2. to get a processor model that could be quickly synthesized and simulated (at least compared to VHDL), and 3. to get a nice, big Esterel benchmark. The ultimate goal of having a processor that could simulate itself was not quite reached, but the other objectives were overall achieved. In particular, we now have a processor model with very short design turn-around cycles.
  7. Marian Boldt, Esterel Compiler for a Synchronous Reactive Processor. Diploma thesis, Christian-Albrechts-Universität zu Kiel, Department of Computer Science, December 2007. (pdf)
    A detailed description of the Esterel compiler for the KEP3a. Earlier stages of this compiler are partly documented in the SAC'06 and ASPLOS'06 papers, see below. This thesis expands on this eg by presenting the thread ID assignment scheme and various compiler optimizations.
  8. Xin Li. The Kiel Esterel processor: a multi-threaded reactive processor. Dissertation, Christian-Albrechts-Universität zu Kiel, Faculty of Engineering, July 2007. (pdf)
    The authorative source on the KEP as of mid-2007. Focusses on the architecture/hardware side, also provides the complete instruction set.
  9. Sascha Gädtke and Claus Traulsen and Reinhard von Hanxleden. HW/SW Co-Design for Esterel Processing. In Proceedings of the InternationalConference on Hardware-Software Codesign and System Synthesis (CODES+ISSS’07), Salzburg, Austria, September 2007.
    An extended abstract of Sascha Gädtke's diploma thesis, see below.
  10. Sascha Gädtke, Hardware/Software Co-Design für einen Reaktiven Prozessor. Diploma thesis, Christian-Albrechts-Universität zu Kiel, Department of Computer Science, May 2007 (pdf)
    An extension of the KEP with external combinational logic to speed up the computation of complex signal expressions. One contribution of this paper is a semantics-preserving source-level transformion of Esterel programs that extracts modules (which then get mapped to the external logic).
  11. Xin Li and Reinhard von Hanxleden. Light-Weight, Predictable Reactive Processing—The Kiel Esterel Processor. In Proceedings of the Design, Automation and Test in Europe University Booth (DATE’07) , Nice, France, April 2007. (pdf)
    A two-page overview of the KEP3a, accompanying a KEP-demo at DATE'07, together with a poster that served as a backdrop.
  12. Marian Boldt, Claus Traulsen and Reinhard von Hanxleden. Worst Case Reaction Time Analysis of Concurrent Reactive Programs. In Proceedings of the Workshop on Model-driven High-level Programming of Embedded Systems (SLA++P'07), Braga, Portugal, March 2007. (pdf) The extended journal version: Electronic Notes in Theoretical Computer Science, 203(4):65–79, June 2008. (pdf)
    An approach for the safe (conservative) estimation of the Worst Case Reaction Time (WCRT) of the KEP3a.
  13. Reinhard von Hanxleden, Xin Li, Partha Roop, Zoran Salcic and Li Hsien Yoong. Reactive Processing for Reactive Systems. ERCIM News, Oct. 2006, pp. 28-29. (pdf)
    A short, high-level description of the reactive processing approach, with authors from the Kiel group and from the University of Auckland. The latter have developed the RePIC/EMPEROR/STARPro processor family, another reactive design that also has an ISA closely matching Esterel constructs. Their first design, the REFLIX, predated the KEP and was to our knowledge the very first reactive processor architecture (Salcic et al., FPL 2002). See also the web site on Reactive Processors from Auckland University.
  14. Xin Li, Marian Boldt, and Reinhard von Hanxleden. Mapping Esterel onto a multi-threaded embedded processor. In Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS’06), San Jose, CA, October 21–25 2006. (pdf)
    This paper presents the KEP3a and its compiler. The KEP3a improves over the KEP3 in that it supports exception handling and provides context-dependent preemption handling instructions. The compiler employs a priority assignment approach that makes use of a novel concurrent control flow graph and has a complexity that in practice tends to be linear in the size of the program. Unlike earlier Esterel compilation schemes, this approach avoids unnecessary context switches by considering each thread’s actual execution state at run time. Furthermore, it avoids code replication present in other approaches.
  15. Xin Li and Marian Boldt and Reinhard von Hanxleden. Compiling Esterel for a Multi-Threaded Reactive Processor. Technical Report 0603, Christian-Albrechts-Universität Kiel, Department of Computer Science, May 2006. Revised September 2006. (pdf)
    A more detailed description of the KEP3a and its compiler.
  16. Sascha Gädtke, Xin Li, Marian Boldt, and Reinhard von Hanxleden. HW/SW Co-Design for a Reactive Processor. In Proceedings of the Student Poster Session at the ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES’06), Ottawa, Canada, June 2006. (pdf)
    This paper presents an approach to accelerate reactive processing via an external logic block that handles complex signal expressions. An Esterel program is synthesized into a software component, running on the Kiel Esterel Processor, and a hardware component, consisting of simple combinational logic. The transformation process involves a two-step procedure, which first partitionsthe program at the source level and subsequently performs the synthesis. An intermediate logic minimization, at the source code level, facilitates the synthesis of compact logic blocks.
  17. Xin Li and Reinhard von Hanxleden. A concurrent reactive Esterel processor based onmulti-threading. In Proceedings of the 21st ACM Symposium on Applied Computing (SAC’06), Special Track Embedded Systems: Applications, Solutions, and Techniques, Dijon, France, April 23–27 2006. (pdf)
    The KEP3 was the first truly concurrent KEP. It implements Esterel’s concurrency operator via multi-threading, which scales well to high degrees of concurrency with minimal resource overhead.
  18. Xin Li and Reinhard von Hanxleden. A concurrent reactive Esterel processor based on multi-threading. Technical Report 0509, Christian-Albrechts-Universität Kiel,Department of Computer Science, November 2005. (pdf)
    An expanded description of the KEP3.
  19. Xin Li, Jan Lukoschus, Marian Boldt, Michael Harder, and Reinhard von Hanxleden. An Esterel Processor with Full Preemption Support and its Worst Case Reaction Time Analysis. In Proceedings of the International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES), pages 225–236, New York, NY, USA, September 2005. ACM Press. (pdf)
    The KEP2 improved over the KEP1 (presented at SYNCHRON’04, see below) in that it includes an interface block that supports the PRE-operator, and can handle further Esterel-constructs such as variables and local signals. Furthermore, the KEP2 includes a Tick Manager which can provide a constant logical tick length and detects timing overruns. This paper presents the KEP2 and describes an approach to analyse its Worst Case Reaction Time (WCRT).
  20. Xin Li and Reinhard von Hanxleden. KEP2 (Kiel Esterel Processor 2): The Esterel Processor. Technical Report 0506, Christian-Albrechts-Universität Kiel, Department of Computer Science, April 2005. (pdf)
    This technical report presents the KEP2 in fair detail, including the complete instruction set.
  21. Xin Li and Reinhard von Hanxleden. The Kiel Esterel Processor - a semi-custom, configurable reactive processor. In Stephen A. Edwards, Nicolas Halbwachs, Reinhard v. Hanxleden, and Thomas Stauner, editors, Synchronous Programming - SYNCHRON’04, number 04491 in Dagstuhl Seminar Proceedings, Dagstuhl, Germany, 2005. Internationales Begegnungs- und Forschungszentrum (IBFI), Schloss Dagstuhl, Germany. (pdf)
    The first KEP paper, the architecture described here is now referred to as the "KEP1." It represented to our knowledge the first custom-designed reactive processor, and the first reactive processor that correctly handled weak and strong abortion. It did not provide full concurrency yet—this was introduced in the multi-threaded KEP3