Tight Approximation for Scheduling Parallel Job on Identical Clusters

Autor: Marin Bougeret, Pierre-Francois Dutot, Denis Trystram, Klaus Jansen, Christina Robenek
Přispěvatelé: Methods, Algorithms for Operations REsearch (MAORE), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), PrograMming and scheduling design fOr Applications in Interactive Simulation (MOAIS), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Université Pierre Mendès France - Grenoble 2 (UPMF), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), Theory of Parallelism, Department of Computer Science, Christian-Albrechts-Universität zu Kiel (CAU)-Christian-Albrechts-Universität zu Kiel (CAU), Méthodes Algorithmes pour l'Ordonnancement et les Réseaux (MAORE), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Laboratoire d'Informatique de Grenoble (LIG), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Bougeret, Marin, Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Inria Grenoble - Rhône-Alpes
Předmět:
Zdroj: HAL
RR-12001, 2012
Popis: In the grid computing paradigm, several clusters share their computing resources in order to distribute the workload. Each of the $N$ cluster is a set of $m$ identical processors (connected by a local interconnection network), and $n$ parallel jobs are submitted to a centralized queue. A job $J_j$ requires $q_j$ processors during $p_j$ units of time. We consider the Multiple Cluster Scheduling Problem ($\MCSP$), where the objective of is to schedule all the jobs in the clusters, minimizing the maximum completion time (makespan). This problem is closely related to the multiple strip packing problem, where the objective is to pack $n$ rectangles into $m$ strips of width $1$, minimizing the maximum height over all the strips. $\MCSP$ is $2$-inapproximable (unless $P=NP$), and several approximation algorithm have been proposed. However, ratio $2$ has only been reached by algorithms that use extremely costly and complex subroutines as "black boxes" (for example area maximization subroutines on a constant ($\approx 10^4$) number of bins, of $PTAS$ for the classical $P||C_{max}$ problem). Thus, our objective is to find a reasonable restriction of $\MCSP$ where the inapproximability lower bound could be tightened in almost linear time. In this spirit we study a restriction of $\MCSP$ where jobs do not require strictly more than half of the processors, and we provide for this problem a $2$-approximation running in $O(log_2(nh_{max})n(N+log(n)))$, where $h_{max}$ is the maximum processing time of a job. This result is somehow optimal, as this restriction of $\MCSP$ (and even simpler ones, where jobs require less than $\frac{m}{c}$, $c \in \mathbb{N}, c \ge 2$) remain $2$-innapproximable unless $\P=\NP$.
Databáze: OpenAIRE
Externí odkaz: