Atrosh
February 7th, 2011, 08:59 PM
Hello everyone,
I am fairly new to multithreaded programming, and Pthreads, in C++.
I am currently writing a parallelized N-Queens solver using Pthreads (http://en.wikipedia.org/wiki/Eight_queens_puzzle), and I've run into some strange problems which I cannot seem to solve.
Problem description:
The program compiles fine; it should create N/2 threads to find all solutions.. However, it only seems to start up 1 or 2 threads most of the time when inputting N=14 for instance (so it should create 7 threads), and then the program crashes, with no error information. Sometimes however it will create all the threads and compute and return the result as expected... Code for the program (lines of interest marked in blue, also please note the line written in red) :
#include <iostream> //
#include <iomanip> // for setw
#include <stdlib.h> // for abs
#include <time.h>
#include <pthread.h>
#ifdef _MSC_VER
# pragma comment(lib, "pthreadVC2.lib")
#endif
#ifndef _REENTRANT
#define _REENTRANT
#endif
#define DEFAULTSIZE 8
#define MAXSIZE 18
#define MAXWORKERS 9
typedef int index;
using namespace std;
class nQueens {
//Private:
pthread_mutex_t barrier; /* mutex lock for the barrier */
pthread_mutex_t cs; /* mutex lock for the critical section*/
pthread_cond_t go; /* condition variable for leaving */
int numWorkers;
int numArrived; /* number who have arrived */
bool firstTime;
bool shouldMultiply;
bool odd;
int n; //dimension of board
int numSolutions[MAXWORKERS];
int numSteps[MAXWORKERS];
// This is the static class function that serves as a C style function pointer
// for the pthread_create call
void static *start_thread(void *threadarg)
{
void* obj;
bool multiply;
int taskid;
struct thread_data *my_data;
my_data = (struct thread_data *) threadarg;
taskid = my_data->thread_id;
multiply = my_data->shouldMultiply;
obj = my_data->obj;
// All we do here is call the actual method which we want the threads to work with.
// In C, this is the method we would ordinarily have passed to the pthread create,
// without the workaround
reinterpret_cast<nQueens *>(my_data->obj)->run(my_data->thread_id,my_data->shouldMultiply);
return NULL;
}
public:
//This struct contains the arguments we want to pass to the running thread.
struct thread_data{
int thread_id;
bool shouldMultiply;
void *obj; //This is only required for the reinterpret_cast to work.
};
nQueens(int n, int workers) {
this->n = n;
numWorkers = workers;
}
void nQueens::start(){
//pthread initialization
pthread_attr_t attr;
pthread_t workerid[MAXWORKERS];
/* set global thread attributes */
pthread_attr_init(&attr);
pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM);
/* initialize mutex and condition variable */
pthread_mutex_init(&barrier, NULL);
pthread_mutex_init(&cs, NULL);
pthread_cond_init(&go, NULL);
//end pthread initialization
struct thread_data thread_data_array[MAXWORKERS]; //create an array of different thread_data structs
// to be passed to each of the workers.
firstTime = true;
numArrived = 0;
shouldMultiply = true;
odd = (n%2 == 1);
/*
First, calculate how many, and which rows will be assigned for each worker.
Then, create the workers and initialize them to start working on their respective
rows immediately.
*/
int jobs = odd ? n/2 +1 : n/2; // Number of rows to compute
// TODO at the moment, the number of jobs cannot be greater than the maximum available amount
// of workers; therefore, each worker will be assigned 1 row to compute.
numWorkers = jobs;
for (int i = 0; i < jobs; ++i){
//Assign arguments for threads:
thread_data_array[i].thread_id = i;
if (odd){
if (i+1 == jobs) // if this is the last worker
thread_data_array[i].shouldMultiply = false; // it shouldn't multiply, since the mid row has unique solutions
else
thread_data_array[i].shouldMultiply = true;
}
thread_data_array[i].obj = this;
}
for (int i = 0; i<jobs; ++i){
//Now create the workers.
printf("\n Creating worker %d ...\n",i);
pthread_create(&workerid[i], &attr, &nQueens::start_thread, (void *)&thread_data_array[i]);
}
pthread_exit(NULL);
}
void nQueens::Barrier(int id, int time) {
pthread_mutex_lock(&barrier);
numArrived++;
printf("\n %d reached barrier: %dst/nd/rd time \n", id, time);
if (numArrived == numWorkers) {
numArrived = 0;
pthread_cond_broadcast(&go);
}
else{
pthread_cond_wait(&go, &barrier);
}
pthread_mutex_unlock(&barrier);
}
void nQueens::finish() {
//display stats
cout << "Number of solutions for " << this->n << " queens: " << numSolutions << endl;
}
//The worker thread " run() "
void nQueens::run(int taskid, bool multiply) {
printf("F");
//taskid is equivalent to which row this worker should put its first queen on,
// so we first place a queen on row taskid, and then run the queen method to
// calculate all the solutions from that starting point.
//printf("worker %d (pthread id %d) has started\n", taskid, pthread_self());
index* col; // col[x]=y means queen at row x, column y
col = new int[n]; //array with coordinates of queens.
numSolutions[taskid] = 0;
numSteps[taskid] = 0;
//Place the first queen:
col[0] = taskid;
queens(1, col, &numSolutions[taskid]); // Start the computation from the next row,
if (multiply)
numSolutions[taskid] *= 2;
Barrier(taskid, 1);
if (taskid==0){
int total = 0;
for (int i=0; i<numWorkers; ++i){
total += numSolutions[i];
}
cout << "Number of solutions for board size " << n << ": " << total << endl;
}
delete [] col;
}
//main routine to traverse nodes of state space tree
void nQueens::queens(index i, index* col, int* solutions) {
// Continue only if columns 0,...,i-1 are promising.
if (promising(i-1, col)) {
if (i==n){ // have a complete solution
++ *solutions;
}
else {
for (index j=0; j<n; ++j) { // place queen in
col[i] = j; // row i, column j
//++numSteps;
queens(i+1, col, solutions); // and continue to next row
}
} //else
} //if-promising
}
//check if a node is promising
bool nQueens::promising(index i, index* col) {
// Check if queen in row k threatens queen in row i
for (index k=0; k<i; k++)
if (col[i] == col[k] || abs(col[i]-col[k]) == i-k)
return false; //does threaten, so not promising
return true;
}
void nQueens::printResults(time_t* pt1, time_t* pt2)
{
double secs;
int hours , mins, intsecs;
//printf("End: \t%s", ctime(pt2));
secs = difftime(*pt2, *pt1);
intsecs = (int)secs;
printf("Calculations took %d second%s.\n", intsecs, (intsecs == 1 ? "" : "s"));
printf("Steps: %d",numSteps);
/* Print hours, minutes, seconds */
hours = intsecs/3600;
intsecs -= hours * 3600;
mins = intsecs/60;
intsecs -= mins * 60;
if (hours > 0 || mins > 0)
{
printf("Equals ");
if (hours > 0)
{
printf("%d hour%s, ", hours, (hours == 1) ? "" : "s");
}
if (mins > 0)
{
printf("%d minute%s and ", mins, (mins == 1) ? "" : "s");
}
printf("%d second%s.\n", intsecs, (intsecs == 1 ? "" : "s"));
}
}
};
int main(int argc, char *argv[]) {
int n; // board size
int numworkers;
//time_t t1, t2;
n = (argc > 1)? atoi(argv[1]) : DEFAULTSIZE;
if (n > MAXSIZE) n = MAXSIZE;
numworkers = (n > MAXWORKERS) ? MAXWORKERS : n;
if (n>0) {
nQueens* nq = new nQueens(n, numworkers);
//time(&t1);
nq->start();
//time(&t2);
//nq->finish();
//nq->printResults(&t1, &t2);
delete nq;
}
return 0;
}
The 'printf("F")' (marked in red in the code) will only be output 1 or 2 times most of the time (i.e. the very first line of the worker method will not be executed most of the time), except for the occasions where all the threads will start up properly and finish. I guess there must be race conditions in the code somehow, but I just cannot seem to find it. I've tried everything; even when locking all other threads and only letting 1 thread at a time run will have the same exact error. It's as if the reinterpret_cast only wants to work sometimes, and sometimes it simply does not forward the call to run()...
Does anyone have ANY idea what could be going on here? I'm simply stuck and I cannot find the problem... Would be greatly appreciated. Thanks a lot...
Best regards,
Atra
I am fairly new to multithreaded programming, and Pthreads, in C++.
I am currently writing a parallelized N-Queens solver using Pthreads (http://en.wikipedia.org/wiki/Eight_queens_puzzle), and I've run into some strange problems which I cannot seem to solve.
Problem description:
The program compiles fine; it should create N/2 threads to find all solutions.. However, it only seems to start up 1 or 2 threads most of the time when inputting N=14 for instance (so it should create 7 threads), and then the program crashes, with no error information. Sometimes however it will create all the threads and compute and return the result as expected... Code for the program (lines of interest marked in blue, also please note the line written in red) :
#include <iostream> //
#include <iomanip> // for setw
#include <stdlib.h> // for abs
#include <time.h>
#include <pthread.h>
#ifdef _MSC_VER
# pragma comment(lib, "pthreadVC2.lib")
#endif
#ifndef _REENTRANT
#define _REENTRANT
#endif
#define DEFAULTSIZE 8
#define MAXSIZE 18
#define MAXWORKERS 9
typedef int index;
using namespace std;
class nQueens {
//Private:
pthread_mutex_t barrier; /* mutex lock for the barrier */
pthread_mutex_t cs; /* mutex lock for the critical section*/
pthread_cond_t go; /* condition variable for leaving */
int numWorkers;
int numArrived; /* number who have arrived */
bool firstTime;
bool shouldMultiply;
bool odd;
int n; //dimension of board
int numSolutions[MAXWORKERS];
int numSteps[MAXWORKERS];
// This is the static class function that serves as a C style function pointer
// for the pthread_create call
void static *start_thread(void *threadarg)
{
void* obj;
bool multiply;
int taskid;
struct thread_data *my_data;
my_data = (struct thread_data *) threadarg;
taskid = my_data->thread_id;
multiply = my_data->shouldMultiply;
obj = my_data->obj;
// All we do here is call the actual method which we want the threads to work with.
// In C, this is the method we would ordinarily have passed to the pthread create,
// without the workaround
reinterpret_cast<nQueens *>(my_data->obj)->run(my_data->thread_id,my_data->shouldMultiply);
return NULL;
}
public:
//This struct contains the arguments we want to pass to the running thread.
struct thread_data{
int thread_id;
bool shouldMultiply;
void *obj; //This is only required for the reinterpret_cast to work.
};
nQueens(int n, int workers) {
this->n = n;
numWorkers = workers;
}
void nQueens::start(){
//pthread initialization
pthread_attr_t attr;
pthread_t workerid[MAXWORKERS];
/* set global thread attributes */
pthread_attr_init(&attr);
pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM);
/* initialize mutex and condition variable */
pthread_mutex_init(&barrier, NULL);
pthread_mutex_init(&cs, NULL);
pthread_cond_init(&go, NULL);
//end pthread initialization
struct thread_data thread_data_array[MAXWORKERS]; //create an array of different thread_data structs
// to be passed to each of the workers.
firstTime = true;
numArrived = 0;
shouldMultiply = true;
odd = (n%2 == 1);
/*
First, calculate how many, and which rows will be assigned for each worker.
Then, create the workers and initialize them to start working on their respective
rows immediately.
*/
int jobs = odd ? n/2 +1 : n/2; // Number of rows to compute
// TODO at the moment, the number of jobs cannot be greater than the maximum available amount
// of workers; therefore, each worker will be assigned 1 row to compute.
numWorkers = jobs;
for (int i = 0; i < jobs; ++i){
//Assign arguments for threads:
thread_data_array[i].thread_id = i;
if (odd){
if (i+1 == jobs) // if this is the last worker
thread_data_array[i].shouldMultiply = false; // it shouldn't multiply, since the mid row has unique solutions
else
thread_data_array[i].shouldMultiply = true;
}
thread_data_array[i].obj = this;
}
for (int i = 0; i<jobs; ++i){
//Now create the workers.
printf("\n Creating worker %d ...\n",i);
pthread_create(&workerid[i], &attr, &nQueens::start_thread, (void *)&thread_data_array[i]);
}
pthread_exit(NULL);
}
void nQueens::Barrier(int id, int time) {
pthread_mutex_lock(&barrier);
numArrived++;
printf("\n %d reached barrier: %dst/nd/rd time \n", id, time);
if (numArrived == numWorkers) {
numArrived = 0;
pthread_cond_broadcast(&go);
}
else{
pthread_cond_wait(&go, &barrier);
}
pthread_mutex_unlock(&barrier);
}
void nQueens::finish() {
//display stats
cout << "Number of solutions for " << this->n << " queens: " << numSolutions << endl;
}
//The worker thread " run() "
void nQueens::run(int taskid, bool multiply) {
printf("F");
//taskid is equivalent to which row this worker should put its first queen on,
// so we first place a queen on row taskid, and then run the queen method to
// calculate all the solutions from that starting point.
//printf("worker %d (pthread id %d) has started\n", taskid, pthread_self());
index* col; // col[x]=y means queen at row x, column y
col = new int[n]; //array with coordinates of queens.
numSolutions[taskid] = 0;
numSteps[taskid] = 0;
//Place the first queen:
col[0] = taskid;
queens(1, col, &numSolutions[taskid]); // Start the computation from the next row,
if (multiply)
numSolutions[taskid] *= 2;
Barrier(taskid, 1);
if (taskid==0){
int total = 0;
for (int i=0; i<numWorkers; ++i){
total += numSolutions[i];
}
cout << "Number of solutions for board size " << n << ": " << total << endl;
}
delete [] col;
}
//main routine to traverse nodes of state space tree
void nQueens::queens(index i, index* col, int* solutions) {
// Continue only if columns 0,...,i-1 are promising.
if (promising(i-1, col)) {
if (i==n){ // have a complete solution
++ *solutions;
}
else {
for (index j=0; j<n; ++j) { // place queen in
col[i] = j; // row i, column j
//++numSteps;
queens(i+1, col, solutions); // and continue to next row
}
} //else
} //if-promising
}
//check if a node is promising
bool nQueens::promising(index i, index* col) {
// Check if queen in row k threatens queen in row i
for (index k=0; k<i; k++)
if (col[i] == col[k] || abs(col[i]-col[k]) == i-k)
return false; //does threaten, so not promising
return true;
}
void nQueens::printResults(time_t* pt1, time_t* pt2)
{
double secs;
int hours , mins, intsecs;
//printf("End: \t%s", ctime(pt2));
secs = difftime(*pt2, *pt1);
intsecs = (int)secs;
printf("Calculations took %d second%s.\n", intsecs, (intsecs == 1 ? "" : "s"));
printf("Steps: %d",numSteps);
/* Print hours, minutes, seconds */
hours = intsecs/3600;
intsecs -= hours * 3600;
mins = intsecs/60;
intsecs -= mins * 60;
if (hours > 0 || mins > 0)
{
printf("Equals ");
if (hours > 0)
{
printf("%d hour%s, ", hours, (hours == 1) ? "" : "s");
}
if (mins > 0)
{
printf("%d minute%s and ", mins, (mins == 1) ? "" : "s");
}
printf("%d second%s.\n", intsecs, (intsecs == 1 ? "" : "s"));
}
}
};
int main(int argc, char *argv[]) {
int n; // board size
int numworkers;
//time_t t1, t2;
n = (argc > 1)? atoi(argv[1]) : DEFAULTSIZE;
if (n > MAXSIZE) n = MAXSIZE;
numworkers = (n > MAXWORKERS) ? MAXWORKERS : n;
if (n>0) {
nQueens* nq = new nQueens(n, numworkers);
//time(&t1);
nq->start();
//time(&t2);
//nq->finish();
//nq->printResults(&t1, &t2);
delete nq;
}
return 0;
}
The 'printf("F")' (marked in red in the code) will only be output 1 or 2 times most of the time (i.e. the very first line of the worker method will not be executed most of the time), except for the occasions where all the threads will start up properly and finish. I guess there must be race conditions in the code somehow, but I just cannot seem to find it. I've tried everything; even when locking all other threads and only letting 1 thread at a time run will have the same exact error. It's as if the reinterpret_cast only wants to work sometimes, and sometimes it simply does not forward the call to run()...
Does anyone have ANY idea what could be going on here? I'm simply stuck and I cannot find the problem... Would be greatly appreciated. Thanks a lot...
Best regards,
Atra