NDLI: Task Set Synthesis with Cost Minimization for Sporadic Real-Time Tasks

Content Provider	IEEE Xplore Digital Library
Author	Jian-Jia Chen
Copyright Year	2013
Description	Author affiliation: Dept. of Inf., Karlsruhe Inst. of Technol. (KIT), Karlsruhe, Germany (Jian-Jia Chen)
Abstract	By allowing users to specify multiple execution versions of a task with different amounts of worst-case execution time and costs, this paper explores how to minimize of the overall system cost under the timing constraints for sporadic real-time tasks. One specific application is to minimize the requirement scratchpad memory size (system cost) to meet the timing constraint, while the worst-case execution time of a task depends on its allocated scratchpad memory size. This paper shows that the problem is NP-hard for approximation, if speed augmentation is not allowed. The algorithms proposed in this paper are analyzed based on (α, β)-approximation, in which a β speed augmentation factor is allowed and the system cost is at most α times of the optimal solution. For tasks with constrained deadlines, an efficient (1, 2/1-η)-approximation algorithm based on dynamic programming is proposed for deadline-monotonic (DM) scheduling, where 0 <; η <; 1 is a user-defined parameter for the rounding precision in dynamic programming. This is further extended to a (1, 1.6322/1-η )-approximation algorithm for earliest-deadline-first (EDF) scheduling. A polynomialtime (1 + ε, 1 + η)-approximation scheme is also developed for EDF scheduling by considering 0 <; ε, 0 <; η <; 1 when the ratio of the maximum relative deadline to the minimum relative deadline of tasks is a constant. This paper is concluded by considering the dual problem to maximize of the system profit by selecting execution versions with different amounts of worst-case execution time.
Sponsorship	IEEE Comput. Soc.
Starting Page	350
Ending Page	359
File Size	329343
Page Count	10
File Format	PDF
ISBN	9781479920068
ISSN	10528725
DOI	10.1109/RTSS.2013.42
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2013-12-03
Publisher Place	Canada
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Real-time systems Timing Approximation methods Approximation algorithms Computational modeling Schedules Scheduling memory allocation sporadic real-time tasks task set synthesis resource (speed) augmentation approximation schedulability analysis
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Hardware and Architecture Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Partitioned Packing and Scheduling for Sporadic Real-Time Tasks in Identical Multiprocessor Systems

Static Approximation Algorithms for Regularity-based Resource Partitioning

Fixed-Relative-Deadline Scheduling of Hard Real-Time Tasks with Self-Suspensions

Polynomial-Time Exact Schedulability Tests for Harmonic Real-Time Tasks

A PTAS for Assigning Sporadic Tasks on Two-type Heterogeneous Multiprocessors

Real-Time Task Scheduling on Island-Based Multi-Core Platforms

Abstract global static-priority scheduling of sporadic task systems on multiprocessor platforms.

Uniprocessor Feasibility of Sporadic Tasks Remains coNP-Complete under Bounded Utilization

Allocation cost minimization for periodic hard real-time tasks in energy-constrained DVS systems (2006)

Task Set Synthesis with Cost Minimization for Sporadic Real-Time Tasks

Similar Documents

Partitioned Packing and Scheduling for Sporadic Real-Time Tasks in Identical Multiprocessor Systems

Static Approximation Algorithms for Regularity-based Resource Partitioning

Fixed-Relative-Deadline Scheduling of Hard Real-Time Tasks with Self-Suspensions

Polynomial-Time Exact Schedulability Tests for Harmonic Real-Time Tasks

A PTAS for Assigning Sporadic Tasks on Two-type Heterogeneous Multiprocessors

Real-Time Task Scheduling on Island-Based Multi-Core Platforms

Abstract global static-priority scheduling of sporadic task systems on multiprocessor platforms.

Uniprocessor Feasibility of Sporadic Tasks Remains coNP-Complete under Bounded Utilization

Allocation cost minimization for periodic hard real-time tasks in energy-constrained DVS systems (2006)

Task Set Synthesis with Cost Minimization for Sporadic Real-Time Tasks