Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

2014

Filename

WUCSE-2014-48.pdf

Technical Report Number

WUCSE-2014-48

Abstract

Federated scheduling is a strategy to schedule parallel real-time tasks: It allocates a dedicated cluster of cores to high-utilization task (utilization >1); It uses a multiprocessor scheduling algorithm to schedule and execute all low-utilization tasks sequentially, on a shared cluster of the remaining cores. Prior work has shown that federated scheduling has the best known capacity augmentation bound of 2 for parallel tasks with implicit deadlines. In this paper, we explore the soft real-time performance of federated scheduling and address the average-case workloads instead of the worst-case values. In particular, we consider stochastic tasks -- tasks for which execution time and critical-path length are random variables. In this case, we use bounded expected tardiness as the schedulability criterion. We define a stochastic capacity augmentation bound and prove that federated scheduling algorithms guarantee the same bound of 2 for stochastic tasks. We present three federated mapping algorithms for core allocation. All of them guarantee bounded expected tardiness and provide the same capacity augmentation bound; In practice, however, we expect them to provide different performances, both in terms of the task sets they can schedule and the actual tardiness they guarantee. Therefore, we performed numerical evaluations using randomly generated task sets to understand the practical differences between the three algorithms.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7ZK5DW9

Download

Share

COinS