Parallel solution of executable graph

OData support
Dr. Mezei Gergely
Department of Automation and Applied Informatics

Nowadays there is an increasing demand for computing power in every field of computing. To satisfy the increased demand, extremely better hardware and software solutions are provided to us than in the past. With the use of an executable graph we are able to provide a general and fast solution for evaluating mathematical formulas. The demand for evaluating mathematical formulas is high for example in the finance industry, where millions of products have to be priced using such formulas.

An executable graph is such graph that has a function in each of its nodes. An execution of a graph means the evaluation of all of its functions. The edges of an executable graph are directed. An edge defines that a result of a function is used by another function as an input. As a node may represent any mathematical function, any kind of mathematical formula can be described with an executable graph, if such formula can be described by applying mathematical functions in some order.

My task was to create a scheduling plan for executable graphs. The graphs are executed in a multiprocessor environment. Therefore, the scheduling plan has to contain both the order of the functions and a mapping that defines on which processor a function shall be executed.

During my work I designed the format of the scheduling plan to match the requirements and I implemented several scheduling algorithms based on the list scheduling technique. I also applied the genetic algorithm to my task. I designed and configured the implementation of the algorithm to provide as good scheduling plans as possible.

An execution of an executable graph can be made even faster if we can reuse the partial results from the previous execution. I designed and implemented an algorithm that determines the functions that has to be re-evaluated in order to obtain the new results. With the result of this algorithm, we only need to execute only part of a graph, which can potentially fasten up the execution.


Please sign in to download the files of this thesis.