Guangdong Liu's dissertation defense, "Multiprocessor Scheduling of Mixed-Criticality Parallel Systems," will be on Wednesday, Nov. 22 at 12:30 p.m. in 256C Avery Hall.
Committee Members: Dr. Ying Lu (Advisor)
Dr. Steve Goddard, Dr. Lisong Xu, Dr. Shige Wang and Dr. Wei Qiao
Abstract:
Motivated by the increasing trend in embedded systems towards platform integration, there has been an increasing research interest in scheduling mixed-criticality (MC) systems. However, most existing efforts have concentrated on scheduling sequential mixed-criticality tasks and ignored intra-task parallelism. As MC systems are increasingly being implemented on multiprocessor platforms, it is important to take advantage of intra-task parallelism in order to accommodate tasks with higher execution demands and tighter deadlines, such as those used in autonomous vehicles, video processing, radar tracking and robotic systems. To fill in this research gap, we propose to conduct a systematic study on multiprocessor scheduling of MC parallel tasks.
There are several big new challenges for developing and analyzing such scheduling approaches for MC parallel tasks. The first challenge is that most existing MC systems are based on sequential task models. This model is limited to inter-task parallelism since each task can only run on a single core. When a model is limited to inter-task parallelism, each individual task's total execution requirement must be smaller than its deadline since individual tasks cannot run any faster than on a single-core machine. Multi-core processors provide an opportunity of exploiting intra-parallelism within each task where each parallelizable MC task can be executed on multiple cores at the same time. In order to fully take advantage of massive multi-core processors, a new parallel MC task model is needed to take advantage of the available parallelism within each task. The second challenge is the lack of theory on scheduling MC parallel tasks on multiprocessors. There have been some recent progresses on scheduling real-time parallel tasks on multiprocessors. They have, however, investigated regular (single criticality), rather than MC task systems. These real-time scheduling techniques usually cannot work efficiently on MC systems because all tasks (both high-criticality and low-criticality tasks) are considered as equally important, resulting in severe resource waste. The MC parallel systems also pose new challenges to existing MC scheduling theories because almost all of them concentrate on sequential MC task systems.
The purpose of this dissertation is to study the scheduling of recurrent parallel MC task set. Each recurrent parallel MC task can generate an infinite number of jobs. In order to achieve this goal, we need to first resolve the scheduling problem for MC system comprising of finite collections of parallel MC non-recurring jobs. Therefore, we have initially studied the scheduling of parallel non-recurring MC jobs, which is considered as a first step towards a more comprehensive study of scheduling recurrent parallel MC tasks. To enable intra-task parallelism, parallel MC job model and task model are introduced first. We then investigate different approaches to scheduling MC parallel systems on multiprocessors. Two types of multiprocessor scheduling approaches are studied: global scheduling and partitioned scheduling. To schedule parallel tasks, we further divide the scheduling approaches into two types: those with or without a task decomposition. In this dissertation, in particular, four different multiprocessor scheduling algorithms are developed: 1) Partitioned Multiprocessor Scheduling of MC Parallel Jobs; 2) Global Scheduling of Parallel MC Tasks without Task Decomposition; 3) Partitioned Scheduling of MC Parallel Tasks; 4) Decomposition-Based Global Scheduling of MC Parallel Tasks with Deadline Tuning.
Simulation experiments are conducted to evaluate these scheduling algorithms. The experimental results confirm the effectiveness of the proposed scheduling algorithms.