Many-Core Real-Time Task Scheduling with Scratchpad Memory

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

5 Scopus Citations
View graph of relations

Author(s)

  • Sheng-Wei Cheng
  • Che-Wei Chang
  • Jian-Jia Chen
  • Tei-Wei Kuo
  • Pi-Cheng Hsiu

Detail(s)

Original languageEnglish
Article number7378514
Pages (from-to)2953-2966
Journal / PublicationIEEE Transactions on Parallel and Distributed Systems
Volume27
Issue number10
Online published12 Jan 2016
Publication statusPublished - Oct 2016
Externally publishedYes

Abstract

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-1/) - 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.

Research Area(s)

  • Many-core architecture, multi-level memory, partitioned scheduling algorithms, real-time systems, resource augmentation, scratchpad memory

Citation Format(s)

Many-Core Real-Time Task Scheduling with Scratchpad Memory. / Cheng, Sheng-Wei; Chang, Che-Wei; Chen, Jian-Jia; Kuo, Tei-Wei; Hsiu, Pi-Cheng.

In: IEEE Transactions on Parallel and Distributed Systems, Vol. 27, No. 10, 7378514, 10.2016, p. 2953-2966.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal