##### **File Download**

##### **Links for fulltext**

##### (May Require Subscription)

**Publisher Website:**10.1145/1583991.1583994**Scopus:**eid_2-s2.0-70449625501

**Conference Paper**: Speed scaling of processes with arbitrary speedup curves on a multiprocessor

Title | Speed scaling of processes with arbitrary speedup curves on a multiprocessor |
---|---|

Authors | |

Keywords | Competitive algorithms Competitive ratio Deterministic algorithms Flow-time Lower bounds |

Issue Date | 2009 |

Publisher | ACM. |

Citation | The 21st Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA 2009), Alberta, Canada, 11-13 August 2009. In Proceedings of the Annual ACM-SPAA, 2009, p. 1-10 How to Cite? |

Abstract | We consider the setting of a multiprocessor where the speeds of the m processors can be individually scaled. Jobs arrive over time and have varying degrees of parallelizability. A nonclairvoyant scheduler must assign the jobs to processors, and scale the speeds of the processors. We consider the objective of energy plus flow time. For jobs that may have side effects or that are not checkpointable, we show an Ωm((α-1)/α2) bound on the competitive ratio of any deterministic algorithm. Here m is the number of processors and α is the exponent of the power function. For checkpointable jobs without side effects, we give an O(log m)-competitive algorithm. Thus for jobs that may have side effects or that are not checkpointable, the achievable competitive ratio grows quickly with the number of processors, but for checkpointable jobs without side effects, the achievable competitive ratio grows slowly with the number of processors. We then show a lower bound of Ω(log1/α m) on the competitive ratio of any algorithm for checkpointable jobs without side effects. Finally we slightly improve the upper bound on the competitive ratio for the single processor case, which is equivalent to the case that all jobs are fully parallelizable, by giving an improved analysis of a previously proposed algorithm. Copyright 2009 ACM. |

Persistent Identifier | http://hdl.handle.net/10722/125698 |

ISBN | |

References |

DC Field | Value | Language |
---|---|---|

dc.contributor.author | Chan, HL | en_HK |

dc.contributor.author | Edmonds, J | en_HK |

dc.contributor.author | Pruhs, K | en_HK |

dc.date.accessioned | 2010-10-31T11:46:43Z | - |

dc.date.available | 2010-10-31T11:46:43Z | - |

dc.date.issued | 2009 | en_HK |

dc.identifier.citation | The 21st Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA 2009), Alberta, Canada, 11-13 August 2009. In Proceedings of the Annual ACM-SPAA, 2009, p. 1-10 | en_HK |

dc.identifier.isbn | 978-1-60558-606-9 | - |

dc.identifier.uri | http://hdl.handle.net/10722/125698 | - |

dc.description.abstract | We consider the setting of a multiprocessor where the speeds of the m processors can be individually scaled. Jobs arrive over time and have varying degrees of parallelizability. A nonclairvoyant scheduler must assign the jobs to processors, and scale the speeds of the processors. We consider the objective of energy plus flow time. For jobs that may have side effects or that are not checkpointable, we show an Ωm((α-1)/α2) bound on the competitive ratio of any deterministic algorithm. Here m is the number of processors and α is the exponent of the power function. For checkpointable jobs without side effects, we give an O(log m)-competitive algorithm. Thus for jobs that may have side effects or that are not checkpointable, the achievable competitive ratio grows quickly with the number of processors, but for checkpointable jobs without side effects, the achievable competitive ratio grows slowly with the number of processors. We then show a lower bound of Ω(log1/α m) on the competitive ratio of any algorithm for checkpointable jobs without side effects. Finally we slightly improve the upper bound on the competitive ratio for the single processor case, which is equivalent to the case that all jobs are fully parallelizable, by giving an improved analysis of a previously proposed algorithm. Copyright 2009 ACM. | en_HK |

dc.language | eng | en_HK |

dc.publisher | ACM. | - |

dc.relation.ispartof | Proceedings of the Annual ACM Symposium on Parallel Algorithms and Architectures | en_HK |

dc.subject | Competitive algorithms | - |

dc.subject | Competitive ratio | - |

dc.subject | Deterministic algorithms | - |

dc.subject | Flow-time | - |

dc.subject | Lower bounds | - |

dc.title | Speed scaling of processes with arbitrary speedup curves on a multiprocessor | en_HK |

dc.type | Conference_Paper | en_HK |

dc.identifier.openurl | http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=978-1-60558-606-9&volume=&spage=1&epage=10&date=2009&atitle=Speed+scaling+of+processes+with+arbitrary+speedup+curves+on+a+multiprocessor | - |

dc.identifier.email | Chan, HL:hlchan@cs.hku.hk | en_HK |

dc.identifier.authority | Chan, HL=rp01310 | en_HK |

dc.description.nature | link_to_OA_fulltext | - |

dc.identifier.doi | 10.1145/1583991.1583994 | en_HK |

dc.identifier.scopus | eid_2-s2.0-70449625501 | en_HK |

dc.identifier.hkuros | 181824 | en_HK |

dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-70449625501&selection=ref&src=s&origin=recordpage | en_HK |

dc.identifier.spage | 1 | en_HK |

dc.identifier.epage | 10 | en_HK |

dc.description.other | The 21st Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA) 2009, Alberta, Canada, 11-13 August 2009. In Proceedings of the Annual ACM-SPAA, 2009, p. 1-10 | - |

dc.identifier.scopusauthorid | Chan, HL=7403402384 | en_HK |

dc.identifier.scopusauthorid | Edmonds, J=7102594589 | en_HK |

dc.identifier.scopusauthorid | Pruhs, K=6603866438 | en_HK |

dc.identifier.citeulike | 9169057 | - |