Scheduling Constrained-Deadline Sporadic Parallel Tasks Considering Memory Contention
CARNEGIE-MELLON UNIV PITTSBURGH PA SOFTWARE ENGINEERING INST
Pagination or Media Count:
Consider constrained-deadline sporadic tasks scheduled on a multiprocessor where i each task is characterized by its execution requirement, deadline, and minimum inter-arrival time, ii each task generates a sequence of jobs, iii the execution requirement of a job and its potential for parallel execution is described by one or many stages with a stage having one or many segments and different segments in the same stage can execute in parallel and a segment is only allowed to start execution if all segments of previous stages have finished execution, and iv there is contention for shared resources in the memory system cache eviction, reordering in memory controller, memory bus contention. We present an algorithm that i performs schedulability testing for tasks scheduled with global-Earliest-Deadline-First gEDF, ii configures the virtual-to-physical address translation so that a cache block fetched to the last-level cache by one task cannot be evicted by another task, iii configures the virtual-to-physical address translation to attempt to eliminate the extra execution time caused by the reordering effect in the memory controller and if this is not possible, then the reordering effect is considered in the schedulability analysis, and iv considers the effect of contention for the memory bus. Our solution is based on formulating this problem as a Mixed-Integer Linear Program MILP. We have implemented a tool based on this theory and validated its output against measurements on a real computer.
- Computer Programming and Software