Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Scheduling of Parallel Tasks with Proportionate Priorities
Information Technology University, Pakistan.
Marmara University, Turkey.
RISE., Swedish ICT, SICS.ORCID-id: 0000-0002-9431-5139
KTH Royal Institute of Technology, Sweden.
Visa övriga samt affilieringar
2016 (Engelska)Ingår i: Arabian Journal for Science and Engineering, ISSN 2193-567X, Vol. 41, nr 8, s. 3279-3295Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

Parallel computing systems promise higher performance for computationally intensive applications. Since programmes for parallel systems consist of tasks that can be executed simultaneously, task scheduling becomes crucial for the performance of these applications. Given dependence constraints between tasks, their arbitrary sizes, and bounded resources available for execution, optimal task scheduling is considered as an NP-hard problem. Therefore, proposed scheduling algorithms are based on heuristics. This paper presents a novel list scheduling heuristic, called the Noodle heuristic. Noodle is a simple yet effective scheduling heuristic that differs from the existing list scheduling techniques in the way it assigns task priorities. The priority mechanism of Noodle maintains a proportionate fairness among all ready tasks belonging to all paths within a task graph. We conduct an extensive experimental evaluation of Noodle heuristic with task graphs taken from Standard Task Graph. Our experimental study includes results for task graphs comprising of 50, 100, and 300 tasks per graph and execution scenarios with 2-, 4-, 8-, and 16-core systems. We report results for average Schedule Length Ratio (SLR) obtained by producing variations in Communication to Computation cost Ratio. We also analyse results for different degree of parallelism and number of edges in the task graphs. Our results demonstrate that Noodle produces schedules that are within a maximum of 12 % (in worst-case) of the optimal schedule for 2-, 4-, and 8-core systems. We also compare Noodle with existing scheduling heuristics and perform comparative analysis of its performance. Noodle outperforms existing heuristics for average SLR values. 

Ort, förlag, år, upplaga, sidor
Springer Verlag , 2016. Vol. 41, nr 8, s. 3279-3295
Nyckelord [en]
Directed acyclic graph (DAG), List scheduling, Multicore, Multiprocessor, Parallel computing, Static task scheduling
Nationell ämneskategori
Naturvetenskap
Identifikatorer
URN: urn:nbn:se:ri:diva-41860DOI: 10.1007/s13369-016-2180-9Scopus ID: 2-s2.0-84976530428OAI: oai:DiVA.org:ri-41860DiVA, id: diva2:1377775
Tillgänglig från: 2019-12-12 Skapad: 2019-12-12 Senast uppdaterad: 2023-05-25Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Person

Popov, Konstantin

Sök vidare i DiVA

Av författaren/redaktören
Popov, Konstantin
Av organisationen
SICS
Naturvetenskap

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 66 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf