Search

Due to the complex computation requirements of autonomous car functions, high-performance ECUs are inevitable for the future automotive system architecture. However, it has been reported that high-performance ECUs are usually more susceptible to the soft-error due to the technology scaling. One of the key methods to tolerate these soft errors (i.e. transient faults) is the lockstep mechanism based on the hardware redundancy. However, since this uses multiple redundant cores to execute a single program, it is very inefficient in terms of resource usage. To cope with this drawback, a new feature, ‘Lockstep/Performance mode switch' was introduced. It aims to guarantee safety for safety-critical tasks using the lockstep and maximize throughput for non-critical tasks using different cores for different tasks. This paper proposes a real-time scheduling method in order to efficiently use this new feature following the previous work. We first propose a condition of Periodic Resource Model(PRM) that avoids pessimism while we construct a PRM with the harmonic task set. Then, we partition the given input set into multiple PRMs where each PRM possesses a harmonic task set and has the optimal PRM period and budget. Consequently, The proposed method achieves optimal maximum schedulable utilization, which is more resource-efficient than the previous work.

Throughout the last decade, the importance of parallel computing has risen greatly to match the ever-increasing computational demand. Frameworks such as OpenMP and OpenCL allow easy parallelization of computing tasks into desirable number of threads, opening up a chance to greatly utilize the parallel computing resources. We call this "parallelization freedom". However, this does not come for free, as parallelization overhead increase with parallelization option (i.e. the number of thread each task is parallelized). Thus parallelization option must be carefully decided to better utilize a given computing resource. This paper addresses the problem of assigning parallelization option to each task for global FP scheduler. For this, we extend the approaches made by Cho, which is limited to the global EDF scheduler case. We prove that a conditionally optimal parallelization assignment of parallelization option also exists for the global FP case. Through extensive simulations, we show a significant improvement of schedulability.

Targeting global EDF scheduling, this paper proposes a conditionally optimal algorithm for parallelizing tasks with parallelization freedom. For this, we extend the interference-based sufficient schedulability analysis and derive monotonic increasing properties of both tolerance and interference for the schedulability. Leveraging those properties, we propose a one-way search based conditionally optimal algorithm with polynomial time complexity. Our extensive experiments through both simulation and actual implementation show that our proposed approach can significantly improve the schedulability up to 60 percent.

Compared to existing multi-screening techniques which are only able to display identical images on different display devices, NANS (N-App N-Screen) technology provides better convenience to users by displaying multiple applications on different display devices simultaneously. However, in order to commercialize the NANS technology, thermal issues by rapid temperature increase have to be solved prior to battery issues by massive power consumption. As the first step of the thermal management for NANS services using NANS technology, this paper proposes a novel thermal prediction method which considers 1) thermal interaction among the multi-core CPU and the display interface chipsets and 2) thermal jumps and drops when changing the operating frequency of multi-core CPU. Experimental results show that our thermal prediction method provides much more accuracy than existing methods when the smart phone is operated especially at high temperature ranges by NANS services.

NAND flash memory is widely used in embedded systems domain due to its non-volatility, low-power consumption, high degree of integration, and shock resistance. However, NAND flash memory only supports page-base read/write operations, to execute program codes from NAND flash memory, RAM whose per-byte price is much higher than that of NAND flash memory is essential. For the cost efficiency, there are researches for minimizing required RAM size to execute real-time tasks. However, since they do not consider read disturb errors, they have a limitation in terms of reliability. Therefore, in this paper, we propose an approach to execute hard real-time tasks on NAND flash memory with minimal RAM size while considering read disturb errors. The suggested approach requires 40% less RAM pages than Shadowing approach, and 36% more RAM pages than HRT-PLRU approach.

The current simulation tools used in the automotive industry do not correctly model timing behaviors of cyber-systems such as varying execution times and preemptions. Thus, they cannot correctly predict the real control performance. Motivated by this limitation, this paper proposes functionally and temporally correct simulation for the cyber-side of an automotive system. The key idea is to keep the data and time correctness only at physical interaction points and enjoy freedom of scheduling simulated jobs for all other cases. This way, the proposed approach significantly improves the real-time simulation capacity of the state-of-the-art simulation methods while keeping the functional and temporal correctness.

Past researches on multicore scheduling assume that a computational unit has already been parallelized into a prefixed number of threads. However, with recent technologies such as OpenCL, a computational unit can be parallelized in many different ways with runtime selectable numbers of threads. This paper proposes an optimal algorithm for parallelizing and scheduling a set of parallel tasks with multiple parallelization options on multiple CPU cores. The proposed algorithm is validated through both simulation and actual implementation. To the best of our knowledge, this is the first work addressing the problem of scheduling real-time tasks with multiple parallelization options on multiple CPU cores.

Integrated vehicle safety system is a key issue when developing intelligent safety vehicles. In order to validate such complex systems before actual ECU implementation, ECU-in-the-Loop Simulation (EiLS) is widely used. However, current EiLS methods only simulate the functional behavior of the target system thus cannot validate the temporal behavior of the resulting system. Hence, this paper incorporates a real-time simulation technique such that the target system’s both functional and temporal correctness can be validated in the early development phase. For the demonstration purpose, we specifically show how our real-time simulation technique aids the development of the integrated vehicle safety system.

This paper introduces a global research collaboration project performed by a Korean-USA research group. The project aims at designing and implementing a run-time platform for reliable, safe, and secure cyber physical systems (CPS). The project consists of layered sub-projects including SoC design for reliable systems, virtualized software architecture for dynamically upgradable systems, and middleware architecture for safety critical networked applications. This paper describes the objectives of each sub-project and the current accomplishments.

The TDoA (Time Difference of Arrivals) based location tracking systems using the RF and ultrasonic signals often give unacceptable errors due to the line-of-sight limitation of the ultrasonic signal. Overcoming this limitation, this paper proposes a novel TDoA based location tracking technique that explicitly exploits the ultrasonic reflection scenarios in the target location estimation. The proposed system can achieve a high location accuracy with errors smaller than 23 cm even when the lines-of-sight of ultrasonic signals are blocked pretty often and hence they are received through reflections.

We propose a new simulation scheme for supporting smooth development of cyber-physical systems (CPSs) from all-simulated systems to all-real systems. For this, we introduce two functionalities which cyber physical simulation should provide.

The localization systems using Time Difference of Arrival (TDoA) of ultrasonic and RF signals are hard to be used in practical settings because of line-of-sight limitation of the ultrasonic signal. Overcoming this limitation, novel multi-lateration method that explicitly exploiting the ultrasonic reflections was proposed. This paper verifies the proposed method by testing in the actual practical settings. As a result, the proposed method estimates the target location with estimation error smaller than 30 cm.

Simulation methods are widely used when designing complex systems to reduce the development effort and cost. Especially when designing cyber-physical systems (CPSs), the importance of the simulation grows bigger and bigger. To simulate CPSs precisely, a holistic simulator is needed considering cyber and physical systems as a whole. In this paper, we clarify the limitations of the existing simulation techniques and tools when used as CPS simulators: (1) unable to reflect the realtime behavior of the system, (2) do not support interactions with external environments. To overcome these limitations, we specifically propose a two-level simulation architecture and an artificial delay concept. Then, we also address the issues to be considered when the simulator is running on a multi-core system. To apply our proposed technique with concrete application scenarios, we introduce our simulation framework targeting an automotive system simulator.

Welcome to Toyama, Japan, and the 17th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2011). The objective of the conference is to bring together researchers and developers from academia and industry to advance the technologies of embedded, real-time, and cyber-physical systems, and also ubiquitous computing applications. Therefore, following the tradition of RTCSA, the conference has three tracks, embedded systems, real-time systems, and ubiquitous computing/cyber-physical systems. RTCSA started as a workshop in 1994, became a conference in 1998, and officially joined IEEE as an IEEE conference in 2005. This year’s RTCSA expands the scope of the ubiquitous computing track to include cyber-physical systems, so that it becomes the ubiquitous computing/cyber-physical systems track. This year, we received a total of 79 submissions. The papers come from 26 countries and regions including Austria, Belgium, Brazil, China, Finland, France, Germany, Greece, India, Iran, Italy, Japan, Korea, Malaysia, Netherlands, Norway, Poland, Portugal, Singapore, Sweden, Switzerland, Taiwan, Thailand, Turkey, United Kingdom, and USA. Each submission was reviewed by at least three peer reviewers. Overall, the best 43 papers—25 regular papers (32% acceptance rate) and 18 short papers—were selected.

In this paper, we propose an optimization approach for robust control design with end-to-end response time constraints in a multi-resource cyber-physical systems (CPS). We introduce a rigorous performance metric for robust system design from the control theoretic viewpoint. Then, we investigate the impact of end-to-end response time analysis techniques on the control performance. We show that the traditional per-job response time analysis significantly degrades the control performance when real-time tasks visit a resource multiple times. We demonstrate that we can meaningfully improve the control performance by adopting the recently-developed per-resource response time analysis. Our simulation results verify the effectiveness of the proposed co-design framework.

IEEE 802.15.4 is a global standard designed for emerging applications in low-rate wireless personal area networks (LR-WPANs). The standard provides nice features such as a beacon-enabled mode and guaranteed time slots for real-time data delivery. However, how to optimally operate those features is still an open issue. For the optimal operation of the features, this paper proposes a holistic optimization method that jointly optimizes three cross-related problems: (1) cluster-tree construction, (2) nodes' power configuration, and (3) duty-cycle scheduling. Our holistic optimization method finds the solution for the three problems such that all the real time packets can be delivered within their deadlines in the most energy-efficient way. Our simulation study shows that, comparing with existing methods, our holistic optimization can guarantee the on-time delivery of all real-time packets while significantly saving the energy and hence significantly increasing the network lifetime.

This paper proposes software bridge mechanism which supports the UPnP, discovery protocol of various wireless devices. Using the proposed bridge mechanism, the user would be able to use diverse contents through heterogeneous devices according to his or her choice. In this paper, porting was done to Android platform in order to verify the proposed mechanisms, and in the process several function modules were newly designed and implemented. And we implemented the service sharing mechanism between heterogeneous devices by using the proposed mechanism.

This paper proposes a novel technique called mRT-PLRU (Multi-tasking Real-Time constrained combination of Pinning and LRU), which forms a generic framework to use inexpensive nonvolatile NAND flash memory for storing and executing real-time programs in multi-tasking environments. In order to execute multiple real-time tasks stored in NAND flash memory with the minimal usage of expensive RAM, the mRT-PLRU is optimally configured in two steps. In the first step, the per-task analysis finds the function of RAM size vs. execution time for each individual task. Using these functions for all the tasks as inputs, the second-step called a stochastic-analysis-in-loop optimization conducts an iterative convex optimization with the stochastic-analysis for the probabilistic schedulability check. As a result, the optimization loop can optimally allocate RAM to multiple tasks such that their deadlines are probabilistically guaranteed with the minimal usage of RAM. Moreover, the mRT-PLRU is optimally configured in a developer-transparent way without giving any burden to the program developer, which is essential for the embedded system industry under a high pressure of time-to-market. The usefulness of the developed technique is intensively verified through both simulation and actual implementation. Our experimental study shows that mRT-PLRU can save up to 80% of RAM required by the industry-common shadowing approach.

NAND flash memory has been widely used as a non-volatile storage for storing data. However, it requires a large amount of SRAM for executing program codes stored in it since it only supports page-based reads, not byte-level random reads. This paper proposes a new paging mechanism called RT-PLRU (real-time constrained combination of pinning and LRU) that allows program codes stored in NAND flash memory to be executed satisfying real-time requirements with minimal usage of SRAM. Moreover, the RT-PLRU is optimally configured in a developer-transparent way without giving any burden to the program developer. The developed technique is specifically applied to a media player program targeting a PMP (portable medial player). To the best of our knowledge, this is the first effort to use NAND flash memory as a code storage for storing and executing real-time programs with minimal usage of SRAM.

Reducing energy consumption is important for mobile embedded systems and one of its solutions is dynamic voltage scaling (DVS). In this paper, we examine how to achieve further energy saving for periodic real-time tasks with non-preemptible sections on EDF algorithm by using DVS. Previous algorithms use two speed levels to deal with run-time blocking situation. However, this paper proposes a multi-speed algorithm that exploits various speed levels depending on specific blocking situation to minimize energy consumption. Moreover, it also presents an enhanced multi-speed algorithm that further reduces the energy dissipation by dropping the speed level early and considering only remaining blocking time to compute a lower speed. We induced feasibility conditions for our algorithms and proved them. The experiments show that proposed algorithms achieve up to 70.8% energy saving compared to previous algorithms.

Advances in networking, sensors, and embedded devices have made it feasible to monitor and provide medical and other assistance to people in their homes. Aging populations will benefit from reduced costs and improved healthcare through assisted living based on these technologies. However, these systems challenge current state-of-the-art techniques for usability, reliability, and security. In this paper we present the PAS open architecture for assisted living, which allows independently developed third party components to collaborate. We discuss key technological issues in assisted living systems, such as tracking, fall detection, security and privacy; and results from our pilot study in a real assisted living facility are presented.

Scheduling periodic tasks that allow some instances to be skipped produces spare capacity in the schedule. Only a fraction of this spare capacity is uniformly distributed and can easily be reclaimed for servicing aperiodic requests. The remaining fraction of the spare capacity is non-uniformly distributed, and no existing technique has been able to reclaim it. We present a method for improving the response times of aperiodic tasks by identifying the non-uniform holes in the schedule and adding these holes as extra capacity to the capacity queue of the CASH mechanism. The non-uniform holes can account for a significant portion of spare capacity, and reclaiming this capacity results in considerable improvements to aperiodic response times.

Building real-time applications on 802.11 wireless networks is challenging because the medium access protocol is distributed and nodes contend for the channel nondeterministically. So far all attempts at providing real-time services in 802.11 require restrictive traffic assumptions such as periodicity. In this paper we describe distributed admission control, a modification to 802.11 that, when used with distributed prioritization, provides real-time guarantees for aperiodic packets. We show that barring external errors such as interference on the channel or incorrect priority scheduling this protocol guarantees deadlines will be met.

Monitoring network status such as end-to-end delay, jitter, and available bandwidth is important to support QoS-sensitive applications and timely detection of network anomalies like denial of service attacks. For this purpose, Internet service providers (ISPs) have started to instrument their networks with network measurement infrastructures (NMIs) that periodically run active measurement tasks using measurement servers located at strategic points in their networks. However, one problem that most network engineers have overlooked is the measurement conflict problem. Since active measurement tasks actively inject test packets to collect measurements along network paths, running multiple active measurements at the same time over the same path could result in misleading reports of network performance. We call this phenomenon a measurement conflict. Our recent observation of such measurement conflict motivates us to form a measurement task scheduling problem of meeting periodicity requirements, where real-time scheduling algorithms can play a role. The scheduling problem, however, is not exactly same as any of the existing scheduling problems in the realtime literature, because the problem involves multiple measurement servers running multiple measurement tasks whose conflict dependency propagates along the chains of paths. For this problem, we propose to use an EDF (earliest deadline first) heuristic but allowing "concurrent executions" if possible, to construct an offline schedule for a given measurement task set. Also, we propose a novel mechanism to flexibly use the offline schedule for minimizing the response time of dynamic on-demand measurement jobs. Further, we implement and deploy our scheduling algorithms in a real working NMI for monitoring Internet 2 Abilene network

This paper proposes a novel task model in which its physical and temporal parameters are specified as time-parameterized functions and their values are finally determined at the actual dispatch time. This model is clearly differentiated from the classical task model where parameters are fixed at the job release time. The new model better suits sensing tasks in tracking applications, since the sensor parameters such as field-of-view and measurement duration can be properly adjusted at the actual sensing time. The new model, however, creates the cyclic dependency between task parameters and scheduling behavior, that is, the task parameters depend on scheduling behavior and the latter in turn depends on the former. This cyclic dependency makes the schedulability check even more difficult. We handle this difficulty by iterative convergence and probabilistic schedulability envelope, which provides an efficient online schedulability check. The experimental study shows that the new model significantly improves the effective capacity of tracking systems without losing track accuracy

In order to satisfy and maintain service level agreements (SLAs), which demand high network availability and good network health, ISPs have started instrumenting their networks with network measurement infrastructures (NMIs) that are composed of dedicated measurement servers. Active measurements are frequently used in NMIs to regularly monitor network health and analyze the experience of end-user application traffic traversing the network. However, active measurements initiated by measurement servers need to be regulated. Unregulated active measurement traffic can cause an unpredictable negative impact on the actual application traffic. Also, running simultaneous conflicting active measurements on measurement servers could result in misleading reports of network performance. In this paper, we describe our active measurements scheduling framework called "OnTimeMeasure" that allows ISPs to regulate the amount of active measurement traffic injected into the network and also prevents conflicts in ongoing active measurements between measurement servers. OnTimeMeasure provides a simple scripting language interface to specify various measurement requirements such as physical topology of measurement server clusters, periodicity of the measurements, and properties of measurement tools. For a given measurement requirements script, OnTimeMeasure uses an efficient heuristic bin-packing algorithm to generate measurement timetables for orchestrating active measurements for a network involving multiple measurement servers, each hosting multiple measurement tools.

As the elderly population increases, the elderly care using inexpensive technological means becomes critical. This paper proposes novel scheduling algorithms for real-time indoor tracking of elderly residents, which is essential to assist and secure their independent living. Our scheduling algorithms are designed by harmonizing both sensing and communication signals and leveraging location-awareness and mobility-consciousness, in order to improve the tracking accuracy while reducing the energy consumption. We performed extensive experiments through both simulation and actual implementation. Our experimental result says that our scheduling algorithms can provide real-time tracking of residents within 20 cm error bound in the typical range of human mobility.

In this paper, we present a novel packet delivery mechanism called multi-path and multi-speed routing protocol (MMSPEED) for probabilistic QoS guarantee in wireless sensor networks. The QoS provisioning is performed in two quality domains, namely, timeliness and reliability. Multiple QoS levels are provided in the timeliness domain by guaranteeing multiple packet delivery speed options. In the reliability domain, various reliability requirements are supported by probabilistic multipath forwarding. All these for QoS provisioning are realized in a localized way without global network information by employing localized geographic packet forwarding augmented with dynamic compensation, which compensates the local decision inaccuracy as a packet travels towards its destination. This way, MMSPEED can guarantee end-to-end requirements in a localized way, which is desirable for scalability and adaptability to large scale dynamic sensor networks. Simulation results show that MMSPEED provides QoS differentiation in both reliability and timeliness domains and, as a result, significantly improves the effective capacity of a sensor network in terms of number of flows that meet both reliability and timeliness requirements.

In recent studies, using mobile elements (MEs) as mechanical carriers of data has been shown to be an effective way of prolonging sensor network life time and relaying information in partitioned networks. As the data generation rates of sensors may vary, some sensors need to be visited more frequently than others. In this paper, a partitioning-based algorithm is presented that schedules the movements of MEs in a sensor network such that there is no data loss due to buffer overflow. Simulation results show that the proposed Partitioning Based Scheduling (PBS) algorithm performs well in terms of reducing the minimum required ME speed to prevent data loss, providing high predictability in inter-visit durations, and minimizing the data loss rate for the cases when the ME is constrained to move slower than the minimum required ME speed.

We compare the performance of two routing schemes for LEO satellite networks through simulation. The two routing schemes represent static and dynamic routing for the case where the LEO satellite network is modeled as a finite state automaton (FSA). Each state in this FSA modeling corresponds to an equal-length interval within the period of the LEO satellite network. Modeling the LEO satellite network in this way allows us to consider the LEO satellite network as if it is a fixed topology network within each state. The routing table for the static routing is fixed within each state whereas that for the dynamic routing is updated continuously according to the shortest-path algorithm. The simulation results show that the static routing performs better in terms of newly initiated call blocking than the dynamic one. The results also show that the static routing gives lower ongoing call blocking probabilities than the dynamic counterpart since the former's pre-computed routing table is less susceptible to the abrupt topological change during a state transition.

We investigate a topological design and routing problem for low Earth orbit (LEO) satellite communication networks where each satellite can have a limited number of direct inter-satellite links (ISLs) to a subset of satellites within its line-of-sight. First, we model LEO satellite network as a FSA (finite state automaton) using satellite constellation information. Second, we solve a combined topological design and routing problem for each configuration corresponding to a state in the FSA. The topological design (or link assignment) problem deals with the selection of ISLs, and the routing problem handles the traffic distribution over the selected links to maximize the number of carried calls. This NP-complete mixed integer optimization problem is solved by a two-step heuristic algorithm that first solves the topological design problem, and then finds the optimal routing. The algorithm is iterated using the simulated annealing technique until the near-optimal solution is found. The link assignment table and the routing table that are pre-calculated off-line for each state are loaded into the satellites and a new set of these tables are retrieved at each state transition. The simulation result shows that the proposed method is applicable to practical LEO satellite networks.