Cache-Aware Allocation of Parallel Jobs on Multi-cores based on Learned Recency
Allocation de tâches parallèles sur des multi-coeurs basée sur la récence
Abstract
Scheduling of tasks on multi-and many-cores benefits significantly from the efficient use of caches. Most previous approaches use the static analysis of software in the context of the processing hardware to derive fixed allocations of software to the cache. However, there are many issues with this approach in terms of pessimism, scalability, analysis complexity, maintenance cost, etc. Furthermore, with ever more complex functionalities being implemented in the system, it becomes nearly impracticable to use static analysis for deriving cache-aware scheduling methods. This paper focuses on a dynamic approach to maximise the throughput of multi-core systems by benefiting from the cache based on empirical assessments. The principal contribution is a novel cache-aware allocation for parallel jobs that are organised as directed acyclic graphs (DAGs). Instead of allocating instruction and data blocks to caches, the proposed allocation operates at a higher abstraction level that allocates jobs to cores, based on the guidance of a predictive model that approximates the execution time of jobs with caching effects taken into account. An implementation of the predictive model is constructed to demonstrate that the execution time approximations can be effectively obtained. The experimental results, including a real-world case study, prove the concept of the proposed cacheaware allocation approach and demonstrate its effectiveness over the state-of-the-art. CCS CONCEPTS • Computer systems organization → Real-time system architecture; Processors and memory architectures.
L'ordonnancement de tâches sur des plateformes multi- ou pluri-coeurs bénéficie fortement d'une utilisation efficace des caches. La plupart des travaux précédents utilisent une approche d'analyse statique de programme pour dériver une allocation statique et fixe de tâches sur les différents cœurs. Toutefois ces approaches présentent de nombreuses faiblesses en termes de pessimisme, de passage à l'échelle, de complexité de l'analyse, de coûts de maintenance, etc. De plus, alors que croît la complexité des services implémentés dans le système, il devient quasiment impraticable d'utiliser des analyses statiques de programme pour dériver une allocation et un ordonnancement de tâches dépendent du cache. La présente contribution propose une approach dynamique pour maximiser le débit d'un système multi-coeur prenant en compte les bénéfices attendus de la hiérarchie mémoire sur la base d'observations empiriques. La contribution principale est une nouvelle politique d'allocation prenant en compte la hiérarchie mémoire, pour des graphes de tâches acycliques. Au lieu d'allouer statiquement des blocs d'instructions et de données dans les caches, l'allocation proposée se base sur un modèle prédictif approximant le temps d'exécution de chaque tâche en prenant en compte les effets de la hiérarchie mémoire. Une implémentation du modèle prédictif est construite pour démontrer que des approximations utiles du temps d'exécution des tâches peuvent être calculées. Les résultats expérimentaux, incluant une étude de cas réelle, démontrent le concept de l'allocation proposée et son efficacité par rapport à l'état de l'art.
Origin : Publisher files allowed on an open archive