by Reinhard von Hanxleden, Xin Li, Partha Roop, Zoran Salcic and Li Hsien Yoong

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.

Many embedded systems belong to the class of reactive systems, which continuously react to inputs from the environment by generating corresponding outputs. The programming of reactive systems typically requires the use of non-standard control flow constructs, such as concurrency and exception handling. Most programming languages, including languages such as C and Java that are commonly used in embedded systems, either do not support these constructs at all, or their use induces non-deterministic program behaviour, regarding both functionality and timing. Furthermore, the concurrent behaviour of reactive programs is typically very fine-grained. Measurements indicate that it is not uncommon to have a context switch after, on average, fewer than five instructions. This makes traditional context switch mechanisms, based on an operating system that consumes thousands of instructions per context switch, impractical.

To address these difficulties, the synchronous language Esterel has been developed to express reactive control flow patterns in a concise manner, with a clear semantics that imposes deterministic program behaviour under all circumstances. There are different options to synthesise an Esterel program into a concrete system. In the software synthesis approach, the Esterel program is translated by an Esterel compiler into a C program, which in turn runs on a COTS processor. Esterel can also be synthesised directly into hardware, via some hardware description language such as VHDL. As a hybrid approach, Esterel can also be used in HW/SW co-design. However, these classical synthesis approaches suffer from the limitations of traditional processors, with their instruction-set architectures geared towards the sequential von-Neumann execution model, or they are very inflexible if HW synthesis is involved.

Recently, another alternative for synthesising Esterel has emerged, the reactive processing approach. Here, the Esterel program is running on a processor that has been developed specifically for reactive systems. The instruction set of these reactive processors closely resembles the constructs found in Esterel, such as waiting for the occurrence of a signal or abortion. A comparison highlighting the main philosophical differences between reactive processors and conventional processors is outlined in Table 1.

Features Reactive Processors Conventional Processors
Execution progression Evolves in discrete instants separated by "tick delimiting instructions". Evolves continuously.
Preemption Accomplished through event reaction block with implicit priority resolution and context switching in hardware. Accomplished through interrupt mechanism requiring explicit priority resolution, context saving and restoration in software.
Concurrency Synchronous parallel execution and broadcast communication between threads. Asynchronous execution requiring explicit message passing/rendezvous for communication between threads.
View of the environment Changes at discrete instants. Inputs are latched at the beginning and outputs are sustained till the end of a "tick". Changes continuouslyInputs can be read at any time, and outputs can be sustained for any duration.

Table 1: Comparison between reactive and conventional processors.

The intention of reactive processors is to unite the pros of both the software and hardware synthesis approach while avoiding most of the cons of both. We get from the software synthesis approach the easy programming process with inexpensive testing and short turnaround times. From the hardware side, we gain low energy consumption and fast program execution. The synchronous model of computation inherent in Esterel ensures deterministic behaviour.

Two strategies have been proposed to design reactive processors, which mainly differ in the way they handle concurrency. Since Esterel is a synchronous language, the operation of all concurrent threads is based on the ticks of a single global clock. The principal challenge is to schedule concurrent threads so that within a logical tick, event producers are executed before event consumers. The EMPEROR processor, developed at the University of Auckland, New Zealand, employs multi-processing and uses dynamic scheduling of events. This allows it to handle many threads running on a cyclic executive on a given processor or between concurrent threads running on different processors. The Kiel Esterel Processor (KEP) family, developed at Kiel University, Germany, handles concurrency via multi-threading, which minimises overall resource usage and easily scales up to very high degrees of concurrency. Unlike the dynamic self-scheduling of threads in the EMPEROR approach, the KEP approach schedules all producers before consumer threads to uniquely determine signal statuses. Both approaches have their advantages and limitations. However, overall they perform much better than conventional processors while performing reactive computations.

Apart from efficiency and determinism concerns, another advantage of reactive processors is that due to their comparatively simple structure (no caches, no pipelining) and their direct implementation of reactive control flow constructs, it becomes feasible to precisely characterise their timing behaviour. In conjunction with the synchronous model of computation, which discretises time into logical ticks, it is possible to derive exact, tight bounds on its Worst Case Reaction Time (WCRT), which tells how much time it takes the system to react to the environment. The KEP processor series is equipped with a Tick Manager that can provide a constant logical tick rate and also detects internal timing over-runs. This can serve to detect hardware failures and provides another safeguard, in addition to static analyses, so that real-time deadlines are met.

FPGA-based implementations of reactive processors have proved very competitive to classical processor designs. For a standard suite of Esterel benchmarks the code size is typically an order of magnitude smaller than that of the MicroBlaze, a 32-bit COTS RISC processor core. The worst case reaction time is typically improved four-fold and energy consumption is also typically reduced to a quarter.

In the five years since its inception, the reactive processing approach has thus demonstrated its promise and its practicality. However, much remains to be done. On the theoretical side, a precise characterisation of the reactive execution semantics is still missing and its relationship to other semantics needs to be investigated, in particular regarding causality issues. The reactive instruction set architectures also pose interesting compiler challenges, for example, regarding the efficient mapping of concurrency with minimal context switching. Finally, the derivation of WCRT bounds is so far done very conservatively - it should be feasible to tighten these analyses further.

Links:
http://www.informatik.uni-kiel.de/rtsys/kep
http://www.ece.auckland.ac.nz/~roop/pageGen.php?pageid=10

Please contact:
Reinhard von Hanxleden, Christian-Albrechts-Universität zu Kiel, Germany
Tel: +49 431 880 7281
E-mail: rvh@informatik.uni-kiel.de

Partha Roop, University of Auckland, New Zealand
Tel: +64 9 3737599
E-mail: p.roop@auckland.ac.nz

Next issue: January 2020
Special theme:
Educational Technology
Call for the next issue
Get the latest issue to your desktop
RSS Feed