OpenMP递归任务创建开销问题及回溯算法并行化故障排查

云上老周

2026-8-21

问题描述

我的并行化回溯数独求解程序在设置超过4个线程时开销显著，线程数大于4时运行时间反而变长。程序找到解后会终止运行。我原本的优化思路是：仅当每个节点至少有2个子节点时才创建任务，且创建的任务数不超过可用线程数；但使用条件if (followingNodes > 1 && depth < maxDepth)时，求解大规模数独完全得不到结果。

相关代码

double start_time;
int threadNum;

struct grid copyGrid(struct grid grid)
{
    size_t size = grid.size * grid.size * sizeof(int);
    int* cpy_sudoku = malloc(size);
    int* src_sudoku = grid.sudoku;
    memcpy(cpy_sudoku, src_sudoku, size);
    struct grid cpyGrid;
    cpyGrid.sudoku = cpy_sudoku;
    cpyGrid.size = grid.size;
    return cpyGrid;
}

int isSafe(struct grid g, int row, int col, int num)
{
    for (int x = 0; x <= g.size - 1; x++)
        if (g.sudoku[row * g.size + x] == num)
            return 0;

    for (int x = 0; x <= g.size - 1; x++)
        if (g.sudoku[x * g.size + col] == num)
            return 0;

    int startRow = row - row % (int)sqrt(g.size),
        startCol = col - col % (int)sqrt(g.size);

    for (int i = 0; i < (int)sqrt(g.size); i++)
        for (int j = 0; j < (int)sqrt(g.size); j++)
            if (g.sudoku[(startRow * g.size + i) + (j * g.size + startCol)] == num)
                return 0;

    return 1;
}

int solveSudoku(struct grid* grid, int row, int col, int depth, int maxDepth)
{
    int index = row * grid->size + col;

    if (row == grid->size - 1 && col == grid->size)
        return 1;

    if (col == grid->size)
    {
        row++;
        col = 0;
    }

    if (grid->sudoku[index] > 0)
        return solveSudoku(grid, row, col + 1, depth, maxDepth);

    num_queue* numsQueue = NULL;
    int followingNodes = 0;
    for (int num = 1; num <= grid->size; num++)
    {
        if (isSafe(*grid, row, col, num) == 1)
        {
            intEnqueue(&numsQueue, num);
            followingNodes++;
        }
    }
    int num;
    while ((num = intDequeue(&numsQueue, 1)) > 0)
    {
        grid->sudoku[index] = num;

        if (followingNodes > 1 && depth < maxDepth)
        {
            struct grid copiedGrid;
            #pragma omp critical
            copiedGrid = copyGrid(*grid);
            #pragma omp task firstprivate(copiedGrid,row,col,depth,maxDepth) shared(start_time)
            {
                if (solveSudoku(&copiedGrid, row, col + 1, depth + 1, maxDepth) == 1)
                {
                    double solutionTime = omp_get_wtime() - start_time;
                    printf("%f\n", solutionTime);
                    exit(0);
                }
                free(copiedGrid.sudoku);
            }

        }
        else if (solveSudoku(grid, row, col + 1, depth, maxDepth) == 1) // Compute serial
            return 1;
        followingNodes--;
    }
    grid->sudoku[index] = 0;
    return 0;
}

int main(int argc, char** argv) {


    threadNum = atoi(argv[1]);
    char* file = argv[2];
    double startInit_time = omp_get_wtime();
    struct grid rootGrid = readGridFromFile(file);

    if (threadNum == 0)
        return 0;
    start_time = omp_get_wtime();
        #pragma omp parallel default(none) shared(rootGrid, threadNum) num_threads(threadNum)
        {
            #pragma omp single nowait
                solveSudoku(&rootGrid, 0, 0, 0, threadNum);
        }
    return 0;
}

问题分析与修复方案

核心问题点

状态污染导致解丢失
当前代码在创建并行任务前直接修改原网格的grid->sudoku[index] = num，后续并行任务复制的是已修改的网格，剩余候选数的串行分支又会覆盖该值继续执行。若并行任务未找到解，串行分支处理时原网格状态已被篡改，导致递归路径完全错误，大规模数独的解自然无法被找到。
临界区引发性能瓶颈
copyGrid被#pragma omp critical包裹，所有线程创建任务时都要排队复制网格，线程数越多竞争越激烈，超过4线程后调度开销远超并行收益，直接导致运行时间变长。实际上copyGrid是无副作用的纯函数，完全不需要临界区保护。
终止逻辑不规范
用exit(0)直接终止进程会导致其他线程未完成任务的资源泄漏，OMP运行时的清理逻辑也无法正常执行，存在隐性风险。

修复步骤

隔离并行任务与原网格状态
将grid->sudoku[index] = num移到并行任务内部和串行分支内部，确保原网格在任务创建时保持初始状态：

volatile int found = 0;

int solveSudoku(struct grid* grid, int row, int col, int depth, int maxDepth)
{
    if (found) return 0;
    // 原有逻辑...
    while ((num = intDequeue(&numsQueue, 1)) > 0)
    {
        if (followingNodes > 1 && depth < maxDepth)
        {
            struct grid copiedGrid = copyGrid(*grid);
            // 在副本上设置数值
            copiedGrid.sudoku[row * copiedGrid.size + col] = num;
            #pragma omp task firstprivate(copiedGrid,row,col,depth,maxDepth) shared(start_time, found)
            {
                if (!found && solveSudoku(&copiedGrid, row, col + 1, depth + 1, maxDepth) == 1)
                {
                    #pragma omp atomic write
                    found = 1;
                    double solutionTime = omp_get_wtime() - start_time;
                    printf("%f\n", solutionTime);
                }
                free(copiedGrid.sudoku);
            }
        }
        else
        {
            // 串行分支修改原网格
            grid->sudoku[index] = num;
            if (solveSudoku(grid, row, col + 1, depth, maxDepth) == 1)
            {
                #pragma omp atomic write
                found = 1;
                return 1;
            }
            grid->sudoku[index] = 0;
        }
        followingNodes--;
    }
    // 原有逻辑...
}

移除不必要的临界区
删除包裹copyGrid的#pragma omp critical代码，允许多线程同时复制网格，消除竞争瓶颈。
优化任务创建条件
不要将maxDepth设为线程数，改为固定小值（如2或3）——数独解空间在浅深度分支最多，深分支任务创建只会增加调度开销。同时可限制总任务数不超过线程数的2倍，避免过度调度。
改用安全的终止机制
定义全局共享的volatile int found = 0，所有递归函数入口先检查found，若已找到解直接返回；找到解时通过原子操作设置found = 1，主线程在并行区域后等待所有任务完成再退出，避免资源泄漏。

内容的提问来源于stack exchange，提问作者izael11

OpenMP递归任务创建开销问题及回溯算法并行化故障排查

核心问题点 #

修复步骤 #

核心问题点

修复步骤