相关疑难解决方法(0)

我目前正在实现一个动态编程算法来解决背包问题.因此我的代码有两个for循环,一个外循环和一个内循环.

从逻辑的角度来看,我可以并行化内部for循环,因为它们之间的计算是相互独立的.由于依赖性,外部for循环不能并行化.

所以这是我的第一个方法:

for(int i=1; i < itemRows; i++){
        int itemsIndex = i-1;
        int itemWeight = integerItems[itemsIndex].weight;
        int itemWorth = integerItems[itemsIndex].worth;

        #pragma omp parallel for if(weightColumns > THRESHOLD)
        for(int c=1; c < weightColumns; c++){
            if(c < itemWeight){
                table[i][c] = table[i-1][c];
            }else{
                int worthOfNotUsingItem = table[i-1][c];
                int worthOfUsingItem = itemWorth + table[i-1][c-itemWeight];
                table[i][c] = worthOfNotUsingItem < worthOfUsingItem ? worthOfUsingItem : worthOfNotUsingItem;
            }
        }
}

代码运行良好,算法正确解决了问题.然后我考虑优化这个,因为我不确定OpenMP的线程管理是如何工作的.我想在每次迭代期间防止不必要的线程初始化,因此我在外部循环周围放置了一个外部并行块.

第二种方法:

#pragma omp parallel if(weightColumns > THRESHOLD)
{
    for(int i=1; i < itemRows; i++){ …