Research Topics

Research Topics

The Timber Modeling Paradigm

Motivation

With the advances of technology towards ambient intelligence and pervasive computing the complexity of embedded systems increase beyond the design of single devices. Traditional design methodologies and tools for embedded system design are simply not up to this task. The need for a shift of paradigm is further stressed by the industrial demands of increased productivity and shorter time to market etc. This is a widely accepted fact acknowledged by both academia and industry. The general trend goes towards executable models, that is, design specification and exploration (modeling) at a high level of abstraction, from which synthesis is carried out for a target technology (deriving an executable).

Vision statement

We seek a design methodology allowing the engineers to collaborate in the design of embedded systems on terms familiar to their disciplines; digital design, signal processing, control and computer communication to name a few. The design methodology should;

o provide prompt means to express the timely behavior of distributed (loosely coupled) embedded systems in context of their physical environment, in a semantically well defined framework allowing formal reasoning,

o provide tools to synthesize such specifications into semantically equivalent and state of the art quality software and hardware descriptions, and

o provide tools for formal analysis of complexity and resource requirements.

Methodology

Our approach Timber, adopts the reactive paradigms proven successful to hardware description languages (such as Verilog and VHDL), and offers abstractions of modern functional programming languages, e.g., higher order functions, type inference and objects. In effect, algorithms (control, DSP, communication, etc.) are promptly captured in Timber by concepts of reactive objects and timed events - thus we provide engineers with a common ground for interdisciplinary collaboration. Timber descriptions can also incorporate modeling of the systems environment, allowing reasoning about the timely behavior of the complete system. This way, we envision Timber to enable powerful hardware software co-design space exploration under a semantically well defined framework. Ultimately, the system description can be synthesized into realizations with minimal resources (with respect to silicon area, CPU requirements, power consumption, memory requirements, etc.) yet guaranteed by formal methods to be correct and robust under all foreseeable circumstances derived from the specification.

Research

Although Timber itself does not imply any specific way of realization (e.g., ASIC, FPGA, single-CPU, multiple-CPU, etc.) or any combination of the mentioned is possible, a fair assumption is that a majority of embedded systems are based on single-CPU systems, (this is especially true for the Embedded Internet System devices currently under development at EISLAB). Even under this limitation, the road is paved with numerous research challenges. In the following a number of topics are shortly presented:

Dynamic memory management in Timber

Scarce memory resources is a common factor to embedded systems often putting a limit on their functionality. Traditional (manual) memory management is a delicate, time consuming and error prone task, which may be remedied by the unique opportunities for automated memory management inherent to Timber.

o We develop techniques for sound dynamic memory management in the context of real time systems. The approach is a low granularity, incremental, copying garbage collector exploiting idle periods of the reactive system. This way, responsiveness can be achieved while maintaining a relatively low memory and CPU overhead.

o We develop tools for dynamic memory analysis, both with respect to memory consumption and CPU overhead. The Timber semantics allows methods from static program analysis together with scheduling theory to be applies in a single framework.

Stack space management in Timber

Traditionally, multi-threaded systems require multiple stack spaces. For embedded systems with scarce memory resources, this becomes a limiting factor as stacks are pre-allocated and a memory overhead is enforced. However, multi-threading is a sought after feature, especially in the context of reactive systems. Traditional design methodologies undertake different approaches to the problem, often limited in the context of real-time systems. However, Timber offers opportunities for overcoming this problem.

o Under the Stack Resource Protocol (SRP) threads are allowed to share a common stack, hence the memory overhead of static stack allocation can be eliminated. We investigate how the theory of SRP can be applied to Timber. Key to this work will be dependability exploration of Timber models through concepts of program analysis.

o Small Embedded systems usually have uniform memory access (i.e. do not comprise complex caching mechanisms). In this context, heap based stack allocation does not suffer from performance loss due to lack of locality (which is the showstopper for heap based allocation in the general case). This offers an opportunity to overcome the static stack memory overhead without the priority inversion due to stack issues limiting the applicability of SRP.

Code synthesis of Timber models

Efficiency (code footprint, CPU load and power consumption) is another key issue when addressing embedded system design with scarce memory, CPU, and power resources. Minimalistic operating systems paired with applications written in C or assembly languages are traditionally considered to be the state-of-art when it comes to efficiency. However, with the advances in compiler technology, the advantage of assembly programming is nowadays considered to be marginal (if any), out ruled by the clear disadvantages when it comes to portability, robustness, and code maintenance. Following this trend, Timber opens up for further abstractions (with higher order functions and object oriented constructs), yet offering opportunities for more aggressive optimizations than adopted in traditional design methodologies.

o We work towards a fully fledged real time Timber kernel, that will be tailored (optimized) to the application. Hence, Timber applications will run natively on the target platform without any additional underlying OS or third party code, hence total control of the system is achieved. Porting requires only changes to the hardware specific parts of the application in addition to minimal changes to the kernel. (Note, that Timber does not cloud the hardware from the programmer in the form of OS constructs, instead device drivers and such are considered as integral to the application, hence the complete implementation is opaque and analyzable).

o We will investigate how the well defined and relatively simple semantics of Timber can be exploited for aggressive supercompilation optimization. Supercompilation is a technique that applies heavy inlining, partial evaluation and folding on a global basis, thus, holds the potential to look further than the scope of optimization foreseeable by any programmer.

o Inherent to the reactive paradigm of Timber, the system will eventually become idle after processing an external interrupt or timed event. During idle time, the system can either be put into low-power mode or be used to perform garbage collection (of the dynamic memory). In either case, the system should stay agile to meet the deadlines and memory requirements of possible future events. We will investigate the opportunities for adaptive power save techniques, that by context awareness (pending timed messages, state of memory manager, etc.) minimizes garbage collection work while ensuring robustness.

Component based design

Component based design (CBD) has gained momentum in the field of software engineering and has shown to bring advantages both with respect to productivity and quality for the design of complex systems. For CBD o reach the realm of real time systems, a number of fundamental questions needs to be addressed, in particular; o Timing. For real time systems, we need to device a component model able to capture the timing behavior in a composable manner. o In the context of embedded systems, we need to device a component model able to capture discrete interaction with the environment.

Timber semantics for distributed systems

Currently the semantics of Timber captures hard real-time systems with tightly coupled communication. Although, this maps well onto many embedded real-time applications, the advent of ambient intelligence and ubiquitous computing is about change this picture drastically. Whereas, the communication interior to a single node is tightly coupled (i.e., the communication can be considered immediate and lossless) the communication between (wirelessly) networked nodes is not! A common way to deal with this problem is to infer middleware to deal with the discrepancy between inter and intra node communication. However, the semantics of such middleware has yet to be seen until formal methods for system analysis can be applied. We advocate to undertake a reactive approach, and hence view inter node communication simply as incoming events to which the node reacts. As Timber is capable of capturing both the application and its environment, the communication channel is given simply as a transfer function, introducing suitable noise figures, bit faults or packet loss, to the level of abstraction of the model at hand. In this way, the loosely coupled communication can be adequately captured inside the well defined semantics of Timber. However, the question how to analyze and present this complex interaction between loosely coupled nodes is an open question.

Timber in Embedded Internet Systems

The realization of Embedded Internet Systems (EIS) is manifested by current and upcoming MULLE devices. The current generation features Bluetooth (BT) and Zigbee (ZB) as the wireless communication interfaces. BT/ZB and TCP/IP stacks are used for communication with http:/web interfaces for configuration and high level communication. Current software implementations (lwBT/lwIP/lwWeb) are based on traditional C programming. Research and development for Timber based stacks are ongoing;

o BCSP stack in Timber, is at a beta stage developed and tested on a previous interpreting Timber tool. BCSP offers direct control over the internal BT stack layers, hence is more efficient and provides support for low-power operation.
(Håkan Evertsson, Masters thesis 2005).

o TCP/IP stack in Timber, is at an alpha stage. During the computer communication project course 2004, a group of students set out to implement a TCP/IP framework. The students successfully implemented the IP communication, TCP timers etc. remains though.

Service Discovery

Service discovery, service integration and security are other key issues to the realization of EIS. We undertake an approach based on standardized open protocols (e.g. TCP/IP and Bluetooth) to ensure ease of integration and compatibility with current and future infrastructures.

o Our survey of Service Discovery Protocols (SDPs) indicates Bonjour (zero-configuration) as suitable with respect to functionality, infrastructure and implementation. A working prototype has been demonstrated on the MULLE platform.

o Service integration and security are currently under survey. One promising technology under investigation is Semantic Web and Web Services. Together they offer an interesting framework for secure man-machine and machine-machine services over the Internet.

Case Studies of EIS Technology

EIS technology has already proven successful to many application areas, e.g. medical monitoring, industrial monitoring and control, security and surveillance systems, etc. In many cases interesting research topics arises when disciplines are crossed.

o The MULLE platform provides support for reactive sensing, control and communication. The platform is under constant development, with the goal to minimize power consumption and size, while offering adequate sensors, actuators and interfaces for specific applications.

o The field of medical monitoring is huge, two related monitoring topics under current research is fall and gait detection. In both cases accelerometer data are collected and signal processing algorithms applied to extract refined information. Such applications servers multiple purposes;

- they create real life demonstrators of the technologies applied

- they give feedback on, and experience, of practical issues such as user interfaces, robustness issues (physical and functional) etc. useful to pinpoint strengths and weaknesses

- they enable interdisciplinary research and collaboration, in this case studies together with the division of healthcare at LTU.

MULLE : a wireless Internet enabled sensor networking platform

The MULLE is a Bluetooth-based sensor node which utilizes standardized protocols such as TCP/IP for communication. The MULLE architecture is a versatile generic sensor platform, capable of measuring and controlling its enviroment.

The MULLE architecture has a number of key properties:

o Interoperability. The use of Bluetooth and TCP/IP enables the MULLE to communicate with a wide range of devices, ranging from PDAs and computers to mobile phones. Furthermore, the use of the TCP/IP protocol suite provides global communication using Internet technology.

o Zero-configurating networking. A sensor network based on the MULLE architecture provides both device and service discovery. This enables a MULLE to automatically obtain an IP-address as well as locating other nodes and services in the local network and on the Internet.

Design Environment for Reactive Real-Time Systems

Integrated Design Environments (IDEs) are widely used for aiding in the process of complex system design. In the context of the Timber language we aim to develop. o A graphical representation for Timber programs. Finding a suitable balance be o A tool allowing interactive and incremental design of Timber programs.