關于并行計算的相關總結

• 1. 定義
• 2. 特征及層次
• 3. 應用舉例
• • 3.1 基于CUDA 的K-Means 多級并行優化方法
  • 3.2 面向GPU的直方圖統計圖像增強并行算法
  • 3.3 基于FPGA的多核可擴充卷積加速器設計

1. 定義

并行計算或稱平行計算是相對于串行計算來說的。它是一種一次可執行多個指令的算法，目的是提高計算速度，及通過擴大問題求解規模，解決大型而複雜的計算問題。所謂并行計算可分為時間上的并行和空間上的并行。時間上的并行就是指流水線技術，而空間上的并行則是指用多個處理器并發的執行計算。

并行計算（Parallel Computing）是指同時使用多種計算資源解決計算問題的過程，是提高計算機系統計算速度和處理能力的一種有效手段。它的基本思想是用多個處理器來協同求解同一問題，即将被求解的問題分解成若幹個部分，各部分均由一個獨立的處理機來并行計算。并行計算系統既可以是專門設計的、含有多個處理器的超級計算機，也可以是以某種方式互連的若幹台的獨立計算機構成的叢集。通過并行計算叢集完成資料的處理，再将處理的結果傳回給使用者。

2. 特征及層次

為利用并行計算，通常計算問題表現為以下特征：

（1）将工作分離成離散部分，有助于同時解決；

（2）随時并及時地執行多個程式指令；

（3）多計算資源下解決問題的耗時要少于單個計算資源下的耗時。

數字圖像處理算法多種多樣，但從資料處理的層面來考慮，可以分為：像素級處理、特征級處理和目标級處理三個層次。

（1）像素級圖像處理

像素級處理，即由一幅像素圖像産生另一幅像素圖像，處理資料大部分是幾何的、規則的和局部的。根據處理過程中的資料相關性，像素級處理又可進一步分為點運算、局部運算和全局運算。

（2）特征級圖像處理

特征級處理是在像素圖像産生的一系列特征上進行的操作。常用的特征包括：形狀特征、紋理特征、梯度特征和三維特征等，一般采用統一的測度，如：均值、方差等，來進行描述和處理，具有在特征域内進行并行處理的可能性。但是，由于其特征具有象征意義和非局部特性，在局部區域并行的基礎上，需要對總體進行處理。利用GPU實作并行化處理的難度比較大。

（3）目标級圖像處理

目标級處理是對由一系列特征産生的目标進行操作。由于目标資訊具有象征意義和複雜性，通常是利用相關知識進行推理，得到對圖像的描述、了解、解釋以及識别。由于其資料之間相關性強，且算法涉及到較多的知識和人工幹預，并行處理的難度也比較大。

3. 應用舉例

3.1 基于CUDA 的K-Means 多級并行優化方法

聚類分析也是資料分類的一種，但與分類技術還存在一定的差别，最大不同之處在于聚類處理資料的所屬類是未知的，它是一個無監督過程。是在沒有相關經驗的基礎上，對資料進行處理，分析出資料間内在關聯并找出規律，将樣本點間距離較近的資料配置設定到相同的聚類中，反之，将樣本點間距離較遠的資料配置設定到不同的聚類中。目前常用的聚類算法分别是基于密度、網格、層次、劃分和模型的聚類算法。

CUDA( Compute Unified Device Architecture) 是由顯示卡廠商NVIDIA 推出的運算平台，是一種通用的并行計算架構，其能充分結合CPU 和GPU 的優點。其中，CPU 為主處理器( host) 執行邏輯事務處理和串行計算，GPU 作為協處理器( device) 執行高度并行化的計算任務。GPU 的計算核心均勻劃分到多個流多處理器( stream multiprocessor，SM) 中。同時，GPU 還有不同的存儲機制。其中，裝置記憶體可接受來自CPU 的資料; 共享記憶體可供SM 中的所有線程塊block 公用;寄存器被配置設定的thread 單獨使用。

3.2 面向GPU的直方圖統計圖像增強并行算法

直方圖統計在圖像增強和目标檢測等領域有着重要的應用。然而，随着圖像規模不斷增大、實時性要求越來越高時，直方圖統計局部增強算法的處理過程較慢，達不到預期滿意的速度。首先，通過充分利用統一計算裝置架構（CUDA）活動線程塊和活動線程來并行處理不同的子圖像塊和像素點，提升了資料通路的效率。然後，采用核心配置參數優化和資料并行計算技術，實作了直方圖統計圖像增強算法在GPU平台上的并行化。最後，采用主機端和裝置端間高效的資料傳輸模式，進一步縮短了系統在異構計算平台上的執行時間。研究表明，對于像幅大小不同的圖像，圖像直方圖統計并行算法的處理速度相比于CPU串行算法均有兩個數量級的提高，處理一幅像幅大小為3241×3685 的圖像需要787.11ms，并行算法的處理速度提高了261.35倍。為實作實時大規模圖像處理奠定了良好基礎。

CUDA 的應用系統是GPU 和CPU 的混合代碼系統。在執行CUDA 系統時，主機端執行的二進制代碼在調用核函數時需要将裝置端代碼通過CUDA API 傳給裝置端。GPU 傳給CUDA API 的裝置端代碼不一定是二進制代碼CUBIN，也可能是運作于JIT動态編譯器上的彙編形式的PTX(Parallel Thread Execution)代碼。最後傳到裝置上的是适合具體GPU 的二進制代碼，其中的資訊多于PTX 或者CUBIN，這是因為CUBIN 或者PTX 隻包含了線程塊一級的資訊，而不包括整個網格的資訊。目前，在GPU 上可以運作的指令長度仍然有限制，不能超過兩百萬條PTX 指令。GPU 端二進制代碼主要包括網格的次元和線程塊的次元，每個線程塊使用的資源數量，要運作的指令以及常數存儲器中的資料。

算法包含三級并行性：

（1）像素點級并行：為了對圖像中包含的隐含特征進行局部增強，需要将圖像進行直方圖統計，對每一幅圖像的每一個像素點的處理是互相獨立的，可以并行執行；

（2）均值和方內插補點級并行：每個像素點的局部均值和局部方差的計算是互相獨立的，可以并行執行；

（3）視窗級并行：每個局部統計視窗的處理是互相獨立的，可以并行處理。

數字圖像本質上就是一個二維數組，每個像素的處理過程是互相獨立并且完全

一樣的計算過程。是以，可以在GPU 叢集上采用MPI 和CUDA 相結合的技術，由MPI 完成更大圖像塊之間的并行，由每個節點上的GPU 完成圖像塊内的并行，通過GPU 叢集可以使處理速度更快，争取能夠在更短的時間内完成更大尺寸的圖像處理工作。

3.3 基于FPGA的多核可擴充卷積加速器設計

為解決卷積神經網絡計算效率和能效較低的問題，提出并設計一種使用定點資料作為輸入的卷積加速器。加速器支援動态量化的8Bits定點資料的卷積計算，通過采用分塊計算的政策和改進的循環計算順序，有效提高計算效率；支援激活、批标準化（BN）、池化和全連接配接等計算；基于軟硬體協同設計的思路，設計包含卷積加速器和ARM處理器在内的SOC系統。提出一種将加速器進行多核擴充的方法，提高算力和移植便捷性。将加速器部署在Xilinx ZCU102開發闆上，其中單核加速器的算力達到了153.6GOP/s，在計算核數目增加到４個和８個的情況下，算力分别增至614.4 GOP/s和1024 GOP/s。

對于FPGA平台中實作的卷積加速設計，主要圍繞以下思路來展開：基于CNN網絡中輸入特征映射和卷積核多通道的特性，設計乘加陣列進行并行計算；基于有限的片上存儲資源，對輸入和權重資料進行分塊，并通過設定片上緩存來暫時存儲分塊資料以減少加速器與片外存儲之間的資料訪存次數；通過設計特定的循環展開計算順序，實作片上緩存資料的複用以及高效的并行計算效率。

加速器主要由計算單元、片上緩存以及控制器組成。計算單元主要由乘加子產品、累加子產品、BN計算子產品、定點處理子產品、激活子產品以及池化子產品組成，是完成加速計算的關鍵部分。片上緩存調用FPGA的BRAM資源，将來自片外的輸入特征映射、權重資料以及卷積計算結果暫存。而控制器主要産生一些控制卷積計算過程的信号，保證計算準确有序進行。