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
DVS: Deterministic Victim Selection to ImprovePerformance in Work-Stealing Schedulers
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)Conference paper, Published paper (Refereed)
Abstract [en]

Task-centric programming models offer a versatile method for exposing parallelism. Such programs are popularly deployed using work-stealing scheduling runtimes. Work-stealers have traditionally employed randomness dependent techniques, considered optimal for several execution configurations. We have identified certain inefficiencies and leeway for improvement on emerging parallel architectures and workloads of fluctuating parallelism. Our deterministic victim selection (DVS) for work-stealing schedulers was designed to provide controllable and predictable uniform distribution of tasks without degrading performance; stealing is restricted between specific pairs of workers. We experimentally show that DVS offers improved scalability and performance for irregular workloads. We demonstrate DVS on Linux and Barrelfish operating systems, using an 48 core Opteron system and a simulated ideal platform respectively. On real hardware, we observed better scaling and 13% average performance gains, up to 55% for specific irregular workloads.

Place, publisher, year, edition, pages
2014.
National Category
Software Engineering
Research subject
SRA - ICT
Identifiers
URN: urn:nbn:se:kth:diva-128183OAI: oai:DiVA.org:kth-128183DiVA: diva2:647136
Conference
MULTIPROG 2014: Programmability Issues for Heterogeneous Multicores
Note

QC 20140403

Available from: 2013-09-10 Created: 2013-09-10 Last updated: 2014-04-03Bibliographically 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

multiprog.14.pdf(705 kB)136 downloads
File information
File name FULLTEXT01.pdfFile size 705 kBChecksum SHA-512
d8c3299dbfa089fc88f29997ba42a39e82a190256cc02cebbec1b4e14f608a06963198be3eab8d6f2898d5145521b3c872d10b4f464cca6a0258ba09334fe219
Type fulltextMimetype application/pdf

Other links

MULTIPROG workshop

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: 136 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

urn-nbn

Altmetric score

urn-nbn
Total: 379 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