Task Scheduling in Parallel Computing

Project Code: 813

Faculty: Faculty of Engineering

Department: Electrical & Computer Engineering

Main Supervisor: Dr Oliver Sinnen

Application open date: 01 Sep 2019

Application deadline: 01 Dec 2022

Enrolment information: NZ Citizens, NZ Permanent Residents, International

Introduction

Crucial for the efficiency of a parallel program is how the (sub)tasks of the program are mapped and ordered on the processors of the system. In task scheduling, the program is represented by a graph, where the nodes represent the tasks and the edges the communication between the tasks. The objective is then to find the best scheduling of this graph on the processors that allows the fastest execution of the program. Unfortunately, this is a very difficult optimisation problem (NP-hard). The research in this area deals with algorithm design, graph theory, complexity theory, multi-criteria optimisation, experimental evaluations on real parallel systems and system modelling. Several PhD and ME projects are available.

What we are looking for in a successful applicant

Knowledge and skills in

  • algorithm design and analysis
  • complexity analysis
  • abstract thinking
  • graph theory
  • conducting experimental and simulation evaluations
Objective

Investigaion and proposal of methods, technologies and approaches for effecient scheduling. This can include one or more of the following:

  • new scheduling models
  • novel algorithms
  • new insights into the complexity of scheduling problems
  • theorectical properties of problems and algorithms, such as bounds or approximation factors
  • implementation and experimental evaluation of algorithms
Other information
Related opportunities