### 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 language | English |
---|---|

Title of host publication | Proceedings - 8th IEEE International Conference on Cloud Computing Technology and Science, CloudCom 2016 |

Publisher | IEEE Computer Society |

Pages | 423-430 |

Number of pages | 8 |

ISBN (Electronic) | 9781509014453 |

DOIs | |

State | Published - Jul 2 2016 |

Event | 8th IEEE International Conference on Cloud Computing Technology and Science, CloudCom 2016 - Luxembourg, Luxembourg Duration: Dec 12 2016 → Dec 15 2016 |

### Publication series

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

Volume | 0 |

### Other

Other | 8th IEEE International Conference on Cloud Computing Technology and Science, CloudCom 2016 |
---|---|

Country | Luxembourg |

City | Luxembourg |

Period | 12/12/16 → 12/15/16 |

### Fingerprint

### 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

*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

}

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

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 -