2022特招题：循环依赖

[TOC]

多次循环以解决循环依赖

每次遍历都尝试更新 b_new[i] 的值。如果 b[i] >= i，则直接赋值；如果 b[i] < i，则检查 b_new[b[i]] 是否已更新，如果未更新，则跳过此次迭代，等待下一次迭代再尝试更新。

核心代码

• 初始化 b_new 为 -1。
• 使用 do-while 循环进行多次遍历，直到一个遍历中没有任何更新为止。
• 在每次迭代中，只处理尚未更新的元素。
• 如果 b[i] >= i，直接赋值。
• 如果 b[i] < i 但 b_new[b[i]] 已被更新，也进行赋值。
• 使用 updated 变量来检测在一次遍历中是否有更新。

start2 = omp_get_wtime();
/******************/
//创建b_new数组
int *b_new = (int *)malloc(sizeof(int) * N);

// 初始化b_new数组为-1
#pragma omp parallel for num_threads(10)
for (int i = 0; i < N; i += 8) // 循环展开
   {
        b_new[i] = -1;
        b_new[i + 1] = -1;
        b_new[i + 2] = -1;
        b_new[i + 3] = -1;
        b_new[i + 4] = -1;
        b_new[i + 5] = -1;
        b_new[i + 6] = -1;
        b_new[i + 7] = -1;
   }

int updated;
// do-while多次遍历以解决依赖
do {
    updated = 0;
    #pragma omp parallel for num_threads(10)
    for (int i = 0; i < N; i++)
    {
        if (b_new[i] == -1) // 只处理尚未更新的元素
        {
            if (b[i] >= i)
            {
                b_new[i] = b[b[i]];// 取原数组元素进行更新
                updated = 1;
            }
            else if (b_new[b[i]] != -1)
            {
                b_new[i] = b_new[b[i]];// 取新数组元素进行更新
                updated = 1;
            }
        }
    }
} while (updated); 
// 如果这次遍历中有更新，则继续下一次遍历，否则说明所有位置都已经更新

/******************/
end2 = omp_get_wtime();

优化结果

在自己的电脑上的效果

在学校超算平台上的效果