請加速以下程序。
|
|
有多行測資，每組第一行會有兩個整數 $N, \; K$，表示要排序 $N$ 個整數，並且以亂數種子 $K$ 生成。
輸出一行 $\sum i \cdot A_i$。
|
|
|
|
實作 bitonic sort，最簡單全部使用 global memory 完成，但是在遞迴公式中，當 $n$ 已經足夠小就可以代入 shared memory 進行計算，這時候效能就非常好。
|
|
當然這種最常見的函數一定有內建可以協助，如 thrust library 就有提供相關的函數，但第一次執行時會特別地慢，有可能是 library 要代入 cache 的緣故。
|
|
|
|
這一題要完成數個 kernel function 可以同時運行，因為有時候使用的 core 並不會同時運作，在有剩餘的 core 情況下，就可以將下一個 kerenl function 帶進來運作，這時候效能就可以大幅度提升。
隨便寫一個測試即可，但是在設計這一題時，發現新版的 GTX 980Ti 並不支援，藉由 CUDA 環境變數仍然無法看出，最後只能在舊版的 GPU 上，利用舊有的 nvprof 進行分析，儘管是最新版的 nvvp 仍然無法針對在 GTX 980Ti 裝置上運作。
|
|
稀疏矩陣為大部份元素皆為零的矩陣，在科學與工程領域中求解線性模型時經常出現大型的稀疏矩陣。現在給予最常見的 Coordinate Format (簡稱 COO 格式)，請問兩個矩陣相乘結果為何。
給予矩陣 $A{n, m}$ 和 $B{m, r}$，請計算稀疏矩陣相乘。
$$A_{4,4} = \begin{bmatrix} 0 & 0 & 0 & 0 \\ 5 & 8 & 0 & 0 \\ 0 & 0 & 3 & 0 \\ 0 & 6 & 0 & 0 \\ \end{bmatrix}, \qquad B_{4,4} = \begin{bmatrix} 0 & 0 & 1 & 3 \\ 0 & 5 & 2 & 0 \\ 3 & 5 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ \end{bmatrix}$$根據 COO 格式，分別轉換矩陣 $A$ 和 $B$ 的所有非零元素，如下表所示
row_index |
col_index |
value |
|---|---|---|
| 1 | 0 | 5 |
| 1 | 1 | 8 |
| 2 | 2 | 3 |
| 3 | 1 | 6 |
row_index |
col_index |
value |
|---|---|---|
| 0 | 2 | 1 |
| 0 | 3 | 3 |
| 1 | 1 | 5 |
| 1 | 2 | 2 |
| 2 | 0 | 3 |
| 2 | 1 | 5 |
| 3 | 1 | 2 |
測資只有一組，第一行會有三個整數 $N, \; M, \; R$，分別表示矩陣 $A, \; B$ 的大小。下一行會有兩個整數 $N_A, \; N_B$，接下來會有 $N_A$ 行，每一行表示矩陣 $A$ 的 COO 格式，隨後會有 $N_B$ 行，每一行表示矩陣 $B$ 的 COO 格式。
給予 COO 格式時，先按照 row_index 由小到大，相同情況由 col_index 由小到大的方式給定，保證不會有重複，每一個元素值 $v$ 介於 $1$ 到 $2^{31}-1$ 之間。
輸出 $C_{n, r} = A_{n, m} \times B_{m, r}$ 的雜湊值。
定義 $\mathit{hash}(C_{n, r}) = \sum\nolimits_{e_{i, j} \in C \text{ and } e_{i, j} \neq 0} \mathit{encrypt}((i+1)*(j+1), e_{i, j})$，實際運作的 流程 可參考以下作法，當然你沒辦法宣告 $N \times M$ 的空間使用：
|
|
|
|
|
|
需要將矩陣 $B$ 轉置後排序，整理成 COO 格式，宣告足夠多的 thread，每一個 thread 分配一個列所有的值，接著使用類似合併排序的方式將答案統計出來。這個版本的效率不算高，因為太多的 branch 以及資料部分上導致 load balance 非常不好，再者是一堆 global memory access。
|
|
每一個 thread 計算 $C_{i, [L, R]}$，然後用額外的空間進行 mapping，並且把這個空間宣告在 private memory，也就是 register 上來加速。這一個做法比上述作法還快個三到四倍。
|
|
小明的數學作業要計算方陣，現在請你幫幫他！
題目給定數個 $N \times N$ 的矩陣和 $2$ 小題。
|
|
輸入有多組測資，每組第一行會有一個整數 $N$，表示題目給定 $N \times N$ 矩陣，第二行上會有 $6$ 個整數，分別為矩陣 $A, B, C, D, E, F$ 的生成種子。
輸出兩行 $X$ 和 $Y$ 的雜湊值，可參考 sequence.c 的流程。
|
|
|
|
|
|
與 OpenMP 一起設計，仿造 OpenCL 版本。
|
|
根據 Nvidia - Streams and Concurrency 讓 Data transfer 和 Kernel execute 時間重疊達到加速。
|
|
Accepted 判斷依準：單一 Device 是否在運行過程中發生并行。
出這一題是為了測試 software pipeline 的設計，加快批次處理的效能，藉由數個 stream 的使用，讓資料傳輸和計算相互重疊。
這一題讓我設計測試 Judge 相當懊惱，藉由 Nvidia 提供環境變數的 debug 資訊產生的 log 檔就能分析執行區間是否有重疊，這個問題就迎刃而解。當然此題不在課程範圍內，提案給老師說要不要教，預料中地被打槍。
|
|
小明的數學作業要計算方陣，現在請你幫幫他！
題目給定數個 $N \times N$ 的矩陣和 $Q$ 小題，每一小題只由加法和乘法構成。
|
|
測資只有一組，第一行會有兩個整數 $M,N$，表示題目給定 $M$ 個 $N \times N$ 矩陣，第二行上會有 $N$ 個整數 $S_i$ 個第 $i$ 個矩陣生成種子。最後會有一行一個整數 $Q$，表示接下來有 $Q$ 行詢問，每一行上會有一個字串 $E$ 表示接下來要處理的矩陣表達式，$E$ 只包含 A-Z 以及 +。
對於每一組測資輸出一行。
|
|
|
|
|
|
跟 OpenCL 的做法類似，讓三個 device 共同合作，每一個表達式都交給一個 device 完成，所以目標分配這些表達式使得計算最長時間最小化。處理手法都差不多，經過調校比 OpenCL 還要快上一些。
由於 CUDA 要藉由 cudaSetDevice(p); 設定計算裝置，那麼相信這個 global function 設置變數是採用 __thread 保留字完成，因此用 OpenMP 建立三條 thread，分別設置就不會相互影響，設置 __thread 的變數在各自 thread 下是獨立不受影響的。
|
|
小明的數學作業要計算方陣，現在請你幫幫他！
題目給定數個 $N \times N$ 的矩陣和 $2$ 小題。
|
|
測資只有一組，第一行會有一個整數 $N$，表示題目給定 $N \times N$ 矩陣，第二行上會有 $6$ 個整數，分別為矩陣 $A, B, C, D, E, F$ 的生成種子。
輸出兩行 $X$ 和 $Y$ 的雜湊值，可參考 sequence.c 的流程。
|
|
|
|
|
|
|
|
|
|
為了加快計算，一個 block 最多有 1024 個 thread 運行，因為牽涉到 warp scheduling/size，又要充分利用每一個 core 的計算能力，根據實驗結果 block size 盡可能大，且又不超過 register 個數為佳，這時候效能就會是最好的。這一點與 OpenCL 不同，當 OpenCL 偵測到填入的 block size 為 NULL 時，他會自動調整到最好的大小，而在 CUDA 就要使用者自己設定才行，這導致有些人反而不會去管大小。
根據上述所講，當然直接貪心找最大值填入即可。
|
|
生命遊戲中，對於任意細胞，規則如下：
每個細胞有兩種狀態-存活或死亡，每個細胞與以自身為中心的周圍八格細胞產生互動。
可以把最初的細胞結構定義為種子，當所有在種子中的細胞同時被以上規則處理後，可以得到第一代細胞圖。按規則繼續處理當前的細胞圖，可以得到下一代的細胞圖，周而復始。
輸入第一行有兩個整數 $N$, $M$，表示盤面大小為 $N \times N$，模擬週期次數 $M$。接下來會有 $N$ 行，每一行上會有 $N$ 個字符，以 0 表示 $(i, j)$ 格子上的細胞屬於死亡狀態，反之 1 為存活狀態。
對於每一組測資輸出 $N$ 行，每一行上有 $N$ 個字元表示模擬 $M$ 次的最終盤面結果。
|
|
|
|
|
|
|
|
|
|
CUDA 的函數分成 blocking 或者是 non-blocking，這是因為是異質計算在 host 上不一定要等到 GPU 算完才能執行下一行指令。kernel function call 是 non-blocking 的，可以藉由 cudaDeviceSynchronize 等待 device 所有的 task 都完成，才進行到下一個運行區塊。
但是別忘記 cudaMemcpy 和 kernel function call 這一類都類似 OpenCL 的 Command Queue，若沒有特別設定，原則上都是 in-order 處理 (相對於隨意順序，必須按照進入 queue 的順序執行)，因此 memory copy 也是一條指令，cudaMemcpy 屬於 blocking 函數，在設計上就不一定要加上 cudaDeviceSynchronize。
|
|
計算兩個大小為 $N \times N$ 方陣 $A, \; B$ 相乘結果 $C = A \times B$。為了節省輸入輸出時間，採用亂數產生，可以參考下述程式碼，並改寫成 CUDA 的版本進行加速。
|
|
測資只有一組，包含三個整數 $N, S_1, S_2$，分別為方陣大小 $N \times N$，產生矩陣 $A$、$B$ 的亂數種子。
輸出一行雜湊值 $H$，可參考 sequence.c 的流程。
|
|
|
|
|
|
與 OpenCL 版本相比，是否乾淨許多呢？完全不用管到底 Context 和 Kerenl Program 如何建造，但是這一些方便性都是因為預設導致的結果。
CUDA 預設會在 device 0 上運作，也就是 PCI-E 順位上的第一個顯卡，若要更動藉由函數 cudaSetDevice(deviceId); 完成，而 OpenCL 的 CommandQueue 則對應到 CUDA 的 Stream，在稍後的題目中，我會提供些許的範例使用 CUDA 這些函數，協助設計的計算流程可以加快。
|
|
請用 CUDA 改寫下段的計算：
|
|
|
|
|
|
|
|
|
|
這裡同我們在 OpenCL 的實作技巧，將生成測資和計算都丟在 GPU 上完成，但是 CUDA 只能在 Nvidia 顯卡上運作，而且根據版本的不同，每一種顯卡的計算能力也不同，可以參考 wiki，最低版本為 1.0，也就在編譯參數中加入 nvcc -arch=compute_10，如果可以到 2.0，下達 nvcc -arch=compute_20，以此類推。編譯器預設計算能力為 1.0，因此如果要在 kernel function 裡面印出訊息 (意即 printf())，至少提供 2.0 以上的編譯參數。
CUDA 程式撰寫就不用像 OpenCL 從找尋 Platform 到抓到 Device，之後再藉由 Device IDs 建立 Context，再從 Context 建立 Program，CUDA 提供 特殊語法，而不像 OpenCL 採用 特殊函數 包裝，這導致編程複雜度差異極大，但是從彈性來看 OpenCL 可以調控的項目較多且動態，但 CUDA 由於是自家產品，效能會稍微比同版本的 OpenCL 來得快，一部分也是因為編譯器不同導致的緣故。
|
|