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)

Programming Abstractions with Debugging Support for Resource-Constrained Devices

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.

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.

Meta-Debugging Pervasive Computers

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.

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.

C++ and the linker

Quite some time ago I found a brillant and extensive article about linkers from Ian Lance Taylor. (see the appendix for a list of links to all 20 parts.) In part 13 he says: "There are some special challenges when using C++", and he is definitely right. I would like to elaborate on what theses challenges are and how the linker can be a serious trap for C++ developers. I learned it the hard way by spending hours and days on bug-hunting. Maybe this article will help others to avoid the frustration.

Simulation of Channel Codes

Part 1:

Design und Implementierung eines Frameworks für Simulationen in der Kanalcodierung mit Anbindung an ein verteiltes System
Alexander Bernauer
Institute of Communications Engineering, University of Ulm

Part 2:

Entwurf und Implementierung eines verteilten Systems mit Benutzerschnittstelle zur Erstellung, Verteilung und Verwaltung von Simulationen in der Kanalcodierung

Stephanie Wist

Institute of Communications Engineering, University of Ulm

Links:

• github project
• appended data of part 1

The COMPASS Location System

The COMPASS Location System
Frank Kargl, Alexander Bernauer
First International Workshop on Location- And Context Awareness (LoCA 2005)
vol. 3479/2005, Oberpfaffenhofen, Germany, Springer LNCS 3479/2005, 05/2005

Windows Messages

Windows Messages
Alexander Bernauer
Datenschleuder #86, Seite 27-29

Article:

Die meisten Hacker beschäftigen sich kaum mit Microsoft Betriebssystemen. Gründe dafür gibt es genug, die meisten davon sind mehr als verständlich. Doch es gibt auf diesen Systemen viel zum Spielen, so dass es sich lohnen könnte, einen genaueren Blick darauf zu werfen. Ein Beispiel dafür ist das Design der grafischen Benutzeroberfläche. Mit den einfachsten Mitteln kann man hier Programme manipulieren, wobei erfahrungsgemäß die wenigsten Entwickler mit diesem Angriffsvektor rechnen.
Windows ist ein ereignisgesteuertes System. Ereignisse erzeugen Nachrichten, die vom System an das betreffende Fenster weitergeleitet werden. Unter Windows kann jeder Thread ein oder mehrere Fenster öffnen, wobei jedes Fenster einen systemweit eindeutigen "WindowHandle" besitzt. Ein Fenster kann der Vater eines zweiten Fensters sein kann, so dass die Menge aller Fenster einen Baum mit dem Desktop als Wurzel bilden. Jedes Fenster gehört zu einer Fensterklasse. Bestandteil einer Fensterklasse ist u.A. die Routine, die eingehende Nachrichten behandelt. Diese Routine wird üblicherweise "WindowProc()" genannt.

Personal Firewalls

Personal Firewalls,
Ansgar Wiechers, Alexander Bernauer
Datenschleuder #86, Seite 30-35

Article:

Der CCC Ulm und der Chaostreff Bad Waldsee haben alle gängigen Personal Firewalls daraufhin getestet, ob das versprochene Mehr an Sicherheit erreicht wird. Das Ergebnis verwundert einen Experten nicht, ist aber für den Laien erstaunlich.

The COMPASS Location System

The COMPASS Location System

Frank Kargl, Alexander Bernauer

Workshop on Location- and Context-Awareness (LoCA 2005)

Links:

• github project
• slides

The Danger of Software Patents

Die Gefahren der Softwarepatente
Alexander Bernauer
Datenschleuder #85, Seite 10-14

Article:

Der CCC Ulm hat zwei Chaosseminare zum Thema Softwarepatente veranstaltet. Am 13. Oktober 2003 hat Christian Cremer, Patentanwalt aus Neu-Ulm, das Patentsystem allgemein und den Übergang zu Softwarepatenten aus seiner Sicht als Patentanwalt dargestellt. Am 4. November 2004 hat Richard M. Stallman einen Vortrag über die Gefahren derSoftwarepatente gehalten. Stallman ist als Gründer der Free Software Foundation und der GNU Bewegung besonders engagiert im Kampf gegen Softwarepatente. Jedoch wird nicht nur freie Software von Softwarepatenten bedroht, sondern fast alle, die im Bereich Informationstechnik tätig sind, und im Grunde auch jeder Endanwender. Dieser Artikel greift die Inhalte und die Argumentationen aus beiden Vorträgen auf und gibt einen Überblick über Softwarepatente und ihre Konsequenzen.

A Fragmentation Protocol for CAN

A fragmentation protocol for CAN (german) (erratum)
Alexander Bernauer
Abteilung für Rechnerstrukturen, University of Ulm

Links:

• github project
• CAN

Controller Area Network (CAN)

CAN - Controller Area Network
Alexander Bernauer
Datenschleuder #83, Seite 24-27

Article:

CAN ist ein Standard für echtzeitfähige Bussysteme. Mitte der Achtziger wurde er in den ersten Luxuslimusinen eingebaut und ist heutzutage aus keinem modernen Automobil mehr wegzudenken. Typischerweise existieren in einem Auto mehrere getrennte CAN Busse mit unterschiedlichen Geschwindigkeiten. Ein Low Speed CAN (ISO 11519-2) mit maximal 10 kBit/s erlaubt Funktionalitäten im sog. Chassis-Bereich. Dazu gehört u.a. das Ein- und Ausschalten von Lichtern und Blinkern, das Verstellen der Sitzposition und der Außenspiegel, die Türverriegelung und andere Komfortfunktionen. Ein zweiter Low Speed CAN erlaubt den Austausch von höherem Informationsaufkommen mit bis zu 40 kBit/s. An diesem Bus hängen u.a. die Anzeigen des Amaturenbretts und die Klimatisierung. Echtzeitkritische Systemem kommunizieren über einen High Speed CAN (ISO 11898-2) mit bis zu 1 MBit/s, der maximalen Transferrate für CAN. Zu diesem Sytemen gehören z.B. die Motorsteurung und die Stabilitätskontrolle.

Free Haven

Free Haven (german)
Alexander Bernauer
Seminar on P2P-Technologies, Institute for Media Informatics, University of Ulm

Links:

• Free Haven
• Institute for Media Informatics
• University of Ulm

Platform FPGA Virtex II Pro

Platform FPGA Virtex II Pro (german)
Rouven Radtke, Alexander Bernauer
Seminar, Institute of Neural Information Processing, University of Ulm

Links:

• Platform FPGA Virtex II Pro
• Institute of Neural Information Processing
• University of Ulm