0

我有以下用于 n-queen 谜题的 Pthreads 代码。它编译成功，但我得到错误的答案。无论我输入什么值，我都会得到答案为零。我想我的代码中有某种逻辑错误。我猜这个问题发生在回溯/递归部分的某个地方。如果有人可以建议我一个解决方案，我会很高兴。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <pthread.h>
#include <assert.h>

int NTHREADS, SIZE; 
int *hist;
int count = 0;

int solve(int col, int tid)
{
    int start = tid * SIZE/NTHREADS;
    int end = (tid+1) * (SIZE/NTHREADS) - 1;
    int i, j;
    if (col == SIZE) 
    {
        count++;
    }

    #define attack(i, j) (hist[j] == i || abs(hist[j] - i) == col - j)
    for (i = start; i <= end; i++) {
        for (j = 0; j < col && !attack(i, j); j++);
        if (j < col) continue;

        hist[col] = i;
        solve(col + 1, tid);
    }

    return count;
}

void *worker(void *arg)
{
    int tid = (int)arg;
    solve(0, tid);
}

int main(int argc, char* argv[])
{
    pthread_t* threads;
    int rc, i;

    // checking whether user has provided the needed arguments
    if(argc != 3)
    {
        printf("Usage: %s <number_of_queens> <number_of_threads>\n", argv[0]);
        exit(1);
    }


    // passing the provided arguments to the SIZE and NTHREADS 
    // variable, initializing matrices, and allocating space 
    // for the threads
    SIZE = atoi(argv[1]);
    NTHREADS = atoi(argv[2]);
    threads = (pthread_t*)malloc(NTHREADS * sizeof(pthread_t));
    hist = (int*)malloc(SIZE * sizeof(int));

    // declaring the needed variables for calculating the running time
    struct timespec begin, end;
    double time_spent;

    // starting the run time
    clock_gettime(CLOCK_MONOTONIC, &begin);

    for(i = 0; i < NTHREADS; i++) {
        rc = pthread_create(&threads[i], NULL, worker, (void *)i);
        assert(rc == 0); // checking whether thread creation was successful
    }

    for(i = 0; i < NTHREADS; i++) {
        rc = pthread_join(threads[i], NULL);
        assert(rc == 0); // checking whether thread join was successful
    }

    // ending the run time
    clock_gettime(CLOCK_MONOTONIC, &end);

    // calculating time spent during the calculation and printing it
    time_spent = end.tv_sec - begin.tv_sec;
    time_spent += (end.tv_nsec - begin.tv_nsec) / 1000000000.0;
    printf("Elapsed time: %.2lf seconds.\n", time_spent);

    printf("\nNumber of solutions: %d\n", count);

    free(hist);
    return 0;

}
4

1 回答 1

0

好吧，有很多错误，但第一个确实导致全部为 0。请注意，如果只使用一个线程，您的程序可以正常工作。

  1. 在内部，您通过计算和solve拆分每个线程的工作，但是这不应该只做一次，因为在递归中您必须再次遍历所有行。startendcol > 0

  2. 您在线程之间共享变量hist，count而不在关键部分保护它们，例如使用信号量。在这种情况下，您可以通过为每个线程提供自己的这些变量版本并count在线程的连接中累积所有条目来避免信号量。共享count会引起问题的概率很低，但共享仍然是错误的，因为您不能假设这count++是一个原子的读-修改-写操作。共享hist只是算法上的错误。

  3. 如果NTHREADS不完全除SIZE，则最后的计算end不一定产生SIZE-1。

  4. 如果NTHREADS > SIZE你start和end将永远是-1。

  5. 作为一种好的做法，您应该始终检查malloc（和朋友）是否不返回NULL，因为这意味着您的内存不足。如果您检查命令行参数的正确性，这也是对您程序的用户的尊重。

如果你解决了这些错误，无论线程数如何，每次在常规大小的棋盘上运行它都会得到 92。祝你好运。

至于代码示例（下面问），我有点不情愿，但你去吧。就个人而言，我会进行更多更改，但我尽可能地贴近您的代码：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <pthread.h>
#include <assert.h>

int NTHREADS, SIZE;
int ** hist = NULL;
int * count = NULL;

static void oof(void)
{
    fprintf(stderr, "Out of memory.\n");
    exit(1);
}

void solve(int col, int tid)
{
    /* If NTHREADS does not divide SIZE, you
     * will not cover all rows.
     * Also make sure SIZE >= NTHREADS, otherwise start is always 0.
     */
    int start = (col > 0) ? 0 : tid * (SIZE/NTHREADS);
    int end = (col > 0 || tid == NTHREADS-1) ? SIZE-1 : (tid+1) * (SIZE/NTHREADS) - 1;
    int i, j;
    if (col == SIZE)
    {
        count[tid]++;
    }

    #define attack(i, j) (hist[tid][j] == i || abs(hist[tid][j] - i) == col - j)
    for (i = start; i <= end; i++) {
        for (j = 0; j < col && !attack(i, j); j++);
        if (j < col) continue;

        hist[tid][col] = i;
        solve(col + 1, tid);
    }
}

void *worker(void *arg)
{
    int tid = (int)arg;
    count[tid] = 0;
    solve(0, tid);
}


int main(int argc, char* argv[])
{
    pthread_t* threads;
    int rc, i, j, sum;

    // checking whether user has provided the needed arguments
    if(argc != 3)
    {
        printf("Usage: %s <number_of_queens> <number_of_threads>\n", argv[0]);
        exit(1);
    }


    // passing the provided arguments to the SIZE and NTHREADS 
    // variable, initializing matrices, and allocating space 
    // for the threads
    SIZE = atoi(argv[1]);
    NTHREADS = atoi(argv[2]);
    threads = (pthread_t*)malloc(NTHREADS * sizeof(pthread_t));
    hist = malloc(SIZE * sizeof(int*));
    count = malloc(SIZE * sizeof(int));
    if (hist == NULL || count == NULL) oof();
    for (i = 0; i < SIZE; i++)
    {
        hist[i] = malloc(SIZE * sizeof(int));
        if (hist[i] == NULL) oof();
        for (j = 0; j < SIZE; j++)
        {
            hist[i][j] = 0;
        }
    }

    // declaring the needed variables for calculating the running time
    struct timespec begin, end;
    double time_spent;

    // starting the run time
    clock_gettime(CLOCK_MONOTONIC, &begin);

    for(i = 0; i < NTHREADS; i++) {
        rc = pthread_create(&threads[i], NULL, worker, (void *)i);
        assert(rc == 0); // checking whether thread creation was successful
    }

    sum = 0;
    for(i = 0; i < NTHREADS; i++) {
        rc = pthread_join(threads[i], NULL);
        assert(rc == 0); // checking whether thread join was successful
        sum += count[i];
    }


    // ending the run time
    clock_gettime(CLOCK_MONOTONIC, &end);

    // calculating time spent during the calculation and printing it
    time_spent = end.tv_sec - begin.tv_sec;
    time_spent += (end.tv_nsec - begin.tv_nsec) / 1000000000.0;
    printf("Elapsed time: %.2lf seconds.\n", time_spent);

    printf("\nNumber of solutions: %d\n", sum);

    for (i = 0; i < SIZE; i++)
    {
        free(hist[i]);
    }
    free(hist); free(count);
    return 0;

}
于 2013-04-20T00:33:54.157 回答