DidaWiki

This SPD project for the current academic year can be selected by any of the students. As explained during the course, the project development and test is still an individual work.

Starting from the description of the project and from the fragments of code provided, a parallel application has to be developed and run and its results and performance must be analyzed.

• The parallelization has to exploit either MPI, TBB, or OpenCL.
• The student is required to propose an analytical model of his program behavior (e.g. expected speedup and performance) and evaluate it against the actual application.
• The result of the project to be delivered is the program code and a short report about the program structure and its results. The report is discussed with the teacher. Note that the problem output will be checked when you deliver your project, before looking at the actual code and the report.

Additional Points: more parallelization strategies can usually be developed with the same framework. Comparing several solutions and studying their behavior will improve the project evaluation. Some effort in this direction is expected from all students, at least in order to motivate the choice of which solution will be implemented and run.

Bonus points: more than one framework can possibly be combined in the same project, or be compared with each other. This is not a requirement to pass the course or achieve full grades.

Exception: as reported in the course wiki main page, students can still propose their own project topic to be parallelized using one or more of the frameworks, according to previous year rules. Please read in the main page the rules that apply, this page does not deal with that case.

Design and implement a parallel application solving a variation of the N-Queen problem.

The N-queen problem requires you to place exactly N queen pieces on an N by N chessboard in such a way that none is attacking any other one. It is a specific set-cover problem, with both heuristic and combinatorial solutions, which has been studied already (see D.E. Knuth's paper for a quick start on set coverage problems) and previously used as a test case for parallel and distributed programming frameworks (see Denis Caromel et al.)

The sequential algorithm for generating solutions is provided as a starting point.

1) In our project we want to generate all ordinary solutions to the N-Queen problem given a specific value on N as a parameter, provided that N⇐24. Since we are interested in the combinatorial exploration of the solution space, a problem whose complexity is exponential, we have an obvious case for parallel solutions. No student is expected to reach or exceed the upper limit N=24 with a complete computation, but the parallel code should cope with all N values up to 24 and test results should show the gains and limits of the implemented parallelization.

2) When generating all simple solutions, we want to record them in a data structure so that they can be reused. In this phase we also want to check when a newfound solution is a derivation of a previous one (either by a 180 degrees reflection along an axis and/or by a 90 degrees rotation), and record how many derivative solutions we find in each group. Note that for moderately high values of N the data structure may become large enough to need its own parallel implementation (e.g. splitting across resources) .

3) The set of unique solutions generated must also be scrutinized for solutions of the amazon problem, that is, placing N pieces on an N by N chessboard where each one of the pieces can move like an amazon. An amazon is a non standard chesspiece that can move both as a queen and as a knight (see http://en.wikipedia.org/wiki/Amazon_%28chess%29). This means that: (a) by converse, each solution of the N amazon problems must be a solution of the N-queen problem; (b) each N-Queen unique solution where at least two queens are less than 2 steps away along rows and columns is not a solution of the amazon problem.

Donald E. Knuth, Dancing links (2000) downloadable from http://arxiv.org/abs/cs/0011047 and from http://www-cs-faculty.stanford.edu/~uno/preprints.html

http://en.wikipedia.org/wiki/Queen_%28chess%29

http://en.wikipedia.org/wiki/Eight_queens_puzzle

Other Bibliography on the problem:

Rodolfo Toledo, Eric Tanter, José Piquer, Denis Caromel, Mario Leyton, “Using Reflexd For A Grid Solution To The N-Queens Problem: A Case Study”, in Achievements in European Research on Grid Systems, Springer, 2008. dowmloadable from http://pleiad.dcc.uchile.cl/papers/2006/toledoAl-cgiw2006.pdf

Wirth, Niklaus (1976), Algorithms + Data Structures = Programs, Prentice-Hall, ISBN 0-13-022418-9

http://www.npluskqueens.info/background.html

• the value of N, 1<N⇐24.
• the degree of parallelism to use in a specific test.
• (possibly: other parameters specifying further the parallel for to use; this is of course implementation dependent, and is left to decide to the student)
• a switch to optionally print all solutions/unique solutions/amazon solutions found either to standard output or to a file (only one is required)

• the overall count of solutions found;
• the overall count of unique solutions found;
• the overall count of unique solutions which also solve the N-amazon problem

if required by the switch, all solutions found shall be output (either on the standard output or in a file), also including a counter stating for each unique solution how many times it was found. Please note that the problem output will be checked when you deliver your project.

The program can be represented as a three stage pipeline:

1. recursively explore the set of potential solution of the N-Queen problem, and extract all solutions.
2. store all solutions in a data structure, checking for derived solutions before storing each new one (and increment the related counter if that's the case)
3. analyze all unique solutions to check if they also solve the amazon problem (and count/store them)

Each stage can be parallelized, according to farm (anonymous, load balancing) or map paradigms (geometric distribution). This is true from the high-level viewpoint: the actual parallel implementation depends on the framework adopted and is required from the student. Besides, it is a student choice the specific tradeoff between simplicity and performance of the parallelization.

The students must choose the parallel patterns and implement them, possibly merging stages or exploding them into parallel skeletons implementing the function. The high-level analysis leading to those choices shall be reported in the report about the project.

Stage 1 is the most obvious candidate or parallelization as it contains a large amount of combinatorial exploration. In order to do that, a subdivision of the search space is required, so that several tasks are generated that can be computed in parallel. The available example code allows to generate several independent tasks (distinct values in the rows array for all rows already assigned). The amount of computation and of solutions found in the subtasks is not homogeneous, you may want to study the issue before choosing the parallelization type.

Stage 2 has to be based on some dictionary structure where you can store and retrieve board positions quickly, in order to check for each new board that it is present in the past output. It is up to the student choose a method and a data structure, as well as to code the simple functions that compute the reflection and rotations of a board. When designing the structure take into account the number of unique solutions that you are going to find for 8<N<20, for instance. That number is easily found on the WWW.

Stage 3 is easier to code, as it simply has to check that no two queens have both coordinates which differ by 1 or 2 (and one of those two cases must actually never happen!).

Available code

The example code for the N-queen problem is made available in C, to ease the porting to MPI, TBB or OpenCL kernels.