Sidharta Andalam

Partha Roop
email: †p.roop@aucklanduni.ac.nz

Alain Girault
email: alain.girault@inria.fr

Predictable multithreading of embedded applications using PRET-C

We propose a new language called Precision Timed C (PRET-C), for predictable and lightweight multithreading in C. PRET-C supports synchronous concurrency, preemption, and a high-level construct for logical time. In contrast to existing synchronous languages, PRET-C offers C-based shared memory communications between concurrent threads that is guaranteed to be thread safe. Due to the proposed synchronous semantics, the mapping of logical time to physical time can be achieved much more easily than with plain C, thanks to a Worst Case Reaction Time (WCRT) analyzer (not presented here). Associated to the PRET-C programming language, we present a dedicated target architecture, called ARPRET, which combines a hardware accelerator associated to an existing softcore processor. This allows us to improve the throughput while preserving the predictability. With extensive benchmarking, we then demonstrate that ARPRET not only achieves completely predictable execution of PRET-C programs, but also improves the throughput when compared to the pure software execution of PRET-C. The PRET-C software approach is also significantly more efficient in comparison to two other light-weight concurrent C variants (namely SC and Protothreads), as well as the well-known Esterel synchronous programming language.

Introduction

Embedded applications are reactive, concurrent, and also have strict timing requirements. The conventional approach to the design of such systems has been the use of a real-time operating system (RTOS) that executes on a speculative processor to manage both the concurrency and timing needs of the application. The problem of concurrency managed through operating system threads has been highlighted by Lee [START_REF] Lee | The problem with threads[END_REF]: "they discard the most essential and appealing properties of sequential computation: understandability, predictability, and determinism". Understandability is lost since the programmer is burdened with ensuring correctness through complex synchronization mechanisms provided by the RTOS. Predictability is sacrificed since concurrency is emulated through RTOS scheduling that is inherently nondeterministic. More importantly, as these threads are "heavy-weight", there is a significant performance penalty to be paid. This is because each thread has to maintain its full execution context.

A move away from this direction is the concept of light weight multithreading in C -a language of choice for embedded systems. Here, through simple libraries and by light-weight context switching, threading is made feasible. Two prominent examples in this category are the recent SC [START_REF] Hanxleden | Synccharts in c: a proposal for lightweight, deterministic concurrency[END_REF] language and an earlier C-library called Protothreads [START_REF] Dunkels | Protothreads: Simplifying event-driven programming of memory-constrained embedded systems[END_REF]. Both languages are inspired by the concept of coroutines where blocks of code (called coroutines) may have multiple entry points and transfer control to other code blocks using yield statements. Both languages rely on C macros to generate pure C code. SC is designed mainly for directly encoding SyncCharts [START_REF] André | Semantics of SyncCharts[END_REF] in C. This is achieved by having a single tick function that manages the state transition between threads using computed goto statements. The main goal of SC has been to achieve reduced code size in comparison to Esterel [START_REF] Berry | The esterel synchronous programming language: design, semantics, implementation[END_REF] based implementations of SyncCharts. The major limitation of SC is that it has no mechanism for resolving signal status and, hence, doesn't preserve the full semantics of SyncCharts. Protothreads [START_REF] Dunkels | Protothreads: Simplifying event-driven programming of memory-constrained embedded systems[END_REF] is a light-weight C library for the programming of concurrent state-machines. The main objective is to produce minimal memory footprint for embedded applications.

In this paper, we propose a solution that is significantly different from the above-mentioned light-weight C libraries in the following way. Firstly, we propose a synchronous C language where light-weight threads communicate through shared memory. Our semantics ensures that shared memory access is thread-safe by construction; this solves the issue of understandability by shifting the responsibility of shared memory management from the programmer to the semantics of the language. Our threads are light-weight and are compiled to a single function where "multithreading" is elicited through context switching using a barrier instruction called EOT. Due to the reliance on a new synchronous semantics [START_REF] Andalam | PRET-C: A new language for programming precision timed architectures[END_REF], composition is causal [START_REF] Benveniste | The synchronous languages 12 years later[END_REF] by construction and, hence, all PRET-C programs are deterministic; this solves the issue of determinism. Finally, we perform static timing analysis to compute the maximum tick length of our PRET-C programs. This value, called the worst case reaction time (WCRT), ensures that the execution of a PRET-C program is time-predictable; this solves the issue of predictability. Furthermore, our solution [START_REF] Roop | Tight wcrt analysis of synchronous c programs[END_REF] for computing the WCRT is based on a new algorithm, tighter than earlier approaches [START_REF] Ju | Performance debugging of esterel specifications[END_REF], [START_REF] Mendler | Wcrt algebra and interfaces for esterel-style synchronous processing[END_REF].

The language extensions to C that we propose are C macros, and hence the standard gcc compiler can be used for backend code generation. The optimized assembly code is represented in an intermediate format called timed concurrent control flow graph (TCCFG), which is used for the WCRT analysis [START_REF] Roop | Tight wcrt analysis of synchronous c programs[END_REF]. PRET-C programs can be executed completely predictably by fixing the tick length to the value determined by this WCRT analysis. This is useful for applications that require full predictability or a fixed sampling rate. Alternatively, they can be executed with a variable tick length for better performances, but at the cost of predictability.

The execution of PRET-C programs can be done using either a hardware or a software approach. In the hardware approach, we extend a general processor with a hardware accelerator. That performs thread scheduling and preemption. We demonstrate the proposed method through the ARPRET processor that is designed by customizing the Xilinx MicroBlaze [START_REF]Xilinx. MicroBlaze Processor Reference Guide[END_REF] soft-core processor. This approach achieves predictable execution without sacrificing throughput. In the software approach, however, we perform efficient thread scheduling in software similarly to CEC [START_REF] Edwards | Code generation in the Columbia Esterel Compiler[END_REF] linked-list based scheduler.

The key contributions of this paper are:

1) The design of a new light-weight and concurrent language called PRET-C, for the predictable programming. PRET-C offers a very simple mechanism for achieving thread-safe shared memory communication between light-weight C-threads, not available in earlier light-weight threading libraries for C. 2) We offer a hardware accelerator for PRET-C execution over soft-core processors so that predictable execution can be achieved without sacrificing throughput. This will be crucial for achieving precision timed implementations of real-time applications.

3) We demonstrate, that ARPRET excels in comparison to the pure software implementation of PRET-C. Interestingly, software implementation of PRET-C significantly outperforms SC, Protothreads, and Esterel in the average and worst case reaction time, while generating compact code. The WCRT analysis is not the focus of the current paper; it can be found in [START_REF] Roop | Tight wcrt analysis of synchronous c programs[END_REF]. Moreover, the structural operational semantics of PRET-C can be found in the companion technical report [START_REF] Andalam | PRET-C: A new language for programming precision timed architectures[END_REF], along with much more detailed comparison with other synchronous programming languages (Esterel and RC). Finally, a preliminary short version of the present work appeared in [START_REF] Andalam | Deterministic, predictable and light-weight multithreading using PRET-C[END_REF]. Compared to this short paper, the present paper contains much more details on the PRET-C language, on the ARPRET architecture, and on the intermediate TCCFG format; it also covers the compilation into TCCFG, which what not presented in [START_REF] Andalam | Deterministic, predictable and light-weight multithreading using PRET-C[END_REF].

The organization of this paper is as follows. In Section 2, we present the PRET-C language through a producer-consumer example. The intermediate format is presented in Section 2.3. In Section 3, we present the ARPRET architecture. The results of the experiment, evaluating the hardware extension and performance against other concurrent programs are presented in Section 4. Finally, the conclusions are presented in Section 5.

PRET-C overview

The overall design philosophy of PRET-C and the associated architecture may be summarized using the following three simple concepts:

• Concurrency: Concurrency is logical but execution is sequential. This ensures both synchronous execution and thread-safe shared memory communication. This is the founding principle of the synchronous programming languages [START_REF] Benveniste | The synchronous languages 12 years later[END_REF].

• Time: Time is logical and the mapping of logical time to physical time is achieved by the compiler and the WCRT analyzer [START_REF] Roop | Tight wcrt analysis of synchronous c programs[END_REF].

• Design approach: ARPRET achieves PRET by simple customizations of general purpose processor (GPP). The extensions to C are minimal and are implemented through C-macros.

PRET-C language extensions

PRET-C extends C using the five constructs shown in Table 1. In order to guarantee a predictable execution, we impose the following four restrictions on the C language:

• Pointers can cause dynamic jumps and dynamic calls with the computed target addresses. We cur- rently disallow pointers to prevent unpredictable control flow. However, in the near future, we will follow a value analysis technique [START_REF] Wilhelm | The worst-case execution-time problem-overview of methods and survey of tools[END_REF] to allow the restricted use of pointers.

• Our current version does not allow dynamic memory allocation. However, some of the recent work [START_REF] Herter | CAMA: Cacheaware memory allocation for WCET analysis[END_REF] guarantees precise (de)allocation times, while focusing on reducing internal fragmentation. In the near future, we will investigate existing ideas to allow dynamic memory allocation.

• All loops must have at least one EOT in their body. This is needed to ensure that thread compositions are deadlock free. This restriction could be relaxed for the loops that can be statically proven to be finite.

• All function calls have to be non-recursive to ensure a temporal upper bound on execution time.

The C extensions are implemented as C-macros, all contained in a pretc.h file that must be included at the beginning of all PRET-C programs. As a result, we only rely on the gcc macro-expander and compiler for compiling PRET-C programs.

Like any C program, a PRET-C program starts with a preamble part (#define and #include lines), followed by global declarations (reactive inputs, reactive outputs, and classical C global variables), and finally function definitions (including the main function).

A PRET-C program runs periodically in a sequence of ticks triggered by an external clock. The inputs coming from the environment are sampled at the beginning of each tick. They are declared with the ReactiveInput statement. The outputs emitted to the environment are declared with the ReactiveOutput statement. Reactive inputs are read from the environment at the beginning of every tick and cannot be modified inside the program. Hence, the value of these variables remains fixed throughout an instant. They have a default value when the environment assigns no value. In contrast, reactive outputs may be updated by the program and can have several values within an instant. The final value of these variables (termed their steady-state value) is emitted to the environment. Reactive outputs behave exactly like normal variables in C, except that they are emitted to the environment while normal variables are for communication between threads, and are not emitted to the environment.

Programmers familiar with usual synchronous languages such as Esterel [START_REF] Berry | The esterel synchronous programming language: design, semantics, implementation[END_REF] or its earlier C-based extensions [START_REF] Lavagno | Ecl: a specification environment for system-level design[END_REF] will notice the difference with PRET-C. Unlike these languages, where the primary means of communication between threads are signals, we use variables. Signals have both a status and an associated value (when the signal is not pure). Esterel forbids the usage of variables for communication between threads for causality reasons. PRET-C allows unrestricted shared variable access across threads, and thread safe communication is achieved using static thread priority. Besides this, our reactive inputs and outputs are similar to Esterel's input and output signals, respectively.

The PAR(T1,...,Tn) statement spawns n threads that are executed in lock step. All spawned threads evolve based on the same view of the environment. However, unlike the usual of other synchronous languages like Esterel, where threads are scheduled in each instant based on their signal dependencies, threads in PRET-C are always scheduled based on a fixed static order. This order is determined based on the order in which threads are spawned using the PAR construct. E.g., a PAR(T1,T2) statement assigns to T1 a higher priority than to T2.

Parallel threads communicate through shared variables and reactive outputs. The task of ensuring mutually exclusive access is achieved by ensuring that, in every instant, all threads are executed in a fixed total order by the scheduler. When more than one thread acts as a writer for the same variable, then the semantics of the program still remains deterministic. Indeed, race conditions can happen in RTOSs when these writes are non-atomic, i.e., if one write operation can be interrupted and another thread can then modify the same variable. However, as long as these writes happen atomically in some fixed order, the value of the result will be always predictable and race conditions will be prevented. This is ensured by our ARPRET architecture thanks to the proposed multithreaded execution. On ARPRET, once a thread starts its execution, it cannot be interrupted. The next thread is scheduled only when the previous thread reaches its EOT. Thus, when two or more threads can modify the same variable, they always do so in some fixed order, ensuring that the data is consistent.

The EOT statement marks the end of a tick. When used within several parallel threads, it implements a synchronization barrier between those threads. Indeed, each EOT marks the end of the local tick of its thread. A global tick elapses only when all participating threads of a PAR( ) reach their respective EOT. In this sense, EOT is similar to the pause statement of Esterel. EOT enforces the synchronization between the parallel threads by ensuring that the next tick is started only when all threads have reached their EOT. Finally, it allows to compute precisely the WCRT of a program by computing the execution time of all the computations scheduled between any two successive EOT instructions. This WCRT analysis is presented in paper [START_REF] Roop | Tight wcrt analysis of synchronous c programs[END_REF].

EOT is similar in spirit to the deadi instruction of [START_REF] Lickly | Predictable programming on a precision timed architecture[END_REF] (immediate deadline). However, unlike the lowlevel deadi instruction that manages timing thanks to timers, EOT is a high-level programming construct. The task of ensuring precise timing of threads is not left to the programmer but is derived by WCRT analysis and is a compilation task [START_REF] Roop | Tight wcrt analysis of synchronous c programs[END_REF]. Moreover, the deadi instruction is also used for achieving mutual exclusion by time-interleaving the access to shared memory. This is achieved by setting precise values to the deadlines. However, if done manually, this task can be very complex, even for simple programs. This is mainly due to arbitrary branching constructs and loops. Automating this task is non-trivial and has not been solved in [START_REF] Lickly | Predictable programming on a precision timed architecture[END_REF]. Our solution to achieve mutual exclusive access to shared memory is ensured by having static thread priorities, and then scheduling the threads in every instant according to this fixed linear order.

The abort P when pre C construct preempts its body P immediately when the condition C is true (like immediate abort in Esterel). Like in Esterel, preemption can be either strong (abort alone) or weak (when the optional weak keyword is used). In case of a strong abort, the preemption happens at the beginning of an instant, while the weak abort allows its body to execute and then the preemption triggers at the end of the instant. All preemptions are triggered by the previous value of the Boolean condition (hence the pre keyword), to ensure that computations are deterministic. This is needed since the values of variables can change during an instant. The use of the pre ensures that preemptions are always taken based on the steady state values of variables from the previous instant. In other words, like in ReactiveC, we use a restricted form of causality compared to Esterel.

A Producer Consumer example

We present in Figure 1 a producer-consumer example adapted from [START_REF] Vahid | Embedded System Design[END_REF] to motivate PRET-C. The program starts by including the pretc.h file (line 1). Then, reactive inputs are declared (lines 3 and 4), followed by regular global C variables (lines 5 and 6), and finally all the C functions are defined (lines 7 to 41). The main function consists of a single main thread that spawns two threads (line 36): a sampler thread that reads some data from the sensor reactive input and deposits this data on a global circular buffer, and a display thread that reads the deposited data from buffer and displays this data on the screen, thanks to the user defined function WriteLCD (line 29). The sampler and display threads communicate using the shared variables cnt and buffer. Also, the programmer has assigned to the sampler thread a higher priority than to the display thread. All the threads are declared as regular C functions.

During its first local tick, the sampler thread does nothing. During its second local tick, it checks if its data buffer is full (line 11): as long as buffer is full, it keeps on waiting until the display thread has read some data so that there is empty space in buffer. When it exits this while loop, it then writes the current instant's value of the sensor input to the next available location of the buffer (line 12) and ends its local tick (line 13). During its third and last local tick, the index i of the buffer and the total number cnt of data in the buffer are incremented (lines 14 and 15), since this is a circular buffer. Then, the sampler loop is restarted.

During its first local tick, the display thread does nothing. During its second local tick, it checks if there is any data available to read from buffer (line 23). If there is no data available, then it ends its local tick and keeps on waiting until some data has been sent by the producer. When this happens, it reads the next data from buffer (line 24) and ends its local tick (line 25). During its next local tick, i is incremented (line 26) and cnt is decremented (line 27). During its last local tick, it sends the data read from the buffer to a display device (line 29).

The main thread (main function) has an enclosing abort over the PAR construct. This preemption is taken whenever an external reset button has been pressed in the previous instant (line 37). In our example, when a strong preemption happens, the two threads are aborted,the cnt is initalized (line 38), and the main thread pauses for an instant before flushing the buffer and restarting the two threads again.

The execution of this code on any GPP with an RTOS to emulate concurrency will lead to race con- ditions. It is the responsibility of the programmer to ensure that critical sections are properly implemented using OS primitives such as semaphores. Race conditions will occur because of non-exclusive accesses to the shared variable cnt. However, on ARPRET, the execution will always be deterministic. Assume that cnt=cnt+1 and cnt=cnt-1 happen during the same tick. Due to the higher priority of sampler over display, cnt will be incremented first, and once sampler reaches its EOT, the ARPRET scheduler (see Section 3) will select display which will then decrement cnt. Thus, the value of cnt will be consistent without the need for enforcing mutual exclusion between the sampler and display threads.

Intermediate format

We propose an intermediate format for PRET-C programs, called Timed Concurrent Control Flow Graph (TCCFG). The TCCFG corresponding to the example of Figure 1 is shown in Figure 2. The TCCFG encodes the explicit control-flow of the threads as well as the forking and joining information of the threads. Depending on the type of aborts, we insert checkabort nodes. For each strong abort in the program, a checkabort node is inserted just after every EOT node. For each weak abort in the program, we insert a checkabort node just before every EOT node.

The TCCFG encodes the explicit control-flow of the threads as well as the forking and joining information of the threads. It has the following types of nodes:

• Start/End node: Every TCCFG has a unique start node where the control begins, and may have an end node if the program can terminate. Both are drawn as concentric circles.

• Fork/Join nodes: They mark where concurrent threads of control start and end. They are drawn as triangles.

• Action nodes: They are used for any C function call or data computation. We use rectangles to draw them.

# -# %# *# -!.# %# .# /# -# %# 0# 0# .# ,# .# ,%# %# -# *# *# %# -# /# .# %# -!.# ,# %# -# -# .# 2 263% CE+ E9# 1# 26377% "#
• EOT nodes: They indicate the end of a local or a global tick, and are drawn as filled rectangles.

• Control flow nodes: We have two types of control flow nodes: conditional nodes to implement conditional branching (drawn as rhombuses labelled with the condition) and jump nodes for mapping unconditional branches (drawn as arrow-shaped pentagons).

• Abort nodes: We have abort start and abort end nodes to mark the scope of an abort. They are drawn as rhombuses labeled either with 's' or 'w' to indicate strong or weak aborts.

• Checkabort nodes: These are special nodes that implement the semantics of aborts. They are drawn as thin rhombuses labeled with 'chk'. More details on the structural translation of aborts are covered in [START_REF] Andalam | PRET-C: A new language for programming precision timed architectures[END_REF].

COMPILING PRET-C INTO TCCFG

PRET-C programs are C programs with the addition of macros that implement the macros of Table 1 to support concurrency and synchronous reactivity. Since we are compiling for MicroBlaze (MB), we use MB based gcc compiler (mb-gcc) to expand the macros and compile the resulting C program into MB assembly code. This assembly code contains a small number of assembly instructions along with lots of information to help the linker. For the timing analysis, we are only interested in the assembly instruction and some specific set of labels. So we first get rid of unwanted information, then we generate the TCCFG nodes using the ASM2TCCFG translator, developed by us. The nodes contain information about the instruction type (Figure 2 shows the node types) and the worst case execution cost.

Figure 3 shows how we translate a PAR instruction in PRET-C into a FORK node in TCCFG. The PAR instruction (shown in Figure 3a) compiles into the MB assembly code shown in Figure 3b. Line 1 of the assembly code contains the assembly comment begin PAR. The ASM2TCCFG translator recognizes this as the beginning of a FORK node. Then, line 2 contains the number of children for this FORK node (two in this case). Recognizing the assembly comment on line 6, ASM2TCCFG reads the next line and extracts the label $L8 as the start address of its first child. Similarly, it extracts the label $L9 on line 20 as the start address of its second child. The analyzer then creates two arrows, pointing from the FORK node respectively to the node containing the label $L8 (start of the sampler thread), and to the node containing the label $L9 (start of the display thread). Finally, the unconditional branch assembly instruction on line 16 is seen by the translator as the end of the fork node.

Following some simple rules, the ASM2TCCFG translator can generate all the nodes and the arrows connecting the nodes of a PRET-C program. To calculate the execution cost of each node, we first calculate the cost of each assembly instruction in the node. We do this by referring to a look up table containing the worst case execution cost of each assembly instruction. This data is based on the MB datasheet [START_REF]Xilinx. MicroBlaze Processor Reference Guide[END_REF]. Secondly, by summing up the cost of all the instructions in any given node, we obtain the worst case execution time for this node. Figure 2.3.1b shows that the worst case execution cost of the FORK node is 13 clock cycles. Once we have the complete TCCFG, the WCRT analysis of PRET-C is performed as presented in [START_REF] Roop | Tight wcrt analysis of synchronous c programs[END_REF].

ARPRET architecture

This section presents the hardware extension to a General Purpose Processor (GPP) called MicroBlaze (MB) [START_REF]Xilinx. MicroBlaze Processor Reference Guide[END_REF] in order to achieve temporal predictability. We designed the PRET-C language to enable the design of PRET machines by simple customizations of GPPs.

The changes needed to execute PRET-C predictably concern the support for concurrency and preemption.

If concurrency is implemented purely in software, the overhead of scheduling will be proportional to the number of parallel threads. Indeed, at each EOT, the scheduler has to select the next thread based on the status of threads and the preemption contexts. Doing this in software will consume significant numbers of clock cycles (compared to a hardware implementation), thus reducing the overall throughput. For this reason, we do the scheduling in hardware, with a custom made Predictable Functional Unit (PFU). Figure 4 shows the basic setup of an Auckland Reactive PRET (ARPRET) platform consisting of a MB soft-core processor that is connected to a PFU. MB is a customizable RISC based soft-core processor, optimized for implementation on the Xilinx FPGA. To guarantee predictability, all instructions and data are stored in on-chip memory. Any read/write operation takes only one clock cycle, simplifying the problem of PFU is inspired by the STARPro processor [START_REF] Yuan | Starpro -a new multithreaded direct execution platform for esterel[END_REF], which stores multiple thread preemption contexts for executing Esterel. STARPro's hardware only allows upto four levels of nested preemptions per thread and it preallocates the hardware for each thread. This is an inefficient use of hardware. In comparison, PFU does not preallocate any hardware. Instead, all threads share the same space in the Abort Table. This is more efficient, as it allows the space consumed by each thread to change dynamically. Also, since PRET-C has fixed priorities compared to Esterel, this simplifies the hardware and reduces the footprint compared to STARPro.

The PFU stores multiple thread contexts and schedules the threads. For each thread, a thread table stores its Program Counter (PC) as a 32-bit value, its status (dead or alive, called TDA), its suspended status (TSP), its local tick status (TLT), and its priority (TP). Depending on the four thread statuses, the scheduler issues the next program counter when requested. Abort contexts are also maintained in an abort table for dealing with preemption.

MB acts as the master by initiating thread creation, termination, and suspension (this is different from Esterel suspend; in PRET-C, any thread that spawns child threads is suspended). The PFU stores the context of each thread in the thread table and monitors the progress of threads as they execute on the MB. When a given thread completes an EOT instruction on the MB, it sends appropriate control information to the TCB using FSL bridge. In response to this, the PFU sets the local tick bit (LTL) for this thread to 1, and then invokes the scheduler. The scheduler then selects the next highest priority thread for execution by retrieving its PC value from the thread table and sending it to MB using FSL bridge. Whenever it completes a local tick, the MB blocks to wait for the next PC value from the PFU. PFU can be configured for two different execution strategies, either with a variable execution time for throughput, or with a constant execution time for predictability. During the constant execution mode, MB awaits for the worst case tick length to expire before starting the next tick. This is stored in WCRT timer and is calculated at compile time by static WCRT analysis of a PRET-C program as detailed [START_REF] Roop | Tight wcrt analysis of synchronous c programs[END_REF]. We next present in detail how the tightly coupled connection between the MB and the PFU is created in ARPRET.

Communication

Communication between MB and the PFU is done by using the Fast Simplex Link (FSL) interface [START_REF]Xilinx. MicroBlaze Processor Reference Guide[END_REF] The communication between the MB (master) and PFU (slave) is triggered when the MB executes instructions such as PAR(T1,T2) and EOT. The PFU contains a Controller Logic that refers to a look up table (LUT) as shown in Table 2 to decode the data from MB. For example, to spawn a thread, the MB writes a value of 10 followed by the start address of the thread onto the FSL bridge. Controller logic decodes 10 as SPAWN. Then, and by referring to the number of reads in Table 2, it fetches one more data element from the FSL bridge and stores it as the PC of the new thread. Also, in response to this SPAWN, other status bits such as the thread status and the suspended bits are altered appropriately. Also, the TLT bit is set to 0 to indicate that the local tick for the thread is not yet reached.

Hardware usage

We next present the results of the hardware resource usage on the FPGA device. The hardware resources in terms of Slices and Look Up Tables (LUT) are shown by Figure 6. Slices are logical blocks providing functionality such as arithmetic, ROM functions, storing, and shifting data. They contain LUTs, storage elements, and multiplexers. Four-input lookup tables are used by FPGA function generators for implementing any arbitrarily defined four-input Boolean function [START_REF]Xilinx. MicroBlaze Processor Reference Guide[END_REF]. From Figure 6 we can see that the hardware resource consumption of ARPRET is linearly proportional to the number of threads. This is due to the fact that ARPRET mostly stores thread contexts, and only minimal datapath is required by the scheduler.

Benchmarks and results

To assess the efficacy of the proposed hardware acceleration, we first compare the hardware execution of PRET-C on ARPRET with the software execution on MicroBlaze. We then compare the software execution of PRET-C with that of Protothreads, SC, and Esterel. Comparison is carried out over both execution time and memory usage of a set of benchmark programs with high degree of concurrency and preemption. Some of the benchmarks are adaptations of programs from the Estbench [START_REF] Edwards | EstBench Esterel Benchmark Suit[END_REF] suite.

To preserve behavioral equivalence when translating PRET-C programs into Protothreads, we made Protothreads synchronous by using the yield construct, which is similar to EOTs, and also by forcing tick synchronization to facilitate a synchronous execution as in PRET-C and Esterel. Preemptions in Protothreads were emulated using a software-like approach based on the placement of checkaborts. For Esterel, all nonimmediate aborts were replaced by the immediate counterparts.

Benchmarking

The benchmarking process was carried out as follows. Firstly, we generated code for ARPRET. Then, for the same benchmarks, we generated C code for execution on MicroBlaze alone (that is, with no PFU). To enable a fair comparison with the hardware scheduler, thread scheduling was done very efficiently in software thanks to CEC-like [START_REF] Edwards | Code generation in the Columbia Esterel Compiler[END_REF] linked-list based scheduler1 . We call this approach the software compilation approach for PRET-C. We present the results of the hardware versus software execution of PRET-C in Figure 7.

For WCRT comparison, we used random test vectors and measured the WCRT over one million reactions. The worst case (shown in Figure 7a) is the maximum of the measured values, while the average case (shown in Figure 7b) is obtained by averaging over all samples. As detailed in Section 3, for predictability, the hardware can be configured with constant tick length, obtained through the static analysis approach [START_REF] Roop | Tight wcrt analysis of synchronous c programs[END_REF]. The hardware approach is 28% more efficient than the software approach for the average case, and 26% for the worst case.

Since there are no hardware acceleration platforms for SC, Protothreads, and Esterel, we compared the software execution of PRET-C with the software execution of these languages. The results are presented in Figure 4.1. Code was generated on MicroBlaze for SC, Protothreads, Esterel, and the PRET-C software approach. We used the CEC compiler for Esterel code generation since it consistently generated the most efficient code compared to all other Esterel compilers.

Figure 4.1a shows the average case reaction times and Figure 4.1b shows the WCRT. On average, PRET-C consumes about 18%, 68%, and 77% less computation time when compared to Protothreads, Esterel, and SC respectively. Similarly for the WCRT, PRET-C consumes about 20%, 50%, and 74% less time respectively. In comparison SC achieves the least throughput. This is due to its implementation of the thread scheduling by calling a function, where the overhead of the function call is proportional to the number of threads. In contrast, the context-switch in PRET-C takes constant time that does not involve any function calls. The memory usage of these languages is presented in Figure 4.1. PRET-C generates significantly more compact code compared to Esterel, while being slightly inferior to SC (by only 4%) and almost equivalent to Protothreads. In summary, these results reveal that PRET-C yields significantly more efficient code compared to all others in both the average and worst case. Also, the memory usage of PRET-C is superior to Esterel and comparable to SC and Protothreads.

Conclusions and future work

Precision Timed (PRET) architectures are a recent attempt to design processors that guarantee predictable execution of code without sacrificing throughput. Researchers from Berkeley and Columbia proposed a tailored processor with a thread interleaved pipeline and a low-level instruction to introduce precise timing in C code [START_REF] Lickly | Predictable programming on a precision timed architecture[END_REF]. In contrast, this paper proposes the customization of embedded soft-core processors to design PRET architectures with minimal hardware requirements. We also propose a new language for programming PRET machines, called PRET-C, by simple synchronous extensions to the C language. PRET-C has constructs for expressing logical time, preemption, and concurrency. Concurrent threads communicate using the shared memory model (regular C variables) and communication is thread-safe by construction. We have designed a new PRET machine, called ARPRET, by customizing the MicroBlaze soft-core processor. We have benchmarked the proposed design by comparing the execution of PRET-C on ARPRET with the execution of Esterel on its speculative counterpart (MicroBlaze). Benchmarking results reveal that the proposed approach achieves predictable execution without sacrificing throughput.

In the future, we will explore more scalable architecture design, consider memory hierarchy, and the multicore execution of PRET-C.

Figure 1 .

 1 Figure 1. A Producer-Consumer example in PRET-C.

Figure 2 .

 2 Figure 2. TCCFG of the Producer-Consumer.

Figure 4 .

 4 Figure 4. ARPRET platform consisting of MicroBlaze GPP and an external functional unit called PFU.

Figure 3 .Figure 5 .

 35 Figure 3. From PAR instruction to FORK node.

Figure 6 .

 6 Figure 6. Number of threads versus hardware consumption in terms of LUTs.

Figure 7 .

 7 Figure 7. Comparing the reaction time on hardware and software.

Figure 8 .

 8 Figure 8. Comparing the Reaction time of PRET-C (software) with Protothreads, Esterel, and SC.

Figure 9 .

 9 Figure 9. Comparing the memory usage of PRET-C (software) with Protothreads, Esterel, and SC.

Table 1 .

 1 PRET-C extensions to C.

	Statement	Description
	ReactiveInput I	declares I as a reactive input coming from the environment
	ReactiveOutput	declares O as a reactive output emitted to
	O	the environment
		synchronously executes in parallel the n
	PAR(T1,...,Tn)	threads Ti, with higher priority of Ti
		over Ti+1
	EOT	marks the end of a tick (local or global depending on its position)
	[weak] abort P	immediately kills P when C is true in the
	when pre C	previous instant

1

  PAR(sampler,display); 2 ...

			1	# begin PAR
			2	# children 2
			3	# / * some computation in parent
					thread * /
			4	# / * stores the return address * /
			5
			6	#@ child info
			7	addik r4,r0,$L8
			8	swi	r4,r0,T1
			9
			10	#@ child info
			11	addik r3,r0,$L9
			12	swi	r3,r0,T2
			13
			14			1234
	16 sampler: 17 / * code for the sampler thread * /	15 16 17	# / * some computation * / bra r7 //unconditional jump ...
	18 ... 19 ...	18 $L8: 19 #/ * assembly code for sampler	1234 5678699AB9	124 5678699AB9
	20 ... 21 display:	20 $L9:	thread * /	C7DEF8 687	CEF79 687
	22	/ * code for the	21	#/ * assembly code for display
		display thread * /			thread * /
		a) PAR in PRET-C.		b) MB assembly code.	c) FORK node in TCCFG.

3 ... 4 ... 5 ... 6 ... 7 ... 8 ... 9 ... 10 ... 11 ... 12 ... 13 ... 14 ... 15 ...

Table 2 .

 2 provided by Xilinx. Two FSL bridges closely couples MB with the PFU, to provide deterministic and predictable communication. Communication with the bridge requires exchange of some common control signals such as the clock, reset, buffer status (FULL/EMPTY), read, write, and also data such as the PC value. Simple lookup table is used by the PFU to decode the data from the FSL bridge.

	Function (ID)	Number of reads	Number of writes
	SPAWN (10)	1	0
	EOT (12)	1	1
	SUSPEND (14)	1	1

CEC is the most efficient compiler for Esterel to C. It has very efficient mechanisms for thread management in software, which ensure minimal context switching


Sander G Huisman

Patricia Ern

Véronique Roig

Interaction and coalescence of large bubbles rising in a thin gap

We present accurate measurements of the relative motion and deformation of two large bubbles released consecutively in a quiescent liquid confined in a thin-gap cell. Although the second injected bubble was smaller, we observed that, in all cases, it accelerated and caught up with the leading bubble. This acceleration is related to the wake of the leading bubble, which also induces significant changes in the width and curvature of the trailing bubble. On the contrary, the velocity of the leading bubble is unaltered during the whole interaction and coalescence process. Shape adaptation of the two bubbles is observed just prior to coalescence. After pinch-off, the liquid film is drained at a constant velocity.

When two bubbles are rising in a quiescent fluid, the paths they follow are related to the perturbations they induce in the liquid and to their capacity to undergo deformation. In the tandem configuration (two bubbles rising along their lines of centers), the wake of the leading bubble is a powerful means to draw the bubbles together. This behavior is expected to promote coalescence, although escaping behavior may occur owing to the bubble's ability to deform or to lateral perturbations that may cause the bubbles to rotate and to line up horizontally [1,2]. Coalescence of a leading bubble with a trailing bubble is commonly observed in experimental high-Reynolds-number bubbly flows [3] but is currently not predicted by theoretical and numerical papers. Potential flow theory predicts that two bubbles rising in tandem will repel each other [4,5] with flow reversibility leading to the existence of a stagnation point between the two bubbles. Moreover, numerical simulations for nondeformable spherical bubbles at moderate-to-large Reynolds numbers predict that bubbles in line reach an equilibrium distance for which the repulsive potential effect balances the attractive viscous effect related to the vorticity produced at the bubble surface [1,6].

Presently, there is little quantitative information on the bubble's kinematics during their interaction and on its relationship with the bubble's deformation. The aim of this paper is to obtain a simultaneous characterization of the kinematics and deformation of two bubbles rising in tandem. For this purpose, we consider the interaction of two large bubbles rising freely in line in a vertical Hele-Shaw cell. The case of large bubbles is particularly interesting since their shapes are preserved by coalescence. The use of a Hele-Shaw cell has the advantage to constrain the motion and the deformation of the bubbles to the plane of the cell.

The motion of an isolated bubble rising in a quiescent liquid in a confined geometry has been studied in detail in Refs. [7][8][9][10]. Given the fixed width e of the cell, the equivalent diameter of the bubble is defined from the area A of the bubble in the plane of the cell d = √ 4A/π . Three nondimensional parameters governing the single-bubble problem may then be introduced, the Archimedes number Ar = d √ gd/ν, the Bond * roig@imft.fr number Bo = ρgd 2 /σ , and the confinement ratio e/d ≪ 1 (g being the gravity acceleration, ν being the liquid kinematic viscosity, ρ being the liquid density, and σ being the surface tension), the density and dynamic viscosity of the bubble being considered negligible relative to those of the liquid. For a given set of parameters, the resulting mean vertical velocity V ∞ of the bubble is used to define the Reynolds number Re = V ∞ d/ν. Furthermore, the dimensionless quantity Re = Re(e/d) 2 compares the in-plane inertial time scale V ∞ /d and the time scale for viscous diffusion in the gap e 2 /ν. The classical Hele-Shaw regime corresponds to Re ≪ 1, whereas inertial effects become predominant when Re ≫ 1 [11]. In the present Brief Report, all the bubbles satisfy 6000 < Ar < 18 000, Re ≫ 1, and Re ≫ 1 and have the shape of a circular segment. When these bubbles are rising alone, we measure that their terminal velocities are given by the relation Re = π 2C d Ar ≃ 0.42 Ar or V ∞ ≃ 0.42 √ gd, indicating that their drag coefficients are, with a very good approximation, independent of the bubble size (C d ≃ 3π ) in agreement with Refs. [7,8]. Upstream of the bubble, the flow can be conveniently predicted by potential flow theory, whereas, the production of vorticity at the bubble surface results in the existence of a stationary wake as can be seen in Fig. 1. Moreover, the shear stresses at the walls impose a faster spatial decrease of the open wake in a Hele-Shaw cell than in an unbounded fluid, which is associated with the viscous length scale

l ν = V ∞ e 2 /ν, namely, u/V ∞ ≃ exp [-10(y -y R )/ l ν ],
where y R is the length of the recirculating wake measured from the bubble center y R ≃ 0.16l ν [8]. At a distance of about 0.4l ν (≃ 4d for Ar ≃ 7000), the liquid velocity in the open wake is already 10% of V ∞ . Note that l ν /d ∼ 1/ √ d so that as Ar increases, the length of the recirculating wake decreases in terms of the bubble diameter (y R ≃ 1.6d for Ar ≃ 7000 and ≃1.3d for Ar ≃ 13 500).

The apparatus consists of two glass panes spaced 1-mm apart and filled with water. The cell has a width of 40 cm and a height of 80 cm, allowing us to visualize the entire process of interaction and coalescence, while making sure the bubbles are not affected by end effects. Gas injection is controlled manually by a combination of pressure reducing valves, stopcock valves, and dispensing needles. The bubbles are recorded using high-speed imaging, after which the FIG. 1. Liquid velocity around an isolated large bubble obtained by particle image velocimetry (Ar = 7000, V ∞ = 0.16 m/s, d = 1.5 cm). Left, in the laboratory frame; right, focus on the recirculating wake in the bubble frame.

background is subtracted from the frames. The resulting frames are binarized, revealing the contours of the bubbles. From the contours, we obtain the kinematics and deformation characteristics of the bubbles.

We vary the injected gas volume for both bubbles and release them in rapid succession from a single capillary. We investigated the case where the second bubble is smaller than the first one. If the delay between the bubbles' injection is not too large, we observe that the trailing bubble catches up with the leading bubble, resulting in coalescence. Figure 2 provides an overview of this process. These experiments indicate that the suction effect provided by the wake of the leading bubble is sufficiently strong to accelerate the secondary bubble until it joins the first bubble. Moreover, this occurs even when the trailing bubble is smaller and has a smaller terminal velocity than the leading bubble, since the terminal velocity of an isolated bubble is proportional to A 1/4 . Figure 2 also reveals that a strong deformation of the secondary bubble occurs when it is sufficiently close to the leading bubble. We now provide a detailed characterization of the whole interaction and coalescence process, in particular, the wake-induced relative motion of the two bubbles, their deformation when the bubbles are close enough, and finally, the thin liquid film drainage occurring after pinch-off of the two bubbles' interfaces.

The data presented are the mean of 40 experiments, performed over a range of Ar numbers (10 000 < Ar 1 < 17 500 and 6000 < Ar 2 < 10 000), where Ar 2 /Ar 1 varies between 0.5 and 0.8 and where the indices 1 and 2 correspond to the leading and trailing bubbles, respectively. Figure 3 presents the instantaneous vertical velocities of the bubbles as a function of the distance between the centers of gravity of the bubbles. Both velocities are normalized with the terminal velocity of an isolated bubble of the same size as the leading bubble. On the abscissa, the distance between the centers of the bubbles is normalized using the viscous length scale l ν . Figure 3 shows that the speed of the leading bubble is unaltered by the presence of the second bubble. This has also been observed in Ref. [12] for three-dimensional (3D) spherical caps, whereas, for small spherical bubbles, the velocity of both bubbles increases prior to coalescence [13]. Regarding the trailing bubble, Fig. 3 shows that it experiences a significant acceleration and then deceleration as it approaches the leading bubble. Thanks to the entrainment provided by the leading bubble's wake, the velocity of the trailing bubble is already 50% higher than its isolated speed and 20% higher than the speed of the leading bubble at y ≃ 0.5l ν (about four diameters away from the top bubble) and continues to increase while the trailing bubble is approaching the leading one. This acceleration phase was measured already in Ref. [12], but they carried out no measurement beyond y/d 1 ≈ 2.5. When the distance between the bubbles is y/ l ν ≈ 0.2 ( y/d 1 ≈ 2), the velocity of the trailing bubble reaches a maximum, about two times faster than the speed of the leading bubble. This corresponds to frames 4 and 5 in Fig. 2. At that point, the trailing bubble is entering the attached recirculating wake of the leading bubble, and it starts to experience large deformations as described later. This velocity is kept until y/ l ν ≈ 0.1 ( y/d 1 ≈ 1). For lower separation distances, the liquid between the two bubbles is pushed out, the bubbles become wider, and the trailing bubble slows down and adapts its velocity to the speed of the leading bubble. For trailing bubbles with Ar 2 ≈ 8440, Fig. 3 also presents the evolution of their vertical velocity when the leading bubbles move either at Ar 1 ≈ 11 810 or at Ar 1 ≈ 16 690 [green curves (light gray top)]. We observe that all the curves superpose satisfactorily. The same result is obtained when fixing Ar 1 and considering two different sets of Ar 2 . This result indicates that, in the ranges of Ar 1 and Ar 2 investigated here, the evolution of the velocity of the trailing bubble with the separation distance follows a unique master curve, provided the velocity is normalized with the velocity of the leading bubble and the separation distance with the viscous length scale associated with the leading bubble. This result fully reveals the crucial role of the wake of the leading bubble in the interaction process. Note that, for comparison, data from a single experiment is also presented. These data are not as smooth as the averaged velocity due to the shape oscillations of the body but also, in some cases, due to the possible lack of alignment of the two bubbles and associated slight horizontal motion.

During the entire process, the width and the curvature of the bubbles evolve. 1/R of the bubbles, normalized by the leading bubble diameter d 1 as a function of the separation distance. During the approach of the trailing bubble, from about four to two equivalent diameters apart (e.g., frames 1-4 in Fig. 2), the top bubble does not change its shape significantly. The constant velocity of the first bubble, thus, is associated with a constant front curvature as can be expected from potential flow theory [7]. The trailing bubble, on the contrary, experiences a pronounced change in shape. It first becomes narrower, which causes the curvature to increase as can be seen in Fig. 4. At y/ l ν ≈ 0.2, the width of the trailing bubble starts to increase, while its curvature and velocity start to decrease. As the bubble continues to approach the leading bubble, it becomes wider and slows down. In the final stage of the approach, the liquid between the two bubbles is pushed out, no immediate coalescence occurs, and the leading bubble adjusts itself in order to accommodate for the trailing bubble by becoming slightly wider (Fig. 4). The bubbles adapt the shape of their interface and match each other's curvature.

Figure 5 shows an overview of the bubbles just before they coalesce. Most of the liquid between the bubbles has been drained, and the shape of the two bubbles together closely resembles a single large bubble. In this situation, the drag of the pair is very close to the leading bubble drag (C d ≃ 3π and comparable velocities), whereas the drag of the pair is larger as long as the two bubbles have separated wakes. In addition, note that the bubbles are not always vertically aligned, despite being injected through the same nozzle, but in all cases, the trailing bubble is captured by the leading one.

The final stage of coalescence is the merge of the interfaces; the fluid between the two bubbles has thinned enough so that nonhydrodynamical forces trigger the film rupture [START_REF] Probstein | Physicochemical Hydrodynamics: An Introduction[END_REF]. The drainage has been observed to be in several forms, depending on the geometry of the bubbles as can be seen in Fig. 6. Film drainage can start at one end and then move across the entire bubble (see Fig. 6) or start in the middle upon which the fluid is evacuated in two directions. It is still an open question whether the fluid is drained partly in the films in between the bubble and the glass or in the sole plane of the cell. A thin liquid film exists between the moving bubbles and the walls. The thickness of this liquid film can be estimated by h/e ≈ Ca 2/3 /(1 + Ca 2/3 ) [8,[START_REF] Aussillous | [END_REF], where Ca = ρνV ∞ /σ is the capillary number. For the largest bubbles of our experiments, this gives a film thickness of h = 25 µm. In the experiments, we used demineralized water, and the scaling law giving the velocity of the isolated bubble (Re = 0.42 Ar) suggests that the liquid speed in the films is negligible, indicating that a shear-free condition applies at the air-water interface of the thin films [7,8]. When the film separating the two bubbles is uniform (absence of a rim) as in the upper sequence of Fig. 6, we found the speed of the moving interface in the frame of reference of the bubble and along the curved film to be constant and about v d ≃ 1.65 m/s. This measure was obtained with a time step of 0.5 ms over a length of the retracting film of 3 cm. Assuming that the drainage occurs in the plane of the cell and that the motion in the thin film is of Darcy type, i.e., that it results from a balance between pressure gradient and viscous friction at the walls, the mean drainage velocity in the gap (thickness e) is given by v d = e 2 12ρν ∂P ∂s , s being the curvilinear abscissa along the film. The pressure gradient in the liquid film ∂P ∂s can be related to the difference in curvature along the 3D interface using Laplace's law. Considering that, in the gap, the bubble curvature is fixed everywhere by thickness e, the pressure gradient at leading order is driven by the change in the plane of the cell (over the length scale d) of the bubble curvature due to the local merging. An order of magnitude of ∂P ∂s , thus, is 1 d σ w , where the film thickness w is smaller than the radius of curvature of the bubble at the film exit (w ≪ d, see Fig. 6). This leads to v d ≃ σ 12ρν e 2 wd , which is O(1) m/s for w ≈ e. A specific investigation should be carried out in the future to accurately measure the 3D geometry of the film and to verify that inertial effects can be neglected.

Accurate simultaneous measurements of the kinematics and of the deformation of two large bubbles rising in line allowed us to identify and to characterize the following different stages of interaction of the bubbles: (i) the trailing bubble is accelerated by the long-range wake of the primary bubble; (ii) the second bubble enters the recirculating wake of the leading bubble, undergoes horizontal contraction, and decelerates; (iii) the bubbles adapt their shape to each other, in particular, their curvatures are significantly modified; (iv) the shape of both bubbles together resembles a single bubble, and the liquid between the bubbles is squeezed out; and (v) the liquid film breaks, and the bubbles merge. The quantitative results presented here for each stage may provide a valuable test for future theoretical and computational papers on the road to predict bubbles' attraction and coalescence.

8 FIG. 2 .

 82 FIG. 2. (Color online)Overview of the trajectories of two coalescing bubbles (Ar 1 = 16 700 and Ar 2 = 8600). The trailing bubble is entrained in the wake of the leading bubble (1-5); the bubbles adapt their shapes(6) and coalesce forming a single bubble(7,8).

FIG. 3 .

 3 FIG. 3. (Color online) Vertical velocity of the trailing bubble (top lines) and of the leading bubble (bottom lines) normalized by the terminal velocity of an isolated bubble of the same size as the leading bubble. . denotes averaging over multiple experiments. (Darker solid lines) Results averaged over 40 experiments and (darker dashed lines) data from a single experiment (Ar 1 = 15 450 and Ar 2 = 8500). The green (light gray) curves compare two sets of experiments, both for 7500 < Ar 2 9000 ( Ar 2 = 8437) and two different ranges of Ar 1 , the dashed line for 11 010 < Ar 1 < 12 800 ( Ar 1 = 11 806), and the solid line for 15 950 < Ar 1 < 17 520 ( Ar 1 = 16 685).

FIG. 4 .

 4 FIG. 4. (Color online) (a) Evolution of the normalized width of the bubbles during approach. Top and bottom lines correspond to the leading and trailing bubbles, respectively. (b) Curvature of the bubbles as a function of separation distance. Top, middle, and bottom lines correspond to the normalized curvature at the top of the trailing bubble, top of the leading bubble, and bottom of the leading bubble, respectively. (Solid lines) Results averaged over 40 experiments and (dashed lines) results from a single experiment (Ar 1 = 15 450 and Ar 2 = 8500).

FIG. 5 .

 5 FIG.5. Overview of different pairs of bubbles just prior to coalescence showing how the bubbles adapt their shapes to each other. Note that each pair of bubbles is shaped like a single big bubble (Ar 1 ≈ 11 000 and Ar 2 ≈ 7000).

FIG. 6 .

 6 FIG. 6. Two sequences of film drainage. (Top three images) The liquid ligament is retracting at a constant velocity. (Bottom images) The film changes geometry halfway, and the fluid is collected in a rim. The scales on the right equal 1 cm.

We thank M. Roudet for performing the PIV measurement and S. Cazin for technical support concerning high-speed imaging. We also thank the E.U. Erasmus Program, D. Lohse (University of Twente, The Netherlands), and D. Legendre (INPT, France) for the training grant allocated to S.G.H.