liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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
Crown Scheduling: Energy-Efficient Resource Allocation, Mapping and Discrete Frequency Scaling for Collections of Malleable Streaming Tasks
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology. (PELAB)ORCID iD: 0000-0001-5241-0026
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology. (PELAB)ORCID iD: 0000-0002-1940-3331
FernUniversität in Hagen, Germany. (Parallelität und VLSI)
FernUniversität in Hagen, Germany. (Parallelität und VLSI)
2013 (English)In: Proceedings of the 23rd International Workshop on Power and Timing Modeling, Optimization and Simulation (PATMOS), 2013 / [ed] Jörg Henkel and Alex Yakovlev (eds.), IEEE Computer Society Digital Library, 2013, 215-222 p.Conference paper, Published paper (Refereed)
Abstract [en]

We investigate the problem of generating energy-optimal code for a collection of streaming tasks that include parallelizable or malleable tasks on a generic many-core processor with dynamic discrete frequency scaling. Streaming task collections differ from classical task sets in that all tasks are running concurrently, so that cores typically run several tasks that are scheduled round-robin at user level in a data driven way. A stream of data flows through the tasks and intermediate results are forwarded to other tasks like in a pipelined task graph. In this paper we present crown scheduling, a novel technique for the combined optimization of resource allocation, mapping and discrete voltage/frequency scaling for malleable streaming task sets in order to optimize energy efficiency given a throughput constraint. We present optimal off-line algorithms for separate and integrated crown scheduling based on integer linear programming (ILP). We also propose extensions for dynamic rescaling to automatically adapt a given crown schedule in situations where not all tasks are data ready. Our energy model considers both static idle power and dynamic power consumption of the processor cores. Our experimental evaluation of the ILP models for a generic manycore architecture shows that at least for small and medium sized task sets even the integrated variant of crown scheduling can be solved to optimality by a state-of-the-art ILP solver within a few seconds.

Place, publisher, year, edition, pages
IEEE Computer Society Digital Library, 2013. 215-222 p.
Keyword [en]
scheduling, streaming tasks, energy optimization, task mapping, malleable tasks, multicore processor, parallel computing, DVFS, frequency scaling, resource allocation, integer linear programming
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-102581DOI: 10.1109/PATMOS.2013.6662176ISI: 000335501300029OAI: oai:DiVA.org:liu-102581DiVA: diva2:679365
Conference
23rd International Workshop on Power and Timing Modeling, Optimization and Simulation (PATMOS), Karlsruhe, 9-11 September 2013
Projects
Integrated Software Pipelining (VR)
Funder
Swedish Research Council, 621-2009-4449Swedish e‐Science Research Center, OpCoReS
Available from: 2013-12-15 Created: 2013-12-15 Last updated: 2015-02-24

Open Access in DiVA

No full text

Other links

Publisher's full textArticle in IEEE XploreAuthor version (PDF)

Authority records BETA

Kessler, ChristophMelot, Nicolas

Search in DiVA

By author/editor
Kessler, ChristophMelot, Nicolas
By organisation
Software and SystemsThe Institute of Technology
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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