Compiler-Assisted Thread Abstractions for Resource-Constrained Systems

Summary

Major operating systems for wireless sensor networks (WSN) enforce an event-based programming paradigm for efficiency reasons. However, practice has shown that the resulting code complexity is hard to manage for software developers and leads to difficult problems during development, deployment, and operations. Thus, thread libraries for WSN applications have been introduced, but the efficiency constraints of the domain often lead to glaring restrictions of the supported thread semantics.

In contrast, compiler-assisted thread abstractions support threads without actually using threads at runtime. Instead, the thread-based code is automatically translated into equivalent event-based code. Currently, two different systems implement this idea, but both have severe limitations regarding both the thread semantics and the tool support.

Our goal is to demonstrate the potential of compiler-assisted thread abstractions by taking the next step and introducing a comprehensive system of compiler and debugger which supports cooperative threads with minor restrictions and which is also platform independent.

A Haskell-based compiler prototype shows the feasibility of our approach and preliminary results demonstrate that the generated code is efficient enough to be executed on wireless sensor network devices. Furthermore, existing optimization potential suggests that compiler-assisted thread abstractions can indeed outperform runtime-based solutions and compete with hand-written event-based code. We are currently working on completing the implementation of the tools and verifying these points by means of an extensive evaluation.

Compiling Business Process Models for Sensor Networks

Wireless sensor networks are increasingly being used to improve business processes. The behavior of such a process is usually captured in models while its implementation is typically created manually. Besides being expensive, this approach entails deviations between the model and the implementation of a business process, thus rendering it less effective. We aim at closing this gap by automatically generating applications from the model of the process instead. In our approach, software developers provide building blocks that are used by business analysts to model business processes and hereby effectively control their execution on an abstract level. Furthermore, the model editor integrates a compiler and a simulator so that the business analysts can test and debug the modeled processes on the same level of abstraction. Our evaluation results show that the generated code can be executed on resource-constrained sensor nodes consuming only 1% more energy than the hand-written equivalents. However, the benefits of our approach come at the price of 10% more RAM and 44% more flash space consumption on average.

A Comprehensive Compiler-Assisted Thread Abstraction for Resource-Constrained Systems

While size and complexity of sensor networks software has increased significantly in recent years, the hardware capabilities of sensor nodes have been remaining very constrained. The predominant event-based programming paradigm addresses these hardware constraints, but does not scale well with the growing software complexity, often leading to software that is hard-to-manage and error-prone. Thread abstractions could remedy this situation, but existing solutions in sensor networks either provide incomplete thread semantics or introduce a significant resource overhead. This reflects the common understanding that one has to trade expressiveness for efficiency and vice versa. Our work, however, shows that this trade-off is not inherent to resource-constrained systems. We propose a comprehensive compiler-assisted cooperative threading abstraction, where full-fledged thread-based C code is translated to efficient event-based C code that runs atop an event-based operating system such as Contiki or TinyOS. Our evaluation shows that our approach outperforms thread libraries and generates code that is almost as efficient as hand-written event-based code with overheads of 1% RAM, 2% CPU, and 3% ROM.

• A Comprehensive Compiler-Assisted Thread Abstraction for Resource-Constrained Systems
• Alexander Bernauer, Kay Römer
• Proceedings of the 12th ACM/IEEE Conference on Information Processing in Sensor Networks (IPSN 2013)

Threads2Events: An Automatic Code Generation Approach

There is a long-standing dispute on whether and when thread-based programming should be preferred over the event-based paradigm. This dispute has also extended into the wireless sensor networks domain. Many existing operating systems rely on events due to their efficiency, but make code management difficult. Others rely on threads for developer comfort, but at the cost of reduced runtime efficiency. In this paper we try to combine the best of both worlds by offering a full-fledged cooperative thread abstraction with blocking I/O to the C programmer that is compiled into efficient event-based code. We present the basic code transformations and investigate their efficiency using a representative application case study. We find that RAM usage of generated code competes with hand-written code, but further optimizations are required to reduce the code size and the number of CPU cycles.

Threads for the Programmer, Events for the Machine

Major motes operating systems like TinyOS or Contiki rely on an event-driven programming paradigm. While the use of events allows for limiting memory usage on resource-constrained motes, it may also hamper the development and debugging of applications, especially as their complexity increases [Dunkels2006]. Several authors also investigated the possibility of introducing threads to mote programming [McCartney2009, Duffy2007, Klues2009]. However, the proposed solutions all induce runtime overhead which is inherent to the thread paradigm. In contrast, protothreads combine the benefits of both paradigms by providing thread semantics to the programmer while using events at runtime. This is achieved by an automatic code generation step performed by the C preprocessor. However, while using the C preprocessor guarantees portability across C compilers, it also introduces some limitations. For instance, certain C language constructs such as switch statements may not be used and values of local variables are not retained across context switches. Furthermore, thread functions are not reentrant, blocking calls may only occur in the top-level thread functions, and debugging is performed in the generated code.
To overcome these limitations, we propose to extend the protothreads abstraction by providing cooperative threads with blocking I/O, reentrant functions, and arbitrary nesting of function calls. This is achieved by a comprehensive compiler which translates thread-based code into efficient event-based code. In order to guarantee the efficiency of the generated code there are still some limitations, though. First, the exact number of threads must be known at compile time. Second, recursive functions must not invoke blocking functions. And third, function pointers must not be used to invoke functions that directly or indirectly invoke blocking functions. We argue, though, that these limitations do not severely affect programming of motes as these constructs are rarely used. Furthermore, the compiler can reliably detect any violations of those restrictions.

lock-free dynamic memory allocation

In 2004 Maged M. Michael introduced the first lock-free dynamic memory allocation.

According to his benchmarks his implementation outperforms standard memory allocation libraries. For me this is the main advantage of non-blocking synchronization for high-load systems. Simply by avoiding taking locks things speed up considerably.

Maged M. Michael released his implementation into open source through the Amino - Concurrent Building Blocks project.

non-blocking synchronization

One of my current fields of interest is non-blocking synchronization. Wikipedia has a good introductive article on this topic. Non-blocking synchronization is of interest for pervasive computing because this technique among other things makes software more robust as it avoids dead-locks and inversions of priority, which are well-known problems of embedded software.

As far as I know the fundamentals of this topic origin from Maurice Herlihy, published first on 1991 in his paper wait-free synchronization.

RIOT

RIOT (german)
Alexander Bernauer
CCC Ulm

Multiprocessors and Multithreading

Multiprocessors and Multithreading (german)
alex, uli, schabi
/dev/radio

Multiprocessors and Multithreading

Multiprocessors and Multithreading (german)
Alexander Bernauer, Markus Schaber
CCC Ulm