This sample code guide will explore new and already existing parallel programming language extensions, directives, and libraries available in Intel® Parallel Composer to solve the well known N-Queens problem.

The basic idea is to present the parallelism alternatives provided by the Intel® Parallel Composer and show how to apply them to a given algorithm. The key questions we are addressing is 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 we are showing in this sample are:

• OpenMP* 3.0 directives
• New parallel extensions: __taskcomplete, __task, __finish, __par
• Intel® Threading Building Blocks (Intel® TBB) along with the “lambda” functions language extension

Each of these new methods provide the C++ developer 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 sample code guide 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 guide 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.

The N-Queens Sample

The N-Queens samples are a collection of Microsoft Visual Studio* 2008 project, solution, and C and C++ source files. The algorithm can be tackled by different approaches; for example, one 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.

If you are not familiar with the N-Queens problem, you can easily find information on the history of the problem, and other possible methods for solving it, on the worldwide web.

Note: The N-Queens problem was first published in 1848 in a German chess magazine by Max Bezzel. The correct answer for the problem was found in 1850 by Dr. Franz Nauck. The first solution for the general N-Queens problem was published in 1969.

Note: Linux users can drop me a line for a Linux version of the N-Queens problem.

Attached to this article is the full tutorial text along with a VS08 solution file.

Have fun

-- Mario Deilmann

Comments (1)

September 2, 2009 10:05 AM PDT rmedel Total Points: 90 Status Points: 40 Green Belt

It would be good to have the material (from the PDF doc) in presentation format, so we could give talks using this example.

Trackbacks (0)

Leave a comment