Overhead-aware real-time scheduling for streaming applications on multiprocessor systems-on-chip

Abstract

With increasing demand for high-performance multimedia in battery-driven mobile devices, multicore architecture such as MPSoC (Multiprocessor System-on-Chip) is becoming widely adopted in embedded systems. When real-time streaming applications such as Internet video conferences and surveillance digital video recorders are executed on such chip multiprocessors, both time performance and energy consumption need to be considered. In order to fully take advantage of the multicore architecture of MPSoCs, various techniques have been proposed to explore and increase parallelism of streaming applications. These parallelization techniques usually impose a large amount of intercore communications with significant energy overhead and intercore communication overhead. By minimizing these overheads, a shorter period can be applied and system performance such as energy consumption and memory usage can be improved. In this thesis, we have attacked these problems from several aspects including the optimization of time performance, energy consumption, and memory usage for streaming applications on MPSoCs considering various overheads. First, we focus on solving the energy optimization problem for real-time streaming applications on MPSoCs by combining task-level coarse-grained software pipelining with DPM (dynamic power management) and DVS (dynamic voltage scaling) considering transition overhead, intercore communication, and discrete voltage levels. We propose a two-phase approach to solve the problem. In the first phase, we propose a coarse-grained task parallelization algorithm to transform a periodic dependent task graph into a set of independent tasks by exploiting the periodic feature of streaming applications. In the second phase, we propose a genetic algorithm that can search and find the best schedule with the minimum energy consumption. Experimental results show that our approach can achieve a 24.4% reduction in energy consumption compared with previous work. Second, we jointly optimize computation and communication task scheduling for streaming applications on MPSoCs with the objective of minimizing schedule length by totally removing intercore communication overhead. By minimizing schedule length, the system performance can be improved by adopting a smaller period or exploring the slacks generated for energy reduction with DVS. To guarantee the schedulability of communication tasks, we perform the schedulability analysis, and theoretically obtain the upper bound of the times needed to reschedule each computation task. Based on the analysis, we formulate the scheduling problem as an ILP (Integer Linear Programming) formulation and obtain an optimal solution. Experimental results show that our technique can achieve a 27.72% reduction in schedule length and a 14.98% reduction in energy consumption compared with previous work. Third, we study the problem of removing intercore communication overhead for streaming applications on MPSoCs with the objective of minimizing the overall memory usage. The intercore communication overhead not only impacts time performance considerably but also influences the total memory usage of MPSoC architecture. Our basic idea is to let tasks with intra-period data dependencies transform to inter-period data dependencies so as to totally remove the intercore communication overhead. To solve the problem, we first perform analysis and obtain the bounds of the times needed to reschedule each task. Then we formulate the scheduling problem as an ILP model to obtain an optimal schedule. We also propose a heuristic approach to efficiently obtain a near optimal solution. Experimental results show that the proposed approach can significantly reduce the schedule length and improve the memory usage compared with previous work.