Evaluating parallel graph-traversing algorithms on the .NET platform

OData support
Nagy Ákos
Department of Automation and Applied Informatics

Processors that are capable of parallel execution have become mainstream. Parallel algorithms and software that uses these algorithms is required to make full of this capability. Efficient parallel solution can improve performance compared to serial solutions.

The .NET framework offers a great number of structures and solutions to allow for parallelization, yet there are no libraries that would provide efficient parallelized serialization of object-graphs. A software library providing efficient parallel serialization of generic object-graphs would allow developers to make better use of the common parallel CPU architecture, and as a result increase performance during serialization and deserialization. This work lays the foundations for such a library.

This document presents parallel serialization algorithms that I designed and implemented. It also presents their inner workings and their performance characteristics. Advantageous solutions and structures from the .NET framework that the presented algorithms use are also presented.

Of course, every serialization problem is different as object-graphs vary greatly in their nature. This led to the definition of an object-graph type that was used for the measurements. The possibilities of parallel serialization was investigated with this object-graph type.

Compared to the serial algorithm chosen as the reference, my best performing parallel implementation running on quad-core processor achieved a 2.7-fold increase in serialization speed in the best case. The algorithms and the results presented here demonstrate that performance improvements can be achieved through the use of parallelized serialization in the case of larger object-graphs.


Please sign in to download the files of this thesis.