Object Oriented Parallelisation of Graph Algorithms using Parallel Iterator

Akeila, L., Sinnen, O. and Humadi, W.

Multi-core machines are becoming widely used which, as a consequence, forces parallel computing to move from research labs to being adopted everywhere. Due to the fact that developing parallel code is a significantly complex process, the main focus of today's research is to design tools which facilitate the process of parallelising code. The Parallel Iterator (PI) is a tool which was developed to automate the process of parallelising loops in OO applications. Graph algorithms can be represented using objects and hence they are excellent use cases for the PI. This paper discusses using the PI to parallelising graph algorithms such as breadth-first search (BFS), depth-first search (DFS) and minimum spanning tree (MST). Using the PI to parallelise such graph algorithms required adding some adaptations to the current concept of the PI to handle certain graph algorithms. The PI facilitates the process of parallelising graph algorithms in a way which keeps the parallel code readable and maintainable while exhibiting speedup. Java was used as the implementation language since it is one of the most commonly used object oriented languages. The parallelised graph algorithms were tested on different graphs and trees with different densities, granularity and structures. The experimental results show that the parallelised graph algorithms exhibit good speedups.

Cite as: Akeila, L., Sinnen, O. and Humadi, W. (2010). Object Oriented Parallelisation of Graph Algorithms using Parallel Iterator. In Proc. Eighth Australasian Symposium on Parallel and Distributed Computing (AusPDC 2010) Brisbane, Australia. CRPIT, 107. Chen, J. and Ranjan, R. Eds., ACS. 41-50

(from crpit.com) (local if available)