10164. Fast 0/1 Knapsack Problem on PC (OpenMP)

I'm a slow walker, but I never walk backwards.

背景

在一般的個人電腦中,核心數量和快取能力與伺服器有所不同。甚至可以特地購買強化快取能力、高時脈、高核心數的處理器 ... 等。不同的組合使其搭配著不同需求的應用,藉以獲得最好的效能展示。現在手上的機器最多使用 2 條執行緒,請問要如何設計高效的平行算法?

題目描述

有 $N$ 個重量和價值分別為 $W_i, V_i$ 的物品,現在要從這些物品中選出總重量不超過 $M$ 的物品,求所有挑選方案中的總價值最大值為何。

輸入格式

輸入只有一組測資,第一行會有兩個整數 $N, M$ 分別表示物品數量和背包能容大的最大重量 $M$。接下來會有 $N$ 行,第 $i$ 行上會有兩個整數 $W_i, V_i$,分別為物品 $i$ 的重量和價值。

  • $1 \le N \le 10000$
  • $1 \le M \le 5000000$
  • $1 \le W_i, \; V_i \le 100000$

輸出格式

輸出一行整數,挑選方案中的最大價值 $B$。保證答案在 32-bit integer 內。

範例輸入

4 5
2 3
1 2
3 4
2 2

範例輸出

7

編譯參數

gcc -std=c99 -O2 -fopenmp main.c -o main -lm
g++ -std=c++98 -O2 -fopenmp main.cpp -o main -lm

特殊環境

在這一題中約束使用 2 條執行緒,若使用超過 2 個執行緒,將會得到 Runtime Error 的錯誤訊息。

OpenMP

透過 void omp_set_num_threads(int num_threads); 設定在 #pragma omp parallel 區域中預設的執行緒數量。下述程式預設 2 條執行緒。

1
2
3
4
5
6
#include <omp.h>
...
int main() {
    omp_set_num_threads(2);
    ...
}

Thread Affinity 執行緒親合性 Linux 版本

若在上傳程式碼中不設定此部分,將會隨機分配到某個處理器上,運氣不好將會得到 TLE。

透過 CPU_SET 加入可運行的 CPU 編號,使用編號可以藉由 tophtop ... 等指令查閱,最後藉由 int sched_setaffinity(pid_t pid, size_t cpusetsize, cpu_set_t *mask); 設定執行緒的環境。下述的例子為親合於 CPU0~CPU5 環境設定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define _GNU_SOURCE
#include <sched.h>
#include <assert.h>
...
int main() {
    #pragma omp parallel
    {
        cpu_set_t cpuset;
        CPU_ZERO(&cpuset);
        for (int i = 0; i < 6; i++)
            CPU_SET(i, &cpuset);
        assert(sched_setaffinity(0, sizeof(cpuset), &cpuset) == 0);
    }
}

在課程使用的 miwa 主機上,處理器 1 的核心編號為 CPU 0-5、CPU 12-17,處理器 2 的核心編號為 CPU 6-11、CPU 18-23,請盡量使用處理器 1,其原因在於非均勻訪存記憶體的關係,處理器 2 存取記憶體的速度稍慢 (若不掉出 L3 Cache 原則上效能是一樣的)。效能差異請自行測試,這可能會影響到你的平行算法設計。

Discussion