一：GPU 編程技術(shù)的發(fā)展歷程及現(xiàn)狀

1.馮諾依曼計(jì)算機(jī)架構(gòu)的瓶頸

  曾經(jīng)，幾乎所有的處理器都是以馮諾依曼計(jì)算機(jī)架構(gòu)為基礎(chǔ)的。該系統(tǒng)架構(gòu)簡單來說就是處理器從存儲器中不斷取指，解碼，執(zhí)行。

       但如今這種系統(tǒng)架構(gòu)遇到了瓶頸：內(nèi)存的讀寫速度跟不上 CPU 時(shí)鐘頻率。具有此特征的系統(tǒng)被稱為內(nèi)存受限型系統(tǒng)，目前的絕大多數(shù)計(jì)算機(jī)系統(tǒng)都屬于此類型。

       為了解決此問題，傳統(tǒng)解決方案是使用緩存技術(shù)。通過給 CPU 設(shè)立多級緩存，能大大地降低存儲系統(tǒng)的壓力：

       然而隨著緩存容量的增大，使用更大緩存所帶來的收益增速會迅速下降，這也就意味著我們要尋找新的辦法了。

2.對 GPU 編程技術(shù)發(fā)展具有啟發(fā)意義的幾件事

1. 70年代末期，克雷系列超級計(jì)算機(jī)研制成功 (克雷1當(dāng)年耗資800萬美元)。

       此類計(jì)算機(jī)采用若干內(nèi)存條的共享內(nèi)存結(jié)構(gòu)，即這些內(nèi)存條可以與多個(gè)處理器相連接，從而發(fā)展成今天的對稱多處理器系統(tǒng) (SMD)。

       克雷2是向量機(jī) - 一個(gè)操作處理多個(gè)操作數(shù)。

       如今的 GPU 設(shè)備的核心也正是向量處理器。

2. 80年代初期，一家公司設(shè)計(jì)并研制了一種被稱為連接機(jī)的計(jì)算機(jī)系統(tǒng)。

       該系統(tǒng)具有16個(gè) CPU 核，采用的是標(biāo)準(zhǔn)的單指令多數(shù)據(jù) (SIMD) 并行處理。連接機(jī)通過這種設(shè)計(jì)能夠消除多余的訪存操作，并將內(nèi)存讀寫周期變?yōu)樵瓉淼?1/16 。

3. CELL 處理器的發(fā)明

       這類處理器很有意思，其架構(gòu)大致如下圖所示：

       在此結(jié)構(gòu)中，一個(gè) PPC 處理器作為監(jiān)管處理器，與大量的 SPE流處理器相連通，組成了一個(gè)工作流水線。

       對于一個(gè)圖形處理過程來說，某個(gè) SPE 可負(fù)責(zé)提取數(shù)據(jù)，另一個(gè) SPE 負(fù)責(zé)變換，再另一個(gè)負(fù)責(zé)存回。這樣可構(gòu)成一道完完整整的流水線，大大提高了處理速度。

       順便提一句，2010年超級計(jì)算機(jī)排名第三的計(jì)算機(jī)就是基于這種設(shè)計(jì)理念實(shí)現(xiàn)的，占地面積達(dá)560平方米，耗資 1.25 億美元。

3.多點(diǎn)計(jì)算模型

  集群計(jì)算是指通過將多個(gè)性能一般的計(jì)算機(jī)組成一個(gè)運(yùn)算網(wǎng)絡(luò)，達(dá)到高性能計(jì)算的目的。這是一種典型的多點(diǎn)計(jì)算模型。而 GPU 的本質(zhì)，也同樣是多點(diǎn)計(jì)算模型。

其相對于當(dāng)今比較火的Hadoop/Spark集群來說：“點(diǎn)”由單個(gè)計(jì)算機(jī)變成了 單個(gè)SM (流處理器簇)，通過網(wǎng)絡(luò)互連變成了通過顯存互連 (多點(diǎn)計(jì)算模型中點(diǎn)之間的通信永遠(yuǎn)是要考慮的重要問題)。

4.GPU 解決方案

 隨著 CPU "功耗墻" 問題的產(chǎn)生，GPU 解決方案開始正式走上舞臺。

       GPU 特別適合用于并行計(jì)算浮點(diǎn)類型的情況，下圖展示了這種情況下 GPU 和 CPU 計(jì)算能力的差別：

       但這可不能說明 GPU 比 CPU 更好，CPU應(yīng)當(dāng)被淘汰。 上圖的測試是在計(jì)算可完全并行的情況下進(jìn)行的。

       對于邏輯更靈活復(fù)雜的串行程序，GPU 執(zhí)行起來則遠(yuǎn)不如 CPU 高效 (沒有分支預(yù)測等高級機(jī)制)。

       另外，GPU 的應(yīng)用早已不局限于圖像處理。事實(shí)上 CUDA 目前的高端板卡 Tesla 系列就是專門用來進(jìn)行科學(xué)計(jì)算的，它們連 VGA 接口都沒。

5.主流 GPU 編程接口

   1. CUDA

       是英偉達(dá)公司推出的，專門針對 N 卡進(jìn)行 GPU 編程的接口。文檔資料很齊全，幾乎適用于所有 N 卡。

       本專欄講述的 GPU 編程技術(shù)均基于此接口。

       2. Open CL

       開源的 GPU 編程接口，使用范圍最廣，幾乎適用于所有的顯卡。

       但相對 CUDA，其掌握較難一些，建議先學(xué) CUDA，在此基礎(chǔ)上進(jìn)行 Open CL 的學(xué)習(xí)則會非常簡單輕松。

       3. DirectCompute

       微軟開發(fā)出來的 GPU 編程接口。功能很強(qiáng)大，學(xué)習(xí)起來也最為簡單，但只能用于 Windows 系統(tǒng)，在許多高端服務(wù)器都是 UNIX 系統(tǒng)無法使用。

       總結(jié)，這幾種接口各有優(yōu)劣，需要根據(jù)實(shí)際情況選用。但它們使用起來方法非常相近，掌握了其中一種再學(xué)習(xí)其他兩種會很容易。

二：從 GPU 的角度理解并行計(jì)算

1.并行計(jì)算中需要考慮的三個(gè)重要問題

       1. 同步問題

       在操作系統(tǒng)原理的相關(guān)課程中我們學(xué)習(xí)過進(jìn)程間的死鎖問題，以及由于資源共享帶來的臨界資源問題等，這里不做累述。

　　2. 并發(fā)度

       有一些問題屬于 “易并行” 問題：如矩陣乘法。在這類型問題中，各個(gè)運(yùn)算單元輸出的結(jié)果是相互獨(dú)立的，這類問題能夠得到很輕松的解決 (通常甚至調(diào)用幾個(gè)類庫就能搞定問題)。

       然而，若各個(gè)運(yùn)算單元之間有依賴關(guān)系，那問題就復(fù)雜了。在 CUDA 中，塊內(nèi)的通信通過共享內(nèi)存來實(shí)現(xiàn)，而塊間的通信，則只能通過全局內(nèi)存。

       CUDA 并行編程架構(gòu)可以用網(wǎng)格 (GRID) 來形容：一個(gè)網(wǎng)格好比一只軍隊(duì)。網(wǎng)格被分成好多個(gè)塊，這些塊好比軍隊(duì)的每個(gè)部門 (后勤部，指揮部，通信部等)。每個(gè)塊又分成好多個(gè)線程束，這些線程束好比部門內(nèi)部的小分隊(duì)，下圖可幫助理解：

       3. 局部性

       在操作系統(tǒng)原理中，對局部性做過重點(diǎn)介紹，簡單來說就是將之前訪問過的數(shù)據(jù) (時(shí)間局部性) 和之前訪問過的數(shù)據(jù)的附近數(shù)據(jù) (空間局部性) 保存在緩存中。

       在 GPU 編程中，局部性也是非常重要的，這體現(xiàn)在要計(jì)算的數(shù)據(jù)應(yīng)當(dāng)在計(jì)算之前盡可能的一次性的送進(jìn)顯存，在迭代的過程中一定要盡可能減少數(shù)據(jù)在內(nèi)存和顯存之間的傳輸，實(shí)際項(xiàng)目中發(fā)現(xiàn)這點(diǎn)十分重要的。

       對于 GPU 編程來說，需要程序猿自己去管理內(nèi)存，或者換句話來說，自己實(shí)現(xiàn)局部性。

2.并行計(jì)算的兩種類型

       1. 基于任務(wù)的并行處理

       這種并行模式將計(jì)算任務(wù)拆分成若干個(gè)小的但不同的任務(wù)，如有的運(yùn)算單元負(fù)責(zé)取數(shù)，有的運(yùn)算單元負(fù)責(zé)計(jì)算，有的負(fù)責(zé)...... 這樣一個(gè)大的任務(wù)可以組成一道流水線。

       需要注意的是流水線的效率瓶頸在于其中效率最低的那個(gè)計(jì)算單元。

　　2. 基于數(shù)據(jù)的并行處理

       這種并行模式將數(shù)據(jù)分解為多個(gè)部分，讓多個(gè)運(yùn)算單元分別去計(jì)算這些小塊的數(shù)據(jù)，最后再將其匯總起來。

       一般來說，CPU 的多線程編程偏向于第一種并行模式，GPU 并行編程模式則偏向于第二種。

3.常見的并行優(yōu)化對象

       1. 循環(huán)

       這也是最常見的一種模式，讓每個(gè)線程處理循環(huán)中的一個(gè)或一組數(shù)據(jù)。

       這種類型的優(yōu)化一定要小心各個(gè)運(yùn)算單元，以及每個(gè)運(yùn)算單元何其自身上一次迭代結(jié)果的依賴性。

       2. 派生/匯集模式

       該模式下大多數(shù)是串行代碼，但代碼中的某一段可以并行處理。

       典型的情況就是某個(gè)輸入隊(duì)列當(dāng)串行處理到某個(gè)時(shí)刻，需要對其中不同部分進(jìn)行不同處理，這樣就可以劃分成多個(gè)計(jì)算單元對改隊(duì)列進(jìn)行處理 (也即派生)，最后再將其匯總 (也即匯集)。

       這種模式常用于并發(fā)事件事先不定的情況，具有 “動態(tài)并行性”。

       3. 分條/分塊模式

       對于特別龐大的數(shù)據(jù) (如氣候模型)，可以將數(shù)據(jù)分為過個(gè)塊來進(jìn)行并行計(jì)算。

       4. 分而治之

       絕大多數(shù)的遞歸算法，比如快速排序，都可以轉(zhuǎn)換為迭代模型，而迭代模型又能映射到 GPU 編程模型上。

       特別說明：雖然費(fèi)米架構(gòu)和開普勒架構(gòu)的 GPU 都支持緩沖棧，能夠直接實(shí)現(xiàn)遞歸模型到 GPU 并行模型的轉(zhuǎn)換。但為了程序的效率，在開發(fā)時(shí)間允許的情況下，我們最好還是先將其轉(zhuǎn)換為迭代模型。

GPU 并行編程的核心在于線程，一個(gè)線程就是程序中的一個(gè)單一指令流，一個(gè)個(gè)線程組合在一起就構(gòu)成了并行計(jì)算網(wǎng)格，成為了并行的程序，下圖展示了多核 CPU 與 GPU 的計(jì)算網(wǎng)格：

我們前面已經(jīng)大概的介紹了CUDA執(zhí)行模型的大概過程，包括線程網(wǎng)格，線程束，線程間的關(guān)系，以及硬件的大概結(jié)構(gòu)，例如SM的大概結(jié)構(gòu)，而對于硬件來說，CUDA執(zhí)行的實(shí)質(zhì)是線程束的執(zhí)行，因?yàn)橛布静恢烂總€(gè)塊誰是誰，也不知道先后順序，硬件(SM)只知道按照機(jī)器碼跑，而給他什么，先后順序，這個(gè)就是硬件功能設(shè)計(jì)的直接體現(xiàn)了。
從外表來看，CUDA執(zhí)行所有的線程，并行的，沒有先后次序的，但實(shí)際上硬件資源是有限的，不可能同時(shí)執(zhí)行百萬個(gè)線程，所以從硬件角度來看，物理層面上執(zhí)行的也只是線程的一部分，而每次執(zhí)行的這一部分，就是我們前面提到的線程束。

線程束和線程塊

線程束是SM中基本的執(zhí)行單元，當(dāng)一個(gè)網(wǎng)格被啟動（網(wǎng)格被啟動，等價(jià)于一個(gè)內(nèi)核被啟動，每個(gè)內(nèi)核對應(yīng)于自己的網(wǎng)格），網(wǎng)格中包含線程塊，線程塊被分配到某一個(gè)SM上以后，將分為多個(gè)線程束，每個(gè)線程束一般是32個(gè)線程（目前的GPU都是32個(gè)線程，但不保證未來還是32個(gè)）在一個(gè)線程束中，所有線程按照單指令多線程SIMT的方式執(zhí)行，每一步執(zhí)行相同的指令，但是處理的數(shù)據(jù)為私有的數(shù)據(jù)，下圖反應(yīng)的就是邏輯，實(shí)際，和硬件的圖形化

線程塊是個(gè)邏輯產(chǎn)物，因?yàn)樵谟?jì)算機(jī)里，內(nèi)存總是一維線性存在的，所以執(zhí)行起來也是一維的訪問線程塊中的線程，但是我們在寫程序的時(shí)候卻可以以二維三維的方式進(jìn)行，原因是方便我們寫程序，比如處理圖像或者三維的數(shù)據(jù)，三維塊就會變得很直接，很方便。
在塊中，每個(gè)線程有唯一的編號（可能是個(gè)三維的編號），threadIdx。
網(wǎng)格中，每個(gè)線程塊也有唯一的編號(可能是個(gè)三維的編號)，blockIdx
那么每個(gè)線程就有在網(wǎng)格中的唯一編號。
當(dāng)一個(gè)線程塊中有128個(gè)線程的時(shí)候，其分配到SM上執(zhí)行時(shí)，會分成4個(gè)塊：

warp0: thread  0,........thread31
warp1: thread 32,........thread63
warp2: thread 64,........thread95
warp3: thread 96,........thread127

   該圖表示，計(jì)算網(wǎng)格由多個(gè)流處理器構(gòu)成，每個(gè)流處理器又包含 n 多塊。

      下面進(jìn)一步對 GPU 計(jì)算網(wǎng)格中的一些概念做細(xì)致分析。

      1. 線程

      線程是 GPU 運(yùn)算中的最小執(zhí)行單元，線程能夠完成一個(gè)最小的邏輯意義操作。

      2. 線程束

      線程束是 GPU 中的基本執(zhí)行單元。GPU 是一組 SIMD 處理器的集合，因此每個(gè)線程束中的線程是同時(shí)執(zhí)行的。這個(gè)概念是為了隱藏對顯存進(jìn)行讀寫帶來的延遲所引入的。

      目前英偉達(dá)公司的顯卡此值為 32，不可改動，也不應(yīng)該對其進(jìn)行改動。

      3. 線程塊

      一個(gè)線程塊包含多個(gè)線程束，在一個(gè)線程塊內(nèi)的所有線程，都可以使用共享內(nèi)存來進(jìn)行通信、同步。但一個(gè)線程塊能擁有的最大線程/線程束，和顯卡型號有關(guān)。

      4. 流多處理器

      流多處理器就相當(dāng)于 CPU 中的核，負(fù)責(zé)線程束的執(zhí)行。同一時(shí)刻只能有一個(gè)線程束執(zhí)行。

      5. 流處理器

      流處理器只負(fù)責(zé)執(zhí)行線程，結(jié)構(gòu)相對簡單。

GPU 和 CPU 在并行計(jì)算方面的不同

      1. 任務(wù)數(shù)量

      CPU 適合比較少量的任務(wù)，而 GPU 則適合做大量的任務(wù)。

      2. 任務(wù)復(fù)雜度

      CPU 適合邏輯比較復(fù)雜的任務(wù)，而 GPU 則適合處理邏輯上相對簡單的任務(wù) (可用比較少的語句描述)。

      3. 線程支持方式

      由于 CPU 中線程的寄存器組是公用的，因此CPU 在切換線程的時(shí)候，會將線程的寄存器內(nèi)容保存在 RAM 中，當(dāng)線程再次啟動的時(shí)候則會從 RAM 中恢復(fù)數(shù)據(jù)到寄存器。

      而 GPU 中的各個(gè)線程則各自擁有其自身的寄存器組，因此其切換速度會快上不少。

      當(dāng)然，對于單個(gè)的線程處理能力來說，CPU 更強(qiáng)。

      4. 處理器分配原則

      CPU 一般是基于時(shí)間片輪轉(zhuǎn)調(diào)度原則，每個(gè)線程固定地執(zhí)行單個(gè)時(shí)間片；而 GPU 的策略則是在線程阻塞的時(shí)候迅速換入換出。

      5. 數(shù)據(jù)吞吐量

      GPU 中的每個(gè)流處理器就相當(dāng)于一個(gè) CPU 核，一個(gè) GPU 一般具有 16 個(gè)流處理器，而且每個(gè)流處理器一次能計(jì)算 32 個(gè)數(shù)。

CUDA是用于GPU計(jì)算的開發(fā)環(huán)境，它是一個(gè)全新的軟硬件架構(gòu)，可以將GPU視為一個(gè)并行數(shù)據(jù)計(jì)算的設(shè)備，對所進(jìn)行的計(jì)算進(jìn)行分配和管理。在CUDA的架構(gòu)中，這些計(jì)算不再像過去所謂的GPGPU架構(gòu)那樣必須將計(jì)算映射到圖形API(OpenGL和Direct 3D)中，因此對于開發(fā)者來說，CUDA的開發(fā)門檻大大降低了。CUDA的GPU編程語言基于標(biāo)準(zhǔn)的C語言，因此任何有C語言基礎(chǔ)的用戶都很容易地開發(fā)CUDA的應(yīng)用程序。

與CUDA相關(guān)的幾個(gè)概念：thread，block，grid，warp，sp，sm。

sp: 最基本的處理單元，streaming processor  最后具體的指令和任務(wù)都是在sp上處理的。GPU進(jìn)行并行計(jì)算，也就是很多個(gè)sp同時(shí)做處理

sm:多個(gè)sp加上其他的一些資源組成一個(gè)sm,  streaming multiprocessor. 其他資源也就是存儲資源，共享內(nèi)存，寄儲器等。

warp:GPU執(zhí)行程序時(shí)的調(diào)度單位，目前cuda的warp的大小為32，同在一個(gè)warp的線程，以不同數(shù)據(jù)資源執(zhí)行相同的指令。

grid、block、thread：在利用cuda進(jìn)行編程時(shí)，一個(gè)grid分為多個(gè)block，而一個(gè)block分為多個(gè)thread.其中任務(wù)劃分到是否影響最后的執(zhí)行效果。劃分的依據(jù)是任務(wù)特性和GPU本身的硬件特性。