Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Scheduling Shared Continuous Resources on Many-Cores
Speaker:Peter Kling
coming from:University of Paderborn
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 22 April 2014
Duration:30 Minutes
Building:E1 4
This talk introduces a new resource constrained scheduling model and presents some first results. We consider a number of jobs scheduled on $m$ identical processors sharing a continuously divisible resource. Each job $j$ comes with a resource requirement $r_j\in\{0,1\}$ and can be processed at full speed if granted its full resource requirement. If receiving only an $x$-portion of $r_j$, it is processed at an $x$-fraction of the full speed. Our goal is to find a resource assignment that minimizes the makespan. Variants of such problems, relating the resource assignment of jobs to their processing speeds, have been studied under the term discrete-continuous scheduling. Known results are either very pessimistic or heuristic in nature.

We suggest a slightly simplified model, focusing on the assignment of shared continuous resources to the processors. The job assignment to processors and the ordering of the jobs have already been fixed. Our work shows that finding an optimal solution is NP-hard if the number of processors is a part of the input, even in the case of unit size jobs. On the positive side, we can give an optimal algorithms for two processors and prove that "balanced" schedules yield a $2-1/m$-approximation. Such schedules can be computed by a simple greedy algorithm, for which this bound is tight.

Name(s):Antonios Antoniadis
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Antonios Antoniadis, 04/15/2014 05:15 PM -- Created document.