Time-Sensitive Networks (TSN) are designed to ensure real-time and reliability performance in industrial applications. While Integer Linear Programming (ILP) based scheduling methods can achieve optimal solutions for network design, they face scalability issues and are primarily suitable for small-scale problems. This paper presents a group scheduling strategy targeting for large-scale TSN applications. The traffic dependency is modeled as an undirected graph to reveal the naturally existing intrinsic community structure among flows. Critical flows and intra-group flows are explicitly identified, allowing the scheduling problem to be decomposed into several subset scheduling problems. The scheduling process prioritizes critical flows, while intra-group flows are scheduled in parallel. Experimental evaluations confirm that the proposed method significantly reduces flowspan and computational overhead, offering an efficient and scalable solution for large scale industrial TSN applications.

Energy storage systems, especially lithium-ion batteries have gained significant attention and interest due to their potential in storing electrical energy and environmental sustainability. They play a crucial role in electric vehicles and significantly impact their performance, particularly in terms of electric driving range and quick acceleration. Despite their advantages, lithium-ion batteries also have limitations. These include the potential for thermal runaway, which can lead to safety hazards if not properly managed, such as outgassing, fire, and explosion that in turn cause significant property damage and fatalities. Published studies on road vehicles have not adequately considered the safety assurance of rechargeable energy storage systems in accordance with ISO 26262 standard. Accordingly in this paper, we focus on the safety assurance of a battery management system (BMS) that prevents thermal runaway and keeps lithium-ion batteries safe in electric vehicles. To this end, the safety life cycle process is performed. At first, the potential hazards that lead to thermal runaway impacting the functions of electric vehicles have been identified and safety goals related to means for preventing and controlling hazards are formulated. Next, the functional safety requirements are derived from each safety goal, and subsequently technical safety requirements are derived. To demonstrate the acceptable safety of electric vehicles using the BMS strategy, the safety cases are developed from the functional safety activities. The safety contracts are derived from battery specifications and chemistry and are associated with safety cases that provide the means for performing necessary adaptations at the operational phase. We leveraged a simulation for performing the verification and validation as well as finetuning of the BMS strategy. Simulation data is gathered, and the critical parameters are monitored to determine safety violations, control actions are triggered to resolve them, and safety cases are updated to reflect the current system safety.

Fog Computing for Robotics and Industrial Automation, FORA, was a European Training Network which focused on future industrial automation architectures and applications based on an emerging technology, called Fog Computing. The research project focused on research related to Fog Computing with applicability to industrial automation and manufacturing. The main outcome of the FORA project was the development of a deterministic Fog Computing Platform (FCP) to be used for implementing industrial automation and robotics solutions for Industry 4.0. This paper reports on the scientific outcomes of the FORA project. FORA has proposed a reference system architecture for Fog Computing, which was published as an open Architecture Analysis Design Language (AADL) model. The tech-nologies developed in FORA include fog nodes and hypervisors, resource management mechanisms and middleware for deploying scalable Fog Computing applications, while guaranteeing the non-functional properties of the virtualized industrial control applications, and methods and processes for assuring the safety and security of the FCP. Several industrial use cases were used to evaluate the suitability of the FORA FCP for the Industrial IoT area, and to demonstrate how the platform can be used to develop industrial control applications and data analytics applications.

In order to meet the requirements of critical applications, modern multi-core multi-SoC real-time systems must handle both periodic and sporadic events within specified deadlines. A two-level scheduling hierarchy that combines time-triggered and fixed-priority scheduling is effective for managing periodic time-triggered (TT) and sporadic event-triggered (ET) tasks, respectively. We introduce two polling-based approaches, called simple and advanced polling, for guaranteeing both TT and ET task deadlines within single core systems. We then propose an optimization heuristic for the task-to-core allocation problem based on genetic algorithms for fully partitioned multi-core systems that can be applied to both polling methods. We evaluate the schedulability and runtime performance of the polling approaches and investigate the effectiveness of the allocation heuristic using synthetic test cases based on real-world application characteristics. The results show that both polling approaches achieve high schedulability with low runtime, and the allocation heuristic can generate good solutions for fully partitioned systems. Furthermore, we show that the server design problem of the advanced polling approach can be integrated into the allocation heuristic to achieve better solutions in terms of schedulability and that our choice of the genetic algorithm has a good speedup when being parallelized.

Time Slotted Channel Hopping (TSCH) is a medium access protocol defined in the IEEE 802.15.4 standard which have been proven to be one of the most reliable options when it comes to industrial applications. TSCH has been designed to be utilized in static network topologies. Thus, if an application scenario requires a mobile network topology, TSCH does not perform reliably. In this paper we introduce active connectivity for mobile application scenarios, such as mobile robots. This is a feature that enables the option to regulate physical characteristics such as the speed of a node as it moves, in order to keep being connected to the TSCH network. We model the active connectivity approach through a basic example where two nodes are moving towards the same direction to infer the main principles of the introduced approach. We evaluate the active connectivity feature through simulations and quantify trade-off between connectivity and application-layer performance.

Industrie 4.0 reinforces advanced technology development to realize Time-Sensitive Networking (TSN) with real-time guarantees. The evolution of traditional industrial- automation systems such as Programmable Logic Controllers (PLCs) to cyber-physical systems by means of virtualization is one of the key enhancements. In this paper, we evaluate the impact of the placement of virtual PLCs (vPLCs) at edge clouds in conjunction with scheduling and routing of Time-Triggered (TT) traffic in 802.1Qbv-based industrial networks. We propose two approaches to solve this problem adopting a multi-objective optimization model. In the first approach, we solve separately the problem of placement and scheduling-routing by using a Mixed Integer Linear Programming (MILP) formulation. While in the second approach, we propose a Simulated Annealing (SA)- based meta-heuristic to solve the joint placement, scheduling, and routing optimization problem. We compare both the algorithms for real-world test cases and validate our solutions using the OMNeT++ simulator.

In this paper, we consider that critical control applications and Fog applications share a Fog Computing Platform (FCP). Critical control applications are implemented as periodic hard real-time tasks and messages and have stringent timing and safety requirements, and require safety certification. Fog applications are implemented as aperiodic tasks and messages and are not critical. Such applications need different approaches to guarantee their timing and dependability requirements. We formulate an optimization problem for the joint configuration of critical control and Fog applications, such that (i) the deadlines and Quality-of-Control (QoC) of control applications are guaranteed at design-time, (ii) the configuration is extensible and supports the addition of future new control applications without requiring costly re-certification, and (iii) the design-time configuration together with the runtime Fog resource management mechanisms, can successfully accommodate multiple dynamic responsive Fog applications. We evaluate our approach on several test cases assuming scenarios for hosting both Fog applications and future critical control applications. The results show that our approach generates extensible schedules which enables Fog nodes to handle Fog applications with a shorter response time and a larger number of future control applications.

Owning to the sub-standards being developed by IEEE Time-Sensitive Networking (TSN) Task Group, the traditional IEEE 802.1 Ethernet is enhanced to support real-time dependable communications for future time- and safety-critical applications. Several sub-standards have been recently proposed that introduce various traffic shapers (e.g., Time-Aware Shaper (TAS), Asynchronous Traffic Shaper (ATS), Credit-Based Shaper (CBS), Strict Priority (SP)) for flow control mechanisms of queuing and scheduling, targeting different application requirements. These shapers can be used in isolation or combination and there is limited work that analyzes, evaluates, and compares their performance, which makes it challenging for end-users to choose the right combination for their applications. This paper aims at (i) quantitatively comparing various traffic shapers and their combinations, (ii) summarizing, classifying, and extending the architectures of individual and combined traffic shapers and their Network calculus (NC)-based performance analysis methods, and (iii) filling the gap in the timing analysis research on handling ATS and CBS used for different priority queues, and two novel hybrid architectures of combined traffic shapers, i.e., TAS+ATS+SP and TAS+ATS+CBS when ATS and CBS used at the same queue. A large number of experiments, using both synthetic and realistic test cases, are carried out for quantitative performance comparisons of various individual and combined traffic shapers, from the perspective of upper bounds of delay, backlog, and jitter. To the best of our knowledge, we are the first to quantitatively compare the performance of the main traffic shapers in TSN. The paper aims at supporting the researchers and practitioners in the selection of suitable TSN sub-protocols for their use cases.

We propose a Software-Defined Network (SDN)based approach for ultra-fast recovery of Time Sensitive Networks (TSN) in the case of failure events. We exploit the Source Routing paradigm for explicit path control and the creation of a stateless TSN data plane. We further propose a TSN failure recovery routing heuristic used to minimise link congestion, while we also introduce the concept of TSN subgraphs to quickly reschedule the flows traversing the problematic area. We evaluate our approach using SDN-based Source Routing and Linux-based TSN scheduling integrated into Mininet.

Time-sensitive networking (TSN) is an upcoming set of Ethernet standards designed for real-time and safety-critical Internet-of-Things (IoT) applications in automotive, aerospace, and industrial automation domains. With the combination, complexity, and flexibility of flow control mechanisms in TSN connected systems, the performance analysis for mixed-critical messages is becoming a difficult challenge. The flexible window-based gate control list (GCL) scheduling model has been proposed as a relaxation to assumptions on frames-to-window allocation, mutually exclusive gates opening, and scheduled end systems and switches, which offers more flexibility in the configuration of GCLs. In this article, we are interested in providing a reliable verification method based on the network calculus theory to drive GCL configurations for TSN networks. To the best of our knowledge, this is the first performance analysis method suitable for the general flexible window-based GCLs in entire TSN networks, by reflecting the relative positional relationships of windows for same priority queues on consecutive nodes and constructing the window limitations into the shaper curve, in order to reduce the pessimism of the latency bounds. We validate the proposed method through Industrial IoT synthetics test cases and two large realistic cases, showing the significant reduction in pessimism on delay bounds, and the correctness and scalability by comparing with results from the previous work and simulation results.

Flow-based microfluidic biochips have attracted much attention in the EDA community due to their miniaturized size and execution efficiency. Previous research, however, still follows the traditional computing model with a dedicated storage unit, which actually becomes a bottleneck of the performance of biochips. In this article, we propose a distributed channel-storage architecture (DCSA) to cache fluid samples inside flow channels temporarily. Since distributed storage can be accessed more efficiently than a dedicated storage unit and channels can switch between the roles of transportation and storage easily, biochips with this architecture can achieve a higher execution efficiency even with fewer resources. Furthermore, we also address the flow-path planning that enables the manipulation of actual fluid transportation/caching on a chip. The simulation results confirm that the execution efficiency of a bioassay can be improved significantly, while the number of valves in the biochip can be reduced accordingly. Also, flow paths for transportation tasks can be constructed and planned automatically with minimum extra resources.

Electric drives are used to control electric motors, which are pervasive in industrial applications. In this paper we propose enhancing the electric drives to fulfil the role of fog nodes within a Fog Computing Platform (FCP). Fog Computing is envisioned as a realization of future distributed architectures in Industry 4.0. We identify the system-level requirements of such an FCP, including requirements that are extracted from the current architecture of drives, which we consider as a baseline. These requirements are then used to design a system-level architecture, which we model using the Architecture Analysis & Design Language (AADL). We identify the "technology bricks" (components such as hardware, software, middleware, services, methods and tools) needed to implement the FCP. The proposed fog-based architecture is then used to implement a Conveyor Belt industrial use case. We evaluate the resulting use case on several aspects, demonstrating the usefulness of the proposed fog-based approach. By developing the electric drives as fog nodes, that we call fogification, new offerings like programmability, analytics and connectivity to customer Clouds are expected to increase the added value. Increased flexibility allows drives to assume a larger role in industrial and domestic control systems, instrumenting thus also legacy systems by using drives as the data source.

Modern Advanced Driver-Assistance Systems (ADAS) merge critical and non-critical software functions with complex timing requirements and inter-dependencies onto the same integrated hardware platform. Real-time safety-critical automotive applications feature complex dependency chains between tasks (e.g., performing sensing, processing and actuation) which have to satisfy worst-case end-to-end latency constraints. The resulting scheduling problem requires both the assignment of tasks to the available cores of the platform and the computation static schedule tables for the real-time tasks, such that task deadlines, as well as end-to-end task chain constraints, are satisfied. We propose a heuristic approach based on Simulated Annealing (SA) which creates static schedule tables by simulating Earliest Deadline First (EDF) scheduling parameterized by task offsets and local deadlines decided by SA. We evaluate the proposed solution with real-world and synthetic test cases scaled to fit the future requirements of ADAS systems.

Demanding IoT application requirements such as high dependability and low latency, cannot be satisfied by centralized cloud computing when deploying these applications. Edge computing is emerging as an alternative to deploy demanding IoT applications closer to the edge of the network. However, with edge computing, available resources are distributed among different resource-constrained devices, which cannot host large monolithic applications. We propose a new hierarchical IoT application model, suitable for the distributed nature of edge computing. Thus, a task in the application is modeled using multiple configurations of smaller tasks, each with their own functionality level and resource requirements. For deployment we use a decentralized resource technical framework that finds a satisfiable task mapping on edge devices. Its functionality is inspired by an auction house, having the objectives of (i) deploying an application such that its requirements are met and (ii) empowers edge devices to be in control of their available resources. For the latter, we propose a new decision policy to help edge devices take better decisions regarding the use of local available resource. Our solution enables efficient device resource utilization when deploying IoT applications at the edge.

Time-Sensitive Networking (TSN) extends IEEE 802.1 Ethernet for safety-critical and real-time applications in several areas, e.g., automotive, aerospace or industrial automation. However, many of these systems also have stringent security requirements, and security attacks may impair safety. Given a TSN-based distributed architecture, a set of applications with tasks and messages, as well as a set of security and redundancy requirements, we are interested to synthesize a system configuration such that the real-time, safety and security requirements are satisfied. We use the Timed Efficient Stream Loss-Tolerant Authentication (TESLA) low-resource multicast authentication protocol to guarantee the security requirements, and redundant disjunct message routes to tolerate link failures. We consider that the tasks are scheduled using static cyclic scheduling and that the messages use the time-sensitive traffic class in TSN, which relies on schedule tables (called Gate Control Lists, GCLs) in the network switches. A configuration consists of the schedule tables for tasks as well as the disjoint routes and GCLs for messages. We propose a Constraint Programming-based formulation for this problem and we evaluate it on several test cases.

Time-Sensitive Networking (TSN) introduces standardized mechanisms that add real-time capabilities to IEEE 802.1 Ethernet networks. In particular, the Time-Aware Shaper (TAS) can be used to send frames in a deterministic fashion according to a predefined global schedule. Existing methods for generating the global communication schedule enforce isolation either in the time or in the space domain. This extended abstract presents a novel, more flexible window-based scheduling algorithm which removes the previously required isolation constraints for Scheduled Traffic (ST) by integrating worst-case delay analysis to guarantee bounded latency.

This article focuses on mixed-criticality applications with functions that have different timing requirements, i.e., hard real-time (HRT), soft real-time (SRT), and functions that are not time-critical (NC). The applications are implemented on distributed cyber-physical systems that use IEEE Time-sensitive Networking (TSN). TSN is the product of an IEEE effort to bring deterministic real-time capabilities to IEEE 802.3 Ethernet. TSN supports the convergence of multiple traffic types, i.e., critical, real-time, and regular “best-effort” traffic within a single network: Time-triggered (TT), where the messages are transmitted based on static schedule tables, Audio-video Bridging (AVB), for dynamically scheduled messages with a guaranteed bandwidth and bounded delays, and Best Effort (BE), for which no timing guarantees are provided. The HRT messages have deadlines, whereas we capture the quality-of-service for the SRT messages using “utility functions.” Given the network topology, the set of application messages, including their routing, and the set of available AVB classes, we are interested in determining the traffic type of each message, such that all the HRT messages are schedulable and the total utility for the SRT messages is maximized. We propose a Tabu Search-based metaheuristic to solve this optimization problem. The proposed proof-of-concept tool has been evaluated using several benchmarks, including two realistic test cases.

Industrial Internet of Things (IIoT) networks are considered the large-scale deployment of IoT devices for industrial applications such as smart manufacturing, harvesting and supply chain management. The Internet of Things (IoT) devices are typically connected over a wireless medium, given the large geographical distribution area and the increasing demand for flexible installations. In some cases, a combination of wired and wireless connectivity can be assumed as common practice. In both scenarios, wireless communications for IIoT networks is a fundamental component of the system architecture that needs to satisfy stringent requirements such as reliable connectivity and minimal delays. Therefore, the dependability of wireless communications for IIoT networks should be carefully studied to provide new solutions, which can guarantee that applications can meet their real-time and reliability requirements while optimizing the control capability of the overall network. This paper focuses on the dependable wireless communications in the IIoT networks, where wireless control and monitoring tasks need to meet stringent real-time and reliability constraints. After reviewing recent solutions and discussing their suitability for IIoT networks, we highlight the yet open challenges that needs to be tackled by both academia and industry.

Time-Sensitive Networking (TSN) is a collection of standards that extend Ethernet to support safety-critical and real-time applications. TSN integrates multiple traffic types, i.e., Time-Triggered (TT) traffic scheduled based on Gate-Control-Lists (GCLs), Audio-Video-Bridging (AVB) traffic that requires bounded latencies, and Best-Effort (BE) traffic, for which no guarantees are provided. This paper proposes a Network Calculus-based approach to determine the worst-case end-to-end delays of AVB traffic in a TSN network with both non-preemption and preemption modes. We consider the effects of TT traffic due to GCLs, "guard bands", i.e., time windows that block other traffic from transmitting, and preemption overhead on the service for AVB traffic. We provide a proof of non-overflow condition for AVB credit, which is used to control the AVB traffic transmission. The analysis method is evaluated on realistic test cases, and compared to related work.

Microfluidic laboratories-on-a-chip (LoCs) are replacing the conventional biochemical analyzers and are able to integrate the necessary functions for biochemical analysis on-chip. There are several types of LoCs, each having its advantages and limitations. In this paper we are interested in flow-based LoCs, in which a continuous flow of liquid is manipulated using integrated microvalves. By combining several microvalves, more complex units, such as micropumps, switches, mixers, and multiplexers, can be built. We consider that the architecture of the LoC is given, and we are interested in synthesizing an implementation, consisting of the binding of operations in the application to the functional units of the architecture, the scheduling of operations and the routing and scheduling of the fluid flows, such that the application completion time is minimized. To solve this problem, we propose a list scheduling-based application mapping (LSAM) framework and evaluate it by using real-life as well as synthetic benchmarks. When biochemical applications contain fluids that may adsorb on the substrate on which they are transported, the solution is to use rinsing operations for contamination avoidance. Hence, we also propose a rinsing heuristic, which has been integrated in the LSAM framework.

The automotive electronic architectures have moved from federated architectures, where one function is implemented in one ECU (Electronic Control Unit), to distributed architectures, consisting of several multicore ECUs. In addition, multicore ECUs are being adopted because of better performance, cost, size, fault-tolerance and power consumption. Automotive manufacturers use AUTomotive Open System ARchitecture (AUTOSAR) as the standardized software architecture for ECUs. With AUTOSAR, the functionality is modeled as a set of software components composed of subtasks, called runnables. In this paper we propose an approach for the automatic software functionality assignment to multicore distributed architectures, implemented as a software tool. The AUTOMAP, decides: the (i) mapping of software components to multicore ECUs, (ii) the assignment of runnables to the ECU cores, (iii) the clustering of runnables into tasks and (iv) the mapping of tasks to 'OS-Applications', such that timing and mapping constraints are satisfied. AUTOMAP has been developed to handle large industrialsized use cases, fine-grained realistic mapping and timing constraints, and to produce outputs that support the system engineer in the mapping task. We have successfully evaluated AUTOMAP on several realistic use cases from Volvo Trucks.

Flow-based microfluidic biochips have attracted much attention in the EDA community due to their miniaturized size and execution efficiency. Previous research, however, still follows the traditional computing model with a dedicated storage unit, which actually becomes a bottleneck of the performance of biochips. In this paper, we propose the first architectural synthesis framework considering distributed storage constructed temporarily from transportation channels to cache fluid samples. Since distributed storage can be accessed more efficiently than a dedicated storage unit and channels can switch between the roles of transportation and storage easily, biochips with this distributed computing architecture can achieve a higher execution efficiency even with fewer resources. Experimental results confirm that the execution efficiency of a bioassay can be improved by up to 28% while the number of valves in the biochip can be reduced effectively.

Microfluidic-based lab-on-a-chips have emerged as a popular technology for implementation of different biochemical test protocols used in medical diagnostics. However, in the manufacturing process or during operation of such chips, some faults may occur that leads to damage of the chip, which in turn results in wastage of expensive reagent fluids. In order to make the chip fault-tolerant, the state-of-the-art technique adopts simulated annealing (SA) based approach to synthesize a fault-tolerant architecture. However, the SA method is time consuming and non-deterministic with over-simplified model that usually derive sub-optimal results. Thus, we propose a progressive optimization procedure for the synthesis of fault-tolerant flow-based microfluidic biochips. Simulation results demonstrate that proposed method is efficient compared to the state-of-the-art techniques and can provide effective solutions in 88% (on average) less CPU time compared to state-of-the-art technique over three benchmark bioprotocols.

Microfluidic VLSI (mVLSI) biochips help perform biochemistry at miniaturized scales, thus enabling cost, performance and other benefits. Although biochips are expected to replace biochemical labs, including point-of-care devices, the off-chip pressure actuators and pumps are bulky, thereby limiting them to laboratory environments. To address this issue, researchers have proposed methods to reduce the number of offchip pressure sources, through integration of on-chip pneumatic control logic circuits fabricated using three-layer monolithic membrane valve technology. Traditionally, mVLSI biochip physical design was performed assuming that all of the control logic is off-chip. However, the problem of mVLSI biochip physical design changes significantly, with introduction of on-chip control, since along with physical synthesis, we also need to (i) perform on/off-chip control partitioning, (ii) on-chip control circuit design and (iii) the integration of on-chip control in the placement and routing design tasks. In this paper we present a design methodology for logic synthesis and physical synthesis of mVLSI biochips that use on-chip control. We show how the proposed methodology can be successfully applied to generate biochip layouts with integrated on-chip pneumatic control.

Routing-based synthesis for digital microfluidic biochips yields faster assay execution times compared to module-based synthesis. We show that routing-based synthesis can lead to deadlocks and livelocks in specific cases, and that dynamically detecting them and adjusting the probabilities associated with different droplet movements can alleviate the situation. We also introduce methods to improve the efficiency of wash droplet routing during routing-based synthesis, and to support nonreconfigurable modules, such as integrated heaters and detectors. We obtain increases in success rates when dealing with resource-constrained chips and reductions in average assay execution time.

This paper presents an overview of the ECSEL project entitled "Safe Cooperating Cyber-Physical Systems using Wireless Communication" (SafeCOP), which runs during the period 2016 - 2019. SafeCOP targets safety-related Cooperating Cyber-Physical Systems (CO-CPS) characterised by use of wireless communication, multiple stakeholders, dynamic system definitions (openness), and unpredictable operating environments. SafeCOP will provide an approach to the safety assurance of CO-CPS, enabling thus their certification and development. The project will define a runtime manager architecture for runtime detection of abnormal behaviour, triggering if needed a safe degraded mode. SafeCOP will also develop methods and tools, which will be used to produce safety assurance evidence needed to certify cooperative functions. SafeCOP will extend current wireless technologies to ensure safe and secure cooperation. SafeCOP will also contribute to new standards and regulations, by providing certification authorities and standardization committees with the scientifically validated solutions needed to craft effective standards extended to also address cooperation and system-of-systems issues. The project has 28 partners from 6 European countries, and a budget of about 11 million Euros corresponding to about 1,300 person-months.

Digital microfluidic biochips (DMBs) are microfluidic devices that manipulate droplets on an array of electrodes. Microfluidic operations, such as transport, mixing, and split, are performed on the electrode array to perform a biochemical application. All previous work assumes that the DMB architecture is given and most approaches consider a rectangular shape for the electrode array. However, nonrectangular application-specific architectures are common in practice. Hence, in this paper, we propose an approach to the synthesis of application-specific architectures, such that the cost of the architecture is minimized and the timing constraints of the biochemical application are satisfied. DMBs can be affected by permanent faults, which may lead to the failure of the biochemical application. Our approach introduces redundant electrodes to synthesize fault-tolerant architectures aiming at increasing the yield of DMBs. We have used a tabu search metaheuristic for this architecture synthesis problem. We have proposed a technique to evaluate the architecture alternatives visited during the search, in terms of their impact on the timing constraints of the application. The proposed architecture synthesis approach has been evaluated using several benchmarks.

Microfluidic biochips are replacing the conventional biochemical analyzers by integrating all the necessary functions for biochemical analysis using microfluidics. Biochips are used in many application areas, such as, in vitro diagnostics, drug discovery, biotech and ecology. The focus of this paper is on continuous-flow biochips, where the basic building block is a microvalve. By combining these microvalves, more complex units such as mixers, switches, multiplexers can be built, hence the name of the technology, “microfluidic Very Large-Scale Integration” (mVLSI). A roadblock in the deployment of microfluidic biochips is their low reliability and lack of test techniques to screen defective devices before they are used for biochemical analysis. Defective chips lead to repetition of experiments, which is undesirable due to high reagent cost and limited availability of samples. This paper presents the state-of-the-art in the mVLSI platforms and emerging research challenges in the area of continuous-flow microfluidics, focusing on testing techniques and fault-tolerant design.

Ethernet is a low-cost communication solution offering high transmission speeds. Although its applications extend beyond computer networking, Ethernet is not suitable for real-time and safety-critical systems. To alleviate this, several real-time Ethernet-based communication protocols have been proposed, such as TTEthernet, which is the focus of this paper. TTEthernet is suitable for mixed-criticality systems both in the safety and temporal domain. TTEthernet offers three traffic classes: static time-triggered (TT) traffic, dynamic traffic with bounded transmission rate (called "Rate Constrained", RC), and unbounded dynamic traffic ("Best-Effort", BE). In this paper we propose a novel worst-case end-to-end delay analysis of the RC traffic for TTEthernet systems. The proposed technique considerably reduces the pessimism of the analysis, compared to existing approaches. We have evaluated the new analysis using several test cases.

In this article, we are interested in implementing mixed-criticality real-time embedded applications on a given heterogeneous distributed architecture. Applications have different criticality levels, captured by their Safety-Integrity Level (SIL), and are scheduled using static-cyclic scheduling. According to certification standards, mixed-criticality tasks can be integrated onto the same architecture only if there is enough spatial and temporal separation among them. We consider that the separation is provided by partitioning, such that applications run in separate partitions, and each partition is allocated several time slots on a processor. Tasks of different SILs can share a partition only if they are all elevated to the highest SIL among them. Such elevation leads to increased development costs, which increase dramatically with each SIL. Tasks of higher SILs can be decomposed into redundant structures of lower SIL tasks. We are interested to determine (i) the mapping of tasks to processors, (ii) the assignment of tasks to partitions, (iii) the decomposition of tasks into redundant lower SIL tasks, (iv) the sequence and size of the partition time slots on each processor, and (v) the schedule tables, such that all the applications are schedulable and the development costs are minimized. We have proposed a Tabu Search-based approach to solve this optimization problem. The proposed algorithm has been evaluated using several synthetic and real-life benchmarks.

This paper focuses on the optimization of the TTEthernet communication protocol, which offers three traffic classes: time-triggered (TT), sent according to static schedules, rate-constrained (RC) that has bounded end-to-end latency, and best-effort (BE), the classic Ethernet traffic, with no timing guarantees. In our earlier work we have proposed an optimization approach named DOTTS that performs the routing, scheduling and packing / fragmenting of TT and RC messages, such that the TT and RC traffic is schedulable. Although backwards compatibility with classic Ethernet networks is one of TTEthernet's strong points, there is little research on this topic. However, in this paper, we extend our DOTTS optimization approach to optimize TTEthernet networks, such that not only the TT and RC messages are schedulable, but we also maximize the available bandwidth for BE messages. The proposed optimization has been evaluated on a space application case study.

In this paper we propose a new Tabu Search-based design optimization strategy for mixed-criticality systems implementing hard and soft real-time applications on the same platform. Our proposed strategy determined an implementation such that all hard real-time applications are schedulable and the quality of service of the soft real-time tasks is maximized. We have evaluated our strategy using an aerospace case study.

Microfluidic-based biochips are replacing the conventional biochemical analyzers, and are able to integrate onchip all the necessary functions for biochemical analysis using microfluidics. The digital microfluidic biochips are based on the manipulation of liquids not as a continuous flow, but as discrete droplets on an array of electrodes. Microfluidic operations, such as transport, mixing, split, are performed on this array by routing the corresponding droplets on a series of electrodes. Researchers have proposed several approaches for the synthesis of digital microfluidic biochips. All previous work assumes that the biochip architecture is given, and most approaches consider a rectangular shape for the electrode array. However, non-regular application-specific architectures are common in practice. Hence, in this paper, we propose an approach to the application-specific architecture synthesis. Our approach can also help the designer to increase the yield by introducing redundant electrodes to tolerate permanent faults. The proposed architecture synthesis algorithm has been evaluated using several benchmarks.

In this paper we are interested in flow-based microfluidic biochips, which are able to integrate the necessary functions for biochemical analysis on-chip. In these chips, the flow of liquid is manipulated using integrated microvalves. By combining several microvalves, more complex units, such as micropumps, mixers, and multiplexers, can be built. In this paper we propose, for the first time to our knowledge, a top-down control synthesis framework for the flow-based biochips. Starting from a given biochemical application and a biochip architecture, we synthesize the control logic that is used by the biochip controller to automatically execute the biochemical application. We also propose a control pin count minimization scheme aimed at efficiently utilizing chip area, reducing macro-assembly around the chip and enhancing chip scalability. We have evaluated our approach using both real-life applications and synthetic benchmarks.

Designs of flow-based microfluidic biochips are receiving much attention recently because they replace conventional biological automation paradigm and are able to integrate different biochemical analysis functions on a chip. However, as the design complexity increases, a flow-based microfluidic biochip needs more chip-integrated micro-valves, i.e., the basic unit of fluid-handling functionality, to manipulate the fluid flow for biochemical applications. Moreover, frequent switching of micro-valves results in decreased reliability. To minimize the valve-switching activities, we develop a network-flow based resource binding algorithm based on breadth-first search (BFS) and minimum cost maximum flow (MCMF) in architectural-level synthesis. The experimental results show that our methodology not only makes significant reduction of valve-switching activities but also diminishes the application completion time for both real-life applications and a set of synthetic benchmarks.

In this paper, we propose a technique to synthesize a cost-efficient distributed platform consisting of multiple Application Specific Instruction Set Processors (multi-ASIPs) running applications with strict timing constraints. Multi-ASIP platform synthesis is a non-trivial task for two reasons. Firstly, we need to know the WCET of tasks in target applications to derive platforms (including synthesized ASIPs) in which the tasks are schedulable. However, the WCET of tasks can be known only after the ASIPs are synthesized. We break this circular dependency by using a probability distribution of the WCET of a task (further referred to as the WCET uncertainty model), which takes into account the underlying microarchitectural configurations for the ASIP implementation. Secondly, the datapath area of the multi-ASIPs synthesized is an important design factor that contributes significantly towards the overall cost of the platform. We propose an area estimation model and a WCET uncertainty model that consider the effect of task datapath similarity. Based on these two models, we support the designer in exploring cost/performance trade-offs during the platform synthesis. We propose an Evolutionary Algorithm-based approach to solve this multiobjective optimization problem. The proposed approach has been evaluated using several benchmarks and it provides a number of multi-ASIP platform solutions exploring the trade-offs in the cost/performance design space.

Microfluidic biochips represent an alternative to conventional biochemical analyzers. A digital biochip manipulates liquids not as continuous flow, but as discrete droplets on a two-dimensional array of electrodes. Several electrodes are dynamically grouped to form a virtual device, on which operations are executed by moving the droplets. So far, researchers have ignored the locations of droplets inside devices, considering that all the electrodes forming the device are occupied throughout the operation execution. In this article, we consider a droplet-aware execution of microfluidic operations, which means that we know the exact position of droplets inside the modules at each time-step. We propose a Tabu Search-based metaheuristic for the synthesis of digital biochips with droplet-aware operation execution. Experimental results show that our approach can significantly reduce the application completion time, allowing us to use smaller area biochips and thus reduce costs.

Microfluidic biochips are replacing the conventional biochemical analyzers and are able to integrate the necessary functions for biochemical analysis on-chip. In this paper we are interested in flow-based biochips, in which the flow of liquid is manipulated using integrated microvalves. By combining several microvalves, more complex units, such as micropumps, switches, mixers, and multiplexers, can be built. The manufacturing technology, soft lithography, used for the flow-based biochips is advancing faster than Moore's law, resulting in increased architectural complexity. However, the designers are still using full-custom and bottom-up, manual techniques in order to design and implement these chips. As the chips become larger and the applications become more complex, the manual methodologies will not scale, becoming highly inadequate. Therefore, for the first time to our knowledge,we propose a top-down architectural synthesis methodology for the flow-based biochips. Starting from a given biochemical application and a microfluidic component library, we are interested in synthesizing a biochip architecture, i.e., performing component allocation from the library based on the biochemical application, generating the biochip schematic (netlist) and then performing physical synthesis (deciding the placement of the microfluidic components on the chip and performing routing of the microfluidic channels), such that the application completion time is minimized. We evaluate our proposed approach by synthesizing architectures for real-life applications as well as synthetic benchmarks.

We are interested in mapping hard real-time applications on distributed heterogeneous architectures. An application is modeled as a set of tasks, and we consider a fixed-priority preemptive scheduling policy. We target the early design phases, when decisions have a high impact on the subsequent implementation choices. However, due to a lack of information, the early design phases are characterized by uncertainties, e.g., in the worst-case execution times (wcets), or in the functionality requirements. We model uncertainties in the wcets using the “percentile method”. The uncertainties in the functionality requirements are captured using “future scenarios”, which are task sets that model functionality likely to be added in the future. In this context, we derive a mapping of tasks in the application, such that the resulted implementation is both robust and flexible. Robust means that the application has a high chance of being schedulable, considering the wcet uncertainties, whereas a flexible mapping has a high chance to successfully accommodate the future scenarios. We propose a Genetic Algorithm-based approach to solve this optimization problem. Extensive experiments show the importance of taking into account the uncertainties during the early design phases.

This paper focuses on mastering the automatic architecture synthesis and application mapping for heterogeneous massively-parallel MPSoCs based on customizable application-specific instruction-set processors (ASIPs). It presents an over-view of the research being currently performed in the scope of the European project ASAM of the ARTEMIS program. The paper briefly presents the results of our analysis of the main problems to be solved and challenges to be faced in the design of such heterogeneous MPSoCs. It explains which system, design, and electronic design automation (EDA) concepts seem to be adequate to resolve the problems and address the challenges. Finally, it introduces and briefly discusses the ASAM design-flow and its main stages.

In this paper we are interested in the timing analysis of mixed-criticality embedded real-time applications mapped on distributed heterogeneous architectures. Mixed-criticality tasks can be integrated onto the same architecture only if there is enough spatial and temporal separation among them. We consider that the separation is provided by partitioning, such that applications run in separate partitions, and each partition is allocated several time slots on a processor. Each partition can have its own scheduling policy. We are interested to determine the worst-case response times of tasks scheduled in partitions using fixed-priority preemptive scheduling. We have extended the state-of-the-art algorithms for schedulability analysis to take into account the partitions. The proposed algorithm has been evaluated using several synthetic and real-life benchmarks.

Distributed Real-time Embedded (DRE) systems are facing great challenges in networked, unpredictable and especially unsecured environments. In such systems, there is a strong need to enforce security on distributed computing nodes in order to guard against potential threats, while satisfying the real-time requirements. This paper proposes a Security-Aware Feedback Control Mechanism (SAFCM) which has the ability to dynamically change the security level to guarantee soft real-time requirements and make the security protection as strong as possible. In order to widely support distributed real-time systems, a multi-input multi-output feedback loop is designed and a model predictive controller is deployed based on an equation model that describes the dynamic behavior of the DRE systems. This control loop uses security level scaling to globally control the CPU utilization and security performance for the whole system. We propose a "security level" metric based on an evolution of cryptography algorithms used in embedded systems. Experimental results demonstrate that SAFCM not only has the excellent adaptivity compared to open-loop mechanism, but also has a better overall performance than PID control mechanism.

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.

This paper presents an approach to the synthesis of low-power fault-tolerant hard real-time applications mapped on distributed heterogeneous embedded systems. Our synthesis approach decides the mapping of tasks to processing elements, as well as the voltage and frequency levels for executing each task, such that transient faults are tolerated, the timing constraints of the application are satisfied, and the energy consumed is minimized. Tasks are scheduled using fixed-priority preemptive scheduling, while replication is used for recovery from multiple transient faults. Addressing energy and reliability simultaneously is especially challenging, since lowering the voltage to reduce the energy consumption has been shown to increase the transient fault rate. We presented a Tabu Search-based approach which uses an energy/reliability trade-off model to find reliable and schedulable implementations with limited energy and hardware resources. We evaluated the algorithm proposed using several synthetic and reallife benchmarks.

Microfluidic biochips are replacing the conventional biochemical analyzers and are able to integrate the necessary functions for biochemical analysis on-chip. There are several types of microfluidic biochips, each having its advantages and limitations. In this paper we are interested in flow-based biochips, in which the flow of liquid is manipulated using integrated microvalves. By combining several microvalves, more complex units, such as micropumps, switches, mixers, and multiplexers, can be built. Although researchers have proposed significant work on the system-level synthesis of droplet-based biochips, which manipulate droplets on a two-dimensional array of electrodes, no research on system-level synthesis of flow-based bioch-ips has been reported so far. The focus has been on application modeling and component-level simulation. Therefore, for the first time to our knowledge, we propose a system-level modeling and synthesis approach for flow-based biochips. We have developed a topology graph-based model of the biochip architecture, and we have used a sequencing graph to model the biochemical applications. We consider that the architecture of the biochip is given, and we are interested to synthesize an implementation, consisting of the binding of operations in the application to the functional units of the architecture, the scheduling of operations and the routing and scheduling of the fluid flows, such that the application completion time is minimized. We propose a List Scheduling-based heuristic for solving this problem. The proposed heuristic has been evaluated using two real-life case studies and a set of four synthetic benchmarks.

In this paper we address the mapping of mixedcriticality hard real-time applications on distributed embedded architectures. We assume that the architecture provides both spatial and temporal partitioning, thus enforcing enough separation between applications. With temporal partitioning, each application runs in a separate partition, and each partition is allocated several time slots on the processors where the application is mapped. The sequence of time slots for all the applications on a processor are grouped within a Major Frame, which is repeated periodically. We assume that the applications are scheduled using static-cyclic scheduling. We are interested to determine the task mapping to processors, and the sequence and size of the time slots within the Major Frame on each processor, such that the applications are schedulable. We have proposed a Tabu Search-based approach to solve this optimization problem. The proposed algorithm has been evaluated using several synthetic and real-life benchmarks.

In this paper we are interested to implement mixed-criticality hard real-time applications on a given heterogeneous distributed architecture. Applications have different criticality levels, captured by their Safety-Integrity Level (SIL), and are scheduled using static-cyclic scheduling. Mixed-criticality tasks can be integrated onto the same architecture only if there is enough spatial and temporal separation among them. We consider that the separation is provided by partitioning, such that applications run in separate partitions, and each partition is allocated several time slots on a processor. Tasks of different SILs can share a partition only if they are all elevated to the highest SIL among them. Such elevation leads to increased development costs. We are interested to determine (i) the mapping of tasks to processors, (ii) the assignment of tasks to partitions, (iii) the sequence and size of the time slots on each processor and (iv) the schedule tables, such that all the applications are schedulable and the development costs are minimized. We have proposed a Tabu Search-based approach to solve this optimization problem. The proposed algorithm has been evaluated using several synthetic and real-life benchmarks.

Microfluidic biochips are replacing the conventional biochemical analyzers, and are able to integrate on-chip all the basic functions for biochemical analysis. The "digital" microfluidic biochips are manipulating liquids not as a continuous flow, but as discrete droplets on a two-dimensional array of electrodes. Basic microfluidic operations, such as mixing and dilution, are performed on the array, by routing the corresponding droplets on a series of electrodes. So far, researchers have assumed that these operations are executed on rectangular virtual devices, formed by grouping several adjacent electrodes. One drawback is that all electrodes are considered occupied during the operation execution, although the droplet uses only one electrode at a time. Moreover, the operations can actually execute by routing the droplets on any sequence of electrodes on the array. Hence, in this paper, we eliminate the concept of virtual modules and allow the droplets to move on the chip on any route during operation execution. Thus, the synthesis problem is transformed into a routing problem. We propose an approach derived from a Greedy Randomized Adaptive Search Procedure (GRASP) and we show that by considering routing-based synthesis, significant improvements can be obtained in the application completion time. The proposed heuristic has been evaluated using two real-life case studies and ten synthetic benchmarks.

In this paper we are interested in mixed hard/soft real-time fault-tolerant applications mapped on distributed heterogeneous architectures. We use the Earliest Deadline First (EDF) scheduling for the hard real-time tasks and the Constant Bandwidth Server (CBS) for the soft tasks. The bandwidth reserved for the servers determines the quality of service (QoS) for soft tasks. CBS enforces temporal isolation, such that soft task overruns do not affect the timing guarantees of hard tasks. Transient faults in hard tasks are tolerated using checkpointing with rollback recovery. We have proposed a Tabu Search-based approach for task mapping and CBS bandwidth reservation, such that the deadlines for the hard tasks are satisfied, even in the case of transient faults, and the QoS for the soft tasks is maximized. Researchers have used fixed execution time models, such as the worst-case execution times for hard tasks and average execution times for soft tasks. However, we show that by using stochastic execution times for soft tasks, significant improvements can be obtained. The proposed strategy has been evaluated using an extensive set of benchmarks.

Microfluidic biochips are replacing the conventional biochemical analyzers, and are able to integrate on-chip all the necessary functions for biochemical analysis. The "digital" microfluidic biochips are manipulating liquids not as a continuous flow, but as discrete droplets, and hence they are highly reconfigurable and scalable. A digital biochip is composed of a two-dimensional array of cells, together with reservoirs for storing the samples and reagents. Several adjacent cells are dynamically grouped to form a virtual device, on which operations are executed. During the execution of an operation, the virtual device can be reconfigured to occupy a different group of cells on the array. In this paper, we present a Tabu Search metaheuristic for the synthesis of digital microfluidic biochips, which, starting from a biochemical application and a given biochip architecture, determines the allocation, resource binding, scheduling and placement of the operations in the application. In our approach, we consider moving the modules during their operation, in order to improve the completion time of the biochemical application. The proposed heuristic has been evaluated using three real-life case studies and ten synthetic benchmarks.

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.

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.

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.

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.

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

We present a constraint logic programming (CLP) approach for synthesis of fault-tolerant hard real-time applications on distributed heterogeneous architectures. We address time-triggered systems, where processes and messages are statically scheduled based on schedule tables. We use process re-execution for recovering from multiple transient faults. We propose three scheduling approaches, which each present a trade-off between schedule simplicity and performance, (i) full transparency, (ii) slack sharing and (iii) conditional, and provide various degrees of transparency. We have developed a CLP framework that produces the fault-tolerant schedules, guaranteeing schedulability in the presence of transient faults. We show how the framework can be used to tackle design optimization problems.The proposed approach has been evaluated using extensive experiments.

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.

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

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.

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.

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.

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.

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.

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

In this paper we present an 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.

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.

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.