Co-optimizing Core Allocation, Mapping and DVFS in Streaming Programs with Moldable Tasks for Energy Efficient Execution on Manycore Architectures
2019 (English)In: 2019 19th International Conference on Application of Concurrency to System Design (ACSD), 2019, p. 63-72Conference paper, Published paper (Refereed)
Abstract [en]
Stream programming abstracts parallelism complexity by modeling a program as a set of streaming tasks. Tasks run repeatedly and can even be internally parallel, i.e., use one or multiple cores simultaneously (moldable). The throughput of the streaming application, as well as its energy consumption, depends strongly on scheduling, i.e., on how tasks are mapped to cores, and on the frequency at which they run. Crown scheduling is a scheduling method that reduces this problem's combinatorial complexity considerably by introducing a few additional restrictions especially on tasks' core allocation sizes and mapping. While it has previously been shown to outperform competing methods, the impact of these restrictions on the schedule quality has, up to now, never been analyzed quantitatively. In this paper, we first propose several crown scheduler improvements toward fewer restrictions. Also, we provide an Integer Linear Programming formulation that solves the same optimization problem without the inherent restrictions of crown scheduling. While in an extreme case an unrestricted schedule might use 3.7 times less energy than a crown schedule for a realistic execution platform model, we show that in practical benchmarks the difference is small while crown schedulers are significantly faster than unrestricted scheduling. We experimentally confirm this with benchmarks derived from random task collections, classic parallel algorithms as well as the Streamit benchmark suite.
Place, publisher, year, edition, pages
2019. p. 63-72
Keywords [en]
parallel computing, energy efficiency, scheduling, mapping, resource allocation, dynamic voltage and frequency scaling, combinatorial optimization, integer linear programming, crown scheduling
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-168602DOI: 10.1109/ACSD.2019.00011ISI: 000719207600008ISBN: 978-1-7281-3843-5 (electronic)OAI: oai:DiVA.org:liu-168602DiVA, id: diva2:1461466
Conference
19th International Conference on Application of Concurrency to System Design (ACSD-2019), Aachen, Germany, June 23-28, 2019
2020-08-262020-08-262024-11-18Bibliographically approved