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.

Program path analysis is an essential component of software defect detection and quality assurance. Accurately identifying infeasible paths can prevent false positives caused by invalid paths, enabling developers to pinpoint actual defects more efficiently and enhancing overall software quality and reliability. This paper proposes an integrated approach for determining infeasible paths based on program path features and constraint-based reinforcement learning. First, a loop-structure path search and reduction algorithm is proposed to systematically simplify path explosion induced by loops. Then, a global subgraph-based path reduction algorithm is introduced to effectively remove redundant and irrelevant paths. Subsequently, we propose a path set generation algorithm guided by control and implication relationships to construct an optimized path set. Path constraints and symbolic path constraints are used to enhance semantic representation. Finally, a reinforcement learning-based model utilizing reachability rewards and exploration rewards to dynamically determine path reachability. Experimental results show that our proposed approach significantly reduces path explosion, accurately identifies infeasible paths and outperforms existing methods in terms of accuracy and computational efficiency.

One of the most effective methods for detecting software security vulnerabilities is taint analysis. Some software defects originate from certain external input data. Analyzing the taint sources and the data flow propagation from these sources to defect points through static analysis can help us understand the causes of software defects and reduce the difficulty of debugging them. This paper combines intraprocedural and interprocedural analysis methods to obtain global taint source information. A novel propagation path calculation algorithm is proposed, incorporating predecessor node computation and alias analysis, effectively reducing the negative impact of irrelevant code on the performance of taint analysis. This method not only helps detect errors that lead to vulnerabilities but also analyzes the impact of vulnerable input data on the system. Based on the global taint source analysis algorithm, we developed a static taint source analysis prototype tool for C programs, called AWsTS. Experiments conducted on five open-source projects show that AWsTS improves the accuracy of analysis results without increasing the required analysis time. The average precision for intra-procedural taint source analysis is 93.4%, and the average recall is 90.2%. Similarly, for interprocedural taint source analysis, the average precision is 87.6%, and the average recall is 84.9%. Additionally, AWsTS can output taint propagation paths, providing valuable support for further taint analysis.

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.

Time-sensitive networking (TSN) is an emerging technology widely used in real-time systems for its high bandwidth and deterministic timing properties. To ensure the deterministic transmission of Time-triggered (TT) messages, a guard band mechanism is employed to prevent interference from other messages, such as Audio-Video Bridging (AVB) and Best-effort (BE) messages, before transmitting the TT messages in TSN. However, this mechanism introduces transmission delays for non-TT messages and bandwidth wastes for the physical links. Another challenge arises from the default First-in-first-out (FIFO) order of incoming messages, resulting in a relatively low acceptance rate for non-TT messages. To address these issues, a hybrid scheduling algorithm based on the min-heap structure (HSMH) is proposed. For AVB messages, HSMH sorts them in ascending style on the basis of deadlines, guaranteeing the earliest deadline message to be sent first. For BE messages, a threshold is designed to diverge them into two queues: a FIFO queue and a STF (shortest-time-first) queue. The former outputs the messages in a FIFO style, while the latter outputs messages in a STF style. All the output order of AVB messages and STF-queue messages are arranged in a min-heap structure. The algorithm can efficiently improve the transmission rate of AVB messages, the sending rate of BE messages, and the overall link utilization. Experimental results demonstrate that the proposed algorithm outperforms existing approaches in all these three aspects.

This paper introduces a novel Real Relative encoding Genetic Algorithm (R$^{2}$GA) to tackle the workflow scheduling problem in heterogeneous distributed computing systems (HDCS). R$^{2}$GA employs a unique encoding mechanism, using real numbers to represent the relative positions of tasks in the schedulable task set. Decoding is performed by interpreting these real numbers in relation to the directed acyclic graph (DAG) of the workflow. This approach ensures that any sequence of randomly generated real numbers, produced by cross-over and mutation operations, can always be decoded into a valid solution, as the precedence constraints between tasks are explicitly defined by the DAG. The proposed encoding and decoding mechanism simplifies genetic operations and facilitates efficient exploration of the solution space. This inherent flexibility also allows R$^{2}$GA to be easily adapted to various optimization scenarios in workflow scheduling within HDCS. Additionally, R$^{2}$GA overcomes several issues associated with traditional genetic algorithms (GAs) and existing real-number encoding GAs, such as the generation of chromosomes that violate task precedence constraints and the strict limitations on gene value ranges. Experimental results show that R$^{2}$GA consistently delivers superior performance in terms of solution quality and efficiency compared to existing techniques.

Integrated Mapping and Scheduling (IMS) problems can be found in many domains, such as electronic design automation (EDA) and modern manufacturing systems. Optimization algorithms to solve the IMS problems can be used to minimize execution time, implementation cost, energy consumption, etc. Genetic Algorithms (GAs) are powerful evolutionary algorithms for tackling many of such IMS op-timization problems. By utilizing biological principles like selection, crossover, and mutation, GAs excel in generating high-quality solutions. Chromosome encoding and decoding, in addition to evolutionary operators, significantly influence GA's efficiency. This paper introduces a relative-priority genetic algorithm (RPGA), a novel GA for IMS problems, such as those in EDA. RPGA employs a unique encoding scheme tailored for IMS problems, especially those with OR nodes representing alternative operation paths. It encodes the relative priority of an operation in a chromosome, which can be divided into two parts: one for path selections and the other for operation scheduling and mappings. Efficient decoding of every chromosome into a solution is facilitated through the concept of a ready operation set. The study extensively compares RPGA and established meta-heuristics using a benchmark set. The experimental results demonstrate that RPGA achieves high solution quality and rapid convergence.

Amid growing concerns about hardware security, comprehensive security testing has become essential for chip certification. This paper proposes a deep-testing method for identifying Trojans of particular concern to middle-to-high-end users, with a focus on illegal instructions. A hidden instruction Trojan can employ a low-probability sequence of normal instructions as a boot sequence, which is followed by an illegal instruction that triggers the Trojan. This enables the Trojan to remain deeply hidden within the processor. It then exploits an intrusion mechanism to acquire Linux control authority by setting a hidden interrupt as its payload. We have developed an unbounded model checking (UMC) technique to uncover such Trojans. The proposed UMC technique has been optimized with slicing based on the input cone, head-point replacement, and backward implication. Our experimental results demonstrate that the presented instruction Trojans can survive detection by existing methods, thus allowing normal users to steal root user privileges and compromising the security of processors. Moreover, our proposed deep-testing method is empirically shown to be a powerful and effective approach for detecting these instruction Trojans.

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.

This article presents a bounded model checking (BMC)-based temperature-aware software-based self-testing (SBST) technique to test worst case delay faults within the highest temperature range. The BMC-based SBST method first defines the sequential constraint. It develops a sequentially constrained automatic test pattern generation (ATPG) to ensure that the generated delay test patterns can emerge in functional mode. It then uses the processor’s multiple-level information to reduce the model complexity, avoid aborts due to time-outs during the BMC process, and generate test programs automatically. A temperature-aware SBST method has then been developed to ensure that the test temperature is within the specified range and test the worst case delays under high temperature. Experimental results demonstrate that the proposed technique achieves an extremely high coverage for delay faults and effectively avoids yield loss caused by the overtesting problem. Its test quality also outperforms that of the existing methods. The generated SBST programs are successful and efficient in testing worst case delay faults under high temperature.

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.

Very-large-scale network-on-chip (VLS-NoC) has become a promising fabric for supercomputers, but this fabric may encounter the many-fault problem. This article proposes a deterministic routing algorithm to tolerate the effects of many faults in VLS-NoCs. This approach generates routing tables offline using a breadth-first traversal algorithm and stores a routing table locally in each switch for online packet transmission. The approach applies the Tarjan algorithm to degrade the faulty NoC and maximizes the number of available nodes in the reconfigured NoC. In 2D NoCs, the approach updates routing tables of some nodes using the deprecated channel/node rules and avoids deadlocks in the NoC. In 3D NoCs, the approach uses a forbidden-turn selection algorithm and detour rules to prevent faceted rings and ensures the NoC is deadlock-free. Experimental results demonstrate that the proposed approach provides fault-free communications of 2D and 3D NoCs after injecting 40 faulty links. Meanwhile, it maximizes the number of available nodes in the reconfigured NoC. The approach also outperforms existing algorithms in terms of average latency, throughput, and energy consumption.

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.

Wafer-level NoC has emerged as a promising fabric to further improve supercomputer performance, but this new fabric may suffer from the many-fault problem. This paper presents a deterministic-path routing algorithm for tolerating many faults on wafer-level NoCs. The proposed algorithm generates routing tables using a breadth-first traversal strategy, and stores one routing table in each NoC switch. The switch will then transmit packages according to its routing table online. We use the Tarjan algorithm to dynamically reconfigure the routes to avoid the faulty nodes and develop the deprecated link/node rules to ensure deadlock-free communication of the NoCs. Experimental results demonstrate that the proposed algorithm does not only tolerate the effects of many faults, but also maximizes the available nodes in the reconfigured NoC. The performance of the proposed algorithm in terms of average latency, throughput, and energy consumption is also better than those of the existing solutions.

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.

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.

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.

With the development of silicon technology and safety-critical applications, the test community is facing many new challenges. In particular, there are many emerging test problems associated with the ever-increasing process variation in the silicon manufacturing process. Adaptive testing has been proposed as a solution to many of these test problems. This panel will debate on what adaptive testing techniques can and can't do as well as the interesting problems and research issues in this area. In a general sense, adaptive testing techniques include all approaches that modify the test configuration, condition, flow, stimuli, and constraints dynamically based on data collected during the test process. We will assume this general definition of adaptive testing and discuss the following questions in this panel: - What test problems can be uniquely solved by adaptive testing? - Is adaptive testing a topic for academia or is it really relevant for the industry? - How popular is adaptive testing in the industry now? Does it has any future? - What is needed to perform efficient adaptive testing and how hard is it to get it done? - What are the major challenges facing the deployment of adaptive testing? - What and how test data should be collected for adaptive testing? - When will the EDA companies start providing tools for adaptive testing? - What will be the hot research issues in adaptive testing? - Etc.

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.

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.

According to ISO 26262, a recent automotive functional safety standard, verification tools shall undergo qualification, e.g. to ensure that they do not fail to detect faults that can lead to violation of functional safety requirements. We present a semi-automatic qualification method involving a monitor and fault injection that reduce cost in the qualification process. We experiment on a verification tool implemented in LabVIEW.

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.

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.

We present an approach for optimization of assertion placement in time-constrained HW/SW modules for detection of errors due to transient and intermittent faults. During the design phases, these assertions have to be inserted into the executable code and, hence, will always be executed with the corresponding code branches. As the result, they can significantly increase execution time of a module, in particular, contributing to a much longer execution of the worst case, and cause deadline misses. Assertions have different characteristics such as tightness (or "local error coverage") and execution latency. Taking into account these properties can increase efficiency of assertion checks in time-constrained embedded HW/SW modules. We have developed a design optimization framework, which (1) identifies candidate locations for assertions, (2) associates a candidate assertion to each location, and (3) selects a set of assertions in terms of performance degradation and assertion tightness. Experimental results have shown the efficiency of the proposed techniques.

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.

The increasing test application times required for testing system-on-chips (SOCs) is a problem that leads to higher costs. For modular core based SOCs it is possibly to employ a concurrent test scheme in order to lower the test application times. To allow each core to be tested as a separate unit, a wrapper is inserted for each core, the scan chains at each core are configured into a fixed number of wrapper chains, and the wrapper chains are connected to the test access mechanism. A problem with concurrent testing is that it leads to higher power consumption as several cores are active at a time. Power consumption above the specified limit of a core or above the limit of the system will cause damage and must be avoided. The power consumption must be controlled both at core level as well as on system level. In this paper, we propose a reconfigurable power conscious core wrapper that we include in a preemptive power constrained test scheduling algorithm. The advantages with the wrapper are that the number of wrapper chains at each core can dynamically be changed during test application and the possibility, through clock gating, to select the appropriate test power consumption for each core. The scheduling technique produces optimal solutions in respect to test time and selects wrapper configurations in a systematic manner while ensuring the power limits at core level and system level are not violated. The wrapper configurations are selected such that the number of wrapper configurations as well as the number of wrapper chains at each wrapper are minimized, which minimizes the wrapper logic as well as the total TAM routing. We have implemented the technique and the experimental results show the efficiency of our approach.

Concurrent testing of the cores in a core-based system- on-chip reduces the test application time but increases the test power consumption. Power models, test architecture design, and scheduling algorithms have been proposed to schedule the tests as concurrently as possible while respecting the power budget. The commonly used global peak power model, with a single value capturing the power dissipated by a core when tested, is simple for a scheduling algorithm to handle but is pessimistic. In this paper, we propose a cycle-accurate power model with a power value per clock cycle and a corresponding test architecture design and scheduling algorithm. The power model takes into account the switching activity in the scan chains caused by both the test stimuli and the expected test responses during scan-in, launch-and-capture, and scan-out. Furthermore, we allow a unique power model per wrapper-chain configuration as the activity in a core will be different depending on the number of wrapper chains at a core. Through circuit simulations on ISCAS'89 benchmarks, we demonstrate a high correlation between the real test power dissipation and our cycle-accurate test power model. Extensive experiments on ITC'02 benchmarks and an industrial design show that the testing time can be reduced substantially by using the proposed cycle-accurate test power model.

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.

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.

Testing of high density SoCs operating at high clock speeds is an important but difficult problem. Many faults, like delay faults, in such sub-micron chips may only appear when the chip works at normal operating speed. In this paper, we propose a methodology for at-speed testing of delay faults in links connecting two distinct clock domains in a SoC. We give an analytical analysis about the efficiency of this method. We also propose a simple digital hardware structure for the receiver end of the link under test to detect delay faults. It is possible to extend our method to combine it with functional testing of the link and adapt it for online testing

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

Concurrent testing of the cores in a modular core-based system-on-chip reduces the test application time but increases the test power consumption. Power models and scheduling algorithms have been proposed to schedule the tests as concurrently as possible while respecting the power budget. The commonly used global peak power model, with a single value capturing the power dissipated by a core when tested, is pessimistic but simple for a scheduling algorithm to handle. In this paper, we propose a cycle-accurate power model with a power value per clock cycle and a corresponding scheduling algorithm. The model takes into account the switching activity in the scan chains caused by both the test stimuli and the test responses during scan-in, launch-and-capture and scan-out. Further, we allow a unique power model per wrapper chain configuration as the activity in a core will be different depending on the number of wrapper chains at a core. Extensive experiments on ITC'02 benchmarks and an industrial design show that the testing time can be substantially reduced (on average 16.5% reduction) by using the proposed cycle-accurate test power model

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

Test application and test design, performed to ensure the production of fault-free chips, are becoming complicated and very expensive, especially in the case of SoCs (system-on-chip), as the number of possible faults in a chip is increasing dramatically due to the technology development. It is therefore important to take test design into consideration as early as possible in the SoC design-flow in order to develop an efficient test solution. We propose a technique for modular core-based SoCs where test design is integrated in the early design exploration process. The technique can, in contrast to previous approaches, already be used in the core selection process to evaluate the impact on the system's final test solution imposed by different design decisions. The proposed technique considers the interdependent problems of core selection, test scheduling, TAM (test access mechanism) design, test set selection, and test resource floorplanning, and minimizes a weighted cost-function based on test time and TAM routing cost, while considering test conflicts and test power limitations. Concurrent scheduling of tests is used to minimize the test application time; however, concurrent test application leads to higher activity during the testing and, hence, higher power consumption. The power consumed during testing is, in general, higher than that during normal operation since it is desirable with hyperactivity in order to maximize the number of tested faults in a minimal time. A system under test can actually be damaged during testing and, therefore, power constraints must be considered. However, power consumption is complicated to model and, often, simplistic models that focus on the global system power limit only have been proposed and used. We therefore include a novel three-level power model: system, power-grid, and core.

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.

This paper addresses the energy minimization problem for system-on-chip testing. We assume a hybrid BIST test architecture where a combination of deterministic and pseudorandom test sequences is used. The objective of our proposed technique is to find the best ratio of these sequences so that the total energy is minimized and the memory requirements for the deterministic test set are met without sacrificing test quality. We propose two different heuristic algorithms and a fast estimation method that enables considerable reduction of the computation time. Experimental results have shown the efficiency of the approach for finding reduced energy solutions with low computational overhead.

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 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 this paper we address the test scheduling problem for system-on-chip designs. Different from previous approaches where it is assumed that all tests are performed until completion, we consider the cases where the test process are terminated as soon as a defect is detected. This is common practice in production test of chips. The proposed technique takes into account the probability of defect-detection by a test in order to schedule the tests so that the expected total test time is minimized. We investigate different test bus structures, test scheduling strategies (sequential scheduling vs. concurrent scheduling), and test set assumptions (fixed test time vs. flexible test time). We have also made experiments to illustrate the efficiency of taking defect probability into account during test scheduling.

A test solution for a complex system requires the design of a test access mechanism (TAM), which is used for the test data transportation, and a test schedule of the test data transportation on the designed TAM. An extensive TAM will lead to lower test-application time at the expense of higher routing costs, compared to a simple TAM with low routing cost but long testing time. It is also possible to reduce the testing time of a testable unit by loading the test vectors in parallel, thus increasing the parallelization of a test. However, such a test-time reduction often leads to higher power consumption, which must be kept under control since exceeding the power budget could damage the system under test. Furthermore, the execution of a test requires resources and concurrent execution of tests may not be possible due to resource or other conflicts. In this paper, we propose an integrated technique for test scheduling, test parallelization, and TAM design, where the test application time and the TAM routing are minimized, while considering test conflicts and power constraints. The main features of our technique are the efficiency in terms of computation time and the flexibility to model the system's test behavior, as well as the support for the testing of interconnections, unwrapped cores and user-defined logic. We have implemented our approach and made several experiments on benchmarks as well as industrial designs in order to demonstrate that our approach produces high-quality solution at low computational cost.

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.

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.

In this paper, we propose an SOC (system-on-chip) test scheduling technique that minimizes the test application time while considering test power limitations and test conflicts. The test power consumption is important to consider since exceeding the system's power limit might damage the system. Our technique takes also into account test conflicts that are due to cross-core testing (testing of interconnections), unit testing with multiple test sets, hierarchical SOCs where cores are embedded in cores, and the sharing of test access mechanism (TAM). Our technique handles these conflicts as well as precedence constraints, which is the order in which the tests has to be applied. We have implemented our algorithm and performed experiments, which shows the efficiency of our approach.

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.

This paper presents a novel reconfigurable powerconscious core test wrapper and discusses its application to optimal power-constrained SOC (system-on-chip) test scheduling. The advantage with the proposed wrapper is that at each core it allows (1) a exible TAM (test access mechanism) bandwidths, and (2) a possibility to select the appropriate test power consumption. Our scheduling technique, an extension of a preemptive scheduling approach,produces optimal solutions in respect to test time, and selects wrapper configurations in a systematic way that implicitly minimizes the TAM routing and the wrapper logic. Experimental results show the efficiency of our 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.

We propose a technique integrating test scheduling, scan chain partitioning and test access mechanism (TAM) design to minimize the test time and the TAM routing cost while considering test conflicts and power constraints. The main features of our technique are (1) the flexibility in modelling the systems test behaviour and (2) the support for interconnection test of unwrapped cores and user-defined logic. Experiments using our implementation on several benchmarks and industrial designs demonstrate that it produces high quality solution at low computational cost.

This paper describes an environment for internet-based collaboration in the field of design and test of digital systems. Automatic Test Pattern Generation (ATPG) and fault simulation tools at behavioral, logical and hierarchical levels available at geographically different places running under the virtual environment using the MOSCITO system are presented The interfaces between the integrated tools and also commercial design tools were developed. The tools can be used separately, or in multiple applications in different design and test flows. The functionality of the integrated design and test system was verified in several collaborative experiments over internet by partners locating in different geographical sites.

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.

An integrated technique for test scheduling and scan-chain division under power constraints is proposed in this paper. We demonstrate that optimal test time can be achieved for systems tested by an arbitrary number of tests per core using scan-chain division and we define an algorithm for it. The design of wrappers to allow different lengths of scan-chains per core is also outlined. We investigate the practical limitations of such wrapper design and make a worst case analysis that motivates our integrated test scheduling and scan-chain division algorithm. The efficiency and usefulness of our approach have been demonstrated with an industrial design.

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 this paper we propose a framework for the testing of system-on-chip (SOC), which includes a set of design algorithms to deal with test scheduling, test access mechanism design, test sets selection, test parallelization, and test resource placement. The approach minimizes the test application time and the cost of the test access mechanism while considering constraints on tests, power consumption and test resources. The main feature of our approach is that it provides an integrated design environment to treat several different tasks at the same time, which were traditionally dealt with as separate problems. Experimental results shows the efficiency and the usefulness of the proposed technique.

Meeting timing requirements is an important constraint imposed on highly integrated circuits, and the verification of timing of a circuit before manufacturing is one of the critical tasks to be solved by CAD tools. In this paper, a new approach and the implementation of several algorithms to speed up gate-level timing simulation are proposed where, instead of gate delays, path delays for tree-like subcircuits (macros) are used. Therefore timing waveforms are calculated not for all internal nodes of the gate-level circuit but only for outputs of macros. The macros are represented by structurally synthesized binary decision diagrams (SSBDD) which enable a fast computation of delays for macros. The new approach to speed up the timing simulation is supported by encouraging experimental results.

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.

The paper presents a hybrid BIST solution for testing systems-on-chip which combines pseudorandom test patterns with stored precomputed deterministic test patterns. A procedure is proposed for fast calculation of the cost of hybrid BIST at different lengths of pseudorandom test to find an optimal balance between test sets, and to perform a core test with minimum cost of both time and memory, and without losing test quality. Compared to the previous approach, based on iterative use of deterministic ATPG for evaluating the cost of stored patterns, a new, extremely fast procedure is proposed, which calculates costs on a basis of fault table manipulations. Experiments on the ISCAS benchmark circuits show that the new procedure is about two orders of magnitude faster than the previous one.

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 propose an integrated technique for extensive optimization of the final test solution for System-on-Chip using Simulated Annealing. The produced results from the technique are a minimized test schedule fulfilling test conflicts under test power constraints and an optimized design of the test access mechanism. We have implemented the proposed algorithm and performed experiments with several benchmarks and industrial designs to show the usefulness and efficiency of our technique.

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 high-level test synthesis algorithm for operation scheduling and data path allocation. Contrary to other works in which scheduling and allocation are performed independently, our approach integrates these two tasks by performing them simultaneously so that the effects of scheduling and allocation on testability are exploited more effectively. The approach is based on an algorithm which applies a sequence of semantics-preserving transformations to a design to generate an efficient RT level implementation from a VHDL behavioral specification. Experimental results show the advantages of the proposed algorithm.

This paper presents an RT level partitioning approach for sequential circuits described as data path and control part. The data path of a circuit is partitioned at some hard-to-test points detected by an RT level testability analysis algorithm. These points are then made directly accessible by DFT techniques. The control part is also modified to control the circuit in normal mode and test mode. In the normal mode, the circuit is controlled to perform its function, while in the test mode, all partitions are controlled independently. As a result, test quality is improved by independent test generation and test application for every partition. The partitioning complexity is reduced by the use of testability analysis results and the area overhead is lower than that of full scan designs for most benchmarks we used. Experiments show results of the approach as compared with no scan, partial scan and full scan schemes.

This paper presents an integrated modelling technique for digital designs consisting of both hardware and software components. The modelling technique is used to capture designs during the synthesis process from a high-level behavioural specification to its structural implementation. Based on the modelling technique, a hardware/software co-design environment is being built, which includes procedures for design evaluation, simulation, hardware/software (re-)partitioning, and movement of functionality from hardware to software and vice versa.>

This paper describes a high-level synthesis system, called CAMAD, for transforming algorithms into hardware implementation structures at register-transfer level. The algorithms are used to specify the behaviors of the hardware to be designed. They are first translated into a formal representation model which is based on timed Petri nets and consists of separate but related descriptions of control and data path. The formal model is used as an intermediate design representation and supports an iterative transformation approach to high-level synthesis. The basic idea is that once the behavioral specification is translated into the initial design representation, it can be viewed as a primitive implementation. Correctness-preserving transformations are then used to successively transform the initial design into an efficient implementation. Selection of transformations is guided by an optimization strategy which makes design decisions concerning operation scheduling, data path allocation, and control allocation simultaneously. The integration of these several synthesis subtasks has resulted in a better chance to reach the globally optimal solution. Experimental results show that our approach produces improved register-transfer designs, especially in the cases when the designed hardware consists of data paths and control logics that are tightly coupled.>

CAMAD is a high level design tool which helps designers to model, analyze, and design VLSI systems. This design aid system is based on a unified design representation model derived from timed Petri nets and consisting of separate but related models of control and data parts. The present paper describes the automatic synthesis package of the CAMAD system which takes a high level behavioral description as its input and synthesizes it into an implementation structure. This implementation structure may then be partitioned into several quasi-independent modules with well-defined interfaces, which allows potentially asynchronous operation of the designed systems as well as physical distribution of the modules.