On the application task granularity and the interplay with the scheduling overhead in many-core shared memory systems

QC 20160513
Task-based programming models are considered one of the most promising programming model approaches for exascale supercomputers because of their ability to dynamically react to changing conditions and reassign work to processing elements. One question, however, remains unsolved: what should the task granularity of task-based applications be? Fine-grained tasks offer more opportunities to balance the system and generally result in higher system utilization. However, they also induce in large scheduling overhead. The impact of scheduling overhead on coarse-grained tasks is lower, but large systems may result imbalanced and underutilized. In this work we propose a methodology to analyze the interplay between application task granularity and scheduling overhead. Our methodology is based on three main points: 1) a novel task algorithm that analyzes an application directed acyclic graph (DAG) and aggregates tasks, 2) a fast and precise emulator to analyze the application behavior on systems with up to 1,024 cores, 3) a comprehensive sensitivity analysis of application performance and scheduling overhead breakdown. Our results show that there is an optimal task granularity between 1.2x10^4 and 10x10^4 cycles for the representative schedulers. Moreover, our analysis indicates that a suitable scheduler for exascale task-based applications should employ a best-effort local scheduler and a sophisticated remote scheduler to move tasks across worker threads.

TEKNIK OCH TEKNOLOGIER Elektroteknik och elektronik Datorsystem hsv//swe
ENGINEERING AND TECHNOLOGY Electrical Engineering, Electronic Engineering, Information Engineering Computer Systems hsv//eng
Scheduling overhead
Task granularity
Task-based programming models
Task-based schedulers
Cluster computing
Computer architecture
Directed graphs
Sensitivity analysis
Supercomputers
Application behaviors
Application performance
Directed acyclic graph (DAG)
Processing elements
Programming models
Shared memory system
Task-based
Scheduling

Kestor, G. (author)
Gioiosa, R. (author)
Markidis, StefanoKTH,Beräkningsvetenskap och beräkningsteknik (CST)(Swepub:kth)u1y5heyt (author)
Laure, ErwinKTH,Beräkningsvetenskap och beräkningsteknik (CST)(Swepub:kth)u1n9d88r (author)
KTHBeräkningsvetenskap och beräkningsteknik (CST) (creator_code:org_t)

In:Proceedings - IEEE International Conference on Cluster Computing, ICCC: IEEE, s. 428-4379781467365987

By the author/editor: Akhmetova, D.; Kestor, G.; Gioiosa, R.; Markidis, Stefan ...; Laure, Erwin

About the subject

ENGINEERING AND TECHNOLOGY: ENGINEERING AND ...; and Electrical Engin ...; and Computer Systems

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.