In this article, we explore new and already existing parallel programming language extensions, directives, and libraries available in Intel Parallel Composer. The basic idea is to present the parallelism alternatives provided by Parallel Composer and show how to apply them to a given algorithm. The key questions we address involve how much coding is necessary to parallelize a given serial application and which mechanism are provided to benefit of threading with higher level constructs?
These new parallel methods are:
- OpenMP 3.0 directives
- New parallel extensions:
- Intel Threading Building Blocks (TBB) along with the lambda functions language extension
Each of these new methods provide C++ developers with a new range of scalability, performance, and usability for developing parallel applications not previously available in Intel C++ compiler products. To illustrate the use and performance of these new features, this article demonstrates how to use each method to implement parallel solutions to the N-Queens problem, which is a well-known programming problem that has definite solutions. This article describes using each of these parallel techniques, shows the code for each implementation, and compares and contrasts the utility and performance of each implementation. All code blocks and examples shown in this guide are taken from the actual code samples included with the Intel Parallel Composer.
1.1 N-Queens Samples
Included with this article are a collection of Microsoft Visual Studio project, solution, and C and C++ source files. The algorithm can be tackled by different approaches; for example, you can choose to optimize for speed or memory or both. Therefore, there are several different samples available. The samples illustrate different approaches and algorithms to solve the N-Queens problem
1.2 The Problem
The ultimate goal of the N-Queens problem is to find the total number of distinct solutions to place a given number of chess queens on a quadratic chess board with a specific number of squares on one side of a board (N) in a way that no two queens would be able to attack each other.
Two queens can attack each others when they are placed on the same horizontal row, vertical column or in one of (2*(2*n - 1)) possible diagonals. For example, on an 8x8 board, there are 92 distinct solutions. The difference between a unique and distinct solution is that distinct solutions allow for symmetrical operations, like rotations and reflections of the board, to be counted as one; so an 8x8 board has 12 unique solutions. Another interesting fact is that the complexity of the N-Queens problem increases exponentially. The world record at the moment is held for the solution on a 25x25 board. It was solved on a heterogeneous cluster around the world similar to the more popular Seti@home project and the cumulated computing time was over 50 years!
The number of solutions is: 2.207.893.435.808.352 Start date: October 8th 2004 End time: June 11th 2005 Computation duration time = 4444h 54m 52s 854 i.e. 185 days 4 hours 54 minutes 52 seconds 854
The results are from (http://proactive.inria.fr/index.php?page=nqueens25).
1.2.1 Problem Analysis
The most common approach is to use the brute-force approach, which is to simply test each position for each board size. Unfortunately, trying a brute-force algorithm by testing if every position on the board is valid will inevitably lead to a huge number of positions to validate (n2)!/((n2)-n)!; even for a 4x4 board the possible number of positions is 16!/12! = 43680.
Applying a heuristic approach by only allowing one queen per row reduces the problem size to a vector of n elements, where each element holds the position in the row and the number of possible solutions reduces to nn. This approach yields 256 positions a 4x4 board. You can reduce the number further by allowing for only one queen per column, which will result in a tuple of queens per column Q1...Qn) which reduces the number of solutions to n!: only 24 for our 4x4 board. You can review the problem of the 4x4 board to illustrate one possible solution. We start by placing the first queen in row 1, column 1, as in Figure 1.
Since there is no chance to place another queen on column 1, the next queen must be placed in row 2, with the first possible placement being row 2, column 3 (Figure 2).
Unfortunately, there is no way to place a queen on the third row so this placement is not a viable solution; therefore, you must try another column on row 2, in this case column 4, as in Figure 3.
The new position seems valid; the next placement might be row 3, column 2 (Figure 4).
Unfortunately, the new placement leaves no options for row 4. Starting over, one can place a queen at row 1, column 2 (Figure 5). Continuing the original strategy, place the next queen at row 2, column 4.
The new placement allows one to add a new queen in row 3, column 1 (Figure 6).
Finally, there is a possible solution because the new layout allows for another queen to be placed in row 4, column 3 (Figure 7).
There might be other solutions. Starting in row 1, column 3 and stepping through the placements again, one finds another solution that mirrors the first (Figure 8).
A check of other possible solutions should convince you that none exist, so there are two solutions on the 4x4 board. These are the only distinct solutions; how many unique solutions exist?
To answer that question, one must look for symmetry. If you section the board using dotted lines, and create mirror images reflected across the lines you might see another solution (Figure 9). There is only one unique solution as we can get the other one by reflection.
We could present the solution as a vector (v) of (n) values (for the rows). Every value contains the number of the column where the queen can be placed. For the original 16 squares (4x4) we have found: v = [2 4 1 3] and [3 1 4 2]
To summarize, the most obvious approach to solving the problems was to add pieces recursively to the board trying to find all possible solutions. It is relatively easy to determine that we can add one queen in each column and look for solutions found based on the original placement of the first queen. The different solutions are independent from the solutions from the queens in the other columns.
This is an example of a tree search, because the algorithm iterates down to the bottom of the search tree once a queen is placed on the board. The search tree of the above example looks like this:
To code our approach, you must define conditions when queen (a) can be attacked by queen (b). First, you must deal with the cases where queens are in the same row or column, v[a] = v[b] here [4 x x 4].
Second, you must define the condition where the queen can be attacked diagonally. The difference of absolute row count and column count is equal, for a < b. Both queens can attack each other if they stay on the same diagonal. There are two possibilities: b-a = v[b] - v[a]
or b-a = v[a] - v[b]
We can combine both conditions to b-a = absolute value | v[a] -v[b] |. The resulting algorithm might look like the following in pseudocode:
Read board size: n Set row to 1 Set v to 0 while ( column > 0) do [ Find out a safe place in column where to safely place a queen if there is a location put v[row] = location if [row = n] [Write solution vector v[1 ... n]] end else if [row < n] go forward one line : row = row + 1 set v[row] to 0 end else do one column back : column = column - 1 end end ]
Backtracking improves upon a brute-force search by building solutions step-by-step, and being able to discard a partial solution along with all solutions that would be built from it.
This works for the eight-queen problem; for example, if you start from an empty board and adds queens one-by-one, the moment you add a queen there is a conflict, and you can see that adding more queens will not remove the conflict; therefore, all solutions derived from that queen can be discarded without testing them.
Tools Recent Articles
This month's Dr. Dobb's Journal
Most Recent Premium Content
- November - Mobile Development
- August - Web Development
- May - Testing
- February - Languages
- Open Source
- Windows and .NET programming
- The Design of Messaging Middleware and 10 Tips from Tech Writers
- Parallel Array Operations in Java 8 and Android on x86: Java Native Interface and the Android Native Development Kit
- January - Mobile Development
- February - Parallel Programming
- March - Windows Programming
- April - Programming Languages
- May - Web Development
- June - Database Development
- July - Testing
- August - Debugging and Defect Management
- September - Version Control
- October - DevOps
- November- Really Big Data
- December - Design
- January - C & C++
- February - Parallel Programming
- March - Microsoft Technologies
- April - Mobile Development
- May - Database Programming
- June - Web Development
- July - Security
- August - ALM & Development Tools
- September - Cloud & Web Development
- October - JVM Languages
- November - Testing
- December - DevOps
Dr. Dobb's Journal
Dr. Dobb's Tech Digest