%0 Conference Paper %1 Albers:2011:MSS:1989493.1989539 %A Albers, Susanne %A Antoniadis, Antonios %A Greiner, Gero %B Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures %C New York, NY, USA %D 2011 %I ACM %K multiprocessor speed.scaling %P 279--288 %R 10.1145/1989493.1989539 %T On multi-processor speed scaling with migration: extended abstract %X We investigate a very basic problem in dynamic speed scaling where a sequence of jobs, each specified by an arrival time, a deadline and a processing volume, has to be processed so as to minimize energy consumption. Previous work has focused mostly on the setting where a single variable-speed processor is available. In this paper we study multi-processor environments with <i>m</i> parallel variable-speed processors assuming that job migration is allowed, i.e. whenever a job is preempted it may be moved to a different processor.</p> <p>We first study the offline problem and show that optimal schedules can be computed efficiently in polynomial time. In contrast to a previously known strategy, our algorithm does not resort to linear programming. We develop a fully combinatorial algorithm that relies on repeated maximum flow computations. The approach might be useful to solve other problems in dynamic speed scaling. For the online problem, we extend two algorithms <i>Optimal Available</i> and <i>Average Rate</i> proposed by Yao et al. 16 for the single processor setting. We prove that <i>Optimal Available</i> is &#945;^&#945;-competitive, as in the single processor case. Here &#945;&#62;1 is the exponent of the power consumption function. While it is straightforward to extend <i>Optimal Available</i> to parallel processing environments, the competitive analysis becomes considerably more involved. For <i>Average Rate</i> we show a competitiveness of (3&#945;)^&#945;/2 + 2^&#945;. %@ 978-1-4503-0743-7

@inproceedings{Albers:2011:MSS:1989493.1989539, abstract = {We investigate a very basic problem in dynamic speed scaling where a sequence of jobs, each specified by an arrival time, a deadline and a processing volume, has to be processed so as to minimize energy consumption. Previous work has focused mostly on the setting where a single variable-speed processor is available. In this paper we study multi-processor environments with <i>m</i> parallel variable-speed processors assuming that job migration is allowed, i.e. whenever a job is preempted it may be moved to a different processor.</p> <p>We first study the offline problem and show that optimal schedules can be computed efficiently in polynomial time. In contrast to a previously known strategy, our algorithm does not resort to linear programming. We develop a fully combinatorial algorithm that relies on repeated maximum flow computations. The approach might be useful to solve other problems in dynamic speed scaling. For the online problem, we extend two algorithms <i>Optimal Available</i> and <i>Average Rate</i> proposed by Yao et al. [16] for the single processor setting. We prove that <i>Optimal Available</i> is &#945;^&#945;-competitive, as in the single processor case. Here &#945;&#62;1 is the exponent of the power consumption function. While it is straightforward to extend <i>Optimal Available</i> to parallel processing environments, the competitive analysis becomes considerably more involved. For <i>Average Rate</i> we show a competitiveness of (3\&#945;)^&#945;/2 + 2^&#945;.}, acmid = {1989539}, added-at = {2013-01-11T21:04:48.000+0100}, address = {New York, NY, USA}, author = {Albers, Susanne and Antoniadis, Antonios and Greiner, Gero}, biburl = {https://www.bibsonomy.org/bibtex/2a7a629e5561f72f215ab3234660ac724/ytyoun}, booktitle = {Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures}, doi = {10.1145/1989493.1989539}, interhash = {e2a3be8af8f7725121e166d503465a3c}, intrahash = {a7a629e5561f72f215ab3234660ac724}, isbn = {978-1-4503-0743-7}, keywords = {multiprocessor speed.scaling}, location = {San Jose, California, USA}, numpages = {10}, pages = {279--288}, publisher = {ACM}, series = {SPAA '11}, timestamp = {2013-01-11T21:04:48.000+0100}, title = {On multi-processor speed scaling with migration: extended abstract}, year = 2011 }