Optimization of model partitioning algorithms

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

Nowadays, it is a common issue in model transformation applications that the models are too huge to handle on a single computer. Both the calculation and the storage capacity can be the bottleneck in these cases. Therefore, it seems to be a good idea to process the models in a distributed way. However, in order to use distributed architecture efficiently, the models must be partitioned among the computers and optimize the number of messages between the computers. This can be achieved by minimizing the connections between the partitions.

Usually, models can be well described by graphs. Entities can be represented by nodes, while relations can be represented by edges. Thus, the problem can be traced back to graph partitioning, where the goal is to minimize the edges between partitions.

During my work, I have explored related articles then I have analyzed my task in detail. After that, I have designed the steps of the algorithm and elaborated the possible usage of apriori information. I have created a framework, which uses the different implementations of algorithm variants. Moreover, I have also added an improved solution that can use apriori information on models. %I have used this framework to test my algorithms, debug and improve them. I have generated several graphs and tested the variants of the algorithm.%by analyzing the execution results, I have gained valuable experiences.

In my thesis, I present existing graph partitioning algorithms and give a detailed specification of the task. After that, I introduce the steps of the algorithm and the different implementations of the variants, while I show the improved solution that can use apriori information on models. I present the method of graph generating and the analysis of test results. Finally, I summarize the experiences and give a few directions for future work.

Downloads

Please sign in to download the files of this thesis.