Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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
Noodle: A Heuristic Algorithm for Task Scheduling in MPSoC Architectures
KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.ORCID iD: 0000-0003-3958-4659
Show others and affiliations
2014 (English)In: Proceedings - 2014 17th Euromicro Conference on Digital System Design, DSD 2014, 2014, 667-670 p.Conference paper, Published paper (Refereed)
Abstract [en]

Task scheduling is crucial for the performance of parallel 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(1) presents a novel heuristic algorithm, called the Noodle heuristic, which differs from the existing list scheduling techniques in the way it assigns task priorities. We conduct an extensive experimental to validate Noodle for task graphs taken from Standard Task Graph (STG). Results show 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.

Place, publisher, year, edition, pages
2014. 667-670 p.
Keyword [en]
List Scheduling, Directed Acyclic Graph (DAG), Multiprocessor System-on-Chip(MPSoC), Parallel Computing
National Category
Computer Systems
Identifiers
URN: urn:nbn:se:kth:diva-172646DOI: 10.1109/DSD.2014.71ISI: 000358409000091Scopus ID: 2-s2.0-84928812217ISBN: 978-1-4799-5793-4 (print)OAI: oai:DiVA.org:kth-172646DiVA: diva2:849090
Conference
17th Euromicro Conference on Digital System Design (DSD), AUG 27-29, 2014, Verona, ITALY
Note

QC 20150827

Available from: 2015-08-27 Created: 2015-08-27 Last updated: 2015-08-27Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Muddukrishna, AnanyaBrorsson, Mats

Search in DiVA

By author/editor
Muddukrishna, AnanyaBrorsson, Mats
By organisation
Software and Computer systems, SCS
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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