Close menu

SURE

Sunderland Repository records the research produced by the University of Sunderland including practice-based research and theses.

Locality-aware task scheduling for homogeneous parallel computing systems

Bhatti, Muhammad Khurram, Oz, Isil, Amin, Sarah, Mushtaq, Maria, Farooq, Umer, Popov, Konstantin and Brorsson, Mats (2017) Locality-aware task scheduling for homogeneous parallel computing systems. Computing, 100. pp. 557-595. ISSN 0010-485X

Item Type: Article

Abstract

In systems with complex many-core cache hierarchy, exploiting data locality can significantly reduce execution time and energy consumption of parallel applications. Locality can be exploited at various hardware and software layers. For instance, by implementing private and shared caches in a multi-level fashion, recent hardware designs are already optimised for locality. However, this would all be useless if the software scheduling does not cast the execution in a manner that promotes locality available in the programs themselves. Since programs for parallel systems consist of tasks executed simultaneously, task scheduling becomes crucial for the performance in multi-level cache architectures. This paper presents a heuristic algorithm for homogeneous multi-core systems called locality-aware task scheduling (LeTS). The LeTS heuristic is a work-conserving algorithm that takes into account both locality and load balancing in order to reduce the execution time of target applications. The working principle of LeTS is based on two distinctive phases, namely; working task group formation phase (WTG-FP) and working task group ordering phase (WTG-OP). The WTG-FP forms groups of tasks in order to capture data reuse across tasks while the WTG-OP determines an optimal order of execution for task groups that minimizes the reuse distance of shared data between tasks. We have performed experiments using randomly generated task graphs by varying three major performance parameters, namely: (1) communication to computation ratio (CCR) between 0.1 and 1.0, (2) application size, i.e., task graphs comprising of 50-, 100-, and 300-tasks per graph, and (3) number of cores with 2-, 4-, 8-, and 16-cores execution scenarios. We have also performed experiments using selected real-world applications. The LeTS heuristic reduces overall execution time of applications by exploiting inter-task data locality. Results show that LeTS outperforms state-of-the-art algorithms in amortizing inter-task communication cost.

Full text not available from this repository.

More Information

Uncontrolled Keywords: Runtime resource management Parallel computing Multicore scheduling Homogeneous systems Directed acyclic graph (DAG) Embedded systems
Related URLs:
Depositing User: Umer Farooq

Identifiers

Item ID: 16386
Identification Number: https://doi.org/10.1007/s00607-017-0581-6
ISSN: 0010-485X
URI: http://sure.sunderland.ac.uk/id/eprint/16386
Official URL: https://link.springer.com/article/10.1007/s00607-0...

Users with ORCIDS

ORCID for Umer Farooq: ORCID iD orcid.org/0000-0002-5220-4908

Catalogue record

Date Deposited: 15 Aug 2023 10:26
Last Modified: 15 Aug 2023 10:26

Contributors

Author: Umer Farooq ORCID iD
Author: Muhammad Khurram Bhatti
Author: Isil Oz
Author: Sarah Amin
Author: Maria Mushtaq
Author: Konstantin Popov
Author: Mats Brorsson

University Divisions

Faculty of Technology > School of Engineering

Subjects

Engineering > Electrical Engineering

Actions (login required)

View Item (Repository Staff Only) View Item (Repository Staff Only)