Home
Lectures
Real-Time Virtual Resources: Static Approximation Algorithms for Regularity-based Resource Partitioning

Real-Time Virtual Resources: Static Approximation Algorithms for Regularity-based Resource Partitioning

Speaker: Albert M. K. Cheng – Houston, TX, United States
Topic(s): Architecture, Embedded Systems and Electronics, Robotics

Abstract

Real-time resource partitioning (RP) divides hardware resources (processors, cores, and other components) into temporal partitions and allocates these partitions as virtual resources (physical resources at a fraction of their service rates) to application tasks. RP can be a layer in the OS or firmware directly interfacing the hardware, and is a key enabling technology for virtualization and cloud computing. Open embedded systems make it easy to securely add and remove software applications as well as to increase resource utilization and reduce implementation cost when compared to systems which physically assign distinct computing resources to run different applications. This seminar will describe ways based on the Regularity-based Resource Partition Model (RRP) to maintain the schedulability of real-time tasks as if they were scheduled on dedicated physical resources and increase the utilization of the physical multi-resources.

As a hierarchical real-time system framework, the Regularity-based Resource Partition Model allocates physical resources in time intervals determined by integral numbers of

a time unit to tasks in different applications. A Regularity-based Resource Partition is characterized by its regularity and availability factor. An important problem is how to schedule a group of resource partitions with the specification of their regularities and availability factors. Mok and Feng have provided the AAF-Single algorithm which works only on a single-resource platform. Li and Cheng have recently extended AAF-Single to AAF-Multi for multi-resource platforms without violating the schedulability bound given by Feng. However, the resource utilization of these two algorithms could be significantly improved. This seminar presents optimized resource partitioning algorithms for the Regularity-base Resource Partition Model. We first decompose the resource partitioning problem into two subproblems, and invoke the Pfair algorithm to solve the first subproblem. Then we introduce a category of approximation algorithms called Static Approximation Algorithms (SAA) to solve the second subproblem. An SAA adjusts the availability factors of the resource partitions with a specific boundary sequence. We prove that the schedulability bound of any feasible SAA is at most 0.5. Furthermore, we develop an optimal SAA called Magic7. Simulation shows that Magic7-enhanced algorithms

significantly improve resource utilization.

About this Lecture

Number of Slides: 48
Duration: 50 minutes
Languages Available: English, Spanish
Last Updated:

Request this Lecture

To request this particular lecture, please complete this online form.

Request a Tour

To request a tour with this speaker, please complete this online form.

All requests will be sent to ACM headquarters for review.