Алгоритм ранцевания, как повысить производительность?

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 массивы, которые поменялись местами на каждой итерации. Это помогает мне предотвратить состояние гонки, но я полагаю, что ложное разделение все еще присутствует (не уверен). Другое мое предположение состоит в том, что условные утверждения внутри прагмы замедляют выполнение.

 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 omp parallel 
{ 
    // I'm using auto, correct the type and initialize as needed 
    auto f_local = f; 
    auto sumK_local = sumK; 

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

     sumK_local = sumK_local - weight[k]; 
     int cmax = 0; 
     cmax = max(capacity - sumK, weight[k]); 
#pragma omp for 
     for (int c = capacity; c >= cmax; c--) 
     { 
      if (f_local[c] < f_local[c - weight[k]] + value[k]) 
      { 
      f_local[c] = f_local[c - weight[k]] + value[k]; 
      M[capacity * k + c] = 1; 
      } 
     } 
    } 
#pragma omp critical 
    { 
     for (int c = capacity; c >= cmax; c--) 
     { 
      if (f[c] < f_local[c]) 
      { 
       f[c] = f_local[c]; 
      } 
     } 
    } 
} 

Answer 2

Я понятия не имею, что инструкции 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--) { 

Это не повлияет на большой-ой сложности, но это должно предложить повышение производительности на практике, особенно если у вас есть большие возможности.

После этого, вы также должны заставить нынешние возможности никогда не превышает емкость котомке в:

currentCapacity = min(currentCapacity, capacity); 

После += я добавил.