---
tags: para., Cuda, opencl, convolution
---

# OpenCL Programming

## Q1: Explain your implementation. How do you optimize the performance of convolution?

### 介紹
我從最初將 image 從 global memory 直接進行計算一步一步改進到最後使用 local memory 進行捲積計算並將常用的 filter 使用 constant 型態來加速讀取，配合 unrolling 減少 GPU 讀取指令的開銷，從 Method 1 ~ Method 4 是我的優化過程。

### 方法
#### Method 1:
最初方法使用 30000 個 thread 來處理 600 * 400的影像，平均每個 thread 需計算出 8 個 filter 的捲積計算，其結果如下表。

| Filter size | 3 | 5 | 7 |
|:----------------------- | ----- | ----- | ----- |
| Spend time (ms) | 0.747 | 1.632 | 1.579 |
| Speedup over the serial | 6.64 | 17.26 | 17.57 |

#### Method 2:
每次進行捲積計算 filter 陣列中的數值都必須經歷一遍，因此 filter 是經常使用且不會進行變更的變數，將其設定為 constant 的暫存器中，constant 的暫存器比 global 還要快，因為他會在 Kernel 啟動前預先緩存，但是大小有所限制，沒辦法使用太大的範圍，經過優化後結果如下表。

| Filter size | 3 | 5 | 7 |
|:----------------------- | ---- | ----- | ----- |
| Spend time (ms) | 0.78 | 1.468 | 1.454 |
| Speedup over the serial | 6.39 | 18.48 | 18.90 |

#### Method 3:
我改變分配 CUDA thread 的策略，設定一個 local 16*16 的 thread block 來對總 global thread 數為圖片大小(長寬取為 thread block 的整數倍)並逐次進行處理，並在計算圖片捲積前，先行將 Input Memory 存到 Local Memory 再進行計算，如此可以加速計算的速率。

我在決定使用 16 * 16 的 thread block 之前也嘗試使用 8 * 8 和 32 * 32 的 thread block 其效果平均來講都略遜於 16 * 16 得 local thread，如下圖，橫軸是 Filter size ，縱軸是比起 serial 的加速倍數。

因此最終選擇16 * 16 的 local thread ，最後結果如下表:
| Filter size | 3 | 5 | 7 |
|:----------------------- | ----- | ----- | ----- |
| Spend time (ms) | 0.552 | 0.591 | 0.604 |
| Speedup over the serial | 9.06 | 46.53 | 44.96 |

#### Method 4:
由於 GPU 不像 CPU 可以忽略迴圈和攤開迴圈之間的差別，GPU 對於讀取指令的開銷是相對大的，因此大量的程式迴圈會拖累整體的執行效率，因此我將雙層迴圈攤開了一層，證實確實對效能有所幫助。結果如下表:

| Filter size | 3 | 5 | 7 |
|:----------------------- | ----- | ----- | ----- |
| Spend time (ms) | 0.519 | 0.662 | 0.566 |
| Speedup over the serial | 9.57 | 41.94 | 48.59 |

### 總結
其中加速有最顯著成果提升的部位再於將計算用的數值從 global 存到 local 之後再進行計算，如此改進提升了兩倍之多的速度，因為捲積計算主要重複最多次且花費最多時間的部位就在 filter 和 piexl 間的乘法計算，而且同一 piexl 總是不只一次被一個捲積計算所使用到，也導致讀取該變數數值的速率變得十分重要。四方法比較的摺線圖如下，橫軸是 Filter size ，縱軸是比起 serial 的加速倍數。: