Locality-aware task scheduling for homogeneous parallel computing systems

↓ Direkt till sidans innehåll
↓ Direkt till sidans sekundära innehåll (sidomenyn)

Sökning: WFRF:(Brorsson Mats 1962 ) > Locality-aware task...

Bhatti, Muhammad KhurramInformation Technology University (ITU), Pakistan,Informat Technol Univ, Embedded Comp Lab, 346-B Ferozpur Rd, Lahore, Pakistan. (författare)

Locality-aware task scheduling for homogeneous parallel computing systems

Artikel/kapitelEngelska2018

Förlag, utgivningsår, omfång ...

2017-11-01
Springer Science and Business Media LLC,2018
printrdacarrier

Nummerbeteckningar

LIBRIS-ID:oai:DiVA.org:ri-33981
https://urn.kb.se/resolve?urn=urn:nbn:se:ri:diva-33981URI
https://doi.org/10.1007/s00607-017-0581-6DOI
https://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-230491URI

Kompletterande språkuppgifter

Språk:engelska
Sammanfattning på:engelska

Ingår i deldatabas

SwePubSwePub

Klassifikation

Ämneskategori:ref swepub-contenttype
Ämneskategori:art swepub-publicationtype

Anmärkningar

QC 20180614
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.

Ämnesord och genrebeteckningar

NATURVETENSKAP Data- och informationsvetenskap hsv//swe
NATURAL SCIENCES Computer and Information Sciences hsv//eng
NATURVETENSKAP Fysik Annan fysik hsv//swe
NATURAL SCIENCES Physical Sciences Other Physics Topics hsv//eng
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

Biuppslag (personer, institutioner, konferenser, titlar ...)

Oz, IsilIzmir Institute of Technology, Turkey,Izmir Inst Technol, Comp Engn Dept, Izmir, Turkey. (författare)
Amin, SarahInformation Technology University (ITU), Pakistan,Informat Technol Univ, Embedded Comp Lab, 346-B Ferozpur Rd, Lahore, Pakistan. (författare)
Mushtaq, MariaInformation Technology University (ITU), Pakistan,Informat Technol Univ, Embedded Comp Lab, 346-B Ferozpur Rd, Lahore, Pakistan. (författare)
Farooq, UmerDhofar University, Oman,Dhofar Univ, Dept Elect & Comp Engn, Salalah 211, Oman. (författare)
Popov, KonstantinRISE,SICS,SICS, Isafjordsgatan 22, S-16429 Kista, Sweden.(Swepub:ri)KonstantinPo@ri.se (författare)
Brorsson, Mats,1962-KTH,Programvaruteknik och datorsystem, SCS,KTH Royal Institute of Technology, Sweden(Swepub:kth)u1dkd5v9 (författare)
Information Technology University (ITU), PakistanInformat Technol Univ, Embedded Comp Lab, 346-B Ferozpur Rd, Lahore, Pakistan. (creator_code:org_t)

Sammanhörande titlar

Ingår i:Computing: Springer Science and Business Media LLC100:6, s. 557-5950010-485X1436-5057

Internetlänk

Hitta via bibliotek

Computing (Sök värdpublikationen i LIBRIS)

Till lärosätets databas

Hitta mer i SwePub

Av författaren/redakt...: Bhatti, Muhammad ...; Oz, Isil; Amin, Sarah; Mushtaq, Maria; Farooq, Umer; Popov, Konstanti ...; visa fler...; Brorsson, Mats, ...; visa färre...

Om ämnet

NATURVETENSKAP: NATURVETENSKAP; och Data och informa ...

NATURVETENSKAP: NATURVETENSKAP; och Fysik; och Annan fysik

Artiklar i publikationen: Computing

Av lärosätet: RISE; Kungliga Tekniska Högskolan

Sök utanför SwePub

Sök vidare i:: Google; Google Book Search; Google Scholar

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.

LIBRIS.kb.se