c - 如何使用 Pthreads 并行化我的 n 皇后拼图？

Question

我有以下用于 n 皇后拼图的 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;

}

Answer 1

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

1. 在solve内部，您通过计算start和end来分割每个线程的工作，但是这不应该完成一次col > 0，因为在递归中你必须再次遍历所有行。

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

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

4. 如果NTHREADS > SIZE，您的start和end将始终为-1。

5. 作为良好实践，您应该始终检查 malloc (和 friend )是否不返回 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;

}