原先譯-原文CUDA程序性能評估模型與深度優(yōu)化研更改篇

SKE:CUDA平臺下單個kernel函數(shù)執(zhí)行時間分析模型摘要:GPGPU由于其具有極高計算性能，相對廉價的成本，較低的功耗等優(yōu)點，在越來越多的領(lǐng)域得到了廣泛的應(yīng)用。從移動終端到超級計算機，使用GPU加速浮點運算已經(jīng)成為了一種趨勢。本文詳細(xì)分析了GPU上各指令的執(zhí)行周期以及多級存儲器特性，并分別建立計算時間（ComputationTime）和通信時間（CommunicationTime）的評估模型，討論了活動線程束（activewarp）和活動線程塊（activeblock）之間在執(zhí)行指令執(zhí)行過程中如何互相隱藏延遲。并在此基礎(chǔ)上，建立了基于CUDA平臺的針對單個kernel函數(shù)進(jìn)行全面評估的數(shù)學(xué)模型SKE（SingleKernelEstimate）。SKE是以kernel函數(shù)執(zhí)行時間ExecutionTime為目標(biāo)函數(shù)，以GPU硬件計算能力限制為約束條件的非線性規(guī)劃函數(shù)。該模型有以下特點：1）適用于NVIDIA公司不同時期的多種GPU架構(gòu)；2）模型中的關(guān)鍵輸入?yún)?shù)只有9個，因此與文獻(xiàn)[19]中的Kernel數(shù)學(xué)評估模型相比，該模型更簡潔；3）模型中的8個限定條件使得程序員能更清晰的了解硬件設(shè)備對kernel函數(shù)執(zhí)行時間的影響；4）預(yù)估的核函數(shù)時間更精確，其最大誤差不超過20%。1引言近來，CPU發(fā)展顯露疲態(tài)，單核計算的頻率提升遇到了瓶頸，多核的效率提升也遠(yuǎn)低于預(yù)期——同主頻的八核的計算能力甚至和四核相仿。而與之相對的是，GPU浮點計算能力獲得了井噴式提高，NVIDIA公司的GTX690擁有3072個流處理器，核心頻率為1019MHz，單精度浮點運算能力已經(jīng)達(dá)到了9.39Tflops，超過了同期CPUI7處理器的150倍！因此越來越多的超級計算機，都將GPU做為浮點運算的加速器。而隨著大數(shù)據(jù)時代的來臨，我們對高性能計算的處理能力需求越來越大。GPU具有極高的計算性能和相對廉價的成本。并且它以超過摩爾定律的速度更新硬件，成為實時海量數(shù)據(jù)流處理的重要解決方案。越來越多的計算密集型程序都選擇GPU進(jìn)行并行加速。然而，GPU在串行運算上的邏輯處理能力就比CPU弱很多。比如整數(shù)除和模運算，雙精度的三角函數(shù)運算，控制流指令，還有訪存指令等等，它們在GPU上的時間開銷都非常昂貴，遠(yuǎn)遠(yuǎn)超過在CPU上的時間開銷[6]。因此，我們把一個程序中邏輯控制指令密集，程序分支多，訪存頻繁的部分交給CPU來串行執(zhí)行，而把計算密集型、高度并行化的部分交給GPU來并行執(zhí)行，從而有效的降低程序運行時間[1]。如何確定一個給定應(yīng)用程序的哪部分放入GPU，哪部分留在CPU會得到最高的加速比；放入GPU中運行的部分，又該如何劃分線程粒度使程序的性能達(dá)到最優(yōu)；以及如何規(guī)劃每個SM的活動線程塊數(shù)量，使程序執(zhí)行時間最短。這是每個想通過GPU加速運算的程序都會遇到的問題。并行算法的分析與設(shè)計成為了解決上述問題的關(guān)鍵點。針對并行算法的設(shè)計與分析，有幾個比較經(jīng)典的模型，如1978年就提出的PRAM模型[12]，和90年代提出的網(wǎng)絡(luò)模型[13]，Log-P模型[14]，以及在PRAM模型上改進(jìn)的QRQW模型。雖然這些模型曾在我們進(jìn)行并行程序設(shè)計與分析時提供過許多幫助。但是他們已經(jīng)遠(yuǎn)遠(yuǎn)無法滿足現(xiàn)在GPU硬件架構(gòu)下的設(shè)計需求。因為GPU上不同特性的多級存儲器，眾核體系架構(gòu)以及多種不同功能的處理單元（ALU/DPU/SFU），都讓原本的分析模型漸漸失去了優(yōu)勢。我們希望能建立一個基于CUDA平臺的針對單個kernel函數(shù)性能的評估模型。并且該模型能滿足絕大部分程序和設(shè)備的要求，使得程序員深入了解程序與硬件之間的聯(lián)系，在編程前就能選擇最佳的解決方案，設(shè)計出最優(yōu)的線程和線程塊劃分方法，從而減少CUDA程序的開發(fā)周期。同時充分發(fā)揮設(shè)備固有屬性的優(yōu)勢，使得cuda程序性能達(dá)到最優(yōu)。2最近的研究自從2007年，NVIDIA公司率先提出了GPGPU(GeneralPurposeGPU)的概念后，很多國內(nèi)外學(xué)者從事了針對GPU并行架構(gòu)分析模型的研究。其研究主要分為兩個方面：一部分研究專注于GPU存儲空間的分析與優(yōu)化。文獻(xiàn)[17]分析了NVIDIA公司Tesla架構(gòu)下多級存儲器的特性，而且我用此研究對H264幀內(nèi)預(yù)測程序進(jìn)行了優(yōu)化，達(dá)到了非常理想的效果；文獻(xiàn)[18]的作者致力于多GPU下的存儲空間優(yōu)化，分析了CPU與GPU間以及不同GPU之間的通信時間；文獻(xiàn)[10]評估了cuda架構(gòu)下共享內(nèi)存的性能，并和其他3種并行編程模型架構(gòu)：OpenMP，IntelTBB和IntelArBB進(jìn)行了比較，發(fā)現(xiàn)OpenMP和IntelTBB性能較低，IntelArBB則和cuda相當(dāng)（但偏低）。另一部分研究工作與本文相似，對GPU并行程序建立分析模型。其中文獻(xiàn)[19]建立了通過程序自動估計kernel函數(shù)執(zhí)行時間的模型，它把整個GPU執(zhí)行分成兩部分：計算線程束CWP(ComputationWarpParallelism)和存取線程束MWP(MemoryWarpParallelism)，并詳細(xì)分析了CWP和MWP各自的耗時，以及它們之間能相互隱藏的時間，但是沒有考慮不同功能的計算單元之間相互隱藏的延遲，而且計算過程過于復(fù)雜，需要輸入的參數(shù)達(dá)到21個之多。文獻(xiàn)[20]針對特定的迭代循環(huán)程序建立了分析模型。文獻(xiàn)[21]提出的模型不夠細(xì)致，也沒有把同步時間納入計算。文獻(xiàn)[22]同樣把計算模型分為通信和計算兩部分，并以模型為依據(jù)優(yōu)化了基于滑動窗口的快速小波變換CUDA程序，使得小波變換能根據(jù)問題規(guī)模以及硬件設(shè)備的架構(gòu)，提供較優(yōu)的線程塊劃分。以上4個評估模型，還兩個共同的缺陷：1）只適應(yīng)最早的Tesla架構(gòu)，2)因為沒有考慮GPU上不同功能處理單元（ALU/DPU/SFU）以及存取單元互相間的隱藏延遲，所以對執(zhí)行時間、通信時間和隱藏延遲時間的評估不夠準(zhǔn)確。本文旨在建立一個適用范圍更廣——包括Tesla架構(gòu)、Fermi架構(gòu)和Kepler架構(gòu)，描述更簡潔明了，計算更簡單精確的GPUKernel函數(shù)分析模型SKE。3SKE對于一個CUDAkernel函數(shù)來說，從調(diào)用它到返回其結(jié)果值所需的執(zhí)行時間（ExecutionTime）Tn包括3個方面：1）GPU計算時間（ComputationTime）Te；2）通信時間（CommunicationTime）Tc；3）線程同步時間（SynchronizationTime）Ts。 (1)3.1計算時間——TeCUDA中的kernel函數(shù)是以block為單位執(zhí)行，一個block必須被分配到一個SM中，但是一個SM中同一時刻可以有多個活動線程塊（activeblock）在等待執(zhí)行。假設(shè)當(dāng)前GPU中執(zhí)行的kernel函數(shù)分配的block個數(shù)為b，GPU含有的SM個數(shù)為S，那么每個SM中的活動線程塊個數(shù)nb為。CUDA采用的是SIMT（SingleInstructionMultipleThread，單指令多線程）執(zhí)行模型[6]，假設(shè)當(dāng)前kernel函數(shù)含有指令數(shù)n，調(diào)用時每個block內(nèi)含有t個線程，GPU的時鐘周期為T，每個SM中標(biāo)準(zhǔn)處理單元SP的數(shù)量為P，那么SM執(zhí)行當(dāng)前block的時間為。綜上所述，計算時間 （2）因為不同的處理指令和處理精度在NVIDIAGPU中所需的時鐘周期數(shù)也不同，所以簡單的用公式（2）來估算指令執(zhí)行時間是不準(zhǔn)確的，具體情況請參看表1：表1不同CUDA處理指令和處理精度執(zhí)行所需時鐘周期數(shù)類別所需時鐘周期指令14加法，乘法，比較運算，位運算，類型轉(zhuǎn)換，同步指令21632bit整數(shù)乘法，求倒，倒數(shù)平方根，對數(shù)332平方根，三角函數(shù)，指數(shù)436float除法5500三角運算，int除法，int求模，控制流指令假設(shè)在我們研究的單個kernel函數(shù)中含有QUOTEnini個i類指令，并且第i類指令所需的時鐘周期數(shù)為pi，則Kernel函數(shù)的執(zhí)行時間是每類指令執(zhí)行時間的和，即QUOTE （3）3.2通信時間——Tc3.2.1GPU的浮點計算能力已經(jīng)達(dá)到了Tflops級，但是GPU存儲器的帶寬只有其浮點計算能力1/100，這使得通信時間成為了GPU通信的最大瓶頸。因此NVIDIA公司在GPU上設(shè)計了性能多樣的多級存儲器。在cuda程序中如何利用這些存儲器是影響cuda程序獲得更高加速比的關(guān)鍵。圖1GPU的存儲器結(jié)構(gòu)如圖1所示，在顯存上的存儲單元分為片內(nèi)存儲器——Sharedmemory和registers；和片外存儲器——Globalmemory、Localmemory、Constantmemory和Texturememory。片內(nèi)存儲器僅有device端能夠?qū)ζ溥M(jìn)行讀寫，并且所需時鐘周期很小，它作為GPU的高速存儲器而存在的，但是它們的存儲空間都普遍較小。片外存儲器中，Localmemory和Texturememory都是Globalmemory中分配的特殊空間；host端能對Globalmemory、Constantmemory和Texturememory進(jìn)行讀寫，host與device間的通信都要通過它們。它們的空間達(dá)到4GB，但是除了Constantmemory以外訪存周期都很長。以下簡單介紹下各存儲器特性：1）Registers：最快的存儲器，訪存只要一個時鐘周期。每個SM上有65536個32位registersfiles，即256KB，每個線程申請的私有變量都會存儲在其中。如果線程的私有變量大小超過了每個線程占有的registersfiles，那么多出來的部分就會被放入Localmemory中。2）Localmemory：在Globalmemory中為每個線程分配的16KB空間，訪存速度和Globalmemory相同，需要400-600個時鐘周期。使用Localmemory會極大的降低cuda程序的執(zhí)行效率。3）Sharedmemory：在不發(fā)生bankconflict情況下，讀取速度與Registers相仿，每個SM只有48KB大小的sharedmemory。同一block內(nèi)的線程可以通過它互相通信。sharedmemory同時還保存著加載kernel函數(shù)時傳遞過來的參數(shù)。4）Constantmemory：它是片外存儲器中速度最快的，并且整個GPU所有線程都可對其進(jìn)行訪問，讀取速度也不受合并訪存條件影響，但是它的大小僅有48KB。5）Globalmemory：訪存所需時鐘周期最大400-600，如果數(shù)據(jù)滿足合并訪存條件，速度可以提高8倍。6）Texturememory：對device來說是只讀的，由于其在片內(nèi)有2層cache，所以即使不滿足合并訪存條件，訪存所需的時鐘周期也可以減少到250-350。表2各級存儲器訪存周期，以GTX680為例NoNameRead/writeSizeLatency(cycles)1registersDeviceR&W6553532-bit12SharedmemoryDeviceR&W48KB/SM13ConstantmemoryDeviceR&WHostR&W48KB44Globalmemory(coalesced)DeviceR&WHostR&W4G62.55TexturememoryDeviceR&WHostR&W4G3006LocalmemoryDeviceR&W16KB/Thread5007GlobalmemoryDeviceR&WHostR&W4G5003.2.2估算公式從表2可知，按訪存速度對各級存儲器進(jìn)行排序，1)registers，2)sharedmemory，3)constantmemory，4)滿足合并訪存條件的globalmemory，5)texturememory，6)localmemory，7)globalmemory。假設(shè)第i類存儲器上的數(shù)據(jù)大小為Di，訪問次數(shù)為mi，訪存周期為qi，每個SM中載入存儲單元(LD/ST)的個數(shù)為L。那么GPU內(nèi)部通信時間 (4)其中l(wèi)a為訪存延遲。假設(shè)GPU位寬為Bit，則字長為Bit/8個字節(jié)，若時鐘周期為T，那么我們可以近似的認(rèn)為 (5)其中表示線程訪存沖突的系數(shù)，在沒有訪存沖突的情況下，默認(rèn)=1。綜合公式(4)和（5），則GPU內(nèi)部通信時間為 (6)3.3同步時間同步時間較為復(fù)雜，我們將一個kernel函數(shù)中執(zhí)行時間最長的線程當(dāng)成關(guān)鍵線程，以它的計算時間作為整個kernel函數(shù)的計算時間。同步指令_syncthreads將占用4個時鐘周期來為每個warp發(fā)出指令[6]。那么此時，該kernel函數(shù)內(nèi)執(zhí)行k次同步所需的時間 (7)其中為同步系數(shù)，如果所有線程都運行在關(guān)鍵路徑上，那么=1。關(guān)鍵路徑是指kernel函數(shù)中執(zhí)行時間最長的線程的執(zhí)行路徑。3.4隱藏延遲在NVIDIA的顯卡架構(gòu)中，每個SM都由兩種特殊類型的運算單元DPU（DoublePrecisionUnit）和SFU（SpecialFunctionUnit）組成，并提供了一種雙發(fā)射并行（dualissue）的功能，它能讓不同種類的功能單元能夠同時運行，在一個執(zhí)行單元工作時，其他的執(zhí)行單元也能執(zhí)行其他的warp指令。因此多個activewarp能夠隱藏SM的流水線延遲。當(dāng)SM上擁有多個activeblock時，它們是被順序執(zhí)行的，前后兩個活動塊的通信和計算可以異步執(zhí)行，當(dāng)一個block進(jìn)行同步或者訪問顯存等高延遲操作時，另一個block就可以占用GPU的執(zhí)行資源[6]。這時，多個activeblock之間就可以隱藏訪存延遲。隨著顯卡硬件技術(shù)的發(fā)展，SM內(nèi)的并行度得到了進(jìn)一步提高。在Fermi架構(gòu)中，SM內(nèi)含有兩個warp調(diào)度器，兩個指令調(diào)度單元，4個SFU，16個存取單元（LD/ST）和32個SP；而最新的Kepler架構(gòu)中，每個SM（又被稱為SMX）又進(jìn)一步引入了4個warp調(diào)度器，8個指令調(diào)度單元，32個更強的SFU,64個DPU，以及192個SP以及32個載入/存儲單元(LD/ST)。由于Kepler架構(gòu)中每個warp調(diào)度器都有兩個指令調(diào)度單元，所以在每個時鐘周期內(nèi)，每個warp可以調(diào)度兩個獨立指令[10]。以上這些架構(gòu)的改變使得activewarp以及activeblock之間隱藏延遲的能力進(jìn)一步增強。雖然GPU架構(gòu)的每次改變都在某種意義上提高了GPU硬件的性能，但是不同的架構(gòu)具有不同的計算能力，如表3表3.Tesla、Fermi和Kepler架構(gòu)的不同計算能力參數(shù)TeslaGT200FermiGF100KeplerGK104Computingability1.02.03.0DeviceGTX280GTX480GTX670S(numberofSM)30157P(numberofSP/SM)832192WarpMaxInSM244864BlockMaxInSM8816RegistersFilesInSM163843276865536Registers/Thread1246363ThreadMaxInBlock51210241024ThreadMaxInSM76815362048從表3可知，當(dāng)前SM上activewarp和activeblock的數(shù)目和設(shè)備的計算能力緊密相關(guān),其中，activeblock的數(shù)目，但是nb受到了許多條件的限制，下一小節(jié)3.5中將會詳細(xì)介紹。假設(shè)每個warp包含的線程數(shù)量為W（目前所有設(shè)備中W都為32），那么activewarp的數(shù)目nw等于每個SM上activeblock的數(shù)量nb乘以每個塊內(nèi)warp的數(shù)量，即。activewarp隱藏的是SP執(zhí)行時的流水線延遲，而activeblock隱藏的是通信延遲。但是當(dāng)它們?yōu)?時，能隱藏的延遲為0；而隨著activewarp和activeblock的數(shù)目增大，所能額外隱藏的延遲逐步減少，因此我們把這部分能隱藏的時間用公式(8)來模擬 (8)由于不同的kernel函數(shù)執(zhí)行時所調(diào)用的ALU,SFU,DPU和LD/ST的順序和次數(shù)不同，而且不同設(shè)備內(nèi)部架構(gòu)和warp排程器數(shù)量等，都不盡相同，因此我們很難用一個給定的參數(shù)rw，rb來衡量所有kernel函數(shù)的隱藏延遲。我們通過實驗測試了延遲時間對整體執(zhí)行時間的影響，并粗略的估計了QUOTErwrw和QUOTErbrb的值:rw=0.95，rb=0.96。3.5性能評估模型本文中，我們用函數(shù)的執(zhí)行時間作為評估函數(shù)性能的依據(jù)。通常情況下，函數(shù)的執(zhí)行時間越短，函數(shù)的性能越好。綜合公式（1）(3)(6)(7)(8)，得kernel函數(shù)的性能評估模型為 (9)公式(9)就是我們構(gòu)建的kernel函數(shù)執(zhí)行時間的評估模型。同時該公式也是kernel函數(shù)執(zhí)行時間的目標(biāo)函數(shù)，目標(biāo)函數(shù)的約束條件可以從以下幾個方面進(jìn)行討論：1)每個block含有的線程必須小于塊內(nèi)線程數(shù)的最大值ThreadMaxInBlock。在Fermi和kepler架構(gòu)中，ThreadMaxInBlock分別等于512和2048。 (10)2）每個SM中分配的線程數(shù)必須小于SM內(nèi)線程數(shù)的最大值。假設(shè)每個SM中分配到的線程數(shù)為tsm，每個SM中全部活動線程塊中總的線程數(shù)的最大值為ThreadMaxInSM， (11)其中txQUOTEnbnb表示SM中所有活動線程塊中含有的線程總數(shù)。3）SM中分配的每個線程的寄存器內(nèi)存QUOTEM1M1要小于當(dāng)前GPU所能允許的寄存器值。寄存器registers是GPU片內(nèi)高速緩存器，其基本單元是寄存器文件registersfile，每個寄存器文件大小為32bit。在kepler架構(gòu)中，registersfile數(shù)目為65535個。 (12)4)SM中分配的每個線程的共享內(nèi)存QUOTEM2M2要小于當(dāng)前GPU所能允許的共享內(nèi)存值。在kepler架構(gòu)中，共享內(nèi)存sharedmemory與二級緩存共用64KB的空間，其大小可在16KB到48KB之間調(diào)整。其中MaxSharedMemory表示GPU線程塊中可用的最大共享內(nèi)存，則每個線程能分配到的共享內(nèi)存 (13)從公式(11)~(13)可得關(guān)于活動線程塊的限定條件： (14)如果nb沒有達(dá)到上限BlockMaxInSM，那么隱藏延遲的效果就不是最好的。5）cuda程序所用的只讀存儲器的大小QUOTEM3M3要小于GPU所允許的最大只讀存儲器的大小。在kepler架構(gòu)中，常數(shù)存儲器constantmemory的最大值MaxConstantMemory為48KB (15)6）cuda程序所占用的其他存儲單元如M4~M7都在片外，它們的和Ms必須小于顯存的大小MaxGlobalMemory。 (16)將公式(9)~(16)聯(lián)立起來，再加入表3的部分限定條件，就是我們所需的非線性規(guī)劃函數(shù)minTn和它的約束條件：3.6目標(biāo)函數(shù)分析目標(biāo)函數(shù)中，時鐘周期T，流多處理器SM的個數(shù)S，每個SM中標(biāo)準(zhǔn)處理器SP的個數(shù)P，LD/ST個數(shù)L，線程束內(nèi)含有線程的數(shù)量W，對于指定的設(shè)備來說，這些都是固定值。除了這些設(shè)備參數(shù)以外，核函數(shù)整體計算時間還受3個要素的影響：1）線程塊的劃分（t，b）；2）線程內(nèi)的計算時間；3）線程內(nèi)的通信時間。其中，線程內(nèi)的計算時間和通信時間相對獨立，根據(jù)表1和表2，我們可以有針對性的對其進(jìn)行優(yōu)化：表1和表2都是按時鐘周期升序排列的，在cuda程序的編寫過程中盡量選擇需求時鐘周期較少的指令和存儲器，具體優(yōu)化步驟可以參考我的上一篇論文[17]，在本文就不多做論述了。除了這兩部分以外，線程塊的劃分不僅影響了每個SM上標(biāo)準(zhǔn)處理器的利用率，而且還影響了活動線程束和活動線程塊的個數(shù)，而活動線程束和活動線程塊的個數(shù)又影響到線程指令之間的隱藏延遲。所以，線程塊的劃分是影響kernel函數(shù)執(zhí)行時間的重要因素。3.7不同線程塊劃分對執(zhí)行時間產(chǎn)生的影響我們在opencv常用的圖像處理函數(shù)中選出3個較為簡單的核函數(shù)進(jìn)行實驗，它們分別是縮放、顏色轉(zhuǎn)換和高斯平滑，處理的對象為同一視頻流中的1000幀的圖像，其分辨率為480x270，存儲格式為RGB，運行的設(shè)備是GTX670。圖2不同線程塊設(shè)計下三個函數(shù)的平均執(zhí)行時間（ms）實驗結(jié)果如圖2和表4所示，當(dāng)每個塊內(nèi)的線程數(shù)量t為32x4時，執(zhí)行時間取得最小值，32x4到32x16之間平均執(zhí)行時間相差不大，但其中32x7，32x11，32x13，32x15為局部高點，32x12為局部低點。表4.不同block維度下三個函數(shù)的平均執(zhí)行時間（ms）3.8SKE預(yù)測的執(zhí)行時間我們通過SKE分別計算出三個核函數(shù)在不同線程塊劃分下的執(zhí)行時間，與上一小節(jié)的實際時間進(jìn)行對比，以此來驗證SKE的準(zhǔn)確性。首先，先假定訪存沖突系數(shù)=1，同步次數(shù)k=0，隱藏延遲的系數(shù)rw=0.95，rb=0.96。接著，確定以GTX670為實驗設(shè)備，其設(shè)備參數(shù)為T=10-9s，S=7，P=192，L=32，W=32。然后，按照不同的線程塊劃分(t，b)，在約束條件下算出活動線程束和活動線程塊的個數(shù)，其結(jié)果如表5所示。表5.不同block維度下活動線程束與活動線程塊個數(shù)，以及評估模型中其他中間變量的值核函數(shù)resize內(nèi)執(zhí)行了16次整數(shù)乘法，12次加法，3次比較，訪問了6次全局內(nèi)存，而且不滿足合并訪存條件。所以=16*16+12*4+3*4=316，=6*500=3000。最終計算出的時間與實際時間對比如表6和圖3a.表6.不同block維度下三個函數(shù)實際執(zhí)行時間與模型計算出的執(zhí)行時間對比圖3a.不同block維度下函數(shù)resize實際執(zhí)行時間（藍(lán)線）與評估模型計算出的時間（紅線）對比圖3b.不同block維度下函數(shù)Rgb2Gray實際執(zhí)行時間（藍(lán)線）與評估模型計算出的時間（紅線）對比圖3c.不同block維度下函數(shù)Smooth實際執(zhí)行時間（藍(lán)線）與評估模型計算出的時間（紅線）對比同樣的，對rbgTogray函數(shù)來說=244，=6*500=2000;而對高斯平滑函數(shù)來說=960，=6000。他們用SKE計算出的執(zhí)行時間如圖3b，與圖3c。計算出的執(zhí)行時間在塊內(nèi)線程數(shù)量t較小時，如32x1,32x2，產(chǎn)生了較大的誤差，這是由于在Fermi架構(gòu)和Kepler架構(gòu)中，從Tesla架構(gòu)的線程級并行TLP，改進(jìn)為指令級并行ILP。每個SM中有多個warp調(diào)度器，當(dāng)塊內(nèi)線程數(shù)t小于SM內(nèi)部標(biāo)準(zhǔn)處理器的個數(shù)P的1/2時，warp調(diào)度器會發(fā)射指令讓更多的block同時在同一個SM中內(nèi)進(jìn)行運算。這時活動線程束和活動線程塊能隱藏更多的延遲。這時有兩種方法修正這種誤差：1）將延遲系數(shù)rw和rb調(diào)整為0.92左右。2）將模型中部分修正為，這是以活動線程束為變量，來計算執(zhí)行時間，其中表示所有SM內(nèi)的活動線程執(zhí)行完畢需要調(diào)用SP的次數(shù)，表示所有線程塊需要分多少次執(zhí)行完畢。如果采用這種方法，活動線程束與活動線程塊的影響已經(jīng)很大部分被計入公式，此時需要將延遲系數(shù)rw和rb調(diào)高到0.99。另外訪問全局內(nèi)存和條件控制指令等等，所需的時鐘周期數(shù)都并不是十分準(zhǔn)確，這些都對最后的評估結(jié)果產(chǎn)生了影響，使得預(yù)估的計算時間與實際執(zhí)行時間平均誤差超過24%。但是，評估公式非常準(zhǔn)確的模擬出了不同線程劃分下執(zhí)行時間的變化趨勢，包括32x4時的最小值，以及32x11，32x13時的局部高點和32x12的局部低點。4SKE的應(yīng)用下面以我們的曾經(jīng)的一個項目為例，討論SKE應(yīng)用到開發(fā)過程中的實用性。首先，項目要求單個計算機節(jié)點要實現(xiàn)硬解碼3000個H264視頻流，其分辨率為352X288，輸出制式為YV12/NV12，GPU要負(fù)責(zé)解碼過程中除熵解碼外的幾乎所有步驟。其中，H264解碼中的幀內(nèi)預(yù)測由于其中含有多種預(yù)測模式，有可能適合多種并行粒度的解決方案，我們對其進(jìn)行主要分析。4.1幀內(nèi)預(yù)測的串行代碼在H264幀內(nèi)預(yù)測中，子塊大小分為3種，不同大小下分別有不同的預(yù)測方向。我們假設(shè)每種預(yù)測模式出現(xiàn)的幾率是相同的，并以其中4X4子塊的預(yù)測模式3為例。如圖4，圖4Intra_4x4_Diagonal_Down_Left預(yù)測模式（模式3）在串行條件下（參考H264編解碼開源代碼JM10.4），他的預(yù)測函數(shù)為：caseDIAG_DOWN_LEFT_PRED:if(!block_available_up) //ioff和joff表示宏塊坐標(biāo)，P_A~P_H等表示已知上鄰居像素點的亮度值img->mpr[0+ioff][0+joff]=(P_A+P_C+2*(P_B)+2)/4;img->mpr[1+ioff][0+joff]=img->mpr[0+ioff][1+joff]=(P_B+P_D+2*(P_C)+2)/4;img->mpr[2+ioff][0+joff]=img->mpr[1+ioff][1+joff]=img->mpr[0+ioff][2+joff]=(P_C+P_E+2*(P_D)+2)/4;img->mpr[3+ioff][0+joff]=img->mpr[2+ioff][1+joff]=img->mpr[1+ioff][2+joff]=img->mpr[0+ioff][3+joff]=(P_D+P_F+2*(P_E)+2)/4;img->mpr[3+ioff][1+joff]=img->mpr[2+ioff][2+joff]=img->mpr[1+ioff][3+joff]=(P_E+P_G+2*(P_F)+2)/4;img->mpr[3+ioff][2+joff]=img->mpr[2+ioff][3+joff]=(P_F+P_H+2*(P_G)+2)/4;img->mpr[3+ioff][3+joff]=(P_G+3*(P_H)+2)/4;break;4.2并行方案的初步設(shè)計我們以并行的粒度不同，設(shè)計了三種并行方案：1)每個線程處理一整個宏塊/子塊的幀內(nèi)預(yù)測；2)每個線程處理一個像素點的幀內(nèi)預(yù)測；3)每個線程計算一種預(yù)測方式內(nèi)相同預(yù)測方向上的一組像素點（如圖4）。以上文的幀內(nèi)預(yù)測模式為例，即1號線程計算預(yù)測矩陣中像素點a的亮度值，2號線程計算b、e，3號線程計算c、f、i，以此類推。現(xiàn)在我們用性能評估公式來估算三種方案的執(zhí)行時間，從而為該視頻解碼選擇出最優(yōu)的解決方案。4.3模型指導(dǎo)下的設(shè)備和存儲器選擇由于共享內(nèi)存遠(yuǎn)超全局內(nèi)存的訪存速度，我們優(yōu)先討論把數(shù)據(jù)全部放入共享內(nèi)存的可能性，這會極大的提高訪存速度。我們存儲圖像各像素的亮度值時，為了避免bankconflict，使用的數(shù)據(jù)類型是unsignedint。三種方案輸入和輸出的數(shù)據(jù)大小相同，故而要把所有數(shù)據(jù)存入共享內(nèi)存的話，以最壞的情況考慮，當(dāng)讀入的待處理宏塊全部為16X16大小時，每個宏塊所需的的存儲空間為1156Byte。若是要把數(shù)據(jù)全部存放到sharedmemory中，也就是說，M2=1156，根據(jù)約束條件(13)，可知 (17)我們以GTX280為例，他的共享內(nèi)存大小MaxSharedMemory=16KB，代入(17)，。由此可知，當(dāng)我們把數(shù)據(jù)全部存放到sharedmemory中時，每個SM最多只能分配14個線程，而GTX280的SM個數(shù)S=30，這種情況下，GTX280的所有SM每次能處理的線程上限為420，而3000個視頻，每個線程處理一個視頻的當(dāng)前宏塊，需要調(diào)用[3000/420]=8次SM，這極大的影響了效率。同樣的，不同設(shè)備能同時處理的宏塊數(shù)見表7。表7.數(shù)據(jù)全部存放在共享內(nèi)存中時，不同設(shè)備能一次性處理的宏塊數(shù)[10]GTX280GTX480GTX670核心代號GT200GF100GK104MaxSharedMemory/SM164848SM個數(shù)30157SP個數(shù)2404801344Sp個數(shù)/SM832192共享內(nèi)存總大小480720336一次性處理的宏塊數(shù)425637297我們的目標(biāo)是3000個視頻同時進(jìn)行幀內(nèi)預(yù)測，從上表可以看出，把所有數(shù)據(jù)存放在共享內(nèi)存中，會讓許多運算單元空閑下來。故而我們把輸入（鄰居信息）存儲在sharedmemory中，而把輸出存儲在globalmemory中。4.4模型指導(dǎo)下的解決方案選擇由于kernel函數(shù)內(nèi)部不需要同步指令，即同步次數(shù)k=0，那么同步時間Ts=0。計算執(zhí)行時間以關(guān)鍵線程（指令/訪存周期最長的線程）為準(zhǔn)。如上文，設(shè)調(diào)用kernel函數(shù)時的block數(shù)量為b，每個block內(nèi)的線程為t，以GTX670為實驗平臺，以4X4宏塊的預(yù)測模式3為例。讓我們分析下三種方案下的線程