2.4263102175e-12

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)

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.
Continue reading →

Quite some time ago I read the Programming in Scala and the Programming Scala book and decided to offer a student lab on a Scala-based implementation of a Reversi tournament framework. One part of this framework is a DSL for the configuration of a tournament. So I went on and investigated the Scala techniques that allow for the construction of internal DSLs. Although there is quite some information on the internet and in the books about Scala DSLs here is what I came up with to get my student started.

Continue reading →

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.

Continue reading →

I have recently worked quite a bit with the language workbench MPS and I think it’s about time to note the experiences I have made and the background knowledge I have collected.

Continue reading →

I am currently writing an implementation of the C99 programming language as a basic language for the MPS language workbench. I call this implementation c-base, because it is intended to be used as a target language for code generation, much like MPS’ Java-like base-language.

I created the model of this MPS language according to the C99 standard grammar. Thus, I had to dive into its documentation and I have found a number of surprising features and properties of the C99 programming language. Not all of them are important, but if you want to be nitpicker in the next C discussion, here is your ammo

So, did you know, that

Continue reading →

Abstractions are crucial in order to manage complex systems. In pervasive computing, though, common programming abstractions tend to be too expensive for the employed resource-constrained devices. In recent years, the wireless sensor network community has proposed several solutions to this problem. However, little has been done to also support debugging on the level of the abstraction. Instead, a developer is forced to understand the lower-level details in order to find and correct defects. This clearly hampers the development of applications. We aim at advancing the state of the art in programming of resource-constrained devices by introducing debugging support for programming abstractions.

Continue reading →

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.

Continue reading →

As computers get more complex, the task of programming them gets more complex as well. This is especially true
for the “Pervasive Computer”, which is a massively distributed system consisting of unreliable embedded devices that communicate with each other over lousy wireless links. A common approach to address the programming problem is to offer programming abstractions that hide certain aspects of the complexity from the programmer. While several such abstractions and mappings thereof to low-level target languages have been proposed, there is a glaring lack of debugging support. It is typically impossible to debug at the conceptual level offered by the programming abstractions, instead one has to resort to debugging the generated target code. In this position paper we argue that programming abstractions should be designed in a way that allows debugging at the same conceptual level as programming. We further present requirements for such debugging tools, a taxonomy of programming abstractions and discuss debugging
challenges, existing solutions, and potential approaches in each class.

Continue reading →

For my current work I need to show how efficient the generated code is. Fortunately the binutils include a tool called size which “lists the section sizes of an object or archive file”.

In order to have representative results I should compile for a platform which is typical for the WSN community. I have chosen the MSP430 because there is a package of a GCC cross compiler for that target in the TinyOS Ubuntu repository.

At first, the numbers looked promising. But at a closer look something was wrong. Investigating the problem emerges something weird.

Continue reading →