## 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 - 2 Jul 2016 |

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

### Publication series

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

Volume | 0 |

ISSN (Print) | 2330-2194 |

ISSN (Electronic) | 2330-2186 |

### Other

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

Country | Luxembourg |

City | Luxembourg |

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

## Keywords

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