Analysis of an Approximation Algorithm for Scheduling Independent Parallel TasksReportar como inadecuado




Analysis of an Approximation Algorithm for Scheduling Independent Parallel Tasks - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 Department of Mathematics and Computer Science New Paltz NY

Abstract : In this paper, we consider the problem of scheduling independent parallel tasks in parallel systems with identical processors. The problem is NP-hard, since it includes the bin packing problem as a special case when all tasks have unit execution time. We propose and analyze a simple approximation algorithm called H m, where m is a positive integer. Algorithm H m has a moderate asymptotic worst-case performance ratio in the range 4-3

. 31-18 for all m≥ 6; but the algorithm has a small asymptotic worst-case performance ratio in the range 1+1-r+1

1+1-r, when task sizes do not exceed 1-r of the total available processors, where r>1 is an integer. Furthermore, we show that if the task sizes are independent, identically distributed i.i.d. uniform random variables, and task execution times are i.i.d. random variables with finite mean and variance, then the average-case performance ratio of algorithm H m is no larger than 1.2898680

., and for an exponential distribution of task sizes, it does not exceed 1.2898305



As demonstrated by our analytical as well as numerical results, the average-case performance ratio improves significantly when tasks request for smaller numbers of processors.

Keywords : Approximation algorithm Average-case performance ratio Parallel task scheduling Probabilistic analysis Worst-case performance ratio





Autor: Keqin Li -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados