Search

Targeting global EDF scheduling, this paper proposes an 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 optimal algorithm with polynomial time complexity. We present a formal proof of the optimality of the proposed algorithm. We first address the single-segment task model and then extend to the multi-segment task model. Our extensive experiments through both simulation and actual implementation show that our proposed approach can significantly improve the schedulability.

Background Delivery of automatic electrical defibrillator (AED) by unmanned aerial vehicle like drones was suggested to improve early defibrillation for out-of-hospital cardiac arrest. We developed a drone-AED flight virtual simulator using 3-dimensional topographic and meteorological information. The goal of this study is to assess the effect of topography and weather on call to AED attach time in drone-AED program. Methods We included patients from 2013 to 2016 in Seoul, South Korea, registered in the Korean out-of-hospital cardiac arrest registry. We developed a drone-AED flight simulation using topographic information of Seoul for Euclidean flight pathway and topographic flight pathway including vertical flight to overcome high-rise structures. We used 4 drone flight scenarios according to weather conditions or visibility: flight and control advanced drone, flight advanced drone, control advanced drone and basic drone. Primary outcome was emergency medical service call to AED attach time. Secondary outcome was success rate of call to AED attachment within 5 or 10 minutes, and pre-arrival rate of drone-AED before AED delivery by ground ambulance. Results 16,596 patients were included. Median flight time of drone-AED was 2.6 and 1.0 minute for topographic flight simulation and Euclidean pathway. Call to AED attach time in topographic pathway was 7.0 minutes in flight and control advanced drone and 8.0 minutes in basic drone. The time in Euclidean pathway was 6.5 minutes in flight and control advanced drone and 7.0 minutes in basic drone. Pre-arrival rate of drone-AED in Euclidean pathway was 38.0% and 16.3% for flight and control advanced drone and basic drone. whereas, pre-arrival rate in the topographic pathway was 27.0% and 11.7%, respectively. Conclusions Drone-AED took longer call to AED attach time in basic drone than flight and control advanced drone. Pre-arrival rate of flight and control advanced drone was decreased in topographic flight pathway compared to Euclidean pathway. Trial registration This study used cases retrospectively registered in the Korean out-of-hospital cardiac arrest registry.

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.

In this paper, we describe a lightweight and accurate fault diagnosis method that detects oil leakage in automobile shock absorbers. Our approach includes a machine learning classifier as its base. These classifiers are quick and maintain a low computational load that are suitable for the automotive environment where only low-performance Electronic Control Units (ECUs) are available. However, these classifiers do not produce sufficiently accurate results when raw sensor data is used as the input. To solve this issue, we have developed an approach that firstly includes sensor data selection, where only sensors that have a strong impact on accuracy are used as input. And secondly, this reduced input dataset undergoes preprocessing using Fast Fourier Transform (FFT) to further improve accuracy. Thus, our methodology produces an oil leakage detection methodology for automobile shock absorbers that addresses the limitations of fault detection in an automotive system by being both lightweight and accurate.

For developing automotive systems, it is important to validate the system performance at the design phase. For this, the simulation methodology is commonly used for the validation of the automotive systems. However, if there is a gap between real performance and simulation result, developers need to go through the process of redesigning and implementing the system which increases the developing cost. For this, we have a novel simuation approach that gurantees functional and temporal correctness while enjoying the freedom of job scheduling. However we cannot apply this approach directly to the ROS2 cyber system which has become popular by its open source community and supporting real-time features because of different task execution behaviors. Therefore, we propose an extended approach which defines new system model for the cyber system based on ROS2 framework to keep the functional and temporal correct simulation approach on the ROS2 cyber system.

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.

Existing simulation methods cannot provide functionally and temporally correct simulations for the cyber-side of automotive systems since they do not correctly model temporal behaviours such as varying execution times and task preemptions. To address such limitations, our previous work proposes a novel simulation technique that guarantees the functional and temporal simulation correctness. However, the simulation technique is designed assuming a single core simulator. In this work, we extend the single core simulator targeting a multicore simulator to enhance the simulation capacity. In this multicore extension, a major challenge is the inter-core interferences in a multicore environment, which causes unpredictability of simulated job execution times, which in turn makes it hard to model the timings of the real cyber-side of an automotive system. To overcome the challenge, this paper empirically analyzes the inter-core interferences for typical automotive workloads and proposes a practical multicore extension approach, which can still provide a functionally and temporally correct simulation, without using complex inter-core isolation mechanisms. Our experimental study shows that the proposed multicore extension approach can significantly improve the simulation capacity over the previous single core simulator while still preserving simulation correctness.

Recent parallel programming frameworks such as OpenCL and OpenMP allow us to enjoy the parallelization freedom for real-time tasks. The parallelization freedom creates the time versus density tradeoff problem in fluid scheduling, i.e., more parallelization reduces thread execution times but increases the density. By system-widely exercising this tradeoff, we propose optimal parameter tuning of real-time tasks aiming at maximizing the schedulability of multicore fluid scheduling. Our experimental study by both simulation and actual implementation shows that the proposed approach well balances the time and the density, and results in up to 80 percent improvement of the 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.

Mixed-criticality systems integrate tasks with various levels of criticality onto the same hardware platform. Critical tasks require tight bounding of worst case latency at any cost, yet for non-critical tasks it is important to provide high performance as much as possible. In this paper, we take workload-driven approach and propose a novel workload-aware DRAM controller design for mixed-criticality system that can successfully achieve both of the conflicting demands in the presence of memory-intensive workloads. By using bank partitioning and request batching with prioritization, we provide tighter worst case latency bound for critical tasks and high performance and fairness for non-critical tasks. Our evaluation shows that the design achieves maximum 18% of performance improvement.

Existing multi-screening technologies have been limited to mirroring the current screen of the smartphone onto all the connected external display devices. In contrast, NANS (N-App N-Screen) technology is able to display different applications (N-App) on different multiple display devices (N-Screen) using only a smartphone. For such NANS services, this paper empirically shows that the thermal violation constraint is more critical than the battery life constraint. For preventing the thermal violation, the existing DTM (Dynamic Thermal Management) techniques cannot be used since they consider thermal violations as abnormal, and hence prevent them by severely throttling CPU frequencies resulting in serious QoS degradation. In NANS service scenarios it is normal to operate in high temperature ranges to continue services with acceptable QoS. Targeting such scenarios, we first propose a novel thermal prediction method specially designed for NANS services. Based on the novel thermal prediction method, we then propose a novel DTM technique called, &ldquo, thermal planning&rdquo, to provide sustainable NANS services with sufficiently high QoS without thermal violations.

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.

IEEE 802.15.4 is a global standard designed for emerging applications in low-rate wireless personal area networks (LRWPANs). The standard provides beneficial features, such as a beacon-enabled mode and guaranteed time slots for realtime 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: cluster-tree construction, nodes’ power configuration, and duty-cycle scheduling. Our holistic optimization method provides a solution for those problems so that all the real-time packets can be delivered within their deadlines in the most energyefficient way. Our simulation study shows that compared to existing methods, our holistic optimization can guarantee the on-time delivery of all real-time packets while significantly saving energy, consequently, significantly increasing the lifetime of the network. Furthermore, we show that our holistic optimization can be extended to take advantage of the spatial reuse of a radio frequency resource among long distance nodes and, hence, significantly increase the entire network capacity. Category: Ubiquitous computing

When developing a vehicle control system, simulation methods are widely used to validate the whole system in the early development phase. With this regard, the simulator should correctly behave just like the real parts that are not yet implemented while interacting with already implemented parts in real-time. However, most simulators cannot provide functionally and temporally accurate behaviors of the target system. In order to overcome this limitation, this paper proposes a novel real-time simulation technique that can efficiently simulate the temporal behavior as well as the functional behavior of the simulation target system.Keywords: vehicle control system, real-world interaction, simulation correctness, task modeling, timing constraints Copyright© ICROS 2015 I. 서론무인 자율 주행 자동차 등의 자동차 제어 시스템과 같이 크고 복잡한 내장형 컴퓨팅 시스템이 개발될 때 실시간 성능 검증을 위하여 시뮬레이션 기법이 이용된다[1]. 현대 자동차의 경우, 서로 다른 5개의 네트워크에 연결된 70개 이상의 ECU (Electronic Control Unit)를 가지기 때문에 복잡한 구조로 인하여 시뮬레이션을 이용한 검증 없이 한 번에 개발하는 것은 어렵다[2]. 여기에서 언급하는 시뮬레이션이란 대상 컴퓨팅 시스템 및 해당 시스템을 포함하는 네트워크와 네트워크에 연결된 다른 컴퓨팅 시스템 위에서 수행될 일부 혹은 모든 태스크들의 실시간 행태를 PC (Personal Computer) 등의 범용 컴퓨팅 장비에서 모사하는 것을 의미한다. 그러나 시중의 “실시간 시뮬레이션”이라 칭하는 시뮬레이터는 단지 실세계를 모사하기 위한 기능성 검증에 치중할 뿐 타이밍 검증은 전혀 고려되지 않는다. 그렇기 때문에 이미 실제로 개발되어진 시스템과 함께 시뮬레이션 할 때 상호작용이 제대로 이루어지지 않아 정확하지 않은 결

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.

To be small and easy to carry, mobile devices canno t be equipped with large and highly capable input/output devices. In order to overcome these li mitations, this study proposes adaptive I/O switching technique as a general solution for explo iting full features of various external input/outpu t devices in lieu of tiny input/output devices in a s martphone. Unlike existing physical-layer connectio n based solutions or application-layer non-system sol utions, we propose a generalized solution at the mobile platform level. With this generalized soluti on, whatever activities of a smartphone can be resolution-adaptively displayed in an external disp lay device. Also, the generalized solution allows u s to use any kinds of external input devices for gene ral mobile applications even if they are not design ed so. Adaptive I/O Switching technique is actually im plemented on open source mobile platform and its effectiveness is demonstrated with several example scenarios.

For advanced features of next generation vehicles, the real-time programs in automotive embedded systems are dramatically increasing. For such large volume program codes, this paper proposes a novel framework to use high-density and low-cost nonvolatile memory, i.e., NAND flash memory, as a low-cost means of storing and executing hard real-time programs. Regarding this, one challenge is that NAND flash memory allows only 2 KB page-based read operations not per-byte random accesses, which requires RAM as working storage for code executions. This paper proposes two solutions, i.e., partitioned RAM solution and shared RAM solution, that minimize the RAM size required to deterministically guarantee the deadlines of all the hard real-time tasks. The proposed solutions are verified with the actual real-time programs for unmanned autonomous driving. To the best of our knowledge, this is the first work that allows us to use NAND flash memory for hard real-time program executions with the minimal usage of RAM.

This paper proposes a novel technique called mRT-PLRU (Multitasking 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 multitasking 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 versus execution time (and the corresponding optimal pinning/LRU combination) 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 determine the RAM sizes for multiple tasks such that their deadlines are probabilistically guaranteed with the minimal size of total RAM. 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 percent of RAM required by the industry-common shadowing approach.

When developing a CPS, since it is nature of CPS to interact with a physical system, CPS should be verified during its development process by real-time simulation supporting timely interactions between the simulator and existing implemented hardwares. Furthermore, when a part of a simulated system is implemented to real hardwares, i.e., incremental development, the simulator should aware changes of the simulated system and apply it automatically without manual description of the changes for effective development. For this, we suggest a real-time simulation framework including the concept of `port` which abstracts communication details between the tasks, and a scheduling algorithm for guaranteeing `real-time correctness` of the simulator.

NAND flash memory has been widely used as a nonvolatile storage for storing data. However, it is challenging to execute program codes on NAND flash memory, since NAND flash memory only supports page-based reads, not byte-level random reads. This paper proposes an automated process to find the optimal paging strategy 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 RAM. Moreover, the proposed process optimally configure the RT-PLRU 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 portable media player (PMP). 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 RAM.

Wireless sensor networks have great potentials to be applied to mission critical real-time applications such as target tracking, emergency detection, and disaster management. For such real-time applications, sensory data should be delivered within the end-to-end deadlines; otherwise, the data may become useless or misleading. In order to provide such deterministic guarantee of end-to-end deadlines, not only packet scheduling within a single hop but also routing across multiple hops have to be jointly considered. In this paper, we propose a combined scheduling and routing mechanism that provides a deterministic guarantee of end-to-end deadlines leveraging real-time scheduling and analysis techniques. Our experimental study shows that the proposed mechanism can accommodate a larger workload meeting all the end-to-end deadlines than a pretty comprehensive set of other possible solutions of scheduling and routing that are known to deterministically guarantee end-to-end deadlines.

Sensors have been increasingly used for many ubiquitous computing applications such as asset location monitoring, visual surveillance, and human motion tracking. In such applications, it is important to place sensors such that every point of the target area can be sensed by more than one sensor. Especially, many practical applications require 3-coverage for triangulation, 3D hull building, and etc. Also, in order to extract meaningful information from the data sensed by multiple sensors, those sensors need to be placed not too close to each other--minimum separation requirement. To address the 3-coverage problem with the minimum separation requirement, our recent work (Kim et al. 2008) proposes two heuristic methods, so called, overlaying method and TRE-based method, which complement each other depending on the minimum separation requirement. For these two methods, we also provide mathematical analysis that can clearly guide us when to use the TRE-based method and when to use the overlaying method and also how many sensors are required. To make it self-contained, in this paper, we first revisit the two heuristic methods. Then, as an extension, we present an ILP-based optimal solution targeting for grid coverage. With this ILP-based optimal solution, we investigate how much close the two heuristic methods are to the optimal solution. Finally, this paper discusses the impacts of the proposed methods on real-deployed systems using two example sensor systems. To the best of our knowledge, this is the first work that systematically addresses the 3-coverage problem with the minimum separation requirement.

As the elderly population increases, elderly care using inexpensive technological means is becoming critical. This paper presents our prototype system that provides real-time indoor tracking of elderly residents and their belongings, which is essential to assisting and securing their independent living. For high-fidelity real-time tracking, we propose novel scheduling algorithms. Our scheduling algorithms are designed by harmonizing both sensing and communication signals and leveraging location awareness and mobility consciousness in order to improve 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 a 20 cm error bound in the typical range of human mobility.

Recent computing applications such as videoconferencing and grid computing run their tasks on distributed computing resources connected through networks. For such applications, knowledge of the network status such as delay, jitter, and available bandwidth can help them select proper network resources to meet the Quality-of-Service (QoS) requirements. Also, the applications can dynamically change the resource selection if the current selection is found to experience poor performance. For such purposes, Internet Service Providers (ISPs) have started to instrument their networks with Network Measurement Infrastructures (NMIs) that run active measurement tasks periodically and/or on demand. However, one problem that most network engineers have overlooked is the measurement conflict problem, which happens when multiple active measurement tasks inject probing packets into the same network segment at the same time, resulting in misleading reports of network performance due to their combined effects. This paper proposes enhanced Earliest Deadline First (EDF) algorithms that allow "Concurrent Executions" to orchestrate offline/online measurement jobs in a conflict-free manner. The simulation study shows that our measurement scheduling mechanism can improve the schedulable utilization of offline measurement tasks up to 300 percent and the response time of on-demand jobs up to 50 percent. Further, we implement and deploy our scheduling mechanism in a real working NMI for monitoring the Internet2 Abilene network. As a case study, we show the utility of our algorithms in the widely used Network Weather Service (NWS).

Increased access to broadband networks has led to a fast-growing demand for voice and video over IP (VVoIP) applications such as Internet telephony (VoIP), videoconferencing, and IP television (IPTV). For pro-active troubleshooting of VVoIP performance bottlenecks that manifest to end-users as performance impairments such as video frame freezing and voice dropouts, network operators cannot rely on actual end-users to report their subjective quality of experience (QoE). Hence, automated and objective techniques that provide real-time or online VVoIP QoE estimates are vital. Objective techniques developed to-date estimate VVoIP QoE by performing frame-to-frame peak-signal-to-noise ratio (PSNR) comparisons of the original video sequence and the reconstructed video sequence obtained from the sender-side and receiver-side, respectively. Since processing such video sequences is time consuming and computationally intensive, existing objective techniques cannot provide online VVoIP QoE. In this paper, we present a novel framework that can provide online estimates of VVoIP QoE on network paths without end-user involvement and without requiring any video sequences. The framework features the "G AP-model", which is an offline model of QoE expressed as a function of measurable network factors such as bandwidth, delay, jitter, and loss. Using the GAP-model, our online framework can produce VVoIP QoE estimates in terms of "Good", "Acceptable", or "Poor" (GAP) grades of perceptual quality solely from the on-line measured network conditions.

This paper addresses the search and track coordination problems of multiple shipboard radars. The proposed approach first exploits the physical characteristics of a single phased array radar to improve its effective capacity. Its effective capacity is abstracted by a closed-form equation called a schedulability envelope. Using the schedulability envelope for each radar, we deal with search and track coordination as a relative-load-balancing problem in a multi-resource environment. The simulation results show that the proposed approach significantly improves the overall capacity of a multi-ship multi-radar system.

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.

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. These mechanisms 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 for local decision inaccuracies 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 up to 50 percent (12 flows versus 18 flows).

This paper describes a stochastic analysis framework which computes the response time distribution and the deadline miss probability of individual tasks, even for systems with a maximum utilization greater than one. The framework is uniformly applied to fixed-priority and dynamic-priority systems and can handle, tasks with arbitrary relative deadlines and execution time distributions.

Many application level qualities are functions of available computation resources. Recent studies have handled the computation resource allocation problem to maximize the overall application quality. However, such QoS problems are fundamentally multi-dimensional optimization problems that require extensive computation. Therefore, online usage of optimization procedures may significantly reduce the computation resource available for applications. This raises the question of how to best use the optimization procedures for dynamic real-time task sets. In dynamic real-time systems, it is important to improve the performance by re-allocating the resources adapting to dynamic situations. However, the overhead of changing task parameters (i.e., algorithms and frequencies) for resource re-allocation is non-negligible in many applications. Thus, too frequent change of resource allocation may not be desirable. This paper proposes a method called service classes configuration to address the QoS problem with dynamic arrival and departure of tasks. The method avoids online usage of optimization procedures by offline designing templates (called service classes) of resource allocation, which will be adaptively used depending on online situations. The service classes are designed by best trading-off the accuracy of dynamic adaptation against the overhead of resource re-allocation. A simplified radar application is used as an illustrative example.

In many practical real-time applications, there is a given set of task frequencies (i.e., inverse of task periods) corresponding to predetermined QoS options that the applications can choose. For example, in audio applications, the typical choices of playback frequencies are for CD quality, radio quality, and phone quality. Similar configurations can be found in streaming video and in control applications. In such systems, applications dynamically arrive requesting one of the periods provided by the QoS manager. Thus, the accurate and efficient online schedulability test is essential for any task set whose periods are chosen from the QoS period set. For this purpose, we propose new utilization bounds as a function of given QoS periods. As long as there is a set of given periods that can be chosen by applications, the bounds developed can be used by the QoS manager to quickly determine the schedulability of dynamic applications.

Cache memory is used in almost all computer systems today to bridge the ever increasing speed gap between the processor and main memory. However, its use in multitasking computer systems introduces additional preemption delay due to the reloading of memory blocks that are replaced during preemption. This cache-related preemption delay poses a serious problem in realtime computing systems where predictability is of utmost importance. We propose an enhanced technique for analyzing and thus bounding the cache-related preemption delay in fixed-priority preemptive scheduling focusing on instruction caching. The proposed technique improves upon previous techniques in two important ways. First, the technique takes into account the relationship between a preempted task and the set of tasks that execute during the preemption when calculating the cache-related preemption delay. Second, the technique considers the phasing of tasks to eliminate many infeasible task interactions. These two features are expressed as constraints of a linear programming problem whose solution gives a guaranteed upper bound on the cache-related preemption delay. This paper also compares the proposed technique with previous techniques using randomly generated task sets. The results show that the improvement on the worst-case response time prediction by the proposed technique over previous techniques ranges between 5 percent and 18 percent depending on the cache refill time when the task set utilization is 0.6. The results also show that as the cache refill time increases, the improvement increases, which indicates that accurate prediction of cache-related preemption delay by the proposed technique becomes increasingly important if the current trend of widening speed gap between the processor and main memory continues.

In multi-tasking real-time systems, inter-task cache interference due to preemptions degrades schedulability as well as performance. To address this problem, we propose a novel scheduling scheme, called limited preemptive scheduling (LPS), that limits preemptions to execution points with small cache-related preemption costs. Limiting preemptions decreases the cache-related preemption costs of tasks but increases blocking delay of higher priority tasks. The proposed scheme makes an optimal trade-off between these two factors to maximize the schedulability of a given task set while minimizing cache-related preemption delay of tasks. Experimental results show that the LPS scheme improves the maximum schedulable utilization by up to 40\% compared with the traditional fully preemptive scheduling (FPS) scheme. The results also show that up to 20\% of processor time is saved by the LPS scheme due to reduction in the cache-related preemption costs. Finally, the results show that both the improvement of schedulability and the saving of processor time by the LPS scheme increase as the speed gap between the processor and main memory widens.

We propose a new framework for the link assignment (i.e., topological design) problem that arises from the use of intersatellite links (ISL's) in low-earth orbit (LEO) satellite networks. In the proposed framework, we model an LEO satellite network as a finite state automaton (FSA), where each state corresponds to an equal-length interval in the system period of the LEO satellite network. This FSA-based framework allows the link assignment problem in LEO satellite networks to be treated as a set of link assignment problems in fixed topology networks. Within this framework, we study various link assignment and routing schemes. In particular, both regular link assignment and link assignment optimized by simulated annealing are considered. For each link assignment, both static and dynamic routing schemes are considered. Our simulation results show that the optimized link assignment combined with static routing achieves the best performance in terms of both newly initiated call blocking probability and ongoing call blocking probability. The results also show that when the link assignment is the same, static routing gives better performance than dynamic routing since the latter requires a substantial amount of time to stabilize its routing table after a state transition.

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.

We propose a new real-time simulation framework for cyber-physical systems (CPSs). It can efficiently dispatch simulation events for real-time simulation of complex events. It can also be easily reconfigured to adapt to various development steps.

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.

The automotive design paradigm is shifting from the "one-function on one ECU (Electronic Control Unit)" paradigm toward the "multi-function on one ECU" paradigm to reduce the ever increasing number of ECUs in a vehicle. In order to support such paradigm shift, this paper proposes a HW (hardware) resource componentizing technique that provides the illusion of a physically isolated ECU component for each automotive SW (software) component even when a multi-function ECU is actually shared by multiple concurrent SW components. With this technique, each SW component's physical properties such as timing behavior can be invariant with its surrounding SW components and hence the automaker can easily compose and verify a complex future automotive system. In order to effectively realize this HW resource componentizing, we propose an"active window based share provisioning" that provides a HW share to a SW component only when it is active. This way, the ECU capacity can be divided not only in the spatial (i.e., share) domain but also in the temporal domain, providing a large number of fine-granular HW components for serving a large number of SW components. The effectiveness of the proposed HW com-ponentizing technique is validated through both simulation and actual implementation with real automotive workload.

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.

Fair queueing algorithms based on Generalized Processor Sharing (GPS) provide sessions with instantaneous fair sharing of server capacity, as well as guaranteed service rate and delay. The instantaneous fair sharing distributes server capacity to currently back-logged sessions in proportion to their weights regardless of the amount of service that the sessions received in the past. From a long-term perspective, however, this type of sharing leads to a different quality of service to sessions even if they have the same weight, since it provides only the instantaneous capacity sharing without considering the accumulated service delay and bandwidth. To minimize such long-term unfairness, we propose a delay and bandwidth normalized scheduling model in which the concept of Value of Service (VoS) is defined from the aspects of both delay and bandwidth. Performance comparisons between the proposed algorithm and traditional fair queueing algorithms show that the proposed algorithm provides better long-term fairness among sessions and is more adaptive to sessions with dynamic traffic patterns without compromising the guarantees of service rate and delay.

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.

For advanced features of next generation vehicles, the real-time programs in automotive embedded systems are dramatically increasing. For such large volume program codes, this paper proposes a novel framework to use high-density and low-cost nonvolatile memory, i.e., NAND flash memory, as a low-cost mean of storing and executing hard real-time programs. Regarding this, one challenge is that NAND flash memory allows only 2KB page-based read operations not per-byte random access, which requires RAM as working storage for code executions. In order to minimize the expensive RAM requirements, the proposed framework optimally partitions the RAM for multiple hard real-time tasks and optimally determines the pinning/LRU combination for each RAM partition such that all task deadlines are deterministically guaranteed. The proposed framework is verified with the actual real-time programs for unmanned autonomous driving. To the best of our knowledge, this is the first work that allows us to use NAND flash memory for hard real-time program executions with the minimal usage of RAM.

The decay usage scheduler pursues long-term fairness in terms of both service bandwidth and service delay, in contrast to GPS (generalized processor sharing)-based schedulers pursuing short-term fairness only in terms of service bandwidth. Due to this bandwidth-delay-balancing characteristic of the decay usage scheduler, I/O-bound interactive processes are preferred to CPU-bound processes, resulting in fairness and better system utilization autonomously. However, there is no firm understanding of the mixed effects of the decay usage parameters on the service performance. This paper empirically analyzes their effects in terms of the resulting service bandwidth and service delay. Such analysis and understanding provides a basis of controlling the decay usage parameters for desirable service provision as required by applications.