Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

A log-linear (2+5/6)-approximation algorithm for parallel machine scheduling with a single orthogonal resource

Uproszczony widok
dc.abstract.enAs the gap between compute and I/O performance tends to grow, modern High-Performance Computing (HPC) architectures include a new resource type: an intermediate persistent fast memory layer, called burst buffers. This is just one of many kinds of renewable resources which are orthogonal to the processors themselves, such as network bandwidth or software licenses. Ignoring orthogonal resources while making scheduling decisions just for processors may lead to unplanned delays of jobs of which resource requirements cannot be immediately satisfied. We focus on a classic problem of makespan minimization for parallel-machine scheduling of independent sequential jobs with additional requirements on the amount of a single renewable orthogonal resource. We present an easily-implementable log-linear algorithm that we prove is 256-approximation. In simulation experiments, we compare our algorithm to standard greedy list-scheduling heuristics and show that, compared to LPT, resource-based algorithms generate significantly shorter schedules.
dc.affiliationUniwersytet Warszawski
dc.conference.countryPortugalia
dc.conference.datefinish2021-09-03
dc.conference.datestart2021-08-30
dc.conference.placeVirtual
dc.conference.seriesEuro-Par: International European Conference on Parallel and Distributed Computing
dc.conference.seriesEuro-Par: International European Conference on Parallel and Distributed Computing
dc.conference.shortcutEuro-Par 2021
dc.conference.weblinkhttps://2021.euro-par.org
dc.contributor.authorNaruszko, Adrian
dc.contributor.authorRządca, Krzysztof
dc.contributor.authorPrzybylski, Bartłomiej
dc.date.accessioned2024-01-24T17:49:01Z
dc.date.available2024-01-24T17:49:01Z
dc.date.issued2021
dc.description.financePublikacja bezkosztowa
dc.identifier.doi10.1007/978-3-030-85665-6_10
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/101624
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages151-166
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.titleA log-linear (2+5/6)-approximation algorithm for parallel machine scheduling with a single orthogonal resource
dc.typeJournalArticle
dspace.entity.typePublication