COMP429-529 - Parallel N-Queens Solver -  Assignment 1-Part 2 - Solved

PART II: Parallel N-Queens Solver
In the second part of this assignment, you are asked to parallelize a serial n-queens solver with OpenMP. Similar to Part I, you are provided with a serial n-queens solver code, which takes an n-queens problem as an input and finds all possible solutions from it. We are using a brute force search for searching for all possible solutions to the problem.

For a given nxn chessboard, the idea is to generate every possible move by trying each cell within a column i, such that 0 ≤ i < n, and then, testing to see whether queen placement in the cell satisfies the n-queens’ constraint (no chess queen in the board/matrix can kill each other). After finding a cell in column i that satisfies the constraints, the program moves to column i+1 to find another queen placement in that column. This process is repeated recursively until the last column n - 1.

A solution is printed after there is a queen in every column of the matrix with the n-queens’ constraint being satisfied. After finding a solution by placing the last queen in column n 1, the program backtracks to the previous column n-2 to try other cells in the column and moves forward again to find another placement of the last queen in column n - 1. This backtracking process is repeated so that when the program backtracks to a column i, all possible placements in columns j, s.t. i < j < n, have been found. By the time the backtracking process completes, all possible solutions for n-queens problem have been found.

1

Part-II-A Task Parallelism                                                                                                PART II: PARALLEL N-QUEENS SOLVER

Part-II-A Task Parallelism
In the first part, you are required to parallelize the n-queens solver with task parallelism. Similar to the serial version, the parallel version is expected to find all possible solutions to a given n-queens problem.

Part-II-B Task Parallelism with Cutoff
The first implementation results in too many tasks in the system which can easily degrade the performance. As a result, you may not experience any speedup or very disappointing speedup. In this part, you will implement an optimization to improve the performance of the parallel code by using a cutoff parameter to limit the number of parallel tasks in your code. To limit task generations, beyond certain depth in the call-path tree of the recursive function, switch to the serial execution and do not generate tasks. This depth is determined by the cutoff parameter you choose.

Part-II-C Task Parallelism with Early Termination
In this part, you will start working from the parallel code that you implemented in Part-II-A. You are going to modify the code so that it stops after finding one solution instead of all possible solutions. To make a fair performance comparison, you should also modify the serial version so that it also stops after finding one solution to n-queens.

Experimental Study
You must collect the performance data on the KUACC cluster. Plot your data as figures and include them in your report along with some description for your observations and explanations. Do the experiments with the input size of 14 and with thread count of 1, 2, 4, 8, 16, and 32 threads unless stated otherwise..

a) Scalability Test
Perform the same strong scaling experiment on your implementation.

•    For the parallel code from Part-II-A and B, you must compute the speedup with respect to the given serial n-queens solver.

•    For the parallel code from Part-II-C, you must compute the speedup with respect to a modified version of the given serial n-queens solver that also terminates after finding one valid solution.

b) Thread Binding Test
Perform the strong scaling experiment under 2 different thread mapping schemes; compact mapping and scatter mapping. If you run the previous test with compact mapping, then you just need to repeat the same test with scatter mapping. See lecture 8 for more explanations.

c) Tests on n-queens Problems of Different Sizes
For this test, you will report the running times of the parallel code from Part-II-A on nqueens problems of different sizes by using 32 threads. The sizes that you will test are 13, 14, and 15.