Open Access. Powered by Scholars. Published by Universities.®

Computer Engineering Commons

Open Access. Powered by Scholars. Published by Universities.®

Articles 1 - 26 of 26

Full-Text Articles in Computer Engineering

Holistic Resource Allocation For Multicore Real-Time Systems, Meng Xu, Linh T.X. Phan, Hyon-Young Choi, Yuhan Lin, Haoran Li, Chenyang Lu, Insup Lee Apr 2019

Holistic Resource Allocation For Multicore Real-Time Systems, Meng Xu, Linh T.X. Phan, Hyon-Young Choi, Yuhan Lin, Haoran Li, Chenyang Lu, Insup Lee

Departmental Papers (CIS)

This paper presents CaM, a holistic cache and memory bandwidth resource allocation strategy for multicore real-time systems. CaM is designed for partitioned scheduling, where tasks are mapped onto cores, and the shared cache and memory bandwidth resources are partitioned among cores to reduce resource interferences due to concurrent accesses. Based on our extension of LITMUSRT with Intel’s Cache Allocation Technology and MemGuard, we present an experimental evaluation of the relationship between the allocation of cache and memory bandwidth resources and a task’s WCET. Our resource allocation strategy exploits this relationship to map tasks onto cores, and to ...


Data Freshness Over-Engineering: Formulation And Results, Dagaen Golomb, Deepak Gangadharan, Sanjian Chen, Oleg Sokolsky, Insup Lee May 2018

Data Freshness Over-Engineering: Formulation And Results, Dagaen Golomb, Deepak Gangadharan, Sanjian Chen, Oleg Sokolsky, Insup Lee

Departmental Papers (CIS)

In many application scenarios, data consumed by real-time tasks are required to meet a maximum age, or freshness, guarantee. In this paper, we consider the end-to-end freshness constraint of data that is passed along a chain of tasks in a uniprocessor setting. We do so with few assumptions regarding the scheduling algorithm used. We present a method for selecting the periods of tasks in chains of length two and three such that the end-to-end freshness requirement is satisfied, and then extend our method to arbitrary chains. We perform evaluations of both methods using parameters from an embedded benchmark suite (E3S ...


Generic Formal Framework For Compositional Analysis Of Hierarchical Scheduling Systems, Jalil Boudjadar, Jin Hyun Kim, Linh Thi Xuan Phan, Insup Lee, Kim G. Larsen, Ulrik Nyman May 2018

Generic Formal Framework For Compositional Analysis Of Hierarchical Scheduling Systems, Jalil Boudjadar, Jin Hyun Kim, Linh Thi Xuan Phan, Insup Lee, Kim G. Larsen, Ulrik Nyman

Departmental Papers (CIS)

We present a compositional framework for the specification and analysis of hierarchical scheduling systems (HSS). Firstly we provide a generic formal model, which can be used to describe any type of scheduling system. The concept of Job automata is introduced in order to model job instantiation patterns. We model the interaction between different levels in the hierarchy through the use of state-based resource models. Our notion of resource model is general enough to capture multi-core architectures, preemptiveness and non-determinism.


Multi-Mode Virtualization For Soft Real-Time Systems, Haoran Li, Meng Xu, Chong Li, Chenyang Lu, Christopher Gill, Linh T.X. Phan, Insup Lee, Oleg Sokolsky Apr 2018

Multi-Mode Virtualization For Soft Real-Time Systems, Haoran Li, Meng Xu, Chong Li, Chenyang Lu, Christopher Gill, Linh T.X. Phan, Insup Lee, Oleg Sokolsky

Departmental Papers (CIS)

Real-time virtualization is an emerging technology for embedded systems integration and latency-sensitive cloud applications. Earlier real-time virtualization platforms require offline configuration of the scheduling parameters of virtual machines (VMs) based on their worst-case workloads, but this static approach results in pessimistic resource allocation when the workloads in the VMs change dynamically. Here, we present Multi-Mode-Xen (M2-Xen), a real-time virtualization platform for dynamic real-time systems where VMs can operate in modes with different CPU resource requirements at run-time. M2-Xen has three salient capabilities: (1) dynamic allocation of CPU resources among VMs in response to their mode changes, (2) overload avoidance at ...


Mc-Adapt: Adaptive Task Dropping In Mixed-Criticality Scheduling, Jaewoo Lee, Hoon Sung Chwa, Linh T.X. Phan, Insik Shin, Insup Lee Oct 2017

Mc-Adapt: Adaptive Task Dropping In Mixed-Criticality Scheduling, Jaewoo Lee, Hoon Sung Chwa, Linh T.X. Phan, Insik Shin, Insup Lee

Departmental Papers (CIS)

Recent embedded systems are becoming integrated systems with components of different criticality. To tackle this, mixed-criticality systems aim to provide different levels of timing assurance to components of different criticality levels while achieving efficient resource utilization. Many approaches have been proposed to execute more lower-criticality tasks without affecting the timeliness of higher-criticality tasks. Those previous approaches however have at least one of the two limitations; i) they penalize all lower-criticality tasks at once upon a certain situation, or ii) they make the decision how to penalize lowercriticality tasks at design time. As a consequence, they underutilize resources by imposing an ...


Data Predictive Control Using Regression Trees And Ensemble Learning, Achin Jain, Francesco Smarra, Rahul Mangharam Sep 2017

Data Predictive Control Using Regression Trees And Ensemble Learning, Achin Jain, Francesco Smarra, Rahul Mangharam

Real-Time and Embedded Systems Lab (mLAB)

Decisions on how to best operate large complex plants such as natural gas processing, oil refineries, and energy efficient buildings are becoming ever so complex that model-based predictive control (MPC) algorithms must play an important role. However, a key factor prohibiting the widespread adoption of MPC, is the cost, time, and effort associated with learning first-principles dynamical models of the underlying physical system. An alternative approach is to employ learning algorithms to build black-box models which rely only on real-time data from the sensors. Machine learning is widely used for regression and classification, but thus far data-driven models have not ...


Process Algebraic Approach To The Schedulability Analysis And Workload Abstraction Of Hierarchical Real-Time Systems, Junkil Park, Insup Lee, Oleg Sokolsky, Dae Yon Hwang, Sojin Ahn, Jin-Young Choi, Inhye Kang Jul 2017

Process Algebraic Approach To The Schedulability Analysis And Workload Abstraction Of Hierarchical Real-Time Systems, Junkil Park, Insup Lee, Oleg Sokolsky, Dae Yon Hwang, Sojin Ahn, Jin-Young Choi, Inhye Kang

Departmental Papers (CIS)

Real-time embedded systems have increased in complexity. As microprocessors become more powerful, the software complexity of real-time embedded systems has increased steadily. The requirements for increased functionality and adaptability make the development of real-time embedded software complex and error-prone. Component-based design has been widely accepted as a compositional approach to facilitate the design of complex systems. It provides a means for decomposing a complex system into simpler subsystems and composing the subsystems in a hierarchical manner. A system composed of real-time subsystems with hierarchy is called a hierarchical real-time system

This paper describes a process algebraic approach to schedulability analysis ...


Extensible Energy Planning Framework For Preemptive Tasks, Jin Hyun Kim, Deepak Gangadharan, Oleg Sokolsky, Axel Legay, Insup Lee May 2017

Extensible Energy Planning Framework For Preemptive Tasks, Jin Hyun Kim, Deepak Gangadharan, Oleg Sokolsky, Axel Legay, Insup Lee

Departmental Papers (CIS)

Cyber-physical systems (CSPs) are demanding energy-efficient design not only of hardware (HW), but also of software (SW). Dynamic Voltage and and Frequency Scaling (DVFS) and Dynamic Power Manage (DPM) are most popular techniques to improve the energy efficiency. However, contemporary complicated HW and SW designs requires more elaborate and sophisticated energy management and efficiency evaluation techniques. This paper is concerned about energy supply planning for real-time scheduling systems (units) of which tasks need to meet deadlines. This paper presents a modelbased compositional energy planning technique that computes a minimal ratio of processor frequency that preserves schedulability of independent and preemptive ...


Vcat: Dynamic Cache Management Using Cat Virtualization, Meng Xu, Linh T.X. Phan, Hyon-Young Choi, Insup Lee Apr 2017

Vcat: Dynamic Cache Management Using Cat Virtualization, Meng Xu, Linh T.X. Phan, Hyon-Young Choi, Insup Lee

Departmental Papers (CIS)

This paper presents vCAT, a novel design for dynamic shared cache management on multicore virtualization platforms based on Intel’s Cache Allocation Technology (CAT). Our design achieves strong isolation at both task and VM levels through cache partition virtualization, which works in a similar way as memory virtualization, but has challenges that are unique to cache and CAT. To demonstrate the feasibility and benefits of our design, we provide a prototype implementation of vCAT, and we present an extensive set of microbenchmarks and performance evaluation results on the PARSEC benchmarks and synthetic workloads, for both static and dynamic allocations. The ...


Autov: An Automotive Testbed For Real-Time Virtualization, Meng Xu, Insup Lee Apr 2017

Autov: An Automotive Testbed For Real-Time Virtualization, Meng Xu, Insup Lee

Departmental Papers (CIS)

Timing isolation is critical for automotive systems. Real-time virtualization, such as RT-Xen, is a promising technique to integrate legacy automotive systems onto a powerful multi-core platform for achieving better performance and lower cost without breaking the timing isolation. However, the real-time virtualization has never been evaluated with real automotive applications in a non-simulation environment. In order to facilitate the evaluation of real-time virtualization for automotive systems, we propose the AutoV, an affordable and accessible automotive testbed for real-time virtualization. We present a case study to demonstrate the applications of the AutoV.


Analysis And Implementation Of Global Preemptive Fixed-Priority Scheduling With Dynamic Cache Allocation, Meng Xu, Linh Thi Xuan Phan, Hyon-Young Choi, Insup Lee Apr 2016

Analysis And Implementation Of Global Preemptive Fixed-Priority Scheduling With Dynamic Cache Allocation, Meng Xu, Linh Thi Xuan Phan, Hyon-Young Choi, Insup Lee

Departmental Papers (CIS)

We introduce gFPca, a cache-aware global pre-emptive fixed-priority (FP) scheduling algorithm with dynamic cache allocation for multicore systems, and we present its analysis and implementation. We introduce a new overhead-aware analysis that integrates several novel ideas to safely and tightly account for the cache overhead. Our evaluation shows that the proposed overhead-accounting approach is highly accurate, and that gFPca improves the schedulability of cache-intensive tasksets substantially compared to the cache-agnostic global FP algorithm. Our evaluation also shows that gFPca outperforms the existing cache-aware non- preemptive global FP algorithm in most cases. Through our implementation and empirical evaluation, we demonstrate the ...


Optimizing The Resource Requirements Of Hierarchical Scheduling Systems, Jin Hyun Kim, Axel Legay, Louis-Marie Traonouez, Abdeldjalil Boudjadar, Ulrik Nyman, Kim G. Larsen, Insup Lee, Jin-Young Choi Dec 2015

Optimizing The Resource Requirements Of Hierarchical Scheduling Systems, Jin Hyun Kim, Axel Legay, Louis-Marie Traonouez, Abdeldjalil Boudjadar, Ulrik Nyman, Kim G. Larsen, Insup Lee, Jin-Young Choi

Departmental Papers (CIS)

Compositional reasoning on hierarchical scheduling systems is a well-founded formal method that can construct schedulable and optimal system configurations in a compositional way. However, a compositional framework formulates the resource requirement of a component, called an interface, by assuming that a resource is always supplied by the parent components in the most pessimistic way. For this reason, the component interface demands more resources than the amount of resources that are really sufficient to satisfy sub-components. We provide two new supply bound functions which provides tighter bounds on the resource requirements of individual components. The tighter bounds are calculated by using ...


Cache-Aware Interfaces For Compositional Real-Time Systems, Linh T.X. Phan, Meng Xu, Insup Lee Dec 2015

Cache-Aware Interfaces For Compositional Real-Time Systems, Linh T.X. Phan, Meng Xu, Insup Lee

Departmental Papers (CIS)

Interface-based compositional analysis is by now a fairly established area of research in real-time systems. However, current research has not yet fully considered practical aspects, such as the effects of cache interferences on multicore platforms. This position paper discusses the analysis challenges and motivates the need for cache scheduling in this setting, and it highlights several research questions towards cache-aware interfaces for compositional systems on multicore platforms.


Towards Compositional Mixed-Criticality Real-Time Scheduling In Open Systems, Jaewoo Lee, Hoon Sung Chwa, Arvind Easwaran, Insik Shin, Insup Lee Dec 2015

Towards Compositional Mixed-Criticality Real-Time Scheduling In Open Systems, Jaewoo Lee, Hoon Sung Chwa, Arvind Easwaran, Insik Shin, Insup Lee

Departmental Papers (CIS)

Although many cyber-physical systems are both mixed-criticality system and compositional system, there are little work on intersection of mixed-criticality system and compositional system. We propose novel concepts for task-level criticality mode and reconsider temporal isolation in terms of compositional mixed-criticality scheduling.


Cache-Aware Compositional Analysis Of Real-Time Multicore Virtualization Platforms, Meng Xu, Linh T.X. Phan, Oleg Sokolsky, Sisu Xi, Chenyang Lu, Christopher Gill, Insup Lee Nov 2015

Cache-Aware Compositional Analysis Of Real-Time Multicore Virtualization Platforms, Meng Xu, Linh T.X. Phan, Oleg Sokolsky, Sisu Xi, Chenyang Lu, Christopher Gill, Insup Lee

Departmental Papers (CIS)

Multicore processors are becoming ubiquitous, and it is becoming increasingly common to run multiple real-time systems on a shared multicore platform. While this trend helps to reduce cost and to increase performance, it also makes it more challenging to achieve timing guarantees and functional isolation. One approach to achieving functional isolation is to use virtualization. However, virtualization also introduces many challenges to the multicore timing analysis; for instance, the overhead due to cache misses becomes harder to predict, since it depends not only on the direct interference between tasks but also on the indirect interference between virtual processors and the ...


Mixed-Criticality Scheduling On Multiprocessors Using Task Grouping, Jiankang Ren, Linh T.X. Phan Jul 2015

Mixed-Criticality Scheduling On Multiprocessors Using Task Grouping, Jiankang Ren, Linh T.X. Phan

Departmental Papers (CIS)

Real-time systems are increasingly running a mix of tasks with different criticality levels: for instance, unmanned aerial vehicle has multiple software functions with different safety criticality levels, but runs them on a single, shared computational platform. In addition, these systems are increasingly deployed on multiprocessor platforms because this can help to reduce their cost, space, weight, and power consumption. To assure the safety of such systems, several mixed-criticality scheduling algorithms have been developed that can provide mixed-criticality timing guarantees. However, most existing algorithms have two important limitations: they do not guarantee strong isolation among the high-criticality tasks, and they offer ...


Rt-Openstack: Cpu Resource Management For Real-Time Cloud Computing, Sisu Xi, Chong Li, Chenyang Lu, Christopher D. Gill, Meng Xu, Linh T.X. Phan, Insup Lee, Oleg Sokolsky Jun 2015

Rt-Openstack: Cpu Resource Management For Real-Time Cloud Computing, Sisu Xi, Chong Li, Chenyang Lu, Christopher D. Gill, Meng Xu, Linh T.X. Phan, Insup Lee, Oleg Sokolsky

Departmental Papers (CIS)

Clouds have become appealing platforms for not only general-purpose applications, but also real-time ones. However, current clouds cannot provide real-time performance to virtual machines (VMs). We observe the demand and the advantage of co-hosting real-time (RT) VMs with non-real-time (regular) VMs in a same cloud. RT VMs can benefit from the easily deployed, elastic resource provisioning provided by the cloud, while regular VMs effectively utilize remaining resources without affecting the performance of RT VMs through pro per resource management at both the cloud and the hypervisor levels. This paper presents RT-OpenStack, a cloud CPU resource management system for co-hosting real-time ...


Fault Tolerance And The Five-Second Rule, Ang Chen, Hanjun Xiao, Andreas Haeberlen, Linh T.X. Phan May 2015

Fault Tolerance And The Five-Second Rule, Ang Chen, Hanjun Xiao, Andreas Haeberlen, Linh T.X. Phan

Departmental Papers (CIS)

We propose a new approach to fault tolerance that we call bounded-time recovery (BTR). BTR is intended for systems that need strong timeliness guarantees during normal operation but can tolerate short outages in an emergency, e.g., when they are under attack. We argue that BTR could be a good fit for many cyber-physical systems. We also sketch a technical approach to providing BTR, and we discuss some challenges that still remain.


Mc-Fluid: Fluid Model-Based Mixed-Criticality Scheduling On Multiprocessors, Jaewoo Lee, Kieu-My Phan, Xiaozhe Gu, Jiyeon Lee, Arvind Easwaran, Insik Shin, Insup Lee Dec 2014

Mc-Fluid: Fluid Model-Based Mixed-Criticality Scheduling On Multiprocessors, Jaewoo Lee, Kieu-My Phan, Xiaozhe Gu, Jiyeon Lee, Arvind Easwaran, Insik Shin, Insup Lee

Departmental Papers (CIS)

A mixed-criticality system consists of multiple components with different criticalities. While mixed-criticality scheduling has been extensively studied for the uniprocessor case, the problem of efficient scheduling for the multiprocessor case has largely remained open. We design a fluid model-based multiprocessor mixed-criticality scheduling algorithm, called MC-Fluid in which each task is executed in proportion to its criticality-dependent rate. We propose an exact schedulability condition for MC-Fluid and an optimal assignment algorithm for criticality-dependent execution rates with polynomial-time complexity. Since MC-Fluid cannot be implemented directly on real hardware platforms, we propose another scheduling algorithm, called MC-DP-Fair, which can be implemented while preserving ...


Detecting Covert Timing Channels With Time-Deterministic Replay, Ang Chen, W. Brad Moore, Hanjun Xiao, Andreas Haeberlen, Linh T.X. Phan, Micah Sherr, Wenchao Zhou Oct 2014

Detecting Covert Timing Channels With Time-Deterministic Replay, Ang Chen, W. Brad Moore, Hanjun Xiao, Andreas Haeberlen, Linh T.X. Phan, Micah Sherr, Wenchao Zhou

Departmental Papers (CIS)

This paper presents a mechanism called timedeterministic replay (TDR) that can reproduce the execution of a program, including its precise timing. Without TDR, reproducing the timing of an execution is difficult because there are many sources of timing variability – such as preemptions, hardware interrupts, cache effects, scheduling decisions, etc. TDR uses a combination of techniques to either mitigate or eliminate most of these sources of variability. Using a prototype implementation of TDR in a Java Virtual Machine, we show that it is possible to reproduce the timing to within 1.85% of the original execution, even on commodity hardware.

The ...


The Middleware Assurance Substrate: Enabling Strong Real-Time Guarantees In Open Systems With Openflow, Andrew L. King, Sanjian Chen, Insup Lee Jun 2014

The Middleware Assurance Substrate: Enabling Strong Real-Time Guarantees In Open Systems With Openflow, Andrew L. King, Sanjian Chen, Insup Lee

Departmental Papers (CIS)

Middleware designed for use in Distributed Real-Time and Embedded (DRE) systems enable cost and development time reductions by providing simple communications abstractions and hiding operating system-level networking API details from developers. While current middleware technologies can hide many low-level details, designers must provide a static configuration for the system’s underlying network in order to achieve required performance characteristics. This has not been a problem for many types of DRE systems where the configuration of the system is relatively fixed from the factory (e.g., aircraft or naval vessels). However for truly open systems (i.e., systems where end users ...


Partitioned Scheduling Of Multi-Modal Mixed-Criticality Real-Time Systems On Multiprocessor Platforms, Dionisio De Niz, Linh T.X. Phan Apr 2014

Partitioned Scheduling Of Multi-Modal Mixed-Criticality Real-Time Systems On Multiprocessor Platforms, Dionisio De Niz, Linh T.X. Phan

Departmental Papers (CIS)

Real-time systems are becoming increasingly complex. A modern car, for example, requires a multitude of control tasks, such as braking, active suspension, and collision avoidance. These tasks not only exhibit different degrees of safety criticality but also change their criticalities as the driving mode changes. For instance, the suspension task is a critical part of the stability of the car at high speed, but it is only a comfort feature at low speed. Therefore, it is crucial to ensure timing guarantees for the system with respect to the tasks’ criticalities, not only within each mode but also during mode changes ...


Cache-Aware Compositional Analysis Of Real-Time Multicore Virtualization Platforms, Meng Xu, Linh T.X. Phan, Insup Lee, Oleg Sokolsky, Sisu Xi, Chenyang Lu, Christopher Gill Dec 2013

Cache-Aware Compositional Analysis Of Real-Time Multicore Virtualization Platforms, Meng Xu, Linh T.X. Phan, Insup Lee, Oleg Sokolsky, Sisu Xi, Chenyang Lu, Christopher Gill

Departmental Papers (CIS)

Multicore processors are becoming ubiquitous, and it is becoming increasingly common to run multiple real-time systems on a shared multicore platform. While this trend helps to reduce cost and to increase performance, it also makes it more challenging to achieve timing guarantees and functional isolation.

One approach to achieving functional isolation is to use virtualization. However, virtualization also introduces many challenges to the multicore timing analysis; for instance, the overhead due to cache misses becomes harder to predict, since it depends not only on the direct interference between tasks but also on the indirect interference between virtual processors and the ...


A Comparison Of Compositional Schedulability Analysis Techniques For Hierarchical Real-Time Systems, Madhukar Anand, Sebastian Fischmeister, Insup Lee Aug 2013

A Comparison Of Compositional Schedulability Analysis Techniques For Hierarchical Real-Time Systems, Madhukar Anand, Sebastian Fischmeister, Insup Lee

Departmental Papers (CIS)

Schedulability analysis of hierarchical real-time embedded systems involves defining interfaces that represent the underlying system faithfully and then compositionally analyzing those interfaces. Whereas commonly used abstractions, such as periodic and sporadic tasks and their interfaces, are simple and well studied, results for more complex and expressive abstractions and interfaces based on task graphs and automata are limited. One contributory factor may be the hardness of compositional schedulability analysis with task graphs and automata. Recently, conditional task models, such as the recurring branching task model, have been introduced with the goal of reaching a middle ground in the tradeoff between expressivity ...


Co-Design Of Control And Platform With Dropped Signals, Damoon Soudbakhsh, Linh T.X. Phan, Oleg Sokolsky, Insup Lee, Anuradha Annaswamy Apr 2013

Co-Design Of Control And Platform With Dropped Signals, Damoon Soudbakhsh, Linh T.X. Phan, Oleg Sokolsky, Insup Lee, Anuradha Annaswamy

Departmental Papers (CIS)

This paper examines a co-design of control and platform in the presence of dropped signals. In a cyber-physical system, due to increasing complexities such as the simultaneous control of several applications, limited resources, and complex platform architectures, some of the signals transmitted may often be dropped. In this paper, we address the challenges that arise both from the control design and the platform design point of view. A dynamic model is proposed that accommodates these drops, and a suitable switching control design is proposed. A Multiple Lyapunov function based approach is used to guarantee the stability of the system with ...


Overhead-Aware Compositional Analysis Of Real-Time Systems, Linh T.X. Phan, Meng Xu, Jaewoo Lee, Insup Lee, Oleg Sokolsky Apr 2013

Overhead-Aware Compositional Analysis Of Real-Time Systems, Linh T.X. Phan, Meng Xu, Jaewoo Lee, Insup Lee, Oleg Sokolsky

Departmental Papers (CIS)

Over the past decade, interface-based compositional schedulability analysis has emerged as an effective method for guaranteeing real-time properties in complex systems. Several interfaces and interface computation methods have been developed, and they offer a range of tradeoffs between the complexity and the accuracy of the analysis. However, none of the existing methods consider platform overheads in the component interfaces. As a result, although the analysis results are sound in theory, the systems may violate their timing constraints when running on realistic platforms. This is due to various overheads, such as task release delays, interrupts, cache effects, and context switches. Simple ...