Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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
Palirria: Accurate on-line parallelism estimation for adaptive work-stealing
KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.ORCID iD: 0000-0002-7860-6593
KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.ORCID iD: 0000-0002-9637-2065
2014 (English)In: PMAM'14 Proceedings of Programming Models and Applications on Multicores and Manycore, ACM Press, 2014, 120-130 p.Conference paper, Published paper (Refereed)
Abstract [en]

We present Palirria, a self-adapting work-stealing scheduling method for nested fork/join parallelism that can be used to estimate the number of utilizable workers and self-adapt accordingly. The estimation mechanism is optimized for accuracy, minimizing the requested resources without degrading performance. We implemented Palirria for both the Linux and Barrelfish operating systems and evaluated it on two platforms: a 48-core NUMA multiprocessor and a simulated 32-core system. Compared to state-of-the-art, we observed higher accuracy in estimating resource requirements. This leads to improved resource utilization and performance on par or better to executing with fixed resource allotments.

Place, publisher, year, edition, pages
ACM Press, 2014. 120-130 p.
Keyword [en]
parallel, workload, runtime, task, adaptive, resource management, load balancing, work-stealing
National Category
Software Engineering
Identifiers
URN: urn:nbn:se:kth:diva-128184Scopus ID: 2-s2.0-84897716570ISBN: 978-1-4503-2657-5 (print)OAI: oai:DiVA.org:kth-128184DiVA: diva2:647141
Conference
2014 International Workshop on Programming Models and Applications for Multicores and Manycores, PMAM 2014; Orlando, FL; United States; 15 February 2014 through 15 February 2014
Note

QC 20140520

Available from: 2013-09-10 Created: 2013-09-10 Last updated: 2017-04-28Bibliographically approved
In thesis
1. Cooperative user- and system-level scheduling of task-centric parallel programs
Open this publication in new window or tab >>Cooperative user- and system-level scheduling of task-centric parallel programs
2013 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

Emerging architecture designs include tens of processing cores on a single chip die; it is believed that the number of cores will reach the hundreds in not so many years from now. However, most common workloads cannot expose fluctuating parallelism, insufficient to utilize such systems. The combination of these issues suggests that large-scale systems will be either multiprogrammed or have their unneeded resources powered off. To achieve these features, workloads must be able to provide a metric on their parallelism which the system can use to dynamically adapt per-application resource allotments.Adaptive resource management requires scheduling abstractions to be split into two cooperating layers. The system layer that is aware of the availability of resources and the application layer which can accurately and iteratively estimate the workload's true resource requirements.This thesis addresses these issues and provides a self-adapting work-stealing scheduling method that can achieve expected performance while conserving resources. This method is based on deterministic victim selection (DVS) that controls the concentration of the load among the worker threads. It allows to use the number of spawned but not yet processed tasks as a metric for the requirements. Because this metric measures work to be executed in the future instead of past behavior, DVS is versatile to handlevery irregular workloads.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2013. vi, 29 p.
Series
Trita-ICT-ECS AVH, ISSN 1653-6363 ; 13:15
Keyword
parallel, workload, runtime, task, adaptive, resource management, load balancing, work-stealing
National Category
Other Electrical Engineering, Electronic Engineering, Information Engineering
Research subject
SRA - ICT
Identifiers
urn:nbn:se:kth:diva-127708 (URN)978-91-7501-816-4 (ISBN)
Presentation
2013-09-27, Sal/Hall D, Forum, KTH-ICT, Isafjordsgatan 39, Kista, 12:10 (English)
Opponent
Supervisors
Note

QC 20130910

Available from: 2013-09-10 Created: 2013-09-04 Last updated: 2013-09-17Bibliographically approved

Open Access in DiVA

p120-varisteas.pdf(802 kB)117 downloads
File information
File name FULLTEXT01.pdfFile size 802 kBChecksum SHA-512
8f4f8f27295062d465a11f1096cc1097bd85038d7dad779253c65e74eee11b2ecd164fbcddb0c98adf90765a98c9015a55a603af02fc9fbe6d9bba65ed69b772
Type fulltextMimetype application/pdf

Other links

ScopusPalirria

Authority records BETA

Varisteas, GeorgiosBrorsson, Mats

Search in DiVA

By author/editor
Varisteas, GeorgiosBrorsson, Mats
By organisation
Software and Computer systems, SCS
Software Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 117 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

isbn
urn-nbn

Altmetric score

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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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