This paper presents a control/scheduling co-design framework that integrates 5G Configured Grant (CG) scheduling with networked control systems (NCS) design. The objective is to minimize the hyperperiod induced by multiple, application-specific sampling periods, which determines the schedule table size and memory footprint at the base station, subject to control quality and wireless resource limits. Hyperperiod minimization under control and resource constraints is nontrivial due to the combinatorial nature of discrete sampling period choices. To address this challenge, we propose a two-stage Hyperperiod-Minimization-oriented Period Assignment (HMPA) method. In the first stage, HMPA performs a feasibility-oriented period search within candidate period sets constructed from restricted primes and exponents, which bound the hyperperiod. In the second stage, a hyperperiod refinement procedure exploits remaining resource slack to further reduce the hyperperiod while preserving feasibility. Experiments demonstrate the efficiency of the proposed framework in terms of finding solutions with significantly reduced hyperperiods.

The IEEE European Test Symposium (ETS) has been facilitating progress in electronic systems testing since its launch in 1996. On the occasion of its 30th anniversary, this collaborative paper gathers sections by 21 ETS teams to outline their influential ideas and milestones. Each team’s section highlights historical perspective, current research, frameworks and projects as well as forward-looking research agendas in the area of electronic-based circuits and systems testing, reliability, safety, security and validation. This anniversary summary documents how research of various ETS teams, exemplifying the test community, has been evolving and transitioning from concepts to practical standards and Electronic Design Automation (EDA) tools and flows. This legacy is a strong base to drive the next generation of advances in electronic systems testing.

Contemporary embedded platforms necessitate advanced resource management techniques to effectively utilize their diverse computational resources . Usually these platforms encounter fluctuations in workloads, making workload prediction have the potential to enhance resource management efficiency. In addition, in modern multi-core systems, there is a discernible tendency for processing cores to decrease in size relative to power consumption . This reduction in core size contributes to higher power density within the chips, leading to elevated chip temperatures. Therefore, addressing the temperature issue becomes critical. This paper introduces a prediction-based and temperature-aware resource management heuristic designed to meet task deadlines, while simultaneously considering energy minimization . When evaluated on real-life workload traces, the proposed method achieves a 5.5% increase in acceptance rate with one-step-ahead prediction and an 8.9% increase with four-steps-ahead prediction in a temperature-aware context, compared to scenarios without prediction.

The fifth-generation (5G) technology standard in telecommunications is expected to support ultra-reliable low latency communication to enable real-time applications such as industrial automation and control. 5G configured grant (CG) scheduling features a pre-allocated periodicity-based scheduling approach, which reduces control signaling time and guarantees service quality. Although this enables 5G to support hard real-time periodic traffics, synthesizing the schedule efficiently and achieving high resource efficiency, while serving multiple communications, are still an open problem. In this work, we study the trade-off between scheduling flexibility and control overhead when performing CG scheduling. To address the CG scheduling problem, we first formulate it using satisfiability modulo theories (SMT) so that an SMT solver can be used to generate optimal solutions. To enhance scalability, we propose two heuristic approaches. The first one as the baseline, Co1, follows the basic idea of the 5G CG scheduling scheme that minimizes the control overhead. The second one, CoU, enables increased scheduling flexibility while considering the involved control overhead. The effectiveness and scalability of the proposed techniques and the superiority of CoU compared to Co1 have been evaluated using a large number of generated benchmarks as well as a realistic case study for industrial automation.

5G is expected to support ultra-reliable low latency communication to enable real-time applications such as industrial automation and control. 5G configured grant (CG) scheduling features a pre-allocated periodicity-based scheduling approach which reduces control signaling time and guarantees service quality. Although this enables 5G to support hard real-time periodic traffics, efficiently synthesizing the schedule and achieving high resource efficiency while serving multiple traffics, is still an open problem. To address this problem, we first formulate it using satisfiability modulo theories (SMT) so that an SMT-solver can be used to generate optimal solutions. For enhancing scalability, two efficient heuristic approaches are proposed. The experiments demonstrate the effectiveness and scalability of the proposed technique.

Modern embedded platforms need sophisticated resource managers to utilize their heterogeneous computational resources efficiently. Furthermore, such platforms are subject to fluctuating workloads that are unforeseeable at design time. Predicting the incoming workload could enhance the efficiency of resource management in this situation. But is that the case? And, if so, how substantial is this improvement? Does multiple-step-ahead prediction of the workload contribute to this improvement? How precise must the prediction be to improve decisions rather than cause harm? By proposing a prediction-based resource manager that aims at meeting task deadlines while minimizing energy usage, and by conducting extensive tests, we attempt to provide answers to the aforementioned questions.

Time-Sensitive Networking (TSN) is a set of IEEE 802.1 technologies that support real-time and reliable Ethernet communication, commonly used in automotive and industrial automation systems. Time-aware scheduling is adopted in TSN to achieve high temporal predictability. In this paper, we demonstrate that such a scheduling solution alone does not always meet all timing requirements and must be combined with network preemption support. We propose an SMT-based synthesis method for preemptive time-triggered scheduling and routing in TSN. Our experiments demonstrate that schedulability is improved significantly when using frame preemption compared to a standard time-triggered message scheduling approach.

Graphic processing units (GPUs) are routinely used for general purpose computations to improve performance. To achieve the sought performance gains, care must be invested in fine tuning the way GPU programs interact with the underlying architecture, accounting for the shared memory bank conflicts and the entailed shared memory transactions. Uncovering inputs leading to particular bank conflicts can turn out to be quite hard given the intricacy of the access patterns and their dependence on the inputs. We propose a symbolic execution based framework to systematically uncover shared memory bank conflicts, to propose inputs to realize a given number of shared memory transactions, and to refute the existence of such inputs if the number of shared memory transactions is impossible to achieve during the execution. This allows programmers to more formally reason about the shared memory conflicts and to validate their impact on performance and security. We have implemented our approach and report on our experiments to explore its usefulness towards performance enhancement and quantifying shared memory side-channel leakage in security applications.

Due to their real-time constraints and high predictability requirements, safety-critical automotive applications are often implemented using time-triggered communication scheduling, which is supported in the Time-Sensitive Networking (TSN) standards. Applications and network communications are assigned Automotive Safety Integrity Levels (ASILs) based on the ISO 26262 standard for functional safety in automotive systems. ISO 26262 outlines, for each ASIL, requirements on coverage of random hardware errors and systematic errors. Prior research has addressed routing and scheduling for time-triggered messages in TSN in the context of random hardware errors and optimization of reliability metrics. However, no work to date has considered the functional safety aspects of addressing systematic errors. Specific to systematic errors, the ISO 26262 standard defines ASIL decomposition as a vehicle to decompose functions into independent components, each with a lower safety requirement than that of the original function. Since the cost of a component is increasing with its ASIL, decomposition can lower the total cost while still meeting the original safety requirements. In this paper, we propose an ASIL decomposition based technique to introduce redundant communication with lower-ASIL components in Ethernet systems with TSN-based time-triggered communication. The ASIL-aware routing and scheduling of messages are determined such that all safety requirements and end-to-end deadlines are satisfied and, at the same time, the total cost of the employed switches is minimized. Extensive experiments have been conducted to evaluate the efficiency of the proposed framework.

Time-sensitive Networking (TSN) on Ethernet is a promising communication technology in the automotive and industrial automation industries due to its real-time and high-bandwidth communication capabilities. Time-triggered scheduling and static routing are often adopted in these areas due to high requirements on predictability for safety-critical applications. Deadline-constrained routing and scheduling in TSN have been studied extensively in past research. However, scheduling and routing with reliability requirements in the context of transient faults are not yet studied. In this work, we propose an Satisfiability Modulo Theory-based technique to perform scheduling and routing that takes both reliability constraints and end-to-end deadline constraints into consideration. Heuristics have been applied to improve the scalability of the solution. Extensive experiments have been conducted to demonstrate the efficiency of our proposed technique.

Generating functional tests for processors has been a challenging problem for decades in the very large-scale integration testing field. This paper presents a method that generates software-based self-tests by leveraging bounded model checking (BMC) techniques and targeting, for the first time, out-of-order [out-of-order execution (OOE)] superscalar processors. To combat the state-space explosion associated with BMC, the proposed method starts by combining module-level abstraction-refinement with slicing to reduce the size of the model under verification. Next, an off-the-shelf BMC solver is used on the obtained extended finite-state machines to generate the leading sequences that are necessary to excite internal processor functions. Finally, constrained automatic test-pattern generation is used to cover all structural faults within every function excited by the obtained leading sequences. Experimental results show that the proposed method leads to extremely high fault coverage on the critical components corresponding to OOE operations in functional mode. The method therefore helps in tackling the over-testing problem that is inherent to the full-scan test approach.

Today, it is common knowledge in the cyber-physical systems domain that the tight interaction between the cyber and physical elements provides the possibility of substantially improving the performance of these systems that is otherwise impossible. On the downside, however, this tight interaction with cyber elements makes it easier for an adversary to compromise the safety of the system. This becomes particularly important, since such systems typically are composed of several critical physical components, e.g., adaptive cruise control or engine control that allow deep intervention in the driving of a vehicle. As a result, it is important to ensure not only the reliability of such systems, e.g., in terms of schedulability and stability of control plants, but also resilience to adversarial attacks. In this article, we propose a security-aware methodology for routing and scheduling for control applications in Ethernet networks. The goal is to maximize the resilience of control applications within these networked control systems to malicious interference while guaranteeing the stability of all control plants, despite the stringent resource constraints in such cyber-physical systems. Our experimental evaluations demonstrate that careful optimization of available resources can significantly improve the resilience of these networked control systems to attacks.

Modern real-time embedded and cyber-physical systems comprise a large number of applications, often of different criticalities, executing on the same computing platform. Partitioned scheduling is used to provide temporal isolation among tasks with different criticalities. Isolation is often a requirement, for example, in order to avoid the case when a low criticality task overruns or fails in such a way that causes a failure in a high criticality task. When the number of partitions increases in mixed criticality systems, the size of the schedule table can become extremely large, which becomes a critical bottleneck due to design time and memory constraints of embedded systems. In addition, switching between partitions at runtime causes CPU overhead due to preemption. In this paper, we propose a design framework comprising a hyper-period optimization algorithm, which reduces the size of schedule table and preserves schedulability, and a re-scheduling algorithm to reduce the number of preemptions. Extensive experiments demonstrate the effectiveness of proposed algorithms and design framework.

Modern embedded platforms need sophisticated resource managers in order to utilize the heterogeneous computational resources efficiently. Moreover, such platforms are exposed to fluctuating workloads unpredictable at design time. In such a context, predicting the incoming workload might improve the efficiency of resource management. But is this true? And, if yes, how significant is this improvement? How accurate does the prediction need to be in order to improve decisions instead of doing harm? By proposing a prediction-based resource manager aimed at minimizing energy consumption while meeting task deadlines and by running extensive experiments, we try to answer the above questions.

We present a software approach to address the data latency issue for certain GPU applications. Each application is modeled as a kernel graph, where the nodes represent individual GPU kernels and the edges capture data dependencies. Our technique exploits the GPU L2 cache to accelerate parameter passing between the kernels. The key idea is that, instead of having each kernel process the entire input in one invocation, we subdivide the input into fragments (which fit in the cache) and, ideally, process each fragment in one continuous sequence of kernel invocations. Our proposed technique is oblivious to kernel functionalities and requires minimal source code modification. We demonstrate our technique on a full-fledged image processing application and improve the performance on average by 30% over various settings.

Increasing internet connectivity poses an existential threat for cyber-physical systems. Securing these safety-critical systems becomes an important challenge. Cyber-physical systems often comprise several control applications that are implemented on shared platforms where both high and low criticality tasks execute together (to reduce cost). Such resource sharing may lead to complex timing behaviors and, in turn, counter-intuitive timing anomalies that can be exploited by adversaries to destabilize a critical control system, resulting in irreversible consequences. We introduce the butterfly attack, a new attack scenario against cyber-physical systems that carefully exploits the sensitivity of control applications with respect to the implementation on the underlying execution platforms. We illustrate the possibility of such attacks using two case-studies from the automotive and avionic domains.

We address the problem of statically checking safety properties (such as assertions or deadlocks) for parameterized phaser programs . Phasers embody a non-trivial and modern synchronization construct used to orchestrate executions of parallel tasks. This generic construct supports dynamic parallelism with runtime registrations and deregistrations of spawned tasks. It generalizes many synchronization patterns such as collective and point-to-point schemes. For instance, phasers can enforce barriers or producer-consumer synchronization patterns among all or subsets of the running tasks. We consider in this work programs that may generate arbitrarily many tasks and phasers. We propose an exact procedure that is guaranteed to terminate even in the presence of unbounded phases and arbitrarily many spawned tasks. In addition, we prove undecidability results for several problems on which our procedure cannot be guaranteed to terminate.

Real-time communication over Ethernet is becoming important in various application areas of cyber-physical systems such as industrial automation and control, avionics, and automotive networking. Since such applications are typically time critical, Ethernet technology has been enhanced to support time-driven communication through the IEEE 802.1 TSN standards. The performance and stability of control applications is strongly impacted by the timing of the network communication. Thus, in order to guarantee stability requirements, when synthesizing the communication schedule and routing, it is needed to consider the degree to which control applications can tolerate message delays and jitters. In this paper we jointly solve the message scheduling and routing problem for networked cyber-physical systems based on the time-triggered Ethernet TSN standards. Moreover, we consider this communication synthesis problem in the context of control applications and guarantee their worst-case stability, taking explicitly into consideration the impact of communication delay and jitter on control quality. Considering the inherent complexity of the network communication synthesis problem, we also propose new heuristics to improve synthesis efficiency without any major loss of quality. Experiments demonstrate the effectiveness of the proposed solutions.

Understanding the execution time is critical for embedded, real-time applications. Worst-case execution time (WCET) is an important metric to check the real-time constraints imposed on embedded applications. For complex execution platforms, such as graphics processing units (GPUs), analysis of WCET imposes great challenges due to the complex characteristics of GPU architecture as well as GPU program semantics. In this paper, we propose GDivAn, a measurement-based WCET analysis tool for arbitrary GPU kernels. GDivAn systematically combines the strength of symbolic execution (SE) and genetic algorithm (GA) to maintain both the scalability and the effectiveness of the analysis process. Our evaluation with several open-source GPU kernels reveals the efficiency of GDivAn.

Today, security can no longer be treated as a secondary issue in embedded and cyber-physical systems. Therefore, one of the main challenges in these domains is the design of secure embedded systems under stringent resource constraints and real-time requirements. However, there exists an inherent trade-off between the security protection provided and the amount of resources allocated for this purpose. That is, the more the amount of resources used for security, the higher the security, but the fewer the number of applications which can be run on the platform and meet their timing requirements. This trade-off is of high importance since embedded systems are often highly resource constrained. In this paper, we propose an efficient solution to maximize confidentiality, while also guaranteeing the timing requirements of real-time applications on shared platforms.

This large volume of special issue includes all regular papers presented at Embedded Systems Week (ESWEEK) 2018 that brings together three leading conferences (CASES, CODES+ISSS, and EMSOFT) in the embedded systems area. ESWEEK is a unique premier event that covers all aspects of embedded systems design and hardware/software architectures. ESWEEK presents a wide range of topics unveiling state-of-the-art techniques as can be found in this special issue. Following the journal-integrated publication model started last year, the three conferences conducted the journal-like two-stage peer-reviewed process before final decision. Acceptance rates have been about 25.5% for all conferences with a total number of 270 submissions to the journal track.

Embedded Systems Week (ESWEEK) is the premier event covering major aspects of hardware and software in the design and architecture of embedded and cyber-physical systems.It brings together three leading conferences (CASES, CODES+ISSS, and EMSOFT), two symposia (ESTIMedia and RSP), workshops, and tutorials.With 363 registered attendees, ESWEEK 2016 was well attended, showing the large interest in the field.ESWEEK 2016 was held in Pittsburgh October 2-7, following the tradition of ESWEEK to rotate between Europe, America, and Asia.At the core of ESWEEK, from Monday to Wednesday, are the three conferences CASES, Codes+ISSS, and EMSOFT, which received 63 technical paper submissions (acceptance ratio 29%), 80 (26%), and 98 (26%), respectively.In addition to the technical paper sessions, special sessions continued to be an important part of the conferences, as experts gave overviews of the newest embedded systems trends.New in 2016 was a focus on the Internet of Things (IoT): The IoT Day (part of Codes+ISSS) presented newest trends in IoT as a mix of technical papers, special sessions, and invited speakers from an embedded-systems point of view.For the first time, the review process of the conferences was conducted in a journal-like, two-stage, peer-reviewed process, with the opportunity for minor/major revision before final decision.This step was in preparation for ESWEEK to move to a journal-integrated publication model starting with 2017.Highlights of ESWEEK were the three keynote presentations: The Monday keynote by Prof. Srini Devadas from MIT emphasized the importance of Secure Hardware Platforms for the IoT.The Tuesday keynote by Louis K. Scheffer from the Howard Hughes Medical Institute presented new paradigms for how to design software and hardware in Learning from Life.Finally, the Wednesday keynote by Kaushik Roy from Purdue University presented the newest trends in approximate computing, a new paradigm that promises to increase computing efficiency.Out of the 241 received technical papers, nine outstanding contributions have been nominated as Best Paper Candidates.Finally, the best paper committees selected the best paper for each conference.The authors of eight papers nominated as Best Paper Candidates for the three ESWEEK conferences have submitted extended versions of their work to this special issue.We have three papers from CASES ("CaffePresso: Accelerating Convolutional Networks on Embedded SoCs," winner of the Best Paper Award; "LOCUS: Low-Power Customizable Many-Core Architecture for Wearables"; and "D-PUF: An Intrinsically Reconfigurable DRAM PUF for Device Authentication and Random Number Generation"), two papers from CODES+ISSS ("Improving Write Performance and Extending Endurance of Object-Based NAND Flash Devices," winner of the Best Paper Award; and "Fault Injection for Test-Driven Development of Robust SoC Firmware"), and three papers from EMSOFT ("Underminer: A Framework for Identifying Nonconverging Behaviors in Black Box System Models," winner of the Best Paper Award; "Simulation-Driven Reachability Using Matrix Measures"; and "Predictable Shared Cache Management for Multicore Real-Time Virtualization").The CASES papers address three extremely relevant application areas of current and future embedded systems: machine learning, Internet of Things, and support for security.The first paper,

In response to the tremendous growth of the Internet, towards what we call the Internet of Things (IoT), there is a need to move from costly, high-time-to-market specific-purpose hardware to flexible, low-time-to-market general-purpose devices for packet processing. Among several such devices, GPUs have attracted attention in the past, mainly because the high computing demand of packet processing applications can, potentially, be satisfied by these throughput-oriented machines. However, another important aspect of such applications is the packet latency which, if not handled carefully, will overshadow the throughput benefits. Unfortunately, until now, this aspect has been mostly ignored. To address this issue, we propose a method that considers the variable bit rate of the traffic and, depending on the current rate, minimizes the latency, while meeting the rate demand. We propose a persistent kernel based software architecture to overcome the challenges inherent in GPU implementation like kernel invocation overhead, CPU-GPU communication and memory access overhead. We have chosen packet classification as the packet processing application to demonstrate our technique. Using the proposed approach, we are able to reduce the packet latency on average by a factor of 3.5, compared to the state-of-the-art solutions, without any packet drop.

Platforms that are based on heterogeneous architectures require an intelligent resource manager. An intelligent resource manager should be able to accurately predict the future workload of the system at hand and take it into consideration. In this paper, we show that there exist patterns in the interarrival times of resource requests, and that these patterns can be used for modeling and prediction of the future arrivals. To this end, we develop a two-phase machine-learning-based framework and apply it to real data. First, in the offline phase of our framework, the interarrival times are clustered based on a number of extracted features, and then an adequate modeling and prediction method is selected for each detected cluster. It is shown that, due to the intricate and varied nature of interarrival times, a universal modeling and prediction method does not provide optimal results, and a customized method should be applied to each of the detected clusters. Second, in the runtime phase of our framework, the results provided from the offline phase are used to perform computationally cheap prediction. The experimental results show that our approach has a prediction error below 12% and provides an error reduction of more than 17% in comparison with a straightforward method.

We address the problem of statically checking control state reachability (as in possibility of assertion violations, race conditions or runtime errors) and plain reachability (as in deadlock-freedom) of phaser programs. Phasers are a modern non-trivial synchronization construct that supports dynamic parallelism with runtime registration and deregistration of spawned tasks. They allow for collective and point-to-point synchronizations. For instance, phasers can enforce barriers or producer-consumer synchronization schemes among all or subsets of the running tasks. Implementations are found in modern languages such as Habanero Java. Phasers essentially associate phases to individual tasks and use their runtime values to restrict possible concurrent executions. Unbounded phases may result in infinite transition systems even in the case of programs only creating finite numbers of tasks and phasers. We introduce an exact gap-order based procedure that always terminates when checking control reachability for programs generating bounded numbers of coexisting tasks and phasers. We also show verifying plain reachability is undecidable even for programs generating few tasks and phasers. We then explain how to turn our procedure into a sound analysis for checking plain reachability (including deadlock freedom). We report on preliminary experiments with our open source tool.

We present a framework for system-level analysis of electronic systems whose runtime behaviors depend on uncertain parameters. The proposed approach thrives on hierarchical interpolation guided by an advanced adaptation strategy, which makes the framework general and suitable for studying various metrics that are of interest to the designer. Examples of such metrics include the end-to-end delay, total energy consumption, and maximum temperature of the system under consideration. The framework delivers a light generative representation that allows for a straightforward, computationally efficient calculation of the probability distribution and accompanying statistics of the metric at hand. Our technique is illustrated by considering a number of uncertainty-quantification problems and comparing the corresponding results with exhaustive simulations.

Embedded systems (ESs) have been widely used in various application domains. It is very important to design ESs that guarantee functional correctness of the system under strict timing constraints. Such systems are known as the real-time embedded systems (RTESs). More recently, RTESs started to be utilized in safety and reliability critical areas, which made the overlooked security issues, especially confidentiality of the communication, a serious problem. Differential power analysis attacks (DPAs) pose serious threats to confidentiality protection mechanisms, i.e., implementations of cryptographic algorithms, on embedded platforms. In this work, we present a scheduling policy, SPARTA, that thwarts DPAs. Theoretical guarantees and preliminary experimental results are presented to demonstrate the efficiency of the SPARTA scheduler.

Today, a considerable portion of embedded systems, e.g., automotive and avionic, comprise several control applications. Guaranteeing the stability of these control applications in embedded systems, or cyber-physical systems, is perhaps the most fundamental requirement while implementing such applications. This is different from the classical hard real-time systems where often the acceptance criterion is meeting the deadline. In other words, in the case of control applications, guaranteeing stability is considered to be a main design goal, which is linked to the amount of delay and jitter a control application can tolerate before instability. This advocates the need for new design and analysis techniques for embedded real-time systems running control applications. In this paper, the analysis and design of such systems considering a server-based resource reservation mechanism are addressed. The benefits of employing servers are manifold: providing a compositional and scalable framework, protection against other tasks' misbehaviors, and systematic bandwidth assignment and co-design. We propose a methodology for designing bandwidth-optimal servers to stabilize control tasks. The pessimism involved in the proposed methodology is both discussed theoretically and evaluated experimentally.

Many modern applications exhibit a dynamic and nonstationary behavior, with certain characteristics in one phase of their execution, which change as the application enters new phases, in a manner unpredictable at design-time. In order to meet the demands of such applications, it is important to have adaptive and self-reconfiguring hardware platforms, coupled with intelligent on-line optimization algorithms, that together can adjust to the run-time requirements. Partially dynamically reconfigurable field programmable gate array architectures offer both high performance and flexibility. Despite these potential advantages, the challenges faced by designers trying to set-up a functioning system are still significant, mainly because of the still immature design tools and limited device drivers. We propose a complete framework, based on Xilinx's commercial design suite, that enables an application designer to leverage the advantages of partial dynamic reconfiguration with minimal effort. Our IP-based architecture, together with the comprehensive application programming interface, can be employed to accelerate an application by dynamically scheduling hardware prefetches. Moreover, a piecewise linear predictor is used to capture correlations and predict the hardware modules that will generate the highest performance improvement. Our evaluation comprises of extensive simulations, as well as a complete implementation of the smallest univalue segment assimilating nucleus image processing application on the ML605 board from Xilinx. The measurements show a significant reduction of the expected execution time compared to previous state-of-the-art prefetching algorithms, with only a minor energy overhead.

No abstract available.

Nowadays, embedded systems have been widely used in all types of application areas, some of which belong to the safety and reliability critical domains. The functional correctness and design robustness of the embedded systems involved in such domains are crucial for the safety of personal/enterprise property or even human lives. Thereby, a holistic design procedure that considers all the important design concerns is essential. In this article, we approach embedded systems design from an integral perspective. We consider not only the classic real-time and quality of service requirements, but also the emerging security and power efficiency demands. Modern embedded systems are not any more developed for a fixed purpose, but instead designed for undertaking various processing requests. This leads to the concept of multimode embedded systems, in which the number and nature of active tasks change during runtime. Under dynamic situations, providing high performance along with various design concerns becomes a really difficult problem. Therefore, we propose a novel power-aware secure embedded systems design framework that efficiently solves the problem of runtime quality optimization with security and power constraints. The efficiency of our proposed techniques are evaluated in extensive experiments.

We propose an analytical framework for probabilistic timing analysis of the event-triggered Dynamic segment of the FlexRay communication protocol. Specifically, our framework computes the Deadline Miss Ratio of each message. The core problem is formulated as a Mixed Integer Linear Program (MILP). Given the intractability of the problem, we also propose several techniques that help to mitigate the running times of our tool. This includes the re-engineering of the problem to run it on GPUs as well as reformulating the MILP itself. Most importantly, we also show how our framework can handle correlations between the queuing events of messages. This is challenging because one cannot apply the convolution operator in the same way as in the case of independent queuing events.

In a modern 3D IC, electrical connections between vertically stacked dies are made using through silicon vias. Through silicon vias are subject to undesirable early-life effects such as protrusion as well as void formation and growth. These effects result in opens, resistive opens, and stress induced carrier mobility reduction, and consequently circuit failures. Operating the ICs under extreme temperature cycling can effectively accelerate such early-life failures and make them detectable at the manufacturing test process. An integrated temperature-cycling acceleration and test technique is introduced in this paper that integrates a temperature-cycling acceleration procedure with pre-, mid-, and post-bond tests for 3D ICs. Moreover, it reduces the need for costly temperature chamber based temperature-cycling acceleration procedures. All these result in a reduction in the overall test costs. The proposed method is a schedule-based solution that creates the required temperature cycling effect along with performing the tests. Experimental results demonstrate its efficiency.

In this paper we address the problem of computing the probability response time distribution of periodic tasks scheduled on a uniprocessor systems. Our framework assumes an arbitrary non-idling preemptive scheduling policy that may be either a fixed-priority scheduler (such as Rate Monotonic - RM) or a dynamic-priority scheduler (such as Earliest Deadline First - EDF). At the same time, our framework can handle arbitrary execution time distributions arbitrary deadlines providing numerically accurate results. We also show how the framework can be extended to compute the correlation coefficients between the response times of different jobs by performing the joint analysis.

Different defects may manifest themselves at different temperatures. Therefore, the tests that target such temperature-dependent defects must be applied at different temperatures appropriate for detecting them. Such multi-temperature testing scheme applies tests at different required temperatures. It is known that a test's power dissipation depends on the previously applied test. Therefore, the same set of tests when organized differently dissipates different amounts of power. The technique proposed in this paper organizes the tests efficiently so that the resulted power levels lead to the required temperatures. Consequently a rapid multi-temperature testing is achieved. Experimental studies demonstrate the efficiency of the proposed technique.

Modern mobile devices provide ultra-high resolutions in their display panels. This imposes ever increasing workload on the GPU leading to high power consumption and shortened battery life. In this paper, we first show that resolution scaling leads to significant power savings. Second, we propose a perception-aware adaptive scheme that sets the resolution during game play. We exploit the fact that game players are often willing to trade quality for longer battery life. Our scheme uses decision theory, where the predicted user perception is combined with a novel asymmetric loss function that encodes users' alterations in their willingness to save power.

Control applications are considered to be among the core applications in cyber-physical and embedded realtime systems, for which jitter is typically an important factor. This paper investigates whether it is possible to guarantee certain amount of jitter for a given set of applications on a shared platform. The effect of jitter on the stability of control applications and its relation with the latency will be discussed. The importance arises from the fact that it is considerably easier to manage the constant part of the delay (known as latency), while the process of coping with the varying part of the delay (known as jitter) is more involved. The proposed solution guarantees certain jitter limits, and at the same time does not lead to overly pessimistic latency values. The results are later used in a design optimization problem to minimize the resource utilized.

Today's embedded systems are exposed to variations in resource usage due to complex software applications, hardware platforms, and impact of the runtime environments. When these variations are large and efficiency is required, on-line resource managers may be deployed on the system to help it control its resource usage. An often neglected problem is whether these resource managers are stable, meaning that the resource usage is controlled under all possible scenarios. In distributed systems, this problem is particularly hard because applications distributed over many resources generate complex dependencies between their resources. In this article, we develop a mathematical model of the system, and derive conditions that, if satisfied, guarantee stability.

Large temperature gradients exacerbate various types of defects including early-life failures and delay faults. Efficient detection of these defects requires that burn-in and test for delay faults, respectively, are performed when temperature gradients with proper magnitudes are enforced on an Integrated Circuit (IC). This issue is much more important for 3-D stacked ICs (3-D SICs) compared with 2-D ICs because of the larger temperature gradients in 3-D SICs. In this paper, two methods to efficiently enforce the specified temperature gradients on the IC, for burn-in and delay-fault test, are proposed. The specified temperature gradients are enforced by applying high-power stimuli to the cores of the IC under test through the test access mechanism. Therefore, no external heating mechanism is required. The tests, high power stimuli, and cooling intervals are scheduled together based on temperature simulations so that the desired temperature gradients are rapidly enforced. The schedule generation is guided by functions derived from a set of thermal equations. The experimental results demonstrate the efficiency of the proposed methods.

Electronic system designs that ignore process variation are unreliable and inefficient. In this paper, we propose a system-level framework for the analysis of temperature-induced failures that considers the uncertainty due to process variation. As an intermediate step, we also develop a probabilistic technique for dynamic steady-state temperature analysis. Given an electronic system under a certain workload, our framework delivers the corresponding survival function, founded on the basis of well-established reliability models, with a closed-form stochastic parameterization in terms of the quantities that are uncertain at the design stage. The proposed solution is exemplified considering systems with periodic workloads that suffer from the thermal-cycling fatigue. The analysis of this fatigue is a challenging problem as it requires the availability of detailed temperature profiles, which are uncertain due to the variability of process parameters. To demonstrate the computational efficiency of our framework, we undertake a design-space exploration procedure to minimize the expected energy consumption under a set of timing, thermal, and reliability constraints.

We present a framework for the analysis of process variation across semiconductor wafers. The framework is capable of quantifying the primary parameters affected by process variation, e.g., the effective channel length, which is in contrast with the former techniques wherein only secondary parameters were considered, e.g., the leakage current. Instead of taking direct measurements of the quantity of interest, we employ Bayesian inference to draw conclusions based on indirect observations, e.g., on temperature. The proposed approach has low costs since no deployment of expensive test structures might be needed or only a small subset of the test equipments already deployed for other purposes might need to be activated. The experimental results present an assessment of our framework for a wide range of configurations.

Burn-in is usually carried out with high temperature and elevated voltage. Since some of the early-life failures depend not only on high temperature but also on temperature gradients, simply raising up the temperature of an IC is not sufficient to detect them. This is especially true for 3D stacked ICs, since they have usually very large temperature gradients. The efficient detection of these early-life failures requires that specific temperature gradients are enforced as a part of the burn-in process. This paper presents an efficient method to do so by applying high power stimuli to the cores of the IC under burn-in through the test access mechanism. Therefore, no external heating equipment is required. The scheduling of the heating and cooling intervals to achieve the required temperature gradients is based on thermal simulations and is guided by functions derived from a set of thermal equations. Experimental results demonstrate the efficiency of the proposed method.

Many cyber-physical systems comprise several control applications implemented on a shared platform, for which stability is a fundamental requirement. This is as opposed to the classical hard real-time systems where often the criterion is meeting the deadline. However, the stability of control applications depends on not only the delay experienced, but also the jitter. Therefore, the notion of deadline is considered to be artificial for control applications that promotes the need for new techniques for designing cyber-physical systems. The approach in this paper is built on a server-based resource reservation mechanism, which provides compositionality, isolation, and the opportunity of systematic controller-server co-design. We address the controller-server co-design of such systems to obtain design solutions with the minimal bandwidth to guarantee stability.

Embedded and real-time software is often constrained by several temporal requirements. Therefore, it is important to design embedded software that meets the required performance goal. The inception of embedded graphics processing units (GPUs) brings fresh hope in developing high-performance embedded software which were previously not suitable for embedded platforms. Whereas GPUs use massive parallelism to obtain high throughput, the overall performance of an application running on embedded GPUs is often limited by memory performance. Therefore, a crucial problem lies in automatically detecting the inefficiency of such software developed for embedded GPUs. In this paper, we propose GUPT, a novel test generation framework that systematically explores and detects poor memory performance of applications running on embedded GPUs. In particular, we systematically combine static analysis with dynamic test generation to expose likely execution scenarios with poor memory performance. Each test case in our generated test suite reports a potential memory-performance issue, along with the detailed information to reproduce the same. We have implemented our test generation framework using GPGPU-Sim, a cycle-accurate simulator and the LLVM compiler infrastructure. We have evaluated our framework for several open-source programs. Our experiments suggest the efficacy of our framework by exposing numerous memory-performance issues in a reasonable time. We also show the usage of our framework in improving the performance of programs for embedded GPUs.

Ethernet AVB is being actively considered by the automotive industry as a candidate for in-vehicle communication backbone. However, several questions pertaining to schedulability of hard real-time messages transmitted via such a switch remain unanswered. In this paper, we attempt to fill this void. We derive equations to perform worst-case response time analysis on Ethernet AVB switches by considering its credit-based shaping algorithm. Also, we propose several approaches to reduce the pessimism in the analysis to provide tighter bounds.

Electronic system design based on deterministic techniques for power-temperature analysis is, in the context of current and future technologies, both unreliable and inefficient since the presence of uncertainty, in particular, due to process variation, is disregarded. In this paper, we propose a flexible probabilistic framework targeted at the quantification of the transient power and temperature variations of an electronic system. The framework is capable of modeling diverse probability laws of the underlying uncertain parameters and arbitrary dependencies of the system on such parameters. For the considered system, under a given workload, our technique delivers analytical representations of the corresponding stochastic power and temperature profiles. These representations allow for a computationally efficient estimation of the probability distributions and accompanying quantities of the power and temperature characteristics of the system. The approximation accuracy and computational time of our approach are assessed by a range of comparisons with Monte Carlo simulations, which confirm the efficiency of the proposed technique.

FlexRay has now become a well-established in-vehicle communication bus at most original equipment manufacturers (OEMs) such as BMW, Audi, and GM. Given the increasing cost of verification and the high degree of crosslinking between components in automotive architectures, an incremental design process is commonly followed. In order to incorporate FlexRay-based designs in such a process, the resulting schedules must be extensible , that is: (i) when messages are added in later iterations, they must preserve deadline guarantees of already scheduled messages, and (ii) they must accommodate as many new messages as possible without changes to existing schedules. Apart from extensible scheduling having not received much attention so far, traditional metrics used for quantifying them cannot be trivially adapted to FlexRay schedules. This is because they do not exploit specific properties of the FlexRay protocol. In this article we, for the first time, introduce new notions of extensibility for FlexRay that capture all the protocol-specific properties. In particular, we focus on the dynamic segment of FlexRay and we present a number of metrics to quantify extensible schedules. Based on the introduced metrics, we propose strategies to synthesize extensible schedules and compare the results of different scheduling algorithms. We demonstrate the applicability of the results with industrial-size case studies and also show that the proposed metrics may also be visually represented, thereby allowing for easy interpretation.

Many cyber-physical systems comprise several control applications sharing communication and computation resources. The design of such systems requires special attention due to the complex timing behavior that can lead to poor control quality or even instability. The two main requirements of control applications are: (1) robustness and, in particular, stability and (2) high control quality. Although it is essential to guarantee stability and provide a certain degree of robustness even in the worst-case scenario, a design procedure which merely takes the worst-case scenario into consideration can lead to a poor expected (average-case) control quality, since the design is solely tuned to a scenario that occurs very rarely. On the other hand, considering only the expected quality of control does not necessarily provide robustness and stability in the worst-case. Therefore, both the robustness and the expected control quality should be taken into account in the design process. This paper presents an efficient and integrated approach for designing high-quality cyber-physical systems with robustness guarantees.

In this paper, we approach embedded systems design from a new angle that considers not only quality of service but also security as part of the design process. Moreover, we also take into consideration the dynamic aspect of modern embedded systems in which the number and nature of active tasks are variable during run-time. In this context, providing both high quality of service and guaranteeing the required level of security becomes a difficult problem. Therefore, we propose a novel secure embedded systems design framework that efficiently solves the problem of run-time quality optimization with security constraints. Experiments demonstrate the efficiency of our proposed techniques.

Modern systems demand high performance, as well as high degrees of flexibility and adaptability. Many current applications exhibit a dynamic and nonstationary behavior, having certain characteristics in one phase of their execution, that will change as the applications enter new phases, in a manner unpredictable at design-time. In order to meet the performance requirements of such systems, it is important to have on-line optimization algorithms, coupled with adaptive hardware platforms, that together can adjust to the run-time conditions. We propose an optimization technique that minimizes the expected execution time of an application by dynamically scheduling hardware prefetches. We use a piecewise linear predictor in order to capture correlations and predict the hardware modules to be reached. Experiments show that the proposed algorithm outperforms the previous state-of-art in reducing the expected execution time by up to 27% on average.

We propose an analytical framework for probabilistic timing analysis of the event-triggered Dynamic segment of the Flex Ray communication protocol. Specifically, our framework computes the Deadline Miss Ratios of each message. The core problem is formulated as a Mixed Integer Linear Program (MILP). Given the intractability of the problem, we also propose several techniques that help to mitigate the running times of our tool. This includes the re-engineering of the problem to run it on GPUs as well as re-formulating the MILP itself.

Many embedded systems comprise several controllers sharing available resources. It is well known that such resource sharing leads to complex timing behavior that can jeopardize stability of control applications, if it is not properly taken into account in the design process, e.g., mapping and scheduling. As opposed to hard real-time systems where meeting the deadline is a critical requirement, control applications do not enforce hard deadlines. Therefore, the traditional real-time analysis approaches are not readily applicable to control applications. Rather, in the context of control applications, stability is often the main requirement to be guaranteed, and can be expressed as the amount of delay and jitter a control application can tolerate. The nominal delay and response-time jitter can be regarded as the two main factors which relate the real-time aspects of a system to control performance and stability. Therefore, it is important to analyze the impact of variations in scheduling parameters, i.e., period and priority, on the nominal delay and response-time jitter and, ultimately, on stability. Based on such an analysis, we address, in this paper, priority assignment and sensitivity analysis problems for control applications considering stability as the main requirement.

Guaranteeing stability of control applications in embedded systems, or cyber-physical systems, is perhaps the alpha and omega of implementing such applications. However, as opposed to the classical real-time systems where often the acceptance criterion is meeting the deadline, control applications do not primarily enforce hard deadlines. In the case of control applications, stability is considered to be the main design criterion and can be expressed in terms of the amount of delay and jitter a control application can tolerate before instability. Therefore, new design and analysis techniques are required for embedded control systems. In this paper, the analysis and design of such systems considering server-based resource reservation mechanism are addressed. The benefits of employing servers are manifold: (1) providing a compositional framework, (2) protection against other tasks misbehaviors, and (3) systematic bandwidth assignment. We propose a methodology for designing bandwidth-efficient servers to stabilize control tasks.

This paper presents a high-level automatic test instruction generation (HATIG) technical that allows, for the first time, to test the scheduling unit of an out-of-order super scalar processor. This technique leverages on existing bounded model checking tools in order to generate software-based self-testing programs from a global EFSM model of the processor under test. The experimental results have demonstrated the efficiency of the proposed technique.

In this paper we propose an analytical technique for the steady-state dynamic temperature analysis (SSDTA) of multiprocessor systems with periodic applications. The approach is accurate and, moreover, fast, such that it can be included inside an optimization loop for embedded system design. Using the proposed solution, a temperature-aware reliability optimization, based on the thermal cycling failure mechanism, is presented. The experimental results confirm the quality and speed of our SSDTA technique, compared to the state of the art. They also show that the lifetime of an embedded system can significantly be improved, without sacrificing its energy efficiency, by taking into consideration, during the design stage, the steady-state dynamic temperature profile of the system.

In this paper we consider distributed real-time embedded systems in which confidentiality of the internal communication is critical. We present an approach to efficiently implement cryptographic algorithms by using hardware/software co-design techniques. The objective is to find the minimal hardware overhead and corresponding process mapping for encryption and decryption tasks of the system, so that the confidentiality requirements for the messages transmitted over the internal communication bus are fulfilled, and time constraints are satisfied. Towards this, we formulate the optimization problems using Constraint Logic Programming (CLP), which returns optimal solutions. However, CLP executions are computationally expensive and, hence, efficient heuristics are proposed as an alternative. Extensive experiments demonstrate the efficiency of the proposed heuristic approaches.

Variants of the 0-1 knapsack problem manifest themselves at the core of several system-level optimization problems. The running times of such system-level optimization techniques are adversely affected because the knapsack problem is NP-hard. In this paper, we propose a new GPU-based approach to accelerate the multiple-choice knapsack problem, which is a general version of the 0-1 knapsack problem. Apart from exploiting the parallelism offered by the GPUs, we also employ a variety of GPU-specific optimizations to further accelerate the running times of the knapsack problem. Moreover, our technique is scalable in the sense that even when running large instances of the multiple-choice knapsack problems, we can efficiently utilize the GPU compute resources and memory bandwidth to achieve significant speedups.

In this paper, we propose a design framework for distributed embedded control systems that ensures reliable execution and high quality of control even if some computation nodes fail. When a node fails, the configuration of the underlying distributed system changes and the system must adapt to this new situation by activating tasks at operational nodes. The task mapping as well as schedules and control laws that are customized for the new configuration influence the control quality and must, therefore, be optimized. The number of possible configurations due to faults is exponential in the number of nodes in the system. This design-space complexity leads to unaffordable design time and large memory requirements to store information related to mappings, schedules, and controllers. We demonstrate that it is sufficient to synthesize solutions for a small number of base and minimal configurations to achieve fault tolerance with an inherent minimum level of control quality. We also propose an algorithm to further improve control quality with a priority-based search of the set of configurations and trade-offs between task migration and replication.

FlexRay, developed by a consortium of over hundred automotive companies, is a real-time communication protocol for automotive networks. In this paper, we propose a new approach for timing analysis of the event-triggered component of FlexRay, known as the dynamic segment. Our technique accounts for the fact that the FlexRay standard allows slot multiplexing, i.e., the same priority can be assigned to more than one message. Existing techniques have either ignored slot multiplexing in their analysis or made simplifying assumptions that severely limit achieving high bandwidth utilization. Moreover, we show that our technique returns less pessimistic results compared to previously known techniques even in the case where slot multiplexing is ignored.

Application-specific instruction-set processors (ASIPs) allow the designer to extend the instruction set of the base processor with selected custom instructions to tailor-fit the application. In this paper, with the help of a motivational example, we first demonstrate that different custom instructions are vulnerable to faults with varying probabilities. This shows that by ignoring the vulnerability to faults, traditional methods of instruction set customization can provide no guarantees on the reliability of the system. Apart from such inherent disparity in error vulnerability across custom instructions, each custom instruction can have multiple implementation choices corresponding to varying hardened levels. Hardening reduces the vulnerability to errors but this comes at the overhead of area costs and reduced performance gain. In this paper, we propose a framework to select custom instructions and their respective hardening levels such that reliability is optimized while the performance gain is satisfied and area costs are met as well. Our framework is based on a novel analytical method to compute the overall system reliability based on the probability of failure of individual instructions. Wide range of experiments that were conducted illustrate how our tool navigates the design space to reveal interesting tradeoffs.

Dynamically reconfigurable computing devices have the ability to adapt their hardware to application demands, providing the performance of hardware acceleration, as well as high flexibility, at competitive costs. For these reasons, FPGA-based reconfigurable systems are becoming popular in many application domains, including soft real-time computing. Unfortunately, one of their biggest limitations is the high reconfiguration overhead. One method to overcome this problem is configuration prefetching, which tries to reduce the reconfiguration penalty by preloading modules on the FPGA before they are needed, and overlapping the reconfiguration with useful computation. In this paper we present a speculative approach to context-aware inter-procedural configuration prefetching that provides statistical guarantees by minimizing the alpha-percentile of the execution time distribution of a soft real-time application. Our method uses profile information and takes into account the calling context of a procedure in order to generate better prefetch solutions. We also propose a middleware needed to apply the context-dependent prefetches at run-time. Our experiments show that the developed algorithm outperforms the previous state-of-art.

Many embedded systems comprise several controllers sharing available resources. It is well known that such resource sharing leads to complex timing behavior that degrades the quality of control, and more importantly, can jeopardize stability in the worst-case, if not properly taken into account during design. Although stability of the control applications is absolutely essential, a design flow driven by the worst-case scenario often leads to poor control quality due to the significant amount of pessimism involved and the fact that the worst-case scenario occurs very rarely. On the other hand, designing the system merely based on control quality, determined by the expected (average-case) behavior, does not guarantee the stability of control applications in the worst-case. Therefore, both control quality and worst-case stability have to be considered during the design process, i.e., period assignment, task scheduling, and control-synthesis. In this paper, we present an integrated approach for designing high-quality embedded control systems, while guaranteeing their stability.

Time-redundancy techniques are commonly used in real-time systems to achieve fault tolerance without incurring high energy overhead. However, reliability requirements of hard real-time systems that are used in safety-critical applications are so stringent that time-redundancy techniques are sometimes unable to achieve them. Standby sparing as a hardware-redundancy technique can be used to meet high reliability requirements of safety-critical applications. However, conventional standby-sparing techniques are not suitable for low-energy hard real-time systems as they either impose considerable energy overheads or are not proper for hard timing constraints. In this paper we provide a technique to use standby sparing for hard real-time systems with limited energy budgets. The principal contribution of this paper is an online energy-management technique which is specifically developed for standby-sparing systems that are used in hard real-time applications. This technique operates at runtime and exploits dynamic slacks to reduce the energy consumption while guaranteeing hard deadlines. We compared the low-energy standby-sparing (LESS) system with a low-energy time-redundancy system (from a previous work). The results show that for relaxed time constraints, the LESS system is more reliable and provides about 26% energy saving as compared to the time-redundancy system. For tight deadlines when the time-redundancy system is not sufficiently reliable (for safety-critical application), the LESS system preserves its reliability but with about 49% more energy consumption.

No abstract available.

In this article, we propose a strategy for the synthesis of fault-tolerant schedules and for the mapping of fault-tolerant applications. Our techniques handle transparency/performance trade-offs and use the fault-occurrence information to reduce the overhead due to fault tolerance. Processes and messages are statically scheduled, and we use process reexecution for recovering from multiple transient faults. We propose a fine-grained transparent recovery, where the property of transparency can be selectively applied to processes and messages. Transparency hides the recovery actions in a selected part of the application so that they do not affect the schedule of other processes and messages. While leading to longer schedules, transparent recovery has the advantage of both improved debuggability and less memory needed to store the fault-tolerant schedules.

Large-scale integration with deep sub-micron technologies has led to high power densities and high chip working temperatures. At the same time, leakage energy has become the dominant energy consumption source of circuits due to reduced threshold voltages. Given the close interdependence between temperature and leakage current, temperature has become a major issue to be considered for power-aware system level design techniques. In this paper, we address the issue of leakage energy optimization through temperature aware idle time distribution (ITD). We first propose an offline ITD technique to optimize leakage energy consumption, where only static idle time is distributed. To account for the dynamic slack, we then propose an online ITD technique where both static and dynamic idle time are considered. To improve the efficiency of our ITD techniques, we also propose an analytical temperature analysis approach which is accurate and, yet, sufficiently fast to be used inside the energy optimization loop.

This paper presents an approach to minimize the average program execution time by optimizing the hardware/software implementation of error detection. We leverage the advantages of partial dynamic reconfiguration of FPGAs in order to speculatively place in hardware those error detection components that will provide the highest reduction of execution time. Our optimization algorithm uses frequency information from a counter-based execution profile of the program. Starting from a control flow graph representation, we build the interval structure and the control dependence graph, which we then use to guide our error detection optimization algorithm.

FlexRay has emerged as the de-facto next generation in-vehicle communication protocol. Messages are scheduled incrementally on FlexRay according to the automotive design paradigm where new applications are added iteratively. On this account, the schedules must be (i) sustainable, i.e., when messages are added in later iterations, they must preserve deadline guarantees of existing messages and (ii) extensible, i.e., they must accommodate future messages without changes to existing schedules. Unfortunately, traditionally used metrics of sustainability and extensibility for timing and schedulability analysis are generic and can not be trivially adapted to FlexRay schedules. This is because of platform-specific properties of FlexRay like being a hybrid paradigm, where both time-triggered and event-triggered segments are used for communication. In this paper, we first introduce new notions of sustainability and extensibility for FlexRay that capture protocol-specific properties and then present novel metrics to quantify sustainable and extensible schedules. We demonstrate the applicability of our results with industrial-size case studies and show that our proposed metrics may be visually represented allowing easy interpretation by system designers in the automotive industry.

In this paper we consider distributed embedded systems in which privacy or confidentiality of the internal communication is critical, and present an approach to optimizing cryptographic algorithms under strict timing constraints. We have developed a technique to search for the best system-affordable cryptographic protection for the messages transmitted over the internal communication bus. Towards this, we formulate the optimization technique in Constraint Logic Programming (CLP), which returns optimal results. However, CLP executions are computationally expensive and hence, we propose an efficient heuristic as an alternative. Extensive experiments demonstrate the efficiency of the proposed heuristic approach.

High temperature and process variation are undesirable effects for modern systems-on-chip. The high temperature is a prominent issue during test and should be taken care of during the test process. Modern SoCs, affected by large process variation, experience rapid and large temperature deviations and, therefore, a traditional static test schedule which is unaware of these deviations will be suboptimal in terms of speed and/or thermal-safety. This paper presents an adaptive test scheduling method which addresses the temperature deviations and acts accordingly in order to improve the test speed and thermal-safety. The proposed method is divided into a computationally intense offline-phase, and a very simple online-phase. In the offline-phase a schedule tree is constructed, and in the online-phase the appropriate path in the schedule tree is traversed, step by step and based on temperature sensor readings. Experiments have demonstrated the efficiency of the proposed method.

Today's embedded systems are exposed to variations in load demand due to complex software applications, hardware platforms, and impact of the run-time environments. When these variations are large, and efficiency is required, on-line resource managers may be deployed on the system to help it control its resource usage. An often neglected problem is whether these resource managers are stable, meaning that the resource usage is controlled under all possible scenarios. In this paper we develop mathematical models for the real-time embedded system and we derive conditions which, if satisfied, lead to stable systems. For the developed system models, we also determine bounds on the worst case response times of tasks.

FlexRay is gaining wide acceptance as the next generation bus protocol for automotive networks. This has led to tremendous research interest in techniques for scheduling signals, which are generated by real-time applications, on the FlexRay bus. Signals are first packed together into frames at the application-level and the frames are then transmitted over the bus. To ensure reliability of frames in the presence of faults, frames must be retransmitted over the bus but this comes at the cost of higher bandwidth utilization. To address this issue, in this paper, we propose a novel frame packing method for FlexRay bus. Our method computes the required number of retransmissions of frames that ensures the specified reliability goal. The proposed frame packing method also ensures that none of the signals violates its deadline and that the desired reliability goal for guaranteeing fault-tolerance is met at the minimum bandwidth cost. Extensive experiments on synthetic as well as a industrial case study demonstrate the benefits of our method.

Optimization techniques for improving the average-case execution time of an application, for which predictability with respect to time is not required, have been investigated for a long time in many different contexts. However, this has traditionally been done without paying attention to the worst-case execution time. For predictable real-time applications, on the other hand, the focus has been solely on worst-case execution time optimization, ignoring how this affects the execution time in the average case. In this paper, we show that having a good average-case delay can be important also for real-time applications for which predictability is required. Furthermore, for real-time applications running on multiprocessor systems-on-chip, we present a technique for optimizing the average case and the worst case simultaneously, allowing for a good average-case execution time while still keeping the worst case as small as possible.

Many embedded control systems are implemented on execution platforms with several computation nodes and communication components. Distributed embedded control systems typically comprise multiple control loops that share the available computation and communication resources of the platform. It is well known that such resource sharing leads to complex delay characteristics that degrade the control quality if not properly taken into account at design time. Scheduling in computation nodes and communication infrastructure, as well as execution periods of the controllers impact the delay characteristics and, consequently, the control quality. In addition, mapping of tasks on computation nodes affect both scheduling of tasks and messages, and the assignment of periods of the control applications. Therefore, control synthesis must be considered during mapping, scheduling, and period assignment in order to achieve high control quality. This paper presents a control-quality optimization approach for integrated mapping, scheduling, period selection, and control synthesis for distributed embedded control systems.

Supply voltage scaling and adaptive body biasing (ABB) are important techniques that help to reduce the energy dissipation of embedded systems. This is achieved by dynamically adjusting the voltage and performance settings according to the application needs. In order to take full advantage of slack that arises from variations in the execution time, it is important to recalculate the voltage (performance) settings during runtime, i.e., online. However, optimal voltage scaling algorithms are computationally expensive, and thus, if used online, significantly hamper the possible energy savings. To overcome the online complexity, we propose a quasi-static voltage scaling (QSVS) scheme, with a constant online time complexity O(1). This allows to increase the exploitable slack as well as to avoid the energy dissipated due to online recalculation of the voltage settings.

Systems on Chip implemented with deep sub micron technologies suffer from two undesirable effects, high power density, thus high temperature, and high process variation, which must be addressed in the test process. This paper presents two temperature-aware scheduling approaches to maximize the test throughput in the presence of inter-chip process variation. The first approach, an off-line technique, improves the test throughput by extending the traditional scheduling method. The second approach, a hybrid one, improves further the test throughput with a chip classification scheme at test time based on the reading of a temperature sensor. Experimental results have demonstrated the efficiency of the proposed methods.

With new technologies, temperature has become a major issue to be considered at system level design. In this paper we propose a temperature aware idle time distribution technique for energy optimization with dynamic voltage scaling (DVS). A temperature analysis approach is also proposed which is accurate and, yet, sufficiently fast to be used inside the optimization loop for idle time distribution and voltage selection.

Recent research has shown that different defects can manifest themselves as failures at different temperature spectra. Therefore, we need multi-temperature testing which applies tests at different temperature levels. In this paper, we discuss the need and problems for testing core-based systems-on-chip at different temperatures. To address the long test time problem for multi-temperature test, we propose a test scheduling technique that generates the shortest test schedules while keeping the cores under test within a temperature interval. Experimental results show the efficiency of the proposed technique.

Today's embedded systems are typically exposed to varying load, due to e.g. changing number of tasks and variable task execution times. At the same time, many of the most frequent real-life applications are not characterized by hard real-time constraints and their design goal is not to satisfy certain hard deadlines in the worst case. Moreover, from the user's perspective, achieving a high level of processor utilization is also not a primary goal. What the user needs, is to exploit the available resources (in our case processor time) such that a high level of quality of service (QoS) is delivered. In this paper we propose efficient run-time approaches, able to distribute the processor bandwidth such that the global QoS produced by a set of applications is maximized, in the context in which the processor demand from individual tasks is continuously varying. Extensive experiments demonstrate the efficiency of the proposed approaches.

Time-triggered periodic control implementations are over provisioned for many execution scenarios in which the states of the controlled plants are close to equilibrium. To address this inefficient use of computation resources, researchers have proposed self-triggered control approaches in which the control task computes its execution deadline at runtime based on the state and dynamical properties of the controlled plant. The potential advantages of this control approach cannot, however, be achieved without adequate online resource-management policies. This paper addresses scheduling of multiple self-triggered control tasks that execute on a uniprocessor platform, where the optimization objective is to find trade-offs between the control performance and CPU usage of all control tasks. Our experimental results show that efficiency in terms of control performance and reduced CPU usage can be achieved with the heuristic proposed in this paper.

FlexRay has been widely accepted as the next generation bus protocol for automotive networks. This has led to tremendous research interest in techniques for scheduling messages on the FlexRay bus, in order to meet the hard real-time deadlines of the automotive applications. However, these techniques do not generate reliable schedules in the sense that they do not provide any performance guarantees in the presence of faults. In this work, we will present a framework for generating fault-tolerant message schedules on the time-triggered (static) segment of the FlexRay bus. We provide formal guarantees that the generated fault-tolerant schedules achieve the reliability goal even in the presence of transient and intermittent faults. Moreover, our technique minimizes the required number of re-transmissions of the messages in order to achieve such fault tolerant schedules, thereby, optimizing the bandwidth utilization. Towards this, we formulate the optimization problem in Constraint Logic Programming (CLP), which returns optimal results. However, this procedure is computationally intensive and hence, we also propose an efficient heuristic. The heuristic guarantees the reliability of the constructed schedules but might be sub-optimal with respect to bandwidth utilization. Extensive experiments run on synthetic test cases and real-life case studies illustrate that the heuristic performs extremely well. The experiments also establish that our heuristic scales significantly better than the CLP formulation.

With new technologies, temperature has become a major issue to be considered at system level design. Without taking temperature aspects into consideration, no approach to energy or/and performance optimization will be sufficiently accurate and efficient. In this paper we propose an on-line temperature aware dynamic voltage and frequency scaling (DVFS) technique which is able to exploit both static and dynamic slack. The approach implies an offline temperature aware optimization step and on-line voltage/frequency settings based on temperature sensor readings. Most importantly, the presented approach is aware of the frequency/temperature dependency, by which important additional energy savings are obtained.

At runtime, an embedded control system can switch between alternative functional modes. In each mode, the system operates by using a schedule and controllers that exploit the available computation and communication resources to optimize the control performance in the running mode. The number of modes is usually exponential in the number of control loops, which means that all controllers and schedules cannot be produced in affordable design-time and stored in memory. This paper addresses synthesis of multi-mode embedded control systems. Our contribution is a method that trades control quality with optimization time, and that efficiently selects the schedules and controllers to be synthesized and stored in memory.

In this paper we propose an approach to the design optimization of fault-tolerant hard real-time embedded systems, which combines hardware and software fault tolerance techniques. We trade-off between selective hardening in hardware and process re-execution in software to provide the required levels of fault tolerance against transient faults with the lowest-possible system costs. We propose a system failure probability (SFP) analysis that connects the hardening level with the maximum number of re-executions in software. We present design optimization heuristics, to select the fault-tolerant architecture and decide process mapping such that the system cost is minimized, deadlines are satisfied, and the reliability requirements are fulfilled.

Many embedded control systems comprise several control loops that are closed over a network of computation nodes. In such systems, complex timing behavior and communication lead to delay and jitter, which both degrade the performance of each control loop and must be considered during the controller synthesis. Also, the control performance should be taken into account during system scheduling. The contribution of this paper is a control-scheduling co-design method that integrates controller design with both static and priority-based scheduling of the tasks and messages, and in which the overall control performance is optimized.

Long test application time and high temperature have become two major issues of system-on-chip (SoC) test. In order to minimize test application times and avoid overheating during tests, we propose a thermal-aware test scheduling technique for core-based SoC in an abort-on-first-fail (AOFF) test environment. The AOFF environment assumes that the test process is terminated as soon as the first fault is detected, which is usually deployed in volume production test. To avoid high temperature, test sets are partitioned into test sub-sequences which are separated by cooling periods. The proposed test scheduling technique utilizes instantaneous thermal simulation results to guide the partitioning of test sets and to determine the lengths of cooling periods. Experimental results have shown that the proposed technique is efficient to minimize the expected test application time while keeping the temperatures of cores under test below the imposed temperature limit.

FlexRay is an automotive communication protocol that combines the comprehensive time-triggered paradigm with an adaptive phase that is more suitable for event-based communication. We study optimization of average response times by assigning priorities and frame identifiers to tasks and messages. Our optimization approach is based on immune genetic algorithms, where in addition to the crossover and mutation operators, we use a vaccination operator that results in considerable improvements in optimization time and quality.

We present an approach to the synthesis of fault-tolerant hard real-time systems for safety-critical applications. We use checkpointing with rollback recovery and active replication for tolerating transient faults. Processes and communications are statically scheduled. Our synthesis approach decides the assignment of fault-tolerance policies to processes, the optimal placement of checkpoints and the mapping of processes to processors such that multiple transient faults are tolerated and the timing constraints of the application are satisfied. We present several design optimization approaches which are able to find fault-tolerant implementations given a limited amount of resources. The developed algorithms are evaluated using extensive experiments, including a real-life example.

Thermal safety has become a major challenge to the testing of systems-on-chip with deep sub-micron technologies. In order to avoid overheating the devices under test while reducing test application times, new techniques are needed. In this paper, we propose a test scheduling technique to minimize the test application time such that the temperatures of individual cores are kept below a given limit. The proposed approach takes into account thermal influences between cores, and thus accurate temperature evolution information of all cores in a system-on-chip is needed for the test scheduling. In order to avoid overheating, we have employed a thermal simulation driven scheduling algorithm, in which instantaneous thermal simulation results are used to guide the partitioning of test sets into test sub-sequences and to determine cooling periods inserted between the partitions. Furthermore, the partitioned test sets for different cores are interleaved such that a cooling period reserved for one core can be utilized for the test-data transportations and test applications for other cores. Experimental results have shown that by using the proposed technique, the test application time is minimized and the temperatures of cores under test are kept below the temperature limit during the entire test process.

This paper proposes a temperature-aware dynamic voltage selection technique for energy minimization and presents a thorough analysis of the parameters that influence the potential gains that can be expected from such a technique, compared to a voltage selection approach that ignores temperature.

This work addresses the issue of design optimization for fault- tolerant hard real-time systems. In particular, our focus is on the handling of transient faults using both checkpointing with rollback recovery and active replication. Fault tolerant schedules are generated based on a conditional process graph representation. The formulated system synthesis approaches decide the assignment of fault-tolerance policies to processes, the optimal placement of checkpoints and the mapping of processes to processors, such that multiple transient faults are tolerated, transparency requirements are considered, and the timing constraints of the application are satisfied.

In this paper we present an approach to the synthesis of fault-tolerant schedules for embedded applications with soft and hard real-time constraints. We are interested to guarantee the deadlines for the hard processes even in the case of faults, while maximizing the overall utility. We use time/utility functions to capture the utility of soft processes. Process re-execution is employed to recover from multiple faults. A single static schedule computed off-line is not fault tolerant and is pessimistic in terms of utility, while a purely online approach, which computes a new schedule every time a process fails or completes, incurs an unacceptable overhead. Thus, we use a quasi-static scheduling strategy, where a set of schedules is synthesized off-line and, at run time, the scheduler will select the right schedule based on the occurrence of faults and the actual execution times of processes. The proposed schedule synthesis heuristics have been evaluated using extensive experiments.

The ever-increasing test data volume for core-based system-on-chip (SOC) integrated circuits is resulting in high test times and excessive tester memory requirements. To reduce both test time and test data volume, we propose a technique for test-architecture optimization and test scheduling that is based on core-level expansion of compressed test patterns. For each wrapped embedded core and its decompressor, we show that the test time does not decrease monotonically with the width of test access mechanism (TAM) at the decompressor input. We optimize the wrapper and decompressor designs for each core, as well as the TAM architecture and the test schedule at the SOC level. Experimental results for SOCs crafted from several industrial cores demonstrate that the proposed method leads to significant reduction in test data volume and test time, especially when compared to a method that does not rely on core-level decompression of patterns.

In this paper, we propose a simulation-based methodology for worst-case response time estimation of distributed real-time systems. Schedulability analysis produces pessimistic upper bounds on process response times. Consequently, such an analysis can lead to overdesigned systems resulting in unnecessarily increased costs. Simulations, if well conducted, can lead to tight lower bounds on worst-case response times, which can be an essential input at design time. Moreover, such a simulation methodology is very important in situations when the running application or the underlying platform is such that no formal timing analysis is available. Another important application of the proposed simulation environment is the validation of formal analysis approaches, by estimating their degree of pessimism. We have performed such an estimation of pessimism for two response-time analysis approaches for distributed embedded systems based on two of the most important automotive communication protocols: CAN and FlexRay.

In this paper we present an approach for scheduling with preemption for fault-tolerant embedded systems composed of soft and hard real-time processes. We are interested to maximize the overall utility for average, most likely to happen, scenarios and to guarantee the deadlines for the hard processes in the worst case scenarios. In many applications, the worst-case execution times of processes can be much longer than their average execution times. Thus, designs for the worst-case can be overly pessimistic, i.e., result in low overall utility. We propose preemption of process executions as a method to generate flexible schedules that maximize the overall utility for the average case while guarantee timing constraints in the worst case. Our scheduling algorithms determine off-line when to preempt and when to resurrect processes. The experimental results show the superiority of our new scheduling approach compared to approaches without preemption.

Both analysis and design optimisation of real-time systems has predominantly concentrated on considering hard real-time constraints. For a large class of applications, however, this is both unrealistic and leads to unnecessarily expensive implementations. This paper addresses the problem of task priority assignment and task mapping in the context of multiprocessor applications with stochastic execution times and in the presence of constraints on the percentage of missed deadlines. We propose a design space exploration strategy together with a fast method for system performance analysis. Experiments emphasize the efficiency of the proposed analysis method and optimisation heuristic in generating high-quality implementations of soft real-time systems with stochastic task execution times and constraints on deadline miss ratios.

The increasing test data volume needed to test core-based system-on-chip contributes to long test application times (TAT) and huge automatic test equipment (ATE) memory requirements. TAT and ATE memory requirement can be reduced by test architecture design, test scheduling, sharing the same tests among several cores, and test data compression. We propose, in contrast to previous work that addresses one or few of the problems, an integrated framework with heuristics for sharing and compression and a constraint logic programming technique for architecture design and test scheduling that minimizes the TAT without violating a given ATE memory constraint. The significance of our approach is demonstrated by experiments with ITC '02 benchmark designs

FlexRay will very likely become the de-facto standard for in-vehicle communications. Its main advantage is the combination of high speed static and dynamic transmission of messages. In the previous work the authors have shown that not only the static but also the dynamic segment can be used for hard-real time communication in a deterministic manner. This paper proposed techniques for optimising the FlexRay bus access mechanism of a distributed system, so that the hard real-time deadlines are met for all the tasks and messages in the system. The authors have evaluated the proposed techniques using extensive experiments

High temperature has become a technological barrier to the testing of high performance systems-on-chip, especially when deep submicron technologies are employed. In order to reduce test time while keeping the temperature of the cores under test within a safe range, thermal-aware test scheduling techniques are required. In this paper, we address the test time minimization problem as how to generate the shortest test schedule such that the temperature limits of individual cores and the limit on the test-bus bandwidth are satisfied. In order to avoid overheating during the test, we partition test sets into shorter test subsequences and add cooling periods in between, such that continuously applying a test sub-sequence will not drive the core temperature going beyond the limit. Further more, based on the test partitioning scheme, we interleave the test sub-sequences from different test sets in such a manner that a cooling period reserved for one core is utilized for the test transportation and application of another core. We have proposed a heuristic to minimize the test application time by exploring alternative test partitioning and interleaving schemes with variable length of test sub-sequences and cooling periods. Experimental results have shown the efficiency of the proposed heuristic.

Today most universities are using course evaluations. However, course evaluations are often discussed and questioned. This paper reports on a survey where we aim at finding out (1) if students have a preconceived notion of a course, (2) if course evaluation scores can be predicted early in a course, (3) if exam throughput impacts course evaluation, and (4) if web-based evaluation reflects the general opinion from students. The results from the study indicate that students do not let preconceived notion impact nor does exam throughput matter to course evaluation. Further, the final web-based results seem to correlate with opinion of students attending lectures. However, the evaluation grades tend to be defined early in the course; hence first impression lasts.

In multiprocessor systems, the traffic on the bus does not solely originate from data transfers due to data dependencies between tasks, but is also affected by memory transfers as result of cache misses. This has a huge impact on worst-case execution time (WCET) analysis and, in general, on the predictability of real-time applications implemented on such systems. As opposed to the WCET analysis performed for a single processor system, where the cache miss penalty is considered constant, in a multiprocessor system each cache miss has a variable penalty, depending on the bus contention. This affects the tasks' WCET which, however, is needed in order to perform system scheduling. At the same time, the WCET depends on the system schedule due to the bus interference. In this paper we present an approach to worst-case execution time analysis and system scheduling for real-time applications implemented on multiprocessor SoC architectures. The emphasis of this paper is on the bus scheduling policy and its optimization, which is of huge importance for the performance of such a predictable multiprocessor application.

Dynamic voltage selection and adaptive body biasing have been shown to reduce dynamic and leakage power consumption effectively. In this paper, we optimally solve the combined supply voltage and body bias selection problem for multiprocessor systems with imposed time constraints, explicitly taking into account the transition overheads implied by changing voltage levels. Both energy and time overheads are considered. The voltage selection technique achieves energy efficiency by simultaneously scaling the supply and body bias voltages in the case of processors and buses with repeaters, while energy efficiency on fat wires is achieved through dynamic voltage swing scaling. We investigate the continuous voltage selection as well as its discrete counterpart, and we prove strong NP-hardness in the discrete case. Furthermore, the continuous voltage selection problem is solved using nonlinear programming with polynomial time complexity, while for the discrete problem, we use mixed integer linear programming and a polynomial time heuristic. We propose an approach that combines voltage selection and processor shutdown in order to optimize the total energy

This paper presents a test scheduling approach for system-on-chip production tests with peak-power constraints. An abort-on-first-fail test approach is assumed, whereby the test is terminated as soon as the first fault is detected. Defect probabilities of individual cores are used to guide the test scheduling and the peak-power constraint is considered in order to limit the test concurrency. Test set partitioning is used to divide a test set into several test sequences so that they can be tightly packed into the two-dimensional space of power and time. The partitioning of test sets is integrated into the test scheduling process. A heuristic has been developed to find an efficient test schedule which leads to reduced expected test time. Experimental results have shown the efficiency of the proposed test scheduling approach

In this paper we present an approach to the scheduling of fault-tolerant embedded systems for safety-critical applications. Processes and messages are statically scheduled, and we use process re-execution for recovering from multiple transient faults. If process recovery is performed such that the operation of other processes is not affected, we call it transparent recovery. Although transparent recovery has the advantages of fault containment, improved debugability and less memory needed to store the fault-tolerant schedules, it will introduce delays that can violate the timing constraints of the application. We propose a novel algorithm for the synthesis of fault-tolerant schedules that can handle the transparency/performance trade-offs imposed by the designer, and makes use of the fault-occurrence information to reduce the overhead due to fault tolerance. We model the application as a conditional process graph, where the fault occurrence information is represented as conditional edges and the transparent recovery is captured using synchronization nodes.

This paper presents an effective approach to formally verify SystemC designs. The approach translates SystemC models into a Petri-Net based representation. The Petri-net model is then used for model checking of properties expressed in a timed temporal logic. The approach is particularly suitable for, but not restricted to, models at a high level of abstraction, such as transaction-level. The efficiency of the approach is illustrated by experiments.

This paper addresses communication optimisation for applications implemented on networks-on-chip. The mapping of data packets to network links and the timing of the release of the packets are critical for avoiding destination contention. This reduces the demand for communication buffers with obvious advantages in chip area and energy savings. We propose a buffer need analysis approach and a strategy for communication synthesis and packet release timing with minimum communication buffer demand that guarantees worst-case response times.

In this paper we present an approach for the mapping optimization of fault-tolerant embedded systems for safety-critical applications. Processes and messages are statically scheduled. Process re-execution is used for recovering from multiple transient faults. We call process recovery transparent if it does not affect operation of other processes. Transparent recovery has the advantage of fault containment, improved debugability and less memory needed to store the fault-tolerant schedules. However, it will introduce additional delays that can lead to violations of the timing constraints of the application. We propose an algorithm for the mapping of fault-tolerant applications with transparency. The algorithm decides a mapping of processes on computation nodes such that the application is schedulable and the transparency properties imposed by the designer are satisfied. The mapping algorithm is driven by a heuristic that is able to estimate the worst-case schedule length and indicate whether a certain mapping alternative is schedulable

FlexRay will very likely become the de-facto standard for in-vehicle communications. However, before it can be successfully used for safety-critical applications that require predictability, timing analysis techniques are necessary for providing bounds for the message communication times. In this paper, we propose techniques for determining the timing properties of messages transmitted in both the static (ST) and the dynamic (DYN) segments of a FlexRay communication cycle. The analysis techniques for messages are integrated in the context of a holistic schedulability analysis that computes the worst-case response times of all the tasks and messages in the system. We have evaluated the proposed analysis techniques using extensive experiments

In some real-time applications, it is desirable to trade off precision for timeliness. For such systems, considered typically under the Imprecise Computation model, a function assigns reward to the application depending on the amount of computation allotted to it. Also, many such applications run on battery-powered devices where the energy consumption is of utmost importance. We address in this paper the problem of energy minimization for Imprecise-Computation systems that have reward and time constraints. We propose a Quasi-Static (QS) approach that exploits, with low on-line overhead, the dynamic slack that arises from variations in the actual number of execution cycles: first, at design-time, a set of solutions are computed and stored (off-line phase); second, the selection among the precomputed assignments is left for run-time, based on actual values of time and reward (on-line phase).

This paper addresses the interrelation between control and data flow in embedded system models through a new design representation, called Dual Flow Net (DFN). A modeling formalism with a very close-fitting control and data flow is achieved by this representation, as a consequence of enhancing its underlying Petri net structure. The work presented in this paper does not only tackle the modeling side in embedded systems design, but also the validation of embedded system models through formal methods. Various introductory examples illustrate the applicability of the DFN principles, whereas the capability of the model to with complex designs is demonstrated through the design and verification of a real-life Ethernet coprocessor.

An increasing number of real-time applications are today implemented using distributed heterogeneous architectures composed of interconnected networks of processors. The systems are heterogeneous not only in terms of hardware and software components, but also in terms of communication protocols and scheduling policies. In this context, the task of designing such systems is becoming increasingly difficult. The success of new adequate design methods depends on the availability of efficient analysis as well as optimization techniques. In this article, we present both analysis and optimization approaches for such heterogeneous distributed real-time embedded systems. More specifically, we discuss the schedulability analysis of hard real-time systems, highlighting particular aspects related to the heterogeneous and distributed nature of the applications. We also introduce several design optimization problems characteristic of this class of systems: mapping of functionality, the optimization of access to communication channel, and the assignment of scheduling policies to processes. Optimization heuristics aiming at producing a schedulable system with a given amount of resources are presented.

For some realtime systems, it is possible to tradeoff precision for timeliness. For such systems, typically considered under the imprecise computation model, a function assigns reward to the application depending on the amount of computation allotted to it. Also, these systems often have stringent energy constraints since many such applications run on battery powered devices. We address in this paper, the problem of maximizing rewards for imprecise computation systems that have energy constraints, more specifically, the problem of determining the voltage at which each task runs as well as the number of optional cycles such that the total reward is maximal while time and energy constraints are satisfied. We propose a quasi-static approach that is able to exploit, with low online overhead, the dynamic slack that arises from variations in the actual number of task execution cycles. In our quasi-static approach, the problem is solved in two steps: first, at design-time, a set of voltage/optional-cycles assignments are computed and stored (offline phase); second, the selection among the precomputed assignments is left for runtime, based on actual completion times and consumed energy (online phase). The advantages of the approach are demonstrated through numerous experiments with both synthetic examples and a real life application

Due to the increasing test data volume needed to test corebased System-on-Chip, several test scheduling techniques minimizing the test application time have been proposed. In contrast to approaches where a fixed test set for each core is assumed, we explore the possibility to use overlapping test patterns from the tests in the system. The overlapping tests serves as alternatives to the original dedicated test for the cores and, if selected, they are transported to the cores in a broadcasted manner so that several cores are tested concurrently. We have made use of a Constraint Logic Programming technique to select suitable tests for each core in the system and schedule the selected tests such that the test application time is minimized while designer-specified hardware constraints are satisfied. The experimental results indicate that we can on average reduce the test application time with 23%.

There exist real-time systems for which it is possible to trade off precision for timeliness. In these cases, a function assigns reward to the application depending on the amount of computation allotted to it. At the same time, many such applications run on battery-powered devices with stringent energy constraints. This paper addresses the problem of maximizing rewards subject to time and energy constraints. We propose a quasi-static approach where the problem is solved in two steps: first, at design-time, a number of solutions are computed and stored (off-line phase); second, one of the precomputed solutions is selected at run-time based on actual values of time and energy (on-line phase). Thus our approach is able to exploit, with low on-line overhead, the dynamic slack caused by tasks executing less number of cycles than in the worst case. We conduct numerous experiments in order to show the advantages of our approach.

As feature sizes shrink, transient failures of on-chip network links become a critical problem. At the same time, many applications require guarantees on both message arrival probability and response time. We address the problem of transient link failures by means of temporally and spatially redundant transmission of messages, such that designerimposed message arrival probabilities are guaranteed. Response time minimisation is achieved by a heuristic that statically assigns multiple copies of each message to network links, intelligently combining temporal and spatial redundancy. Concerns regarding energy consumption are addressed in two ways. Firstly, we reduce the total amount of transmitted messages, and, secondly, we minimise the application response time such that the resulted time slack can be exploited for energy savings through voltage reduction. The advantages of the proposed approach are guaranteed message arrival probability and guaranteed worst case application response time.

Supply voltage scaling and adaptive body-biasing are important techniques that help to reduce the energy dissipation of embedded systems. This is achieved by dynamically adjusting the voltage and performance settings according to the application needs. In order to take full advantage of slack that arises from variations in the execution time, it is important to recalculate the voltage (performance) settings during run time, i.e., online. However voltage scaling (VS) is computationally expensive, and thus significantly hampers the possible energy savings. To overcome the online complexity, we propose a quasi-static voltage scaling scheme, with a constant online time complexity O(1). This allows us to increase the exploitable slack as well as to avoid the energy dissipated due to online recalculation of the voltage settings. We conduct several experiments that demonstrate the advantages of the proposed technique over the previously published voltage scaling approaches.

In this paper we present an approach to the design optimization of fault tolerant embedded systems for safety-critical applications. Processes are statically scheduled and communications are performed using the time-triggered protocol. We use process re-execution and replication for tolerating transient faults. Our design optimization approach decides the mapping of processes to processors and the assignment of fault-tolerant policies to processes such that transient faults are tolerated and the timing constraints of the application are satisfied. We present several heuristics which are able to find fault-tolerant implementations given a limited amount of resources. The developed algorithms are evaluated using extensive experiments, including a real-life example.

This paper presents a method for power-constrained system-on-chip test scheduling in an abort-on-first-fail environment where the test is terminated as soon as a fault is detected. We employ the defect probabilities of individual cores to guide the scheduling, such that the expected total test time is minimized and the peak power constraint is satisfied. Based on a hybrid BIST architecture where a combination of deterministic and pseudorandom test sequences is used, the power-constrained test scheduling problem can be formulated as an extension of the two-dimensional rectangular packing problem and a heuristic has been proposed to calculate the near optimal order of different test sequences. The method is also generalized for both test-per-clock and test-per-scan approaches. Experimental results have shown that the proposed heuristic is efficient to find a near optimal test schedule with a low computation overhead.

This paper proposes a validation approach, based on simulation, which addresses problems related to both state space explosion of formal methods and low coverage of informal methods. Formal methods, in particular model checking, are used to aid the simulation process in certain situations in order to boost coverage. The invocation frequency of the model checker is dynamically controlled by estimating certain parameters, based on statistics collected previously during the same validation session, in order to minimise verification time and at the same time achieve reasonable coverage. The approach has been demonstrated feasible by numerous experimental results.

The increasing amount of test data needed to test SOC (system-on-chip) entails efficient design of the TAM (test access mechanism), which is used to transport test data inside the chip. Having a powerful TAM shorten the test time, but it costs large silicon area to implement it. Hence, it is important to have an efficient TAM with minimal required hardware overhead. We propose a technique that makes use of the existing bus structure with additional buffers inserted at each core to allow test application to the cores and test data transportation over the bus to be performed asynchronously. The non-synchronization of test data transportation and test application makes it possible to perform concurrent testing of cores while test data is transported in a sequence. We have implemented a Tabu search based technique to optimize our test architecture, and the experimental results indicate that it produces high quality results at low computational cost.

Recent research has shown that the combination of dynamic voltage scaling (DVS) and adaptive body biasing (ABB) yields high energy reductions in embedded systems. Nevertheless, the implementation of DVS and ABB requires a significant system cost, making it less attractive for many small systems. In this paper we demonstrate that it is possible to reduce this system cost and to achieve comparable energy saving to that obtained using combined DVS and ABB scheme through a co-synthesis methodology which is aware of the tasks' power-composition profile (the ratio of the dynamic power to the leakage power). In particular, the presented methodology performs a power management selection at the architectural level, i. e., it decides upon which processing elements to be equipped with which power management scheme (DVS, ABB, or combined DVS and ABB) - with the aim to achieve high energy savings at a reduced implementation cost. The proposed technique maps, schedules, and voltage scales applications specified as task graphs with timing constraints. Detailed experiments including a real-life benchmark are conducted to demonstrate the effectiveness of the proposed methodology.

We address in this paper the problem of scheduling for multiprocessor real-time systems with hard and soft tasks. Utility functions are associated to soft tasks to capture their relative importance and how the quality of results is affected when a soft deadline is missed. The problem is to find a task execution order that maximizes the total utility and guarantees the hard deadlines. In order to account for actual execution times, we consider time intervals for tasks rather than fixed execution times. A single static schedule computed offline is pessimistic, while a purely online approach, which computes a new schedule every time a task completes, incurs an unacceptable overhead. We propose therefore a quasi-static solution where a number of schedules are computed at design-time, leaving for run-time only the selection of a particular schedule, based on the actual execution times. We propose an exact algorithm as well as heuristics that tackle the time and memory complexity of the problem. We evaluate our approach through synthetic examples and a realistic application.

We present an approach to the analysis and optimization of heterogeneous distributed embedded systems for hard real-time applications.The systems are heterogeneous not only in terms of hardware components, but also in terms of communication protocols and scheduling policies.When several scheduling policies share a resource, they are organized in a hierarchy.In this paper, we address design problems that are characteristic to such hierarchically scheduled systems: assignment of scheduling policies to tasks, mapping of tasks to hardware components, and the scheduling of the activities.We present algorithms for solving these problems.Our heuristics are able to find schedulable implementations under limited resources, achieving an efficient utilization of the system.

We present a novel co-design methodology for the synthesis of energy-efficient embedded systems. In particular, we concentrate on distributed embedded systems that accommodate several different applications within a single device, i.e., multimode embedded systems. Based on the key observation that operational modes are executed with different probabilities, that is, the system spends uneven amounts of time in the different modes, we develop a new co-design technique that exploits this property to significantly reduce energy dissipation. Energy and cost savings are achieved through a suitable synthesis process that yields better hardware-resource-sharing opportunities. We conduct several experiments, including a realistic smart phone example, that demonstrate the effectiveness of our approach. Reductions in power consumption of up to 64% are reported.

We present an approach to frame packing for multicluster distributed embedded systems consisting of time-triggered and event-triggered clusters, interconnected via gateways. In our approach, the application messages are packed into frames such that the application is schedulable, thus the end-to-end message communication constraints are satisfied. We have proposed a schedulability analysis for applications consisting of mixed event-triggered and time-triggered processes and messages, and a worst-case queuing delay analysis for the gateways, responsible for routing inter-cluster traffic. Optimization heuristics for frame packing aiming at producing a schedulable system have been proposed. Extensive experiments and a real-life example show the efficiency of our frame-packing approach.

This paper describes a heuristic for system-on-chip test scheduling in an abort-on-fail context, where the test is terminated as soon as a defect is detected. We consider an hybrid BIST architecture, where a test set is assembled from pseudorandom and deterministic test patterns. We take into account defect probabilities of individual cores in order to schedule the tests so that the expected total test time in the abort-on fail environment is minimized. Different from previous approaches, our hybrid BIST based approach enables us not only to schedule the tests but also to modify the internal test composition, the order and ratio of pseudorandom and deterministic test patterns, in order to reduce the expected total test time. Experimental results have shown the efficiency of the proposed heuristic to find good quality solutions with low computational overhead.

Dynamic voltage scaling and adaptive body biasing have been shown to reduce dynamic and leakage power consumption effectively. In this paper, we optimally solve the combined supply voltage and body bias selection problem for multi-processor systems with imposed time constraints, explicitly taking into account the transition overheads implied by changing voltage levels. Both energy and time overheads are considered. We investigate the continuous voltage scaling as well as its discrete counterpart, and we prove NP-hardness in the discrete case. Furthermore, the continuous voltage scaling problem is formulated and solved using nonlinear programming with polynomial time complexity, while for the discrete problem we use mixed integer linear programming. Extensive experiments, conducted on several benchmarks and a real-life example, are used to validate the approaches.

This paper addresses the problem of scheduling for real-time systems that include both hard and soft tasks. The relative importance of soft tasks and how the quality of results is affected when missing a soft deadline are captured by utility functions associated to soft tasks. Thus the aim is to find the execution order of tasks that makes the total utility maximum and guarantees hard deadlines. We consider time intervals rather than fixed execution times for tasks. Since a purely off-line solution is too pessimistic and a purely on-line approach incurs an unacceptable overhead due to the high complexity of the problem, we propose a quasi-static approach where a number of schedules are prepared at design-time and the decision of which of them to follow is taken at run-time based on the actual execution times. We propose an exact algorithm as well as different heuristics for the problem addressed in this paper.

We present an approach to design optimization of multi-cluster embedded systems consisting of time-triggered and event-triggered clusters, interconnected via gateways. In this paper, we address design problems which are characteristic to multi-clusters: partitioning of the system functionality into time-triggered and event-triggered domains, process mapping, and the optimization of parameters corresponding to the communication protocol. We present several heuristics for solving these problems. Our heuristics are able to find schedulable implementations under limited resources, achieving an efficient utilization of the system. The developed algorithms are evaluated using extensive experiments and a real-life example.

This paper proposes a formal verification methodology which smoothly integrates with component-based system-level design, using a divide and conquer approach. The methodology assumes that the system consists of several reusable components, each of them already verified by their designers and which are considered correct under the assumption that the environment satisfies certain properties assumed by the component. What remains to be verified is the glue logic inserted between the components. Each such glue logic is verified one at a time using model checking techniques. Experiments, performed on a real-life example (mobile telephone), demonstrating the efficiency and intuitivity of the methodology, are moreover thoroughly presented. Three different properties have been verified on one part of the system.

This paper addresses the problem of BIST synthesis that takes into account wiring area. A technique for minimizing BIST hardware overhead is presented. The technique uses results of symbolic testability analysis to guarantee testability of all modules in the design. New behavioral-level BIST enhancement metrics are used to guide synthesis in such a way that the number of testability enhancements is minimized. The technique is not only fast but also adds low BIST overhead.

We propose a new technique for the combined voltage scaling of processors and communication links, taking into account dynamic as well as leakage power consumption. The voltage scaling technique achieves energy efficiency by simultaneously scaling the supply and body bias voltages in the case of processors and buses with repeaters, while energy efficiency on fat wires is achieved through dynamic voltage swing scaling. We also introduce a set of accurate communication models for the energy estimation of voltage scalable embedded systems. In particular, we demonstrate that voltage scaling of bus repeaters and dynamic adaption of the voltage swing on fat wires can significantly influence the system's energy consumption. Experimental results, conducted on numerous generated benchmarks and a real-life example, demonstrate that substantial energy savings can be achieved with the proposed techniques.

Both analysis and design optimization of real-time systems has predominantly concentrated on considering hard real-time constraints. For a large class of applications, however, this is both unrealistic and leads to unnecessarily expensive implementations. We address the problem of task priority assignment and task mapping in the context of multiprocessor applications with stochastic execution times and in the presence of constraints on the percentage of missed deadlines. We propose a design space exploration strategy based on tabu search together with a fast method for system performance analysis. Experiments emphasize the efficiency of the proposed analysis method and optimization heuristic in generating high quality implementations of soft real-time systems with stochastic task execution times and constraints on deadline miss ratios.

In the past decade, the limitations of models considering fixed (worst-case) task execution times have been acknowledged for large application classes within soft real-time systems. A more realistic model considers the tasks having varying execution times with given probability distributions. Considering such a model with specified task execution time probability distribution functions, an important performance indicator of the system is the expected deadline miss ratio of the tasks and of the task graphs. This article presents an approach for obtaining this indicator in an analytic way. Our goal is to keep the analysis cost low, in terms of required analysis time and memory, while considering as general classes of target application models as possible. The following main assumptions have been made on the applications that are modeled as sets of task graphs: the tasks are periodic, the task execution times have given generalized probability distribution functions, the task execution deadlines are given and arbitrary, the scheduling policy can belong to practically any class of non-preemptive scheduling policies, and a designer supplied maximum number of concurrent instantiations of the same task graph is tolerated in the system. Experiments show the efficiency of the proposed technique for monoprocessor systems.

We present an iterative schedule optimization for multirate system specifications, mapped onto heterogeneous distributed architectures containing dynamic voltage scalable processing elements (DVS-PEs). To achieve a high degree of energy reduction, we formulate a generalized DVS problem, taking into account the power variations among the executing tasks. An efficient heuristic is presented that identifies optimized supply voltages by not only "simply" exploiting slack time, but under the additional consideration of the power profiles. Thereby, this algorithm minimizes the energy dissipation of heterogeneous architectures, including power-managed processing elements, effectively. Further, we address the simultaneous schedule optimization toward timing behavior and DVS utilization by integrating the proposed DVS heuristic into a genetic list scheduling approach. We investigate and analyze the possible energy reduction at both steps of the co-synthesis (voltage scaling and scheduling), including the power variations effects. Extensive experiments indicate that the presented work produces solutions with high quality.

In this paper, we present an approach to mapping and scheduling of distributed embedded systems for hard real-time applications, aiming at a minimization of the system modification cost. We consider an incremental design process that starts from an already existing system running a set of applications. We are interested in implementing new functionality such that the timing requirements are fulfilled and the following two requirements are also satisfied: 1) the already running applications are disturbed as little as possible and 2) there is a good chance that later, new functionality can easily be added to the resulted system. Thus, we propose a heuristic that finds the set of already running applications which have to be remapped and rescheduled at the same time with mapping and scheduling the new application, such that the disturbance on the running system (expressed as the total cost implied by the modifications) is minimized. Once this set of applications has been determined, we outline a mapping and scheduling algorithm aimed at fulfilling the requirements stated above. The approaches have been evaluated based on extensive experiments using a large number of generated benchmarks as well as a real-life example.

This paper presents a solution to the test time minimization problem for core-based systems. We assume a hybrid BIST approach, where a test set is assembled, for each core, from pseudorandom test patterns that are generated online, and deterministic test patterns that are generated off-line and stored in the system. In this paper, we propose an iterative algorithm to find the optimal combination of pseudorandom and deterministic test sets of the whole system, consisting of multiple cores, under given memory constraints, so that the total test time is minimized. Our approach employs a fast estimation methodology in order to avoid exhaustive search and to speed-up the calculation process. Experimental results have shown the efficiency of the algorithm to find near optimal solutions.

This paper deals with specific issues related to the design of distributed embedded systems implemented with mixed, event-triggered and time-triggered task sets, which communicate over bus protocols consisting of both static and dynamic phases. Such systems are emerging as a new standard for automotive applications. We have developed a holistic timing analysis and scheduling approach for this category of systems. Three alternative scheduling heuristics are presented and compared. We have also identified several new design problems characteristic to such hybrid systems. An example related to bus access optimization in the context of a mixed static/dynamic bus protocol is presented. Experimental results prove the efficiency of such an optimization approach.

We present an approach to frame packing for multi-cluster distributed embedded systems consisting of time-triggered and event-triggered clusters, interconnected via gateways. In our approach, the application messages are packed into frames such that the application is schedulable. Thus, we have also proposed a schedulability analysis for applications consisting of mixed event-triggered and time-triggered processes and messages, and a worst case queuing delay analysis for the gateways, responsible for routing inter-cluster traffic. Optimization heuristics for frame packing aiming at producing a schedulable system have been proposed. Extensive experiments and a real-life example show the efficiency of our frame-packing approach.

In this paper, we present an efficient two-step iterative synthesis approach for distributed embedded systems containing dynamic voltage scalable processing elements (DVS-PEs), based on genetic algorithms. The approach partitions, schedules, and voltage scales multi-rate specifications given as task graphs with multiple deadlines. A distinguishing feature of the proposed synthesis is the utilisation of a generalised DVS method. In contrast to previous techniques, which "simply" exploit available slack time, this generalised technique additionally considers the PE power profile during a refined voltage selection to further increase the energy savings. Extensive experiments are conducted to demonstrate the efficiency of the proposed approach. We report up to 43.2% higher energy reductions compared to previous DVS scheduling approaches based on constructive techniques and total energy savings of up to 82.9% for mapping and scheduling optimised DVS systems.

This paper presents an approach to the analysis of task sets implemented on multiprocessor systems, when the task execution times are specified as generalized probability distributions. Because of the extreme complexity of the problem, an exact solution is practically impossible to be obtained even for toy examples. Therefore, our methodology is based on approximating the generalized probability distributions of execution times by Coxian distributions of exponentials. Thus, we transform the generalized semi-Markov process, corresponding to the initial problem, into a continuous Markov chain (CTMC) which, however, is extremely large and, hence, most often is impossible to be stored in memory. We have elaborated a solution which allows to generate and analyze the CTMC in an efficient way, such that only a small part has to be stored at a given time. Several experiments investigate the impact of various parameters on complexity, in terms of time and memory, as well as the trade-offs regarding the accuracy of generated results.

In this paper we present an approach to incremental design of dis-tributed embedded systems for hard real-time applications. We start from an already existing system running a set of applications and the design problem is to implement new functionality so that the already running applications are not disturbed and there is a good chance that, later, new functionality can easily be added to the resulted sys-tem. The mapping and scheduling problem are considered in the con-text of a realistic communication model based on a TDMA protocol.

In order to represent efficiently large systems, a mechanism for hierarchical composition is needed so that the model may be constructed in a structured manner and composed of simpler units easily comprehensible by the designer at each description level. In this paper we formally define the notion of hierarchy for a Petri net based representation used for modeling embedded systems. We show how small parts of a large system may be transformed by using the concept of hierarchy and the advantages of a transformational approach in the verification of embedded systems. A real-life example illustrates the feasibility of our approach on practical applications.

This paper presents an efficient way to analyse the performance of task sets, where the task execution time is specified as a generalized continuous probability distribution. We consider fixed task sets of periodic, possibly dependent, non-pre-emptable tasks with deadlines less than or equal to the period. Our method is not restricted to any specific scheduling policy and supports policies with both dynamic and static priorities. An algorithm to construct the underlying stochastic process in a memory and time efficient way is presented. We discuss the impact of various parameters on complexity, in terms of analysis time and required memory. Experimental results show the efficiency of the proposed approach.

We present an approach to bus access optimization and schedulability analysis for the synthesis of hard real-time distribution embedded systems. The communication model is based on a time-triggered protocol. We have developed an analysis for the communication delays proposing four different message scheduling policies over a time-triggered communication channel. Optimization strategies for the bus access scheme are developed, and the four approaches to message scheduling are compared using extensive experiments.

Presents an approach to schedulability analysis for hard real-time systems with control and data dependencies. We consider distributed architectures consisting of multiple programmable processors, and the scheduling policy is based on a static priority pre-emptive strategy. Our model of the system captures both data and control dependencies, and the schedulability approach is able to reduce the pessimism of the analysis by using the knowledge about control and data dependencies. Extensive experiments as well as a real-life example demonstrate the efficiency of our approach.

Design of embedded systems is a complex task that requires design cycles founded upon formal notation, so that the synthesis from specification to implementation can be carried out systematically. The authors present a computational model for embedded systems based on Petri nets called PRES+. It includes an explicit notion of time and allows a concise formulation of models. Tokens, in our notation hold information, and transitions when fired perform transformation of data. Based on this model we define several notions of equivalence (reachable, behavioral, time, and total), which provide the framework for transformational synthesis of embedded systems. Different representations of an Ethernet network coprocessor are studied in order to illustrate the applicability of PRES+ and the definitions of equivalence on practical systems.

The paper explores aspects concerning system-level specification, modelling and simulation of real time embedded system. By means of case studies, we investigate how object oriented methodologies, and in particular UML, support the modelling of industrial scale real time systems, and how different architectures can be explored by model simulation. We are mainly interested in the problem of system specification as it appears from the prospect of the whole design process. The discussion is illustrated by a large system model from the telecommunications area, the GSM base transceiver station.

In this paper, we concentrate on aspects related to the synthesis of distributed embedded systems consisting of programmable processors and application-specific hardware components. The approach is based on an abstract graph representation that captures, at process level, both dataflow and the flow of control. Our goal is to derive a worst case delay by which the system completes execution, such that this delay is as small as possible; to generate a logically and temporally deterministic schedule; and to optimize parameters of the communication protocol such that this delay is guaranteed. We have further investigated the impact of particular communication infrastructures and protocols on the overall performance and, specially, how the requirements of such an infrastructure have to be considered for process and communication scheduling. Not only do particularities of the underlying architecture have to be considered during scheduling but also the parameters of the communication protocol should be adapted to fit the particular embedded application. The optimization algorithm, which implies both process scheduling and optimization of the parameters related to the communication protocol, generates an efficient bus access scheme as well as the schedule tables for activation of processes and communications.

We present an approach to process scheduling based on an abstract graph representation which captures both data-flow and the flow of control. Target architectures consist of several processors, ASICs and shared buses. We have developed a heuristic which generates a schedule table so that the worst case delay is minimized. Several experiments demonstrate the efficiency of the approach.

This paper presents a list-scheduling algorithm for graphs with data and control dependencies. We assume that tasks are partitioned between hardware resources as scheduling takes place after partitioning in our co-synthesis tool. Control dependencies are introduced by if statements, and model complementary functionalities. A detailed discussion of our algorithm is presented. Extensive experimental work shows the effectiveness of our method for generating close-to-optima schedules in short run-times.