Heterogeneous architectures became a compelling choice for edge processors executing complex DNN workloads, as they provide an ideal blend of openness, customization, energy-efficient heterogeneity, and scalable performance. Compiler optimization for DNNs on heterogeneous System-on-Chip (SoC) architectures however, must navigate complex hardware-software co-design, data movement minimization, aggressive parallelism exploitation, and advanced static/dynamic code transformations to deliver high performance and energy efficiency.This paper presents a novel compiler ecosystem for highly heterogeneous SoCs with multiple back-end targets, spanning from typical CPUs, to programmable RISC-V clusters and up to dedicated and reconfigurable accelerators. It puts together static analysis, optimization, and scheduling infrastructure to overcome the limitations of current state-of-the-art tools for heterogeneous edge AI processors. Our compilation pipeline introduces several innovative features: (1) an automatic end-to-end flow for RISC-V-based platforms, (2) efficient data layout remapping (reducing memory footprint by 35% on average) and recognition of complex ternary reductions for auto-vectorization, (3) code layout adaptation for hardware simplification, (4) a novel MLIR-based RISC-V backend supporting optimized matrix-multiplication micro-kernels that reach 90% of peak performance, (5) periodic scheduling capabilities for layer-fused CNNs, and (6) automated mapping and scheduling onto heterogeneous CGRA templates for advanced parallel kernel execution, delivering 33% higher energy efficiency than the scalar implementation and up to 3.6× higher performance. These advances enable hardware-aware compilation that reduces manual optimization effort, lowers energy consumption through memory and computation optimization, and minimizes memory footprint and data transfers.

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.

Artificial Intelligence (AI) has had a profound impact on our contemporary society, and it is indisputable that it will continue to play a significant role in the future. To further enhance AI experience and performance, a transition from large-scale server applications towards AI-powered edge devices is inevitable. In fact, current projections indicate that the market for Smart Edge Processors (SEPs) will grow beyond 70 Billion USD by 2026 [1]. Such a shift comes with major challenges, as these devices have limited computing and energy resources yet need to be highly performant. Additionally, security mechanisms need to be implemented to protect against diverse attack vectors as attackers now have physical access to the device. Besides cryptographic keys, Intellectual Property (IP), including neural network weights, may also be potential targets. The CONVOLVE [2] project (currently in its intermediate stage) follows a holistic approach to address these challenges and establish the EU in a leading position in embedded, ultra-low-power and secure processors for edge computing. It encompasses novel hardware technologies, end-to-end integrated workflows, and a security-by-design approach. This paper highlights the security aspects of future edge-AI processors by illustrating challenges encountered in CONVOLVE, the solutions we pursue including some early results, and directions for future research.

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.

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.

Dynamic Neural Networks (DyNN) offer the ability to adapt their structure, parameters, or precision dynamically, making them suitable for systems with rapidly changing environmental conditions, such as wireless communication. Traditional uniform quantization, if applied in DyNNs, will result in unnecessary switching power as the precision requirements are different at different environment conditions. To address this issue, we present two main contributions. 1) An offline non-uniform quantization algorithm enabling run-time quantization adaptation while preserving system performance. 2) A low-overhead dynamic data-gating architecture facilitating run-time non-uniform quantization. The proposed algorithm facilitates dynamic data-gating of up to 8-bits for QPSK demodulation parameters with no performance loss in a Digital Video Broadcast (DVB-S.2) receiver simulation. The DyNN architecture with data-gating, synthesized using GF 22-nm FDSOI CMOS technology achieves a 43% total power reduction with a minimal 3% area overhead compared to the architecture without data-gating.

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].

In wireless communication receivers, soft demodulation translates the noisy received symbols into soft decision information, typically in the form of Log Likelihood Ratios (LLR). Of late, Neural Network (NN)-based demodulators show promise, offering improved performance. However, there is a growing concern about the rising complexity in NN based LLR estimation, particularly with denser modulation schemes. This increased complexity leads to higher area and power consumption, posing challenges for efficiency in edge device applications. To address this issue, this paper proposes a novel NN architecture named LLRSymNet, which works by exploiting the symmetries found in the LLR functions of the bits in the received symbols, which stems from the symmetries present in the modulation constellations used for transmission. By doing so, it reduces the computational complexity compared to existing NN-based soft demodulators. Experimental evaluation of LLRSymNet within the DVB-S.2 receiver system demonstrates performance enhancements and achieves complexity reductions of up to 75% for M-PSK and M-APSK modulation schemes, and up to 81% for denser M-QAM modulations, compared to conventional NN architectures.

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.

With the rise of deep learning (DL), our world braces for artificial intelligence (AI) in every edge device, creating an urgent need for edge-AI SoCs. This SoC hardware needs to support high throughput, reliable and secure AI processing at ultra-low power (ULP), with a very short time to market. With its strong legacy in edge solutions and open processing platforms, the EU is well-positioned to become a leader in this SoC market. However, this requires AI edge processing to become at least 100 times more energy-efficient, while offering sufficient flexibility and scalability to deal with AI as a fast-moving target. Since the design space of these complex SoCs is huge, advanced tooling is needed to make their design tractable. The CONVOLVE project (currently in Inital stage) addresses these roadblocks. It takes a holistic approach with innovations at all levels of the design hierarchy. Starting with an overview of SOTA DL processing support and our project methodology, this paper presents 8 important design choices largely impacting the energy efficiency and flexibility of DL hardware. Finding good solutions is key to making smart-edge computing a reality.

This paper addresses one of the directions of the HORIZON EU CONVOLVE project being dependability of smart edge processors based on computation-in-memory and emerging memristor devices such as RRAM. It discusses how how this alternative computing paradigm will change the way we used to do manufacturing test. In addition, it describes how these emerging devices inherently suffering from many non-idealities are calling for new solutions in order to ensure accurate and reliable edge computing. Moreover, the paper also covers the security aspects for future edge processors and shows the challenges and the future directions.

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.

Item does not contain fulltext

Temporal Convolutional Networks (TCNs) involving mono channels as input, have shown superior performance compared to state-of-the-art sequence detection recursive networks in a variety of applications. TCNs leverage the concept of dilated causal convolution for a wider receptive field coverage of input (mono) channels, which requires scaling the delay between input samples in Multiply-Accumulate (MAC) units in different layers. We demonstrate a possible data-flow transformation to convert a dilated convolution to a non-dilated convolution to remove such need for delay scaling while maintaining the same receptive field. The new data-flow transformation allows for hardware units to be shared across all layers with single-delay units between the MAC units. We demonstrate how such data-flow transformation can be easily achieved using generic Finite Impulse Response (FIR) filter modules, simplifying the deployment of TCNs. We validate the predicted savings using Cadence Stratus High-Level Synthesis (HLS). A gesture recognition case study using ultrasound is synthesized achieving 25% savings in both energy and area if the data-flow transformation is applied.

Traditional embedded systems and recent platforms used in emerging computing paradigms (e.g., fog computing) have resource limits and require their applications and services to be dynamically added (i.e., deployed) and removed at run-time. These applications often have non-functional (quality) requirements (e.g., end-to-end latency) which are only satisfied when sufficient resources are allocated to them. Hence, a run-time decision-maker is needed to optimize the deployments, in terms of resource budgets that are allocated to applications. Additionally, computing platforms have become heterogeneous in terms of their resources and the applications they execute. However, the existing deployment solutions are limited to specific resources and services. In this paper, we propose a run-time deployment framework that is more flexible in defining constraints and optimization goals and works with more heterogeneous resources and resource models than existing solutions. The framework is implemented on an embedded platform as a proof of concept.

On the trend of ultrasound-based gesture recognition, this study introduces the concept of time-sequence classification of ultrasonic patterns induced by hand movements on a microphone array. We refer to time-sequence ultrasound echoes as continuous frequency patterns being received in real-time at different steering angles. The ultrasound source is a single tone continuously being emitted from the center of the microphone array. In the interim, the array beamforms and locates an ultrasonic activity (induced echoes) after which a processing pipeline is initiated to extract band-limited frequency features. These beamformed features are organized in a 2D matrix of size 11 × 30 updated every 10ms on which a Temporal Convolutional Network (TCN) outputs continuous classification. Prior to that, the same TCN is trained to classify Doppler shift variability rate. Using this approach, we show that a user can easily achieve 49 gestures at different steering angles by means of sequence detection. To make it simple to users, we define two Doppler shift variability rates; very slow and very fast which the TCN detects 95-99% of the time. Not only a gesture can be performed at different directions but also the length of each performed gesture can be measured. This leverages the diversity of inair ultrasonic gestures allowing more control capabilities. The process is designed under low-resource settings; that is, given the fact that this real-time process is always-on, the power and memory resources should be optimized. The proposed solution needs 6.2 - 10.2 MMACs and a memory footprint of 6KB allowing such gesture recognition system to be hosted by energy- constrained edge devices such as smart-speakers.

Timing properties of applications strongly depend on resources that are allocated to them. Applications often have multiple resource requirements, all of which must be met for them to proceed. Performance analysis of event-based systems has been widely studied in the literature. However, the proposed works consider only one resource requirement for each application task. Additionally, they mainly focus on the rate at which resources serve applications (e.g., power, instructions or bits per second), but another aspect of resources, which is their provided capacity (e.g., energy, memory ranges, FPGA regions), has been ignored. In this work, we propose a mathematical framework to describe the provisioning rate and capacity of various types of resource. Additionally, we consider the simultaneous use of multiple resources. Conservative bounds on response times of events and their backlog are computed. We prove that the bounds are monotone in event arrivals and in required and provided rate and capacity, which enables verification of real-time application performance based on worst-case characterizations. The applicability of our framework is shown in a case study.

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.

( 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.

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.

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.

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%.

Flexible Manufacturing Systems (FMSs) need a scheduler to provide timing instructions for the operations of different products. Previous work has presented heuristics for fixed-order 2-re-entrant scheduling problems; where products visit a re-entrant machine exactly two times for production. We propose an extension to this scheduling model, and an extension to the scheduling heuristic, that allows jobs to move along different flows on re-entrant machines; i.e. jobs can visit the re-entrant machine once or twice. An FMS that requires such variable re-entrance with fixed-order output is a Large Scale Printer (LSP). The scheduling problem in an LSP is modeled as a variable re-entrance flowshop with relative due dates and sequence-dependent setup times, with a fixed order output. We show that out-of-order input of products can be beneficial to the scheduling quality in variable re-entrance scheduling. A fixed re-entrant heuristic is extended such that it orders operations on the re-entrant machine to minimize the completion time of variable re-entrant job sets. The resulting heuristic produces good quality schedules for variable re-entrant job sets without losing schedule quality for fixed re-entrant job sets.

Finite-state machine-based scenario-aware dataflow (FSM-SADF) is a dynamic dataflow model of computation that combines streaming data and finite-state control. For the most part, it preserves the determinism of its underlying synchronous dataflow (SDF) concurrency model and only when necessary introduces the non-deterministic variation in terms of scenarios that are represented by SDF graphs. This puts FSM-SADF in a sweet spot in the trade-off space between expressiveness and analyzability.

Finite-state machine-based scenario-aware dataflow (FSM-SADF) is a dynamic non-deterministic dataflow model of computation that combines streaming data and finite-state control. However, FSM-SADF in its current state cannot be used in applications involving modeling and analysis of systems whose behavior depends on explicit values of timestamp of events. In this work we propose a compositional semantics for FSM-SADF that enables FSM-SADF to be used in modeling and analysis of such systems. We base the semantics of the composition on standard composition of processes with conditional rendezvous communication at the control level and the compositions of SDF graphs at the dataflow level. We evaluate the approach on a case study from the multimedia domain in the context of first come, first served schedulers.

(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.

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.

A number of modeling approaches combining dataflow and finite-state machines (FSMs) have been proposed to capture applications that combine streaming data with finite control. FSM-based scenario-aware dataflow (FSM-SADF) is such an FSM/dataflow hybrid that occupies a sweet spot in the tradeoff between analyzability and expressiveness. However, the model suffers from compactness issues when the number of scenarios increases. This hampers its use in analysis of applications exposing high levels of data-dependent dynamics. In this paper, we address this problem by combining parameterized dataflow with finite control of FSM-SADF. We refer to the generalization as FSM-based parameterized SADF (FSM-πSADF). We introduce the formal semantics of the model, in terms of maxplus algebra and in particular max-plus automata. Thereafter, by leveraging the existing results of FSM-SADF, we propose a worst-case performance analysis framework for FSM-πSADF. We show that by using FSM-πSADF and its analysis framework, one can, unlike with FSM-SADF, compactly capture streaming applications exhibiting high levels of data-dependent dynamics in presence of finite control. Furthermore, we show that for practical models our analysis typically yields tighter bounds on worst-case performance indicators such as throughput and latency than the existing techniques based on conservative FSM-SADF modeling (if such modeling can be applied at all). We evaluate our approach on a realistic case-study from the multimedia domain.

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.

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 design of embedded wireless and multimedia applications requires temporal analysis to verify if real-time constraints such as throughput and latency are met. This paper presents a design-time analytical approach to derive a conservative upper bound to the maximum end-to-end latency of a streaming application. Existing analytical approaches often assume static application models, which cannot cope with the data-dependent execution of dynamic streaming applications. Consequently, they give overly pessimistic upper bounds. In this paper, we use an expressively richer dataflow model of computation as an application model. The model supports adaptive applications that change their graph structure, execution times, and data rates, depending on their mode of operation, or scenario. We first formalize the latency analysis problem in the presence of dynamically switching scenarios. We characterize each scenario with a compact matrix in (max, +) algebra using a symbolic execution of one graph iteration. The resulting matrices are then composed to derive a bound to the end-to-end latency under a periodic source. Aperiodic sources such as sporadic streams can be analyzed by reduction to a periodic reference. We demonstrate the applicability of the technique with dataflow models from the wireless application domain. Moreover, the method is illustrated with a tradeoff analysis in resource reservation under a throughput constraint. The evaluation shows that the approach has a low runtime, which enables it to be effectively integrated in multiprocessor design flows of streaming applications.

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.

Dynamic dataflow models of computation (MoCs) have been introduced to provide designers with enough expressive power to capture increasing levels of dynamism in modern streaming applications. Among dynamic dataflow MoCs, parametrized dataflow MoCs hold an important place as they integrate dynamic parameters and run-time adaptation of parameters in a structured way. In this work, we analyze the temporal behaviour of an important class of parametrized dataflow MoCs based on synchronous dataflow (SDF). We refer to such models as SDF-based parametrized dataflow (SDF-PDF). We show that our analysis allows to derive tighter worst-case throughput guarantees than the existing techniques. To achieve this, we introduce the (max,+) algebraic semantics of the model. Thereafter, we model run-time parameter adaptation using the theory of (max,+) automata, where the maximum cycle mean (MCM) analysis of the (max,+) automaton structure immediately yields the worst-case throughput value. We evaluate our approach on a representative case study from the multimedia domain.

The FSM-based scenario-aware data ow (FSM-SADF) model of computation has been introduced to facilitate the analysis of dynamic streaming applications. FSM-SADF interprets application's execution as an execution of a sequence of static modes of operation called scenarios. Each scenario is modeled using a synchronous data ow (SDF) graph (SDFG), while a finite-state machine (FSM) is used to encode scenario occurrence patterns. However, FSM-SADF can precisely capture only those dynamic applications whose behaviors can be abstracted into a reasonably sized set of scenarios (coarse-grained dynamism). Nevertheless, in many cases, the application may exhibit thousands or even millions of behaviours (fine-grained dynamism). In this work, we generalize the concept of FSM-SADF to one that is able to model dynamic applications exhibiting fine-grained dynamism. We achieve this by applying parametrization to the FSM-SADF's base model, i.e. SDF, and defining scenarios over parametrized SDFGs. We refer to the extension as parametrized FSM-SADF (PFSM-SADF). Thereafter, we present a novel and a fully parametric analysis technique that allows us to derive tight worst-case performance (throughput and latency) guarantees for PFSM-SADF specifications. We evaluate our approach on a realistic case-study from the multimedia domain.

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.

Embedded streaming applications require design-time temporal analysis to verify real-time constraints such as throughput and latency. In this paper, we introduce a new analytical technique to compute temporal bounds of streaming applications mapped onto a shared multiprocessor platform. We use an expressively rich application model that supports adaptive applications where graph structure, execution times and data rates may change dynamically. The analysis technique combines symbolic simulation in (max, +) algebra with worst-case resource availability curves. It further enables a tighter performance guarantee by improving the WCRTs of service requests that arrive in the same busy time. Evaluation on real-life application graphs shows that the technique is tens of times faster than the state-of-the-art and enables tighter throughput guarantees, up to a factor of 4, compared to the typical worst-case analysis.

Analyzing worst-case application timing for systems with shared resources is difficult, especially when non-monotonic arbitration policies like First-Come-First-Served (FCFS) scheduling are used in combination with varying task execution times. Analysis methods that conservatively analyze these systems are often based on state-space exploration, which is not scalable due to its inherent susceptibility to combinatorial explosion. We propose a scalable timing analysis method on periodically restarted Directed Acyclic Task Graphs, that can provide conservative bounds on task timing properties when shared resources with FCFS scheduling are used. By expressing task enabling and completion times in intervals, denoting best-case and worst-case timing properties, contention on the shared resources can be estimated using conservative approximations. With an industrial case study we show that our approach can easily analyze models with thousands of tasks in less than 10 seconds, and the worst-case bounds obtained show an average improvement of 46% compared to bounds obtained by static worst-case analysis.

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.

In time-critical systems such as in avionics, for safety and timing guarantees, applications are isolated from each other. Resources are partitioned in time and space creating a partition per application. Such isolation allows fault containment and independent development, testing and verification of applications. Current partitioned systems do not allow dynamically adding applications. Applications are statically loaded in their respective partitions. However dynamic loading can be useful or even necessary for scenarios such as on-board software updates, dynamic reconfiguration or re-loading applications in case of a fault. In this paper we propose a software architecture to dynamically create and manage partitions and a method for compostable dynamic loading which ensures that loading applications do not affect the running applications and vice versa. Furthermore the loading time is also predictable i.e. the loading time can be bounded a priori. We achieve this by splitting the loading process into parts, wherein only a small part which reserves minimum required resources is executed in the system partition and the other parts are executed in the allocated application partition which ensures isolation from other applications. We implement the software architecture for a SoC prototype on an FPGA board and demonstrate its composability and predictability properties.

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.

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.

Hierarchical SDF models are not compositional: a composite SDF actor cannot be represented as an atomic SDF actor without loss of information that can lead to rate inconsistency or deadlock. Motivated by the need for incremental and modular code generation from hierarchical SDF models, we introduce in this paper DSSF profiles. DSSF (Deterministic SDF with Shared FIFOs) forms a compositional abstraction of composite actors that can be used for modular compilation. We provide algorithms for automatic synthesis of non-monolithic DSSF profiles of composite actors given DSSF profiles of their sub-actors. We show how different trade-offs can be explored when synthesizing such profiles, in terms of compactness (keeping the size of the generated DSSF profile small) versus reusability (maintaining necessary information to preserve rate consistency and deadlock-absence) as well as algorithmic complexity. We show that our method guarantees maximal reusability and report on a prototype implementation.

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.

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.

Programming embedded and cyber-physical systems requires attention not only to functional behavior and correctness, but also to non-functional aspects and specifically timing and performance. A structured, compositional, model-based approach based on stepwise refinement and abstraction techniques can support the development process, increase its quality and reduce development time through automation of synthesis, analysis or verification. Toward this, we introduce a theory of timed actors whose notion of refinement is based on the principle of worst-case design that permeates the world of performance-critical systems. This is in contrast with the classical behavioral and functional refinements based on restricting sets of behaviors. Our refinement allows time-deterministic abstractions to be made of time-non-deterministic systems, improving efficiency and reducing complexity of formal analysis. We show how our theory relates to, and can be used to reconcile existing time and performance models and their established theories.

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%.

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.

The Synchronous Dataflow (SDF) model of computation by Lee and Messerschmitt has become popular for modeling concurrent applications on a multiprocessor platform. It is used to obtain a guaranteed, predictable performance. The model, on the other hand, is quite restrictive in its expressivity, making it less applicable to many modern, more dynamic applications. A common technique to deal with dynamic behavior is to consider different scenarios in separation. This analysis is, however, currently limited mainly to sequential applications. In this article, we present a new analysis approach that allows analysis of synchronous dataflow models across different scenarios of operation. The dataflow graphs corresponding to the different scenarios can be completely different. Execution times, consumption and production rates and the structure of the SDF may change. Our technique allows to derive or prove worst-case performance guarantees of the resulting model and as such extends the model-driven approach to designing predictable systems to significantly more dynamic applications and platforms. The approach is illustrated with three MP3 and MPEG-4 related case studies.

The Synchronous Dataflow (SDF) model of computation is popular for modelling the timing behaviour of real-time embedded hardware and software systems and applications. It is an essential ingredient of several automated design-flows and design-space exploration tools. The model can be analysed for throughput and latency properties. Although the SDF model is fairly simple, the analysis algorithms are often of high complexity and the models that need to be analysed may be fairly large. This paper introduces two graph transformations for reducing large SDF graphs into simpler, smaller ones that can be analysed more efficiently and give a conservative and often tight estimation of the timing of the original model and hence of the hard real-time system. We can make SDF based methods more efficient and prove that analyses that were done manually in an ad-hoc fashion in the past, can be done automatically and with guaranteed correctness. Additionally we introduce a novel conversion from SDF to Homogeneous SDF, a step applied in many analysis methods for SDF, which yields an up to 250X improvement on the number of actors, thus mitigating the problems with the size explosion observed in the traditional conversion.

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.

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.

Synchronous data flow (SDF) graphs have a simple and elegant semantics (essentially linear algebra) which makes SDF graphs eminently suitable as a vehicle for studying scheduling optimisations. We extend related work on using SPIN to experiment with scheduling optimisations aimed at minimising buffer requirements. We show that for a benchmark of commonly used case studies the performance of our SPIN based scheduler is comparable to that of state of the art research tools. The key to success is using the semantics of SDF to prove when using (even unsound and/or incomplete) optimisations are justified. The main benefit of our approach lies in gaining deep insight in the optimisations at relatively low cost.

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.

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.

The complexity of designing hardware/software systems motivates research on frameworks that structure and automate the design process. Such design methodologies reduce the risk of expensive design-implementation iterations by assisting designers in constructing models. Software/hardware engineering (SHE) is a general-purpose system-level design methodology that supports analysing both functional correctness and performance properties. SHE combines the Unified Modelling Language with the parallel object-oriented specification language to specify models. The designer is assisted in constructing models using these languages and applying the analysis techniques with various guidelines and modelling patterns. A key feature of SHE is its foundation on formal methods, which ensures that the obtained analysis results are unambiguous. SHE also includes guidelines and techniques for automatic synthesis of real-time control software. This is again based on formal methods to ensure that properties in a model (including real-time properties) are preserved by the software realisation. Finally, to enable an effective and efficient application of the modelling languages as well as the analysis and synthesis techniques, SHE is accompanied with a set of user-friendly tools. This paper gives an overview of SHE, thereby briefly touching upon the underlying mathematical foundation of the analysis and synthesis techniques as well as upon some open issues that require further research.

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.

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.

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

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

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.

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.

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.

Formal techniques have been widely applied in the design of real-time systems and have significantly helped detect design errors by checking real-time properties of the model. However, a model is only an approximation of its realization in terms of the issuing time of events. Therefore, a real-time property verified in the model can not always be directly transferred to the realization. In this paper, both the model and the realization are viewed as sets of timed state sequences. In this context, we first investigate the real-time property preservation between two neighboring timed state sequences (execution traces of timed systems), and then extend the results to two "neighboring" timed systems. The study of real-time property preservation gives insight in building a formal link between real-time properties satisfied in the model and those in the realization.