Many-Core Real-Time Task Scheduling with Scratchpad Memory

摘要

This work is motivated by the demand for scheduling tasks upon the increasingly popular island-based many-core architectures. On such an architecture, homogeneous cores are grouped into islands, each of which is equipped with a scratchpad memory module (referred to as local memory). We first show the NP-hardness and the inapproximability of the scheduling problem. Despite the inapproximability, positive results can still be found when different cases of the problem are investigated. A (3−1F) - approximation algorithm is proposed for the minimization of the maximum system utilization, where F is the number of cores in the platform. When the technique of resource augmentation is considered, this paper further develops a (γ+1) -memory 2γ−1γ−1 -approximation algorithm, where γ represents the trade-off between CPU utilization and local memory space. On the other hand, a special case is also considered when the ratio of the worst-case execution time of a task without and with using the local memory is bounded by a constant. The capabilities of the proposed algorithms are then evaluated with benchmarks from MRTC, UTDSP, NetBench and DSPstone, where the maximum system utilization can be significantly reduced even when the local memory size is only 5 percent of the total footprint of all of the tasks.