Change search
ReferencesLink to record
Permanent link

Direct link
Local Linear Time Convergence of a Primal-Dual Energy Minimization Algorithm for Parallel Processing
Blekinge Institute of Technology, Faculty of Engineering, Department of Mathematics and Natural Sciences.
2014 (English)Conference paper (Refereed)
Abstract [en]

We consider energy minimization by speed-scaling of an open shop multiprocessor with n jobs and m machines. The paper studies the complexity of a primal-dual solution algorithm of [4], which was an open question in that paper.We prove that in a neighbourhood of the solution the complexity of the algorithm is O(mn log(1/ε) if n and m are not equal and ε is the roundoff error of the computer. The paper demonstrates how linearization can be used to investigate the complexity of an algorithm close to the optimum. An estimate of the size of the neighbourhood where the linearization error is smaller than the computer’s roundoff error is also given.

Abstract [sv]

Pappret undersöker en energiminimiseringsalgoritm för en multiprocessor där processorns hastighet kan lokalt varieras för att minimera energin. För en open shop multiprocessor med n tasks och m maskiner studeras effektiviteten för en nyligen publicerad primal-dual algoritm. Nära optimium är dess komplexitet O(mn log(1/ε)) om n och m inte är lika och ε är datorns avrundningsfel. I pappret demonstreras hur linjarisering kan användas för att undersöka en algoritms komplexitet nära optimum. Vi visare också en uppskattning storleken för det område runt optimum där linjariseringsfelet är mindre än datorns avrundningsfel.

Place, publisher, year, edition, pages
IEEE , 2014.
, International Symposium on Parallel and Distributed Computing, ISSN 2379-5352
Keyword [en]
Open shop multiprocessor, Primal-dual algoritm, Speed-scaling, Complexity, Linearization.
National Category
Mathematical Analysis Computer Science
URN: urn:nbn:se:bth-6413DOI: 10.1109/ISPDC.2014.21ISI: 000360933900019Local ID: 978-1-4799-5918-1OAI: diva2:833919
13th International Symposium on Parallel and Distributed Computing (ISPDC), Marseille

Published in proceedings of 2014 IEEE 13th International Symposium on Parallel and Distributed Computing (ISPDC),

Available from: 2015-02-18 Created: 2015-02-18 Last updated: 2015-10-20Bibliographically approved

Open Access in DiVA

fulltext(86 kB)26 downloads
File information
File name FULLTEXT01.pdfFile size 86 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Lennerstad, Håkan
By organisation
Department of Mathematics and Natural Sciences
Mathematical AnalysisComputer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 26 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 25 hits
ReferencesLink to record
Permanent link

Direct link