Lab 6 - Parallelizing techniques (2 - parallel explore)

Due: week 11

Goal

The goal of this lab is to implement a simple but non-trivial parallel algorithm.

Requirement

Solve the problem below:

Given a directed graph, find a Hamiltonean cycle, if one exists. Use a specified number of threads to parallelize the search. Important The search should start from a fixed vertex (no need to take each vertex as the starting point), however, the splitting of the work between threads should happen at several levels, for all possible choices among the neighbors of each current vertex.

For example, if you have 8 threads and the first vertex has an out-degree of 3, two of the branches will have 3 threads allocated each, and the remaining branch will have 2 threads. Then, if on the first branch the neighbor of the start vertex has a 4 out-neighbors distinct from the start vertex, then two of them will be explored by one thread, and the last thread will explore the other 2 neighbors; further down, there will be non-parallel search.

Create then a second implementation in Java using ForkJoinPool and RecursiveTask.

The documentation will describe:

• the algorithms,
• the synchronization used in the parallelized variants,
• the performance measurements