2022 Special Admission Problem: Circular Dependency

[TOC]

Multiple Passes to Resolve Circular Dependency

Each pass attempts to update the value of b_new[i]. If b[i] >= i, the value is assigned directly; if b[i] < i, it checks whether b_new[b[i]] has already been updated. If not, this iteration is skipped and the update is retried on the next pass.

Core Code

• Initialize b_new to -1.
• Use a do-while loop for multiple passes until a pass produces no updates.
• In each iteration, only process elements that have not yet been updated.
• If b[i] >= i, assign directly.
• If b[i] < i but b_new[b[i]] has already been updated, also perform the assignment.
• Use an updated variable to detect whether any updates occurred during a pass.

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();

Optimization Results

Results on My Own Computer

Results on the University Supercomputer Platform