Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Locality-aware task scheduling for homogeneous parallel computing systems
Information Technology University (ITU), Pakistan.
Izmir Institute of Technology, Turkey.
Information Technology University (ITU), Pakistan.
Information Technology University (ITU), Pakistan.
Show others and affiliations
2018 (English)In: Computing, ISSN 0010-485X, E-ISSN 1436-5057, Vol. 100, no 6, p. 557-595Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
2018. Vol. 100, no 6, p. 557-595
Keywords [en]
Directed acyclic graph (DAG), Embedded systems, Homogeneous systems, Multicore scheduling, Parallel computing, Runtime resource management, Directed graphs, Distributed computer systems, Energy utilization, Hardware, Heuristic algorithms, Multitasking, Optimization, Parallel processing systems, Scheduling algorithms, Homogeneous system, Multi core, Multi-level cache architecture, Parallel computing system, Performance parameters, Resource management, State-of-the-art algorithms, Scheduling
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:ri:diva-33981DOI: 10.1007/s00607-017-0581-6Scopus ID: 2-s2.0-85032798462OAI: oai:DiVA.org:ri-33981DiVA, id: diva2:1230345
Available from: 2018-07-03 Created: 2018-07-03 Last updated: 2023-05-25Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Popov, Konstantin

Search in DiVA

By author/editor
Popov, Konstantin
By organisation
SICS
In the same journal
Computing
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 46 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf