Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, Published 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.
Series
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
Identifiers
URN: urn:nbn:se:bth-6413DOI: 10.1109/ISPDC.2014.21ISI: 000360933900019Local ID: oai:bth.se:forskinfo3286C721500AD2A6C1257DF000334A06ISBN: 978-1-4799-5918-1 (print)OAI: oai:DiVA.org:bth-6413DiVA: diva2:833919
Conference
13th International Symposium on Parallel and Distributed Computing (ISPDC), Marseille
Note

Published in proceedings of 2014 IEEE 13th International Symposium on Parallel and Distributed Computing (ISPDC), http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6898623

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

Open Access in DiVA

fulltext(86 kB)274 downloads
File information
File name FULLTEXT01.pdfFile size 86 kBChecksum SHA-512
aa1928768b97341b1be6ddb693af84c68e4acf74d0d0a2b2efbd45eadb72791b84419e770d72c4a10941afc9bd7dc03df13a6b117d8da0d4e7cf573df53754d7
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: 274 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

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 218 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf