Parallel Computation Laboratory

Exercise 3: N Queens

Write parallel implementations of the backtracking algorithm for solving the problem of placing N queens on a board of size N such that no queen can beat another. Use the mechanisms of

1. Unix processes, signals, and pipes (no shared memory), and
2. the Message Passing Interface (MPI)

for implementing a procedure

nqueens(N, w, file)

that computes all solutions and, if w is true, writes them to file.

Run the programs with input sizes N = 2ⁱ, 2ⁱ⁺¹, ..., 2^i+k and w = true, false such that the corresponding program runs take between 1 second and at least one minute and use 1, 2, 4, 6, 8, 16 processors (as many as available).

1. Use for time measurements wall clock times (return value of times(), see the man pages). The timings must start before nqueen is called and stop after nqueens returns.
2. The result of this exercise is a paper containing the
   1. Documented source code,
   2. Output for one test run of each program (just one page, truncated),
   3. Tables with absolute runtimes,
   4. Runtime diagrams,
   5. Speedup diagrams,
   6. Efficiency diagrams,
   7. Your analysis of the results, your experiences and conclusions.
3. 1 extra point for each the fastest Unix program and for the fastest MPI program that solves the largest problem (w=true) with not more than 8 processors in not more than one minute.

Deadline and Presentation: June 16.