递归函数并行化问题：OpenMP优化find_words函数遇性能异常

问题描述 #

我实现了一个基于递归回溯的字母网格单词查找程序，串行运行时约40秒能得到正确结果，但尝试用OpenMP并行化后，程序运行时间过长疑似死循环。

递归函数代码：

void find_words(char grid[ROWS][COLS], int row, int col, char prefix[MAX_WORD_LENGTH], int visited[ROWS][COLS], node_t** table) {
    // Mark current cell as visited
    visited[row][col] = 1;

    // Append current letter to prefix
    char current_word[MAX_WORD_LENGTH];
    strncpy(current_word, prefix, MAX_WORD_LENGTH);
    strncat(current_word, &grid[row][col], 1);

    // Check if prefix is a word in the dictionary
    if (ht_search(table, current_word)) 
    {
         int is_Exist=0;
         int i;
       
        for (i=0;i<found_words_counter;i++)
         {
            if(strcmp(found_words[i],current_word)==0)
            {
               is_Exist=1;
               break;
            }
         }  
         if(!is_Exist)  
            {   
              strncpy(found_words[found_words_counter++],current_word,MAX_WORD_LENGTH);
            }
       }
   
    // Check for words that can be formed by extending the prefix
    int i, j;
    #pragma omp parallel for private(i, j) shared(grid, visited, table, current_word)
      for (i = -1; i <= 1; i++) {
        for (j = -1; j <= 1; j++) {
            if (row+i >= 0 && row+i < ROWS && col+j >= 0 && col+j < COLS && !visited[row+i][col+j] && !(i == 0 && j == 0)) {
                find_words(grid, row+i, col+j, current_word, visited, table);
            }
        }
    }

    // Mark current cell as unvisited
    visited[row][col] = 0;
}

主函数调用代码：

#pragma omp parallel for private(i, j) shared(grid, visited, table, prefix)
for (i = 0; i < ROWS; i++) {
    for (j = 0; j < COLS; j++) {
        find_words(grid, i, j, prefix, visited, table);
    }
}

程序功能是从ROWS×COLS的字母网格中，通过回溯拼接字母前缀，检查前缀是否存在于含50k单词的哈希表中，若存在则加入结果数组。请问递归函数能否并行化？如何正确修改实现并行化？

解决方案 #

递归回溯类程序可以并行化，但你的代码存在三个核心问题导致死循环和性能崩溃，以下是修复方案：

1. 消除共享visited数组的线程冲突 #

你在主函数中让所有线程共享同一个visited数组，多个线程同时修改和回溯标记时会彻底混乱：比如线程A标记某单元格为已访问，线程B未感知到该标记就重复访问，或者线程A回溯时错误清除线程B的标记，直接引发无限递归或死循环。

修复：每个线程的起始单元格迭代（每个i,j）必须拥有独立的visited数组副本，主函数并行循环修改如下：

#pragma omp parallel for collapse(2) private(i, j, visited, prefix)
for (i = 0; i < ROWS; i++) {
    for (j = 0; j < COLS; j++) {
        // 每个迭代初始化独立的visited数组和空前缀
        int visited[ROWS][COLS] = {0};
        char prefix[MAX_WORD_LENGTH] = "";
        find_words(grid, i, j, prefix, visited, table);
    }
}

collapse(2)用于并行化二维循环，提升线程利用率；每个迭代的visited和prefix都是私有变量，线程间完全隔离。

2. 修复全局结果数组的竞态条件 #

found_words和found_words_counter是全局共享变量，多个线程同时读写会导致数据竞争：比如两个线程同时判断某个单词未存在，然后同时写入数组导致内容覆盖，或者计数器递增混乱引发数组越界，这也会导致程序异常或卡死。

修复：用OpenMP临界区保护对全局结果的操作，缩小临界区范围以减少性能损失：

if (ht_search(table, current_word)) 
{
    #pragma omp critical
    {
        int is_Exist = 0;
        for (int k = 0; k < found_words_counter; k++)
        {
            if(strcmp(found_words[k], current_word) == 0)
            {
                is_Exist = 1;
                break;
            }
        }  
        if(!is_Exist)  
        {   
            strncpy(found_words[found_words_counter++], current_word, MAX_WORD_LENGTH);
        }
    }
}

若担心临界区开销过大，可改为每个线程先收集自身的结果列表，最后再合并到全局数组，完全避免竞争。

3. 删除递归内部的并行循环 #

你在递归函数中嵌套了#pragma omp parallel for，这会导致每次递归都创建新的线程池，线程数量指数级增长，系统资源直接耗尽，程序彻底卡死。

修复：去掉递归内部的并行指令，改为串行遍历邻接单元格：

// 去掉#pragma omp parallel for，改为串行循环
int i, j;
for (i = -1; i <= 1; i++) {
    for (j = -1; j <= 1; j++) {
        if (row+i >= 0 && row+i < ROWS && col+j >= 0 && col+j < COLS && !visited[row+i][col+j] && !(i == 0 && j == 0)) {
            find_words(grid, row+i, col+j, current_word, visited, table);
        }
    }
}

修改后的完整递归函数 #

void find_words(char grid[ROWS][COLS], int row, int col, char prefix[MAX_WORD_LENGTH], int visited[ROWS][COLS], node_t** table) {
    // Mark current cell as visited
    visited[row][col] = 1;

    // Append current letter to prefix
    char current_word[MAX_WORD_LENGTH];
    strncpy(current_word, prefix, MAX_WORD_LENGTH);
    strncat(current_word, &grid[row][col], 1);

    // Check if prefix is a word in the dictionary
    if (ht_search(table, current_word)) 
    {
        #pragma omp critical
        {
            int is_Exist = 0;
            for (int k = 0; k < found_words_counter; k++)
            {
                if(strcmp(found_words[k], current_word) == 0)
                {
                    is_Exist = 1;
                    break;
                }
            }  
            if(!is_Exist)  
            {   
                strncpy(found_words[found_words_counter++], current_word, MAX_WORD_LENGTH);
            }
        }
    }

    // Check for words that can be formed by extending the prefix
    int i, j;
    for (i = -1; i <= 1; i++) {
        for (j = -1; j <= 1; j++) {
            if (row+i >= 0 && row+i < ROWS && col+j >= 0 && col+j < COLS && !visited[row+i][col+j] && !(i == 0 && j == 0)) {
                find_words(grid, row+i, col+j, current_word, visited, table);
            }
        }
    }

    // Mark current cell as unvisited
    visited[row][col] = 0;
}

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