Scheduling shared continuous resources on many-cores

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10385246" target="_blank" >RIV/00216208:11320/18:10385246 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/s10951-017-0518-0" target="_blank" >https://doi.org/10.1007/s10951-017-0518-0</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10951-017-0518-0" target="_blank" >10.1007/s10951-017-0518-0</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Scheduling shared continuous resources on many-cores

Popis výsledku v původním jazyce

We consider the problem of scheduling a number of jobs on m identical processors sharing a continuously divisible resource. Each job j comes with a resource requirement . The job can be processed at full speed if granted its full resource requirement. If receiving only an x-portion of , it is processed at an x-fraction of the full speed. Our goal is to find a resource assignment that minimizes the makespan (i.e., the latest completion time). 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. In this article, we suggest and analyze a slightly simplified model. It focuses 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. It is shown that, even for unit size jobs, finding an optimal solution is NP-hard if the number of processors is part of the input. Positive results for unit size jobs include a polynomial-time algorithm for any constant number of processors. Since the running time is infeasible for practical purposes, we also provide more efficient algorithm variants: an optimal algorithm for two processors and a -approximation algorithm for m processors.

Název v anglickém jazyce

Scheduling shared continuous resources on many-cores

Popis výsledku anglicky

We consider the problem of scheduling a number of jobs on m identical processors sharing a continuously divisible resource. Each job j comes with a resource requirement . The job can be processed at full speed if granted its full resource requirement. If receiving only an x-portion of , it is processed at an x-fraction of the full speed. Our goal is to find a resource assignment that minimizes the makespan (i.e., the latest completion time). 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. In this article, we suggest and analyze a slightly simplified model. It focuses 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. It is shown that, even for unit size jobs, finding an optimal solution is NP-hard if the number of processors is part of the input. Positive results for unit size jobs include a polynomial-time algorithm for any constant number of processors. Since the running time is infeasible for practical purposes, we also provide more efficient algorithm variants: an optimal algorithm for two processors and a -approximation algorithm for m processors.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2018

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Journal of Scheduling

ISSN

1094-6136

e-ISSN

—

Svazek periodika

21

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

16

Strana od-do

77-92

Kód UT WoS článku

000425010300006

EID výsledku v databázi Scopus

2-s2.0-85018499646