c++ - 背包算法，如何获得更好的性能？

Question

Openmp 的性能优于串行代码 x2，但如果可能的话，我希望获得更好的性能。

这是C++中的串行代码:

for (int k = 0; k < numelem[i]; k++)
{
    sumK = sumK - weight[k];
    int cmax = 0;
    cmax = max(capacity - sumK, weight[k]);

    for (int c = capacity; c >= cmax; c--)
    {
        if (f[c] < f[c - weight[k]] + value[k])
        {
            f[c] = f[c - weight[k]] + value[k];
            M[capacity * k + c] = 1;
        }
    }
}

对于 openmp 版本，我使用了两个在每次迭代时交换的 f0、f1 数组。这有助于我防止竞争条件，但我想错误共享仍然存在(不确定)。其他我的假设是，pragma 中的条件语句用于减慢执行速度。

        for (int k = 0; k < numelem[i]; k++) {

            sumK = sumK - weight[k];
            int cmax = 0;
            cmax = max(capacity - sumK, weight[k]);
            int c = capacity;

            if (k % 2 == 0) {

#pragma omp parallel
    {

#pragma omp for
                for (c = capacity; c >= cmax; c--) {

                    //FALSE SHARING???

                    if (f0[c] < f0[c - weight[k]] + value[k]) {
                        f1[c] = f0[c - weight[k]] + value[k];
                        M[capacity * k + c] = 1;
                    } else {
                        f1[c] = f0[c];
                    }
                }
            } 

            else {

#pragma omp for
                for (c = capacity; c >= cmax; c--) {

                    //FALSE SHARING???

                    if (f1[c] < f1[c - weight[k]] + value[k]) {
                        f0[c] = f1[c - weight[k]] + value[k];
                        M[capacity * k + c] = 1;
                    } else {
                        f0[c] = f1[c];
                    }
                }

            }

        }
    }   

在这里您可以找到 serial c++ 的完整代码和 openmp c++

这项工作基于这篇文章:

• Solving knapsack problems on GPU by V. Boyera, D. El Baza, M. Elkihel
• 相关工作:Accelerating the knapsack problem on GPUs by Bharath Suri

Answer 1

我不知道 pragma 指令是做什么用的，但是关于算法，你可以优化这部分:

for (c = capacity; c >= cmax; c--) {

我猜 capacity 代表背包的全部容量。

想法是，您并不总是需要从这里开始进行迭代。从您当前访问过的项目的权重总和开始迭代就足够了。

所以你可以这样做:

      currentCapacity = 0;
      for (int k = 0; k < numelem[i]; k++) {

            currentCapacity += weight[k];
            sumK = sumK - weight[k];
            int cmax = 0;
            cmax = max(currentCapacity - sumK, weight[k]);
            int c = currentCapacity;

            if (k % 2 == 0) {

#pragma omp parallel
    {

#pragma omp for
                for (c = currentCapacity; c >= cmax; c--) {

它不会影响 big-oh 的复杂性，但它应该会在实践中提供性能提升，尤其是在您有大容量的情况下。

在此之后，您还应该强制当前容量永远不会超过背包的容量:

currentCapacity = min(currentCapacity, capacity);

在我添加的+=之后。