Show simple item record

dc.contributor.author
Kumar, Pratyush
dc.contributor.author
Thiele, Lothar
dc.date.accessioned
2017-06-11T14:29:10Z
dc.date.available
2017-06-11T14:29:10Z
dc.date.issued
2014-07
dc.identifier.uri
http://hdl.handle.net/20.500.11850/94139
dc.description.abstract
The YDS algorithm computes a schedule on a DVS-enabled resource to meet deadlines of all jobs and optimally minimize the total energy consumption. The algorithm requires that an exact execution time of each job be known. For settings where execution times are variable or uncertain, stochastic scheduling has been proposed to preferentially accelerate less probable phases of jobs to reduce the expected energy consumption. However, an analogue to the YDS algorithm for the stochastic setting has not been optimally solved. In this paper, we propose the p-YDS algorithm to minimize the expected energy consumption for a set of jobs with arbitrary arrival times, deadlines, and execution times. We then derive the competitive ratio of the YDS algorithm w.r.t. the p-YDS algorithm, for the metric of expected energy consumption. By comparing two optimal algorithms, this ratio specifies the worst-case energy cost of being agnostic to the variability in the execution time of jobs.
dc.language.iso
en
dc.publisher
Institut für technische Informatik und Kommunikation, ETH Zürich
dc.title
p-YDS Algorithm: An Optimal Extension of YDS Algorithm to Minimize Expected Energy For Real-Time Jobs
dc.type
Report
ethz.journal.title
TIK Report
ethz.journal.volume
353
ethz.size
29 p.
ethz.notes
.
ethz.publication.place
Zürich
ethz.publication.status
published
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.::02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.::03429 - Thiele, Lothar / Thiele, Lothar
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.::02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.::03429 - Thiele, Lothar / Thiele, Lothar
ethz.identifier.url
ftp://ftp.tik.ee.ethz.ch/pub/people/kumarpr/EMSOFT14a_TR.pdf
ethz.date.deposited
2017-06-11T14:29:25Z
ethz.source
ECIT
ethz.identifier.importid
imp593652a65140270023
ethz.ecitpid
pub:148001
ethz.eth
yes
ethz.availability
Metadata only
ethz.rosetta.installDate
2017-07-12T22:17:17Z
ethz.rosetta.lastUpdated
2018-11-02T17:14:07Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=p-YDS%20Algorithm:%20An%20Optimal%20Extension%20of%20YDS%20Algorithm%20to%20Minimize%20Expected%20Energy%20For%20Real-Time%20Jobs&rft.jtitle=TIK%20Report&rft.date=2014-07&rft.volume=353&rft.au=Kumar,%20Pratyush&Thiele,%20Lothar&rft.genre=report&
 Search via SFX

Files in this item

FilesSizeFormatOpen in viewer

There are no files associated with this item.

Publication type

Show simple item record