Utility-based scheduling for periodic tasks with multiple parallelization options

Dawei Li, Jie Wu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Modern cloud computing systems have been using multiple processing units on servers to increase their processing capability. Recently, applications with multiple parallelization options have been witnessed, and serve as a promising model for efficiently utilizing the processing capacity of the system. In this paper, we consider utility-based scheduling for periodic multisegment tasks with multiple parallelization options on platforms with multiple homogeneous processing units. Our goal is to maximize the system's overall utility achieved by scheduling the tasks. We show that the problem is closely related to another problem, which minimizes the density of each task separately. We consider two typical types of utility models, namely, a uniform utility model, where all tasks have equal utility, and a general utility model, where all tasks have different utility values. For the uniform utility model, we give the optimal solution for selecting and scheduling tasks. For the general utility model, we prove that the problem can be reduced to the classic 0-1 knapsack problem, and thus is NP-complete, we then provide the Fully Polynomial Time Approximation Scheme (FPTAS) for the problem. FPTAS algorithms are known for high time complexity, especially if we want to achieve near-optimal solutions. We then provide a simple 1/2 approximation algorithm based on a greedy strategy with significantly reduced time complexity. Simulations show that tasks with multiple parallelization options can improve system utility significantly, comparisons show that the 1/2 approximation algorithm can achieve near-optimal solutions under general conditions.

Original languageEnglish
Title of host publicationProceedings - 8th IEEE International Conference on Cloud Computing Technology and Science, CloudCom 2016
PublisherIEEE Computer Society
Pages423-430
Number of pages8
ISBN (Electronic)9781509014453
DOIs
StatePublished - 2 Jul 2016
Event8th IEEE International Conference on Cloud Computing Technology and Science, CloudCom 2016 - Luxembourg, Luxembourg
Duration: 12 Dec 201615 Dec 2016

Publication series

NameProceedings of the International Conference on Cloud Computing Technology and Science, CloudCom
Volume0
ISSN (Print)2330-2194
ISSN (Electronic)2330-2186

Other

Other8th IEEE International Conference on Cloud Computing Technology and Science, CloudCom 2016
CountryLuxembourg
CityLuxembourg
Period12/12/1615/12/16

Keywords

  • Multi-core processors
  • multiple parallelization options
  • parallel processing
  • periodic tasks
  • utility-based scheduling

Fingerprint Dive into the research topics of 'Utility-based scheduling for periodic tasks with multiple parallelization options'. Together they form a unique fingerprint.

  • Cite this

    Li, D., & Wu, J. (2016). Utility-based scheduling for periodic tasks with multiple parallelization options. In Proceedings - 8th IEEE International Conference on Cloud Computing Technology and Science, CloudCom 2016 (pp. 423-430). [7830713] (Proceedings of the International Conference on Cloud Computing Technology and Science, CloudCom; Vol. 0). IEEE Computer Society. https://doi.org/10.1109/CloudCom.2016.0072