## (1)研究題目
A GPU approach in solving Knapsack Problems.
## (2)組員分工
黃恩明：研究方法設計、程式實做
黃永玄：文獻資料整理
## (3)研究動機
The Knapsack Problem is a popular combinatorial optimization problem which be the type NP-hard. It assumes a case where there is a knapsack which can hold a maximum weight W. There is a set of items N from which each item has its own weight and value. The problem is how to pack the knapsack with the maximum possible value and also staying under the weight limit of W.
The 0/1 Knapsack Problem is a unique case of the classic Knapsack Problem. Each item from the set is either included or excluded in its entirety. A brute force approach can be used which would generate all the subsets of N and compare them to get the most optimal solution. But as the input size increases, the number of subsets also increases exponentially making this approach computationally impractical.
We propose a GPU-based approach with Dynamic Programing algorithem as a common and efficient implementation to solve this problem. It employs the use of dividing the problem into multiple subproblems to make it more suitable for parallel computation.
We use GPU threads and memory managing which simultaneously work on the different sub-problems, hence making the computation much faster and efficient. Our present approach employs only a single GPU and we further aim to extend it to a multi-GPU approach shortly.
## (4) 研究方法
### 4.1 文獻探討
#### 4.1.1 問題定義
我們先對問題進行分割，對某一件物品有兩種狀態也就是選擇放或不放：
- 不放進背包，背包價值不變、背包耐重不變
- 放進背包，背包價值上升、背包耐重下降
可以歸納出一個公式為
如果以遞迴的方式處理此問題，可以整理出一個公式為：
```
c(n, w) = max( c(n-1, w), c(n-1, w-weight[n]) + cost[n] )
n：已經放入第 0 個到第 n 個物品到背包
w：背包能承受的重量上限
c(n, w)：如果只有第 0 個到第 n 個物品，且承受重量為 w 時，同時也代表是最大的價值的答案。
weight[n]：第 n 個物品的重量。
cost[n]：第 n 個物品的價值。
```
也就是 c(n-1, w) 代表不放入背包，價值為放 n-1 個物品的價值，而若決定要放入背包，其價值代表 c(n-1, w-weight[n]) + cost[n] 就代表要放入背包，價值為上一次的價值加上此次物品價值。
#### 4.1.2 CPU 計算
以 CPU 的方式來處理背包的問題與一般動態規劃問題一樣，只要找出狀態（重量、價值）與選擇（放入背包、不放背包）就可以處理[1]，其時間複雜度在窮舉的情況下 總共會有 O(2ᴺ) 個集合，驗證一個子集合需時 O(N)，因此總時間時間複雜度 O(2ᴺN) ，其中 N 是物品的數量。
實做方式可以根據推算方式可以再分成 Top-down 與 Bottom-up：
```
// Top Down
const int N = 100; // 物品總數上限
const int W = 100000; // 背包耐重上限
//（可以使用物品的總重量作為此值）
int cost[N], weight[N]; // 物品的價值與重量
int c[N + 1][W + 1]; // DP表格
// n為物品個數，w為背包耐重限制。
int knapsack(int n, int w)
{
if (w < 0) return -1e9; // 耐重能力不足，故只能不放。
if (n == 0) return 0; // 沒有物品時，就沒有cost。
// memoization，直接讀取記憶體的答案。
if (c[n][w]) return c[n][w];
// 遞迴求得小問題的答案
return c[n][w] = max(
knapsack(n-1, w-weight[n]) + cost[n],
knapsack(n-1, w)
);
}
```
```
// Bottom-up
const int N = 100, W = 100000;
int cost[N], weight[N];
int c[N + 1][W + 1];
void knapsack(int n, int w)
{
memset(c, 0, sizeof(c));
for (int i = 0; i < n; ++i) // 窮舉每種物品
for (int j = 0; j <= w; ++j)// 窮舉每種重量
if (j - weight[i] < 0)
// 耐重能力不足，故只能不放。
c[i+1][j] = c[i][j];
else
// 耐重能力足夠，可以放或不放。
c[i+1][j] = max(
c[i][j],
c[i][j - weight[i]] + cost[i]
);
cout << "最高的價值為" << c[n][w];
}
```
#### 4.1.3 GPU 計算
有些研究已經針對KP提出了幾種平行動態編程算法（例如：參見[2]，[3]和[4]），我們知道在處理背包過程中，大部份是在計算 c(n, w) 的值，因此我們需要平行化這個計算過程。
[5] 提出一個方法是基於 GPU 的 m 個 kernels 並由 CPU thread 進行管理，Kernel 裡面是要計算的每個背包最大價值，這種方法主要好處是在整個流程中每個 CPU Thread 的內容，也就是在平行的步驟結束時都不會殺死 CPU Thread 所以可以保證 communication 的最小化。
### 4.2 Memory Usage Enhance
我們的研究中主要是針對單一 GPU 的計算能力最大化，針對 Memory 的使用方法進行調整與改善。
#### 4.2.1 基於重量的 memory 管理
#### 4.2.2 基於價值的 memory 管理
(5)程式解說
## (6) 實驗數據及討論
### 6.1 Optimization Techniques
#### 6.1.1 Algorithm
1. Bucket grouping
2. `std::sort`
3. Bitmask
4. Pruning
5. Rolling array
#### 6.1.2 Other
1. Async memcpy
2. Larger bitmask capacity (32bit -> 64bit)
3. Unrolling loops
4. Memory Padding
5. Accessing coalesced memory
6. Use `__device__ int __ffsll (long long int)`
7. Calculate more numbers in each threads
(7)結論
參考資料：
1. Martello, Silvano. "Knapsack problems: algorithms and computer implementations." Wiley-Interscience series in discrete mathematics and optimiza tion (1990).
- http://www.or.deis.unibo.it/kp/Chapter2.pdf
- https://dl.acm.org/doi/book/10.5555/98124
2. El Baz, Didier, and Moussa Elkihel. "Load balancing methods and parallel dynamic programming algorithm using dominance technique applied to the 0–1 knapsack problem." Journal of Parallel and Distributed Computing 65.1 (2005): 74-84.
3. Lou, Der-Chyuan, and Chin-Chen Chang. "A parallel two-list algorithm for the knapsack problem." Parallel Computing 22.14 (1997): 1985-1996.
4. Gerasch, Thomas E., and Pearl Y. Wang. "A survey of parallel algorithms for one-dimensional integer knapsack problems." INFOR: Information Systems and Operational Research 32.3 (1994): 163-186.
5. Boyer, Vincent, Didier El Baz, and Moussa Elkihel. "Dense dynamic programming on multi GPU." 2011 19th International Euromicro Conference on Parallel, Distributed and Network-Based Processing. IEEE, 2011.
- https://www.sciencedirect.com/science/article/pii/S0305054811000876
6. Boyer, Vincent, Didier El Baz, and Moussa Elkihel. "Solving knapsack problems on GPU." Computers & Operations Research 39.1 (2012): 42-47.
7. https://hal.archives-ouvertes.fr/hal-01152223/file/ArticleCuda.pdf
8. https://on-demand.gputechconf.com/gtc/2015/posters/GTC_2015_Developer_Algorithms_09_P5238_WEB.pdf
以小組方式進行
> 作業要求:
> 1. 自行定義一個利用平行計算方法的研究題目
> 2. 目的是展示如何利用平行計算方法實現一個計算的應用，或改善原有程式的效能
> 3. 必須要有程式實作，並在期末向助教demo
> 3. 完成一份成果報告書，內容包含
> (1)研究題目、(2)組員分工、(3)研究動機、(4)研究方法、(5)程式解說、(6)實驗數據及討論、(7)結論
> 4. 一份簡報投影片，並在期末做10分鐘的口頭報告
>
> 繳交項目:
> 在deadline(1/10 23:59)(1/12 23:59)前，上傳以下項目至ilms
> 1. 成果報告書
> 2. 報告投影片
> (程式碼不需要繳交，但要在課程的程式環境，或自行準備的環境，完成demo)
>
> 評分標準: (可參考附件的評分表)
> 1. 題目的定義
> 2. 作法的合理性
> 3. 實作的技術難度
> 4. 結果的評量方式與討論
> 5. 內容的表達清晰度
>
> 配分:
> 1. 成果報告書: 30%
> 2. Demo: 30%
> 3. 口頭報告: 40%
Sign in with Wallet
Connect another wallet