BlommaGraphs

• Website
• Source code

Multi-core architectures of computers, which are common for today, demand processes to be parallelised as efficiently as possible to maximize utilisation of cores and to minimize communication costs between them.

For this reason, processes are separated into atomic operations, called tasks. Dependencies between tasks create a directed, acyclic graph, called task graph. Nodes are formed by tasks whereas dependencies are modelled by edges. Since each task needs some time to complete and time is spent for communication between tasks (e.g. to exchange data), both, nodes and edges, are weighted. Communication time is only needed if two dependent tasks are not executed on the same CPU-core.

The project goal was to schedule these tasks most efficiently on a pre-defined architecture (i.e. number of cores). Different scheduling algorithms have been implemented as well as tools to evaluate the results automatically.

The BlommaGraphs tool suite is the result of the project. It can be used to generate and schedule task graphs and to evaluate the produced results.

To create new task graphs, a task graph generator has been built. A variety of parameters like number of tasks, branching factor and intervals for execution and communication times can be configured to generate different kinds of graphs. These can be used to evaluate scheduling algorithms under different working conditions.

To represent task graphs in human readable form, a serializer has been implemented using the STG format (with communication costs). This is also used to save task graphs into files.

Three scheduling algorithms have been implemented:

• LAST (Localized Allocation of Static Tasks)
• DLS (Dynamic Level Scheduling)
• Genetic algorithm (developed by ourselves)

It is also possible to schedule streams of task graphs, i.e. one process is executed multiple times in parallel. A simple concept merges a number of graphs into one and uses scheduling algorithms mentionend above. In addition, a custom algorithm has been implemented to schedule multiple task graphs.

To compare the results of different approaches, an evaluation tool has been developed. It creates a set of task graphs, schedules them using the available algorithms and generates a visualized representation of the results. Among the evaluated characteristics of each algorithm are its runtime, satisfaction of deadlines and duration of the schedule. By using the output of the evaluation tool, it is possible to assess the quality of scheduling algorithms. Some examples can be found on the official website.