基于異構(gòu)計算的矩陣廣義逆算法研究及實現(xiàn)

1、!七狀舊域I X富UNIVERSITY OF ELECTRONIC SC I ENCE AND TECHNOLOGY OF CHINA碩士學位論文MASTER THESIS論文題目基于異構(gòu)計算的矩陣廣義逆算法研究及實現(xiàn)學科專業(yè)通信與信息系統(tǒng)學 號201121010401作者姓名范興山指導教師 李廣軍 教授獨創(chuàng)性聲明本人聲明所呈交的學位論文是本人在導師指導下進行的研究工 作及取得的研究成果。據(jù)我所知，除了文中特別加以標注和致謝的地 方外，論文中不包含其他人已經(jīng)發(fā)表或撰寫過的研究成果，也不包含 為獲得電子科技大學或其它教育機構(gòu)的學位或證書而使用過的材料。 與我一同工作的同志對本研究所做的任何貢獻均

2、已在論文中作了明 確的說明并表示謝意。作者簽名：力事山 日期：籍隹&月V日論文使用授權(quán)本學位論文作者完全了解電子科技大學有關(guān)保留、使用學位論文 的規(guī)定，有權(quán)保留并向國家有關(guān)部門或機構(gòu)送交論文的復印件和磁盤, 允許論文被查閱和借閱。本人授權(quán)電子科技大學可以將學位論文的全 部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進行檢索，可以采用影印、縮印或掃描 等復制手段保存、匯編學位論文。（保密的學位論文在解密后應遵守此規(guī)定）作者簽名：么老小導師簽名:日期：年4月3日分類號密級UDC注 1學位論文基于異構(gòu)計算的矩陣廣義逆算法研究及實現(xiàn)（題名和副題名）范興山（作者姓名）指導教師李廣軍 教授電子科技大學（姓名、職稱、單位名稱）

3、申請學位級別 碩士 學科專業(yè)通信與信 息系統(tǒng)提交論文日期2014415 論文答辯日學位授予單位和日期 電子科技大學 2014年6月29日答辯委員會主席評閱人注1：注明國際十進分類法UDC的類號。RESEARCH AND IMPLEMENTATIONOF GENERALIZED INVERSE ALGORITHMWITH HETEROGENEOUS COMPUTINGA Master Thesis Submitted toUniversity of Electronic Science and Technology of ChinaMajor： Communication and Informa

4、tion SystemAuthor：Fan XingshanAdvisor：Prof. Guangjun LiSchool: Communication and Information Engineering摘要廣義逆矩陣理論不僅是許多數(shù)學分支的基本工具，更是在經(jīng)濟學、信息處理、 自動控制、通信學、密碼學和統(tǒng)計學等應用學科中都有著廣泛的應用。因此，提升 廣義逆矩陣的計算性能有著非常大的實用價值，然而傳統(tǒng)的CPU串行計算對此卻 無能為力。近年來，以O(shè)penCL計算架構(gòu)為代表的異構(gòu)計算發(fā)展迅速，己廣泛應用于多個 領(lǐng)域，在圖像視頻處理、密碼學等領(lǐng)域常用來進行運算加速，廣義逆矩陣也可以通 過OpenC

5、L這種異構(gòu)計算方式提升其計算性能。本文以異構(gòu)計算為背景，以O(shè)penCL為編程架構(gòu)，實現(xiàn)廣義逆矩陣的運算加 速。本文首先對OpenCL規(guī)范作了簡短介紹；基于GPU和FPGA的硬件架構(gòu)，分 別分析它們的OpenCL實現(xiàn)機制；由于GPU和FPGA在硬件架構(gòu)與實現(xiàn)機制上是 完全不一樣的，它們的性能優(yōu)化技術(shù)也迥然不同，因而分別對它們的優(yōu)化技術(shù)進行 分析。本文以運算所需的加法和乘法次數(shù)為指標，對三種常用的廣義逆矩陣算法的 計算復雜度進行分析，解方程法的計算量要略高于其他兩種算法。然而通過基于異 構(gòu)計算的實現(xiàn)復雜度分析，在最小任務數(shù)、控制流、運算資源等關(guān)鍵指標上，解方 程法要明顯好于另外兩種算法。綜合計算復

6、雜度和實現(xiàn)復雜度的分析結(jié)果，解方程 法能獲得更好的異構(gòu)計算性能。因此本文以解方程法為基礎(chǔ)設(shè)計一套基于異構(gòu)計 算的實現(xiàn)方案，在最優(yōu)的并行度基礎(chǔ)上，對方案中的多個模塊進行并行化處理，并 設(shè)計相應的同步點以保證數(shù)據(jù)的一致性。依據(jù)OpenCL的運行機制，分別對存儲訪 問部分和數(shù)據(jù)處理部分進行深入優(yōu)化，以提高算法的運算性能，并用MATLAB對 該方案進行驗證。本文分別在GPU和FPGA上實現(xiàn)該方案，并針對它們各自的架構(gòu)特點，制定 不同的優(yōu)化策略和測試方案。測試結(jié)果表明：在計算誤差方面，GPU由于其內(nèi)部 的浮點運算單位精度較高，其最大誤差低至10-7級；而FPGA由于其內(nèi)部的乘法 器位寬僅為18位，其誤差

7、相對較大，最大誤差在IO；級。與MATLAB標準函數(shù) 運行時間相比，GPU平臺憑借其成熟的開發(fā)理論和巨量的計算資源，加速比達到 T 1909； FPGA平臺由于其開發(fā)理論不成熟，只獲得34的加速比，但還有著巨大 的提升空間。關(guān)鍵詞：矩陣廣義逆，異構(gòu)計算，OpenCL, GPU, FPGAABSTRACTIt is the general picture that the generalized inverse is a fundamental tool in the fields of mathematics. Also it can be widely applied effectively

8、 in terms of economics, information processing, automatic control, communications, cryptography, statistics etc. In this sense, improving the performance of the calculation processes of generalized inverse is likely to achieve huge practical value. On the contraiy, the traditional CPU architectures

9、which focus on the serial computing, can barely cope with it.Recently, heterogeneous computing, such as computing in OpenCL, develops rapidly, especially in the areas of wide processing as well as cryptography, which brings the acceleration during processing. In fact, generalized inverse can be acce

10、lerated and it can benefit from computing in OpenCL.In this paper, we present the implementation of generalized inverse by using OpenCL coding architecture. First of all, a brief presentation on the OpenCL specification is presented and then two platforms including the GPU and the FPGA are analysed

11、in order to figure out the mechanisms of implementation when we decide to build generalized inverse with OpenCL. In addition, as the hardware as well as the mechanism vary a lot between the GPU and the FPGA, different optimized strategies are presented to achieve the well-run designs.In this paper,

12、the number of addition and multiplication are considered as the index to estimate the complexity in thiee common generalized inverse algorithms. Computational complexity of solving equations method is slightly higher than the other two algorithms. However, through the analysis of realization complex

13、ity under heterogeneous computing, solving equations method is significantly better than the other two algorithms in the indicators of the minimum number of tasks, control flow, computing resources, etc. Integrated the analysis results of computational complexity and realization complexity, solving

14、equations method can get better performance with heterogeneous computing. Therefore, this paper design a realization scheme based on solving equations, make multiple modules of scheme parallel, and design appropriate synchronization points to ensure data consistency. Based on OpenCL operating mechan

15、ism, the thesis optimizes the data processing and storage accessing to improve computing performance, and verifies it using MATLAB.The scheme is implemented in the GPU and FPGA respectively, and different optimization strategies and testing scheme are applied according to the different architectural

16、 in each platform. The test results show that: in terms of the calculation error, the maximum enor of GPU is as low as 107 level because of its internal high-precision floating point arithmetic units. The eiTor of FPGA platform is relatively larger because its internal multipliers only have 18 bits.

17、 The maximum error is in the 103 level. Compared with the MATLAB, GPUs speed-up ratio reached 1909 with the benefit from the sophisticated development and the large amount of computing resources. FPGA only speeded up 34 times, because of the immaturity design methods, but there is a tremendous space

18、 for improvement.Key words: Heterogeneous Computing, Generalized Inverse Matrix, OpenCL, GPU, FPGA目錄 TOC o 1-5 h z HYPERLINK l bookmark50 o Current Document 第一章緒論1 HYPERLINK l bookmark53 o Current Document 1.1研究背景1 HYPERLINK l bookmark56 o Current Document 1.2國內(nèi)外研究現(xiàn)狀2 HYPERLINK l bookmark59 o Curren

19、t Document 1.2.1矩陣廣義逆2 HYPERLINK l bookmark62 o Current Document 1.2.2異構(gòu)計算3 HYPERLINK l bookmark65 o Current Document 13本文的結(jié)構(gòu)安排4 HYPERLINK l bookmark71 o Current Document 第二章 基于OpenCL標準的異構(gòu)計算6 HYPERLINK l bookmark74 o Current Document 異構(gòu)計算概述6 HYPERLINK l bookmark77 o Current Document OpenCL標準簡介7 HYPE

20、RLINK l bookmark81 o Current Document OpenCL 架構(gòu)8 HYPERLINK l bookmark85 o Current Document 23.1平臺模型8 HYPERLINK l bookmark88 o Current Document 23.2執(zhí)行模型9 HYPERLINK l bookmark91 o Current Document 2.3.3內(nèi)存模型10 HYPERLINK l bookmark94 o Current Document 23.4編程模型12 HYPERLINK l bookmark97 o Current Documen

21、t 2.4基于GPU的異構(gòu)平臺12 HYPERLINK l bookmark100 o Current Document GPU 概述13 HYPERLINK l bookmark104 o Current Document GPU 的 OpenCL 框架13 HYPERLINK l bookmark108 o Current Document 2.4.3基于GPU的OpenCL優(yōu)化技術(shù)15 HYPERLINK l bookmark114 o Current Document 2.5基于FPGA的異構(gòu)平臺17 HYPERLINK l bookmark119 o Current Document

22、 FPGA 概述18 HYPERLINK l bookmark122 o Current Document FPGA 的 OpenCL 框架19 HYPERLINK l bookmark138 o Current Document 2.5.3基于FPGA的OpenCL優(yōu)化技術(shù)22 HYPERLINK l bookmark146 o Current Document 2.6本章小結(jié)23 HYPERLINK l bookmark149 o Current Document 第三章 矩陣廣義逆算法研究24 HYPERLINK l bookmark152 o Current Document 3.1矩

23、陣廣義逆概述24 HYPERLINK l bookmark164 o Current Document 3.2常用算法介紹26 HYPERLINK l bookmark167 o Current Document 3.2.1初等變換法26 HYPERLINK l bookmark181 o Current Document 3.2.2滿秩分解法27 HYPERLINK l bookmark184 o Current Document 3.2.3解方程法28 HYPERLINK l bookmark195 o Current Document 3.3常用算法的計算復雜度分析29 HYPERLIN

24、K l bookmark198 o Current Document 3.3.1初等變換法29 HYPERLINK l bookmark204 o Current Document 3.3.2滿秩分解法31 HYPERLINK l bookmark211 o Current Document 3.3.3解方程法33 HYPERLINK l bookmark218 o Current Document 3.4基于異構(gòu)計算的實現(xiàn)復雜度分析34 HYPERLINK l bookmark225 o Current Document 3.4.1初等變換法37 HYPERLINK l bookmark23

25、3 o Current Document 3.4.2滿秩分解法40 HYPERLINK l bookmark241 o Current Document 3.4.3解方程法42 HYPERLINK l bookmark249 o Current Document 3.5本章小結(jié)45 HYPERLINK l bookmark255 o Current Document 第四章基于異構(gòu)計算的矩陣廣義逆實現(xiàn)方案設(shè)計46 HYPERLINK l bookmark258 o Current Document 4.1基于異構(gòu)計算的方案設(shè)計46 HYPERLINK l bookmark261 o Curre

26、nt Document 4.2算法的并行化設(shè)計48 HYPERLINK l bookmark264 o Current Document 4.2.1矩陣乘法并行化49 HYPERLINK l bookmark267 o Current Document 4.2.2解矩陣方程并行化50 HYPERLINK l bookmark270 o Current Document 4.23數(shù)據(jù)同步點設(shè)計54 HYPERLINK l bookmark289 o Current Document 43基于異構(gòu)計算的算法優(yōu)化56 HYPERLINK l bookmark292 o Current Documen

27、t 4.3.1數(shù)據(jù)處理優(yōu)化56 HYPERLINK l bookmark295 o Current Document 4.3.2存儲訪問優(yōu)化58 HYPERLINK l bookmark298 o Current Document MATLAB 驗證61 HYPERLINK l bookmark301 o Current Document 4.5本章小結(jié)64 HYPERLINK l bookmark304 o Current Document 第五章基于OpenCL的矩陣廣義逆實現(xiàn)及測試66 HYPERLINK l bookmark307 o Current Document 5.1開發(fā)平臺簡

28、介66 HYPERLINK l bookmark312 o Current Document 5.2基于OpenCL的方案實現(xiàn)68 HYPERLINK l bookmark315 o Current Document 5.2.1宿主機程序設(shè)計69 HYPERLINK l bookmark324 o Current Document GPU內(nèi)核實現(xiàn)70 HYPERLINK l bookmark330 o Current Document 5.23 FPGA內(nèi)核實現(xiàn)72 HYPERLINK l bookmark339 o Current Document 53測試及分析76 HYPERLINK l

29、 bookmark342 o Current Document 5.3.1測試方案76 HYPERLINK l bookmark345 o Current Document 5.3.2測試結(jié)果及性能分析78 HYPERLINK l bookmark350 o Current Document 5.4本章小結(jié)85 HYPERLINK l bookmark353 o Current Document 第六章總結(jié)與展望86 HYPERLINK l bookmark356 o Current Document 6.1本文工作總結(jié)86 HYPERLINK l bookmark362 o Current

30、Document 6.2未來研究展望86 HYPERLINK l bookmark368 o Current Document 致謝88參考文獻89攻讀碩士學位期間的研究成果93圖目錄 TOC o 1-5 h z 圖1-1異構(gòu)計算示意圖2圖2-1 OpenCL平臺模型8圖2-2全局ID、局部ID和工作組索引之間的關(guān)系10圖2-3 OpenCL內(nèi)存模型11圖2-4現(xiàn)代GPU架構(gòu)13圖2-5 AMD GPU的內(nèi)存架構(gòu)14圖2-6順序讀取模式16圖2-7聯(lián)合讀取模式16圖2-8 LDS組織結(jié)構(gòu)17圖2-9FPGA 結(jié)構(gòu)18圖2-10 FPGA 的 OpenCL 架構(gòu)19圖2-11 4端口的本地內(nèi)存2

31、1圖2-12本地內(nèi)存配置21圖3-1子任務無法組合35圖3-2子任務可以組合36圖4-1總體實現(xiàn)方案46圖4-2 OpenCL設(shè)備上的線程映射關(guān)系47圖4-3解方程法的算法流程48圖4-4 一個線程計算一個元素49圖4-5 一個線程計算一行元素50圖4-6 一個線程計算一列元素50圖4-7解矩陣方程流程圖51圖4-8線程k的解矩陣方程任務流圖52圖4-9線程k的變換第k行任務流圖53圖4-10線程k的行交換流程53圖4-11 OpenCL 同步點54圖4-12數(shù)據(jù)同步點位置55圖4-13 MATLAB仿真流程圖61圖4-14處理前M-1列62圖4-15最大絕對誤差64圖4-16最大相對誤差64

32、圖5-1開發(fā)平臺66圖 5-2 DE4-530 視圖68圖 5-3 宿主機程序流程69圖5-4 FPGA實現(xiàn)框圖73圖5-5解矩陣方程模塊74圖5-6測試方案框圖76圖5-7 GPU的最大絕對誤差78圖5-8 FPGA的最大絕對誤差79圖5-9 CPU串行程序的執(zhí)行時間79圖5-10 GPU平臺的總計算時間80圖5-11 GPU平臺的平均計算時間81圖5-12 GPU平臺的加速比81圖5-13 FPGA平臺的循環(huán)展開測試結(jié)果82圖5-14 FPGA平臺的總計算時間83圖5-15 FPGA平臺的平均計算時間83圖5-16 FPGA平臺的加速比84表目錄 TOC o 1-5 h z 表2-1宿主機

33、和設(shè)備對內(nèi)存的管理11表3-1行變換的計算量30表3-2列變換的計算量30表3-3計算矩陣B的運算量32表3-4計算（時AG 的運算量32表3-5初等變換法中各子任務的可選并行度37表3-6初等行變換中的if判斷個數(shù)38表3-7初等行變換需要的同步點38表3-8初等行變換單個線程的加法器需求量38表3-9計算QXP的加法器需求量39表3-10初等行變換中單個線程的加法器需求量39表3-11計算QXP的乘法器需求量39表3-12滿秩分解法中各子任務的可選并行度40表3-13滿秩分解法的if判斷個數(shù)40表3-14滿秩分解需要的同步點41表3-15滿秩分解中單個線程的加法器需求量41表3-16矩陣求

34、逆中的加法器需求量41表3-17矩陣乘法中加法器的需求量41表3-18滿秩分解中單個線程的乘法器需求量42表3-19矩陣求逆中的乘法器需求量42表3-20矩陣乘法中乘法器的需求量42表3-21解方程法中各子任務的可選并行度43表3-22解矩陣方程的if判斷個數(shù)43表3-23解矩陣方程需要的同步點43表3-24解矩陣方程中單個線程的加法器需求量44表3-25矩陣乘法的加法器需求量44表3-26解矩陣方程中單個線程的乘法器需求量44表3-27矩陣乘法的乘法器需求量44表4-1解方程法的子任務并行度48表4-2數(shù)據(jù)處理優(yōu)化減少的運算量58表4-3全局存儲優(yōu)化前后的訪問次數(shù)59表4-4全局存儲優(yōu)化前后

35、的訪問時間估計59表4-5添加私有變量后的訪存優(yōu)化效果60表4-6本地存儲的優(yōu)化結(jié)果60表4-7訪存優(yōu)化結(jié)果61表4-8GPU平臺的訪存優(yōu)化結(jié)果72表5-1硬件環(huán)境66表5-2軟件環(huán)境67表5-3 AMD HD 7950的關(guān)鍵指標67表5-4 EP4SGX530C2 邏輯資源68表5-5 DDR參數(shù)68表5-6 GPU測試集77表5-7 FPGA展開次數(shù)測試77表5-8 FPGA測試集78表5-9測試案例所需的線程數(shù)80表5-10 FPGA平臺綜合結(jié)果84縮略詞表英文縮寫英文全稱中文注釋CPUCentral Processing Unit中央處理器GPUGraphic Processing U

36、nit圖形處理器APUAccelerated Processing Unit加速處理器GPGPUGeneral Purpose Graphic Processing Unit通用圖形處理器FPGAField Programmable Gate Array現(xiàn)場可編程門陣列DSPDigital Signal Processor數(shù)字信號處理器LTELong Term Evolution3GPP長期演進項目OFDMOrthogonal Frequency Division Multiplexing正交頻分復用DDRDouble Data Rate雙倍速率SDRAMCUCompute Unit計算單元P

37、EProcessing Element處理單元IPIntellectual Property知識產(chǎn)權(quán)SIMDSingle Instruction Multiple Data單指令多數(shù)據(jù)流SPMDSingle Program Multiple Data單程序多數(shù)據(jù)LUTLook-Up Table查找表RAMRamdom Access Memory隨機存取存儲器FIFOFirst Input First Output先入先出隊列第一章緒論1.1研究背景任何一門學科的產(chǎn)生與發(fā)展都跟它的應用是密切相關(guān)的，廣義逆矩陣也是如 此。針對普通逆矩陣只對非奇異方陣有效的缺點，Moore, E.H在1920年提出

38、廣 義逆矩陣的概念及定義，奠定了廣義逆矩陣的發(fā)展基礎(chǔ)。正是可應用的場景廣 泛，才使得廣義逆矩陣這一學科得到了快速的發(fā)展。半個多世紀以來，廣義逆矩陣已廣泛應用于多個領(lǐng)域和學科。在控制理論及 其應用中，廣義逆矩陣常用于對隨機和確定性系統(tǒng)的濾波、固定點平滑、固定滯 后平滑與預報中，以得到離散線性隨機系統(tǒng)和定常系統(tǒng)狀態(tài)的最優(yōu)線性無偏估計 和無差估計。在神經(jīng)網(wǎng)絡(luò)計算領(lǐng)域，Kohonen模型（最優(yōu)線性聯(lián)想神經(jīng)網(wǎng)絡(luò)）的 樣本集上誤差為零，可求取既簡單又誤差小的矩陣W是困難的，若用廣義逆矩 陣來進行求解，則可以很好地解決該問題。在通信領(lǐng)域中，廣義逆矩陣的應用也是非常廣泛。比如在秘鑰協(xié)議中，為了 增強秘鑰的安全

39、性和實用性，常采用廣義逆矩陣來生成秘鑰。在OFDM系統(tǒng)的 信道估計中，由于其信號矩陣并不總是方陣，因此也需要用到廣義逆矩陣來求解 信道的沖擊響應和頻率函數(shù)閔。由于廣義逆矩陣的實現(xiàn)較為復雜，人們一般將目光都集中在純算法的研究上, 以期提高廣義逆矩陣的計算效率4。然而，提高廣義逆矩陣的計算效率還有另外 一種方法，就是通過具體實現(xiàn)方案的加速，異構(gòu)計算就是這樣一種加速手段。異構(gòu)計算是將多個不同類型的計算單元組成一個混合計算系統(tǒng)，有效利用計 算資源，提高計算效率，如圖1-1所示。在電腦中，通過PCIe接口可以將CPU、 GPU、FPGA等多個異構(gòu)計算設(shè)備連接在一起，這些計算設(shè)備協(xié)同作業(yè)，共同完 成計算任

40、務，獲得強大的加速能力，從而讓整個系統(tǒng)達到最佳的能效比和性能。近年來，由于人們對能耗越來越關(guān)注，使得異構(gòu)計算發(fā)展非常迅速，巳廣泛 應用于圖像視頻處理領(lǐng)域。文獻6通過異構(gòu)計算，有效調(diào)用GPU、FPGA等多個 平臺對動態(tài)場景中的光線進行實時跟蹤繪制，以實現(xiàn)高質(zhì)量的全局光照明效果。 文獻7通過調(diào)用GPU對二維圖像的處理和顯示進行加速，相比CPU能獲得200 以上的加速比，即使是與專業(yè)的NVIDIA GPU相比也能達到5的加速比。本文采用異構(gòu)計算的方式實現(xiàn)廣義逆矩陣算法，以期獲得較好的加速性能， 同時對FPGA平臺的OpenCL開發(fā)方法進行探索。ApplicationApplicalion #2App

41、lication 3CPUQueueGPUQueueGPUQueueCPUFPGAQueueQueueI ASK TAK#16TASK 心TASK #33 TASK #36TASK 4按 TASK 聆5TASK #31TASK #34TASK *36TASKTASK 12 TASK(5 TASK 22TASK 1 TASK #14TASK 21WK iJ21TASK #21TASK ff 21TASK#21IASKBI ASK 制TASK #1 IFPGA圖1-1異構(gòu)i I算示意圖1.2國內(nèi)外研究現(xiàn)狀1.2.1矩陣廣義逆在研究廣義逆矩陣領(lǐng)域，Moore, E.H是公認的第一人，早在1920年，

42、其在 美國數(shù)學會通報上便刊文提出了廣義逆矩陣的概念及定義，但是卻并沒有引起人 們足夠的重視。直到到1955年，英國學者PenroseR在劍橋哲學會學報上了發(fā)表 了著名論文廣義逆矩陣，Pemose R在文中采用了更簡便實用的定義，即是 Moore-Pemose逆矩陣，這種定義得到了人們的廣泛認可。在Moore-Penrose逆矩 陣的基礎(chǔ)上，研究者們針對不同的應用環(huán)境，又定義了多種廣義逆矩陣。比如, Bott和Duffin基于電網(wǎng)絡(luò)領(lǐng)域提出了 Bott-Duffin逆矩陣，Erdelyi在研究Abel群 時提出了群逆的概念，其他還有加權(quán)廣義逆矩陣和a 一8廣義逆矩陣等兇。隨著廣義逆矩陣的研究不斷

43、深入，其應用領(lǐng)域越來越廣，從數(shù)值分析、數(shù)學 規(guī)劃到控制論、博弈論和計量經(jīng)濟學等領(lǐng)域都需要用到廣義逆矩陣。DawsonE在 1997年將廣義逆矩陣引入密碼學，用于秘鑰協(xié)商。在2005年，陳曦等一些學者 對廣義逆矩陣在通信中的應用進行研究，成功將廣義逆矩陣應用于OFDM系統(tǒng) 的信道估計網(wǎng)。在計算廣義逆矩陣方面，人們已提出了多種算法，如常用的滿秩分解法、遞 推法、奇異值分解法和初等變換法等。在這些常用方法的基礎(chǔ)上，近年來又有一 些學者提出一些新的技術(shù)方法，如半迭代法和分裂迭代法等。目前針對廣義逆矩陣的研究大部分都是理論性的探索，其中一個研究方向是 將廣義逆矩陣應用到不同的領(lǐng)域，甚至在該特定領(lǐng)域中提出

44、一種廣義逆矩陣的變 形；另一個研究方向是如何計算廣義逆矩陣，主要停留在算法層面，并沒有針對 具體平臺進行實現(xiàn)優(yōu)化。因此，本文對廣義逆矩陣算法在GPU和FPGA平臺上分別進行實現(xiàn)及優(yōu)化 具有實際的意義。1.2.2異構(gòu)計算異構(gòu)計算并不是一個嶄新的領(lǐng)域，在上世紀八十年代就巳誕生出“異構(gòu)計算” 這個概念。不過，早期的異構(gòu)計算并不是基于單機系統(tǒng)，而是以高速互聯(lián)網(wǎng)絡(luò)為 基礎(chǔ)，組織多臺計算機進行并行運算，以獲得最大的性能，這種方式是屬于網(wǎng)絡(luò) 異構(gòu)計算（NHC）。在這種結(jié)構(gòu)中，程序被拆分成許多相對較為獨立的子任務， 這些子任務分別在不同的計算機上運行，通過消息傳遞來實現(xiàn)數(shù)據(jù)共享。然而，異構(gòu)計算還有另外一個分支

45、，那就是單機異構(gòu)計算，將單個計算機系 統(tǒng)中的CPU、GPU、DSP和FPGA等計算資源整合在一起，協(xié)作完成計算任務 的一種模式。單機異構(gòu)計算有著巨大的應用前景，比如圖像視頻加速a、3D技 術(shù)以及手機等其他一些手持終端設(shè)備。其中，CPU與GPU協(xié)作運算的研究歷史比較久遠，NVIDIA在2006年就提 出了 GPGPU概念，期望通過GPU運算進行應用加速，為此還提出了一套完整 的解決方案CUD Ao CUDA內(nèi)含API和C語言編譯器等，CPU通過調(diào)用顯卡內(nèi) 的流處理器進行數(shù)學運算。另一家GPU廠商AMD對于異構(gòu)計算的解決方案則 是將GPU內(nèi)核集成到CPU芯片上，如今我們所熟知的APU就是其最初方案

46、， 目前其發(fā)展迅速，已基本搭建起了異構(gòu)計算的開放生態(tài)環(huán)境。2008年，在世界開發(fā)者大會上誕生了第一個通用的異構(gòu)計算標準OpenCL, 該標準免費開放，任何廠商或者學者都可以參與它的研究開發(fā)。與其他的異構(gòu)計 算標準不一樣,OpenCL提供了統(tǒng)一的編程環(huán)境,OpenCL程序可以在CPUGPU FPGAM和DSP等計算設(shè)備上輕松地進行移植操作，以實現(xiàn)通用的異構(gòu)計算編 程。由于各個異構(gòu)平臺的架構(gòu)完全不同，OpenCL并不將算法映射到具體的平臺 硬件上，而是作為一種抽象的并行編程框架，通過提供開發(fā)語言、API庫和運行 系統(tǒng)來支持軟件開發(fā)U3。目前基于CPU+GPU的異構(gòu)開發(fā)已進行了大量的研究，已有許多應

47、用采用 OpenCL在GPU上進行實現(xiàn)，并獲得了很好的加速性能，如圖像模糊化處理、加 密算法ME、動態(tài)場景光線跟蹤、矩陣分解Um*等。在計算機系統(tǒng)中，除了 GPU可以與CPU 一起構(gòu)成異構(gòu)系統(tǒng)外，還有許多其 他加速設(shè)備也可以與CPU構(gòu)成異構(gòu)系統(tǒng)，比如FPGA和DSP等。許多硬件設(shè)備 廠商都宣稱對異構(gòu)計算進行支持，然而目前除了 GPU外，就只有FPGAT商進 行了實際的支持。在2013年，Altera和Xilinx】?。相繼推出了基于OpenCL異構(gòu) 計算的開發(fā)平臺和開發(fā)軟件，不過只有特定的幾款開發(fā)板支持異構(gòu)開發(fā)。目前，Altera和Xilinx均提供了相關(guān)的OpenCL開發(fā)套件，并進行了大力

48、推廣，因此基于FPGA的異構(gòu)開發(fā)已逐漸加速，不少學者對圖像視頻壓縮的、數(shù) 學運算、通信算法等在FPGA上的實現(xiàn)進行了研究，比如FFT、矩陣乘法SI、 Turbo編解碼四、LDPC編解碼網(wǎng)等?？傮w來說，異構(gòu)計算在GPU平臺上已經(jīng)有了比較充分的研究，但大部分研 究是基于圖像視頻類應用，對于通信、科學計算等其他一些應用領(lǐng)域則少有研究。 在FPGA平臺上的研究才剛剛開始，由于其平臺的特殊結(jié)構(gòu)，并不能照搬GPU 平臺上的開發(fā)理論，需要研究其特有的開發(fā)方法。1.3本文的結(jié)構(gòu)安排本文的擬研究方向是基于異構(gòu)計算的矩陣廣義逆算法研究及實現(xiàn)。將以移動 通信為背景，恰當選擇廣義逆矩陣的各項參數(shù)。在現(xiàn)有的一些廣義逆矩

49、陣算法基 礎(chǔ)上，分析比較幾種常用算法的計算復雜度，選擇其中適合于采用異構(gòu)計算實現(xiàn) 的算法。以所選算法為基礎(chǔ)，制定一套基于異構(gòu)計算的實現(xiàn)方案，對方案進行并 行化處理和深入優(yōu)化，以期獲得較高的異構(gòu)運算性能，并用MATLAB對方案進 行功能仿真。最后，在GPU和FPGA這個兩個架構(gòu)迥異的異構(gòu)平臺上分別實現(xiàn) 該方案，制定不同的優(yōu)化策略和多套測試方案，結(jié)合測試結(jié)果對比并分析它們的 性能。本文一共分為六章，各章節(jié)的結(jié)構(gòu)安排如下：第一章主要介紹了廣義逆矩陣的廣泛應用，對異構(gòu)計算和廣義逆矩陣的國內(nèi) 外發(fā)展現(xiàn)狀進行了介紹，并提出了它們所面臨的一些問題。第二章則是對異構(gòu)計算進行闡述，詳細介紹主流的異構(gòu)計算標準Op

50、enCL規(guī) 范及其四種模型，闡述FPGA和GPU這個兩個異構(gòu)平臺的OpenCL機制，討論 它們各自的OpenCL優(yōu)化技術(shù)。第三章首先介紹廣義逆矩陣的概念及性質(zhì)，并著重介紹了初等變換法、解方 程法和滿秩分解法這三種常用算法，最后詳細分析這三種方法的計算復雜度和基 于異構(gòu)計算的實現(xiàn)復雜度。第四章在解方程組法的基礎(chǔ)上，設(shè)計一套基于異構(gòu)計算的實現(xiàn)方案，對方案 及其中的關(guān)鍵模塊進行并行化處理，并按照數(shù)據(jù)處理和存儲訪問進行深入優(yōu)化, 最終用MATLAB對該計算方案進行總體仿真。第五章首先介紹了方案的實現(xiàn)平臺，在GPU和FPGA平臺上分別進行實現(xiàn) 和優(yōu)化，根據(jù)它們的平臺特點分別制定多套測試方案，結(jié)合測試結(jié)果

51、進行性能分 析和比較。第六章是對本文工作取得的工作和研究成果進行總結(jié)，指出目前采用 OpenCL對FPGA平臺進行開發(fā)的短板，對矩陣廣義逆和基于OpenCL的FPGA 開發(fā)未來的研究方向進行展望。本文的創(chuàng)新之處在于利用異構(gòu)計算對矩陣廣義逆運算進行加速，同時對 FPGA的OpenCL開發(fā)方法進行探索。既可以拓展FPGA的應用范圍域，也可以 在GPU之外為異構(gòu)計算提供一個新的途徑。第二章基于OpenCL標準的異構(gòu)計算異構(gòu)計算（Heterogeneous computing）是當今半導體行業(yè)的一個熱門詞匯，上到 芯片廠商，下到普通消費者，都對其表現(xiàn)了極大的興趣，應用范圍也是越來越廣泛。 本章將對異構(gòu)

52、計算的框架進行概述，詳細介紹現(xiàn)如今的主流標準OpenCL規(guī)范及 其四種模型，分別闡述GPU和FPGA這兩個異構(gòu)平臺實現(xiàn)OpenCL的機制、特性 及優(yōu)化技術(shù)。2.1異構(gòu)計算概述隨著能源問題的日益突出和性能需求的不斷上升，如今的計算機界已經(jīng)不再 只關(guān)注原始的運算性能，轉(zhuǎn)而重點關(guān)注能效比，即每瓦特功耗所能提供的性能。這種變化將極大影響計算機產(chǎn)業(yè)，甚至顛覆人們以往的認識，首先是微處理器 從單核向多核發(fā)展。假設(shè)原先使用的是一個頻率為f、電壓為V的單核處理器，如 果我們將這個單核處理器換成一個類似的雙核處理器（工作頻率為f/2）,則其回路 電容會提高2.2倍，但是電壓會顯著減少到原來的0.6倍。單核處理器

53、和雙核處理 器的運算性能是一樣的，但是雙核處理器的功耗卻只有單核處理器的0.396倍。正 是由于多核處理器在功耗上的巨大優(yōu)勢，使得多核成為微處理器發(fā)展的趨勢。其次，這些核必須是一樣的嗎？這個就需要考慮專用與通用邏輯的功耗效能。 通用處理器本質(zhì)上必須包括大量的功能單元來響應計算需求，專用處理器也是處 理器，只是由于其只專用于某個特定功能，因而只需包含特定功能所需的功能單元 即可，不會浪費太多的晶體管。因此，芯片越專用，其功耗效能就越好，異構(gòu)才是 趨勢所在?，F(xiàn)代PC的主板上都會有多個插槽，這些插槽都可以安裝多核CPU、內(nèi)存控制 器、圖形處理單元（GPU）等其他帶有PCIe接口的設(shè)備，這些設(shè)備的體系

54、架構(gòu)可 能完全不一樣，它們組合在一起就成了一個異構(gòu)平臺。這些設(shè)備可以同時工作，若 能充分利用它們就可以最大限度地發(fā)揮系統(tǒng)的能力。時至今日，異構(gòu)計算已經(jīng)遍布 計算行業(yè)的每一個領(lǐng)域，上到高端服務器、高性能計算，下到低功耗嵌入式設(shè)備（包 括智能手機和平板機），無所不在。為了與正在發(fā)生的異構(gòu)計算變革同步，發(fā)動一場軟件的并行化革命，我們需要 一個并行軟件行業(yè)。軟件需要兼容多個平臺，既要保證跨開發(fā)商兼容，也要保證跨 代支持，這個行業(yè)才能發(fā)展壯大，解決之道就是建立異構(gòu)計算的一個行業(yè)標準VI。異構(gòu)計算是將計算機系統(tǒng)中的多個計算設(shè)備組成一個混合計算系統(tǒng)，各計算 設(shè)備根據(jù)自己的特長完成相應的子運算任務，共同完成一

55、個大的計算任務，以期達 到高能效比。常見的計算設(shè)備有：CPU、GPU、DSP、FPGA等卸】。因此，作為異 構(gòu)計算的行業(yè)標準就得對各種計算單元進行廣泛支持。目前有好幾種異構(gòu)計算的廠家標準，比如OpenCL、CUDA、C+AMP等。其 中以 OpenCL 最有前景，OpenCL 由 KhionosGroup 創(chuàng)建，已得到了 FPGA、DSP、 GPU等廣大的設(shè)備企業(yè)支持，是一個真正意義上的異構(gòu)計算標準29。OpenCL標準簡介2008年，蘋果在全球開發(fā)者大會上提出OpenCL規(guī)范，通過提供開放免費的 API,推動手機上GPU通用計算的發(fā)展。2009年，KhronosGroup組織在蘋果提案 的基

56、礎(chǔ)上發(fā)布OpenCL 1.0標準，并成立相應的異構(gòu)計算工作組。經(jīng)過5年的發(fā)展， OpenCL標準已經(jīng)陸續(xù)推出4個版本，現(xiàn)在是OpenCL2.0版本。如今，OpenCL陣 容已經(jīng)相當強大，芯片廠商方面有AMD、NVIDIA, Intek ARM等國際巨頭，F(xiàn)PGA 方面有Altera和Xilinx這兩個最強大的FPGA廠商,設(shè)備商有Freescle、IBM Th Apple.三星、NOKIA.摩托羅拉等?？梢哉f是除了微軟之外，基本上所有的大型 相關(guān)企業(yè)都對OpenCL進行了支持，是事實上的異構(gòu)計算行業(yè)標準。OpenCL為異構(gòu)平臺提供了一個通用的編程框架，它提供任務并行和數(shù)據(jù)并行 兩種并行機制，大

57、大擴展了這些異構(gòu)平臺的應用范圍，不再局限于傳統(tǒng)的應用領(lǐng)域。 OpenCL的語言主要由兩部分組成：編寫內(nèi)核程序的類C語言、管理平臺的API。如今大部分的高端計算機系統(tǒng)基本上都引入了高性能的CPU、GPU和其他類 型的加速器。這就為軟件開發(fā)提出了一個內(nèi)在的要求，即必須保證編寫的軟件能夠 在各種異質(zhì)平臺上進行移植，并且能充分合理的利用整個計算機系統(tǒng)的所有資源。OpenCL正是為了滿足用戶的這個要求而設(shè)計的，OpenCL可以很輕松地在多 個平臺之間進行移植。它應用廣泛，從嵌入式消費類軟件的開發(fā)到高性能計算解決 方案，都可以通過其完成。OpenCL提供一個可移植的抽象層模型和APL各設(shè)備 廠商自行開發(fā)設(shè)

58、計底層硬件驅(qū)動，這樣就為OpenCL開發(fā)人員提供了一個與平臺 獨立的開發(fā)工具，以及豐富的平臺開發(fā)庫。與傳統(tǒng)的軟件編程不一樣,OpenCL并不隱藏硬件，而是通過顯式地定義平臺、 上下文來調(diào)度不同的設(shè)備進行工作。因而，OpenCL編程可以分為兩部分：一是主 機程序，負責管理各種加速設(shè)備，為每個加速設(shè)備創(chuàng)建相應的運行環(huán)境，并為之準 備數(shù)據(jù)；二是加速程序，在加速器設(shè)備上運行，采用并行方式執(zhí)行，以獲得很好的 加速性能，這是與傳統(tǒng)的軟件編程最大的不同之處。OpenCL 架構(gòu)OpenCL作為開放性的異構(gòu)計算行業(yè)標準，計算平臺可以是GPU、CPU,也可 以是FPGA、DSP等，OpenCL將這些計算設(shè)備組織成

59、一個統(tǒng)一的混合計算平臺。 OpenCL是一個完整的并行編程框架，為OpenCL開發(fā)人員提供了硬件抽象層API 和面向內(nèi)核的異構(gòu)編程環(huán)境，便于開發(fā)者更方便地開發(fā)和優(yōu)化他們的應用331。OpenCL框架主要包含4個模型，本節(jié)將分別對它們進行介紹：平臺模型執(zhí)行模型內(nèi)存模型編程模型2.3.1平臺模型OpenCL平臺模型定義了異構(gòu)平臺的組織方式。如圖2-1所示，OpenCL平臺 由兩部分構(gòu)成：宿主機和OpenCL設(shè)備。宿主機是異構(gòu)計算的主控機，一般由CPU 扮演該角色，只能存在一個宿主機。OpenCL設(shè)備主要進行數(shù)據(jù)運算操作，作為從 設(shè)備接收宿主機的指令進行數(shù)據(jù)處理，可以是CPU、GPU、DSP或FPG

60、A,以及 OpenCL開發(fā)商支持的任何其他處理器，平臺中可以有多個OpenCL設(shè)備。OpenCL設(shè)備內(nèi)的計算資源由多個計算單元（ComputeUnit,簡稱CU）構(gòu)成， 這些計算單元可以進一步劃分成多個更小的處理單元（Processing Element,簡稱 PE）,處理單元是OpenCL設(shè)備進行計算操作的最小單元。計算單元OpenCL設(shè)備圖2-1 OpenCL平臺模型OpenCL宿主機負責管理所有的外部計算設(shè)備，計算任務通常都由宿主機發(fā)起, 選擇特定的OpenCL外設(shè)并為之建立相應的執(zhí)行環(huán)境，將計算任務和數(shù)據(jù)通過PCIe 接口發(fā)送給OpenCL外設(shè),外設(shè)會同時調(diào)用內(nèi)部的多個計算單元對數(shù)據(jù)進