MPI并行回溯数独求解：大尺寸数独网格计算丢失问题排查

我基于MPI实现了并行回溯算法求解数独，但遇到了网格计算丢失的问题：

• 9x9数独基本能正常得到解
• 16x16大尺寸数独几乎无法得到解，且程序返回极快
• 推测是未计算所有缓存网格或缓存未生效——注释掉solveSudoku里的continue语句，或者禁用缓存时，总能得到正确解

我的设计思路：

• 由管理进程（进程0）在运行时收集其他计算进程生成的数独网格队列，所有网格均源自原始数独
• 计算进程在本地无任务时向管理进程请求更多网格；完成当前分支计算后，从管理进程获取缓存网格继续求解
• solveSudoku函数实现回溯算法，同时负责缓存数独的分支节点

我曾怀疑大量MPI_Send调用导致消息丢失，但改用同步的MPI_Ssend后问题依旧。

核心代码：solveSudoku函数 #

int solveSudoku(struct grid* grid, int row, int col, grids_queue** gridQueue, int* gridCount, int cacheGrids)
{
    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, gridQueue, gridCount, cacheGrids);

    int multiplePaths = 0;
    // 第一个循环：检查是否有多个可选值，尝试将其中一个缓存到管理进程
    if (cacheGrids == 1) 
    {
        int count = 0;
        for (int num = 1; num <= grid->size; num++)
        {
            if (isSafe(*grid, row, col, num) == 1)
            {
                count++;
                if (count > 1) 
                {
                    multiplePaths = 1;
                    break;
                }
            }
        }
    }
    int cachedGrid = 0;
    for (int num = 1; num <= grid->size; num++)
    {
        if (isSafe(*grid, row, col, num) == 1)
        {
            grid->sudoku[index] = num;

            // 缓存网格
            if (multiplePaths == 1 && cachedGrid == 0)
            {
                if (attemptGridCache(*grid) == 1) 
                {
                    // 跳过当前节点
                    cachedGrid = 1;
                    continue;
                }
            }
            if (solveSudoku(grid, row, col + 1, NULL, gridCount, cacheGrids) == 1)
                return 1;

        }
        grid->sudoku[index] = 0;
    }
    // 无解，返回0
    return 0;
}

核心代码：MPI通信与主逻辑 #

#define MANAGER_RECV_GRIDS 11
#define COMPUT_RECV_GRIDS 12
#define COMPUT_STATUS 13
#define MANAGER_STATUS 14
#define SOLUTION_TIME 15

double solutionFindTime = 0;
double start_time;
int pid;
int gridWidth;
int gridSize;

int attemptGridCache(struct grid sudokuGrid) {
    // 发送计算进程状态
    int computeStatus = 1;
    MPI_Ssend(&computeStatus, 1, MPI_INT, 0, COMPUT_STATUS, MPI_COMM_WORLD);
    // 获取管理进程状态
    int managerStatus;
    MPI_Recv(&managerStatus, 1, MPI_INT, 0, MANAGER_STATUS, MPI_COMM_WORLD, MPI_STATUS_IGNORE);

    // 将网格发送到管理进程缓存
    if (managerStatus != GRIDS_FULL)
    {
        MPI_Send(sudokuGrid.sudoku, gridSize, MPI_INT, 0, MANAGER_RECV_GRIDS, MPI_COMM_WORLD);
        return 1;
    }
    return 0;
}
struct grid recvGrid(int srcpid, int tag)
{
    size_t size = gridSize * sizeof(int);
    int* recvGrid = malloc(size);
    MPI_Recv(recvGrid, gridSize, MPI_INT, srcpid, tag, MPI_COMM_WORLD, MPI_STATUS_IGNORE); 
    struct grid g;
    g.sudoku = recvGrid;
    g.size = gridWidth;
    return g;
}
void computeGrid(struct grid grid, int cacheGrids)
{
    if (solveSudoku(&grid, 0, 0, NULL, NULL, cacheGrids) == 1)
    {
        printf("<<<<<<<<<<<<<<<<<Solution found on pid %d >>>>>>>>>>>>>>>>>\n", pid);
        double end_time = MPI_Wtime();
        solutionFindTime = end_time - start_time;
    }
}

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

    double end_time;
    double duration;
    double initDuration;

    MPI_Init(&argc, &argv);
    MPI_Comm_size(MPI_COMM_WORLD, &process_count);
    MPI_Comm_rank(MPI_COMM_WORLD, &pid);
    char* file = argv[1];
    start_time = MPI_Wtime();

    if (process_count == 0 || process_count == 2)
        return 0;

    // 进程0使用的网格队列
    grids_queue* manager_gridQueue = NULL;
    int sudokuListSize = 0;

    // 管理进程初始化
    if (pid == 0)
    {
        double startInit_time = MPI_Wtime();
        manager_gridQueue = initParallel(process_count - 1, &sudokuListSize, file);
        initDuration = MPI_Wtime() - startInit_time;
        gridWidth = manager_gridQueue->item.size;
    }
    // 广播网格尺寸
    MPI_Bcast(&gridWidth, 1, MPI_INT, 0, MPI_COMM_WORLD);
    gridSize = gridWidth * gridWidth;
    if(pid == 0 && process_count != 1)
    {
        for (int i = 1; i < process_count; i++)
        {
            // 向其他进程发送初始网格
            MPI_Send(dequeue(&manager_gridQueue).sudoku, gridSize, MPI_INT, i, COMPUT_RECV_GRIDS, MPI_COMM_WORLD);
            sudokuListSize--;
        }
        int msg;
        int idlingProcessesCount = 0;
        int computationFinished = 0;
        do {
            // 接收其他进程的状态
            MPI_Status status;
            MPI_Recv(&msg, 1, MPI_INT, MPI_ANY_SOURCE, COMPUT_STATUS, MPI_COMM_WORLD, &status);
            // 回复管理进程状态
            int reply;
            if (sudokuListSize <= 0)
                reply = GRIDS_EMPTY;
            else if (sudokuListSize < process_count - 1)
                reply = GRIDS_AVAILABLE;
            else
                reply = GRIDS_FULL;

            MPI_Send(&reply, 1, MPI_INT, status.MPI_SOURCE, MANAGER_STATUS, MPI_COMM_WORLD);

            // 缓存来自计算进程的网格
            if (msg == 1 && reply != GRIDS_FULL) {
                enqueue(&manager_gridQueue, recvGrid(status.MPI_SOURCE, MANAGER_RECV_GRIDS));
                sudokuListSize++;
            }
            // 计算进程完成当前任务，闲置等待新工作
            else if (msg == 0) {
                if (reply != GRIDS_EMPTY) {
                    MPI_Send(dequeue(&manager_gridQueue).sudoku, gridSize, MPI_INT, status.MPI_SOURCE, COMPUT_RECV_GRIDS, MPI_COMM_WORLD);
                    sudokuListSize--;
                }
                // 无网格可用，等待更多进程确认是否完成
                else {
                    idlingProcessesCount++;
                    // 所有进程闲置且无剩余工作，结束计算
                    if (idlingProcessesCount == process_count - 1) {
                        computationFinished = 1;
                    }
                }
            }
        } while (computationFinished == 0);
    }
    else if(pid != 0)
    {
        // 计算初始网格
        computeGrid(recvGrid(0, COMPUT_RECV_GRIDS), 1);
        // 从动态队列获取网格计算
        int managerStatus;
        do {
            // 请求新工作
            int computeStatus = 0;
            MPI_Ssend(&computeStatus, 1, MPI_INT, 0, COMPUT_STATUS, MPI_COMM_WORLD);
            // 获取管理进程状态
            MPI_Recv(&managerStatus, 1, MPI_INT, 0, MANAGER_STATUS, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
            if (managerStatus != GRIDS_EMPTY)
                computeGrid(recvGrid(0, COMPUT_RECV_GRIDS), 1);
        } while (managerStatus != GRIDS_EMPTY);
    }
    else if (pid == 0 && process_count == 1) {
        computeGrid(dequeue(&manager_gridQueue), 0);
    }

    // 输出统计信息
    if (pid == 0) {
        end_time = MPI_Wtime();
        duration = end_time - start_time;
        D(printf("\\     //\n"));
        D(printf(" \\   //\n"));
        D(printf("  \\_// Duration: %f\n", duration));
        printf("%f\n", duration);
        printf("%f\n", solutionFindTime);
        printf("%f\n", initDuration);
    }

    MPI_Finalize();
    return 0;
}

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