Many real-world applications deal with the problem of scheduling repetitive tasks in a periodic fashion. Often, such tasks involve precedence constraints and require sharing a limited set of, possibly heterogeneous, resources to enable their execution. This results in a problem that combines resource allocation and periodic task scheduling, which we refer to as the Allocation and Periodic Scheduling Problem (APSP). This paper proposes two linear-programming models for solving the APSP based on a novel modeling approach. The first model is a monolithic Mixed-Integer Linear Programming (MILP) model and the second one is a MILP model with a Benders decomposition. Both models allow finding an optimal resource allocation and periodic schedule that minimizes the period, i.e., they optimize throughput. In contrast to earlier work on optimally solving the APSP, our approach uses a time bound on considered start times of task executions, meaning that only the repetitions starting within the time bound are considered in the solving process. This effectively constrains the search space for finding optimal schedules. For feasible problem instances, we prove that there exists an optimal schedule in which all tasks execute at least once within this time bound, showing the soundness of the approach. Where earlier models for the APSP are in essence non-linear, our approach results in easier-to-solve linear models. Experiments show that, in comparison to the state of the art, our models are less prone to numerical instabilities and find optimal solutions more often, while being competitive in solve time.

Modern vehicles increasingly rely on distributed computing platforms that exchange large volumes of sensor and control data with strict timing requirements. Ensuring that this traffic meets its deadlines over Ethernet-based in-vehicle networks requires Time-Sensitive Networking (TSN) and, in particular, effective configuration of the Time-Aware Shaper (TAS). However, generating and updating TAS schedules that remain valid as traffic patterns evolve is an NP-hard problem that traditional optimization or heuristic methods address only partially. This paper introduces a Deep Reinforcement Learning (DRL) scheduler that learns to configure TAS schedules directly from network state while preserving standard compliance through analytical validation. The proposed DRL scheduler encodes the scenario (network topology and workload) of the in-vehicle network using a Graph Neural Network (GNN) and learns scheduling policies that balance deadline satisfaction, latency, and resource utilization. Evaluation on a comprehensive benchmark shows that the proposed approach consistently outperforms state-of-the-art heuristics and a topology-specific DRL baseline, achieving higher success rate and lower delay while maintaining efficient bandwidth use. Once trained, it can adapt to new traffic scenarios within milliseconds, demonstrating the potential of the DRL-based scheduler as a foundation for adaptive and reliable communication in next-generation software-defined vehicles.

Containerisation is becoming a cornerstone of modern distributed systems, thanks to their lightweight virtualisation, high portability, and seamless integration with orchestration tools such as Kubernetes. The usage of containers has also gained traction in real-time cyber-physical systems, such as software-defined vehicles, which are characterised by strict timing requirements to ensure safety and performance. Nevertheless, ensuring real-time execution of co-located containers is challenging because of mutual interference due to the sharing of the same processing hardware. Existing parallel computing frameworks such as Ray and its Kubernetes-enabled variant, KubeRay, excel in distributed computation but lack support for scheduling policies that allow guaranteeing real-time timing constraints and CPU resource isolation between containers, such as the SCHED_DEADLINE policy of Linux. To fill this gap, this paper extends Ray to support real-time containers that leverage SCHED_DEADLINE. To this end, we propose KubeDeadline, a novel, modular Kubernetes extension to support SCHED_DEADLINE. We evaluate our approach through extensive experiments, using synthetic workloads and a case study based on the MobileNet and EfficientNet deep neural networks. Our evaluation shows that KubeDeadline ensures deadline compliance in all synthetic workloads, adds minimal deployment overhead (in the order of milliseconds), and achieves lower worst-case response times, up to 4 times lower, than vanilla Kubernetes under background interference.

As vehicles develop into software-defined platforms with powerful automated driving capabilities and driver support systems, their in-vehicle networks become significantly more complicated. A key technique for ensuring deterministic, low-latency connectivity for crucial data traffic in such settings is Time-Sensitive Networking (TSN), and specifically the Time-Aware Shaper (TAS). However, current TAS scheduling techniques have difficulty adjusting schedules to dynamically shifting traffic patterns and changing operating conditions. This paper presents an adaptive scheduler using Deep Reinforcement Learning (DRL), which aims to meet strict deadlines, reducing latency and providing near-ideal resource usage. Experimental results for different vehicle scenarios show that our DRL-based scheduler performs better in terms of success rate, low latency, and overall network performance than state-of-the-art heuristic algorithms such as earliest deadline first (EDF) scheduling.

In-vehicle networks (IVNs) are rapidly evolving to support increasingly complex automotive applications, demanding higher bandwidth and deterministic timing bounds. Time-Sensitive Networking (TSN) has emerged as a promising Ethernet-based technology that addresses these stringent requirements. However, evaluating TSN-based IVN strategies remains a challenge due to the lack of standardized benchmarks and simulation tools. This paper introduces INSIM, a modular simulation platform specifically designed for TSN-based IVNs, providing an intuitive graphical interface, an extensible plug-in architecture, and integrated benchmarking features. INSIM integrates analytical performance models and discrete-event simulations (as plug-ins), enhancing the workflow for engineers by refining topology design, adjusting parameters, conducting simulations, and assessing performance, while providing researchers with a flexible platform to plug in, analyze, and compare custom network resource managers or analytical performance models.

Homogeneous Synchronous DataFlow Graphs (HSDFGs) have become a popular method for analysing the performance of manufacturing systems. Manufacturing tasks, modelled by actor firings in an HSDFG, are bounded by their earliest possible starting times, determined by the completion of preceding tasks. Taking into account these lower bounds, an HSDFG represents different possible task schedules for these tasks, namely any actor firing scheme that satisfies these lower bounds. However, in some cases, tasks in a manufacturing system must be completed before a deadline, which introduces an upper bound. Additionally, the relative start times between tasks may need to adhere to a lower bound. Such lower and upper bounds are not naturally supported by classical HSDFGs. In such cases, an HSDFG cannot represent all relevant aspects of the behaviour of a manufacturing system. This article extends the HSDFG model to support the specification of lower-bound and upper-bound constraints on timing differences between actor-firing starts and completions. The paper then presents a new method for transforming extended HSDFGs into a (max, +) linear system in the form of its state-space matrices. This system can be used to synthesize a task schedule that adheres to the specified lower and upper bounds while achieving the earliest possible execution times, optimizing throughput or makespan. We illustrate the necessity for specifying lower and upper bounds, and the application of our techniques, with a manufacturing system case study.

Centralised servers provide on-demand resources to process offloaded workloads from computing nodes. While server-based computing has been successful for applications with soft timing constraints, it falls short for safety-critical real-time systems with hard timing requirements. To bridge this gap, we develop a job-level admission test to satisfy the requirements for real-time applications deployed on a server by extending the “(M, K)-firm weakly hard” model to server systems, ensuring timely processing of server requests. We introduce an admission policy to regulate the workload and prevent deadline misses while attempting to admit more requests than the minimum required by the initial (M, K) constraints. The admission policy is designed to allow an optimal resource allocation to applications deployed on the server.11This work is an extension of our work-in-progress paper at RTAS'24 [1].

Ensuring deadlines of hard real-time applications in server-based deployments is a challenging problem, particularly if the workload arrives following an arbitrary arrival curve. This work extends the “(M, /K)-firm weakly hard” model to server-based systems, ensuring timely processing of real-time requests to the server. We introduce an admission policy to regulate the remote server workload and prevent deadline misses while attempting to admit more requests than the minimum required, when possible. We guarantee the weakly hard constraints through optimal resource allocation and server confiauration.

Abstract An execution trace is a model of a single system behavior. Execution traces occur everywhere in the system’s lifecycle as they can typically be produced by executable models, by prototypes of (sub)systems, and by the system itself during its operation. An execution trace can be visualized and analyzed with various techniques, providing insight into the dynamic behavior, performance, bottlenecks, etc., of the system. In this paper, we present the Trace tool of the Eclipse Trace4cps project for the visualization and analysis of execution traces. A prominent application is the trace-based performance engineering of embedded or cyber-physical systems. Performance is an important system quality, as it can give a competitive advantage. Reasoning about system-level performance in such systems, however, is hard due to its cross-cutting nature. We show how the Trace tool can support this by various examples. Performance engineering is not the only application of the Trace tool, however: it supports system analysis in a wide range of situations.

Product family development facilitates reuse across all phases of systems engineering; in case of model-based systems engineering, this reuse involves the models as well. Introducing a model-based way of working is challenging, especially for product family development. This paper describes a case of introducing a modelbased way of working in brown-field product family development. We explain how we developed a master model, i.e. a library of model elements, to predict and optimize the productivity of a family of industrial production systems. Using this master model, we construct models of existing and yet-to-be-developed product family members by configuring and combining the appropriate library elements. We use system and model execution traces to validate the productivity models. For this, we developed a master transformation, i.e. a library of execution trace transformation rules, to unify system and model execution traces. Besides the master model and the master transformation, we present lessons learned regarding the introducing a model-based way of working. This proves both technically and organizationally complex, especially for brown-field product family development, but besides the intended prediction and optimization, it brings benefits with respect to capturing domain knowledge and system validation.

Streaming systems are naturally modeled with synchronous dataflow graphs (SDFGs). The max-plus semantics of an SDFG is a compact matrix representation of its timing behavior. The max-plus semantics enables us to analyze and control timing properties of the systems, such as the obtainable minimum guaranteed throughput and maximum latency. Deriving the max-plus semantics, and consequently, performance analysis may be computationally expensive since the state-of-the-art method simulates one iteration of an SDFG. This holds, in particular, for systems whose components operate at different levels of granularity, as this results in many executions of some components in one iteration. This article aims at efficiently calculating the max-plus semantics of SDFGs. This article proposes an optimization framework exploring decompositions of a given SDFG and finding a composition sequence whose computational effort for compositionally obtaining the max-plus semantics is minimal. Not only does our proposed technique accelerate the performance analysis of multiscale streaming systems, but it also allows us to compute the max-plus semantics of some systems for which the state-of-the-art method does not succeed because of memory limitations.

The energy efficiency of an Internet of Things (IoT) receiver can be improved by introducing an adjustable tradeoff between signal quality and energy consumption. In good channel conditions, the receiver can be set to consume less energy per bit, without compromising signal quality in bad channel conditions. We propose a system-level receiver design that enables adequate configuration and combination of signal quality and energy tradeoffs in multiple receiver components. Co-design of all components is essential. We identify the most energy-efficient configurations in our system-level design under different channel conditions. With those configurations, the proposed receiver outperforms a state-of-the-art adjustable receiver with only an adjustable analog front end by several tens of percent in energy per successfully received bit and by$2\times $in energy-sensitivity configuration range. To show the efficacy of the proposed approach, we integrate a model of the proposed design into the OMNeT++ simulator and show the benefits on an environmental monitoring scenario. In this scenario, we report up to$6\times $energy savings for the entire transceiver compared to the conventional transceiver design without adjustable receiver.

System-Performance Engineering (SysPE) encompasses modeling formalisms, methods, techniques, and industrial practices to design systems for performance, where performance is taken integrally into account during the whole system life cycle. Industrial SysPE state of practice is generally model-based. Due to the rapidly increasing complexity of systems, there is a need to develop and establish model-driven methods and techniques. To structure the field of SysPE, we identify (1) industrial challenges motivating the importance of SysPE, (2) scientific challenges that need to be addressed to establish model-driven SysPE, (3) important focus areas for SysPE and (4) best practices. We conducted a survey to collect feedback on our views. The responses were used to update and validate the identified challenges, focus areas, and best practices. The final result is presented in this paper. Interesting observations are that industry sees a need for better design-space exploration support, more than for additional performance modeling and analysis techniques. Also tools and integral methods for SysPE need attention. From the identified focus areas, scheduling and supervisory control is seen as lacking established best practices.

Image-based control (IBC) systems use camera sensor(s) to perceive the environment. The inherent compute-heavy nature of image processing causes long processing delay that negatively influences the performance of the IBC systems. Our idea is to reduce the long delay using coarse-grained approximation of the image signal processing pipeline without affecting the functionality and performance of the IBC system. The question is: how is the degree of approximation related to the closed-loop quality-of-control (QoC), memory utilization and energy consumption? We present a software-in-the-loop (SiL) evaluation framework for the above approximation-in-the-loop system. We identify the error resilient stages and the corresponding coarse-grained approximation settings for the IBC system. We perform trade off analysis between the QoC, memory utilisation and energy consumption for varying degrees of coarse-grained approximation. We demonstrate the effectiveness of our approach using a concrete case study of a lane keeping assist system (LKAS). We obtain energy and memory reduction of upto 84% and 29% respectively, for 28% QoC improvements.

In this work, a design of an IEEE 802.15.4 con-formant O-QPSK demodulator is proposed, which is capable of trading off receiver sensitivity for power savings. Such design can be used to meet rigid energy and power constraints for many applications in the Internet-of-Things (IoT) context. In a Body Area Network (BAN), for example, the circuits need to operate with extremely limited energy sources, while still meeting the network performance requirements. This challenge can be addressed by the paradigm of adequate computing, which trades off excessive quality of service for power or energy using approximation techniques. Three different, adjustable approximation techniques are integrated into the demodulation to trade off effective signal quantization bit-width, filtering performance, and sampling frequency for power. Such approximations impact incoming signal sensitivity of the demodulator. For detailed trade-off analysis, the proposed design is implemented in a commercial 40-nm CMOS technology to estimate power and in Python to estimate sensitivity. Simulation results show up to 64% power savings by sacrificing $\tilde 7$ dB sensitivity.

Cyber-Physical Systems (CPS) are dynamic and reactive systems interacting with processes, environment and, sometimes, humans. They are often distributed with sensors and actuators, smart, adaptive, predictive and react in real-time. Indeed, as sight for human beings, image- and video-processing pipelines are a prime source for environmental information for systems allowing them to take better decisions according to what they see. Therefore, in FitOptiVis we are developing novel methods and tools to integrate complex image and video processing pipelines. FitOptiVis aims to deliver a reference architecture for describing and optimizing quality and resource management for imaging and video pipelines in CPS both at design- and run-time. The architecture is concretized in low-power, high-performance, smart components, and in methods and tools for combined design-time and run-time multi-objective optimization and adaptation within system and environment constraints.

Cyber-physical systems (CPS) are complex, heterogeneous, and dynamic systems, spanning hardware and software components ranging from edge devices to cloud platforms. CPS need to satisfy many rigorous constraints, e.g., with respect to deadlines, safety, and quality, yielding a large configuration space where only a limited number of configurations meet the constraints and only a fraction are optimal regarding certain qualities. Finding the optimal configurations is hard, especially during runtime operation. We present QRML, the Quality and Resource Management domain-specific Language, and an accompanying toolset. QRML enables specifying heterogeneous hardware/software systems and their composition and configurations conveniently, automated reasoning about them, and generating implementation artifacts like quality and resource monitoring templates. A QRML model consists of a hierarchy of components. Component specifications express constraints and requirements, that may serve multiobjective quality and resource optimization and exploration purposes. The QRML toolset offers language support, visualizations, documentation generation, template-code generation, and constraint-solving support.

Tensor Cores (TCUs) are specialized units first introduced by NVIDIA in the Volta microarchitecture in order to accelerate matrix multiplications for deep learning and linear algebra workloads. While these units have proved to be capable of providing significant speedups for specific applications, their programmability remains difficult for the average user. In this paper, we extend the Halide DSL and compiler with the ability to utilize these units when generating code for a CUDA based NVIDIA GPGPU. To this end, we introduce a new scheduling directive along with custom lowering passes that automatically transform a Halide AST in order to be able to generate code for the TCUs. We evaluate the generated code and show that it can achieve over 5X speedup compared to Halide manual schedules without TCU support, while it remains within 20% of the NVIDIA cuBLAS implementations for mixed precision GEMM and within 10% of manual CUDA implementations with WMMA intrinsics.

Vehicle platooning is a technology capable of reducing the distance between vehicles, which in turn increases the road capacity and reduces the fuel consumption. In vehicle platooning, vehicles exchange information through wireless Vehicle-to-Vehicle (V2V) communication. The maximum message rate is limited by the traffic of vehicles equipped with V2V capabilities and the communication protocols. It can vary between 1Hz and 10Hz in IEEE 802. 11p. Many platoon control strategies in the literature do not consider the limited message rate and are not usable in real-life scenarios. One of the strategies capable of dealing with lower message rates uses Model Predictive Control (MPC), a type of optimal controller with a high computational cost. In this work, we analyze the performance of an MPC platoon control over IEEE 802. 11p using embedded platforms from Cohda Wireless and NXP Semiconductors. We consider a set of commonly used message rates -1, 2, 5 and 10Hz as well as sensor noise. We analyze the string stability and fuel consumption to evaluate the performance of the platoon controllers. We show that MPC provides satisfactory performance with a message rate as low as 1Hz and it outperforms the platoon control state-of-the-art techniques. Our results clearly show the need for taking into account message rate restrictions in the control algorithms.

The Halide DSL and compiler have enabled high-performance code generation for image processing pipelines targeting heterogeneous architectures through the separation of algorithmic description and optimization schedule. However, automatic schedule generation is currently only possible for multi-core CPU architectures. As a result, expert knowledge is still required when optimizing for platforms with GPU capabilities. In this work, we extend the current Halide Autoscheduler with novel optimization passes to efficiently generate schedules for CUDA-based GPU architectures. We evaluate our proposed method across a variety of applications and show that it can achieve performance competitive with that of manually tuned Halide schedules, or in many cases even better performance. Experimental results show that our schedules are on average 10% faster than manual schedules and over 2× faster than previous autoscheduling attempts.

( m , k )-firm real-time tasks require meeting the deadline of at least m jobs out of any k consecutive jobs. When compared to hard real-time tasks, ( m , k )$-firm tasks open up the possibility of tighter resource-dimensioning in implementations. Firmness analysis verifies the satisfaction of ( m , k )-firmness conditions. Scheduling policies under which a set of periodic tasks runs on a resource influence the number of deadline missed jobs. Therefore, the nature of the firmness analysis problem depends on scheduling policies. In this work, we present Firmness Analysis (FAn) methods for three common scheduling policies—synchronous and asynchronous Static Priority Preemptive (SPP) policies and Time Division Multiple Access (TDMA). We first introduce the Balloon and Rake problem—the problem of striking the maximum number of balloons in a balloon line with a rake. We show that the common core of firmness analysis problems can be abstracted as the Balloon and Rake problem. Next, we prove that the Finite Point method is a solution to the Balloon and Rake problem. We illustrate how existing FAn methods for the TDMA and asynchronous SPP policies can be adapted to use the same solution framework for the Balloon and Rake problem. Using the solution of the Balloon and Rake problem, we adapt the existing FAn methods to synchronous SPP scheduling policies. The scalability of the FAn methods is compared with that of a timed-automata approach, a brute-force approach, and a Mixed Integer Linear Programing method. The FAn methods scale substantially better to firmness analysis problem instances with a large k and a high number of tasks.

Cyber-Physical Systems (CPS) are systems that are in feedback with their environment, possibly with humans in the loop. They are often distributed with sensors and actuators, smart, adaptive and predictive and react in real-time. Image- and video-processing pipelines are a prime source for environmental information improving the possibilities of active, relevant feedback. In such a context, FitOptiVis aims to provide end-to-end multi-objective optimization for imaging and video pipelines of CPS, with emphasis on energy and performance, leveraging on a reference architecture, supported by low-power, high-performance, smart devices, and by methods and tools for combined design-time and run-time multi-objective optimization within system and environment constraints.

To handle the rigid power and energy constraints in the Digital BaseBand (DBB) of Wireless Sensor Networks (WSN)s, we introduce approximate computing as a new power reduction method. The Received Signal Strength Indicator (RSSI) computation is a key element in DBB processing. We evaluate the trade-off in RSSI computation between Quality-of-Service (QoS) and power consumption through circuit-level approximation. RSSI elements are approximated in such a way that error propagation is minimized. In an industrial 40-nm CMOS technology, substantial energy savings up to 24% are achieved for every successfully transferred bit in DBB processing in a low- power listening WSN scenario.

Image-based control uses image-processing algorithms to acquire sensing information. The sensing delay associated with the image-processing algorithm is typically platform-dependent and time-varying. Modern embedded platforms allow to characterize the sensing delay at design-time obtaining a delay histogram, and at run-time measuring its precise value. We exploit this knowledge to design variable-delay controllers. This design also takes into account the resource configuration of the image processing algorithm: sequential (with one processing resource) or pipelined (with multiprocessing capabilities). Since the control performance strongly depends on the model quality, we present a simulation benchmark that uses the model uncertainty and the delay histogram to obtain bounds on control performance. Our benchmark is used to select a variable-delay controller and a resource configuration that outperform a constant worst-case delay controller.

Efficient code generation for image processing applications continues to pose a challenge in a domain where high performance is often necessary to meet real-time constraints. The inherently complex structure found in most image-processing pipelines, the plethora of transformations that can be applied to optimize the performance of an implementation, as well as the interaction of these optimizations with locality, redundant computation and parallelism, can be indentified as the key reasons behind this issue. Recent domain-specific languages (DSL) such as the Halide DSL and compiler attempt to encourage high-level design-space exploration to facilitate the optimization process. We propose a novel optimization strategy that aims to maximize producer-consumer locality by exploiting reuse in image-processing pipelines. We implement our analysis as a tool that can be used alongside the Halide DSL to automatically generate schedules for pipelines implemented in Halide and test it on a variety of benchmarks. Experimental results on three different multi-core architectures show an average performance improvement of 40% over the Halide Auto-Scheduler and 75% over a state-of-the art approach that targets the PolyMage DSL.

Pipelined image-based control uses parallel instances of its image-processing algorithm in a pipelined fashion to improve the quality of control. A performance-oriented control design improves the controller settling time with each additional processing resource, which creates a resources-performance trade-off. In real-life applications, it is common to have a continuous-time model with additive uncertainties in one or more parameters that may affect the controller performance and the aforementioned trade-off. We present a robustness analysis framework for performance-oriented pipelined controllers with additive model uncertainties. We present a technique to obtain discrete-time uncertainties based on the continuous-time uncertainties for given uncertainty bounds. To benchmark such uncertainty bounds for a real system, we consider uncertainties in one element of the system, potentially caused by multiple uncertain parameters in the model. Robustness and its impact in the trade-off analysis are studied. We also provide a robustness-oriented pipelined controller design that takes into account the benchmarked uncertainties. Our results show that in performance-oriented designs, the tolerable uncertainties for a pipelined controller decrease when increasing the number of pipes. In robustness-oriented designs, the controller robustness is enhanced with each newly added pipe. We show the feasibility of our technique by implementing a realistic example in a Hardware-in-the-Loop simulation.

Schedulers assign starting times to events in a system such that a set of constraints is met and system productivity is maximized. We characterize the scheduler behaviour for the case where decisions are made by comparing affine expressions of design parameters such as task workload, processing speed, robot travelling speed, or a controller’s rise and settling time. Deterministic schedulers can be extended with symbolic execution, to keep track of the affine conditions on the parameters for which the scheduling decisions are made. We introduce a divide-and-conquer algorithm that uses this information to determine parameter regions for which the same sequence of decisions is taken given a particular scenario. The results provide designers insight in the impact of parameter changes on the performance of their system. The exploration can also be executed with the KLEE symbolic execution engine of the LLVM tool chain to extract the same results. We show that the divide-and-conquer approach provides the results much faster than the generic symbolic execution engine of KLEE. The results allow visualization of the sensitivity to all parameter combinations. The results of our approach therefore provide more insight in the sensitivity to parameters.

Wireless sensor networks (WSNs) are considered as a promising solution in intravehicle networking to reduce wiring and production costs. This application requires reliable and real-time data delivery, while the network is very dense. The time-slotted channel hopping (TSCH) mode of the IEEE 802.15.4 standard provides a reliable solution for low-power networks through guaranteed medium access and channel diversity. However, satisfying the stringent requirements of in-vehicle networks is challenging and demands for special consideration in network formation and TSCH scheduling. This paper targets convergecast in dense in-vehicle WSNs, in which all nodes can potentially directly reach the sink node. A cross-layer low-latency topology management and TSCH scheduling (LLTT) technique is proposed that provides a very high timeslot utilization for the TSCH schedule and minimizes communication latency. It first picks a topology for the network that increases the potential of parallel TSCH communications. Then, by using an optimized graph isomorphism algorithm, it extracts a proper match in the physical connectivity graph of the network for the selected topology. This network topology is used by a lightweight TSCH schedule generator to provide low data delivery latency. Two techniques, namely grouped retransmission and periodic aggregation, are exploited to increase the performance of the TSCH communications. The experimental results show that LLTT reduces the end-to-end communication latency compared to other approaches, while keeping the communications reliable by using dedicated links and grouped retransmissions.

Memory-bound applications heavily depend on the bandwidth of the system in order to achieve high performance. Improving temporal and/or spatial locality through loop transformations is a common way of mitigating this dependency. However, choosing the right combination of optimizations is not a trivial task, due to the fact that most of them alter the memory access pattern of the application and as a result interfere with the efficiency of the hardware prefetching mechanisms present in modern architectures. We propose an optimization algorithm that analytically classifies an algorithmic description of a loop nest in order to decide whether it should be optimized stressing its temporal or spatial locality, while also taking hardware prefetching into account. We implement our technique as a tool to be used with the Halide compiler and test it on a variety of benchmarks. We find an average performance improvement of over 40% compared to previous analytical models targeting the Halide language and compiler.

Modular design is a common practice when designing complex applications for embedded systems. Another important practice in the embedded systems domain is the use of abstract models to realize predictable behaviour. Modular model-based design allows to construct a modular model of a complex system via model composition. The model of computation considered in this paper is scenario-aware dataflow, a dataflow model that allows for dynamic behaviour. We model applications with behaviour that changes according to a periodic pattern. Composing models with periodic patterns results in a model with a periodic pattern with a common hyper-period. We propose an efficient algorithmic method to compose cyclo-static scenario-aware dataflow models by generating composite patterns in a concise representation. We show that our approach can automatically generate concise models of several real-life image processing applications.

Vehicle platooning has gained attention for its potential to achieve an increased road capacity and safety, and a higher fuel efficiency. Member vehicles of a platoon wirelessly communicate complying with industrial standards such as IEEE 802.11p. By exchanging information with other members via wireless communication, a platoon member computes its desired acceleration which is then passed on to the engine control system via in-vehicle network to physically realize the acceleration. This leads to a multi-layer control scheme. The upper-layer is influenced by the behavior of 802.11p communication and network congestion due to transmissions by other vehicles in the traffic. The lower-layer engine control loop communicates over the fast and reliable in-vehicle networks (e.g., FlexRay, Ethernet). Design of the overall system therefore depends on (i) the characteristics of 802.11p-based communication (ii) the nature of the traffic (iii) the control algorithms running at the two layers. We present a cosimulation framework consisting of Matlab (for the multi-layer control algorithms), ns-3 (for the 802.11p network) and SUMO (for the traffic behavior). The framework can be used to validate different platooning setups. As an illustrative case study, we consider a multi-layer control strategy where the upper-layer uses Model Predictive Control (MPC) at a rate in compliance with 802.11p and the lower-layer uses statefeedback control at a higher sampling rate in line with in-vehicle networking capabilities. The control strategy is evaluated considering various realistic traffic and network congestion scenarios.

We develop a model-based approach to predict timing of service-based software applications on Linux-based multi-core platforms for alternative mappings (affinity and priority settings). Service-based applications consist of communicating sequential (Linux) processes. These processes execute functions (also called services), but can only execute them one at a time. Models are inferred automatically from execution traces to enable timing optimization of existing (legacy) systems. Our approach relies on a linear progress approximation of functions. We compute the expected share of each function based on the mapping (affinity and priority) parameters and the functions that are currently active. We validate our models by carrying out a controlled lab experiment consisting of a multi-process pipelined application mapped in different ways on a quadcore Intel i7 processor. A broad class of affinity and priority settings is fundamentally unpredictable due to Linux binding policies. We show that predictability can be achieved if the platform is partitioned in disjoint clusters of cores such that i) each process is bound to such a cluster, ii) processes with non real-time priorities are bound to singleton clusters, and iii) all processes bound to a non-singleton cluster have different real-time priorities. For mappings using singleton clusters with niceness priorities only, our model predicts execution latencies (for each pipeline iteration) with errors less than 5% relative to the measured execution times. For mappings using a non-singleton cluster (with different real-time priorities) relative errors of less than 2% are obtained. When real-time and niceness priorities are mixed, we predict with errors of 7%.

Image-Based Control (IBC) systems have a long sample period. Sensing in these systems consists of compute-intensive image processing algorithms whose response times are dependent on image workload. IBC systems are typically designed for the worst-case workload that results in a long sample period and hence suboptimal quality-of-control (QoC). This worst-case based design is further considered for mapping of controller tasks and allocating platform resources, resulting in significant resource over-provisioning. Our design philosophy is to sample as fast as possible to optimise QoC for a given platform allocation, and for this, we present a structured design flow. Workload variations determine how fast we can sample and we model this dynamic behaviour using the concept of workload scenarios. Our choice of scenario-aware dataflow as the formal model for our application enables us to: i) model dynamic behaviour, analyse timing, and optimally map application tasks to the platform for maximising the effective utilisation of allocated resources, ii) relate throughput of the dataflow graph to the sample period, and thus combine dataflow analysis and mapping with control design parameters and QoC to identify system scenarios, and iii) to efficiently implement a run-time mechanism that manages necessary dynamic reconfiguration between system scenarios. Our results show that our design approach outperforms the worst-case based design with respect to optimising QoC and maximising effective resource utilisation.

Feedback control applications are robust to occasional deadline misses. This opens up the possibility of saving scarce (computation and communication) resources on embedded platforms. Stability and performance requirements of a control loop impose restrictions on acceptable patterns of deadline misses (e.g., not too many misses in a row). Such requirements are captured by (m,k)-firmness conditions. That is, at least m control computation jobs must meet deadlines in any k consecutive jobs. (m,k)-firm design requires (i) representation of stability and performance requirements in terms of (m,k)-firm deadlines (ii) controller synthesis taking into account the (m,k)-firmness parameters (iii) schedule analysis to verify guarantees on meeting the firmness conditions. We present a co-synthesis framework for these three design components and illustrate its applicability with examples.

The IEEE 802.15.4 Time-Slotted Channel Hopping (TSCH) protocol defines two types of timeslots for communications, namely dedicated and shared timeslots. An upper layer in the protocol stack uses these timeslots to design a communication schedule for the network links, based on the required bandwidth for each link. Considering a network with time-varying data traffic generation by each node, the bandwidth requirements are changing over time for each link. This leads to poor efficiency of a predefined schedule when there is no data traffic for the dedicated timeslots, or there is too much data traffic injected to the shared timeslots. In this paper, we propose a new type of timeslot, called hybrid timeslot. A hybrid timeslot acts as a dedicated timeslot for a specific link, when there are packets available to be transmitted on that link. Otherwise, it acts as a shared timeslot that can be accessed by other links, using a contention-based mechanism. The hybrid timeslot has backward compatibility with the TSCH protocol and is functional with a few adaptations in the parameter setup of the TSCH protocol. Experimental and simulation results show that for heterogeneous networks using hybrid timeslots improves communication latency without reliability penalty.

(m, k)-firm real-time tasks must meet the deadline of at least m jobs out of any k consecutive jobs to satisfy the firmness requirement. Scheduling of an (m,k)-firm task requires firmness analysis, whose results are used to provide system-level guarantees on the satisfaction of firmness conditions. We address firmness analysis of an (m, k)-firm task that is intended to be added to a set of asynchronous tasks scheduled under a Static-Priority Preemptive (SPP) policy. One of the main causes of deadline misses in periodic tasks running under an SPP policy is interference from higher priority tasks. Since the synchrony between the newly added task and higher priority tasks is unknown, the interference from the higher priority tasks is also unknown. We propose an analytic Firmness Analysis (FAn) method to obtain a synchrony that results in the maximum minimum number of deadline hit jobs in any k consecutive jobs of the task. Scalability of FAn is compared with that of existing work - a brute-force search approach - and a timed-automata model of the problem that is analysed using the reachability check of the Uppaal model checker. Our method substantially reduces the complexity of the analysis.

Time-Slotted Channel Hopping (TSCH) is considered as one of the most reliable MAC solutions for low- power wireless networking. In order to establish time-slotted communications, this technique requires all nodes to remain synchronized. The synchronization is continuously done through normal communications to compensate the clock drift between different nodes. In this paper, we present a detailed look into the behavior of the IEEE 802.15.4 PHY and MAC in terms of the synchronization task. We show that the relation between timeslot offsets provided by the standard leads to different synchronization error margins for positive and negative relative clock drifts. This is due to the time required for detection of ongoing transmissions at receivers. This may lead to the situation that two nodes are able to communicate in only one direction. Depending on which node is the source node, the available margin to compensate the relative clock drift is different. Accordingly, we provide new values for timeslot offsets to compensate positive and negative relative clock drifts equally. Simulation results confirm that the standard offsets reduce the performance of TSCH due to asymmetric synchronization error handling. The results also show that this negative effect is mitigated by using the new offsets provided in this paper.

High-end manufacturing systems are cyber-physical systems, where productivity depends on the close cooperation of mechanical (physical) and scheduling (cyber) aspects. Mechanical and control constraints impose minimal and maximal time differences between events in the product flow. Sequence-dependent constraints are used by a scheduler to optimize system productivity while satisfying operational requirements. The numerous constraints in a schedule are typically related to a relatively small set of parameters, such as speeds, lengths, or settling times. We contribute a parametric critical path algorithm that identifies bottlenecks in terms of the feasible parameter combinations. This algorithm allows analysis of schedules to identify bottlenecks in terms of the underlying cause of constraints. We also contribute a way to find Pareto-optimal cost-performance tradeoffs and their associated parameter combinations. These results are used to quantify the impact of relaxing constraints that hinder system productivity.

Multi-scale dataflow models have actors acting at multiple granularity levels, e.g., a dataflow model of a video processing application with operations on frame, line, and pixel level. The state of the art timing analysis methods for both static and dynamic dataflow types aggregate the behaviours across all granularity levels into one, often large iteration, which is repeated without exploiting the structure within such an iteration. This poses scalability issues to dataflow analysis, because behaviour of the large iteration is analysed by some form of simulation that involves a large number of actor firings. We take a fresh perspective of what is happening inside the large iteration. We take advantage of the fact that the iteration is a sequence of smaller behaviours, each captured in a scenario, that are typically repeated many times. We use the (max ,+) linear model of dataflow to represent each of the scenarios with a matrix. This allows a compositional worst-case throughput analysis of the repeated scenarios by raising the matrices to the power of the number of repetitions, which scales logarithmically with the number of repetitions, whereas the existing throughput analysis scales linearly. We moreover provide the first exact worst-case latency analysis for scenario-aware dataflow. This compositional latency analysis also scales logarithmically when applied to multi-scale dataflow models. We apply our new throughput and latency analysis to several realistic applications. The results confirm that our approach provides a fast and accurate analysis.

IEEE 802.15.4 Time-Slotted Channel Hopping (TSCH) aims to improve communication reliability in Wireless Sensor Networks (WSNs) by reducing the impact of the medium access contention, multipath fading, and blocking of wireless links. While TSCH outperforms single-channel communications, cross-technology interference on the license-free ISM bands may affect the performance of TSCH-based WSNs. For applications such as in-vehicle networks for which interference is dynamic over time, it leads to non-guaranteed reliability of the communications over time. This article proposes an Enhanced version of the TSCH protocol together with a Distributed Channel Sensing technique (ETSCH+DCS) that dynamically detects good quality channels to be used for communication. The quality of channels is extracted using a combination of a central and a distributed channel-quality estimation technique. The central technique uses Non-Intrusive Channel-quality Estimation (NICE) technique that proactively performs energy detections in the idle part of each timeslot at the coordinator of the network. NICE enables ETSCH to follow dynamic interference, while it does not reduce throughput of the network. The distributed channel quality estimation technique is executed by all the nodes in the network, based on their communication history, to detect interference sources that are hidden from the coordinator. We did two sets of lab experiments with controlled interferers and a number of simulations using real-world interference datasets to evaluate ETSCH. Experimental and simulation results show that ETSCH improves reliability of network communications, compared to basic TSCH and the state-of-the-art solution. In some experimental scenarios NICE itself has been able to increase the average packet reception ratio by 22% and shorten the length of burst packet losses by half, compared to the plain TSCH protocol. Further experiments show that DCS can reduce the effect of hidden interference (which is not detectable by NICE) on the packet reception ratio of the affected links by 50%.

Online scheduling of operations is essential to optimize productivity of flexible manufacturing systems (FMSs) where manufacturing requests arrive on the fly. An FMS processes products according to a particular flow through processing stations. This work focusses on online scheduling of re-entrant FMSs with flows using processing stations where products pass twice and with limited buffering between processing stations. This kind of FMS is modelled as a re-entrant flow shop with due dates and sequence-dependent set-up times. Such flow shops can benefit from minimization of the time penalties incurred from set-up times. On top of an existing greedy scheduling heuristic we apply a meta-heuristic that simultaneously explores several alternatives considering trade-offs between the used metrics by the scheduling heuristic. We identify invariants to efficiently remove many infeasible scheduling options so that the running time of online implementations is improved. The resulting algorithm is much faster than the state of the art and produces schedules with on average 4.6% shorter makespan.

This article studies the scheduling of real-time streaming applications on multiprocessor systems-on-chips with predictable memory hierarchy. An iteration-based task-FIFO co-scheduling framework is proposed for this problem. We obtain FIFO size distributions using Pareto space searching, based on which the task-to-processor mapping is obtained with the potential FIFO allocation being taken into account; then, the FIFO-to-memory allocation is optimized to minimize the total memory access cost; finally, a self-timed throughput analysis method that considers memory and direct memory access controller contention is utilized to analyze the throughput. Our methods are validated by a set of synthesized and practical applications on different platforms.

No abstract available.

Self re-entrant flowshops consist of machines which process jobs several times. They are found in applications like TFT-LCD assembly, LED manufacturing and industrial printing. The structure of a self re-entrant flowshop influences its performance. To get better performance while reducing costs a fast performance estimation method can be used to explore the trade-offs between the structure and the performance during the design process. We present a novel performance estimator that uses the information in the jobs being processed to analyse the trade-offs. We study the impact of the design parameters of an industrial printer using the performance estimator with an average estimation time of 1.1 milliseconds per job and with an average accuracy of not less than 96%.

This paper introduces a formal modeling approach for compositional specification of both functionality and timing of manufacturing systems. Functionality aspects can be considered orthogonally to timing aspects. The functional aspects are specified using two abstraction levels; high-level activities and lower level actions. Design of a functionally correct controller is possible by looking only at the activity level, abstracting from the different execution orders of actions and their timing. As a result, controller design can be performed on a much smaller state space compared to an explicit model where timing and actions are present. The performance of the controller can be analyzed and optimized by taking into account the timing characteristics. Since formal semantics are given in terms of a (max, +) state space, various existing performance analysis techniques can be used. We illustrate the approach, including performance analysis, on an example manufacturing system.

The problem of online face tracking from unconstrained videos is still unresolved. Challenges range from coping with severe online appearance variations to coping with occlusion. We propose RFTD (Robust Face Tracking-by-Detection), a system which combines tracking and detection into a single framework to robustly track a face from unconstrained videos. RFTD is based on the idea that adaptive and stable algorithmic components can complement each other in the task of online tracking. An online Structured Output SVM (SO-SVM) is combined with an offline trained face detector to break the self-learning loop typical in tracking. In turn, the face detector is supervised by a Deformable Part Model (DPM) landmark detector to asses the reliability of the face detection output. Extensive evaluation shows that RFTD delivers consistently good tracking performances across different scenarios, i.e., high mean success rate and lowest standard deviation across benchmark videos.

Wireless in-vehicle networks are considered as a flexible and cost-efficient solution for the new generation of cars. One of the candidate wireless technologies for these wireless sensor networks is the IEEE 802.15.4 standard which operates in the 2.4 GHz ISM band. This is while the number of wireless devices that operate in this band is ever increasing. This broad usage of the same RF band may cause considerable performance degradation of wireless networks due to interference. There is some work on the coexistence of the IEEE 802.15.4 protocol and other standard technologies such as IEEE 802.11 (Wi-Fi) and IEEE 802.15.1 (Bluetooth), but none of it considers the highly dynamic conditions of in-vehicle networks. In this paper, we investigate the interference behavior in in-vehicle environments using real-world experiments. We consider different scenarios and measure the interference on all the 16 channels of IEEE 802.15.4 in the 2.4 GHz band.The measurement data set is available to the public. This real-world data set can be used for realistic and accurate network simulation. To study the effect of interference on in-vehicle networks, we use this data set to evaluate the performance of an IEEE 802.15.4e TSCH link. The simulation results show that the packet error rate for some interference scenarios is considerably high and dynamic over time. This shows the value of the data set and reveals the importance of using adaptive interference mitigation techniques to improve the reliability of wireless in-vehicle networks.

Synchronous dataflow graphs (SDFGs) are widely used to represent digital signal processing algorithms and streaming media applications. This paper presents several methods for binding and scheduling SDFGs on a multiprocessor platform. Exploring the state space generated by a self-timed execution (STE) of an SDFG, we present an exact method for static rate-optimal scheduling of SDFGs via implicit retiming and unfolding. By modeling a constraint as an extra enabling condition for the STE, we get a constrained STE which implies a schedule under the constraint. We present a general framework for scheduling SDFGs under constraints on the number of processors, buffer sizes, auto-concurrency, or combinations of them. Exploring the state space generated by the constrained STE, we can check whether a retiming, which leads to a rate-optimal schedule under the processor (or memory) constraint, exists. Combining this with a binary search strategy, we present heuristic methods to find a proper retiming and a static scheduling that schedules the retimed SDFG with optimal rate and with as few processors (or as little storage space) as possible. None of the methods explicitly converts an SDFG to its equivalent homogenous SDFG, the size of which may be tremendously larger than the original SDFG. We perform experiments on several models of real applications and hundreds of synthetic SDFGs. The results show that the exact method outperforms existing methods significantly; our heuristics reduce the resources used and are computationally efficient.

Online detection and tracking of a variable number of faces in video is a crucial component in many real-world applications ranging from video-surveillance to online gaming. In this paper we propose FAST-DT, a fully automated system capable of detecting and tracking a variable number of faces online without relying on any scene-specific cues. FAST-DT integrates a generic face detector with an adaptive structured output SVM tracker and uses the detector's continuous confidence to solve the target creation and removal problem. We improve in recall and precision over a state-of-the-art method on a video dataset of more than two hours while providing in addition an increase in throughput.

Cross-technology interference on the license-free ISM bands has a major negative effect on the performance of Wireless Sensor Networks (WSNs). Channel hopping has been adopted in the Time-Slotted Channel Hopping (TSCH) mode of IEEE 802.15.4e to eliminate blocking of wireless links caused by external interference on some frequency channels. This paper proposes an Enhanced version of the TSCH protocol (ETSCH) which restricts the used channels for hopping to the channels that are measured to be of good quality. The quality of channels is extracted using a new Non-Intrusive Channel-quality Estimation (NICE) technique by performing energy detections in selected idle periods every timeslot. NICE enables ETSCH to follow dynamic interference well, while it does not reduce throughput of the network. It also does not change the protocol, and does not require non-standard hardware. ETSCH uses a small Enhanced Beacon hopping Sequence List (EBSL) to broadcast periodic Enhanced Beacons (EB) in the network to synchronize nodes at the start of timeslots. Experimental results show that ETSCH improves reliability of network communication, compared to basic TSCH and a more advanced mechanism ATSCH. It provides higher packet reception ratios and reduces the maximum length of burst packet losses.

Development of high-level supervisory controllers is an important challenge in the design of high-tech systems. It has become a significant issue due to increased complexity, combined with demands for verified quality, time to market, ease of development, and integration of new functionality. To deal with these challenges, model-based engineering approaches are suggested as a cost-effective way to support easy adaptation, validation, synthesis, and verification of controllers. This paper presents an industrial case study on modular design of a supervisory controller for wafer logistics in lithography machines. The uncontrolled system and control requirements are modeled independently in a modular way, using small, loosely coupled and minimally restrictive extended finite automata. The multiparty synchronization mechanism that is part of the specification formalism provides clear advantages in terms of modularity, traceability, and adaptability of the model. We show that being able to refer to variables and states of automata in guard expressions and state-based requirements, enabled by the use of extended finite automata, provides concise models. Additionally, we show how modular synthesis allows construction of local supervisors that ensure safety of parts of the system, since monolithic synthesis is not feasible for our industrial case.

Wireless Sensor Networks (WSNs) are commonly deployed in dynamic environments where events, such as moving sensor nodes and changing external interference, impact the performance, or Quality of Service (QoS), of the network. QoS is expressed by the values of multiple, possibly conflicting, network quality metrics, such as network lifetime and maximum latency of communicating a packet to the sink. Sufficient QoS should be provided by the WSN to ensure that the end-user can successfully use the WSN to perform its application. We propose a distributed reconfiguration approach that actively maintains a sufficient level of QoS at runtime for a heterogeneous WSN in a dynamic environment. Every node uses a feedback control strategy to resolve any difference between the current and required QoS of the network by adapting controllable parameters of the protocol stack. Example parameters are the transmission power and maximum number of packet retransmissions. Nodes collaborate such that, with the combined adaptations, the required network QoS is achieved. The behavior of the reconfiguration approach and the tradeoffs involved are analyzed in detail. With the use of simulations and experiments with actual deployments, we show that our approach allows a better optimization of QoS objectives while constraints are met; for example, it achieves the same packet loss with a significantly longer lifetime, compared to current (re-)configuration approaches.

Synchronous dataflow graphs (SDFGs) are widely used to model digital signal processing (DSP) and streaming media applications. In this paper, we use retiming to optimize SDFGs to achieve a high throughput with low storage requirement. Using a memory constraint as an additional enabling condition, we define a memory constrained self-timed execution of an SDFG. Exploring the state-space generated by the execution, we can check whether a retiming exists that leads to a rate-optimal schedule under the memory constraint. Combining this with a binary search strategy, we present a heuristic method to find a proper retiming and a static scheduling which schedules the retimed SDFG with optimal rate (i.e., maximal throughput) and with as little storage space as possible. Our experiments are carried out on hundreds of synthetic SDFGs and several models of real applications. Differential synthetic graph results and real application results show that, in 79% of the tested models, our method leads to a retimed SDFG whose rate-optimal schedule requires less storage space than the proven minimal storage requirement of the original graph, and in 20% of the cases, the returned storage requirements equal the minimal ones. The average improvement is about 7.3%. The results also show that our method is computationally efficient.

Patient observations in health care, subjective surveys in social research or dyke sensor data in water management are all examples of measurements. Several ontologies already exist to express measurements, W3C's SSN ontology being a prominent example. However, these ontologies address quantities and properties as being equal, and ignore the foundation required to establish comparability between sensor data. Moreover, a measure of an observation in itself is almost always inconclusive without the context in which the measure was obtained. ContoExam addresses these aspects, providing for a unifying capability for context-aware expressions of observations about quantities and properties alike, by aligning them to ontological foundations, and by binding observations inextricably with their context.

Object detection and tracking is one of the most important components in computer vision applications. To carefully evaluate the performance of detection and tracking algorithms, it is important to develop benchmark data sets. One of the most tedious and error-prone aspects when developing benchmarks, is the generation of the ground truth. This paper presents FAST-GT (FAst Semi-automatic Tool for Ground Truth generation), a new generic framework for the semiautomatic generation of ground truths. FAST-GT reduces the need for manual intervention thus speeding-up the ground-truthing process.

Node mobility is a key feature of using Wireless Sensor Networks (WSNs) in many sensory applications, such as healthcare. The Medium Access Control (MAC) protocol should properly support the mobility in the network. In particular, mobility is complicated for contention-free protocols like Time Division Multiple Access (TDMA). An efficient access to the shared medium is scheduled based on the node's local neighborhood. This neighborhood may vary over time due to node movement or other dynamics. In scenarios including body-area networking, for instance, some clusters of nodes move together, creating further challenges but also opportunities. This article presents a MAC protocol, MCMAC, that provides efficient support for cluster mobility in TDMA-based MAC protocols in WSNs. The proposed protocol exploits a hybrid contention-free and contention-based communication approach to support cluster mobility. This relieves the protocol from rescheduling demand due to frequent node movements. Moreover, we propose a listening scheduling mechanism to avoid idle listening to mobile nodes that leads to a considerable energy saving for sensor nodes. The protocol is validated by performing several experiments in a real-world large-scale deployment including several mobile clusters. The protocol is also evaluated by extensive simulation of networks with various scales and configurations.

Latest trends in embedded platform architectures show a steady shift from high frequency single core platforms to lower-frequency but highly-parallel execution platforms. Scheduling applications with stringent latency requirements on such multiprocessor platforms is challenging. Our work is motivated by the scheduling challenges faced by ASML, the world's leading provider of wafer scanners. A wafer scanner is a complex cyber-physical system that manipulates silicon wafers with extreme accuracy at high throughput. Typical control applications of the wafer scanner consist of thousands of precedence-constrained tasks with latency requirements. Machines are customized so that precise characteristics of the control applications to be scheduled and the execution platform are only known during machine start-up. This results in large-scale scheduling problems that need to be solved during start-up of the machine under a strict timing constraint on the schedule delivery time. This paper introduces a fast and scalable static-order scheduling approach for applications with stringent latency requirements and a fixed binding on multiprocessor platforms. It uses a heuristic that makes scheduling decisions based on a new metric to find feasible schedules that meet timing requirements as quickly as possible and it is shown to be scalable to very large task graphs. The computation of this metric exploits the binding information of the application. The approach will be incorporated into the ASML's latest generation of wafer scanners.

This paper provides an overview of the architecture for self-organizing, co-operative and robust Building Automation Systems (BAS) proposed by the EC funded FP7 SCUBA1project. We describe the current situation in monitoring and control systems and outline the typical stakeholders involved in the case of building automation systems. We derive seven typical use cases which will be demonstrated and evaluated on pilot sites. From these use cases the project designed an architecture relying on six main modules that realize the design, commissioning and operation of self-organizing, co-operative, robust BAS.

There is a strong push towards smart buildings that aim to achieve comfort, safety and energy efficiency, through building automation systems (BAS) that incorporate multiple subsystems such as heating and air-conditioning, lighting, access control etc. The design, commissioning and operation of BAS is already challenging when handling an individual subsystem; however when introducing co-operation between systems the complexity increases dramatically. Balancing the contradictory requirements of comfort, safety and energy efficiency and coping with the dynamics of constantly changing environmental conditions, usage patterns, user needs etc. is a demanding task. This paper outlines an approach to the systematic engineering of cooperating, adaptive building automation systems, which aims to formalize the engineering approach in the form of an integrated tool chain that supports the building stakeholders to produce site-specific robust and reliable building automation.

Sensor nodes in many Wireless Body Area Network (WBAN) architectures are supposed to deliver sensed data to a gateway node on the body. To satisfy the data delivery requirements, the network needs to adapt itself to the changes in connection status of the body nodes to the gateway. As a prerequisite, Link Quality Estimation (LQE) needs to be done to detect the connection status of the nodes. The quality of links in WBANs is highly time-varying. The LQE technique should be agile to react fast to such link quality dynamics while avoiding frequent fluctuations to reduce the network adaptation overhead. In this paper, we present an empirical study on using different LQE methods for detecting the connection status of body nodes to the gateway in WBANs. A set of experiments using 16 wireless motes deployed on a body are performed to log the behavior of the wireless links. We explore the trade-offs made by each LQE method in terms of agility, stability, and reliability in detecting connection changes by analyzing the experimental data. Moreover, different LQE methods are used in an adaptive multi-hop WBAN mechanism, as a case study, and their impact on the Quality-of-Services (QoS) are investigated.

Dynamic behavior of streaming applications can be effectively modeled by scenario-aware dataflow graphs (SADFs). Many streaming applications must provide timing guarantees (e.g., throughput) to assure their quality-of-service. For instance, a video decoder which is running on a mobile device is expected to deliver a video stream with a specific frame rate. Moreover, the energy consumption of such applications on handheld devices should be as low as possible. This paper proposes a technique to select a suitable multiprocessor DVFS point for each mode (scenario) of a dynamic application described by an SADF. The technique assures strict timing guarantees while minimizing energy consumption. The technique is evaluated by applying it to several streaming applications. It solves the problem faster than the state of the art technique for dataflow graphs. Moreover, the DVFS controller devised using the proposed technique is more compact and reduces energy consumption compared to the controller devised using the counterpart technique.

Synchronous dataflow graphs (SDFGs) are used extensively to model streaming applications. An SDFG can be extended with scheduling decisions, allowing SDFG analysis to obtain properties, such as throughput or buffer sizes for the scheduled graphs. Analysis times depend strongly on the size of the SDFG. SDFGs can be statically scheduled using static-order schedules. The only generally applicable technique to model a static-order schedule in an SDFG is to convert it to a homogeneous SDFG (HSDFG). This may lead to an exponential increase in the size of the graph and to suboptimal analysis results (e.g., for buffer sizes in multiprocessors). We present techniques to model two types of static-order schedules, i.e., periodic schedules and periodic single appearance schedules, directly in an SDFG. Experiments show that both techniques produce more compact graphs compared to the technique that relies on a conversion to an HSDFG. This results in reduced analysis times for performance properties and tighter resource requirements.

Many combinatorial optimization problems in the embedded systems and design automation domains involve decision making in multidimensional spaces. The multidimensional multiple-choice knapsack problem (MMKP) is among the most challenging of the encountered optimization problems. MMKP problem instances appear for example in chip multiprocessor runtime resource management and in global routing of wiring in circuits. Chip multiprocessor resource management requires solving MMKP under real-time constraints, whereas global routing requires scalability of the solution approach to extremely large MMKP instances. This article presents a novel MMKP heuristic, CPH (for Compositional Pareto-algebraic Heuristic), which is a parameterized compositional heuristic based on the principles of Pareto algebra. Compositionality allows incremental computation of solutions. The parameterization allows tuning of the heuristic to the problem at hand. These aspects make CPH a very versatile heuristic. When tuning CPH for computation time, MMKP instances can be solved in real time with better results than the fastest MMKP heuristic so far. When tuning CPH for solution quality, it finds several new solutions for standard benchmarks that are not found by any existing heuristic. CPH furthermore scales to extremely large problem instances. We illustrate and evaluate the use of CPH in both chip multiprocessor resource management and in global routing.

This paper presents a collaborative procedure for multiobjective global routing. Our procedure takes multiple global routing solutions, which are generated independently (e.g., by one router that runs in different modes concurrently or by different routers running in parallel), as input. It then performs multiobjective optimization based on Pareto algebra and quickly generates multiple global routing solutions with a tradeoff between the considered objectives. The user can control the number of generated solutions and the degree of exploring the tradeoff between them by constraining the maximum allowable degradation in each objective. This paper then considers the following three multiobjective case studies: 1) minimization of interconnect power and wirelength; 2) minimization of routing congestion and wirelength; and 3) minimization of wirelength with respect to the (finite-capacity) routing resources. The maximum allowable degradation in wirelength is specified in all cases. Our multiobjective procedure runs in only a few minutes for each of the International Symposium on Physical Design 2008 benchmarks, even the unroutable ones, which imposes a tolerable overhead in the design flow. In our simulations, we demonstrate the effectiveness of our procedure using five modern academic global routers.

Synchronous dataflow graphs (SDFGs) are used extensively to model streaming applications. An SDFG can be extended with scheduling decisions, allowing SDFG analysis to obtain properties like throughput or buffer sizes for the scheduled graphs. Analysis times depend strongly on the size of the SDFG. SDFGs can be statically scheduled using static-order schedules. The only generally applicable technique to model a static-order schedule in an SDFG is to convert it to a homogeneous SDFG (HSDFG). This conversion may lead to an exponential increase in the size of the graph and to sub-optimal analysis results (e.g., for buffer sizes in multi-processors). We present a technique to model periodic static-order schedules directly in an SDFG. Experiments show that our technique produces more compact graphs compared to the technique that relies on a conversion to an HSDFG. This results in reduced analysis times for performance properties and tighter resource requirements.

The two-player mean-payoff game is a well-known game theoretic model that is widely used, for instance in economics and control theory. For controller synthesis, a controller is modeled as a player while the environment, or plant, is modeled as the opponent player (adversary). Synthesizing an optimal controller that satisfies a given criterion corresponds to finding a winning strategy for the controller player. Emerging streaming applications (audio, video, communication, etc.) for embedded systems exhibit both input sensitive and controller sensitive runtime behavior, where the controller's role is runtime management or scheduling. Embedded controllers need to be optimized for dynamic inputs, while guaranteeing throughput constraints. In this paper, we consider this design task for scenario- and resource-aware dataflow graphs that model streaming applications. Scenarios in these models capture classes of dynamic environment behavior. We demonstrate how to model and solve the controller synthesis problem by constructing a winning strategy in a two-player mean payoff throughput game.

Wireless sensor networks are typically operating in a dynamic context where events, such as moving sensor nodes and changing external interference, constantly impact the quality-of-service of the network. We present a distributed feedback control mechanism that actively balances multiple conflicting network-wide quality metrics, such as power consumption and end-to-end packet latency, for a heterogeneous wireless sensor network operating in a dynamic context. Nodes constantly decide if and how to adapt controllable parameters of the entire protocol stack, using sufficient information of the current network state. Using experiments with an actual deployment we show that our controller allows to maintain the required network-wide quality-of-service, with up to 30% less power consumed, compared to the most applicable (re-)configuration approaches.

Scenario-aware dataflow graphs (SADFs) efficiently model dynamic applications. The throughput of an application is an important metric to determine the performance of the system. For example, the number of frames per second output by a video decoder should always stay above a threshold that determines the quality of the system. During design-space exploration (DSE) or run-time management (RTM), numerous throughput calculations have to be performed. Throughput calculations have to be performed as fast as possible. For synchronous dataflow graphs (SDFs), a technique exists that extracts throughput expressions from a parameterized SDF in which the execution time of the tasks (actors) is a function of some parameters. Evaluation of these expressions can be done in a negligible amount of time and provides the throughput for a specific set of parameter values. This technique is not applicable to SADFs. In this paper, we present a technique, based on Max-Plus automata, that finds throughput expressions for a parameterized SADF. Experimental evaluation shows that our technique can be applied to realistic applications. These results also show that our technique is better scalable and faster compared to the available parametric throughput analysis technique for SDFs.

In this paper we address the problem of sink placement for Gossip-based Wireless Sensor Networks (GWSN). Sink placement plays an important role in planning and deployment of sensor networks. It is an efficient means to improve performance and achieve design objectives. Sink deployment requires an optimization strategy to search a space of possible placement options, and a performance evaluation method to assess the quality of different sink placements. The stochastic nature of the gossip protocol makes this task challenging for GWSN. Simulation is the most common way to accurately evaluate gossiping performance; however, the time required to obtain statistically significant results is considerable and limits the scalability of the sink deployment process. We use a fast and accurate performance evaluation technique, which exploits specifics of the sink placement problem and significantly reduces evaluation time. In order to further improve the speed of the sink placement procedure we propose a greedy simulated annealing search heuristic that converges fast to a near-optimal placement. We have performed an extensive set of experiments to evaluate the performance of the proposed sink placement framework.

This paper presents an exact method and a heuristic method for static rate-optimal multiprocessor scheduling of real-time multi rate DSP algorithms represented by synchronous data flow graphs (SDFGs). Through exploring the state-space generated by a self-timed execution (STE) of an SDFG, a static rate-optimal schedule via explicit retiming and implicit unfolding can be found by our exact method. By constraining the number of concurrent firings of actors of an STE, the number of processors used in a schedule can be limited. Using this, we present a heuristic method for processor-constrained rate-optimal scheduling of SDFGs. Both methods do not explicitly convert an SDFG to its equivalent homogenous SDFG. Our experimental results show that the exact method gives a significant improvement compared to the existing methods, our heuristic method further reduces the number of processors used.

Adaptation of the network architecture through on-demand data forwarding is an efficient mechanism to provide robustness against long outages in WBANs. We developed an experimental testbed that provides online observation of the network behavior for different data propagation approaches in WBANs. The demonstration shows how different approaches deal with special challenges in WBANs such as low quality of wireless links, topology variations due to posture changes, and mobility. Moreover, sensor nodes can be configured online to investigate how different protocols react in various situations.

Practical experience reveals the characteristic properties of Wireless Body Area Networks (WBANs), signifying the need for a well-designed communication protocol. High mobility, stringent resource constraints, and low and time-variant quality of wireless links are some of the challenging issues in WBANs. Typical applications further have varying Quality-of-Service requirements and demand reliable and fast data transmission at low energy cost. This paper proposes a simple, robust, and optimized protocol for data propagation in WBANs. A hybrid design approach is proposed that automatically adapts the network topology according to the connectivity status of the network. An on-demand data forwarding mechanism combined with an epidemic data propagation strategy realize a proper data delivery and robustness while minimizing the idle listening and unnecessary data forwarding. Several experiments using wireless sensor nodes deployed on a body reveal how this protocol can automatically adapt the network in different situations. The results confirm the robustness and improved behavior of this protocol in comparison with existing fixed protocol architectures.

Multirate digital signal processing (DSP) algorithms are often modeled with synchronous dataflow graphs (SDFGs). A lower iteration period implies a faster execution of a DSP algorithm. Retiming is a simple but efficient graph transformation technique for performance optimization, which can decrease the iteration period without affecting functionality. In this paper, we deal with two problems: feasible retiming-retiming a SDFG to meet a given iteration period constraint, and optimal retiming-retiming a SDFG to achieve the smallest iteration period. We present a novel algorithm for feasible retiming and based on that one, a new algorithm for optimal retiming, and prove their correctness. Both methods work directly on SDFGs, without explicitly converting them to their equivalent homogeneous SDFGs. Experimental results show that our methods give a significant improvement compared to the earlier methods.

The ever increasing performance gap between processors and memories is one of the biggest performance bottlenecks for computer systems. In this paper, we propose a task scheduling technique that schedules an application, modeled with a task graph, on a multiprocessor system-on chip (MPSoC) that contains a limited on-chip memory. The proposed scheduling technique explores the trade-off between executing tasks in a code-driven (i.e. executing parallel tasks) or data-driven (i.e. executing pipelined tasks) manner to minimize the run-time of the application. Our static scheduler identifies those task sequences in which it is useful to use a code-driven execution and those task sequences that benefit from a data-driven execution. We extend the proposed technique to consider prefetching when choosing a suitable task order. The technique is implemented using an integer linear programming framework. To evaluate the effectiveness of the technique, we use an application from the multimedia domain and a synthetic task graph that is used in related work. Our experimental results show that our scheduler is able to reduce the run-time of an MP3 decoder application by 8% compared to a commonly used heuristic scheduler.

Synchronous dataflow graphs (SDFGs) are widely used to model streaming applications such as signal processing and multimedia applications in embedded systems. Trade-off analysis between performance and resource usage of SDFGs allows designers to explore implementation alternatives of a system while meeting its performance requirements and resource constraints. This type of analysis is computationally very challenging, particularly when resources may be shared among computations. With resource sharing, system scheduling decisions lead to a combinatorial explosion in the number of scheduling alternatives to be explored. We present a new approach to explore the trade-offs in a such systems. It breaks analysis down in iterations of dataflow graph execution and uses a max-plus algebra semantics. The experimental results on a set of realistic benchmark models show that the new iteration-based approach and the traditional time-based analysis approach complement each other. None of the two approaches dominates the other in terms of quality of the analysis results and analysis time. The two approaches combined give the highest quality result.

Pareto analysis is a broadly applicable method to model and analyze tradeoffs in multi-objective optimization problems. The set of Pareto optimal solutions is guaranteed to contain the best solution for any arbitrary cost function or selection procedure. This work introduces a method to explicitly take uncertainty into account during Pareto analysis. A solution is not modeled by a single point in the solution space, but rather by a set of such points. This is useful in settings with much uncertainty, such as during model-based design space exploration for embedded systems. A bounding-box abstraction is introduced as a finite representation of Pareto optimal solutions under uncertainty. It is shown that the set of Pareto optimal solutions in the proposed approach still captures exactly the potentially best solutions for any cost function as well as any way of reducing the amount of uncertainty. During model-based design space exploration, for instance, design and implementation choices that are made during the development process reduce the amount of uncertainty. Steps in such a refinement trajectory can render previously Pareto optimal solutions sub optimal. The presented results provide a way to ensure that early selections in the refinement process remain valid.

Network dynamics, such as mobility and increase in network load, can influence the performance of a Wireless Sensor Network (WSN). In this paper, we introduce a method which exploits design-time knowledge of the application scenario dynamics to construct a proactive run-time reconfiguration approach. The approach anticipates for the impact that predefined dynamic events can have on the performance of the WSN by switching between various modes of operation defined at design-time. A mode defines the values for the controllable parameters of the network protocol stack. Our approach explicitly differentiates between parameters that can be adapted locally, per node, and those that should be considered globally for the whole WSN. Design-time definition of modes results in a very low run-time overhead as we only require detection of the mode to use and a low overhead synchronization to change global parameters. The approach is made robust by using a recovery approach for nodes unaware of their global mode after, for example, (re-)joining the network. Experiments with an office monitoring deployment and extensive simulations of a cow-health monitoring scenario show that our approach can easily be adopted by practical WSN deployments and results in a significant reduction in resource usage, e.g., power consumption in our examples, at a very low run-time overhead cost.

The inherently unreliable communication infrastructure compel WSN protocols to employ error control mechanisms. Traditionally, error control is achieved by a retransmission scheme using acknowledgment mechanisms. WSN architectures are severely resource constrained and the additional energy expense of transmitting error control messages can seriously degrade network lifetime. In this paper, we analyze performance of error control schemes for the case of point-to-multipoint communication. An explicit acknowledgment mechanism may provide for reliable communication, but has two major drawbacks: 1) the over head is significant for small data messages, and 2) in case of asymmetrical communication links, multi-hop dissemination of acknowledgments is required. As an alternative to such explicit acknowledgment schemes we propose the use of probabilistic acknowledgments. In this probabilistic scheme, a sender estimates the probability that a message has been successfully delivered, based on information about the quality of the radio channel. A message is then retransmitted until the probability of successful delivery reaches a defined threshold value. Network capacity available for error control can be distributed prudently among all information items to be disseminated, possibly taking into account different application requirements. We formulate are transmission control strategy which results in minimal latency and maximal message delivery ratio.

In many applications of Wireless Sensor Networks (WSNs), heterogeneity is a common property in terms of different sensor types and different circumstances like node location, link quality, and local node density. In many applications, there are several different sensor types with entirely different Quality-of-Service (QoS) requirements. The requirements may also vary over time according to the application scenario and also due to network dynamics. Different requirements appeal different approaches while forwarding sensed data through a multi-hop communication network. This paper proposes a dynamic priority assignment strategy to be used for data routing in heterogeneous WSNs aiming to fairly propagate information according to its importance and requirements. To cope with heterogeneity and dynamics, nodes in the routing path dynamically compute priorities for individual data items according to the attached QoS requirements. We apply the proposed strategy for a healthcare monitoring application scenario which consists of an ambient network and several mobile clusters of nodes in the form of Wireless Body Area Networks (WBANs). The nodes have very different requirements and WBANs show a high mobility in the network with more stringent demands. The results show a large improvement in the achieved QoS for more demanding information.

Modern embedded multimedia systems process multiple concurrent streams of data processing jobs. Streams often have throughput requirements. These jobs are implemented on a multiprocessor system as a task graph. Tasks communicate data over buffers, where tasks wait on sufficient space in output buffers before producing their data. For cost reasons, jobs share resources. Because jobs can share resources with other jobs that include tasks with date-dependent execution rates, we assume run-time scheduling on shared resources. Budget schedulers are applied, because they guarantee a minimum budget in a maximum replenishment interval. Both the buffer sizes as well as the budgets influence the temporal behaviour of a job. Interestingly, a trade-off exists: a larger buffer size can allow for a smaller budget while still meeting the throughput requirement. This work is the first to address the simultaneous computation of budget and buffer sizes.We solve this non-linear problem by formulating it as a second-order cone program. We present tight approximations to obtain a non-integral second-order cone program that has polynomial complexity. Our experiments confirm the non-linear trade-off between budget and buffer sizes.

Media processing systems often have limited resources and strict performance requirements. An implementation must meet those design constraints while minimizing resource usage and energy consumption. Design-space exploration techniques help system designers to pinpoint bottlenecks in a system for a given configuration. The trade-offs between performance and resources in the design space can guide designers to tailor and tune the system. Many applications in those systems are computationally intensive and can be modeled by a synchronous dataflow graph. We present a bottleneck-analysis-driven technique to explore the design space of those systems automatically and incrementally. The feasibility and efficiency of the technique is demonstrated with experiments on a set of realistic application models ranging from multimedia to digital printing.

The design of new embedded systems is getting more and more complex as more functionality is integrated into these systems. To deal with the design complexity, a predictable design flow is needed. The result should be a system that guarantees that an application can perform its own tasks within strict timing deadlines, independent of other applications running on the system. Synchronous Dataflow Graphs (SDFGs) provide predictability and are often used to model time-constrained streaming applications that are mapped onto a multiprocessor platform. However, the model abstracts from the dynamic application behaviour which may lead to a large overestimation of its resource requirements. We present a design flow that takes the dynamic behaviour of applications into account when mapping them onto a multiprocessor platform. The design flow provides throughput guarantees for each application independent of the other applications while taking into account the available processing capacity, memory and communication bandwidth. The design flow generates a set of mappings that provide a trade-off in their resource usage. This trade-off can be used by a run-time mechanism to adapt the mapping in different use-cases to the available resource. The experimental results show that our design flow reduces the resource requirements of an MPEG-4 decoder by 66% compared to a state-of-the-art design flow based on SDFGs.

Scratchpad memories (SPMs) have become a promising on-chip storage solution for embedded systems from an energy, performance and predictability perspective. The thermal behavior of these types of memories has not been considered in detail. This thermal behavior plays an important role in the reliability of silicon devices and in their static (leakage) power consumption. In this paper, we propose two different techniques to improve the thermal behavior of SPMs. First, we propose a hardware-based, thermal-aware address translation technique that physically distributes memory accesses to consecutive addresses evenly over the whole memory area. Second, we propose a software-based, thermal-aware address generation technique. This technique tries to distribute the variables that are allocated to the SPM in such a way that an even thermal distribution is achieved. The first technique works particularly well for applications with a regular access pattern, whereas the second technique can also improve the behavior of applications with irregular access patterns. The two techniques thus complement each other and work well together. Using the first technique we show that the peak temperature of an SPM in 65nm technology, when running a typical streaming application, is decreased by up-to 10.0°C. Temperature cycling is reduced from up-to 14.8°C to almost zero in comparison with a non-thermal-aware solution. For our benchmark applications with an irregular access pattern, the second technique is able to reduce the peak temperature by up-to 3.5°C. These savings for both techniques are obtained without any performance degradation or extra silicon area.

This work contributes to throughput calculation for real-time multiprocessor applications experiencing dynamic workload variations. We focus on a method to predict the system throughput when processing an arbitrarily long data frame given the meta-characteristics of the workload in that frame. This is useful for different purposes, such as resource allocation or dynamic voltage scaling in embedded systems. An accurate enough analysis is not trivial when two factors are combined: parallelism and dynamic workload variations. In earlier work, two analysis methods showed good accuracy for several application examples, but no comparative experiments were carried out. In this work, we contribute new propositions to the theoretical basis of the previous methods. Based on these propositions, we remove a potential problem in a common subroutine and propose a new analysis method.We compare the methods experimentally. The new method provides a significant reduction of the throughput prediction error, up to 12%.

This paper proposes a framework for (signal) interconnect power optimization at the global routing stage. In a typical design flow, the primary objective of global routing is minimization of wirelength and via consumption. Our framework takes a global routing solution that is optimized for this objective, and quickly generates a new solution that is optimized for signal power, with only a small, controlled degradation in wirelength. Our model of signal power includes layer-dependent fringe and area capacitances of the routes, and their spacing. Our framework is fast compared to the existing global routing procedures, thereby not causing much overhead and fitting well in the design flow to optimize signal power after wirelength minimization. The framework is based on Pareto-algebraic operations and generates multiple global routing solutions to provide a tradeoff between power and wirelength, thereby allowing the user to optimize power with a controlled degradation in wirelength. The generated solution remains free of overflow in routing resource usage. We experiment with large benchmarks from the ISPD 2008 suite and a 45nm technology model. We show on average 19.9% dynamic power saving with at most 3% wirelength degradation using the existing wirelength optimized solutions from the open literature.

Wireless sensor networks (WSNs) are developing into a promising solution for many applications, for example in healthcare. In many scenarios, there is some form of node mobility. The medium access control (MAC) mechanisms should support the expected kind of mobility in the network. Mobility is particularly complicating for contention free MAC protocols like TDMA-based protocols, because they dedicate unique slots to every node in a neighborhood. In scenarios such as body-area networking, some clusters of nodes move together, creating further challenges and opportunities. This paper proposes MCMAC (Mobile Cluster MAC), a TDMA-based MAC protocol to support mobile clusters in WSNs. The proposed protocol does not need adaptation time after movement of clusters. Several optimization mechanisms are proposed to decrease power consumption. Simulation results show that the optimizations decrease power consumption of nodes around 70% without increasing latency of data transmission compared to the non-optimized version.

Single-Rate Data-Flow (SRDF) graphs, also known as Homogeneous Synchronous Data-Flow (HSDF) graphs or Marked Graphs, are often used to model the implementation and do temporal analysis of concurrent DSP and multimedia applications. An important problem in implementing applications expressed as SRDF graphs is the computation of the minimal amount of buffering needed to implement a static periodic schedule (SPS) that is optimal in terms of execution rate, or throughput. Ning and Gao [1] propose a linear-programming-based polynomial algorithm to compute this minimal storage amount, claiming optimality. We show via a counterexample that the proposed algorithm is not optimal. We prove that the problem is, in fact, NP-complete. We give an exact solution, and experimentally evaluate the degree of inaccuracy of the algorithm of Ning and Gao.

editorial Free Access Share on Editorial: Model-driven embedded-system design Editors: Twan Basten Embedded Systems Institute, Netherlands, Eindhoven University of Technology, Netherlands Embedded Systems Institute, Netherlands, Eindhoven University of Technology, NetherlandsView Profile , Rolf Ernst Technische Universität Braunschweig, Germany Technische Universität Braunschweig, GermanyView Profile Authors Info & Claims ACM Transactions on Embedded Computing SystemsVolume 10Issue 2Article No.: 15pp 1–4https://doi.org/10.1145/1880050.1880051Published:07 January 2011Publication History 0citation572DownloadsMetricsTotal Citations0Total Downloads572Last 12 Months10Last 6 weeks4 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 SiteeReaderPDF

Modern embedded systems typically contain chip-multiprocessors (CMPs) and support a variety of applications. Applications may run concurrently and can be started and stopped over time. Each application may typically have multiple feasible configurations, trading off quality aspects (energy consumption, audio-visual quality) with resource usage for various types of resources. Overall system quality needs to be guaranteed and optimized at all times. This leads to the need for a run-time management solution that selects an appropriate system configuration from all the application configurations of active applications. This run-time management problem can be phrased as a multi-dimensional multiple-choice knapsack (MMKP) problem. We present a compositional heuristic to solve MMKP, that due to the compositionality is better suited to CMP run-time management than existing heuristics that are all not compositional. Our heuristic outperforms the best-known heuristic to date. The heuristic is parameterized, leading to the additional advantage that it allows to trade off execution time vs. solution quality, and to bound the time needed to compute a solution. The latter makes it particularly well-suited for resource-constrained embedded platforms.

In the past decade, real-time embedded systems have become much more complex due to the introduction of a lot of new functionality in one application, and due to running multiple applications concurrently. This increases the dynamic nature of today's applications and systems, and tightens the requirements for their constraints in terms of deadlines and energy consumption. State-of-the-art design methodologies try to cope with these novel issues by identifying several most used cases and dealing with them separately, reducing the newly introduced complexity. This article presents a generic and systematic design-time/run-time methodology for handling the dynamic nature of modern embedded systems, which can be utilized by existing design methodologies to increase their efficiency. It is based on the concept of system scenarios , which group system behaviors that are similar from a multidimensional cost perspective—such as resource requirements, delay, and energy consumption—in such a way that the system can be configured to exploit this cost similarity. At design-time, these scenarios are individually optimized. Mechanisms for predicting the current scenario at run-time, and for switching between scenarios, are also derived. This design trajectory is augmented with a run-time calibration mechanism, which allows the system to learn on-the-fly during its execution, and to adapt itself to the current input stimuli, by extending the scenario set, changing the scenario definitions, and both the prediction and switching mechanisms. To show the generality of our methodology, we show how it has been applied on four very different real-life design problems. In all presented case studies, substantial energy reductions were obtained by exploiting scenarios.

Synchronous data flow graphs (SDFGs) have proved to be a very successful tool for modeling, analysis and synthesis of multimedia applications targeted at both single- and multiprocessor platforms. One of the most prominent performance constraints of concurrent real-time applications is throughput. For given actor execution times, throughput can be verified by analyzing the SDFG models of such applications, for instance using maximum cycle mean analysis or state space analysis. In various contexts, such as design space exploration or run-time reconfiguration, many fast throughput computations are required for varying actor execution times. We present methods to compute throughput of an SDFG where actor execution times can be parameters. The throughput of these graphs is obtained in the form of a function of these parameters. Recalculation of throughput is then merely an evaluation of this function for specific parameter values, which is much faster than the standard throughput analysis. We propose three different algorithms for parametric throughput analysis and evaluate these algorithms experimentally, showing the feasibility of the approach and showing that a divide and conquer algorithm performs best.

Multimedia applications usually have throughput constraints. An implementation must meet these constraints, while it minimizes resource usage and energy consumption. The compute intensive kernels of these applications are often specified as cyclo-static or synchronous dataflow graphs. Communication between nodes in these graphs requires storage space which influences throughput. We present an exact technique to chart the Pareto space of throughput and storage trade-offs, which can be used to determine the minimal buffer space needed to execute a graph under a given throughput constraint. The feasibility of the exact technique is demonstrated with experiments on a set of realistic DSP and multimedia applications. To increase scalability of the approach, a fast approximation technique is developed that guarantees both throughput and a, tight, bound on the maximal overestimation of buffer requirements. The approximation technique allows to trade off worst-case overestimation versus run-time.

Embedded multimedia systems often run multiple time-constrained applications simultaneously. These systems use multiprocessor systems-on-chip of which it must be guaranteed that enough resources are available for each application to meet its throughput constraints. This requires a task binding and scheduling mechanism that provides timing guarantees for each application independent of other applications while taking into account the available processor space, memory and communication bandwidth.

Congestion has negative effects on network performance. In this paper, a novel congestion control strategy is presented for networks-on-chip (NoC). For this purpose we introduce a new communication service, congestion-controlled best-effort (CCBE). The load offered to a CCBE connection is controlled based on congestion measurements in the NoC. Link utilization is monitored as a congestion measure, and transported to a model predictive controller (MPC). Guaranteed bandwidth and latency connections in the NoC are used for this, to assure progress of link utilization data in a congested NoC. We also present a simple but effective model for link utilization for the model-based predictions. Experimental results show that the presented strategy is effective and has reaction speeds of several microseconds which is considered acceptable for realtime embedded systems

This paper presents the Pareto calculator, a tool for compositional computation of Pareto points, based on the algebra of Pareto points. The tool is a useful instrument for multidimensional optimisation problems, design-space exploration and development of quality management and control strategies. Implementations and their complexity of the operations of the algebra are discussed. In particular, a generalisation of the well-known divide-and-conquer algorithm was discussed to compute the Pareto points (optimal solutions) from a set of possible configurations, also known as the maximal vector or skyline problem. The generalisation lies in the fact that we allow for partially ordered domains instead of only totally ordered ones. The calculator is available through the following url: http://www.es.ele.tue.nl/pareto

Synchronous data flow graphs (SDFGs) are a very useful means for modeling and analyzing streaming applications. Some performance indicators, such as throughput, have been studied before. Although throughput is a very useful performance indicator for concurrent real-time applications, another important metric is latency. Especially for applications such as video conferencing, telephony and games, latency beyond a certain limit cannot be tolerated. This paper proposes an algorithm to determine the minimal achievable latency, providing an execution scheme for executing an SDFG with this latency. In addition, a heuristic is proposed for optimizing latency under a throughput constraint. Experimental results show that latency computations are efficient despite the theoretical complexity of the problem. Substantial latency improvements are obtained, of 24-54% on average for a synthetic benchmark of 900 models, and up to 37% for a benchmark of six real DSP and multimedia models. The heuristic for minimizing latency under a throughput constraint gives optimal latency and throughput results under a constraint of maximal throughput for all DSP and multimedia models, and for over 95% of the synthetic models.

Programmable multiprocessor systems-on-chip are becoming the preferred implementation platform for embedded streaming applications. This enables using more software components, which leads to large and frequent dynamic variations of data-dependent execution times. In this context, accurate and conservative prediction of execution times helps in maintaining good audio/video quality and reducing energy consumption by dynamic evaluation of the amount of on-chip resources needed by applications. To be effective, multiprocessor systems have to employ the available parallelism. The combination of task-level parallelism and task delay variations makes predicting execution times a very hard problem. So far, under these conditions, no appropriate techniques exist for the conservative prediction of execution times with the required accuracy. In this paper, we present a novel technique for this problem, exploiting the concept of scenario-based prediction, and taking into account the transient and periodic behavior of scenarios and the effect of scenario transitions. In our MPEG-4 shape-decoder case study, we observe no more than 11% average overestimation.

Quality of Service (QoS) support for wireless sensor networks (WSN) is a fairly new topic that is gaining more and more interest. This paper introduces a method for configuring the nodes of a WSN such that application-level QoS constraints are met. This is a complex task, since the search space is typically extremely large. The method is based on a recent algebraic approach to Pareto analysis, that we use to reason about QoS trade-offs. It features an algorithm that keeps the working set of possible configurations small, by analysing parts of the network in a hierarchical fashion, and meanwhile discarding configurations that are inferior to other configurations. Furthermore, we give WSN models for two different applications, in which QoS trade-offs are made explicit. Test results show that the models are accurate and that the method is scalable and thus practically usable for WSN, even with large numbers of nodes.

An increasing computational demand is placed on the image processing capacity of current and future smart cameras. SIMD processor architectures provide an efficient solution because their repetitive structure matches the data-parallel execution pattern inherent in pixel-type processing. But the lack of support for communicating pixel data over variable distances has forced designers to allocate dedicated hardware or FPGAs for compensating lens distortion and other non-linear operations. We propose a hardware extension to SIMD processors that enables dynamic communication. Using detailed area cost models and a high-level simulator we optimize the extension with regard to the number of buses, bus arbitration policies, and local instruction buffer sizes

Multimedia applications usually have throughput constraints. An implementation must meet these constraints, while it minimizes resource usage and energy consumption. The compute intensive kernels of these applications are often specified as Synchronous Dataflow Graphs. Communication between nodes in these graphs requires storage space which influences throughput. We present exact techniques to chart the Pareto space of throughput and storage trade-offs, which can be used to determine the minimal storage space needed to execute a graph under a given throughput constraint. The feasibility of the approach is demonstrated with a number of examples.

Networks-on-chip (NoC) are a scalable interconnect solution for systems on chip and are rapidly becoming reality. Monitoring is a key enabler for debugging or performance analysis and quality-of-service techniques. The NoC design problem and the NoC monitoring problem cannot be treated in isolation. We propose a monitoring-aware NoC design flow able to take into account the monitoring requirements in general. We illustrate our flow with a debug driven monitoring case study of transaction monitoring. By treating the NoC design and monitoring problems in synergy, the area cost of monitoring can be limited to 3-20% in general

Network-on-chip-based multiprocessor systems-on-chip are considered as future embedded systems platforms. One of the steps in mapping an application onto such a parallel platform involves scheduling the communication on the network-on-chip. This paper presents different scheduling strategies that minimize resource usage by exploiting all scheduling freedom offered by networks-on-chip. Our experiments show that resource-utilization is improved when compared to existing techniques

Synchronous data flow graphs (SDFGs) have proven to be suitable for specifying and analyzing streaming applications that run on single- or multi-processor platforms. Streaming applications essentially continue their execution indefinitely. Therefore, one of the key properties of an SDFG is liveness, i.e., whether all parts of the SDFG can run infinitely often. Another elementary requirement is whether an implementation of an SDFG is feasible using a limited amount of memory. In this paper, we study two interpretations of this property, called boundedness and strict boundedness, that were either already introduced in the SDFG literature or studied for other models. A third and new definition is introduced, namely self-timed boundedness, which is very important to SDFGs, because self-timed execution results in the maximal throughput of an SDFG. Necessary and sufficient conditions for liveness in combination with all variants of boundedness are given, as well as algorithms for checking those conditions. As a by-product, we obtain an algorithm to compute the maximal achievable throughput of an SDFG that relaxes the requirement of strong connectedness in earlier work on throughput analysis

SIMD processors are increasingly used in embedded systems for multi-media applications because of their area- and energy-efficiency. Communication between the processing elements (PEs) in an SIMD processor has remained a cause of inefficiency however; the SIMD concept prescribes that all PEs communicate in the same clock cycle. Existing SIMD architectures solve this problem either by multi-hop communication (causing cycle overhead), or by a fully connected communication network (causing area overhead). To solve the communication bottleneck, we propose a reconfigurable SIMD architecture (RC-SIMD) with a set of delay-lines in the instruction bus, distributing the accesses to the communication network over time. We can (re-) configure the size and number of delay-lines, a specific configuration representing a trade-off between the number of clock cycles and the length of a clock period. Reconfiguration time is typically much less than 1% of the execution time of an algorithm, and the extra configuration hardware is less than 2%. Experiments show that our reconfigurable architecture achieves (on average) more than 10% performance improvement over a non-reconfigurable architecture

Networks-on-chip (NoCs) are a scalable interconnects solution to large scale multiprocessor systems on chip and are rapidly becoming reality. As the ratio of embedded cores per I/O pin increases, the run-time observability becomes a bottleneck. Run-time NoC monitoring can alleviate this problem. As NoCs are the result of sophisticated synthesis design flows, monitoring must be taken into account during this process. We present several scalable alternatives for NoC monitoring. The alternatives vary from using physically separated interconnects for user data and monitoring data, to a completely shared single interconnect. For each alternative we evaluate area cost, required design flow modifications, non-intrusiveness and reusability of monitoring resources for application communication traffic. An interesting trade-off is presented showing that what is area efficient requires efforts in modifying the NoC design flow and in achieving non-intrusiveness. All the experiments are done in the context of the /Ethereal NoC and design flow

Data flow models are used for specifying and analysing signal processing and streaming applications. However, traditional data flow models are either not capable of expressing the dynamic aspects of modern streaming applications or they do not support relevant analysis techniques. The dynamism in modern streaming applications often originates from different modes of operation (scenarios) in which data production and consumption rates and/or execution times may differ. This paper introduces a scenario-aware generalisation of the synchronous data flow model, which uses a stochastic approach to model the order in which scenarios occur. The formally defined operational semantics of a scenario-aware data flow model implies a Markov chain, which can be analysed for both long-run average and worst-case performance metrics using existing exhaustive or simulation-based techniques. The potential of using scenario-aware data flow models for performance analysis of modern streaming applications is illustrated with an MPEG-4 decoder example

Modern embedded applications usually have real-time constraints and they have requirements for low energy consumption. At system level, intra-task dynamic voltage scaling (DVS) is one of the most effective techniques for energy reduction. It changes the processor's supply voltage and clock frequency to the lowest level that still allows the real-time constraints to be met. In this paper, we present how intra-task scenarios, which capture correlations between different parts of the application, can be applied on top of existing DVS techniques, making them more effective. Furthermore, we extend our method for automatic discovery of scenarios and adapt it to the DVS requirements. We show that, by augmenting an existing DVS method with scenarios, the average energy consumption of two real-life benchmarks is reduced with 14% to 52%.

Signal processing and multimedia applications are often implemented on resource constrained embedded systems. It is therefore important to find implementations that use as little resources as possible. These applications are frequently specified as synchronous dataflow graphs. Communication between actors of these graphs requires storage capacity. In this paper, we present an exact method to determine the minimum storage capacity required to execute the graph using model-checking techniques. This can be done for different measures of storage capacity. The problem is known to be NP-complete and because of this, existing buffer minimisation techniques are heuristics and hence not exact. Modern model-checking tools are quite efficient and they have been successfully applied to scheduling-related problems. We study the feasibility of this approach with examples.

Modern embedded applications usually have real-time constraints and they are implemented using heterogeneous multiprocessor systems-on-chip. Dimensioning a system requires accurate estimations of the worst-case execution time (WCET). Overestimation leads to over-dimensioning. This paper introduces a method for automatic discovery of scenarios that incorporate correlations between different parts of applications. It is based on the application parameters with a large impact on the execution time. We show on a benchmark that, using scenarios, the estimated WCET may be reduced with 16%.

This extended abstract presents models to derive timing and resource usage numbers for an application when distant, shared memories are used in an important class of future embedded platforms, namely network-on-chip-based multiprocessors.

Predictable, tile-based multiprocessor networks-on-chip are considered as future embedded systems platforms. Each tile contains one or a few processors and local memories. These memories are typically too small to store large data structures (e.g. a video frame). A solution to this is to embed tiles with large memories in the architecture. However, fetching data from these memories is slow because of the large network delays. The delay can be hidden by using prefetching. Our main contributions are models that allow timing analysis to provide guaranteed quality and performance when using remote memories and prefetching. We use two realistic video applications to show that our models can be used in practice to derive a predictable system using large memory tiles and prefetching, and to provide guaranteed real-time performance.

This paper focuses on stream-oriented applications with real-time constraints for on-chip multiprocessors, e.g. video/audio coding. In such an application the same function, e.g. frame decoding, is executed over and over again. In general, the execution time is data-dependent. Thus, at run-time a situation may arise when the execution time exceeds the deadline specified in the real-time constraints and a preventive action should be taken. For stream-oriented applications pipelined execution of the function is very important for achieving the required throughput. An accurate execution time estimation method supporting pipelined execution on a multiprocessor architecture is proposed in this paper

Networks on chip (NoCs) are a scalable interconnect solution for multiprocessor systems on chip. We propose a generic reconfigurable online event-based NoC monitoring service, based on hardware probes attached to NoC components, offering run-time observability of NoC behavior and supporting system-level debugging. We present a probe architecture, its programming model, traffic management strategies, and a cost analysis. We prove feasibility via a prototype implementation for the Æthereal NoC. Two MPEG NoC examples show that the monitoring service area, without advanced optimizations, is 17--24% of the NoC area. Two realistic monitoring examples show that monitoring traffic is several orders of magnitude lower than the 2GB/s/link raw bandwidth.

We lay a foundation for modeling and validation of asynchronous designs in a multi-clock synchronous programming model. This allows us to study properties of globally asynchronous systems using synchronous simulation and model-checking toolkits. Our approach can be summarized as automatic transformation of a design consisting of two asynchronously composed synchronous components into a fully synchronous multi-clock model preserving behavioral equivalence. The ultimate goal of this research is to provide the ability to model and build GALS systems in a fully synchronous design framework and deploy it on an asynchronous network preserving all properties of the system proven in the synchronous framework.

Data flow process networks are a good model of computation for streaming multimedia applications incorporating audio, video and/or graphics streams. Process networks are concurrent processes communicating streams of data through FIFO channels. They can be executed efficiently and determinately on multiprocessor platforms. However, such stream processing applications are becoming more dynamic, often requiring run-time reconfigurations. Moreover, stream processing is not always an application on its own, but may be a component of a larger application. This application, e.g. a game application, may be control oriented and event driven; events may interact with the streaming component and (re)configure it.In order to capture the interaction between reactive and streaming components as well as reconfiguration in dynamic stream processing, we introduce in this paper a formal, operational and compositional semantics of so-called reactive process networks. This operational semantics can serve as the basis for programming models that allow the programming of streaming components interacting with reactive system components and their reconfigurations. It also supports the construction of analysis and synthesis tools for dynamic streaming multimedia applications. It allows the integration of reactive behaviour in process networks as general as Kahn process networks, but it is also suitable for more restricted and efficient classes of process networks.

We consider a dynamic application running on a multiprocessor network-on-chip as a set of independent jobs, each job possibly running on multiple processors. To provide guaranteed quality and performance, the scheduling of jobs, jobs themselves and the hardware must be amenable to timing analysis. For a certain class of applications and multiprocessor architectures, we propose exact timing models that effectively co-model both the computation and communication of a job. The models are based on interprocessor communication (IPC) graphs [4]. Our main contribution is a precise model of network-on-chip communication, including buffer models. We use a JPEG-decoder job as an example to demonstrate that our models can be used in practice to derive upper bounds on the job execution time and to reason about optimal buffer sizes.

We present a concurrency model that allows reasoning about concurrency in executable specifications. The model mainly focuses on data-flow and streaming applications and at task-level concurrency. The aim of the model is to provide insight in concurrency bottlenecks in an application and to provide support for performing implementation independent concurrency optimization.

Due to an increasing need for flexibility, embedded systems embody more and more programmable processors as their core components. Due to silicon area and power considerations, the corresponding instruction sets are often highly encoded to minimize code size for given performance requirements. This has hampered the development of robust optimizing compilers because the resulting irregular instruction set architectures are far from convenient compiler targets. Among other considerations, they introduce an interdependence between the tasks of instruction selection and scheduling. This so-called phase coupling is so strong that, in practice, instruction selection rather than scheduling is responsible for the quality of the schedule, which tends to disappoint. The lack of efficient compilation tools has also severely hampered the design space exploration of code-size efficient instruction sets, and correspondingly, their tuning to the application domain. In this article, we present an approach that reduces the need for explicit instruction selection by transferring constraints implied by the instruction set to static resource constraints. All resulting schedules are then guaranteed to correspond to a valid implementation with given instructions. We also demonstrate the suitability of this model to enable instruction set design (-space exploration) with a simple, well-understood and proven method long used in high-level synthesis (HLS) of ASICs. Experimental results show the efficacy of our approach.

The design of application (-domain) specific instruction-set processors (ASIPs), optimized for code size, has traditionally been accompanied by the necessity to program assembly, at least for the performance critical parts of the application. The highly encoded instruction sets simply lack the orthogonal structure present in e.g. VLIW processors, that allows efficient compilation. This lack of efficient compilation tools has also severely hampered the design space exploration of code-size efficient instruction sets, and correspondingly, their tuning to the application domain. In Zhao et al (Proc. 14th Int. Symp. on System Synthesis, 2001), a practical method is demonstrated to model a broad class of highly encoded instruction sets in terms of virtual resources easily interpreted by classic resource constrained schedulers (such as the popular list-scheduling algorithm), thereby allowing efficient compilation with well understood compilation tools. In this paper we will demonstrate the suitability of this model to also enable instruction set design (-space exploration) with a simple, well-understood and proven method long used in the high-level synthesis (HLS) of ASICs. A small case study proves the practical applicability of the method.

Partial-order reduction is a well-known technique to cope with the state-space-explosion problem in the verification of concurrent systems. Using the hierarchical structure of concurrent systems, we present an enhancement of the partial-order-reduction scheme of G.J. Holzman and D. Peled (1995) and D. Peled (1994). A prototype of the new algorithm has been implemented on top of the verification tool SPIN. The first experimental results are encouraging.

Workflow management technology promises a flexible solution for business-process support facilitating the easy creation of new business processes and modification of existing processes. Unfortunately, today's workflow products have no support for workflow verification. Errors made at design-time are not detected and result in very costly failures at run-time. This paper presents the verification tool Woflan. Woflan analyzes workflow process definitions downloaded from commercial workflow products using state-of-the-art Petri-net-based analysis techniques. This paper describes the functionality of Woflan emphasizing diagnostics to locate the source of a design error. Woflan is evaluated via two case studies, one involving 20 groups of students designing a complex workflow process and one involving an industrial workflow process designed by Staffware Benelux. The results are encouraging and show that Woflan guides the user in finding and correcting errors in the design of workflows.

Designing and implementing a visual debugger for distributed programs is a significant challenge. Distributed applications are often large and frequently exhibit a high degree of complexity. Consequently, a debugger must address problems of complexity and scale in at least two ways. First, appropriate user interfaces should allow a user to manage the vast amount of information typically obtained from distributed executions. Second, the tool itself, in handling this information, should be implemented efficiently, providing a user with reasonable response times for interactive use. Our research efforts, concentrating on these problems, have led to the development of Poet, a tool for the collection and presentation of event-based traces of distributed executions. Poet makes as few assumptions as possible about characteristics that must be possessed by all target environments. Information describing each target environment is placed in configuration files, allowing a single set of Poet executables to be used for all target environments. Comparing Poet's performance to XPVM, the standard visualization tool for PVM executions, reveals that this target-system independence does not impose a performance penalty.