給兩個字串 $X, \; Y$，在兩個字串中都有出現且最長的子序列 (subsequence)，就是最長共同子字串
。
有多組測資，每組測資有兩行字串 $X, \; Y$，$X, \; Y$ 只由 A T C G 四個字母構成。
針對每一組測資，輸出一行 $X, \; Y$ 的最長共同子字串長度以及任何一組最長共同子字串。
|
|
|
|
|
|
附錄為舊版設計，可以針對 OpenMP 的設計再重新設計 CUDA 版本。
舊版設計根據 CPU 平行與不平行以及 GPU 三種狀態，根據閥值決定要選擇運行哪一種版本。若加上足夠小的情況下，直接用 $O(N^2)$ 表格直接回溯，和 OpenMP 判斷閥值的公式，效能還能在加速個兩到三倍，但整體而言未必比純 OpenMP 還要快，因為有 GPU 啟動的 overhead，要跑夠多的測資才看得出來。
|
|
給兩個字串 $X, \; Y$，在兩個字串中都有出現且最長的子序列 (subsequence)，就是最長共同子字串
。
有多組測資，每組測資有兩行字串 $X, \; Y$，$X, \; Y$ 只由 A T C G 四個字母構成。
針對每一組測資，輸出一行 $X, \; Y$ 的最長共同子字串長度。
|
|
|
|
|
|
相比於 OpenMP 版本，由於 GPU 的快取設計不如 CPU，在我們使用失敗指針優化 branch 的發生，對 GPU 反而還是慢的，因為要存取 global memory，這使得還不如發生 branch，讓 warp 分多次跑反而比較快，因為有足夠多的 warp 在一個 block。在優化程度上，CPU 和 GPU 還是得分開解決。
|
|
給兩個字串 $X, \; Y$，在兩個字串中都有出現且最長的子序列 (subsequence)，就是最長共同子字串
。
有多組測資，每組測資有兩行字串 $X, \; Y$，$X, \; Y$ 只由 A T C G 四個字母構成。
針對每一組測資，輸出一行 $X, \; Y$ 的最長共同子字串長度以及任何一組最長共同子字串。
|
|
|
|
雖然我們都知道數據小時，由於有 $O(N^2)$ 大小的表可以協助回溯找解，但當 $N$ 非常大時，就無法儲存這張表。因此，可以採用分治算法找到這一張表，也就是所謂的 Hirschberg’s algorithm，相關的 demo 在此。
時間複雜度為 $O(N \log N)$，空間複雜度為 $O(N)$，平行部分可以採用 fine-grain 設計，那麼就會有不斷建立 thread 的 overhead，但更容易處於負載平衡 (workload balance)。另一種則是在遞迴分治下，拆成好幾個 thread 完成各自部分，這樣比較容易觸發 cache 的性質。
從實作中，fine-grain 比 coarse-grain 好上許多。
|
|
|
|
給兩個字串 $X, \; Y$，在兩個字串中都有出現且最長的子序列 (subsequence)，就是最長共同子字串
。
有多組測資，每組測資有兩行字串 $X, \; Y$，$X, \; Y$ 只由 A T C G 四個字母構成。
針對每一組測資，輸出一行 $X, \; Y$ 的最長共同子字串長度。
|
|
|
|
由於同學在課堂中提及這個應用，然後實作的效能稍微感到懷疑，再加上這一題的難度跟演算法上相當簡單，難的地方在於如何解決 DP 平行。
從遞迴公式來看，
$$\begin{align*} dp[x][y] = \left\{\begin{matrix} dp[x-1][y-1] + 1 & \text{if } A_x = B_x \\ \max(dp[x-1][y],dp[x][y-1]) & \text{otherwise}\\ \end{matrix}\right. \end{align*}$$唯一的解決方案就是把紀錄矩陣旋轉 45 度，並且搭配滾動數組，需要保留三排進行完成遞迴轉移。
然而，在旋轉 45 度後，平行度在每一列是呈現波形，逐漸變大後又逐漸變小，這導致快取效果不是很好，當分配在不同的 CPU 上時，他們之間先前代入的資料可能不是這次所需，因為變大變小的原因，分配的區段不與之前重疊，傳到另一個 CPU 上平行的效率非常低落，若是在數個 core 在同一個 CPU 上，就能不掉出 L3 cache，但平行度也因此受到限制。
在我們實驗主機上，一個 CPU 總共有 6 個 core，加速最多 6 倍。
|
|
感謝 R04922075 古耕竹同學提供相關資訊，將這一題越推越快。
在論文中，他將原先的 LCS 的遞迴公式改變，多一個額外的輔助數組，其輔助數組的空間大小為 $O(|\alpha|\cdot N)$。仍然 $dp[i][j]$ 為字串 $A$ 前 $i$ 個字元與字串 $B$ 前 $j$ 個字元的最常共同子字串長度。藉由輔助數組 $P[c][j]$ 為上一個字串 $c$ 出現在位置 $j$ 之前的位置在哪。
遞迴公式改為 (這裡我們先忽略邊界條件)：
$$dp[x][y] = \max(dp[x-1][y],dp[x-1][P[A[x]][y]-1]+1)$$從最優子結構分析，分成最後 $A[x]$ 是否與 $B[y]$ 匹配，在不匹配的情況下選擇 $dp[x-1][y]$，匹配的情況下選擇 $dp[x-1][P[A[x]][y]-1]+1$。
下述提及的特殊陣列宣告方式，採用 linux 常用的 -std=c99 標準贊助
|
|
這部分由高等編譯器課程獨家贊助 Advanced Compiler Support
由於 OpenMP 有很多 shared memory 存取，導致在平行區塊儘管開了 -O2 優化，很多表達式都要重複計算，沒辦法像一般序列化程式，可以讓編譯器理解到要做 Strength reduction 或者是 Common subexpression elimination，因此由程序員自己將 C 寫得接近組合語言，這樣效能才會達到最好。
因此在遞迴公式中，經常存取二維陣列，假設不會重疊或相同的情況，直接用兩個指針維護，意即在 inner loop 常常呼叫 ... += dp[i][j] ... 的話，改成 ... += dpI[j] ...，就可以減少 i * SIZE2D 的 offset 計算。同理找到一些 loop invariant，如 A[x]，將變數往前提，就能減少 share memory 存取次數。
那為了處理邊界條件，可能會需要一些 branch 完成，這裡採用前處理和失敗指針的方式避開 branch 發生，這樣效能又有小幅度地上升。若在 intel CPU 上，可以透過 intel Parallel Studio XE 2016 下的 Analyzers 中其中一個 VTune Amplifier 調校看出。
這樣還不是極限，甚至可以加入 static __thread 或者利用 #pragma omp threadprivate(var) 進行 copy optimization 來提高資料局部性 (data local locality)，但這會牽涉到 cache size，屬於 machine dependency 的相關優化，加或不加要看機器硬體情況。
|
|
請加速以下程序。
|
|
有多行測資，每組第一行會有兩個整數 $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 下是獨立不受影響的。
|
|