Tight Approximation for Scheduling Parallel Job on Identical Clusters

Marin Bougeret 1, * Pierre-Francois Dutot 2, 3 Denis Trystram 2, 4 Klaus Jansen 5 Christina Robenek 5
* Corresponding author
1 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
5 Theory of Parallelism
Department of Computer Science
Abstract : 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$.
Complete list of metadatas

Cited literature [7 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00656780
Contributor : Marin Bougeret <>
Submitted on : Thursday, January 5, 2012 - 9:55:28 AM
Last modification on : Friday, May 3, 2019 - 12:08:04 PM
Long-term archiving on : Friday, April 6, 2012 - 2:26:29 AM

File

RR_lirmm.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00656780, version 1

Citation

Marin Bougeret, Pierre-Francois Dutot, Denis Trystram, Klaus Jansen, Christina Robenek. Tight Approximation for Scheduling Parallel Job on Identical Clusters. RR-12001, 2012. ⟨lirmm-00656780⟩

Share

Metrics

Record views

926

Files downloads

357