Utility-based scheduling for periodic tasks with multiple parallelization options

Dawei Li, Jie Wu

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

1 Citation (Scopus)

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 - Jul 2 2016
Event8th IEEE International Conference on Cloud Computing Technology and Science, CloudCom 2016 - Luxembourg, Luxembourg
Duration: Dec 12 2016Dec 15 2016

Publication series

NameProceedings of the International Conference on Cloud Computing Technology and Science, CloudCom
Volume0

Other

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

Fingerprint

Scheduling
Approximation algorithms
Processing
Polynomials
Cloud computing
Computer systems
Servers

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics

Keywords

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

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
Li, Dawei ; Wu, Jie. / Utility-based scheduling for periodic tasks with multiple parallelization options. Proceedings - 8th IEEE International Conference on Cloud Computing Technology and Science, CloudCom 2016. IEEE Computer Society, 2016. pp. 423-430 (Proceedings of the International Conference on Cloud Computing Technology and Science, CloudCom).
@inproceedings{88e3ee8bd1204329b68263c66ab9b17a,
title = "Utility-based scheduling for periodic tasks with multiple parallelization options",
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.",
keywords = "Multi-core processors, multiple parallelization options, parallel processing, periodic tasks, utility-based scheduling",
author = "Dawei Li and Jie Wu",
year = "2016",
month = "7",
day = "2",
doi = "https://doi.org/10.1109/CloudCom.2016.0072",
language = "English",
series = "Proceedings of the International Conference on Cloud Computing Technology and Science, CloudCom",
publisher = "IEEE Computer Society",
pages = "423--430",
booktitle = "Proceedings - 8th IEEE International Conference on Cloud Computing Technology and Science, CloudCom 2016",

}

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., 7830713, Proceedings of the International Conference on Cloud Computing Technology and Science, CloudCom, vol. 0, IEEE Computer Society, pp. 423-430, 8th IEEE International Conference on Cloud Computing Technology and Science, CloudCom 2016, Luxembourg, Luxembourg, 12/12/16. https://doi.org/10.1109/CloudCom.2016.0072

Utility-based scheduling for periodic tasks with multiple parallelization options. / Li, Dawei; Wu, Jie.

Proceedings - 8th IEEE International Conference on Cloud Computing Technology and Science, CloudCom 2016. IEEE Computer Society, 2016. p. 423-430 7830713 (Proceedings of the International Conference on Cloud Computing Technology and Science, CloudCom; Vol. 0).

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

TY - GEN

T1 - Utility-based scheduling for periodic tasks with multiple parallelization options

AU - Li, Dawei

AU - Wu, Jie

PY - 2016/7/2

Y1 - 2016/7/2

N2 - 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.

AB - 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.

KW - Multi-core processors

KW - multiple parallelization options

KW - parallel processing

KW - periodic tasks

KW - utility-based scheduling

UR - http://www.scopus.com/inward/record.url?scp=85012977470&partnerID=8YFLogxK

U2 - https://doi.org/10.1109/CloudCom.2016.0072

DO - https://doi.org/10.1109/CloudCom.2016.0072

M3 - Conference contribution

T3 - Proceedings of the International Conference on Cloud Computing Technology and Science, CloudCom

SP - 423

EP - 430

BT - Proceedings - 8th IEEE International Conference on Cloud Computing Technology and Science, CloudCom 2016

PB - IEEE Computer Society

ER -

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