Noodle : A heuristic algorithm for task scheduling in MPSoC architectures

• 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 paper1 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.

Ämnesord

TEKNIK OCH TEKNOLOGIER  -- Elektroteknik och elektronik -- Datorsystem (hsv//swe)

ENGINEERING AND TECHNOLOGY  -- Electrical Engineering, Electronic Engineering, Information Engineering -- Computer Systems (hsv//eng)

Nyckelord

Directed Acyclic Graph (DAG)

List Scheduling

Multiprocessor System-on-Chip(MPSoC)

Parallel Computing

Algorithms

Application specific integrated circuits

Computational complexity

Directed graphs

Heuristic algorithms

Microprocessor chips

Multiprocessing systems

Multitasking

Optimization

Parallel processing systems

Scheduling

System-on-chip

Comparative analysis

List-scheduling

MPSoC architectures

Multiprocessor system on chips

Optimal schedule

Parallel application

Scheduling heuristics

Scheduling algorithms

Publikations- och innehållstyp

ref (ämneskategori)

kon (ämneskategori)