Home - SeanSpires/Project1-306-Team-Stonks GitHub Wiki

This wiki is to document Team Stonks (Team 16)'s implementation of the Branch and Bound algorithm to solve the multi-processing scheduling problem.

The Problem

As processor technology have begun to reach physical limitations, more and more computer systems have started to utilise multiple processors (parallelisation) to increase performance. To efficiently use more than one processor, a software program must be written correspondingly. The program must be divided or split into multiple tasks and they must be executed by the different processors. A crucial problem for the efficiency of executing such a parallel program is how tasks are mapped to the available processors and in which order they are executed.

A program is described by a task graph, where the nodes of the graph represent tasks and the edges represent data transfer or dependencies between the tasks. The data transfers are directed and there must not be any cycle, which makes the graph a directed acyclic graph. Our scheduling problem now becomes the assignment of the nodes (tasks) of the graph to a given set of p processors. We also need to define the order in which the tasks are executed on the processors. The objective is to do the mapping and ordering of the tasks in such a way that the total execution time of the program is minimised.