The Kiel Esterel Processor

Embedded 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.

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.

Annotated KEP References

1. 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.
   
   
2. 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.
   
   
3. 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.
   
   
4. 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.
   
   
5. 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.
   
   
6. 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).
   
   
7. 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.
   
   
8. 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++P07), Braga, Portugal, March 2007. (pdf)
   
   An approach for the safe (conservative) estimation of the Worst Case Reaction Time (WCRT) of the KEP3a.
   
   
9. 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.

10. 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.
    
    
11. 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.
    
    
12. 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.
    
    
13. 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.
    
    
14. 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.
    
    
15. 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).
    
    
16. 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.
    
    
17. 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.