File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/1378533.1378580
- Scopus: eid_2-s2.0-57349137634
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Competitive non-migratory scheduling for flow time and energy
Title | Competitive non-migratory scheduling for flow time and energy |
---|---|
Authors | |
Keywords | Competitive analysis Dynamic speed scaling Energy minimization Online scheduling algorithms |
Issue Date | 2008 |
Publisher | ACM. |
Citation | Annual Acm Symposium On Parallelism In Algorithms And Architectures, 2008, p. 256-264 How to Cite? |
Abstract | Energy usage has been an important concern in recent research on online scheduling. In this paper we extend the study of the tradeoff between flow time and energy from the single-processor setting [8, 6] to the multi-processor setting. Our main result is an analysis of a simple non-migratory online algorithm called CRR (classified round robin) on m ≤ 2 processors, showing that its flow time plus energy is within O(1) times of the optimal non-migratory offline algorithm, when the maximum allowable speed is slightly relaxed. This result still holds even if the comparison is made against the optimal migratory offline algorithm (the competitive ratio increases by a factor of 2.5). As a special case, our work also contributes to the traditional online flow-time scheduling. Specifically, for minimizing flow time only, CRR can yield a competitive ratio one or even arbitrarily smaller than one, when using sufficiently faster processors. Prior to our work, similar result is only known for online algorithms that needs migration [21, 23], while the best non-migratory result can achieve an O(1) competitive ratio [14]. The above result stems from an interesting observation that there always exists some optimal migratory schedule S that can be converted (in an offline sense) to a non-migratory schedule S′ with a moderate increase in flow time plus energy. More importantly, this non-migratory schedule always dispatches jobs in the same way as CRR. Copyright 2008 ACM. |
Persistent Identifier | http://hdl.handle.net/10722/93429 |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Lam, TW | en_HK |
dc.contributor.author | To, IKK | en_HK |
dc.contributor.author | Lee, LK | en_HK |
dc.contributor.author | Wong, PWH | en_HK |
dc.date.accessioned | 2010-09-25T15:00:53Z | - |
dc.date.available | 2010-09-25T15:00:53Z | - |
dc.date.issued | 2008 | en_HK |
dc.identifier.citation | Annual Acm Symposium On Parallelism In Algorithms And Architectures, 2008, p. 256-264 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/93429 | - |
dc.description.abstract | Energy usage has been an important concern in recent research on online scheduling. In this paper we extend the study of the tradeoff between flow time and energy from the single-processor setting [8, 6] to the multi-processor setting. Our main result is an analysis of a simple non-migratory online algorithm called CRR (classified round robin) on m ≤ 2 processors, showing that its flow time plus energy is within O(1) times of the optimal non-migratory offline algorithm, when the maximum allowable speed is slightly relaxed. This result still holds even if the comparison is made against the optimal migratory offline algorithm (the competitive ratio increases by a factor of 2.5). As a special case, our work also contributes to the traditional online flow-time scheduling. Specifically, for minimizing flow time only, CRR can yield a competitive ratio one or even arbitrarily smaller than one, when using sufficiently faster processors. Prior to our work, similar result is only known for online algorithms that needs migration [21, 23], while the best non-migratory result can achieve an O(1) competitive ratio [14]. The above result stems from an interesting observation that there always exists some optimal migratory schedule S that can be converted (in an offline sense) to a non-migratory schedule S′ with a moderate increase in flow time plus energy. More importantly, this non-migratory schedule always dispatches jobs in the same way as CRR. Copyright 2008 ACM. | en_HK |
dc.language | eng | en_HK |
dc.publisher | ACM. | en_HK |
dc.relation.ispartof | Annual ACM Symposium on Parallelism in Algorithms and Architectures | en_HK |
dc.subject | Competitive analysis | en_HK |
dc.subject | Dynamic speed scaling | en_HK |
dc.subject | Energy minimization | en_HK |
dc.subject | Online scheduling algorithms | en_HK |
dc.title | Competitive non-migratory scheduling for flow time and energy | en_HK |
dc.type | Conference_Paper | en_HK |
dc.identifier.email | Lam, TW: hresltk@hkucc.hku.hk | en_HK |
dc.identifier.email | Lee, LK: lklee@cs.hku.hk | en_HK |
dc.identifier.authority | Lam, TW=rp00135 | en_HK |
dc.identifier.authority | Lee, LK=rp00140 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1145/1378533.1378580 | en_HK |
dc.identifier.scopus | eid_2-s2.0-57349137634 | en_HK |
dc.identifier.hkuros | 146736 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-57349137634&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.spage | 256 | en_HK |
dc.identifier.epage | 264 | en_HK |
dc.identifier.scopusauthorid | Lam, TW=7202523165 | en_HK |
dc.identifier.scopusauthorid | To, IKK=23398547200 | en_HK |
dc.identifier.scopusauthorid | Lee, LK=12646190100 | en_HK |
dc.identifier.scopusauthorid | Wong, PWH=9734871500 | en_HK |
dc.identifier.citeulike | 6497502 | - |