We introduce model folding, a novel data-free model compression technique that merges structurally similar neurons across layers, significantly reducing the model size without the need for fine-tuning or access to training data. Unlike existing methods, model folding preserves data statistics during compression by leveraging k-means clustering, and using novel data-free techniques to prevent variance collapse or explosion. Our theoretical framework and experiments across standard benchmarks, including ResNet18 and LLaMA-7B, demonstrate that model folding achieves comparable performance to data-driven compression techniques and outperforms recently proposed data-free methods, especially at high sparsity levels. This approach is particularly effective for compressing large-scale models, making it suitable for deployment in resource-constrained environments.

Multitask real-time embedded systems are often restricted by tight energy budgets, whilst they usually have environmental interactions through software-controlled energy-hungry peripheral modules like LTE, WiFi, and GSM. The way that the driver calls are used within the embedded software to do such a control introduces program energy-hotspots (EHs) from the peripheral module perspective, namely the code pieces wasting the system energy. By the energy waste, we mean that the energy consumption is reducible via some program code modifications without threatening the system schedulability and logical correctness. This paper examines the program EHs of fixed-priority real-time tasks where two types of energy inefficiency can occur: Intra-task type, causing energy waste even if a task runs individually, and inter-task type, happening due to the interaction between different system tasks, namely preemption scenarios even if there is no intra-task EH. The main cause of such EHs is the unnecessary time intervals between the driver calls, causing extra energy consumption by peripheral modules. We propose some static analysis methods to automatically detect and eliminate both types of intra-and inter-task EHs regarding their mutual relevance, according to the extreme (worst-case and best-case) execution times of certain task code parts. Our manipulations on the tasks to eliminate the EHs include some program code modifications with the awareness of system schedulability and logical correctness, and changing some scheduling decisions, namely limiting the preemption points. After applying our proposed method to the test tasks, our simulation results show an energy reduction of up to 19 percent.

Low-power wireless networks have the potential to enable applications that are of great importance to industry and society. However, existing network protocols do not meet the dependability requirements of many scenarios as the failure of a single node or link can completely disrupt communication and take significant time and energy to recover. This paper presents Hydra, a low-power wireless protocol that guarantees robust communication despite arbitrary node and link failures. Unlike most existing deterministic protocols, Hydra steers clear of centralized coordination to avoid a single point of failure. Instead, all nodes are equivalent in terms of protocol logic and configuration, performing coordination tasks such as synchronization and scheduling concurrently. This concept of concurrent coordination relies on a novel distributed consensus algorithm that yields provably unique decisions with low delay and energy overhead. In addition to a theoretical analysis, we evaluate Hydra in a multi-hop network of 23 nodes. Our experiments demonstrate that Hydra withstands random node failures without increasing coordination overhead and that it re-establishes efficient and reliable data exchange within seconds after a major disruption.

Spatial-temporal graph models are prevailing for abstracting and modelling spatial and temporal dependencies. In this work, we ask the following question: whether and to what extent can we localise spatial-temporal graph models? We limit our scope to adaptive spatial-temporal graph neural networks (ASTGNNs), the state-of-the-art model architecture. Our approach to localisation involves sparsifying the spatial graph adjacency matrices. To this end, we propose Adaptive Graph Sparsification (AGS), a graph sparsification algorithm which successfully enables the localisation of ASTGNNs to an extreme extent (fully localisation). We apply AGS to two distinct ASTGNN architectures and nine spatial-temporal datasets. Intriguingly, we observe that spatial graphs in ASTGNNs can be sparsified by over 99.5% without any decline in test accuracy. Furthermore, even when ASTGNNs are fully localised, becoming graph-less and purely temporal, we record no drop in accuracy for the majority of tested datasets, with only minor accuracy deterioration observed in the remaining datasets. However, when the partially or fully localised ASTGNNs are reinitialised and retrained on the same data, there is a considerable and consistent drop in accuracy. Based on these observations, we reckon that (i) in the tested data, the information provided by the spatial dependencies is primarily included in the information provided by the temporal dependencies and, thus, can be essentially ignored for inference; and (ii) although the spatial dependencies provide redundant information, it is vital for the effective training of ASTGNNs and thus cannot be ignored during training. Furthermore, the localisation of ASTGNNs holds the potential to reduce the heavy computation overhead required on large-scale spatial-temporal data and further enable the distributed deployment of ASTGNNs.

Embedded nodes in future cyber-physical systems are mostly self-powered, scavenging their required energy from the environment. The environmental sources of energy are usually variable, so that some prediction methods are employed to proactively adapt to the variable harvesting energy. However, prediction errors may surprise the system with some unpredicted changes, needing appropriate reactions. We consider an energy-harvesting real-time system with periodic tasks of multiple performance levels. An energy-resilient scheduler is proposed for the system to react to the unpredicted changes such that the system is survivable, recovers from such a change in a timely manner, and appropriately controls its performance degradation. After the recovery, however, the energy-resilient scheduler preserves the system survivability and maximizes its performance in a prediction time horizon, while it will be ready for another surprise. We provide some theoretical properties and a feasibility test which are used in the design of the energy-resilient scheduler. Our simulations show that the proposed resilient scheduler outperforms well-known performance maximization methods, effectively approximates the optimal solution, and reacts appropriately against surprises of high severity.

Distributed embedded systems are pervasive components jointly operating in a wide range of applications. Moving toward energy harvesting powered systems enables their long-term, sustainable, scalable, and maintenance-free operation. When these systems are used as components of an automatic control system to sense a control plant, energy availability limits when and how often sensed data are obtainable and therefore when and how often control updates can be performed. The time-varying and non-deterministic availability of harvested energy and the necessity to plan the energy usage of the energy harvesting sensor nodes ahead of time, on the one hand, have to be balanced with the dynamically changing and complex demand for control updates from the automatic control plant and thus energy usage, on the other hand. We propose a hierarchical approach with which the resources of the energy harvesting sensor nodes are managed on a long time horizon and on a faster timescale, self-triggered model predictive control controls the plant. The controller of the harvesting-based nodes’ resources schedules the future energy usage ahead of time and the self-triggered model predictive control incorporates these time-varying energy constraints. For this novel combination of energy harvesting and automatic control systems, we derive provable properties in terms of correctness, feasibility, and performance. We evaluate the approach on a double integrator and demonstrate its usability and performance in a room temperature and air quality control case study.

In many real-world wireless IoT networks, the application dictates the location of the nodes and therefore the link characteristics are inhomogeneous. Furthermore, nodes may in many scenarios only communicate with the Internet-attached gateway via multiple hops. If an energy-efficient short-range modulation scheme is used, nodes that are reachable only via high-path-loss links cannot communicate. Using a more energy-demanding long-range modulation allows connecting more nodes but would be inefficient for nodes that are easily reachable via low-path-loss links. Combining multiple modulations is challenging, as low-power radios usually only support the use of a single modulation at a time. In this article, we present the Long-Short-Range (LSR) protocol which supports low-power multi-hop communication using multiple modulations and is suited for networks with inhomogeneous link characteristics. To reduce the inherent redundancy of long-range modulations, we present a method to determine the connectivity graph of the network during regular data communication without adding significant overhead. In simulations, we show that LSR allows for reducing power consumption significantly for many scenarios when compared to a state-of-the-art multi-hop communication protocol using a single long-range modulation. We demonstrate the applicability of LSR with an implementation on real hardware and a testbed with long-range links.

Future mobile devices are anticipated to perceive, understand and react to the world on their own by running multiple correlated deep neural networks locally on-device. Yet the complexity of these deep models needs to be trimmed down both within-model and cross-model to fit in mobile storage and memory. Previous studies squeeze the redundancy within a single model. In this work, we aim to reduce the redundancy across multiple models. We propose Multi-Task Zipping (MTZ), a framework to automatically merge correlated, pre-trained deep neural networks for cross-model compression. Central in MTZ is a layer-wise neuron sharing and incoming weight updating scheme that induces a minimal change in the error function. MTZ inherits information from each model and demands light retraining to re-boost the accuracy of individual tasks. MTZ supports typical network layers (fully-connected, convolutional and residual) and applies to inference tasks with different input domains. Evaluations show that MTZ can fully merge the hidden layers of two VGG-16 networks with a 3.18% increase in the test error averaged on ImageNet for object classification and CelebA for facial attribute classification, or share$39.61\%$parameters between the two networks with$<0.5\%$increase in the test errors. The number of iterations to retrain the combined network is at least$17.8\times$lower than that of training a single VGG-16 network. Moreover, MTZ can effectively merge nine residual networks for diverse inference tasks and models for different input domains. And with the model merged by MTZ, the latency to switch between these tasks on memory-constrained devices is reduced by$8.71{\times}$.

Time series forecasting has widespread applications in urban life ranging from air quality monitoring to traffic analysis. However, accurate time series forecasting is challenging because real-world time series suffer from the distribution shift problem, where their statistical properties change over time. Despite extensive solutions to distribution shifts in domain adaptation or generalization, they fail to function effectively in unknown, constantly-changing distribution shifts, which are common in time series. In this paper, we propose Hyper TimeSeries Forecasting (HTSF), a hypernetwork-based framework for accurate time series forecasting under distribution shift. HTSF jointly learns the time-varying distributions and the corresponding forecasting models in an end-to-end fashion. Specifically, HTSF exploits the hyper layers to learn the best characterization of the distribution shifts, generating the model parameters for the main layers to make accurate predictions. We implement HTSF as an extensible framework that can incorporate diverse time series forecasting models such as RNNs. Extensive experiments on 7 benchmarks demonstrate that HTSF achieves state-of-the-art performances.

Wireless sensors form an integral part of the Internet of Things (IoT), standing at the edge between the cyber and physical domains. Ac-quiring and transmitting environmental data is an energy-intensive workload, especially when considering networks spanning large buildings or even cities. Many works aim to integrate energy har-vesting into wireless sensors, providing them with a greater level of energy autonomy. Initially deployed for energy-rich outdoor environments, recent advances have allowed wireless sensors to efficiently utilize the reduced energy harvested in indoor lighting conditions. This demo introduces a harvesting-based Dual Proces-sor Platform, the DPP3e, designed for energy harvesting in indoor environments. It features various sensors for advanced indoor en-vironmental sensing, e.g. air quality measurements, a low-power display for immediate visual feedback, and a powerful micro controller for energy-efficient inference of Tensorflow models. Fur-thermore, it has two separate RF interfaces: a 2.4 GHz Bluetooth Low Energy (BLE) radio for short-range communication, and a sub-GHz transceiver for long-range communication. Using configurable power domains and advanced power management, it can sustain sending BLE packets every 5 seconds while consuming only 37 µ W.

With the Internet of Things (IoT) large amounts of data can be gathered at the edge, centrally collected and subsequently utilized for various application domains. Efficient and reliable synchro-nous communication protocols are essential for automated data gathering, yet they typically require a stable energy supply. En-ergy harvesting enables long-term deployments, but it imposes widely varying energy budgets on each node in the network. To re-main efficient, synchronous protocols need to consider this energy variability. We propose a selective flooding protocol that employs low-energy communication rounds for all nodes and additional high-energy rounds only for nodes with high input power thus increasing their throughput. Low-energy rounds gather data with high reliability and maintain global network synchronization, while high-energy rounds use increased transmit power to overcome potentially-broken links that depend on low-power nodes. We eval-uate our proposed method on the FlockLab testbed and build a small network composed of standalone energy harvesting nodes. The average power consumption of almost 84 µW and 177 µW for low- and high-power nodes, respectively, are fully sustainable by indoor photovoltaic harvesting.

Data collected by IoT devices are often private and have a large diversity across users. Therefore, learning requires pre-training a model with available representative data samples, deploying the pre-trained model on IoT devices, and adapting the deployed model on the device with local data. Such an on-device adaption for deep learning empowered applications demands data and memory efficiency. However, existing gradient-based meta learning schemes fail to support memory-efficient adaptation. To this end, we propose p-Meta, a new meta learning method that enforces structure-wise partial parameter updates while ensuring fast generalization to unseen tasks. Evaluations on few-shot image classification and reinforcement learning tasks show that p-Meta not only improves the accuracy but also substantially reduces the peak dynamic memory by a factor of 2.5 on average compared to state-of-the-art few-shot adaptation methods.

Intelligent personal and home applications demand multiple deep neural networks (DNNs) running on resourceconstrained platforms for compound inference tasks, known as multitask inference. To fit multiple DNNs into low-resource devices, emerging techniques resort to weight sharing among DNNs to reduce their storage. However, such reduction in storage fails to translate into efficient execution on common accelerators such as GPUs. Most DNN graph rewriters are blind for multi-DNN optimization, while GPU vendors provide inefficient APIs for parallel multi-DNN execution at runtime. A few prior graph rewriters suggest cross-model graph fusion for low-latency multi-DNN execution. Yet they request duplication of the shared weights, erasing the memory saving of weight-shared DNNs. In this paper, we propose MTS, a novel graph rewriter for efficient multitask inference with weight-shared DNNs. MTS adopts a model stitching algorithm which outputs a single computational graph for weight-shared DNNs without duplicating any shared weight. MTS also utilizes a model grouping strategy to avoid overwhelming the GPU when co-running tens of DNNs. Extensive experiments show that MTS accelerates multitask inference by up to 6.0× compared to sequentially executing multiple weightshared DNNs. MTS also yields up to 2.5× lower latency and 3.7× less memory usage compared with NETFUSE, a state-of-the-art multi-DNN graph rewriter.

Accurate calibration of low-cost environmental sensors is a prerequisite for their successful use in many monitoring applications. State-of-the-art calibration methods vary from simple linear regression to sophisticated deep models based on LSTMs and GRUs. The latter take past measurements to improve calibration accuracy. In this article, we argue that both recent past and close future measurements help to achieve accurate calibration, whereas accuracy improvements beyond the past come with a delay introduced by the occurrence of the future. We propose a generalized many-to-many calibration scheme called SensorFormer based on the successful Transformer model which takes both past and future raw measurements into account. We show that the proposed approach: 1) outperforms other methods by improving calibration accuracy by 16.5%–20.4% on public data sets and own field data and 2) can efficiently run on low-power microcontrollers with very limited computational and storage capabilities. The latter is achieved by a novel optimization technique based on learnable input subsampling taking advantage of the properties of typical sensor data. We manage to reduce the model size by 20%–33% and minimize the overall floating point operations per second (FLOPs) by 65% while maintaining superior accuracy than state-of-the-art methods.

Energy harvesting is increasingly used as a long-term energy supply for the Internet of Things, wireless sensor networks, and cyber-physical systems. However, the challenge of mitigating the variability of energy harvesting sources needs to be addressed before ubiquitous adoption can happen. Otherwise, an unreliable operation of devices with frequent shutdowns during times of energy scarcity would be encountered. One finds probabilistic performance metrics helpful in designing power management solutions for the long-term operation of energy harvesting nodes. These metrics include the probability of battery depletion, expected energy consumption, expected battery level, and similar. This article proposes a stochastic modeling technique and corresponding analysis which can provide such metrics. Our advanced analysis is based on Markov chains. By modeling harvested energy with random variables, new and existing energy management policies are analyzed and compared. We propose an adaptive energy management strategy inspired by mixed-criticality systems. In the proposed strategy, the system can degrade or drop less essential tasks in real time to ensure a graceful degradation of service in adverse harvesting conditions. We compare the proposed energy management approach to several existing alternatives. To this end, we conduct extensive simulations for indoor and outdoor environments, where our strategy matches or outperforms the state of the art. Initial results also validate the high precision of our stochastic model and analysis in comparison to simulations using real-world data.

Coarse-grained reconfigurable array (CGRA) has emerged as a promising hardware accelerator due to the excellent balance between reconfigurability, performance, and energy efficiency. The performance of a CGRA strongly depends on the existence of a high-quality compiler to map the application kernels on the architecture. Unfortunately, the state-of-the-art compiler technology falls short in generating high-performance mapping within an acceptable compilation time, especially with increasing CGRA size. We proposeHiMap—a fast and scalable CGRA mapping approach—that is also adept at producing close-to-optimal solutions for regular computational kernels prevalent in existing and emerging application domains. The key strategy behindHiMap’s efficiency and scalability is to exploit the regularity in the computation by employing a virtual systolic array (VSA) as an intermediate abstraction layer in a hierarchical mapping.HiMapfirst maps the loop iterations of the kernel onto a VSA and then distills out the unique patterns in the mapping. These unique patterns are subsequently mapped onto subspaces of the physical CGRA. They are arranged together according to the systolic array mapping to create a complete mapping of the kernel. Experimental results confirm thatHiMapcan generate application mappings that hit the performance envelope of the CGRA.HiMapoffers$17.3\times $and$5\times $improvement in performance and energy efficiency of the mappings compared to the state of the art. The compilation time ofHiMapfor near-optimal mappings is less than 15 min for 64$\times $64 CGRA while existing approaches take days to generate inferior mappings.

Sensing systems powered by energy harvesting have traditionally been designed to tolerate long periods without energy. As the Internet of Things (IoT) evolves toward a more transient and opportunistic execution paradigm, reducing energy storage costs will be key for its economic and ecologic viability. However, decreasing energy storage in harvesting systems introduces reliability issues. Transducers only produce intermittent energy at low voltage and current levels, making guaranteed task completion a challenge. Existing ad hoc methods overcome this by buffering enough energy either for single tasks, incurring large data-retention overheads, or for one full application cycle, requiring a large energy buffer. We present Julienning : an automated method for optimizing the total energy cost of batteryless applications. Using a custom specification model, developers can describe transient applications as a set of atomically executed kernels with explicit data dependencies. Our optimization flow can partition data- and energy-intensive applications into multiple execution cycles with bounded energy consumption. By leveraging interkernel data dependencies, these energy-bounded execution cycles minimize the number of system activations and nonvolatile data transfers, and thus the total energy overhead. We validate our methodology with two batteryless cameras running energy-intensive machine learning applications. Using a solar testbed, we replay real-world illuminance traces to experimentally demonstrate optimized batteryless execution with a transducer-to-application energy efficiency of 74.5%. Partitioning results demonstrate that compared to ad hoc solutions, our method can reduce the required energy storage by over 94% while only incurring a 0.12% energy overhead.

Testbeds for wireless IoT devices facilitate testing and validation of distributed target nodes. A testbed usually provides methods to control, observe, and log the execution of the software. However, most of the methods used for tracing the execution require code instrumentation and change essential properties of the observed system. Methods that are non-intrusive are typically not applicable in a distributed fashion due to a lack of time synchronization or necessary hardware/software support. In this article, we present a tracing system for validating time-critical software running on multiple distributed wireless devices that does not require code instrumentation, is non-intrusive and is designed to trace the distributed state of an entire network. For this purpose, we make use of the on-chip debug and trace hardware that is part of most modern microcontrollers. We introduce a testbed architecture as well as models and methods that accurately synchronize the timestamps of observations collected by distributed observers. In a case study, we demonstrate how the tracing system can be applied to observe the distributed state of a flooding-based low-power communication protocol for wireless sensor networks. The presented non-intrusive tracing system is implemented as a service of the publicly accessible open source FlockLab 2 testbed.

Adapting neural networks to unseen tasks with few training samples on resource-constrained devices benefits various Internet-of-Things applications. Such neural networks should learn the new tasks in few shots and be compact in size. Meta-learning enables few-shot learning, yet the meta-trained networks can be over-parameterised. However, naive combination of standard compression techniques like network pruning with meta-learning jeopardises the ability for fast adaptation. In this work, we propose adaptation-aware network pruning (ANP), a novel pruning scheme that works with existing meta-learning methods for a compact network capable of fast adaptation. ANP uses weight importance metric that is based on the sensitivity of the meta-objective rather than the conventional loss function, and adopts approximation of derivatives and layer-wise pruning techniques to reduce the overhead of computing the new importance metric. Evaluations on few-shot classification benchmarks show that ANP can prune meta-trained convolutional and residual networks by 85% without affecting their fast adaptation.

10.23919/DATE51398.2021.9473916

Pre-trained language models have been widely adopted as backbones in various natural language processing tasks.However, existing pre-trained language models ignore the descriptive meta-information in the text such as the distinction between the title and the mainbody, leading to over-weighted attention to insignificant text.In this paper, we propose a hypernetwork-based architecture to model the descriptive meta-information and integrate it into pre-trained language models.Evaluations on three natural language processing tasks show that our method notably improves the performance of pre-trained language models and achieves the state-of-the-art results on keyphrase extraction.

Many mobile applications demand selective execution of multiple correlated deep learning inference tasks on resource-constrained platforms. Given a set of deep neural networks, each pre-trained for a single task, it is desired that executing arbitrary combinations of tasks yields minimal computation cost. Pruning each network separately yields suboptimal computation cost due to task relatedness. A promising remedy is to merge the networks into a multitask network to eliminate redundancy across tasks before network pruning. However, pruning a multitask network combined by existing network merging schemes cannot minimise the computation cost of every task combination because they do not consider such a future pruning. To this end, we theoretically identify the conditions such that pruning a multitask network minimises the computation of all task combinations. On this basis, we propose Pruning-Aware Merging (PAM), a heuristic network merging scheme to construct a multitask network that approximates these conditions. The merged network is then ready to be further pruned by existing network pruning methods. Evaluations with different pruning schemes, datasets, and network architectures show that PAM achieves up to 4.87x less computation against the baseline without network merging, and up to 2.01x less computation against the baseline with a state-of-the-art network merging scheme.

Today’s deeply embedded systems, with real-time interactions to the environment, are largely battery-operated, and peripheral modules like LTE, WiFi, and GPS are among the most energy-hungry components of them. These components are often under the direct control of an embedded software. Some pieces of the software program are called energy hotspots if they can be transformed towards better system energy consumption while leaving it logically- and temporally-correct. This paper focuses on three such energy hotspots from the peripheral module perspective. The root causes of the hotspots in the software program are misplaced driver calls: Early acquiring or late releasing of the module causes it to waste energy in the active state, having unnecessary distance between the use operations causes extra tail energy overhead, and unaccounted releasing and re-acquiring of the module causes more energy consumption in comparison to leaving the module unreleased. We provide static analysis methods for the detection and elimination of such energy hotspots automatically with regard to some relations between temporal requirements of the real-time embedded software, the time and energy specifications of the module, and the extreme (worst-case/best-case) execution times of specific pieces of the software program. Our simulation results show about 4.7 to 20 percent of energy reductions after elimination of the energy hotspots of the test programs using our proposed method.

Low-power wireless sensor networks have demonstrated their potential for the detection of rare events such as rockfalls and wildfires, where rapid reporting as well as long-term energy-efficient operation is vital. However, current systems require periodic synchronization to maintain network coordination, heavily rely on node placement or use costly long-range links to infrastructure. We present STeC, a novel wireless communication design that directly exploits the spatial and temporal correlation of signals from the sensed phenomenon to orchestrate event-based communication. We leverage the locality of a co-detection, where a physical event triggers multiple sensors quasi-simultaneously, to efficiently collect, characterize and report sensor data. This eliminates the overhead of periodic network activity and centralized control, resulting in more energy-efficient communication with a lower, more consistent detection latency. In doing so, we propose a fundamentally new approach to avoid the elementary conflict between duty cycle and latency requirements immanent to synchronous protocols by exploiting correlated sensor signals for networking. Experiments using real-world traces of a natural hazard detection application show that STeC reduces the detection latency by up to 87 % compared to standard single-hop communication and outperforms traditional schedule-based methods by up to 58.4 x in energy efficiency.

Employing energy harvesting to power the Internet of Things supports their long-term, self-sustainable, and maintenance-free operation. These energy harvesting systems have an energy management subsystem to orchestrate the flow of energy and optimize their achievable system performance. Numerous such algorithms for a single harvesting-based system have been proposed. When envisioning the joint use of multiple distributed energy harvesting nodes in a single application, the performance and behavior of the distributed system depends on the mutual energy availability and therefore energy management of all nodes. We propose to perform the energy management of multiple distributed energy harvesting nodes jointly and thus, optimize the distributed system's performance as opposed to the performance of each energy harvesting node individually. We demonstrate the novel joint optimization in a scenario with multiple energy harvesting nodes and observe that the distributed system's performance improves by 28 % compared to when each node's energy is managed individually.

Smart manufacturing aims to overcome the limitations of today's rigid assembly lines by making the material flow and manufacturing process more flexible, versatile, and scalable. The main economic drivers are higher resource and cost efficiency as the manufacturers can more quickly adapt to changing market needs and also increase the lifespan of their production sites. The ability to close feedback loops fast and reliably over long distances among mobile robots, remote sensors, and human operators is a key enabler for smart manufacturing. Thus, this article provides a perspective on control and coordination over wireless networks. Based on an analysis of real-world use cases, we identify the main technical challenges that need to be solved to close the large gap between the current state of the art in industry and the vision of smart manufacturing. We discuss to what extent existing control-over-wireless solutions in the literature address those challenges, including our own approach toward a tight integration of control and wireless communication. In addition to a theoretical analysis of closed-loop stability, practical experiments on a cyber-physical testbed demonstrate that our approach supports relevant smart manufacturing scenarios. This article concludes with a discussion of open challenges and future research directions.

Abstract Mixed-criticality systems often need to fulfill safety standards that dictate different requirements for each criticality level, for example given in the ‘probability of failure per hour’ format. A recent trend suggests designing this kind of systems by jointly scheduling tasks of different criticality levels on a shared platform. When this is done, the usual assumption is that tasks of lower criticality are degraded when a higher criticality task needs more resources, for example when it overruns a bound on its execution time. However, a way to quantify the impact this degradation has on the overall system is not well understood. Meanwhile, to improve schedulability and to avoid over-provisioning of resources due to overly pessimistic worst-case execution time estimates of higher criticality tasks, a new paradigm emerged where task’s execution times are modeled with random variables. In this paper, we analyze a system with probabilistic execution times, and propose metrics that are inspired by safety standards. Among these metrics are the probability of deadline miss per hour, the expected time before degradation happens, and the duration of the degradation. We argue that these quantities provide a holistic view of the system’s operation and schedulability.

We investigate the compression of deep neural networks by quantizing their weights and activations into multiple binary bases, known as multi-bit networks (MBNs), which accelerate the inference and reduce the storage for the deployment on low-resource mobile and embedded platforms. We propose Adaptive Loss-aware Quantization (ALQ), a new MBN quantization pipeline that is able to achieve an average bitwidth below one-bit without notable loss in inference accuracy. Unlike previous MBN quantization solutions that train a quantizer by minimizing the error to reconstruct full precision weights, ALQ directly minimizes the quantization-induced error on the loss function involving neither gradient approximation nor full precision maintenance. ALQ also exploits strategies including adaptive bitwidth, smooth bitwidth reduction, and iterative trained quantization to allow a smaller network size without loss in accuracy. Experiment results on popular image datasets show that ALQ outperforms state-of-the-art compressed networks in terms of both storage and accuracy.

As computing systems are increasingly shared among different users or application domains, researchers have intensified their efforts to detect possible data leaks. In particular, many investigations highlight the vulnerability of systems w.r.t. covert and side channel attacks. However, the effort required to reproduce and compare different results has proven to be high. Therefore, we present a novel methodology for covert channel evaluation. In addition, we introduce the Experiment Orchestration Toolkit ExOT, which provides software tools to efficiently execute the methodology.Our methodology ensures that the covert channel analysis yields expressive results that can be reproduced and allow the comparison of the threat potential of different data leaks. ExOT is a software bundle that consists of easy to extend C++ libraries and Python packages. These libraries and packages provide tools for the generation and execution of experiments, as well as the analysis of the experimental data. Therefore, ExOT decreases the engineering effort needed to execute our novel methodology. We verify these claims with an extensive evaluation of four different covert channels on an Intel Haswell and an ARMv8 based platform. In our evaluation, we derive capacity bounds and show achievable throughputs to compare the threat potential of these different covert channels.

Low-power wireless communication is a central building block of Cyber-physical Systems and the Internet of Things. Conventional low-power wireless protocols make avoiding packet collisions a cornerstone design choice. The concept of synchronous transmissions challenges this view. As collisions are not necessarily destructive, under specific circumstances, commodity low-power wireless radios are often able to receive useful information even in the presence of superimposed signals from different transmitters. We survey the growing number of protocols that exploit synchronous transmissions for higher robustness and efficiency as well as unprecedented functionality and versatility compared to conventional designs. The illustration of protocols based on synchronous transmissions is cast in a conceptional framework we establish, with the goal of highlighting differences and similarities among the proposed solutions. We conclude the paper with a discussion on open research questions in this field.

There is a growing trend to deploy deep neural networks at the edge for high-accuracy, real-time data mining and user interaction. Applications such as speech recognition and language understanding often apply a deep neural network to encode an input sequence and then use a decoder to generate the output sequence. A promising technique to accelerate these applications on resource-constrained devices is network pruning, which compresses the size of the deep neural network without severe drop in inference accuracy. However, we observe that although existing network pruning algorithms prove effective to speed up the prior deep neural network, they lead to dramatic slowdown of the subsequent decoding and may not always reduce the overall latency of the entire application. To rectify such drawbacks, we propose entropy-based pruning, a new regularizer that can be seamlessly integrated into existing network pruning algorithms. Our key theoretical insight is that reducing the information entropy of the deep neural network outputs decreases the upper bound of the subsequent decoding search space. We validate our solution with two state-of-the-art network pruning algorithms on two model architectures. Experimental results show that compared with existing network pruning algorithms, our entropy-based pruning method notably suppresses and even eliminates the increase of decoding time, and achieves shorter overall latency with only negligible extra accuracy loss in the applications.

Social scientists, psychologists, and epidemiologists use empirical human interaction data to research human behaviour, social bonding, and disease spread. Historically, systems measuring interactions have been forced to choose between deployability and measurement fidelity---they operate only in instrumented spaces, under line-of-sight conditions, or provide coarse-grained proximity data. We introduce SociTrack, a platform for autonomous social interaction tracking via wireless distance measurements. Deployments require no supporting infrastructure and provide sub-second, decimeter-accurate ranging information over multiple days. The key insight that enables both deployability and fidelity in one system is to decouple node mobility and network management from range measurement, which results in a novel dual-radio architecture. SociTrack leverages an energy-efficient and scalable ranging protocol that is accurate to 14.8 cm (99th percentile) in complex indoor environments and allows our prototype to operate for 12 days on a 2000 mAh battery. Finally, to validate its deployability and efficacy, SociTrack is used by early childhood development researchers to capture caregiver-infant interactions.

Closing feedback loops fast and over long distances is key to emerging cyber-physical applications; for example, robot motion control and swarm coordination require update intervals of tens of milliseconds. Low-power wireless communication technology is preferred for its low cost, small form factor, and flexibility, especially if the devices support multi-hop communication. Thus far, however, feedback control over multi-hop low-power wireless networks has only been demonstrated for update intervals on the order of seconds. To fill this gap, this article presents a wireless embedded system that supports dynamic mode changes and tames imperfections impairing control performance (e.g., jitter and message loss), and a control design that exploits the essential properties of this system to provably guarantee closed-loop stability for physical processes with linear time-invariant dynamics in the presence of mode changes. Using experiments on a cyber-physical testbed with 20 wireless devices and multiple cart-pole systems, we are the first to demonstrate and evaluate feedback control and coordination with mode changes over multi-hop networks for update intervals of 20 to 50 milliseconds.

Sensing systems for long-term monitoring constitute an important part of the emerging Internet of Things. In this domain, energy harvesting and infrastructure-less communication enable truly autonomous and maintenance-free operation of sensor nodes gathering long-term environmental data. Due to the infrastructure-less nature of the communication, receivers are not always available. The variable energy provided by the environment and the receiver’s mobility lead to non-deterministic node availability. In this work, we study infrastructure-less data transmission schemes to optimize communication when both senders and receivers exhibit intermittent behavior. We rely on the notion of data utility, describing the importance of sensed data to the receiver, to determine an optimal communication scheme. Deriving the communication policy that maximizes the utility of the received data is shown to be a convex optimization problem. The resulting scheme is implemented and validated on a batteryless Bluetooth Low Energy sensor node that communicates to commodity smartphones. Our evaluation demonstrates that the model accurately captures the application scenario with a maximum root-mean-square error of less than 0.016 in data reception probability. The communication scheme’s adaptiveness to variable harvesting conditions is experimentally demonstrated under varying harvesting conditions and is shown to significantly increase the data utility.

A central challenge in designing embedded control systems or cyber-physical systems (CPS) is that of translating high-level models of control algorithms into efficient implementations, while ensuring that model-level semantics are preserved. While a large body of techniques for designing provably correct control strategies exist in the control theory literature, when it comes to transforming mathematical descriptions of these strategies to an efficient implementation, the available means are surprisingly ad hoc in nature. Among other reasons, this is because of (i) implementation platform details not sufficiently being accounted for in controller models, (ii) side effects introduced in the code generation process, (iii) various compiler optimizations whose impact on the dynamics of the plant being controlled not being properly understood, (iv) the presence of analog components on the implementation platform whose behavior is difficult to model, (v) computation and communication delays that exist in an implementation but were not accounted for in the model, and (vi) also the effects of image/video processing whose accuracy and timing behavior are difficult to model. As we move towards designing autonomous systems, these issues become biting problems on the path to certification, and striking a balance between performance and certification. In this position paper, we discuss some of these challenges - that we formulate as the need for modeling the interactions between various implementation layers in a CPS - and potential research directions to address them.

In this demo abstract we present a custom-built low-power geo-phone sensor node which features on-device mountaineer classification using a convolutional neural network. The execution of such a processing-heavy algorithm on an embedded platform is enabled by optimizing the memory requirement of the neural network through advanced quantization and pipelining techniques. As a result, real-time classification with low energy consumption can be achieved.

In natural hazard warning systems fast decision making is vital to avoid catastrophes. Decision making at the edge of a wireless sensor network promises fast response times but is limited by the availability of energy, data transfer speed, processing and memory constraints. In this work we present a realization of a wireless sensor network for hazard monitoring based on an array of event-triggered single-channel micro-seismic sensors with advanced signal processing and characterization capabilities based on a novel co-detection technique. On the one hand we leverage an ultra-low power, threshold-triggering circuit paired with on-demand digital signal acquisition capable of extracting relevant information exactly and efficiently at times when it matters most and consequentially not wasting precious resources when nothing can be observed. On the other hand we utilize machine-learning-based classification implemented on low-power, off-the-shelf microcontrollers to avoid false positive warnings and to actively identify humans in hazard zones. The sensors' response time and memory requirement is substantially improved by quantizing and pipelining the inference of a convolutional neural network. In this way, convolutional neural networks that would not run unmodified on a memory constrained device can be executed in real-time and at scale on low-power embedded devices. A field study with our system is running on the rockfall scarp of the Matterhorn Hörnligrat at 3500 m a.s.l. since 08/2018.

The Dual Processor Platform (DPP) is a novel architecture template for networked embedded systems based on a strictly asynchronous processor interconnect that allows to minimize interference with a proven predictable behavior [7]. Contrary to traditional platforms [1, 5] DPP tries to mitigate interference by isolating different tasks and mapping them onto dedicated hardware resources. Typically, two different task sets - (i) sensing/actuation/data processing and (ii) communication - are mapped onto two different physically separated processing elements (usually low-power microcontrollers), allowing each to be optimized according to their individual requirements. Such hardware partitioning is a standard approach, frequently found in more complex sensor system implementations [2]. While the communication processor handles wireless packet transmission and reception, the application processor is dedicated to the sensor data acquisition, processing and actuation. But this strict separation of resources and function also requires a processor interconnect: BOLT [7], a stateful processor interconnect specifically designed based on this paradigm allows a strict decoupling of the power, clock and time domains of the two processing elements by allowing only asynchronous message passing between the two. The strict limitation to an asynchronous interface allows for predictable run-time behavior that, in addition to typical behavior observed from experiments, has been formally verified [7]. The most notable advantages of this approach are:

In this paper, we present the design of our prototype of an automated real-time and affordable pollen sensing system. The design consists of three main subsystems: (1) a trap with automatic filtering, (2) a particle concentration system, and (3) a digital microscope with autofocus. The prototype shows effective particle gathering, filtering and concentration in a tiny sized area. As a result, we reduce particle loss and improve image quality taken by the optical system when searching and autofocusing on pollen grains. Our first prototype collects raw time-stamped data and transmits these to the backend server where we plan to run the detection and classification algorithms to extract accurate pollen counts from microscopic images. The key advantage of processing images at the backend is that we let the experts undertake corrective actions and help the system learn to detect and classify pollen using state-of-the-art interactive imitation learning algorithms. The final model can then run locally on embedded hardware.

This abstract describes the first public demonstration of feedback control and coordination of multiple physical systems over a dynamic multi-hop low-power wireless network with update intervals of tens of milliseconds. Our running system can dynamically change between different sets of application tasks (e.g., sensing, actuation, control) executing on the spatially distributed embedded devices, while closed-loop stability is provably guaranteed even across those so-called mode changes. Moreover, any subset of the devices can move freely, which does not affect closed-loop stability and control performance as long as the wireless network remains connected.

Designing and testing low-power wireless communication protocols often requires experimental deployments on real hardware in realistic settings. Infrastructure testbeds have the advantage that they allow reproducible results using different network configurations. However, most testbeds are either in- or outdoor only and do not span long and short ranges at the same time. In this work, we present an extension to the popular FlockLab testbed on a campus-scale in order to better support testing of long-range communciation, for example using the LoRa modulation. Different to existing LoRa test networks where specific protocol layers are fixed, we support custom modification above the physical hardware (above PHY) which allows the development and testing of alternative full custom MAC layers that are not based on LoRaWAN.

Power densities of modern mobile system-on-a-chip designs can quickly exceed the thermal design limits during typical application use such as gaming or Web browsing. Resulting high temperatures lead to frequent thermal throttling and significant loss in quality-of-service (QoS) delivered to users. Thus, a joint consideration of thermal constraints and QoS requirements is essential to maximize the overall user experience. Prior techniques either rely on users to determine the best tradeoff point between QoS and temperature, or greedily utilize the thermal headroom to maximize performance, causing QoS to drop below user tolerable levels over extended durations of use. This paper introduces the MAESTRO framework to automatically manage QoS at runtime depending on application characteristics and thermal constraints. MAESTRO builds on the observation that increased temperatures can be tolerated for applications with bursty compute patterns due to idle periods between activities, while causing large QoS degradations for long-running applications with continuous computations. MAESTRO: 1) detects such continuous computations that are susceptible to throttling; 2) proactively finds a QoS level to balance user experience and temperature; and 3) performs closed-loop DVFS and thermally efficient thread mapping to meet the target QoS on a heterogeneous multicore CPU. Such application-adaptive control of QoS-temperature tradeoffs allows MAESTRO to sustain a target QoS level within a user tolerable range for longer durations without sacrificing the performance of latency-sensitive bursty computations. Evaluations on a real system prototype validates MAESTRO's ability to accurately detect potential throttlinginduced QoS degradations and demonstrates 41% to 6.7× longer durations of sustained QoS compared to state-of-the-art for a set of mobile applications.

In this work, we present a formal study on optimizing the energy consumption of energy harvesting embedded systems. To deal with the uncertainty inherent in solar energy harvesting systems, we propose the Stochastic Power Management (SPM) scheme, which builds statistical models of harvested energy based on historical data. The proposed stochastic scheme maximizes the lowest energy consumption across all time intervals while giving strict probabilistic guarantees on not encountering battery depletion. For situations where historical data is not available, we propose the use of (i) a Finite Horizon Control (FHC) scheme and (ii) a non-uniformly scaled energy estimator based on an astronomical model, which is used by FHC. Under certain realistic assumptions, the FHC scheme can provide guarantees on minimum energy usage that can be supported over all times. We further propose and evaluate a piece-wise linear approximation of FHC for efficient implementation in resource-constrained embedded systems. With extensive experimental evaluation for eight publicly available datasets and two datasets collected with our own deployments, we quantitatively establish that the proposed solutions are highly effective at providing a guaranteed minimum service level and significantly outperform existing solutions.

Event-triggered wireless sensing systems are an important class of wireless sensor network, where the detection of non-deterministic events enables the monitoring and control of processes in industries such as manufacturing, healthcare, and agriculture. The system properties of low latency, energy efficiency, and adaptability make event-triggered wireless sensing systems a key technological enabler for the Industrial Internet of Things. <?tight?>Wireless sensing systems based on periodic multi-hop communication exhibit a fundamental trade-off between latency and energy efficiency, which is unfavorable for event-triggered application scenarios. To address this technological gap, we present B litz , the first communication architecture that combines asynchronous and synchronous flooding primitives to facilitate low latency and energy-efficient multi-hop communication of non-deterministic events. B litz also incorporates a novel scheme for mitigating erroneous wake-ups, which is shown analytically and experimentally to further reduce energy consumption. We present a prototype implementation of B litz and evaluate its performance in an indoor testbed deployment. Experiments show that BLITZ supports a mean latency as low as 108.9ms for an 8-bit event packet and its associated data packet of 32 bytes through a 4-hop network, and a power dissipation of 16μW during periods of inactivity.

Wired fieldbuses have long been proven effective in supporting Cyber-Physical Systems (CPS). However, various domains are now striving for wireless solutions due to ease of deployment or novel functionality requiring the ability to support mobile devices. Low-power wireless protocols have been proposed in response to this need, but requirements of a large class of CPS applications can still not be satisfied. We thus propose Time-Triggered Wireless (TTW), a distributed low-power wireless system design that minimizes communication energy consumption and offers end-to-end timing predictability, runtime adaptability, reliability, and low latency. Evaluation shows a 2× reduction in communication latency and 33-40% lower radio-on time compared with DRP, the closest related work, validating the suitability of TTW for new exciting wireless CPS applications.

Future mobile devices are anticipated to perceive, understand and react to the world on their own by running multiple correlated deep neural networks on-device. Yet the complexity of these neural networks needs to be trimmed down both within-model and cross-model to fit in mobile storage and memory. Previous studies focus on squeezing the redundancy within a single neural network. In this work, we aim to reduce the redundancy across multiple models. We propose Multi-Task Zipping (MTZ), a framework to automatically merge correlated, pre-trained deep neural networks for cross-model compression. Central in MTZ is a layer-wise neuron sharing and incoming weight updating scheme that induces a minimal change in the error function. MTZ inherits information from each model and demands light retraining to re-boost the accuracy of individual tasks. Evaluations show that MTZ is able to fully merge the hidden layers of two VGG-16 networks with a 3.18% increase in the test error averaged on ImageNet and CelebA, or share 39.61% parameters between the two networks with <0.5% increase in the test errors for both tasks. The number of iterations to retrain the combined network is at least 17.8 times lower than that of training a single VGG-16 network. Moreover, experiments show that MTZ is also able to effectively merge multiple residual networks.

Air pollution is a major concern for public health and urban environments. Conventional air pollution monitoring systems install a few highly accurate, expensive stations at representative locations. Their sparse coverage and low spatial resolution are insufficient to quantify urban air pollution and its impacts on human health and environment. Advances in low-cost portable air pollution sensors have enabled air pollution monitoring deployments at scale to measure air pollution at high spatiotemporal resolution. However, it is challenging to ensure the accuracy of these low-cost sensor deployments because the sensors are more error-prone than high-end sensing infrastructures and they are often deployed in harsh environments. Sensor calibration has proven to be effective to improve the data quality of low-cost sensors and maintain the reliability of long-term, distributed sensor deployments. In this paper, we review the state-of-the-art low-cost air pollution sensors, identify their major error sources, and comprehensively survey calibration models as well as network recalibration strategies suited for different sensor deployments. We also discuss limitations of exiting methods and conclude with open issues for future sensor calibration research.

Most modern processors use dynamic voltage and frequency scaling (DVFS) for power management. DVFS allows to optimize power consumption by scaling voltage and frequency depending on performance demand. Previous research has indicated that this frequency scaling might pose a security threat in the form of a covert channel, which could leak sensitive information. However, an analysis able to determine whether DVFS is a serious security issue is still missing. In this paper, we conduct a detailed analysis of the threat potential of a DVFS-based covert channel. We investigate two multicore platforms representative of modern laptops and hand-held devices. Furthermore, we develop a channel model to determine an upper bound to the channel capacity, which is in the order of 1 bit per channel use. Last, we perform an experimental analysis using a novel transceiver implementation. The neural network-based receiver yields packet error rates between 1% and 8% at average throughputs of up to 1.83 and 1.20 bps for platforms representative of laptops and hand-held devices, respectively. Considering the well-known small message criterion, our results show that a relevant covert channel can be established by exploiting the behavior of computing systems with DVFS.

While energy harvesting is generally seen to be the key to power cyber-physical systems in a low-cost, long-term, efficient manner, it has generally required large energy storage devices to mitigate the effects of the source’s variability. The emerging class of transiently powered systems embrace this variability by performing computation in proportion to the energy harvested, thereby minimizing the obtrusive and expensive storage element. By using an efficient Energy Management Unit (EMU), small bursts of energy can be buffered in an optimally sized capacitor and used to supply generic loads, even when the average harvested power is only a fraction of that required for sustained system operation. Dynamic Energy Burst Scaling (DEBS) can be used by the load to dynamically configure the EMU to supply small bursts of energy at its optimal power point, independent from the harvester’s operating point. Parameters like the maximum burst size, the solar panel’s area, as well as the use of energy-efficient Non-Volatile Memory Hierarchy (NVMH) can have a significant impact on the transient system’s characteristics such as the wake-up time and the amount of work that can be done per unit of energy. Experimental data from a solar-powered, long-term autonomous image acquisition application show that, regardless of its configuration, the EMU can supply energy bursts to a 43.4mW load with efficiencies of up to 79.7% and can work with input power levels as low as 140μW. When the EMU is configured to use DEBS and NVMH, the total energy cost of acquiring, processing and storing an image can be reduced by 77.8%, at the price of increasing the energy buffer size by 65%.

With the appearance of wearable devices and the IoT, energy harvesting nodes are becoming more and more important. The design and evaluation of these small standalone sensors and actuators, which harvest limited amounts of energy, requires novel tools and methods. Fast and accurate measurement systems are required to capture the rapidly changing harvesting scenarios and characterize leakage currents and energy efficiencies. The need for real-world experiments creates a demand for compact and portable equipment to perform in-situ power measurements and environmental logging. This work presents the RocketLogger, a hand-held measurement device that combines both properties: portability and accuracy. The custom analog front-end allows logging at sampling rates up to 64 kSPS. The fast range switching within 1.4 μ8 guarantees continuous power measurements starting from 4pW at 1 mV up to 2.75 W at 5.5 V. The software provides remote control and manages data acquisition of up to 13Mb/ sec in real-time. We extensively characterize the RocketLogger's performance, demonstrate the need for its properties in three use-cases at different stages of the system design flow, and show its advantages in measuring and validating new harvesting-driven devices for the IoT.

Sensing tongue movements enables various applications in hands-free interaction and alternative communication. We propose BARTON, a BARometer based low-power and robust TONgue movement sensing system. Using a low sampling rate of below 50 Hz, and only extracting simple temporal features from in-ear pressure signals, we demonstrate that it is plausible to distinguish important tongue gestures (left, right, forward) at low power consumption. We prototype BARTON with commodity earpieces integrated with COTS barometers for in-ear pressure sensing and an ARM micro-controller for signal processing. Evaluations show that BARTON yields 94% classification accuracy and 8.4 mW power consumption, which achieves comparable accuracy, but consumes 44 times lower energy than the state-of-the-art microphone-based solutions. BARTON is also robust to head movements and operates with music played directly from earphones.

We propose a novel method for mitigating erroneous wake-ups that are commonly associated with ultra-low power wake-up receivers. Recent research in low-power protocols has demonstrated significant improvements in energy-efficiency by employing ultra-low power wake-up receivers. However, due to the low-complexity receiver structures adopted, wake-up receivers are susceptible to external interference, which can cause the detection of non-existent wake-ups. The occurrence of these erroneous wake-ups wastes precious energy resources, thereby negating the potential energy savings in employing wake-up receivers. We address this challenging problem by extracting time-domain features from the output of the wake-up receiver, and construct a classifier to distinguish between correct and erroneous wake-ups. We describe the design of the proposed wake-up classifier and present preliminary results.

Low-power wireless technology promises greater flexibility and lower costs in cyber-physical systems. To reap these benefits, communication protocols must deliver packets reliably within real-time deadlines across resource-constrained devices , while adapting to changes in application requirements (e.g., traffic demands) and network state (e.g., link qualities). Existing protocols do not solve all these challenges simultaneously, because their operation is either localized or a function of network state, which changes unpredictably over time. By contrast, this article claims a global approach that does not use network state information as input can overcome these limitations. The Blink protocol proves this claim by providing hard guarantees on end-to-end deadlines of received packets in multi-hop low-power wireless networks, while seamlessly handling changes in application requirements and network state. We build Blink on the non-real-time Low-Power Wireless Bus (LWB) and design new scheduling algorithms based on the earliest-deadline-first policy. Using a dedicated priority queue data structure, we demonstrate a viable implementation of our algorithms on resource-constrained devices. Experiments show that Blink (i) meets all deadlines of received packets, (ii) delivers 99.97% of packets on a 94-node testbed, (iii) minimizes communication energy consumption within the limits of the underlying LWB, (iv) supports end-to-end deadlines of 100ms across four hops and nine sources, and (v) runs up to 4.1 × faster than a conventional scheduler implementation on popular microcontrollers.

Recently, there has been an increasing trend towards executing real-time applications on multi-core platforms. However, this complicates the design problem, as applications running on different cores can interfere due to shared resources and mediums. In this paper, we focus on thermal interference, where a given task (τ 1 ) heats the processor, resulting in reduced service (due to Dynamic Thermal Management (DTM)) to another task (τ 2 ). In real-time domain, where tasks have deadline constraints, thermal interference is a substantial problem as it directly impacts the Worst Case Execution Time (WCET) of the effected application (τ 2 ). The problem exacerbates as we move to mixed-criticality systems, where the criticality of τ 2 may be greater than the criticality of τ 1 , complicating the certification process. In this paper, we propose a server based strategy (Thermal Isolation Server (TI Server)) which can be used to avoid thermal interference of applications. We also present a heuristic to design TI Servers to meet the timing constraints of all tasks and the thermal constraints of the system. TI Servers are time/space composable, and can be applied to a variety of task models. We also evaluate TI Servers on a hardware test-bed for validation purposes.

A common multi-core pattern consists of processors communicating through shared, multi-banked on-chip memory. Two approaches exist: Interleaved address mapping, which spreads consecutive data over all banks, and contiguous address mapping, which stores consecutive data on a single bank. In this work, we compare both approaches on the Kalray MPPA-256 platform. For contiguous mapping, we propose an algorithm, based on graph colouring techniques, to automatically perform the assignment of data blocks to memory banks with the goal of minimising access collisions and delays. Experiments with representative, parallel real-world benchmarks show that 69% of the tested configurations, when optimised for contiguous mapping by our algorithm, run up to 86% faster on average than with interleaved mapping.

Recent industrial trends favor the adoption of multi-core architectures for mixed-criticality applications. Although several mixed-criticality multi-core scheduling approaches have been proposed, currently there are few implementations on hardware that demonstrate efficient resource utilization and the ability to bound interference on shared resources. To address this necessity, we develop a mixed-criticality runtime environment on the Kalray MPPA-256 Andey many-core platform. The runtime environment implements a scheduling policy based on adaptive temporal partitioning. We develop models, methods and implementation principles to implement the necessary scheduling primitives, to achieve high platform utilization and to perform a compositional worst-case execution time analysis. The bounds account for scheduling overheads and for the inter-task interference on the platform’s shared memory. Using realistic benchmarks from avionics and signal processing, we validate the correctness and tightness of the bounds and demonstrate a high platform utilization.

Mixed-criticality is a significant recent trend in the embedded system industry, where common computing platforms are utilized to host functionalities of varying criticality levels. To date, most scheduling techniques have focused on the timing aspect of this problem, while functional safety (i.e. fault-tolerance) is often neglected.

In mixed-criticality scheduling, the widely assumed mode-switch scheme assumes that both high- and low-criticality tasks are schedulable when no tasks overrun (normal mode) and all high-criticality tasks are schedulable even when they overrun (critical mode, where low-criticality tasks are abandoned/degraded). However, this scheme triggers a mode-switch immediately after any task overruns, which can be abrupt and pessimistic. In this paper, we tackle dual-criticality systems scheduled by earliest-deadline-first, and propose light-weight mode-switch schemes that are effective in keeping the system "away" from the critical mode. Our main idea is to perform overrun budgeting for all tasks as a whole, by monitoring task executions and updating a common overrun budget. This way, the overrun budget is shared among all tasks, and adaptively replenished leveraging run-time information; consequently, mode-switch can be postponed as much as possible. Experimental results demonstrate that the proposed mode-switch schemes outperform existing solutions to a large extent, in reducing the abandoned jobs and mode-switch frequencies, as well as in increasing the time ratio that all tasks are scheduled in the system.

Modern multicore processors feature easily accessible temperature sensors that provide useful information for dynamic thermal management. These sensors were recently shown to be a potential security threat, since otherwise isolated applications can exploit them to establish a thermal covert channel and leak restricted information. Previous research showed experiments that document the feasibility of (low-rate) communication over this channel, but did not further analyze its fundamental characteristics. For this reason, the important questions of quantifying the channel capacity and achievable rates remain unanswered.

We present a heterogeneous system architecture for event-triggered wireless sensing capable of supporting high spatial resolution. The key differentiator between the proposed architecture and alternative state-of-the-art approaches is the ability to simultaneously maximize operational lifetime and minimize end-to-end latency of detected events. Our novel architecture takes advantage of heterogeneity with respect to the operation of the wireless communication protocol and the construction of the sensing platform. We present a two-hop proof of concept implementation, exhibiting end-to-end latencies on the order of tenths of a second, while dissipating on the order of tens of microwatts during periods of inactivity.

If visions and forecasts of industry come true then we will be soon surrounded by billions of interconnected embedded devices. We will interact with them in a cyber-human symbiosis, they will not only observe us but also our environment, and they will be part of many visible and ubiquitous objects around us. The information that is collectively gathered and analyzed is supposed to help us in our daily live, in making faithful decisions, but it will also directly be used for actuation and it will cause changes by means of local and global control loops.

In this paper we study a general energy minimization problem for mixed-criticality systems on multi-cores, considering different system operation modes, and static & dynamic energy consumption. While making global scheduling decisions, trade-offs in energy consumption between different modes and also between static and dynamic energy consumption are required. Thus, such a problem is challenging. To this end, we first develop an optimal solution analytically for unicore and a corresponding low-complexity heuristic. Leveraging this, we further propose energy-aware mapping techniques and explore energy savings for multi-cores. To the best of our knowledge, we are the first to investigate mixed-criticality energy minimization in such a general setting. The effectiveness of our approaches in energy reduction is demonstrated through both extensive simulations and a realistic industrial application.

In cyber-physical systems (CPS), the communication among the sensing, actuating, and computing elements is often subject to hard real-time constraints. Real-time communication among wireless network interfaces and real-time scheduling for complex, dynamic applications have been intensively studied. Despite these major efforts, there is still a significant gap to fill. In particular, the integration of several real-time components to provide end-to-end real-time guarantees between interfaces of distributed applications in wireless CPS is an unsolved problem. We thus present a distributed protocol that considers the complete transmission chain including peripheral busses, memory accesses, networking interfaces, and the wireless real-time protocol. Our protocol provably guarantees that message buffers along this chain do not overflow and that all messages received at the destination application interface meet their end-to-end deadlines. To achieve this while being adaptive to unpredictable changes in the system and the real-time traffic requirements, our protocol establishes at run-time a set of contracts among all major elements of the transmission chain based on a worst-case delay and buffer analysis of the overall system. Using simulations, we validate that our analytic bounds are both safe and tight.

Experimental research in low-power wireless networking lacks a reference benchmark. While other communities such as databases or machine learning have standardized benchmarks, our community still uses ad-hoc setups for its experiments and struggles to provide a fair comparison between communication protocols. Reasons for this include the diversity of network scenarios and the stochastic nature of wireless experiments. Leveraging on the excellent testbeds and tools that have been built to support experimental validation, we make the case for a reference benchmark to promote a fair comparison and reproducibility of results. This abstract describes early design elements and a benchmarking methodology with the goal to gather feedback from the community rather than propose a definite solution.

We demonstrate the RocketLogger, a mobile data logger designed for prototyping energy harvesting IoT devices. Novel IoT applications require new dataloggers with a highly increased dynamic range for current measurement to accommodate both ultra-low sleep currents of few nanoamperes as well as wireless communication currents in the range of hundreds of milliamperes. In parallel to ultra-low currents and high dynamic range measurements, novel applications require mobile measurements for easy in-situ characterization or wearable device testing. The RocketLogger is a solution that fulfills these requirements. While being fully mobile, it measures currents from 5 nA up to 500 mA with very fast and seamless range-switching. Using a sample energy harvesting application, we demonstrate its low-current measurement capabilities, fast, seamless auto-ranging and easy-to-use remote user interface.

Shared on-chip memory is common on state-of-the-art multicore platforms. In a number of designs, memory throughput is enhanced by providing multiple independent memory banks and spreading consecutive memory addresses to these (interleaving). This can reduce, but not eliminate, the number of access conflicts. In this paper, we statically analyse the probabilities and frequencies of these access conflicts and calculate the expected throughput for various hardware configurations and software applications. Using two techniques -- the classic occupancy distribution and a Markov model -- we are able to explain most of the underlying conflict mechanisms and to provide accurate estimations. We present the practical consequences for hardware and software design and establish an intuitive understanding of the characteristics of interleaved memory architectures.

In this work we present the first formal study on optimizing the energy utilization of energy harvesting embedded systems while giving bounds on the minimum energy usage. Furthermore, to deal with the uncertainty inherent to solar energy harvesting we propose to use (i) a finite horizon scheme, and (ii) anon-uniformly scaled energy estimation based on an astronomical model. Under certain realistic assumptions, the finite horizon scheme can provide guarantees on minimum energy utilization, and therefore minimum utility. We show that a single non-uniform scaling function is applicable to solar energy traces from diverse locations. We further propose and evaluate a piece-wise linear approximation for efficient implementation as a small look-up table for resource constrained embedded systems. With extensive experimental evaluation for eight publicly available datasets and two datasets collected with our own deployments, we quantitatively establish that the proposed solution is highly effective at providing a guaranteed minimum utilization, and significantly out-performs four previously proposed solutions.

The continuing proliferation of smartphones makes them an effective means to monitor the number of people within an area, for example, to gain insights into customer engagement in retail and to enable an intelligent traffic system in a city. However, current approaches to obtain this information are either invasive as they require to continuously run a dedicated smartphone app, or they compromise users' privacy by sniffing the MAC addresses of their smartphones. As a consequence, lawyers, authorities, and the population are very skeptical toward adopting such innovative systems. We present DevCnt, the first system that counts in real-time the number of Wi-Fi enabled smartphones in a non-invasive manner while preserving by design the privacy of the smartphone users. This paper details how DevCnt detects active Wi-Fi scans performed by smartphones on a ZigBee device, and how DevCnt uses the number of detected scans to estimate the number of Wi-Fi enabled smartphones. Results from controlled and real-world experiments show that DevCnt: (i) detects more than 99% of active Wi-Fi scans even under interference from multiple wireless technologies, (ii) achieves up to 91% accuracy in the estimated smartphone counts, and (iii) provides meaningful estimates in a real test run involving hundreds of Wi-Fi transmitters.

In this paper, we take a dynamical systems perspective of real-time systems. In particular, we investigate the evolution of response times of periodic jobs and aim to show that oscillatory and chaotic behavior can be exhibited by standard scheduling algorithms. To this end, we present a simple periodic task specification that leads to oscillations of response times for a fixed priority scheduler. We then show three task specifications that lead to complex dynamic behavior under various scheduling algorithms: (a) round robin, (b) multiprocessor fixed-priority, and (c) priority inheritance protocol. As a practical validation of the results, we implemented the multiprocessor fixed-priority scheduler using POSIX threads and standard locking mechanisms. Finally, we discuss general observations and implications of the observed and proven phenomena.

Programming models which specify an application as a network of independent computational elements have emerged as a promising paradigm for programming streaming applications. The antagonism between expressivity and analysability has led to a number of different such programming models, which provide different degrees of freedom to the programmer. One example are Kahn process networks (KPNs), which, due to certain restrictions in communication, can guarantee determinacy (their results are independent of timing by construction). On the other hand, certain dataflow models, such as the CAL Actor Language, allow non-determinacy and thus higher expressivity, however at the price of static analysability and thus a potentially less efficient implementation. In many cases, however, non-determinacy is not required (or even not desired), and relying on KPN for the implementation seems advantageous. In this paper, we propose an algorithm for classifying dataflow actors (i.e. computational elements) as KPN compatible or potentially not. For KPN compatible dataflow actors, we propose an automatic KPN translation method based on this algorithm. In experiments, we show that more than 75% of all mature actors of a standard multimedia benchmark suite can be classified as KPN compatible and that their execution time can be reduced by up to 1.97x using our proposed translation technique. Finally, in a manual classification effort, we validate these results and list different classes of KPN incompatibility.

Workflow graphs (WFGs) are control-flow graphs extended by parallel fork and join. They are used to represent the main control-flow of e.g. business process models modeled in languages such as BPMN or UML activity diagrams. A WFG is said to be sound if it is free of deadlocks and exhibits no lack of synchronization. We study the question whether the executions of a time-annotated sound WFG meet a given deadline. We present polynomial-time algorithms and NP-hardness results for different cases. In particular, we show that it can be decided in polynomial time whether some executions of a sound WFG meet the deadline. Furthermore we show that for general probabilistic WFGs, it is NP-hard to determine whether the probability of an execution meeting the deadline is higher than a given threshold, whereas the expected duration of an execution can be computed in polynomial time.

The availability of novel, high-resolution pollution maps enables a wide range of new application scenarios, which were not possible before. In this paper, we combine high-resolution pollution maps available for the city of Zurich, Switzerland, with road network data to analyze how much urban dwellers can reduce their exposure to air pollution by not taking the shortest path between origin and destination but a healthier and slightly longer alternative route. We introduce a new weight function to assess the exposure on each street segment and evaluate the benefits of the healthier path. Finally, we efficiently implement the algorithm as stand-alone application for iOS and Android devices. The app helps city residents to understand and reduce their exposure to air pollutants.

Frequent sensor calibration is essential in sensor networks with low-cost sensors. We exploit the fact that temporally and spatially close measurements of different sensors measuring the same phenomenon are similar. Hence, when calibrating a sensor, we adjust its calibration parameters to minimize the differences between co-located measurements of previously calibrated sensors. In turn, freshly calibrated sensors can now be used to calibrate other sensors in the network, referred to as multi-hop calibration.

Resource interference is a fundamental barrier to realizing predictable wireless embedded systems. We address this problem by (i) partitioning application and communication tasks onto dedicated platforms, and (ii) designing a platform interconnect to facilitate asynchronous message exchange with predictable run-time behavior. We motivate the need for this platform interconnect, termed Bolt, and describe a prototype implementation. Evaluation results indicate that the developed platform interconnect exhibits tightly bounded run-time execution with low jitter, and a negligible resource overhead with respect to state-of-the-art application and communication platforms.

We present a new technique for overcoming the fundamental trade-off between energy-efficiency and end-to-end packet latency pervading all event-triggered wireless sensing applications. Instead of applying popular synchronous or pseudo-asynchronous protocols, we leverage state-of-the-art wake-up receivers to facilitate purely asynchronous rendezvous. We then extend the per-hop asynchrony into a multi-hop flooding primitive, termed Wake-up Flooding. We describe the underpinnings of the flooding primitive and present preliminary results of wake-up flooding implemented on a custom dual-radio wireless sensing platform deployed in an indoor testbed.

Multicore systems are being increasingly used for embedded system deployments, even in safety-critical domains. Co-hosting applications of different criticality levels in the same platform requires sufficient isolation among them, which has given rise to the mixed-criticality scheduling problem and several recently proposed policies. Such policies typically employ runtime mechanisms to monitor task execution, detect exceptional events like task overruns, and react by switching scheduling mode. Implementing such mechanisms efficiently is crucial for any scheduler to detect runtime events and react in a timely manner, without compromising the system’s safety. This paper investigates implementation alternatives for these mechanisms and empirically evaluates the effect of their runtime overhead on the schedulability of mixed-criticality applications. Specifically, we implement in user-space two state-of-the-art scheduling policies: the flexible time-triggered FTTS [1] and the partitioned EDFVD [2], and measure their runtime overheads on a 60-core Intel R Xeon Phi and a 4-core Intel R Core i5 for the first time. Based on extensive executions of synthetic task sets and an industrial avionic application, we show that these overheads cannot be neglected, esp. on massively multicore architectures, where they can incur a schedulability loss up to 97%. Evaluating runtime mechanisms early in the design phase and integrating their overheads into schedulability analysis seem therefore inevitable steps in the design of mixed-criticality systems. The need for verifiably bounded overheads motivates the development of novel timing-predictable architectures and runtime environments specifically targeted for mixed-criticality applications.

Efficiently exploiting multicore processors for real-time applications is challenging because jobs that run concurrently on different cores can interfere on shared resources, severely complicating precise timing analysis. We propose a new scheduling model called Isolation Scheduling (IS), IS provides a framework to exploiting multicores for real-time applications where tasks are grouped in classes. IS enforces mutually exclusive execution among different task classes, thus avoiding inter-class interference by construction. We show that IS encompasses several recent advances in real-time scheduling as special cases and we propose global and partitioned scheduling algorithms based on this model. Specific results are provided if the task classes correspond to different safety criticality levels.

In this paper, we tackle the challenge of rapidly disseminating rare events through a multi-hop network, while achieving unprecedented energy-efficiency. Contrary to state-of-the-art approaches, we circumvent the undesirable trade-offs associated with low-power duty-cycled protocols and backscatter technologies, and demonstrate a paradigm shift in low-power protocol design. We present Zippy, an on-demand flooding technique that provides robust asynchronous network wake-up, fine-grained per-hop synchronization and efficient data dissemination by leveraging low-complexity transmitter and receiver hardware. We are the first to demonstrate the on-demand flooding of rare events through a multi-hop network with end-to-end latencies of tens of milliseconds, while dissipating less than 10 microwatts during periods of inactivity. We present a prototype implementation of our proposed approach using a wireless sensor platform constructed from commercially available components. We extensively evaluate Zippy's performance in a laboratory setting and in an indoor testbed.

The wireless sensor network community is currently undergoing a platform paradigm shift, moving away from classical single-processor motes toward heterogeneous multi-processor architectures. These emerging platforms promise efficient concurrent processing with energy-proportional system performance. The use of shared interconnects and shared memory for inter-processor communication, however, causes interference in the time, power, and clock domains, which prevents designers from fully harnessing these benefits. We thus designed Bolt, the first ultra-low-power processor interconnect for the compositional construction of heterogeneous wireless embedded platforms. This paper presents the architectural blueprint for interconnecting two independent processors, while enabling asynchronous inter-processor communication with predictable run-time behavior. We detail a prototype implementation of Bolt, and apply formal methods to analytically derive bounds on the execution time of its message passing operations. Experiments with a custom-built dual-processor platform show that our Bolt prototype incurs a negligible power overhead relative to state-of-the-art platforms, offers predictable message passing with empirical bounds that match the analytical ones to within a few clock cycles, and achieves a high throughput of up to 3.3 Mbps.

We demonstrate the capabilities of Bolt, an ultra-low-power processor interconnect for the composable construction of new multi-processor wireless embedded platforms. Bolt provides asynchronous bidirectional communication between two processors with predictable message transfer times. In this way, Bolt solves the resource interference problem inherent in today's wireless embedded platforms, enabling simpler and more robust system designs with minimal resource overhead. Using our Bolt prototype implemented on a state-of-the-art microcontroller, we demonstrate Bolt's composability and decoupling in time, power, and clock domains.

Complex embedded systems are typically mixed-critical, where heterogeneous guarantees must be provided for functionalities of different criticalities. We study in this paper the reconfiguration of services provided to low criticality tasks in reaction to the overruns of high criticality tasks. We further investigate the quantification of the resetting time of the system services. For both service reconfiguration and resetting, we derive tight analysis results under Earliest Deadline First (EDF) scheduling.

A widely considered strategy to prevent interference issues on multi-processor systems is to isolate the execution of the individual applications by running each of them on a dedicated virtual guest machine. The amount of computing power available to a single application, however, depends on the other applications running on the system and may change over time. A promising approach to maximize the performance under such conditions is to adapt the application's degree of parallelism when the resources allocated to the application are changed. This enables an application to exploit not more parallelism than required, thereby reducing inter-process communication and scheduling overheads. In this paper, we introduce AdaPNet, a run-time system to execute streaming applications, which are modeled as process networks, efficiently on platforms with dynamic resource allocation. AdaPNet responds to changes in the available resources by first calculating a process network that maximizes the performance of the application on the new resources. Then, AdaPNet transparently transforms the application into the alternative network without discarding the program state. Targeting two many-core systems, we demonstrate that AdaPNet outperforms comparable run-time systems, which do not adapt the degree of parallelism, in terms of speed-up and memory usage.

We consider in this paper fault-tolerant mixed-criticality scheduling, where heterogeneous safety guarantees must be provided to functionalities (tasks) of varying criticalities (importances). We model explicitly the safety requirements for tasks of different criticalities according to safety standards, assuming hardware transient faults. We further provide analysis techniques to bound the effects of task killing and service degradation on the system safety and schedulability. Based on our model and analysis, we show that our problem can be converted to a conventional mixed-criticality scheduling problem. Thus, we broaden the scope of applicability of the conventional mixed-criticality scheduling techniques. Our proposed techniques are validated with a realistic flight management system application and extensive simulations.

This paper presents a static mapping optimization technique for fault-tolerant mixed-criticality MPSoCs. The uncertainties imposed by system hardening and mixed criticality algorithms, such as dynamic task dropping, make the worst-case response time analysis difficult for such systems. We tackle this challenge and propose a worst-case analysis framework that considers both reliability and mixed-criticality concerns. On top of that, we build up a design space exploration engine that optimizes fault-tolerant mixed-criticality MPSoCs and provides worst-case guarantees. We study the mapping optimization considering judicious task dropping, that may impose a certain service degradation. Extensive experiments with real-life and synthetic benchmarks confirm the effectiveness of the proposed technique.

We present a new framework that efficiently detects and tolerates timing faults in real time systems. Timing faults are observed when the inputs and/or outputs of a given system fail to meet their desired timing properties, such as I/O rates. Most current approaches either rely on heartbeat monitoring which is too restrictive; or on statistical or inexact methods which are not suitable for embedded real time systems. Current approaches based on the abstract real time model of the given application are resource intensive, and may not be suitable for embedded systems. Our framework utilizes active replication, and is based on already existing timing models for real time applications to develop fault detection and tolerance strategies. The approach does not require any timekeeping at runtime, and is efficient in terms of computational resources used. Experiments using three realistic applications on the Intel Baremetal SCC demonstrate the efficiency of our framework, both in memory and computational resources used.

Real-time systems are often guaranteed in terms of schedulability, which verifies whether or not all jobs meet their deadlines. However, such a guarantee can be insufficient in certain applications. In this paper, we propose a method to compute a language-based guarantee which provides a more detailed description of the deadline miss patterns of an observed task. The only requirement of our method is that the timing behavior of the real-time system be modelled by a network of timed automata. We compute the language-based guarantee by constructing an equivalent finite state automaton in an iterative manner, using a counter-example guided procedure. We illustrate the language-based guarantee for two applications: design of a networked control system and scheduling in a mixed criticality system. In both cases, we show that the language-based guarantee leads to a more efficient design than the schedulability guarantee.

A common trend in real-time embedded systems is to integrate multiple applications on a single platform. Such systems are known as mixed-criticality (MC) systems when the applications are characterized by different criticality levels. Nowadays, multicore platforms are promoted due to cost and performance benefits. However, certification of multicore MC systems is challenging as concurrently executed applications of different criticalities may block each other when accessing shared platform resources. Most of the existing research on multicore MC scheduling ignores the effects of resource sharing on the response times of applications. Recently, a MC scheduling strategy was proposed, which explicitly accounts for these effects. This paper discusses how to combine this policy with an optimization method for the partitioning of tasks to cores as well as the static mapping of memory blocks, i.e., task data and communication buffers, to the banks of a shared memory architecture. Optimization is performed at design time targeting at minimizing the worst-case response times of tasks and achieving efficient resource utilization. The proposed optimization method is evaluated using an industrial application.

This paper presents a novel mapping optimization technique for mixed critical multi-core systems with different reliability requirements. For this scope, we derived a quantitative reliability metric and presented a scheduling analysis that certifies given mixed-criticality constraints. Our framework is capable of investigating re-execution, passive replication, and modular redundancy with optimized voter placement, while typical hardening approaches consider only one or two of these techniques. The proposed technique complies with existing safety standards and is power-efficient, as demonstrated by our experiments.

Thermal constraints limit the time for which a processor can run at high frequency. Such thermal-throttling complicates the computation of response times of jobs. For multiple processors, a key decision is where to allocate the next job. For distributed thermally-throttled procesosrs, we present COOLIP with a simple allocation policy: a job is allocated to the earliest available processor, and if there are several available simultaneously, to the coolest one. For Poisson distribution of inter-arrival times and Gaussian distribution of execution demand of jobs, COOLIP matches the 95-percentile response time of Earliest Finish-Time (EFT) policy which minimizes response time with full knowledge of execution demand of unfinished jobs and thermal models of processors. We argue that COOLIP performs well because it directs the processors into states such that a defined sufficient condition of optimality holds.

Consolidating functionalities with different safety requirements into a common platform gives rise to mixed-criticality systems. The state-of-the-art research has focused on providing heterogeneous timing guarantees for tasks of varying criticality levels. This is achieved by dropping less critical tasks when critical tasks overrun. However, with drastically increased computing requirements and the often battery-operated nature of mixed-criticality systems, energy minimization for such systems is also becoming crucial. In fact, this has already been possible since many modern processors are equipped with the capacity of dynamic voltage and frequency scaling (DVFS), where processor frequency can be reduced at runtime to save energy.

The YDS algorithm computes a schedule on a DVS-enabled resource to meet deadlines of all jobs and optimally minimize the total energy consumption. The algorithm requires that an exact execution time of each job be known. For settings where execution times are variable or uncertain, stochastic scheduling has been proposed to preferentially accelerate less probable phases of jobs to reduce the expected energy consumption. However, an analogue to the YDS algorithm for the stochastic setting has not been optimally solved. In this paper, we propose the p-YDS algorithm to minimize the expected energy consumption for a set of jobs with arbitrary arrival times, deadlines, and execution times. We then derive the competitive ratio of the YDS algorithm w.r.t. the p-YDS algorithm, for the metric of expected energy consumption. By comparing two optimal algorithms, this ratio specifies the worst-case energy cost of being agnostic to the variability in the execution time of jobs.

EURETILE investigates foundational innovations in the design of massively parallel tiled computing systems by introducing a novel parallel programming paradigm and a multi-tile hardware architecture. Each tile includes multiple general-purpose processors, specialized accelerators, and a fault-tolerant distributed network processor, which connects the tile to the inter-tile communication network. This paper focuses on the EURETILE software design flow, which provides a novel programming environment to map multiple dynamic applications onto a many-tile architecture. The elaborated high-level programming model specifies each application as a network of autonomous processes, enabling the automatic generation and optimization of the architecture-specific implementation. Behavioral and architectural dynamism is handled by a hierarchically organized runtime-manager running on top of a lightweight operating system. To evaluate, debug, and profile the generated binaries, a scalable many-tile simulator has been developed. High system dependability is achieved by combining hardware-based fault awareness strategies with software-based fault reactivity strategies. We demonstrate the capability of the design flow to exploit the parallelism of many-tile architectures with various embedded and high performance computing benchmarks targeting the virtual EURETILE platform with up to 192 tiles.

Up-to-date information on urban air pollution is of great importance for health protection agencies to assess air quality and provide advice to the general public in a timely manner. In particular, ultrafine particles (UFPs) are widely spread in urban environments and may have a severe impact on human health. However, the lack of knowledge about the spatio-temporal distribution of UFPs hampers profound evaluation of these effects. In this paper, we analyze one of the largest spatially resolved UFP data set publicly available today containing over 25 million measurements. We collected the measurements throughout more than a year using mobile sensor nodes installed on top of public transport vehicles in the city of Zurich, Switzerland. Based on these data, we develop land-use regression models to create pollution maps with a high spatial resolution of 100m × 100 m. We compare the accuracy of the derived models across various time scales and observe a rapid drop in accuracy for maps with subweekly temporal resolution. To address this problem, we propose a novel modeling approach that incorporates past measurements annotated with metadata into the modeling process. In this way, we achieve a 26% reduction in the root-mean-square error-a standard metric to evaluate the accuracy of air quality models-of pollution maps with semi-daily temporal resolution. We believe that our findings can help epidemiologists to better understand the adverse health effects related to UFPs and serve as a stepping stone towards detailed real-time pollution assessment.

The trend to integrate multiple functionalities on the same (off-the-shelf) hardware has made the selection of the right scheduling algorithm and configuration difficult. This selection requires the designer to validate any scheduling decision already during early design steps on the target architecture, e.g., by using a reconfigurable scheduling framework running in the user-space. In this paper, we first identify the requirements that such a scheduling framework must fulfill. Then, we propose SF3P: an open-source framework that meets these requirements. To this end, we define an interface common to all scheduling algorithms and separate the scheduling algorithm from its low-level implementation. With these features, SF3P can not only prototype a scheduler at high level of abstraction, but also execute the implemented task-set on specific hardware. Furthermore, SF3P can hierarchically compose scheduling algorithms, useful in the mixed criticality domain, and could also be used to explore different scheduling policies in the system optimization phase. We demonstrate these features by implementing SF3P on top of a POSIX-compliant operating system on two different platforms: Raspberry Pi and an Intel Core i7 desktop system.

In this work we consider a real-world environmental monitoring scenario that requires uninterrupted system operation over time periods on the order of multiple years. To achieve this goal, we propose a novel approach to dynamically adjust the system's performance level such that energy neutral operation, and thus long-term uninterrupted operation can be achieved. We first consider the annual dynamics of the energy source to design an appropriate power subsystem (i.e., solar panel size and energy store capacity), and then dynamically compute the long-term sustainable performance level at runtime. We show through trace-driven simulations using eleven years of real-world data that our approach outperforms existing predictive, e.g., EWMA, WCMA, and reactive, e.g., ENO-MAX, approaches in terms of average performance level by up to 177%, while reducing duty-cycle variance by up to three orders of magnitude. We further demonstrate the benefits of the dynamic power management scheme using a wireless sensor system deployed for environmental monitoring in a remote, high-alpine environment as a case study. A performance evaluation over two years reveals that the dynamic power management scheme achieves a two-fold improvement in system utility when compared to only applying appropriate capacity planning.

Hard real-time embedded systems impose a strict latency requirement on interconnection subsystems. In the case of network-on-chip (NoC), this means each packet of a traffic stream has to be delivered within a time interval. In addition, with the increasing complexity of NoC, it consumes a significant portion of total chip power, which boosts the power footprint of such chips. In this paper, we propose a methodology to minimize the energy consumption of NoC without violating the prespecified latency deadlines of real-time applications. First, we develop a formal approach based on network calculus to obtain the worst-case delay bound of all packets, from which we derive a safe estimate of the number of cycles that a packet can be further delayed in the network without violating its deadline-the worst-case slack. With this information, we then develop an optimization algorithm that trades the slacks for lower NoC energy. Our algorithm recognizes the distribution of slacks for different traffic streams, and assigns different voltages and frequencies to different routers to achieve NoC energy-efficiency, while meeting the deadlines for all packets. Furthermore, we design a feedback-control strategy to enable dynamic frequency and voltage scaling on the network routers in conjunction with the energy optimization algorithm. It can flexibly improve the energy-efficiency of the overall network in response to sporadic traffic patterns at runtime.

On-chip temperatures continue to rise, in spite of design efforts towards more efficient cooling and novel low-power technologies. Run-time thermal management techniques, such as speed scaling and system throttling, constitute a standard component in today's processors. One such technique is the feedback control of the processing speed based on the on-chip temperature. If suitably designed, such a controller can ensure that the temperature of the processor does not exceed a given bound, independent of the application. Such isolation of needs is encouraging. However, from the application's stand-point, such a processor must provide performance guarantees; in particular, the guarantee that real-time jobs do not have worst-case delays larger than their relative deadlines. For applications which exhibit variability, such as bursty arrival patterns, computing such guarantees is not apparent. As key enablers in such a computation, for the specific setting of First-Come-First-Serve (FCFS) scheduling, we (a) define and prove a monotonicity principle satisfied by the processor with the said controller, and (b) propose a thermally clipped processor model. We identify the worst-case trace simulating which on a suitably chosen thermally clipped processor provides the tight upper-bound on the worst-case delay. These results hold for general models of (a) the power consumption of the processor, (b) its thermal model, (c) the speed scaling law, and (d) the task model. For this modelling scope, we show that the same worst-case trace also leads to the worst-case temperature of the processor. This is useful to characterise tasks which do not load the processor sufficiently to hit the given peak temperature bound. We demonstrate the utility of this calculation by designing a shaper to delay the arrival times of jobs and thereby restrict the observed worst-case temperature while still meeting the task's deadlines.

Running each application of a many-core system on an isolated (virtual) guest machine is a widely considered solution for performance and reliability issues. When a new application is started, the guest machine is assigned with an amount of computing resources that depends on the overall workload of the system and is not known to the designer at specification time. For instance, the computing resources might consist of many slow or a few fast processing elements. If the application is statically specified, as, for example, with Kahn process networks, the number of processing elements usable by an application is upper bounded by its number of processes. Similarly, the inter-process communication overhead might limit the maximum performance if the number of processing elements is significantly smaller than the number of processes. In this paper, we propose a formal extension for streaming programming models called expandable process networks (EPNs) that tackles this challenge by abstracting several possible granularities in a single specification. This enables the automatic exploration of task, data, and pipeline parallelism by two basic design transformation techniques, namely replication and unfolding. Then, the EPN semantics facilitates the synthesis of multiple design implementations that are all derived from one high-level specification. At runtime, the best fitting implementation for the given computing resources is selected to maximize the performance. Finally, we demonstrate the effectiveness of the proposed model on Intel's 48-core SCC processor.

Technology scaling is a common trend in current embedded systems. It has promoted the use of multi-core, multi-processor, and distributed platforms. Such systems usually require run-time migration of distributed applications between the different nodes of the platform in order to balance the workload or to tolerate faults. Before an application can be migrated, it needs to be brought to a stable state such that restarting the application after migration does not violate its functional correctness. An application in a stable state does not change its context any further, and therefore, stabilization is a prerequisite for any application migration. Process networks are a common model of computation for specifying distributed applications. However, most results on the migration of process networks do not provide an algorithm to put a general process network into a stable state, suitable for migration. This paper proposes a technique which efficiently and correctly brings a process network executing on a distributed system to a known stable state. The correctness of the technique is independent of the temporal characteristics of the system and the topology of the process network. The required modifications of a process network are lightweight and preserve its original functionality. A model characterizing the timing properties of the technique is provided. The feasibility and efficiency of the proposed approach and the respective model are validated with experimental results on Intel's SCC platform.

Hard real-time embedded systems impose a strict latency requirement on interconnection subsystems. In the case of network-on-chip (NoC), this means each packet of a traffic stream has to be delivered within a time interval. In addition, with the increasing complexity of NoC, it consumes a significant portion of total chip power, which boosts the power footprint of such chips. In this work, we propose a methodology to minimize the energy consumption of NoC without violating the pre-specified latency deadlines of real-time applications. First, we develop a formal approach based on network calculus to obtain the worst-case delay bound of all packets, from which we derive a safe estimate of the number of cycles that a packet can be further delayed in the network without violating its deadline---the worst-case slack. With this information, we then develop an optimization algorithm that trades the slacks for lower NoC energy. Our algorithm recognizes the distribution of slacks for different traffic streams, and assigns different voltages and frequencies to different routers to achieve NoC energy-efficiency, while meeting the deadlines for all packets.

We study the problem of assigning speeds to resources serving distributed applications with delay, buffer and energy constraints. We argue that the considered problem does not have any straightforward solution due to the intricately related constraints. As a solution, we propose using Real-Time Calculus (RTC) to analyse the constraints and a SATisfiability solver to efficiently explore the design space. To this end, we develop an SMT solver by using the OpenSMT framework and the Modular Performance Analysis (MPA) toolbox. Two key enablers for this implementation are the analysis of incomplete models and generation of conflict clauses in RTC. The results on problem instances with very large decision spaces indicate that the proposed SMT solver performs very well in practice.

Wireless sensor networks are increasingly used in application scenarios where a high data quality is inevitable, e.g., the control of industrial production areas. Nevertheless, many deployments must live with strict constraints regarding the sensing hardware and may not employ newest sensing technologies, e.g., due to limited energy budget, size, and bandwidth. Additionally, many applications would benefit from not only gathering absolute sensor readings but also knowing the quality of their low-cost sensor measurements. In this paper, we introduce a model-driven approach that (i) provides reliable accuracy bounds for individual noisy sensor readings and (ii) detects systematic and transient sensor errors. We apply our method to static and mobile real-world deployments of noisy and unstable low-cost sensors by analyzing large sets of urban temperature and ozone measurements. We find that the proposed algorithm successfully calculates precise accuracy bounds. We compare them to measurements of high-quality instruments and show that up to 96 % of the reference measurements are inside the computed accuracy bounds in the static scenario and up to 94 % in the mobile scenario. This is surprisingly high for the used low-cost sensors. By analyzing data from our static longterm deployment, we reveal that the ozone sensor's reliability is dependent on seasonal weather conditions.

Health monitoring is an integral service for the long-term operation of wireless sensor networks. Instead of actively adding probe or status traffic, recently proposed passive health monitoring systems infer system health solely from existing application traffic. Our results from extensive testbed experiments prove that the detection rate of an exemplary monitoring application is significantly improved, i.e., by up to 28% to overall 94%, when a passive health estimation method is complemented with a minimally active component. This paper presents Hybrid Monitoring, a novel health monitoring system that combines the advantages of passive and active health monitoring systems. Results from the analysis of passively reconstructed, inexact per-hop timing information are significantly improved when one bit of extra information is added to every packet. The resulting system is able to estimate a significant health metric, i.e., the number of occurred failure events on a node, with a high confidence. The temporal resolution of the estimated signal is equal to the packet sampling interval, the performance of our system is not affected by large packet delays, e.g., when a sensor node is disconnected for a long time.

A common trend in real-time safety-critical embedded systems is to integrate multiple applications on a single platform. Such systems are known as mixed-criticality (MC) systems as the applications are usually characterized by different criticality levels (CLs). Nowadays, multicore platforms are promoted due to cost and performance benefits. However, certification of multicore MC systems is challenging because concurrently executed applications with different CLs may block each other when accessing shared platform resources. Most of the existing research on multicore MC scheduling ignores the effects of resource sharing on the execution times of applications. This paper proposes a MC scheduling strategy which explicitly accounts for these effects. Applications are executed by a flexible time-triggered criticality-monotonic scheduling scheme. Schedulers on different cores are dynamically synchronized such that only a statically known subset of applications of the same CL can interfere on shared resources, e. g.,memories, buses. Therefore, the timing effects of resource sharing are bounded and we quantify them at design time. We combine this scheduling strategy with a mapping optimization technique for achieving better resource utilization. The efficiency of the approach is demonstrated through extensive simulations as well as comparisons with traditional temporal partitioning and state-of-the-art scheduling algorithms. It is also validated on a real-world avionics system.

Current research in mixed-criticality systems assumes that any task of lower criticality levels can be dropped at anytime in order to guarantee the schedulability of tasks of higher criticality levels. However, in an industrial mixed-criticality system, tasks may interfere with each other only under certain scenarios. Currently a designer does not have any means to specify or control this. The paper proposes the Interference Constraint Graph (ICG) which specifies the allowed interferences between tasks. The new specification formalism generalizes and can easily express many of the existing mixed-criticality scheduling conditions. In spite of its generality, we show that standard fixed-priority scheduling can be efficiently applied. Experiments demonstrate that the ICG model enables systematic reduction of the number of tasks that can be dropped.

Mathematical models play a pivotal role in understanding and designing advanced low-power wireless systems. However, the distributed and uncoordinated operation of traditional multi-hop low-power wireless protocols greatly complicates their accurate modeling. This is mainly because these protocols build and maintain substantial network state to cope with the dynamics of low-power wireless links. Recent protocols depart from this design by leveraging synchronous transmissions (ST), whereby multiple nodes simultaneously transmit towards the same receiver, as opposed to pair wise link-based transmissions (LT). ST improve the one-hop packet reliability to an extent that efficient multi-hop protocols with little network state are feasible. This paper studies whether ST also enable simple yet accurate modeling of these protocols. Our contribution to this end is two-fold. First, we show, through experiments on a 139-node test bed, that characterizing packet receptions and losses as a sequence of independent and identically distributed (i.i.d.) Bernoulli trials-a common assumption in protocol modeling but often illegitimate for LT-is largely valid for ST. We then show how this finding simplifies the modeling of a recent ST-based protocol, by deriving (i) sufficient conditions for probabilistic guarantees on the end-to-end packet reliability, and (ii) a Markovian model to estimate the long-term energy consumption. Validation using test bed experiments confirms that our simple models are also highly accurate, for example, the model error in energy against real measurements is 0.25%, a figure never reported before in the related literature.

Welcome to Taipei, Taiwan, and the IEEE 19th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2013). RTCSA has been a prestigious technical conference sponsored by the IEEE Technical Committee on Real-Time Systems for years. The objective of the conference is to bring together academic researchers and industry developers for intensive discussion of recent advances in the field of embedded systems, real-time systems, and cyber-physical systems.

Up-to-date information on urban air pollution, such as reliable pollution maps, is of great importance for health protection agencies to timely assess the air quality situation and provide advice to the general public. Ultrafine particles (UFPs) are widely spread in urban environments and believed to have severe impact on the human health. However, the lack of spatially resolved data hampers profound evaluation of these effects. In this work, we introduce one of the largest spatially resolved UFP data set available today, with over 25 million measurements to build high-resolution pollution maps for an urban area of 100 km2. The data is collected throughout more than one year using mobile sensor nodes, which are installed on top of public transport vehicles in the city of Zurich, Switzerland. We develop land-use regression models to create pollution maps with a high spatial resolution and study their temporal resolution limit.

Traditional low-power wireless protocols maintain distributed network state to cope with link dynamics. Modeling the protocol operation as a function of network state is difficult as the state is frequently updated in an uncoordinated fashion. Recent protocols use synchronous transmissions (ST): multiple nodes send simultaneously towards the same receiver, as opposed to pairwise link-based transmissions (LT). ST enable efficient multi-hop protocols with little network state.

By integrating computational and physical elements through feedback loops, CPSs implement a wide range of safety-critical applications, from high-confidence medical systems to critical infrastructure control. Deployed systems must therefore provide highly dependable operation against unpredictable real-world dynamics. However, common CPS hardware-comprising battery-powered and severely resource-constrained devices interconnected via low-power wireless-greatly complicates attaining the required communication guarantees. VIRTUS fills this gap by providing atomic multicast and view management atop resource-constrained devices, which together provide virtually synchronous executions that developers can leverage to apply established concepts from the dependable distributed systems literature. We build VIRTUS upon an existing best-effort communication layer, and formally prove the functional correctness of our mechanisms. We further show, through extensive real-world experiments, that VIRTUS incurs a limited performance penalty compared with best-effort communication. To the best of our knowledge, VIRTUS is the first system to provide virtual synchrony guarantees atop resource-constrained CPS hardware.

No abstract available.

High computational performance in multiprocessor system-on-chips (MPSoCs) is constrained by the ever-increasing power densities in integrated circuits, so that nowadays MPSoCs face various thermal issues. For instance, high chip temperatures may lead to long-term reliability concerns and short-term functional errors. Therefore, the new challenge in designing embedded real-time MPSoCs is to guarantee the final performance and correct function of the system, considering both functional and non-functional properties. One way to achieve this is by ruling out mapping alternatives that do not fulfill requirements on performance or peak temperature already in early design stages. In this article, we propose a thermal-aware optimization framework for mapping real-time applications onto MPSoC platforms. The performance and temperature of mapping candidates are evaluated by formal temporal and thermal analysis models. To this end, analysis models are automatically generated during design space exploration, based on the same specifications as used for software synthesis. The analysis models are automatically calibrated with performance data reflecting the execution of the system on the target platform. The data is automatically obtained prior to design space exploration based on a set of benchmark mappings. Case studies show that the performance and temperature requirements are often conflicting goals and optimizing them together leads to major benefits in terms of a guaranteed and predictable high performance.

Temperature plays an increasingly important role in the overall performance and reliability of a computing system. Multi- and many-core systems provide an opportunity to manage the overall temperature profile by cleverly designing the application-to-core mapping and the associated scheduling policies. An uncontrolled temperature profile may lead to an unplanned performance loss, since the system activates protective mechanisms such as voltage and/or frequency scaling to cool itself. Similarly, deep thermal cycles with high frequency lead to severe deterioration in the overall reliability of the system. Design space exploration tools are often used to optimize binding and scheduling choices based on a given set of constraints and objectives, thus motivating the need for fast and accurate temperature estimation techniques. We argue that the currently available techniques are not an ideal fit to design space exploration tools, and suggest a system level technique which is based on application fingerprinting. It does not need any information about the processor floorplan, the physical and thermal structure, or about power consumption. Instead, its temperature estimation is based on a set of application-specific calibration runs and associated temperature measurements using available built-in sensors. We show that a given application possesses a unique thermal signature on the system it executes on, which provides a computationally fast method to calculate accurate temperature traces. Extensive experimental studies show that our technique can estimate temperature on all cores of a system to within $5^{o}C$, and is three orders of magnitude faster than state of the art numerical simulators like \emph{Hotspot.}

The next generation of embedded software has high performance requirements and is increasingly dynamic. Multiple applications are typically sharing the system, running in parallel in different combinations, starting and stopping their individual execution at different moments in time. The different combinations of applications are forming system execution scenarios. In this paper, we present the distributed application layer, a scenario-based design flow for mapping a set of applications onto heterogeneous on-chip many-core systems. Applications are specified as Kahn process networks and the execution scenarios are combined into a finite state machine. Transitions between scenarios are triggered by behavioral events generated by either running applications or the run-time system. A set of optimal mappings are precalculated during design-time analysis. Later, at run-time, hierarchically organized controllers monitor behavioral events, and apply the precalculated mappings when starting new applications. To handle architectural failures, spare cores are allocated at design-time. At run-time, the controllers have the ability to move all processes assigned to a faulty physical core to a spare core. Finally, we apply the proposed design flow to design and optimize a picture-in-picture software.

We propose a performance verification technique for cyber-physical systems that consist of multiple control loops implemented on a distributed architecture. The architectures we consider are fairly generic and arise in domains such as automotive and industrial automation; they are multiple processors or electronic control units (ECUs) communicating over buses like FlexRay and CAN. Current practice involves analyzing the architecture to estimate worst-case end-to-end message delays and using these delays to design the control applications. This involves a significant amount of pessimism since the worst-case delays often occur very rarely. We show how to combine functional analysis techniques with model checking in order to derive a delay-frequency interface that quantifies the interleavings between messages with worst-case delays and those with smaller delays. In other words, we bound the frequency with which control messages might suffer the worst-case delay. We show that such a delay-frequency interface enables us to verify much tigher control performance properties compared to what would be possible with only worst-case delay bounds.

Mapping applications onto multiprocessor system-on-chip (MPSoC) devices is a well-known and complex optimization problem, receiving large interest in recent years. Diverse frameworks for mapping optimization have been developed, that typically distribute application tasks to available processors while optimizing one or more objectives such as performance and energy consumption. However, even though the memory subsystem is a resource that contributes drastically to the overall performance and energy consumption of the MPSoC, no mapping optimization framework is considering it so far. This paper addresses this challenge, and investigates the effect of memory hierarchies for MPSoC mapping. A memory-aware mapping optimization tool (that we refer to as MAMOT) has been developed for this purpose. We primarily focus on heterogeneous MPSoCs with heterogeneous memory hierarchies. Our evaluations show that considering memory mapping during MPSoC mapping optimization may reduce the application runtime up to 29.5% and its energy consumption up to 40%.

Nowadays, real-time applications expect the supporting computing system to be reconfigured at run-time. Even during such reconfiguration, timing requirements of the applications must be met. By extension, such requirements are relevant in the design of resource reservations techniques. In this work, we consider such a reconfiguration of the reservation provided by a constant bandwidth server (CBS). Firstly, we de-fine an exact notion of correctness of a server's reconfiguration. Then we design a provably correct server algorithm R-CBS that allows for run-time reconfiguration of a standard CBS. The algorithm maintains specific information about the execution trace and uses it to efficiently perform the reconfiguration at the earliest possible time. We highlight the advantages of R-CBS in comparison to reconfiguration of TDMA servers and in reconfiguring multiple servers simultaneously.

With increasing use of embedded systems in safety critical systems, architectures and design processes for safety have become a primary objective in systems design. Most such systems are also time critical leading to safety and time critical systems. Safety standards impose strong requirements on such systems challenging system performance and cost. Very often, however, only part of the functions is safety and time critical calling for a design approach that both meets the safety requirements and provides efficiency and flexibility for less critical functions. These conflicting requirements have given rise to the new research area of mixed critical system design with enormous practical relevance. The tutorial addresses key aspects of mixed critical system design.

Multicore architectures are increasingly used nowadays in embedded real-time systems. Parallel execution of tasks feigns the possibility of a massive increase in performance. However, this is usually not achieved because of contention on shared resources. Concurrently executing tasks mutually block their accesses to the shared resource, causing non-deterministic delays. Timing analysis of tasks in such systems is then far from trivial. Recently, several analytic methods have been proposed for this purpose, however, they cannot model complex arbitration schemes such as FlexRay which is a common bus arbitration protocol in the automotive industry. This paper considers real-time tasks composed of superblocks, i.e., sequences of computation and resource accessing phases. Resource accesses such as accesses to memories and caches are synchronous, i.e., they cause execution on the processing core to stall until the access is served. For such systems, the paper presents a state-based modeling and analysis approach based on Timed Automata which can model accurately arbitration schemes of any complexity. Based on it, we compute safe bounds on the worst-case response times of tasks. The scalability of the approach is increased significantly by abstracting several cores and their tasks with one arrival curve, which represents their resource accesses and computation times. This curve is then incorporated into the Timed Automata model of the system. The accuracy and scalability of the approach are evaluated with a real-world application from the automotive industry and benchmark applications.

We present the low-power wireless bus (LWB), a simple yet efficient communication support for low-power wireless networks. The LWB maps different communication demands onto fast Glossy network flooding, effectively turning the wireless network into a bus-like infrastructure. The LWB requires no information of the network topology, thus drastically reducing the control overhead of common solutions such as route maintenance, and natively supports many-to-many communication and mobile nodes in addition to more traditional static, one-to-many scenarios. For instance, experiments on a 90-node testbed show that on average the LWB reduces packet loss by a factor of 231 and energy consumption due to communication by a factor of 11 compared to a state-of-the-art many-to-many routing protocol.

We present pTunes, a framework for runtime adaptation of low-power MAC protocol parameters. The MAC operating parameters bear great influence on the system performance, yet their optimal choice is a function of the current network state. Based on application requirements expressed as network lifetime, end-to-end latency, and end-to-end reliability, pTunes automatically determines optimized parameter values to adapt to link, topology, and traffic dynamics. To this end, we introduce a flexible modeling approach, separating protocol-dependent from protocol-independent aspects, which facilitates using pTunes with different MAC protocols, and design an efficient system support that integrates smoothly with the application. To demonstrate its effectiveness, we apply pTunes to X-MAC and LPP. In a 44-node testbed, pTunes achieves up to three-fold lifetime gains over static MAC parameters optimized for peak traffic, the latter being current - and almost unavoidable - practice in real deployments. pTunes promptly reacts to changes in traffic load and link quality, reducing packet loss by 80% during periods of controlled wireless interference. Moreover, pTunes helps the routing protocol recover quickly from critical network changes, reducing packet loss by 70% in a scenario where multiple core routing nodes fail.

Several recent works consider the problem of temperature-constrained scheduling of jobs. In such attempts, speed of the processor and the execution of jobs is software-controlled such that temperature and performance constraints are met. An alternative approach is to use measurements from temperature sensors to actuate the speed of the processor as a feedback control loop. Though such a solution explicitly and independently meets the thermal constraints, the analysis of the real-time properties of tasks served by such a processor is not straightforward. In this paper, we study this problem for a variable stream of jobs characterized by an input arrival rate. We show that an intuitive notion of monotonicity extends to such a processor. Using this property, we present an analytical technique to determine the worst-case delay suffered by jobs. The presented technique efficiently and tightly determines the delay as a function of the initial temperature. The simplicity of this analysis motivates further analysis and mainstream use of such systems.

Due to increased on-chip power density, multi-core systems face various thermal issues. In particular, exceeding a certain threshold temperature can reduce the system's performance and reliability. Therefore, when designing a real-time application with non-deterministic workload, the designer has to be aware of the maximum possible temperature of the system. This paper proposes an analytic method to calculate an upper bound on the worst-case peak temperature of a real-time system with multiple cores generated under all possible scenarios of task executions. In order to handle a broad range of uncertainties, task arrivals are modeled as periodic event streams with jitter and delay. Finally, the proposed method is applied to a multi-core ARM platform and our results are validated in various case studies.

For hard real-time systems, worst-case timing models are employed to validate whether timeliness properties, such as meeting deadlines, are always satisfied. We argue that such a deadline-interface should be generalised in view of two separate motivations: (a) applications can tolerate bounded non-satisfaction of timeliness properties due to inherent robustness or relaxed quality requirements, and (b) worst-case timing models do not expose the occurrence of certain rare yet predictable events. As a more expressive interface, we propose the Rare-Event with Settling-Time (REST) model wherein, during rare events nominal timing models can be violated up to a known bound. Such a violation may lead to non-satisfaction of the timeliness properties up to a certain bound. We characterise this bound in terms of (a) the longest interval when the deadlines are not met, which we call the settling-time, and (b) the maximum number of jobs that can miss deadlines during the settling-time called the overshoot. We propose two models of rare events, characterised on an interval domain. For a single stream of jobs, we provide methods to tightly compute the settling-time and overshoot. For multiple streams of jobs on a single processor, we show that amongst schedulers agnostic to the occurrence of the rare event, the EDF scheduler optimally minimises the settling-time. In contrast, RM is not optimal within the class of fixed priority schedulers.

We present the Low-Power Wireless Bus (LWB), a communication protocol that supports several traffic patterns and mobile nodes immersed in static infrastructures. LWB turns a multi-hop low-power wireless network into an infrastructure similar to a shared bus, where all nodes are potential receivers of all data. It achieves this by mapping all traffic demands on fast network floods, and by globally scheduling every flood. As a result, LWB inherently supports one-to-many, many-to-one, and many-to-many traffic. LWB also keeps no topology-dependent state, making it more resilient to link changes due to interference, node failures, and mobility than prior approaches. We compare the same LWB prototype on four testbeds with seven state-of-the-art protocols and show that: (i) LWB performs comparably or significantly better in many-to-one scenarios, and adapts efficiently to varying traffic loads; (ii) LWB outperforms our baselines in many-to-many scenarios, at times by orders of magnitude; (iii) external interference and node failures affect LWB's performance only marginally; (iv) LWB supports mobile nodes acting as sources, sinks, or both without performance loss.

In the context of wireless data collection, a common application class in wireless sensor networks, this paper presents a novel, non-intrusive algorithm for the precise reconstruction of the packet path, the per-hop arrival order and the per-hop arrival times of individual packets from partial in-band information at runtime. Information is reconstructed outside the network immediately after a packet is received at the sink. After establishing the correctness of our proposed algorithm, we evaluate its performance in testbed experiments using CTP and Dozer, two well-known data collection protocols. Foremost interested in obtaining a better understanding of the performance of long-term real-world deployments, Multi-hop Network Tomography (MNT) is applied to in total more than 140 million packets that have been obtained from three multi-year WSN deployments of the PermaSense project. The capabilities of the performance analysis of deployed systems using the proposed algorithm and methodology are demonstrated in a case study.

In the context of low-power wireless sensor networks, this paper presents multi-hop network tomography (MNT), a novel, non-intrusive algorithm for reconstructing the path, the per-hop arrival order, and the per-hop arrival time of individual packets at runtime. While explicitly transmitting this information over the radio would negatively impact the performance of the system under investigation, information is instead reconstructed after packets have been received at the sink.

Modern real-time streaming applications are increasingly implemented on multiprocessor systems-on-chip (MPSoC). The implementation, as well as the verification of real-time applications executing on MPSoCs, are difficult tasks, however. A major challenge is the performance analysis of MPSoCs, which is required for early design space exploration and final system verification. Simulation-based methods are not well-suited for this purpose, due to long runtimes and non-exhaustive corner-case coverage. To overcome these limitations, formal performance analysis methods that provide guarantees for meeting real-time constraints have been developed. Embedding formal performance analysis into the MPSoC design cycle requires the generation of a faithful analysis model and its calibration with the system-specific parameters. In this article, a design flow that automates these steps is presented. In particular, we integrate modular performance analysis (MPA) into the distributed operation layer (DOL) MPSoC programming environment. The result is an MPSoC software design flow that allows for automatically generating the system implementation, together with an analysis model for system verification.

Traffic shaping is a well-known technique in the area of networking and is proven to reduce global buffer requirements and end-to-end delays in networked systems. Due to these properties, shapers also play an increasingly important role in the design of multiprocessor embedded systems that exhibit a considerable amount of on-chip traffic. Despite the growing importance of traffic shapping in this area, no methods exist for analyzing shapers in distributed embedded systems and for incorporating them into a system-level performance analysis. Until now it was not possible to determine the effect of shapers on end-to-end delay guarantees or buffer requirements in such systems. In this work, we present a method for analyzing greedy shapers, and we embed this analysis method into a well-established modular performance analysis framework for real-time embedded systems. The presented approach enables system-level performance analysis of complete systems with greedy shapers, and we prove its applicability by analyzing three case study systems.

Cyber-Physical Systems (CPS) require a high degree of reliability and robustness. Hence it is important to assert their correctness with respect to extra-functional properties, like power consumption, temperature, etc. In turn the physical quantities may be exploited for assessing system implementations. This article develops a methodology for utilizing measurements of physical quantities for testing the conformance of a running CPS with respect to a formal description of its required behavior allowing to uncover defects. We present foundations and implementations of this approach and demonstrate its usefulness by conformance testing power measurements of a wireless sensor node with a formal model of its power consumption.

Dynamic thermal management (DTM) techniques to manage the load on a system to avoid thermal hazards are soon becoming mainstream in today's systems. With the increasing percentage of leakage power, switching off the processors is becoming a viable alternative technique to speed scaling. For real-time applications, it is crucial that under such techniques the system still meets the performance constraints. In this paper we study stop-go scheduling to minimize peak temperature when scheduling an application, modeled as a task-graph, within a given makespan constraint. For a given static-ordering of execution of the tasks, we derive the optimal schedule referred to as the JUST schedule. We prove that for periodic task-graphs, the optimal temperature is independent of the chosen static-ordering when following the proposed JUST schedule. Simulation experiments validate the theoretical results.

This paper advocates a rigorously formal and compositional style for obtaining key performance and/or interface metrics of systems with real-time constraints. We propose a hierarchical approach that couples the independent and different by nature frameworks of Modular Performance Analysis with Real-time Calculus (MPA-RTC) and Parametric Feasibility Analysis (PFA). Recent work on Real-time Calculus (RTC) has established an embedding of state-based component models into RTC-driven performance analysis for dealing with more expressive component models. However, with the obtained analysis infrastructure it is possible to analyze components only for a fixed set of parameters, e.g., fixed CPU speeds, fixed buffer sizes etc., such that a big space of parameters remains unstudied. In this paper, we overcome this limitation by integrating the method of parametric feasibility analysis in an RTC-based modeling environment. Using the PFA tool-flow, we are able to find regions for component parameters that maintain feasibility and worst-case properties. As a result, the proposed analysis infrastructure produces a broader range of valid design candidates, and allows the designer to reason about the system robustness.

When designing an evolutionary algorithm, one question which arises is what a good mutation operator should look like. In order to be able to anticipate which operators may perform well and which may perform poorly, knowledge about the behavior of the mutation operator is necessary. To this end, we formally define three operator properties: Exhaustiveness, locality and unbiasedness. Furthermore, we provide statistical measures that allow to compare operators that work on the same optimization problem. The novelty of our approach is that the properties are formally defined in a unified manner, and that the measures can be calculated on arbitrary decision spaces, only assuming that a distance measure between solutions in decision space is given. Tests on a binary decision space using several mutation operators with known properties show that the statistical measures presented in this paper are able to reflect the properties well. Also, the measures are calculated for mutation operators of a more complex problem, namely the cluster partitioning problem. To test the validity of our measures, we introduce an exploration benchmark that measures how well the solutions can move across the decision space when applying a mutation operator to them. Tests on both the binary and the partitioning problem show that our measures reflect the operator behavior well.

With increasing power densities, managing on-chip temperatures has become an important design challenge. We propose a novel approach to this problem with the use of shapers to dynamically and selectively insert idle times during the execution of hard real-time jobs on a single speed processor. For the class of leaky bucket shapers which have a lightweight implementation, we derive the shaper such that no job misses its real-time deadline and the peak temperature is optimally reduced. The analysis and design of such shapers allows for dynamically variable streams of jobs; for instance, periodic streams with jitter. We extend our results to consider non-zero power and timing overhead in transitioning to the idle mode. With experimental results, we demonstrate that the proposed approach provides a large improvement: on average 8K peak temperature reduction or 40% increase in utilization for a given peak temperature.

Nowadays, the reliability and performance of modern embedded multi-processor systems is threaten by the ever-increasing power densities in integrated circuits, and a new additional goal of software synthesis is to reduce the peak temperature of the system. However, in order to perform thermal-aware mapping optimization, the timing and thermal characteristics of every candidate mapping have to be analyzed. While the task of analyzing timing characteristics of design alternatives has been extensively investigated in recent years, there is still a lack of methods for accurate and fast thermal analysis. In order to obtain desired evaluation times, the system has to be simulated at a high abstraction level. This often results in a loss of accuracy, mainly due to missing knowledge of system's characteristics. This paper addresses this challenge and presents methods to automatically calibrate high-level thermal evaluation methods. Furthermore, the viability of the methods for automated model calibration is illustrated by means of a novel high-level thermal evaluation method.

The field of Wireless Sensor Networks (WSNs) is now in a stage where serious applications of societal and economical importance are in reach. For example, it is well known that the global climate change dramatically influences the visual appearance of mountain areas like the European Alps. Very destructive geological processes may be triggered or intensified, impacting the stability of slopes, possibly inducing landslides. Unfortunately, the interactions between these complex processes is poorly understood. Therefore, one needs to develop wireless sensing technology as a new scientific instrument for environmental sensing under extreme conditions. Large variations in temperature, humidity, mechanical forces, snow coverage, and unattended operation play a crucial role in long-term deployments. We argue that, in order to significantly advance the application domain, it is inevitable that sensor networks be created as a quality scientific instrument with known and predictable properties, and not as a research toy delivering average observations at best. In this paper, key techniques for achieving highly reliable, yet resource efficient wireless sensor networks are discussed on the basis of productive wireless sensor networks measuring permafrost processes in the Swiss Alps.

Component-based validation techniques for parallel and distributed embedded systems should be able to deal with heterogeneous components, interactions, and specification mechanisms. This paper describes various approaches that allow the composition of subsystems with different execution and interaction semantics by combining computational and analytic models. In particular, this work shows how finite state machines, timed automata, and methods from classical real-time scheduling theory can be embedded into MPA (modular performance analysis), a contemporary framework for system-level performance analysis. The result is a powerful tool for compositional performance validation of distributed real-time systems.

With the evolution of today's semiconductor technology, chip temperature increases rapidly mainly due to the growth in power density. For modern embedded real-time systems, it is crucial to estimate maximal temperatures in order to take mapping or other design decisions to avoid burnout, and still be able to guarantee meeting real-time constraints. This paper provides answers to the question: When work-conserving scheduling algorithms, such as earliest-deadline-first (EDF), rate-monotonie (RM), deadline-monotonic (DM), are applied, what is the worst-case peak temperature of a real-time embedded system under all possible scenarios of task executions? We propose an analytic framework, which considers a general event model based on network and real-time calculus. This analysis framework has the capability to handle a broad range of uncertainties in terms of task execution times, task invocation periods, and jitter in task arrivals. Simulations show that our framework is a cornerstone to design real-time systems that have guarantees on both schedulability and maximal temperatures.

With ever-increasing power densities, managing on-chip temperatures by optimizing mapping and scheduling of tasks is becoming increasingly necessary. We study the minimization of end-to-end delay for thermally constrained scheduling of an application that is specified as a task graph and is executing on parallel processors without speed scaling. We show that task graph scheduling on thermally constrained systems is monotonic, i.e., delaying the execution of a task longer than necessary cannot lead to the early completion of any other task. Using this monotonicity principle, we design the provably optimal schedule for a given mapping, called the JUST schedule. The JUST schedule can be easily implemented using temperature sensors. We then present different thermal-aware modifications to standard mapping heuristics and evaluate them on a large set of problem instances. The experimental results illustrate that with simple thermal-aware modifications, mappings with much smaller end-to-end delay can be identified.

Servers have been proposed to implement resource reservations on shared resources. Such reservations isolate the temporal behavior of tasks sharing the shared resources, thereby providing performance guarantees to tasks independent of other tasks. In existing work, resource reservation has been synonymous to utilization (also called bandwidth) on the resource, i.e., we can reserve only a constant fraction of the resource utilization via a server. Such reservation schemes are not suited to serve interrupt-like tasks: tasks that occur seldom but require quick service or tasks with jitter. With this motivation, we present a generalized server algorithm, called Demand Bound Server (DBS), whose offered service is characterized by the demand bound function (dbf) of the task it serves. We show that schedulability of DBS tightly follows that of EDF, and if schedulable a DBS provides a performance guarantee as requested by the dbf of the task. We present an implementation of DBS when the dbf is a shifted-periodic curve and characterize its overhead. We also present efficient composition operations on DBS that widen the class of implemented servers to tightly serve tasks arising in most practical settings.

Typically, optimization attempts to find a solution which minimizes the given objective function. But often, it might also be useful to obtain a set of structurally very diverse solutions which all have acceptable objective values. With such a set, a decision maker would be given a choice of solutions to select from. In addition, he can learn about the optimization problem at hand by inspecting the diverse close-to-optimal solutions. This paper proposes NOAH, an evolutionary algorithm which solves a mixed multi-objective problem: Determine a maximally diverse set of solutions whose objective values are below a provided objective barrier. It does so by iteratively switching between objective value and set-diversity optimization while automatically adapting a constraint on the objective value until it reaches the barrier. Tests on an nk-Landscapes problem and a 3-Sat problem as well as on a more realistic bridge construction problem show that the algorithm is able to produce high quality solutions with a significantly higher structural diversity than standard evolutionary algorithms.

In this paper, we present a performance analysis of the communication stack of the PermaDozer application. Our offline analysis is based on long-term performance data from three diverse real-world wireless sensor network deployments. Two of the deployments considered are located in the Swiss mountains at 3.500 meters a.s.l., the third deployment is located along a river in the Swiss midlands. Apart from climatic differences, the three deployments also vary in network size, network density, node placement, and type and quantity of RF interference. From September 2008 to May 2011 more than 99.6 million WSN packets have been collected serving as the dataset. All three deployments are based on the same software and hardware. This allows us to comparatively study the performance of the PermaDozer protocol under different deployment settings and environmental conditions. For the period between June 2010 and May 2011, our networks achieved a data yield of >; 99.5%. But, we can also clearly notice that achieving this performance requires varying effort in terms of radio duty cycle resulting in different power consumption and network lifetime.

Modern multiprocessor and multicore architectures adopt shared resources to meet increased performance requirements. Adaptive arbiters, such as FlexRay, have been adopted to grant access to shared resources. While increasing the performance, timing analysis is more challenging with this kind of arbiter. This paper considers real-time tasks that are composed of super blocks, while super blocks themselves are composed of phases. Phases are characterized by their worst-case computation time on their processing element and their worst-case number of access requests to a shared resource. Resource accesses, such as access to caches or scratchpad memory, are synchronous and cause the processing element to stall until the access is served. Based on dynamic programming, we develop an algorithm that safely derives an upper-bound of the worst-case response time of a phase. The worst-case response time of a task can then be determined for both sequential or time-triggered execution of super blocks. Experimental results are conducted for a real-world application.

As modern VLSI technology is scaling to the deep sub-micron domain, embedded systems face a power-efficiency problem, i.e., static power consumption caused by the leakage current. This paper explores how to use dynamic power management to reduce static power consumption while guaranteeing hard real-time properties. To tackle event arrivals with non-deterministic patterns, the arrival curve model is adopted to describe event arrivals in the interval domain. To reduce runtime overhead, periodic power management is investigated, which turns on and off a system with a fixed period. To reduce the timing complexity of computing such a periodic scheme, two algorithms, which are based on a linear-segmented representation of the arrival curve model, are proposed to trade the complexity with accuracy for energy reduction. We also present simulation results to demonstrate the effectiveness of our algorithms.

Several servers have been proposed to schedule streams of a periodic jobs in the presence of other periodic tasks. Standard schedulability analysis has been extended to consider such servers. However, not much attention has been laid on computing the worst-case delay suffered by a given stream of jobs when scheduled via a server. Such analysis is essential for using servers to schedule hard real-time tasks. We illustrate, with examples, that well established resource models, such as supply bound function and models from Real-Time Calculus, do not tightly characterize servers. In this work, we analyze the server algorithm of the Constant Bandwidth Server and compute a provably tight resource model of the server. The approach used enables us to differentiate between the soft and hard variants of the server. A similar approach can be used to characterize other servers, the final results for which are presented.

SUMMARY With the growing complexity of embedded systems software, high code quality can only be achieved using a compiler. Sophisticated compilers provide a vast spectrum of various optimizations to improve code aggressively w.r.t. different objective functions, e.g. average‐case execution time ( ACET ) or code size. Owing to the complex interactions between the optimizations, the choice for a promising sequence of code transformations is not trivial. Compiler developers address this problem by proposing standard optimization levels, e.g. O3 or Os . However, previous studies have shown that these standard levels often miss optimization potential or might even result in performance degradation. In this paper, we propose the first adaptive worst‐case execution time ( WCET )‐aware compiler framework for an automatic search of compiler optimization sequences that yield highly optimized code. Besides the objective functions ACET and code size, we consider the WCET which is a crucial parameter for real‐time systems. To find suitable trade‐offs between these objectives, stochastic evolutionary multi‐objective algorithms identifying Pareto optimal solutions for the objectives 〈WCET, ACET 〉 and 〈WCET, code size 〉 are exploited. A comparison based on statistical performance assessments is performed that helps to determine the most suitable multi‐objective optimizer. The effectiveness of our approach is demonstrated on real‐life benchmarks showing that standard optimization levels can be significantly outperformed. Copyright © 2011 John Wiley & Sons, Ltd.

Dynamic power management has become essential for battery-driven embedded systems. This paper explores how to efficiently and effectively reduce the energy consumption of a device (system) for serving multiple event streams. Considering two different preemptive scheduling, i.e., earliest deadline first and fixed priority, we propose new method to adaptively control the power mode of the device according to historical arrivals of events. Our method can not only tackle arbitrary event arrivals but also provide hard real-time guarantees with respect to both timing and backlog constraints. Simulation results are presented as well to demonstrate the effectiveness of our approach.

In this paper a framework for energy management in energy harvesting embedded systems is presented. As a possible example scenario, we focus on wireless sensor nodes which are powered by solar cells. We demonstrate that classical power management solutions have to be reconceived and/or new problems arise if perpetual operation of the system is required. In particular, we provide a set of algorithms and methods for different application scenarios, including real-time scheduling, application rate control as well as reward maximization. The goal is to optimize the performance of the application subject to given energy constraints. Our methods optimize the system performance which allows the usage of, e.g., smaller solar cells and smaller batteries. Our theoretical results are supported by simulations using long-term measurements of solar energy in an outdoor environment. Furthermore, to demonstrate the practical relevance of our approaches, we measured the implementation overhead of our algorithms on real sensor nodes.

Multi-Processor Systems-on-Chip (MPSoC) are an increasingly important design paradigm not only for mobile embedded systems but also for industrial applications such as automotive and avionic systems. Such systems typically execute multiple concurrent applications, with different execution modes. Modes define differences in functionality and computational resource demands and are assigned with an execution probability. We propose a dynamic mapping approach to maintain low power consumption over the system lifetime. Mapping templates for different application modes and execution probabilities are computed offline and stored on the system. At runtime a manager monitors the system and chooses an appropriate pre-computed template. Experiments show that our approach outperforms global static mapping approaches up to 45%.

Multi-processor and multi-core systems are becoming increasingly important in time critical systems. Shared resources, such as shared memory or communication buses are used to share data and read sensors. We consider real-time tasks constituted by superblocks, which can be executed sequentially or by a time triggered static schedule. Three models to access shared resources are explored: (1) the dedicated access model, in which accesses happen only in dedicated phases, (2) the general access model, in which accesses could happen at anytime, and (3) the hybrid access model, combining the dedicated and general access model. For resource access based on a Time Division Multiple Access (TDMA) protocol, we analyze the worst-case completion time for a superblock, derive worst-case response times for tasks and obtain the relation of schedulability between different models. We conclude with proposing the dedicated sequential model as the model of choice for time critical resource sharing multi-processor/multi-core systems.

This paper summarizes a special session on multi-core/multi-processor system-on-chip (MPSoC) programming challenges. Wireless multimedia terminals are among the key drivers for MPSoC platform evolution. Heterogeneous multi-processor architectures achieve high performance and can lead to a significant reduction in energy consumption for this class of applications. However, just designing energy efficient hardware is not enough. Programming models and tools for efficient MPSoC programming are equally important to ensure optimum platform utilization. Unfortunately, this discipline is still in its infancy, which endangers the return on investment for MPSoC architecture designs. On one hand there is a need for maintaining and gradually porting a large amount of legacy code to MPSoCs. On the other hand, special C language extensions for parallel programming as well as adapted process network programming models provide a great opportunity to completely rethink the traditional sequential programming paradigm for sake of higher efficiency and productivity. MPSoC programming is more than just code parallelisation, though. Besides energy efficiency, limited and specialized processing resources, and real-time constraints also growing software complexity and mapping of simultaneous applications need to be taken into account. We analyze the programming methodology requirements for heterogeneous MPSoC platforms and outline new approaches.

Employing COTS components in real-time embedded systems leads to timing challenges. When multiple CPU cores and DMA peripherals run simultaneously, contention for access to main memory can greatly increase a task's WCET. In this paper, we introduce an analysis methodology that computes upper bounds to task delay due to memory contention. First, an arrival curve is derived for each core representing the maximum memory traffic produced by all tasks executed on it. Arrival curves are then combined with a representation of the cache behavior for the task under analysis to generate a delay bound. Based on the computed delay, we show how tasks can be feasibly scheduled according to assigned time slots on each core.

Leakage power consumption contributes significantly to the overall power dissipation for systems that are manufactured in advanced deep sub-micron technology. Different from many previous results, this paper explores leakage-aware energy-efficient scheduling if leakage power consumption depends on temperature. We propose a pattern-based approach which divides a given time horizon into several time segments with the same length, where the processor is in the active (dormant, respectively) mode for a fixed amount of time at the beginning (end, respectively) of each time segment. Computation is advanced in the active mode, whereas the dormant mode helps reduce the temperature via cooling as well as the leakage power consumption. Since the pattern-based approach leads to a steady state with an equilibrium temperature, we develop a procedure to find the optimal pattern whose energy consumption in steady state is the minimum. Compared to existing work, our approach is more effective, has less run-time scheduling overhead, and requires only a simple scheduler to control the system mode periodically. The paper contains extensive simulation results which validate the new models and methods.

Many real-time applications are designed to work in different operating modes each characterized by different functionality and resource demands. With each mode change, resource demands of applications change, and static resource reservations may not be feasible anymore. Dynamic environments where applications may be added and removed online also need to adapt their resource reservations. In such scenarios, resource reconfigurations are needed for changing the resource reservations during runtime and achieve better resource allocations. There are a lot of results in the scientific literature of how to find the optimal amount of resources needed by an application in the different operating modes, or how an application can perform safe mode transitions. However, the problem of resource reconfigurations for systems with reservations has not been addressed. A resource scheduler should be reconfigured online in such a way that it still guarantees a certain amount of resources during the reconfiguration process, otherwise applications may miss deadlines. The paper proposes a framework for scheduling real-time applications through scheduling servers that provide resource reservations, and algorithms for changing the resource reservations online while still guaranteeing the feasibility of the system and the schedulability of applications. The framework analysis is integrated into a well-known modular performance analysis paradigm based on Real-Time Calculus. The results are illustrated with examples and a case study.

Performance boosting of modern computing systems is constrained by the chip/circuit power dissipation. Dynamic voltage scaling (DVS) has been applied for reducing the energy consumption by dynamically changing the supply voltage. One can optimistically apply greedy online DVS scheduling algorithms by considering only the events that have arrived in the system. However, this might require a speed that is beyond a system's capability. Alternatively, one can pessimistically use a conservative speed to ensure timing guarantees, which might consume an excessive amount of energy as events might be processed faster than necessary. This paper presents an adaptive scheme that combines these two strategies for the scheduling of arbitrary event streams. The proposed adaptive DVS scheduler chooses the execution speed dynamically as long as it is below a certain threshold. Once the speed exceeds this threshold, the proposed scheduler operates at a constant (pessimistic) speed for guaranteeing the feasibility. The computation of the threshold speed is, however, not straight-forward. For deriving it, we make use of a framework based on timed model checking because the scheduler is strongly state-dependent. The resulting analysis framework allows to obtain the threshold speed for the proposed adaptive DVS scheduling algorithm such that both timing and speed constraints are guaranteed to be met and at the same time an energy-efficient execution is ensured.

Communication stacks are composed of distinct layers that, in principle, operate independently and interact through well-defined interfaces. However, resource constraints in sensor networks typically necessitate optimizations, leading to implicit assumptions and dependencies among layers (e.g., a collection protocol assumes the MAC protocol provides sufficient bandwidth). These dependencies are often tracked manually, yet become extremely complex as protocols evolve and requirements change. We propose to model assumptions and dependencies explicitly, as constraints on protocol parameters. This allows for using standard tools to generate feasible protocol configurations. We demonstrate the effectiveness of our approach using the example of FTSP running on top of a low-power listening MAC protocol.

With the growing complexity of embedded systems software, high code quality can only be achieved using a compiler. Sophisticated compilers provide a vast spectrum of various optimizations to improve code aggressively w. r. t. different objective functions, e. g., average-case execution time (ACET) or code size. Due to the complex interactions between the optimizations, the choice for a promising sequence of code transformations is not trivial. Compiler developers address this problem by proposing standard optimization levels, e. g., O3 or Os. However, previous studies have shown that these standard levels often miss optimization potential or might even result in performance degradation. In this paper, we propose the first adaptive WCET-aware compiler framework for an automatic search of compiler optimization sequences which yield highly optimized code. Besides the objective functions ACET and code size, we consider the worst-case execution time (WCET) which is a crucial parameter for real-time systems. To find suitable trade-offs between these objectives, stochastic evolutionary multi-objective algorithms identifying Pareto optimal solutions are exploited. A comparison based on statistical performance assessments is performed which helps to determine the most suitable multi-objective optimizer. The effectiveness of our approach is demonstrated on real-life benchmarks showing that standard optimization levels can be significantly outperformed.

This paper extends the methodology of analytic real-time analysis of distributed embedded systems towards merging and extracting sub-streams based on event type information. For example, one may first merge a set of given event streams, then process them jointly and finally decompose them into separate streams again. In other words, data streams can be hierarchically composed into higher level event streams and decomposed later on again. The proposed technique is strictly compositional, hence highly suited for being embedded into well known performance evaluation frameworks such as Symta/S and MPA (Modular Performance Analysis). It is based on a novel characterization of structured event streams which we denote as Event Count Curves. They characterize the structure of event streams in which the individual events belong to a finite number of classes. This new concept avoids the explicit maintenance of stream-individual information when routing a composed stream through a network of system components. Nevertheless it allows an arbitrary composition and decomposition of sub-streams at any stage of the distributed event processing. For evaluating our approach we analyze a realistic case-study and compare the obtained results with other existing techniques.

Modern computing systems have adopted multicore architectures and multiprocessor systems on chip (MPSoCs) for accommodating the increasing demand on computation power. However, performance boosting is constrained by shared resources, such as buses, main memory, DMA, etc.This paper analyzes the worst-case completion (response) time for real-time tasks when time division multiple access (TDMA) policies are applied for resource arbitration.Real-time tasks execute periodically on a processing element and are constituted by sequential superblocks. A superblock is characterized by its accesses to a shared resource and its computation time. We explore three models of accessing shared resources: (1)dedicated access model, in which accesses happen only at the beginning and the end of a superblock, (2) general access model, in which accesses could happen anytime during the execution of a superblock, and (3) hybrid access model, which combines the dedicated and general access models. We present a framework to analyze the worst-case completion time of real-time tasks (superblocks) under these three access models, for a given TDMA arbiter. We compare the timing analysis of the three proposed models for a real-world application.

Dynamic Voltage Scaling (DVS) has been widely used for decreasing the dynamic power dissipation of processors. For real-time systems, DVS techniques have been developed that permit to meet the timing constraints of multiple real-time tasks and at the same time reduce the overall dynamic energy consumption. Known methods for static priority DVS scheduling are, however, either restricted to simple periodic/sporadic task release patterns or presume full a priori knowledge of task release times. Moreover, none of the present approaches considers the optimization of task priorities for reducing the energy consumption. In this paper we explore how to determine the static priorities and individual execution speeds (supply voltages) of multiple tasks with non-deterministic release times bounded by arrival curves such that the energy consumption is reduced and the real-time constraints are met. The result are different heuristics for the design of DVS-based real-time systems with static priorities. We show that the proposed methodology leads to energy-efficient system designs and demonstrate the applicability of the approach by means of experiments.

Reliability and predictability of the timing behavior have shown to be major issues for wireless sensor network deployments. Real-time requirements presented by several applications can be fulfilled by implementing communication schemes that lower possible sources of non-determinism of the timing behavior, assuming that the nodes are synchronized. The predictability of current synchronization protocols, however, cannot be verified, due to potential interferences with other activities. In this paper we propose Secondis, a dissemination protocol that periodically synchronizes and orchestrates activities in the network, providing three main benefits. (1) The synchronization task is performed in short time windows, where no interferences can occur, independently of any available communication structure. (2) The synchronization is energy efficient, and (3) robust against link and node failures. Secondis provides probabilistic bounds about its predictability, by means of a probabilistic model checker analysis. It proposes a novel adaptive flooding scheme based on the observation that only a subset of the nodes is important for the propagation. The behavior is analyzed in simulation, using realistic models of the wireless channel and hardware clocks.

We analyze push and pull for data collection in wireless sensor networks. Most applications to date use the traditional push approach, where nodes transmit sensed data immediately to the sink. Using a pull approach, nodes store the data in their local flash memory, and only engage in communication during dedicated collection phases. We show how one can transform an existing push-based collection protocol into a pull-based one, and compare the power consumption of both approaches on a 35-node testbed. Our results show that substantial energy gains are possible with pull, provided that the application can tolerate a long latency.

Energy harvesting (also known as energy scavenging) is the process of generating electrical energy from environmental energy sources. There exists a variety of different energy sources such as solar energy, kinetic energy, or thermal energy. In recent years, this term has been frequently applied in the context of small autonomous devices such as wireless sensor nodes. In this article, a framework for energy management in energy harvesting embedded systems is presented. As a possible scenario, we focus on wireless sensor nodes that are powered by solar cells. We demonstrate that classical power management solutions have to be reconceived and/or new problems arise if perpetual operation of the system is required. In particular, we provide a set of algorithms and methods for various application scenarios, including real-time scheduling, application rate control, as well as reward maximization. The goal is to optimize the performance of the application subject to given energy constraints. Our methods optimize the system performance which, for example, allows the usage of smaller solar cells and smaller batteries. Furthermore, we show how to dimension important system parameters like the minimum battery capacity or a sufficient prediction horizon. Our theoretical results are supported by simulations using long-term measurements of solar energy in an outdoor environment. In contrast to previous works, we present a formal framework which is able to capture the performance, the parameters, and the energy model of various energy harvesting systems. We combine different viewpoints, include corresponding simulation results, and provide a thorough discussion of implementation aspects.

Recently, there has been a substantial interest in the design of systems that receive their energy from regenerative sources such as solar cells. In contrast to approaches that minimize the power consumption subject to performance constraints, we are concerned with optimizing the performance of an application while respecting the limited and time-varying amount of available power. In this paper, we address power management of, e.g., wireless sensor nodes which receive their energy from solar cells. Based on a prediction of the future available energy, we adapt parameters of the application in order to maximize the utility in a long-term perspective. The paper presents a formal model of the corresponding optimization problem including constraints concerning buffer sizes, timing, and rates. Instead of solving the optimization problem online which may be prohibitively complex in terms of running time and energy consumption, we apply multiparametric programming to precompute the application parameters offline for different environmental conditions and system states. In order to guarantee sustainable operation, we propose a hierarchical software design which comprises a worst-case prediction of the incoming energy. As a further contribution, we suggest a new method for approximate multiparametric linear programming which substantially lowers the computational demand and memory requirement of the embedded software. Our approaches are evaluated using long-term measurements of solar energy in an outdoor environment.

Assuming that evolutionary multiobjective optimization (EMO) mainly deals with set problems, one can identify three core questions in this area of research: 1) how to formalize what type of Pareto set approximation is sought; 2) how to use this information within an algorithm to efficiently search for a good Pareto set approximation; and 3) how to compare the Pareto set approximations generated by different optimizers with respect to the formalized optimization goal. There is a vast amount of studies addressing these issues from different angles, but so far only a few studies can be found that consider all questions under one roof. This paper is an attempt to summarize recent developments in the EMO field within a unifying theory of set-based multiobjective search. It discusses how preference relations on sets can be formally defined, gives examples for selected user preferences, and proposes a general preference-independent hill climber for multiobjective optimization with theoretical convergence properties. Furthermore, it shows how to use set preference relations for statistical performance assessment and provides corresponding experimental results. The proposed methodology brings together preference articulation, algorithm design, and performance assessment under one framework and thereby opens up a new perspective on EMO.

Multiprocessor SOC platforms have been adopted for a wide range of high-performance applications, like automotive and avionic systems. Task assignment and processing unit allocation are key steps in the design of predictable and efficient embedded systems. Given the execution modes of applications, we propose a methodology to compute a task to processing element mapping, such that the expected average power consumption is minimized. Changing usage scenarios are represented by varying execution probabilities of modes. Statically precomputed template mappings for each execution probability are stored on the system and applied at runtime, allowing the system to adapt to changing environmental conditions. The underlying model considers static (leakage) and dynamic power. This study shows that deriving approximative solutions with a constant worst-case approximation factor in polynomial time is not achievable unless P = NP, even if a feasible task mapping is provided as an input. A polynomial-time heuristic algorithm is proposed that applies a multiple-step heuristic to derive template mappings. At runtime a manager monitors the system and chooses an appropriate precomputed template, hence low power-consumption is maintained over the systems lifetime. Experimental results reveal the effectiveness of the proposed algorithm by comparing the derived solutions to the optimal ones, obtained via an integer linear program (ILP).

Many application domains require adaptive real-time embedded systems that can change their functionality over time. In such systems it is not only necessary to guarantee timing constraints in every operating mode, but also during the transition between different modes. Known approaches that address the problem of timing analysis over mode changes are restricted to fixed priority scheduling policies. In addition, most of them are also limited to simple periodic event stream models and therefore, they can not faithfully abstract the bursty timing behavior which can be observed in embedded systems. In this paper, we propose a new method for the design and analysis of adaptive multi-mode systems that supports any event stream model and can handle earliest deadline first (EDF) as well as fixed priority (FP) scheduling of tasks. We embed the analysis method into a well-established modular performance analysis framework based on Real-Time Calculus and prove its applicability by analyzing a case study.

As application complexity increases, modern embedded systems have adopted heterogeneous processing elements to enhance the computing capability or to reduce the power consumption. The heterogeneity has introduced challenges for energy efficiency in hardware and software implementations. This paper studies how to partition real-time tasks on a platform with heterogeneous processing elements (processors) so that the energy consumption can be minimized. The power consumption models considered in this paper are very general by assuming that the energy consumption with higher workload is larger than that with lower workload, which is true for many systems. We propose an approximation scheme to derive near-optimal solutions for different hardware configurations in energy/power consumption. When the number of processors is a constant, the scheme is a fully polynomial time approximation scheme (FPTAS) to derive a solution with energy consumption very close to the optimal energy consumption in polynomial-time/space complexity. Experimental results reveal that the proposed scheme is very effective in energy efficiency with comparison to the state-of-the-art algorithm.

This paper advocates a strict compositional and hybrid approach for obtaining key (performance) metrics of embedded systems. At its core the developed methodology abstracts system components by either flow-oriented and purely analytic descriptions or by state-based models in the form of timed automata. The interaction among the heterogeneous components is modeled by streams of discrete activity-triggers. In total this yields a hybrid framework for the compositional analysis of embedded systems. It supplements contemporary techniques for the following reasons: (a) state space explosion as intrinsic to formal verification is limited to the level of isolated components; (b) computed performance metrics such as buffer sizes, delays and utilization rates are not overly pessimistic, because coarse-grained purely analytic models are used for components only which conform to the stateless model of computation. For demonstrating the usefulness of the presented ideas we implemented a corresponding tool-chain and investigated the performance of a two-staged computing system, where one stage exhibits state-dependent behavior only coarsely coverable by a purely analytic and stateless component abstraction.

Applications for parallel and distributed embedded systems are often specified as dataflow graphs with dependency cycles. Examples of corresponding models of computation are marked graphs or synchronous dataflow (SDF) graphs. Performance analysis is often used in the exploration of different implementation alternatives or in order to provide guarantees on the timing behavior. This paper describes a new approach to the modular performance analysis of cyclic dataflow graphs such as SDF graphs as existing component-based analysis methods are not able to faithfully deal with cycles in the event flow. The new method results in tight bounds on essential quantities like buffer sizes, end-to-end delays and throughput. Because of the generality of the approach, one can analyze not only systems that can be modeled as marked graphs but also implementations that contain buffers with finite sizes, that produce system-wide back-pressure caused by blocking write semantics. The embedding of the novel approach into a modular performance analysis method allows the analysis of distributed implementations that use resource sharing mechanisms such as fixed-priority scheduling and time division multiple access (TDMA). The paper presents the new models and methods as well as experimental results.

Dynamic voltage scaling (DVS) has been widely adopted to reduce the energy consumption resulting from the dynamic power of modern processors. However, while the leakage power resulting from the leakage current becomes significant, how to aggregate the idle time to turn processors to the sleep or dormant modes is crucial in reducing the overall energy consumption. Moreover, for systems with non-DVS components, the execution order of tasks also affects the system-wide energy consumption. With the consideration of the dynamic and leakage power of processors as well as the power consumption resulting from non-DVS components, this paper summarizes our work on energy-efficient real-time task scheduling for both uniprocessor and multiprocessor platforms through procrastination of task executions, preemption control, and proper task assignment.

Adopting multiple processing units to enhance the computing capability or reduce the power consumption has been widely accepted for designing modern computing systems. Such configurations impose challenges on energy efficiency in hardware and software implementations. This work targets power-aware and energy-efficient task partitioning and processing unit allocation for periodic real-time tasks on a platform with a library of applicable processing unit types. Each processing unit type has its own power consumption characteristics for maintaining its activeness and executing jobs. This paper proposes polynomial-time algorithms for energy-aware task partitioning and processing unit allocation. The proposed algorithms first decide how to assign tasks onto processing unit types to minimize the energy consumption, and then allocate processing units to fit the demands. The proposed algorithms for systems without limitation on the allocated processing units are shown with an (m + 1)-approximation factor, where mis the number of the available processing unit types. For systems with limitation on the number of the allocated processing units, the proposed algorithm is shown with bounded resource augmentation on the limited number of allocated units. Experimental results show that the proposed algorithms are effective for the minimization of the overall energy consumption.

Power management has been a critical issue in the design of embedded systems due to the limited power supply. To prolong the lifetime, energy minimization has been studied under performance constraints in the past decade. The emerging embedded systems with the capability to harvest energy from the environment have recently triggered the revision of power management to improve the quality of service dynamically. As the available power/energy of an electronic device changes over time and is limited by many environmental factors, the system has to decide when to change to which service level to provide better quality of service without wasting the harvested energy. In this paper, we explore how to maximize the quality of service, in terms of system rewards, of a periodic application with discrete levels in an energy harvesting system. To decide service levels in a time horizon, this paper presents algorithms to derive optimal solutions if the future harvested energy is known. In addition, we present efficient algorithms to derive near-optimal solutions approximately. Our work is supported by simulation results which are based on long-term measurements of the power generated by real solar cells.

Thermal management becomes a prominent issue in system design for both server systems and embedded systems. A system could fail if the peak temperature exceeds its thermal constraint. This research studies thermal-constrained scheduling for frame-based real-time tasks on a dynamic voltage/speed scaling system. Our objective is to design speed schedulers for real-time tasks by utilizing dynamic voltage/speed scaling to meet both timing and thermal constraints. Two approaches are proposed: One is based on the minimization of the response time under the thermal constraint, and the other is based on the minimization of the temperature under the timing constraint. We present detailed schedulability analysis for both proposed approaches. Our data show that our proposed proactive approaches outperform existing reactive ones.

As the power density of modern electronic circuits increases dramatically, systems are prone to overheating. Thermal management has become a prominent issue in system design. This paper explores thermal-aware scheduling for sporadic real-time tasks to minimize the peak temperature in a homogeneous multicore system, in which heat might transfer among some cores. By deriving an ideally preferred speed for each core, we propose global scheduling algorithms which can exploit the flexibility of multicore platforms at low temperature. Compared with load-balancing strategies, the proposed algorithms can significantly reduce the peak temperature by up to 30degC to 70degC for simulated platforms.

Multiprocessor SoC platforms have been adopted for a wide range of high performance applications. Task assignment and processing unit allocation are key steps in the design of predictable and efficient embedded systems. Provided that the probability distributions and mutual exclusion conditions for executing applications are known a priori, this paper explores the mapping of tasks onto processing units while minimizing the expected average power consumption. The underlying model considers static (leakage) and dynamic power. This study shows that deriving approximative solutions with a constant worst-case approximation factor in polynomial time is not achievable unless P=NP, even if a feasible task mapping is provided as an input. A polynomial-time heuristic algorithm is proposed that applies a multiple-step heuristic. Experimental results reveal the effectiveness of the proposed algorithm by comparing the derived solutions to the optimal ones, obtained via an integer linear program (ILP) specification.

Energy-efficient and power-aware designs have played important roles in modern computing systems to reduce the power bills for server systems or prolong the lifetime of embedded devices. Moreover, systems with multiple heterogeneous processing units have been widely adopted to enhance the computing capability or reduce the power consumption. This work explores how to synthesize a heterogeneous multiprocessor platform or select processing units with the partitioning of real-time tasks so that the energy consumption is minimized. Given a set of processing unit types, characterized by the power consumption for maintaining activeness and executing jobs, this paper proposes an efficient and effective algorithm to allocate processing units with energy-efficient task partitioning. We show that the algorithm is with a (1+ ln n)-approximation factor, in worst cases, for processing unit types with a variety of power consumption models, where n is the number of tasks. The approximation factor is asymptotically optimal for polynomial-time approximation algorithms unless P = NP. Experimental results show that the proposed algorithm is effective for energy consumption minimization.

Thermal constraints have limited the performance improvement of modern computing systems in recent years. As a system could fail if the peak temperature exceeds its thermal constraint, overheating should be avoided while designing a system. Moreover, higher temperature also leads to higher leakage power consumption. This paper explores dynamic thermal management to minimize the energy consumption for a specified computing demand under the thermal constraint. We develop energy-efficient speed scheduling schemes for frame-based real-time tasks under thermal constraints. Experimental results reveal the effectiveness of the proposed scheme in terms of energy consumption in comparison with the reactive schemes in the literature.

Performance boosting of modern computing systems has been constrained by the significant chip/circuit power dissipation. Dynamic voltage scaling (DVS) has been applied in the past decade for reducing the energy consumption by dynamically changing the supply voltage. On-line scheduling algorithms for DVS systems usually guarantee the real-time constraints of the system based on the condition that they can select any system speed that is sufficiently high to allow processing of all events within their deadlines. However, practical systems have a maximum available system speed and the feasibility of using on-line DVS algorithms needs to be verified during design time, i.e., they will never require during runtime a speed higher than the maximum available. This paper presents feasibility analysis of two on-line DVS algorithms that can compute in advance an upper bound on the system speed that these algorithms may require given that there is a single input event stream described by the worst-case event arrivals in interval domain. Moreover, we also present new results on the competitive ratios of the resulting schedules for energy consumption minimization with comparison to the off-line optimal solutions to show the effectiveness of the two algorithms. At the end, the performance of the different algorithms is evaluated.

Power dissipation has constrained the performance boosting of modern computer systems in the past decade. Dynamic power management has been widely applied to change the system (or device) state dynamically to reduce the power consumption. This paper explores how to effectively reduce the energy consumption to handle event streams with hard real-time guarantees. We adopt Real-Time Calculus to describe the event arrival and resource service by arrival curves and service curves in the interval domain, respectively. We develop online algorithms to adaptively control the power mode of the device, postponing the processing of arrival events as late as possible. Profited from the worst-case interval-based abstraction, our algorithms can on one hand tackle arbitrary event arrivals (even with burstiness) and on the other hand guarantee hard real-time requirements in terms of both timing and backlog constraints. We also present simulation results to demonstrate the effectiveness of our algorithms.

Wireless sensor networks (WSNs) are used for long-term observation and monitoring. Such long-lasting deployments require different maintenance tasks, such as the replacement of nodes and the most critical initial installation of the sensor nodes. During maintenance, the actual node placement is modified resulting in temporary topology fluctuations, which are very expensive in terms of energy. We propose the NoSE protocol stack enhancement for WSNs to target maintenance tasks. NoSE provides the functionality for switching the network between an operational state and a deep sleep state. The deep sleep state allows for switching the network to energy savings, while performing maintenance. The network may be woken up at any given time. During the time bounded start-up, a comprehensive neighborhood assessment provides a solid basis for the subsequent network topology setup. Thus the success of a maintenance task, e.g., the initial deployment of the nodes, can be instantly validated. We present NoSE on a case study focusing on the initialization of a fire-detector WSN validated on a testbed and in simulation.

A vital factor for a successful deployment of sensor nodes is testing of all system aspects in a realistic setup. This work presents a testbed architecture which allows for detailed monitoring and stimulation of a wireless sensor node. In particular, time-accurate state extraction and power measurements are provided in a distributed, yet synchronized context. The FlockLab testbed architecture provides a distributed lab instrument, where detailed observations of every sensor node enable thorough testing. Software services allow for formulating testcases and reliable test data collection.

Within the PermaSense project, two wireless sensor networks have been deployed for a long-term operation in the Swiss Alps. For enabling state-of-the-art permafrost research based on the collected data, highest possible data quality and yield have to be ensured. But, the operation of wireless sensors networks remains a hard research problem. Firstly, deployed wireless sensors networks are subject to continuous changes. Second, there are scenarios that can only be tested in the field as the capabilities of testbeds are too limited. Basically, it is not possible to test for many months before deploying in the field. In this poster, we present an analysis of our data that has been collected over nine months. In addition to describing our system design and methods, we also share our experiences from discovered severe incidences.

In this paper, we discuss the idea of incorporating preference information into evolutionary multi-objective optimization and propose a preference-based evolutionary approach that can be used as an integral part of an interactive algorithm. One algorithm is proposed in the paper. At each iteration, the decision maker is asked to give preference information in terms of his or her reference point consisting of desirable aspiration levels for objective functions. The information is used in an evolutionary algorithm to generate a new population by combining the fitness function and an achievement scalarizing function. In multi-objective optimization, achievement scalarizing functions are widely used to project a given reference point into the Pareto optimal set. In our approach, the next population is thus more concentrated in the area where more preferred alternatives are assumed to lie and the whole Pareto optimal set does not have to be generated with equal accuracy. The approach is demonstrated by numerical examples.

Solar harvesting circuits have been recently proposed to increase the autonomy of embedded systems. One key design challenge is how to optimize the efficiency of solar energy collection under non stationary light conditions. This paper proposes a scavenger that exploits miniaturized photovoltaic modules to perform automatic maximum power point tracking at a minimum energy cost. The system adjusts dynamically to the light intensity variations and its measured power consumption is less than 1 mW. Experimental results show increments of global efficiency up to 80%, diverging from ideal situation by less than 10%, and demonstrate the flexibility and the robustness of our approach.

This paper is concerned with solar driven sensors deployed in an outdoor environment. We present feedback controllers which adapt parameters of the application such that a maximal utility is obtained while respecting the time-varying amount of available energy. We show that already simple applications lead to complex optimization problems, involving unacceptable running times and energy consumptions for resource constrained nodes. In addition, naive designs are highly susceptible to energy prediction errors. We address both issues by proposing a hierarchical control approach which both reduces complexity and increases robustness towards prediction uncertainty. As a key component of this hierarchical approach, we propose a new worst-case energy prediction algorithm which guarantees sustainable operation. All methods are evaluated using long-term measurements of solar energy in an outdoor setting. Furthermore, we measured the implementation overhead on a real sensor node.

The Modular Performance Analysis based on Real-Time Calculus (MPA-RTC), developed by Thiele et al., is an abstraction for the analysis of component-based real-time systems. The formalism uses an abstract stream model to characterize both workload and availability of computation and communication resources. Components can then be viewed as stream transformers. The Real-Time Calculus has been used successfully on systems where dependencies between components, via either workload or resource streams, are acyclic. For systems with cyclic dependencies the foundations and performance of the formalism are less well understood.

Modern computing systems often adopt multiple processing elements to enhance the computing capability or reduce the power consumption, especially for embedded systems. Such configurations impose challenges on energy efficiency in hardware and software implementations. This paper targets energy-efficient task partitioning for real-time tasks on a platform with two heterogeneous processing elements (processors), in which each one has its own characteristics on power consumption and job execution. This paper proposes a general framework for different hardware configurations in energy/power consumption. The framework provides a fully polynomial-time approximation scheme (FPTAS) to derive a solution with energy consumption very close to the optimal energy consumption in tolerable time/space complexity. Experimental results reveal that the proposed framework is effective in energy efficiency.

The pursuit of energy efficiency is becoming more and more important in hardware and software designs. This research explores energy-efficient scheduling for a periodic real-time task with uncertain execution time in dynamic voltage scaling (DVS) systems with non-negligible leakage/static power consumption. Distinct from the assumption of non-reducible static power consumption in the literature, this paper considers the possibility to reduce it by turning a processor to a dormant mode. We propose an algorithm to derive an optimal frequency assignment to minimize the expected energy consumption without procrastination, while another extended algorithm is developed to apply procrastination scheduling for further energy reduction. Experimental results show that the proposed algorithms can effectively minimize the expected energy consumption.

Renewable energies can enable embedded systems to be functional indefinitely. In particular for small autonomous sensors, energy harvesting techniques have attracted much interest. This paper considers systems which provide services periodically with adjustable quality evaluated in terms of rewards. The reward garnered for one service is monotonically increasing and strictly concave with respect to the energy consumption of the service. There exist two major constraints which arise due to the burstiness of common energy sources: (1) The harvested energy is temporarily low and the service must be lowered or suspended. (2) During bursts, the harvested energy exceeds the battery capacity. To resolve these issues, we propose algorithms to derive optimal solutions which maximize the overall reward. Furthermore, we determine the minimum battery capacity necessary to optimally exploit a given power source. By applying real data recorded for photovoltaic cells as the harvested energy, simulations illuminate the merits of our algorithms.

There are numerous possibilities to assemble a very resource-efficient and power-aware distributed sensor network tailored to a specific application. However, the task of initializing the network has not yet attracted much attention. This paper presents the NoSE (Neighbor Search and link Estimation) initialization scheme. NoSE provides an exhaustive neighbor search including a thorough link assessment, leveraging both high reactivity and greatly minimized energy consumption. Based on the information obtained in the initial link assessment phase, a routing protocol can subsequently set up and use an optimized network topology.

FPGA-based multiprocessor systems are viable solutions for stream-based embedded applications. They provide a software abstraction which enables coarse-grained parallel deployment on an FPGA chip. A widely used model for such a deployment is the class of Kahn process networks despite their limitation to pure FIFO communications. In this paper, a new mechanism denoted as windowed FIFO is introduced, extending the functionality for data transfer. The new concept allows non-destructive read, reordering, and skipping of data within a communication channel. We present the behavior, the software interface and the hardware design of this mechanism. We introduce our abstraction of WFIFO process network which is suitable for systematic and automated synthesis while still inheriting the nice property of Kahn process networks, i.e. being determinate. Also, we present illuminating examples to demonstrate the practicality of the outlined approach.

In modern embedded systems, data streams are often partitioned into separate sub-streams which are processed on parallel hardware components. To analyze the performance of these systems with high accuracy, correlations between event streams must be taken into account. No methods are known so far that are able to model such a scenario with the desired accuracy. In this paper, we present a new approach to analyze correlations and we embed this analysis method into a well-established modular performance analysis framework. The presented approach enables system-level performance analysis of complete systems by taking into account stream correlations and blocking-read semantics. Experimental results on a hardware-software prototyping system are provided that show the accuracy of the analysis in a practical application

Recently, there has been a substantial interest in the design of systems that receive their energy from regenerative sources such as solar cells. In contrast to approaches that attempt to minimize the power consumption we are concerned with adapting parameters of the application such that a maximal utility is obtained while respecting the limited and time-varying amount of available energy. Instead of solving the optimization problem on-line which may be prohibitively complex in terms of running time and energy consumption, we propose a parameterized specification and the computation of a corresponding optimal on-line controller. The efficiency of the new approach is demonstrated by experimental results and measurements on a sensor node

Of late, there has been a considerable interest in models, algorithms and methodologies specifically targeted towards designing hardware and software for streaming applications. Such applications process potentially infinite streams of audio/video data or network packets and are found in a wide range of devices, starting from mobile phones to set-top boxes. Given a streaming application and an architecture, the timing analysis problem is to determine the timing properties of the processed data stream, given the timing properties of the input stream. Most of the previous work related to estimating or optimizing these timing properties take a high-level view of the architecture and neglect microarchitectural features such as caches. In this paper, we show that an accurate estimation of a streaming application's timing properties, however, heavily relies on an appropriate modeling of the processor micro-architecture, such as its instruction cache. Towards this, we present a novel framework for timing analysis of stream processing applications. Our framework accurately models the evolution of the instruction cache of the underlying processor as a stream is processed, and the fact that the execution time involved in processing any data item depends on all the previous data items occurring in the stream. We have implemented a prototype of this framework partly in C and partly in Mathematica and plan to integrate it into a design-space exploration tool for system-level design of hardware-software architectures for streaming applications.

System level performance analysis plays a fundamental role in the design process of real-time embedded systems. Several different approaches have been presented so far to address the problem of accurate performance analysis of distributed embedded systems in early design stages. The existing formal analysis methods are based on essentially different concepts of abstraction. However, the influence of these different models on the accuracy of the system analysis is widely unknown, as a direct comparison of performance analysis methods has not been considered so far. We define a set of benchmarks aimed at the evaluation of performance analysis techniques for distributed systems. We apply different analysis methods to the benchmarks and compare the results obtained in terms of accuracy and analysis times, highlighting the specific effects of the various abstractions. We also point out several pitfalls for the analysis accuracy of single approaches and investigate the reasons for pessimistic performance predictions.

No abstract available.

We present S-XTC, a topology control algorithm that uses the received signal strength indicator (RSSI) of the radio on wireless sensor nodes. The algorithm is based on XTC, a practical topology control algorithm that constructs a relative neighborhood graph. In contrast to the pure XTC our extensions add to the robustness and resilience against fluctuation in the RSSI values. While guaranteeing connectivity and a bounded node degree, network topologies are able to adapt to gradual changes in the network and it's environment. In this paper, we discuss the shortcomings of the previous algorithm and evaluate S-XTC by analytical proofs and simulation results. Furthermore, we have successfully implemented and tested S-XTC on the BTnode platform of which we discuss a case study and performance evaluation

We present a performance analysis technique for distributed real-time systems in a setting where certain components are modeled in a purely functional manner, while the remaining components require additional modeling of state information. The functional models can be efficiently analyzed but have restricted expressiveness. On the other hand, state-based models are more expressive and offer a richer set of analyzable properties but are computationally more expensive to analyze. We show that by appropriately composing these two classes of models it is possible to leverage on their respective advantages. To this end, we propose an interface between components that are modeled using real-time calculus [Chakraborty, Kiinzli and Thiele, DATE 2003] and those that are modeled using event count automata [Chakraborty, Phan and Thiagarajan, RTSS 2005]. The resulting modeling technique is as expressive as event count automata, but is amenable to more efficient analysis. We illustrate these advantages using a number of examples and a detailed case study.

Today's wireless sensor networks (WSN) focus on energy-efficiency as the main metric to optimize. However, an increasing number of scenarios where sensor networks are considered for time-critical purposes in application sce- narios like intrusion detection, industrial monitoring, or health care systems demands for an explicit support of per- formance guarantees in WSNs and, thus, in turn for a re- spective mathematical framework. In [1], a sensor network calculus was introduced in order to accommodate a worst- case analysis of WSNs. This sensor network calculus fo- cused on the communication aspect in WSNs, but had not yet a possibility to treat in-network processing in WSNs. In this work, we now incorporate in-network processing fea- tures as they are typical for WSNs by taking into account computational resources on the sensor nodes. Furthermore, we propose a simple, yet effective priority queue manage- ment discipline which achieves a good balance of response times across sensor nodes in the field.

We present an analytic method to determine the provably smallest possible slot length that must be allocated in a TDMA resource, to serve an event-triggered hard real-time load with arbitrary deterministic timing behavior. Based on this method, we then present constructive methods to find all feasible as well as the optimal cycle length in a TDMA resource, and we show how to determine the minimum required bandwidth of a TDMA resource. We demonstrate the applicability and computational efficiency of the presented methods in a case study of a large distributed embedded system with a TDMA bus, where we find the optimal parameter set for the TDMA bus

Recent research on performance analysis for embedded systems shows a trend to formal compositional models and methods. These compositional methods can be used to determine the performance of embedded systems by composing formal analytical models of the individual components. In case there exist no formal component models with the required precision, simulation-based approaches are used for system-level performance analysis. The often high runtimes of simulation runs lead to the new approach described in this paper: Analytical methods are combined with simulation-based approaches to speed up simulation. We describe how the simulation models can be coupled with the formal analysis framework, specify the interfaces needed for such a combination and show the applicability of the approach using a case study

Traffic shaping is a well-known technique in the area of networking and is proven to reduce global buffer requirements and end-to-end delays in networked systems. Due to these properties, shapers also play an increasingly important role in the design of multi-processor embedded systems that exhibit a considerable amount of on-chip traffic. Despite their growing importance in this area, no methods exist to analyze shapers in distributed embedded systems, and to incorporate them into a system-level performance analysis. Hence it is until now not possible to determine the effect of shapers to end-to-end delay guarantees or buffer requirements in these systems. In this work, we present a method to analyze greedy shapers, and we embed this analysis method into a well-established modular performance analysis framework. The presented approach enables system-level performance analysis of complete systems with greedy shapers, and we prove its applicability by analyzing two case study systems

This paper investigates real-time scheduling in a system whose energy reservoir is replenished by an environmental power source. The execution of tasks is deemed primarily energy-driven, i.e., a task may only respect its deadline if its energy demand can be satisfied early enough. Hence, a useful scheduling policy should account for properties of the energy source, capacity of the energy storage as well as power dissipation of the single tasks. We show that conventional scheduling algorithms (like e.g. EDF) are not suitable for this scenario. Based on this motivation, we state and prove optimal scheduling algorithms that jointly handle constraints from both energy and time domain. Furthermore, an offline schedulability test for a set of periodic or even bursty tasks is presented. Finally, we validate the proposed theory by means of simulation and compare our algorithms with the classical earliest deadline first algorithm

Recently, a number of frameworks were proposed to extend interface theory to the domains of single-processor and distributed real-time systems. This paper unifies some of these approaches and proves properties like refinement and independent implementability. We also explicitly state the requirements to a framework for these properties to be fulfilled. Further, a new notion of adaptive interfaces is introduced that supports the design by providing mechanisms for propagating system constraints, such as (end-to-end) delays, available computing and communication resources, buffer spaces, and energy. Guarantees and assumptions on interfaces are not any longer static but adapt according to the system environment. This can be used to answer synthesis questions at design time or to adapt system parameters to changing environment requirements at run-time. The applicability of the presented framework is proven by adapting it to a number of different real-time analysis models.

This paper presents a novel method for optimal temporal partitioning of sequential circuits for time-multiplexed reconfigurable architectures. The method bases on slowdown and retiming and maximizes the circuit's performance during execution while restricting the size of the partitions to respect the resource constraints of the reconfigurable architecture. A mixed integer linear program (MILP) formulation of the problem was provided, which can be solved exactly. In contrast to related work, our approach optimizes performance directly, takes structural modifications of the circuit into account, and is extensible. The application of the new method to temporal partitioning for a coarse-grained reconfigurable architecture was presented

Interface-based design is now considered to be one of the keys to tackling the increasing complexity of modern embedded systems. The central idea is that different components comprising such systems can be developed independently and a system designer can connect them together only if their interfaces match, without knowing the details of their internals. We use the concept of rate interfaces for compositional (correct-by-construction) design of embedded systems whose components communicate through data streams. Using the associated rate interface algebra, two components can be connected together if the output rate of one component is "compatible" with the input rate of the other component. We formalize this notion of compatibility and show that such an algebra is non-trivial because it has to accurately model the burstiness in the arrival rates of such data streams and the variability in their processing requirements. We discuss how rate interfaces simplify compositional design and at the same time help in functional and performance verification which would be difficult to address otherwise. Finally, we illustrate these advantages through a realistic case study involving a component-based design of a multiprocessor architecture running a picture-in-picture application

MOTIVATION: In recent years, there have been various efforts to overcome the limitations of standard clustering approaches for the analysis of gene expression data by grouping genes and samples simultaneously. The underlying concept, which is often referred to as biclustering, allows to identify sets of genes sharing compatible expression patterns across subsets of samples, and its usefulness has been demonstrated for different organisms and datasets. Several biclustering methods have been proposed in the literature; however, it is not clear how the different techniques compare with each other with respect to the biological relevance of the clusters as well as with other characteristics such as robustness and sensitivity to noise. Accordingly, no guidelines concerning the choice of the biclustering method are currently available. RESULTS: First, this paper provides a methodology for comparing and validating biclustering methods that includes a simple binary reference model. Although this model captures the essential features of most biclustering approaches, it is still simple enough to exactly determine all optimal groupings; to this end, we propose a fast divide-and-conquer algorithm (Bimax). Second, we evaluate the performance of five salient biclustering algorithms together with the reference model and a hierarchical clustering method on various synthetic and real datasets for Saccharomyces cerevisiae and Arabidopsis thaliana. The comparison reveals that (1) biclustering in general has advantages over a conventional hierarchical clustering approach, (2) there are considerable performance differences between the tested methods and (3) already the simple reference model delivers relevant patterns within all considered settings.

System level performance analysis techniques play an important role in the design process of complex embedded systems. They allow to analyze essential characteristics of a system design in an early design stage and support therewith the choice of important design decisions. While analytical methods for system level performance analysis lead to hard bounded analysis results, the obtained results are often overly pessimistic due to a lack of details such analytical methods can incorporate in their system analysis. To overcome this problem, we present new abstract models for event streams and system components of embedded systems, and show how these models can be combined to modules for modular performance analysis. With the presented models, we can capture complex functional properties of systems, as for example caches, variable resource demand of events in an event stream, or arbitrary up- and down-sampling of event streams in a system component. The applicability of our models and their advantages over traditional models for performance analysis are shown in a case study of a system component with LRU (Least Recently Used) cache.

In this paper, we introduce a new task model that is specifically targeted towards representing stream processing applications. Examples of such applications are those involved in network packet processing (such as a software-based router) and multimedia processing (such as an MPEG decoder application). Our task model is made up of two parts: (i) a new task structure to accurately model the software structures of stream processing applications such as conditional branches and different end-to-end deadlines for different types of input data items, and (ii) a new event model to represent the arrival pattern of the data items to be processed, which triggers the task structure. This event model is more expressive than classical models such as purely periodic, periodic with jitter or sporadic event models. We then present algorithms for the schedulability analysis of this task model. The basic scheme underlying our algorithms is a generalization of the techniques used for the schedulability analysis of the recently proposed generalized multiframe and the recurring real-time task models.

The central idea behind interface-based design is to describe components by a component interface. In contrast to a component description that describes what a component does, a component interface describes how a component can be used. A well designed component interface provides enough information to decide whether two or more components can work together properly in a system. In this work, we expand the idea of interface-based design to the area of real-time system design. Here, the term of 'working together properly' refers to questions like: Does the composed system satisfy all requested real-time properties such as delay and throughput constraints? For this, we introduce Real-Time Interfaces, that connect the principles of Real-Time Calculus with Interface-based Design. In contrast to traditional real-time system design, in interface-based real-time system design the compliance to real-time constraints is checked at composition time. This leads to faster design processes and partly removes the need for the classical binary search approach to find an economically dimensioned system. Further, interface-based real-time system design also benefits from the properties of incremental design and independent implementability.

Deployment-support networks (DSNs) have been proposed as a novel tool for the development, test, deployment, and validation of wireless sensor networks. They are expected to enhance scalability and flexibility in deployment by eliminating cable connections. In this paper, we describe our implementation of a DSN, giving details on the algorithms for topology control and maintenance. We provide various measurements of DSNs spanning up to 71 BTnode rev3 devices, featuring the largest Bluetooth scatternet reported to date. We also discuss our experience gained in the development and experimentation. Our results strongly suggest that our implementation scales well to a large number of nodes.

Clock synchronization is a crucial basic service in ad-hoc sensor networks. Most proposed algorithms employ hierarchical communication structures that may be expensive to maintain when nodes are mobile and network topologies are dynamic. Interval-based synchronization has been proposed as particularly suited for sensor networks, as it does not require any particular communication pattern. In this paper, we show that node mobility puts no burden on interval-based synchronization, but actually helps it. This is not the case for time-estimate-based approaches that rely on specific communication patterns. Mobility resilience therefore further strengthens the case of interval-based clock synchronization for ad-hoc sensor networks

Modern embedded systems are typically integrated as multiprocessor system on chips, and are often characterized by the complex behaviors and dependencies that system components exhibit. Different events that trigger such systems normally cause different execution demands, depending on their event type as well as on the task they are processed by, leading to complex workload correlations. For example in data processing systems, the size of an events payload data will typically determine its execution demand on most or all system components, leading to highly correlated workloads. Performance analysis of such complex system is often very difficult, and conventional analysis methods have no means to capture the possible existence of workload correlations. This leads to overly pessimistic analysis results, and thus to too expensive system designs with considerable performance reserves. We propose an abstract model to characterize and capture workload correlations present in a system architecture, and we show how the captured additional system information can be incorporated into an existing framework for modular performance analysis of embedded systems. We also present a method to analytically obtain the proposed abstract workload correlation model from a typical system specification. The applicability of our approach and its advantages over conventional performance analysis methods is shown in a detailed case study of a multiprocessor system on chip, where the analysis results obtained with our approach are considerably improved compared to the results obtained with conventional analysis methods.

We present an interface theory based approach to static analysis of actor models. We first introduce a new interface theory, which is based on interface automata, and which is capable of counting with numbers. Using this new interface theory, we can capture temporal and quantitative aspects of an actor interface as well as an actor's token exchange rate. We will show, how to extract this information from actors written in the cal actor language (CAL), and we also present a method to capture the interface information as well as the structure of dataflow models into an interface automaton. This automaton acts as glue between the automata of all actors in the model, and by successfully composing all actor automata with it, we can prove interface compatibility of all actors with the composition framework. After successful composition, the resulting automaton will contain information that can be used for further static analysis of the composite actor model.

The analysis of real-time properties of an embedded system usually relies on the worst-case execution times (WCET) of the tasks to be executed. In contrast to that, in real world applications the running time of tasks may vary from execution to execution, e.g. in multimedia applications. The traditional worst-case analysis of the system then returns overly pessimistic estimates of the system performance. In this paper we propose a new effective method to characterize tasks with variable execution requirements, which leads to tighter worst-case bounds on system performance and better use of available resources. We show the applicability of our approach by a detailed study of a multimedia application.

In this paper, we present a novel use of an FPGA as a computing element for streaming based application. We investigate the virtualized execution of dynamic reconfigurable tasks. We use the process networks model as a coordination language which is interpreted on a virtual machine run-time system. We present and discuss the results of a design space exploration, which evaluates the performance of the system architecture for different configurations.

Interval-based synchronization provides the nodes of a distributed system with guaranteed bounds on a common time. This is a crucial piece of infrastructure in many distributed sensing and actuating systems. In this paper, we propose a modification to a known interval-based synchronization algorithm; our new algorithm obtains substantially better results in sensor-network scenarios by taking advantage of the typical drift diversity of the nodes' clocks. We propose a model for synchronization in ad-hoc, sporadic-communication scenarios. The model allows us to identify the worst and the best case in terms of achievable time uncertainty and to show the worst-case optimality of the discussed algorithms. Simulations show that in the average case, our modification significantly reduces the time uncertainty.

Clock synchronization is a crucial basic service in typical sensor networks, since the observations of distributed sensors more often than not need to be ordered ("a happened before b") or otherwise related ("a and b happened within a time window of size x") in time. Ad-hoc networks may exhibit characteristics which make the use of traditional clock-synchronization algorithms infeasible. Recently, algorithms suitable for ad-hoc networks have been presented.We first propose an improvement to an existing algorithm. While needing less computation and no more communication or memory than the original algorithm, our new algorithm always yields equal or better results and thus outperforms the original algorithm. We then examine how even better synchronization can be obtained, possibly at the cost of additional computation, communication, and memory. To this end, we introduce a model for internal synchronization. This model allows us to find an algorithm which makes use of all the data a node can obtain from the network for a given communication pattern and thus provides optimal synchronization in our model.

Many real-time embedded systems process event streams which are composed of a finite number of different event types. Each different event type on the stream would typically impose a different workload to the system, and thus the knowledge of possible correlations and dependencies between the different event types could be exploited to get tighter analytic performance estimations of the complete system. We propose an abstract stream model to characterize such an event stream. The model captures the needed information of all possible traces of a class of event streams and can hence be used to obtain hard bounded worst-case and best-case estimations of a system. We show how the proposed abstract stream model can be obtained from a concrete stream specification, and how it can be used for performance analysis. The applicability of our approach and its advantages over traditional worst-case performance analysis are shown in a case study of a multimedia application.

Wearable computing has recently gained much popularity as an ambitious vision for future personalized mobile systems. Its aim is intelligent, environment aware systems unobtrusively embedded into the mobile environments of their users. With the combination of complex processing requirements, the necessity of placing sensors and input/output modules at different locations on the user's body, and stringent limits on size, weight, and battery capacity, the design of such systems is an inherently challenging problem. We demonstrate how systematic design and quantitative analysis can be applied to wearable architectures. We first present a model that allows various factors influencing the design of a wearable system to be incorporated into formal cost metrics. In particular, we show how to consistently incorporate specific wearable factors such as device placement requirements, ergonomics, and dynamic workload profiles into the model. We then discuss how efficient estimation algorithms can be extended and applied to the evaluation of different architectures with respect to our cost metrics. Finally, we discuss quantitative results from a proof-of-concept case study showing the trade offs between different architectures for a given wearable scenario. Summarized, we demonstrate how the description and the design of wearable systems can be put on a systematic, formal basis allowing us to treat them similar as conventional embedded systems.

This paper presents a rigorous running time analysis of evolutionary algorithms on pseudo-Boolean multiobjective optimization problems. We propose and analyze different population-based algorithms, the simple evolutionary multiobjective optimizer (SEMO), and two improved versions, fair evolutionary multiobjective optimizer (FEMO) and greedy evolutionary multiobjective optimizer (GEMO). The analysis is carried out on two biobjective model problems, leading ones trailing zeroes (LOTZ) and count ones count zeroes (COCZ), as well as on the scalable m-objective versions mLOTZ and mCOCZ. Results on the running time of the different population-based algorithms and for an alternative approach, a multistart (1+1)-EA based on the /spl epsi/-constraint method, are derived. The comparison reveals that for many problems, the simple algorithm SEMO is as efficient as this (1+1)-EA. For some problems, the improved variants FEMO and GEMO are provably better. For the analysis, we propose and apply two general tools, an upper bound technique based on a decision space partition and a randomized graph search algorithm, which facilitate the analysis considerably.

This paper deals with online scheduling of tasks to partially reconfigurable devices. Such devices are able to execute several tasks in parallel. All tasks share the reconfigurable surface as a single resource which leads to highly dynamic allocation situations. To manage such devices at runtime, we propose a reconfigurable operating system that splits into three main modules: scheduler, placer, and loader. The main characteristic of the resulting online scheduling problem is the strong nexus between scheduling and placement. We discuss a fast online placement technique and then focus on scheduling real-time tasks. We devise guarantee-based schedulers for two scenarios, namely tasks with arbitrary and synchronous arrival times. The schedulers exploit the knowledge about task properties to improve the system's performance. The experiments show that the developed schedulers lead to substantial performance gains at an acceptable runtime overhead.

An important issue in multiobjective optimization is the quantitative comparison of the performance of different algorithms. In the case of multiobjective evolutionary algorithms, the outcome is usually an approximation of the Pareto-optimal set, which is denoted as an approximation set, and therefore the question arises of how to evaluate the quality of approximation sets. Most popular are methods that assign each approximation set a vector of real numbers that reflect different aspects of the quality. Sometimes, pairs of approximation sets are also considered. In this study, we provide a rigorous analysis of the limitations underlying this type of quality assessment. To this end, a mathematical framework is developed which allows one to classify and discuss existing techniques.

After adequately demonstrating the ability to solve different two-objective optimization problems, multi-objective evolutionary algorithms (MOEAs) must show their efficacy in handling problems having more than two objectives. In this paper, we suggest three different approaches for systematically designing test problems for this purpose. The simplicity of construction, scalability to any number of decision variables and objectives, knowledge of exact shape and location of the resulting Pareto-optimal front, and ability to control difficulties in both converging to the true Pareto-optimal front and maintaining a widely distributed set of solutions are the main features of the suggested test problems. Because of these features, they should be useful in various research activities on MOEAs, such as testing the performance of a new MOEA, comparing different MOEAs, and having a better understanding of the working principles of MOEAs.

Many real-time embedded systems involve a collection of independently executing event-driven code blocks, having hard real-time constraints. Tasks in many such systems, like network processors, are either not preemptable or have restrictions on the number of preemptions allowed. All the previous work on the schedulability analysis of such systems either have exponential complexity, or allow unbounded number of preemptions and are usually based on heuristics. In this paper we present the exact necessary and sufficient conditions under EDF, for the schedulability of such a collection of code blocks in a non-preemptive environment, and give efficient algorithms for testing them. We validate our analytical results with experiments and show that the schedulability analysis problem in such systems can be exactly and efficiently solved in practice.

We present an analytical method to evaluate embedded network packet processor architectures, and to explore their design space. Our approach is in contrast to those based on simulation, which tend to be infeasible when the design space is very large. We illustrate the feasibility of our method using a detailed case study.

The schedulability analysis problem for many realistic task models is intractable. Therefore, known algorithms either have exponential complexity or at best can be solved in pseudo-polynomial time, thereby restricting application of the concerned models to a large extent. We introduce the notion of "approximate schedulability analysis" and show that if a small amount of "error" (which is specified as an input to the algorithm) can be tolerated in decisions made by the algorithm, then this problem can be solved in polynomial time. Our algorithms are analogous to fully polynomial time approximation schemes in the context of optimization problems. We show that this concept of approximate schedulability analysis is fairly general and can be applied to any task model which satisfies certain "task-independence" assumptions. Lastly, we substantiate our theoretical results with experimental evidence and clearly show tradeoffs between running time of the schedulability analysis and the error incurred for various values of the input error parameter.

Over the past few years, the research on evolutionary algorithms has demonstrated their niche in solving multiobjective optimization problems, where the goal is to find a number of Pareto-optimal solutions in a single simulation run. Many studies have depicted different ways evolutionary algorithms can progress towards the Pareto-optimal set with a widely spread distribution of solutions. However, none of the multiobjective evolutionary algorithms (MOEAs) has a proof of convergence to the true Pareto-optimal solutions with a wide diversity among the solutions. In this paper, we discuss why a number of earlier MOEAs do not have such properties. Based on the concept of epsilon-dominance, new archiving strategies are proposed that overcome this fundamental problem and provably lead to MOEAs that have both the desired convergence and distribution properties. A number of modifications to the baseline algorithm are also suggested. The concept of epsilon-dominance introduced in this paper is practical and should make the proposed algorithms useful to researchers and practitioners alike.

Embedded systems typically include reactive and transformative functions, often described in different languages and semantics which are well established in their respective application domains. Additionally, a large part of the system functionality and components is reused from previous designs including legacy code. There is little hope that a single language will replace this heterogeneous set of languages. A design process must be able to bridge the semantic differences for verification and synthesis and should account for limited knowledge of system properties. This paper presents the system property intervals (SPI) model, which employs behavioral intervals and process modes to allow the common representation of different languages and semantics. This model is the basis of a workbench which is targeted at the design of heterogeneously specified embedded systems.

This study investigates the use of multiobjective techniques in genetic programming (GP) in order to evolve compact programs and to reduce the effects caused by bloating. The proposed approach considers the program size as a second, independent objective besides the program functionality. In combination with a multiobjective evolutionary technique, SPEA2, this method outperforms four other strategies to reduce bloat with regard to both convergence speed and size of the produced programs on an even-parity problem.

Modern embedded computing systems tend to be heterogeneous assemblages of concurrent subsystems, typically described in different languages and semantics which are well established in the various application fields. For example, the specification of the functional and timing behavior necessitates a mixture of different basic models of computation and communication which come from transformatlive or reactive domains. There is little hope that a single language will replace this heterogeneous set of languages. In fact, experiments with system specification languages show that there is not a unique universal specification language to support the whole life cycle. A similar problem occurs when reused components shall be integrated, possibly described in another language and incompletely documented. Examples would be components of other companies or "legacy code". The lack of coherency of the different languages, methods and toots is a substantial obstacle on the way to higher design productivity and design quality. A design process must be able to bridge the semantic differences for verification and synthesis and should account for limited knowledge of system properties. This paper describes approaches which allow for the common representation of different languages and incomplete specifications. In particular, recent results on the use of internal design representations targeted to scheduling and design space exploration are reviewed. The information useful for methods like allocation of resources, partitioning the design and scheduling must be estimated or extracted from the various input languages and mapped onto internal representations which describe properties of the subsystems and their coordination. Design methods work on these internal representations and eventually refine them by adding components and reducing non-determinism.

In this paper, an internal design model called FunState (functions driven by state machines) is presented that enables the representation of different types of system components and scheduling mechanisms using a mixture of functional programming and state machines. It is shown how properties relevant for scheduling and verification of specification models such as Boolean dataflow, cyclostatic dataflow, synchronous dataflow, marked graphs, and communicating state machines as well as Petri nets can be represented in the FunState model of computation. Examples of methods suited for FunState are described, such as scheduling and verification. They are based on the representation of the model's state transitions in the form of a periodic graph. The feasibility of the novel approach is shown with an asynchronous transfer mode switch example.

Though it has been claimed that elitism could improve evolutionary multi-objective search significantly, a thorough and extensive evaluation of its effects is still missing. Guidelines on how elitism could successfully be incorporated have not yet been developed. This paper presents a unified model of multi-objective evolutionary algorithms, in which arbitrary variation and selection operators can be combined as building blocks, including archiving and re-insertion strategies. The presented model enables most specific multi-objective (evolutionary) algorithm to be formulated as an instance of it, which will be demonstrated by simple examples. We further show how elitism can be quantified by the model's parameters and how this allows an easy evaluation of the effect of elitism on different algorithms.

This paper establishes a link between three areas, namely Max-Plus Linear System Theory as used for dealing with certain classes of discrete event systems, Network Calculus for establishing time bounds in communication networks, and real-time scheduling. In particular, it is shown that important results from scheduling theory can be easily derived and unified using Max-Plus Algebra. Based on the proposed network theory for real-time systems, the first polynomial algorithm for the feasibility analysis and optimal priority assignment for a general task model is derived.

In this paper, we provide a systematic comparison of various evolutionary approaches to multiobjective optimization using six carefully chosen test functions. Each test function involves a particular feature that is known to cause difficulty in the evolutionary optimization process, mainly in converging to the Pareto-optimal front (e.g., multimodality and deception). By investigating these different problem features separately, it is possible to predict the kind of problems to which a certain technique is or is not well suited. However, in contrast to what was suspected beforehand, the experimental results indicate a hierarchy of the algorithms under consideration. Furthermore, the emerging effects are evidence that the suggested test functions provide sufficient complexity to compare multiobjective optimizers. Finally, elitism is shown to be an important factor for improving evolutionary multiobjective search.

In this paper, a representation of multivalued functions called interval decision diagrams (IDDs) is introduced. It is related to similar representations such as binary decision diagrams. Compared to other functional representations with regard to symbolic formal verification approaches, IDDs show some important properties that enable us to verify process networks and related models of computation more adequately than with conventional approaches. Therefore, a new form of transition relation representation called interval mapping diagram (IMD) is introduced. A novel approach to symbolic model checking of process networks is presented. Several drawbacks of traditional strategies are avoided using IDDs and IMDs. The resulting transition relation IMD is very compact, enabling fast image computations. Furthermore, no artificial limitations concerning buffer capacities or equivalent have to be introduced. Additionally, applications concerning scheduling of process networks are feasible. IDDs and IMDs are defined, their properties are described, and computation methods and techniques are given.

Many embedded systems are implemented with a set of alternative function variants to adapt the system to different applications or environments. This paper proposes a novel approach for the coherent representation and selection of function variants in the different phases of the design process. In this context, the modeling of reconfiguration of system parts is supported in a natural way. Using a real example from the video processing domain, the approach is explained and validated. 1 Introduction Many embedded systems are implemented with a fixed core function and a set of alternative function variants to adapt the system to different applications or environments. Examples are TV sets which can be adapted to different standards or automotive control systems to be used in countries with different emission laws. Function variants are mutually exclusive, i. e. only one variant of a set of alternative functions is selected a time. There may be several of those variant sets in one embedde...

Symbolic model checking tries to reduce the state explosion problem by implicit construction of the state space. The major limiting factor is the size of the symbolic representation mostly stored in huge binary decision diagrams. A new approach to symbolic model checking of Petri nets and related models of computation is presented, outperforming the conventional one and avoiding some of its drawbacks. Our approach is based on a novel, efficient form of representation for multi-valued functions called interval decision diagram (IDD) and the corresponding image computation technique using interval mapping diagrams (IMDs). IDDs and IMDs are introduced, their properties are described, and the feasibility of the new approach is shown with some experimental results.

In this paper, an internal design model called FunState (functions driven by state machines) is presented that enables the representation of different types of system components and scheduling mechanisms using a mixture of functional programming and state machines. It is shown how properties relevant for scheduling and verification of specification models like boolean dataflow, cyclostatic dataflow, synchronous dataflow, marked graphs, and communicating state machines as well as Petri nets may be represented in the FunState model. Examples of methods suited for FunState are described, such as scheduling and verification. They are based on the representation of the model's state transitions in form of a periodic graph.

Evolutionary algorithms (EAs) are often well-suited for optimization problems involving several, often conflicting objectives. Since 1985, various evolutionary approaches to multiobjective optimization have been developed that are capable of searching for multiple solutions concurrently in a single run. However, the few comparative studies of different methods presented up to now remain mostly qualitative and are often restricted to a few approaches. In this paper, four multiobjective EAs are compared quantitatively where an extended 0/1 knapsack problem is taken as a basis. Furthermore, we introduce a new evolutionary approach to multicriteria optimization, the strength Pareto EA (SPEA), that combines several features of previous multiobjective EAs in a unique manner. It is characterized by (a) storing nondominated solutions externally in a second, continuously updated population, (b) evaluating an individual's fitness dependent on the number of external nondominated points that dominate it, (c) preserving population diversity using the Pareto dominance relationship, and (d) incorporating a clustering procedure in order to reduce the nondominated set without destroying its characteristics. The proof-of-principle results obtained on two artificial problems as well as a larger problem, the synthesis of a digital hardware-software multiprocessor system, suggest that SPEA can be very effective in sampling from along the entire Pareto-optimal front and distributing the generated solutions over the tradeoff surface. Moreover, SPEA clearly outperforms the other four multiobjective EAs on the 0/1 knapsack problem.

In this paper.an approach to symbolic model checking of process networks is introduced.It is based on intewal decision dia- grams (IDDs), a representation ofmtdti-valued functions.Compared to other model checking strategies, IDDs show some important properties that enable the verification of process networks more adequately than with conventional approaches.Additionally, applacations conceding scheduling ~villbesho~vn.Anew form of transition relation representation called interval mapping diagrams (IhlDs~and their less general version predicate action diagrams &ADs&is explained together with the corresponding methods.

The specijcation of embedded systems veq often contains a mi.x~ureof diferent models of computation.In particular the data $oti~and control $oiv associated to the transformative and reactii'e domains, respectively, are tightly coupled.The paper considers classes of applications that feature communicating processes ~vhoseflmctions depend on a]nite set of computation modes.The change behveen these modes is synchronized by data communication.An approach is presented to model the correlation of process modes and to fidly utilize this information for schedlding.A modeling ~ample sho}vs the optimization potential of the n~v approach.

Lattice basis reduction is an important problem in geometry of numbers with applications in combinatorial optimization, computer algebra, and cryptography. The well-known sequential LLL algorithm finds a short vector in O(n 4 log B) arithmetic operations on integers having binary length O(n log B), where n denotes the dimension of the lattice and B denotes the maximum L 2 norm of the initial basis vectors. In this paper a new analysis of the parallel algorithm of Roch and Villard is presented. It is shown that on an n x n mesh it needs O(n 2 log B) arithmetic operations on integers having binary length O(n log B). This improves the previous analysis and shows that an asymptotical speedup of n 2 is possible using n 2 processors.

This paper deals with the system-level performance analysis and optimization of a class of digital systems we call mixed asynchronous-synchronous systems. In such a system, each computation module is either synchronous or asynchronous. The communication among all of the modules is assumed to be data driven. In order to adequately describe the timing of such architectures, we introduce a graph model called MASS, which is based on several extensions of timed marked graphs. The first extension is that the node set V is partitioned into synchronous and asynchronous nodes. A synchronous node can only fire at ticks of its local module clock. Based on these extensions, we analyze the behavior of MASS, in particular, period, periodicity, and maximal throughput rate. Finally, we introduce the optimization problem of assigning appropriate clock phases to synchronous nodes so to maximize the throughput rate of the resulting system. An exact solution as well as a polynomial time algorithm for nearly optimal phase assignment are presented.

A single integer linear programming model for optimally scheduling partitioned regular algorithms is presented. The herein presented methodology differs from existing methods in the following capabilities: (1) Not only constraints on the number of available processors and communication capabilities are taken into account, but also processor caches and constraints on the size of available memories are modeled and taken into account in the optimization model. (2) Different types of processors can be handled. (3) The size of the optimization model (number of integer variables) is independent of the size of the tiles to be executed. Hence, (4) the number of integer variables in the optimization model is greatly reduced such that problems of relevant size can be solved in practical execution time.

This paper deals with the cyclo-static (periodic) scheduling of iterative instruction sequences on VLIW-processor architectures, in the case when the period is imposed (periodic real time constraints). This problem naturally arises when designing VLIW-processor architectures as I/O interfaces between cyclo-static-processor arrays and the external world. Three important mapping problems related to periodic real time constraints are discussed, depending on the VLIW-processor resource constraints and optimization criteria that are considered. Precise conditions under which there exist cycle-static schedules are formulated. Whenever possible, we present systematic and optimal mapping methodologies with polynomial solution time. The starting point is thereby a novel description of iterative instruction sequences in the form of generalized directed acyclic graphs (DAG's). Finally, an innovative VLIW-processor architecture, called Extended Periodic Operation Model (EPOM) with distributed shift register file, which optimally fits into the mapping trajectory, is presented.

Evolutionary algorithms are a common probabilistic optimization method based on the model of natural evolution. One important operator in these algorithms is the selection scheme, for which in this paper a new description model, based on fitness distributions, is introduced. With this, a mathematical analysis of tournament selection, truncation selection, ranking selection, and exponential ranking selection is carried out that allows an exact prediction of the fitness values after selection. The correspondence of binary tournament selection and ranking selection in the expected fitness distribution is proved. Furthermore, several properties of selection schemes are derived (selection intensity, selection variance, loss of diversity), and the three selection schemes are compared using these properties.

In this paper, we describe a new processor model called Periodic Operation Model (POM) that is suitable for real time image processing. First we analyze existing image processing systems in order to situate our approach. Starting from the processor architecture, we derive the corresponding algorithm class by means of a novel hardware description. Then we address the allocation and scheduling problem. We show that allocation and scheduling can be decoupled in the mapping process related to POM-processor arrays and outline the principles of an optimal mapping trajectory. We describe the outline of a novel ILP-model for allocation of POM-processor arrays which takes into account array-topology and bus bandwidth constraints. Finally we discuss implementational aspects of the POM as well as applications in image processing. We especially show that POM-processor arrays can be integrated onto single chips, thereby allowing to achieve several GOPS processing power per chip.

The forumnists address the question of high density computations on a single chip. The surface of a chip offers an ideal medium not only to store information or to process data, but also to execute computations. The 1 Giga floating point operations per second per chip mark has been achieved, we are now moving towards the teraflop mark. How is this going to happen, what are the limitations, what are the opportunities-those are central questions.>

A method for optimizing the schedule and allocation of uniform algorithms onto processor arrays is derived. The main results described in the following paper are: (1) single (integer) linear programs are given for the optimal schedule of regular algorithms with and without resource constraints, (2) the class of algorithms is extended by allowing certain nonconvex index domains, (3) effecient branch and bound techniques are used such that problems of relevant size can be solved. Moreover, additional constraints such as cache memory bus bandwidths and access conflicts can be considered also. The results are applied to an example of relevant size.>

The paper describes the systematic design of processor arrays with a given dimension and a given number of processing elements. The unified approach to the solution of this problem called partitioning is based on the following concepts: (1) Algorithms and processor arrays are represented by (piecewise regular) programs. (2) The concept of stepwise refinement of programs is used to solve the partitioning problem by applying a sequence of provably correct program transformations. In contrary to other approaches, nonperfect tilings may be considered. The parameters of the introduced program transformations enable the realization of different partitioning schemes. (3) It is shown that the class of piecewise regular programs is closed under partitioning.>

Article Analysis of free schedule in periodic graphs Share on Authors: Wolfgang Backes View Profile , Uwe Schwiegelshohn View Profile , Lothar Thiele View Profile Authors Info & Claims SPAA '92: Proceedings of the fourth annual ACM symposium on Parallel algorithms and architecturesJune 1992 Pages 333–342https://doi.org/10.1145/140901.141910Online:01 June 1992Publication History 9citation242DownloadsMetricsTotal Citations9Total Downloads242Last 12 Months4Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The authors consider a formal and systematic method to convert a class of nested loop programs to single assignment codes and, when possible, to regular algorithms (RAs) for systolic array implementation. The authors concentrate on the analysis of certain imperative nested loop programs in view of the ultimate objective, which is the (semi)-automatic design of systolic arrays from such initial behavioral specifications. The nested loop programs can be represented by a graph displaying the variable dependences between iterations. Characteristic properties of this dependence graph are given. In terms of this dependence graph, a procedure is described to transform the program into a single assignment program in which each variable takes on a unique value during the execution of the program. The method provides a systematic way to analyze data dependences in imperative nested loop programs. The approach is complementary to those used in parallelizing/vectorizing compilers. Instead of searching for independent iterations or statements (i.e. parallelism), iterations that are strictly dependent on each other are detected.>

The author examines systematic methods for analyzing and designing self-timed regular arrays of processors. Methods are given to derive measures of efficiency and to verify the computational behavior of a given self-timed regular array. It is shown that the optimization of a given regular self-timed processor array with respect to its processor utilization can be given mathematically in the form of linear programming or integer linear programming problems whose sizes are independent of the size of the array.>

A pure systolic realization of an algorithm for solving the n*n assignment problem is presented. This systolic algorithm can be implemented on an homogeneous hexagonal processor array and requires O(n/sup 2/) area complexity and O(n/sup 2/) time complexity.>

This paper presents an algorithm which is essentially equivalent to Jacobi-type algorithms with a cyclic-by-rows iteration scheme but also enables a fast parallel and systolic computation. Further, a comparison with other parallel algorithms for the same problem is provided. At last a systolic array is derived which requires (n+1)2/4 processor cells and has a time complexity of O(n) for each sweep.

In this paper homogeneous systolic solutions to overdetermined systems of linear equations are described. The least-squares problem (LSP) can be solved on two-dimensional mesh-connected or hexagonal arrays. Simple partitioning schemes can be applied to solve large-scale problems. A general systematic method is given to derive linear processor arrays from given two-dimensional ones. This hierarchical approach leads to one-dimensional systolic arrays for the LSP with advantageous properties. The data occur in a lexicographical input/ output scheme and pipelined arithmetic units can be used.