Change search
ReferencesLink to record
Permanent link

Direct link
Effective cooperative scheduling of task-parallel applications on multiprogrammed parallel architectures
KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS. (Multicore Center)ORCID iD: 0000-0002-7860-6593
2015 (English)Doctoral thesis, monograph (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 parallel workloads cannot fully utilize such systems. They expose fluctuating parallelism, and do not scale up indefinitely as there is usually a point after which synchronization costs outweigh the gains of parallelism. The combination of these issues suggests that large-scale systems will be either multiprogrammed or have their unneeded resources powered off.Multiprogramming leads to hardware resource contention and as a result application performance degradation, even when there are enough resources, due to negative share effects and increased bus traffic. Most often this degradation is quite unbalanced between co-runners, as some applications dominate the hardware over others. Current Operating Systems blindly provide applications with access to as many resources they ask for. This leads to over-committing the system with too many threads, memory contention and increased bus traffic. Due to the inability of the application to have any insight on system-wide resource demands, most parallel workloads will create as many threads as there are available cores. If every co-running application does the same, the system ends up with threads $N$ times the amount of cores. Threads then need to time-share cores, so the continuous context-switching and cache line evictions generate considerable overhead.This thesis proposes a novel solution across all software layers that achieves throughput optimization and uniform performance degradation of co-running applications. Through a novel fully automated approach (DVS and Palirria), task-parallel applications can accurately quantify their available parallelism online, generating a meaningful metric as parallelism feedback to the Operating System. A second component in the Operating System scheduler (Pond) uses such feedback from all co-runners to effectively partition available resources.The proposed two-level scheduling scheme ultimately achieves having each co-runner degrade its performance by the same factor, relative to how it would execute with unrestricted isolated access to the same hardware. We call this fair scheduling, departing from the traditional notion of equal opportunity which causes uneven degradation, with some experiments showing at least one application degrading its performance 10 times less than its co-runners.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2015. , xiii, 154 p.
, TRITA-ICT, 2015:14
Keyword [en]
multicore, parallel, scheduler, workload, runtime, task, adaptive, resource management, load balancing, work-stealing
National Category
Communication Systems
Research subject
Computer Science
URN: urn:nbn:se:kth:diva-175461ISBN: 978-91-7595-708-1OAI: diva2:861129
Public defence
2015-11-09, Rum 301, Elektrum, KTH-ICT, Isafjordagatan 31, Kista, 09:00 (English)

QC 20151016

Available from: 2015-10-16 Created: 2015-10-15 Last updated: 2015-10-16Bibliographically approved

Open Access in DiVA

phd_varisteas(4343 kB)231 downloads
File information
File name FULLTEXT01.pdfFile size 4343 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Varisteas, Georgios
By organisation
Software and Computer systems, SCS
Communication Systems

Search outside of DiVA

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

Total: 773 hits
ReferencesLink to record
Permanent link

Direct link