基于异构计算的矩阵广义逆算法研究及实现

1、!七状旧域I X富UNIVERSITY OF ELECTRONIC SC I ENCE AND TECHNOLOGY OF CHINA硕士学位论文MASTER THESIS论文题目基于异构计算的矩阵广义逆算法研究及实现学科专业通信与信息系统学 号201121010401作者姓名范兴山指导教师 李广军 教授独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均

2、已在论文中作了明 确的说明并表示谢意。作者签名：力事山 日期：籍隹&月V日论文使用授权本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘, 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。（保密的学位论文在解密后应遵守此规定）作者签名：么老小导师签名:日期：年4月3日分类号密级UDC注 1学位论文基于异构计算的矩阵广义逆算法研究及实现（题名和副题名）范兴山（作者姓名）指导教师李广军 教授电子科技大学（姓名、职称、单位名称）

3、申请学位级别 硕士 学科专业通信与信 息系统提交论文日期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摘要广义逆矩阵理论不仅是许多数学分支的基本工具，更是在经济学、信息处理、 自动控制、通信学、密码学和统计学等应用学科中都有着广泛的应用。因此，提升 广义逆矩阵的计算性能有着非常大的实用价值，然而传统的CPU串行计算对此却 无能为力。近年来，以OpenCL计算架构为代表的异构计算发展迅速，己广泛应用于多个 领域，在图像视频处理、密码学等领域常用来进行运算加速，广义逆矩阵也可以通 过OpenC

5、L这种异构计算方式提升其计算性能。本文以异构计算为背景，以OpenCL为编程架构，实现广义逆矩阵的运算加 速。本文首先对OpenCL规范作了简短介绍；基于GPU和FPGA的硬件架构，分 别分析它们的OpenCL实现机制；由于GPU和FPGA在硬件架构与实现机制上是 完全不一样的，它们的性能优化技术也迥然不同，因而分别对它们的优化技术进行 分析。本文以运算所需的加法和乘法次数为指标，对三种常用的广义逆矩阵算法的 计算复杂度进行分析，解方程法的计算量要略高于其他两种算法。然而通过基于异 构计算的实现复杂度分析，在最小任务数、控制流、运算资源等关键指标上，解方 程法要明显好于另外两种算法。综合计算复

6、杂度和实现复杂度的分析结果，解方程 法能获得更好的异构计算性能。因此本文以解方程法为基础设计一套基于异构计 算的实现方案，在最优的并行度基础上，对方案中的多个模块进行并行化处理，并 设计相应的同步点以保证数据的一致性。依据OpenCL的运行机制，分别对存储访 问部分和数据处理部分进行深入优化，以提高算法的运算性能，并用MATLAB对 该方案进行验证。本文分别在GPU和FPGA上实现该方案，并针对它们各自的架构特点，制定 不同的优化策略和测试方案。测试结果表明：在计算误差方面，GPU由于其内部 的浮点运算单位精度较高，其最大误差低至10-7级；而FPGA由于其内部的乘法 器位宽仅为18位，其误差

7、相对较大，最大误差在IO；级。与MATLAB标准函数 运行时间相比，GPU平台凭借其成熟的开发理论和巨量的计算资源，加速比达到 T 1909； FPGA平台由于其开发理论不成熟，只获得34的加速比，但还有着巨大 的提升空间。关键词：矩阵广义逆，异构计算，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国内外研究现状2 HYPERLINK l bookmark59 o Curren

19、t Document 1.2.1矩阵广义逆2 HYPERLINK l bookmark62 o Current Document 1.2.2异构计算3 HYPERLINK l bookmark65 o Current Document 13本文的结构安排4 HYPERLINK l bookmark71 o Current Document 第二章 基于OpenCL标准的异构计算6 HYPERLINK l bookmark74 o Current Document 异构计算概述6 HYPERLINK l bookmark77 o Current Document OpenCL标准简介7 HYPE

20、RLINK l bookmark81 o Current Document OpenCL 架构8 HYPERLINK l bookmark85 o Current Document 23.1平台模型8 HYPERLINK l bookmark88 o Current Document 23.2执行模型9 HYPERLINK l bookmark91 o Current Document 2.3.3内存模型10 HYPERLINK l bookmark94 o Current Document 23.4编程模型12 HYPERLINK l bookmark97 o Current Documen

21、t 2.4基于GPU的异构平台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优化技术15 HYPERLINK l bookmark114 o Current Document 2.5基于FPGA的异构平台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优化技术22 HYPERLINK l bookmark146 o Current Document 2.6本章小结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基于异构计算的实现复杂度分析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本章小结45 HYPERLINK l bookmark255 o Current Document 第四章基于异构计算的矩阵广义逆实现方案设计46 HYPERLINK l bookmark258 o Current Document 4.1基于异构计算的方案设计46 HYPERLINK l bookmark261 o Curre

26、nt Document 4.2算法的并行化设计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数据同步点设计54 HYPERLINK l bookmark289 o Current Document 43基于异构计算的算法优化56 HYPERLINK l bookmark292 o Current Documen

27、t 4.3.1数据处理优化56 HYPERLINK l bookmark295 o Current Document 4.3.2存储访问优化58 HYPERLINK l bookmark298 o Current Document MATLAB 验证61 HYPERLINK l bookmark301 o Current Document 4.5本章小结64 HYPERLINK l bookmark304 o Current Document 第五章基于OpenCL的矩阵广义逆实现及测试66 HYPERLINK l bookmark307 o Current Document 5.1开发平台简

28、介66 HYPERLINK l bookmark312 o Current Document 5.2基于OpenCL的方案实现68 HYPERLINK l bookmark315 o Current Document 5.2.1宿主机程序设计69 HYPERLINK l bookmark324 o Current Document GPU内核实现70 HYPERLINK l bookmark330 o Current Document 5.23 FPGA内核实现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测试结果及性能分析78 HYPERLINK l bookmark350 o Current Document 5.4本章小结85 HYPERLINK l bookmark353 o Current Document 第六章总结与展望86 HYPERLINK l bookmark356 o Current Document 6.1本文工作总结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异构计算示意图2图2-1 OpenCL平台模型8图2-2全局ID、局部ID和工作组索引之间的关系10图2-3 OpenCL内存模型11图2-4现代GPU架构13图2-5 AMD GPU的内存架构14图2-6顺序读取模式16图2-7联合读取模式16图2-8 LDS组织结构17图2-9FPGA 结构18图2-10 FPGA 的 OpenCL 架构19图2-11 4端口的本地内存2

31、1图2-12本地内存配置21图3-1子任务无法组合35图3-2子任务可以组合36图4-1总体实现方案46图4-2 OpenCL设备上的线程映射关系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数据同步点位置55图4-13 MATLAB仿真流程图61图4-14处理前M-1列62图4-15最大绝对误差64图4-16最大相对误差64

32、图5-1开发平台66图 5-2 DE4-530 视图68图 5-3 宿主机程序流程69图5-4 FPGA实现框图73图5-5解矩阵方程模块74图5-6测试方案框图76图5-7 GPU的最大绝对误差78图5-8 FPGA的最大绝对误差79图5-9 CPU串行程序的执行时间79图5-10 GPU平台的总计算时间80图5-11 GPU平台的平均计算时间81图5-12 GPU平台的加速比81图5-13 FPGA平台的循环展开测试结果82图5-14 FPGA平台的总计算时间83图5-15 FPGA平台的平均计算时间83图5-16 FPGA平台的加速比84表目录 TOC o 1-5 h z 表2-1宿主机

33、和设备对内存的管理11表3-1行变换的计算量30表3-2列变换的计算量30表3-3计算矩阵B的运算量32表3-4计算（时AG 的运算量32表3-5初等变换法中各子任务的可选并行度37表3-6初等行变换中的if判断个数38表3-7初等行变换需要的同步点38表3-8初等行变换单个线程的加法器需求量38表3-9计算QXP的加法器需求量39表3-10初等行变换中单个线程的加法器需求量39表3-11计算QXP的乘法器需求量39表3-12满秩分解法中各子任务的可选并行度40表3-13满秩分解法的if判断个数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判断个数43表3-23解矩阵方程需要的同步点43表3-24解矩阵方程中单个线程的加法器需求量44表3-25矩阵乘法的加法器需求量44表3-26解矩阵方程中单个线程的乘法器需求量44表3-27矩阵乘法的乘法器需求量44表4-1解方程法的子任务并行度48表4-2数据处理优化减少的运算量58表4-3全局存储优化前后的访问次数59表4-4全局存储优化前后

35、的访问时间估计59表4-5添加私有变量后的访存优化效果60表4-6本地存储的优化结果60表4-7访存优化结果61表4-8GPU平台的访存优化结果72表5-1硬件环境66表5-2软件环境67表5-3 AMD HD 7950的关键指标67表5-4 EP4SGX530C2 逻辑资源68表5-5 DDR参数68表5-6 GPU测试集77表5-7 FPGA展开次数测试77表5-8 FPGA测试集78表5-9测试案例所需的线程数80表5-10 FPGA平台综合结果84缩略词表英文缩写英文全称中文注释CPUCentral Processing Unit中央处理器GPUGraphic Processing U

36、nit图形处理器APUAccelerated Processing Unit加速处理器GPGPUGeneral Purpose Graphic Processing Unit通用图形处理器FPGAField Programmable Gate Array现场可编程门阵列DSPDigital Signal Processor数字信号处理器LTELong Term Evolution3GPP长期演进项目OFDMOrthogonal Frequency Division Multiplexing正交频分复用DDRDouble Data Rate双倍速率SDRAMCUCompute Unit计算单元P

37、EProcessing Element处理单元IPIntellectual Property知识产权SIMDSingle Instruction Multiple Data单指令多数据流SPMDSingle Program Multiple Data单程序多数据LUTLook-Up Table查找表RAMRamdom Access Memory随机存取存储器FIFOFirst Input First Output先入先出队列第一章绪论1.1研究背景任何一门学科的产生与发展都跟它的应用是密切相关的，广义逆矩阵也是如 此。针对普通逆矩阵只对非奇异方阵有效的缺点，Moore, E.H在1920年提出

38、广 义逆矩阵的概念及定义，奠定了广义逆矩阵的发展基础。正是可应用的场景广 泛，才使得广义逆矩阵这一学科得到了快速的发展。半个多世纪以来，广义逆矩阵已广泛应用于多个领域和学科。在控制理论及 其应用中，广义逆矩阵常用于对随机和确定性系统的滤波、固定点平滑、固定滞 后平滑与预报中，以得到离散线性随机系统和定常系统状态的最优线性无偏估计 和无差估计。在神经网络计算领域，Kohonen模型（最优线性联想神经网络）的 样本集上误差为零，可求取既简单又误差小的矩阵W是困难的，若用广义逆矩 阵来进行求解，则可以很好地解决该问题。在通信领域中，广义逆矩阵的应用也是非常广泛。比如在秘钥协议中，为了 增强秘钥的安全

39、性和实用性，常采用广义逆矩阵来生成秘钥。在OFDM系统的 信道估计中，由于其信号矩阵并不总是方阵，因此也需要用到广义逆矩阵来求解 信道的冲击响应和频率函数闵。由于广义逆矩阵的实现较为复杂，人们一般将目光都集中在纯算法的研究上, 以期提高广义逆矩阵的计算效率4。然而，提高广义逆矩阵的计算效率还有另外 一种方法，就是通过具体实现方案的加速，异构计算就是这样一种加速手段。异构计算是将多个不同类型的计算单元组成一个混合计算系统，有效利用计 算资源，提高计算效率，如图1-1所示。在电脑中，通过PCIe接口可以将CPU、 GPU、FPGA等多个异构计算设备连接在一起，这些计算设备协同作业，共同完 成计算任

40、务，获得强大的加速能力，从而让整个系统达到最佳的能效比和性能。近年来，由于人们对能耗越来越关注，使得异构计算发展非常迅速，巳广泛 应用于图像视频处理领域。文献6通过异构计算，有效调用GPU、FPGA等多个 平台对动态场景中的光线进行实时跟踪绘制，以实现高质量的全局光照明效果。 文献7通过调用GPU对二维图像的处理和显示进行加速，相比CPU能获得200 以上的加速比，即使是与专业的NVIDIA GPU相比也能达到5的加速比。本文采用异构计算的方式实现广义逆矩阵算法，以期获得较好的加速性能， 同时对FPGA平台的OpenCL开发方法进行探索。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异构i I算示意图1.2国内外研究现状1.2.1矩阵广义逆在研究广义逆矩阵领域，Moore, E.H是公认的第一人，早在1920年，

42、其在 美国数学会通报上便刊文提出了广义逆矩阵的概念及定义，但是却并没有引起人 们足够的重视。直到到1955年，英国学者PenroseR在剑桥哲学会学报上了发表 了著名论文广义逆矩阵，Pemose R在文中采用了更简便实用的定义，即是 Moore-Pemose逆矩阵，这种定义得到了人们的广泛认可。在Moore-Penrose逆矩 阵的基础上，研究者们针对不同的应用环境，又定义了多种广义逆矩阵。比如, Bott和Duffin基于电网络领域提出了 Bott-Duffin逆矩阵，Erdelyi在研究Abel群 时提出了群逆的概念，其他还有加权广义逆矩阵和a 一8广义逆矩阵等凶。随着广义逆矩阵的研究不断

43、深入，其应用领域越来越广，从数值分析、数学 规划到控制论、博弈论和计量经济学等领域都需要用到广义逆矩阵。DawsonE在 1997年将广义逆矩阵引入密码学，用于秘钥协商。在2005年，陈曦等一些学者 对广义逆矩阵在通信中的应用进行研究，成功将广义逆矩阵应用于OFDM系统 的信道估计网。在计算广义逆矩阵方面，人们已提出了多种算法，如常用的满秩分解法、递 推法、奇异值分解法和初等变换法等。在这些常用方法的基础上，近年来又有一 些学者提出一些新的技术方法，如半迭代法和分裂迭代法等。目前针对广义逆矩阵的研究大部分都是理论性的探索，其中一个研究方向是 将广义逆矩阵应用到不同的领域，甚至在该特定领域中提出

44、一种广义逆矩阵的变 形；另一个研究方向是如何计算广义逆矩阵，主要停留在算法层面，并没有针对 具体平台进行实现优化。因此，本文对广义逆矩阵算法在GPU和FPGA平台上分别进行实现及优化 具有实际的意义。1.2.2异构计算异构计算并不是一个崭新的领域，在上世纪八十年代就巳诞生出“异构计算” 这个概念。不过，早期的异构计算并不是基于单机系统，而是以高速互联网络为 基础，组织多台计算机进行并行运算，以获得最大的性能，这种方式是属于网络 异构计算（NHC）。在这种结构中，程序被拆分成许多相对较为独立的子任务， 这些子任务分别在不同的计算机上运行，通过消息传递来实现数据共享。然而，异构计算还有另外一个分支

45、，那就是单机异构计算，将单个计算机系 统中的CPU、GPU、DSP和FPGA等计算资源整合在一起，协作完成计算任务 的一种模式。单机异构计算有着巨大的应用前景，比如图像视频加速a、3D技 术以及手机等其他一些手持终端设备。其中，CPU与GPU协作运算的研究历史比较久远，NVIDIA在2006年就提 出了 GPGPU概念，期望通过GPU运算进行应用加速，为此还提出了一套完整 的解决方案CUD Ao CUDA内含API和C语言编译器等，CPU通过调用显卡内 的流处理器进行数学运算。另一家GPU厂商AMD对于异构计算的解决方案则 是将GPU内核集成到CPU芯片上，如今我们所熟知的APU就是其最初方案

46、， 目前其发展迅速，已基本搭建起了异构计算的开放生态环境。2008年，在世界开发者大会上诞生了第一个通用的异构计算标准OpenCL, 该标准免费开放，任何厂商或者学者都可以参与它的研究开发。与其他的异构计 算标准不一样,OpenCL提供了统一的编程环境,OpenCL程序可以在CPUGPU FPGAM和DSP等计算设备上轻松地进行移植操作，以实现通用的异构计算编 程。由于各个异构平台的架构完全不同，OpenCL并不将算法映射到具体的平台 硬件上，而是作为一种抽象的并行编程框架，通过提供开发语言、API库和运行 系统来支持软件开发U3。目前基于CPU+GPU的异构开发已进行了大量的研究，已有许多应

47、用采用 OpenCL在GPU上进行实现，并获得了很好的加速性能，如图像模糊化处理、加 密算法ME、动态场景光线跟踪、矩阵分解Um*等。在计算机系统中，除了 GPU可以与CPU 一起构成异构系统外，还有许多其 他加速设备也可以与CPU构成异构系统，比如FPGA和DSP等。许多硬件设备 厂商都宣称对异构计算进行支持，然而目前除了 GPU外，就只有FPGAT商进 行了实际的支持。在2013年，Altera和Xilinx】?。相继推出了基于OpenCL异构 计算的开发平台和开发软件，不过只有特定的几款开发板支持异构开发。目前，Altera和Xilinx均提供了相关的OpenCL开发套件，并进行了大力

48、推广，因此基于FPGA的异构开发已逐渐加速，不少学者对图像视频压缩的、数 学运算、通信算法等在FPGA上的实现进行了研究，比如FFT、矩阵乘法SI、 Turbo编解码四、LDPC编解码网等。总体来说，异构计算在GPU平台上已经有了比较充分的研究，但大部分研 究是基于图像视频类应用，对于通信、科学计算等其他一些应用领域则少有研究。 在FPGA平台上的研究才刚刚开始，由于其平台的特殊结构，并不能照搬GPU 平台上的开发理论，需要研究其特有的开发方法。1.3本文的结构安排本文的拟研究方向是基于异构计算的矩阵广义逆算法研究及实现。将以移动 通信为背景，恰当选择广义逆矩阵的各项参数。在现有的一些广义逆矩

49、阵算法基 础上，分析比较几种常用算法的计算复杂度，选择其中适合于采用异构计算实现 的算法。以所选算法为基础，制定一套基于异构计算的实现方案，对方案进行并 行化处理和深入优化，以期获得较高的异构运算性能，并用MATLAB对方案进 行功能仿真。最后，在GPU和FPGA这个两个架构迥异的异构平台上分别实现 该方案，制定不同的优化策略和多套测试方案，结合测试结果对比并分析它们的 性能。本文一共分为六章，各章节的结构安排如下：第一章主要介绍了广义逆矩阵的广泛应用，对异构计算和广义逆矩阵的国内 外发展现状进行了介绍，并提出了它们所面临的一些问题。第二章则是对异构计算进行阐述，详细介绍主流的异构计算标准Op

50、enCL规 范及其四种模型，阐述FPGA和GPU这个两个异构平台的OpenCL机制，讨论 它们各自的OpenCL优化技术。第三章首先介绍广义逆矩阵的概念及性质，并着重介绍了初等变换法、解方 程法和满秩分解法这三种常用算法，最后详细分析这三种方法的计算复杂度和基 于异构计算的实现复杂度。第四章在解方程组法的基础上，设计一套基于异构计算的实现方案，对方案 及其中的关键模块进行并行化处理，并按照数据处理和存储访问进行深入优化, 最终用MATLAB对该计算方案进行总体仿真。第五章首先介绍了方案的实现平台，在GPU和FPGA平台上分别进行实现 和优化，根据它们的平台特点分别制定多套测试方案，结合测试结果

51、进行性能分 析和比较。第六章是对本文工作取得的工作和研究成果进行总结，指出目前采用 OpenCL对FPGA平台进行开发的短板，对矩阵广义逆和基于OpenCL的FPGA 开发未来的研究方向进行展望。本文的创新之处在于利用异构计算对矩阵广义逆运算进行加速，同时对 FPGA的OpenCL开发方法进行探索。既可以拓展FPGA的应用范围域，也可以 在GPU之外为异构计算提供一个新的途径。第二章基于OpenCL标准的异构计算异构计算（Heterogeneous computing）是当今半导体行业的一个热门词汇，上到 芯片厂商，下到普通消费者，都对其表现了极大的兴趣，应用范围也是越来越广泛。 本章将对异构

52、计算的框架进行概述，详细介绍现如今的主流标准OpenCL规范及 其四种模型，分别阐述GPU和FPGA这两个异构平台实现OpenCL的机制、特性 及优化技术。2.1异构计算概述随着能源问题的日益突出和性能需求的不断上升，如今的计算机界已经不再 只关注原始的运算性能，转而重点关注能效比，即每瓦特功耗所能提供的性能。这种变化将极大影响计算机产业，甚至颠覆人们以往的认识，首先是微处理器 从单核向多核发展。假设原先使用的是一个频率为f、电压为V的单核处理器，如 果我们将这个单核处理器换成一个类似的双核处理器（工作频率为f/2）,则其回路 电容会提高2.2倍，但是电压会显著减少到原来的0.6倍。单核处理器

53、和双核处理 器的运算性能是一样的，但是双核处理器的功耗却只有单核处理器的0.396倍。正 是由于多核处理器在功耗上的巨大优势，使得多核成为微处理器发展的趋势。其次，这些核必须是一样的吗？这个就需要考虑专用与通用逻辑的功耗效能。 通用处理器本质上必须包括大量的功能单元来响应计算需求，专用处理器也是处 理器，只是由于其只专用于某个特定功能，因而只需包含特定功能所需的功能单元 即可，不会浪费太多的晶体管。因此，芯片越专用，其功耗效能就越好，异构才是 趋势所在。现代PC的主板上都会有多个插槽，这些插槽都可以安装多核CPU、内存控制 器、图形处理单元（GPU）等其他带有PCIe接口的设备，这些设备的体系

54、架构可 能完全不一样，它们组合在一起就成了一个异构平台。这些设备可以同时工作，若 能充分利用它们就可以最大限度地发挥系统的能力。时至今日，异构计算已经遍布 计算行业的每一个领域，上到高端服务器、高性能计算，下到低功耗嵌入式设备（包 括智能手机和平板机），无所不在。为了与正在发生的异构计算变革同步，发动一场软件的并行化革命，我们需要 一个并行软件行业。软件需要兼容多个平台，既要保证跨开发商兼容，也要保证跨 代支持，这个行业才能发展壮大，解决之道就是建立异构计算的一个行业标准VI。异构计算是将计算机系统中的多个计算设备组成一个混合计算系统，各计算 设备根据自己的特长完成相应的子运算任务，共同完成一

55、个大的计算任务，以期达 到高能效比。常见的计算设备有：CPU、GPU、DSP、FPGA等卸】。因此，作为异 构计算的行业标准就得对各种计算单元进行广泛支持。目前有好几种异构计算的厂家标准，比如OpenCL、CUDA、C+AMP等。其 中以 OpenCL 最有前景，OpenCL 由 KhionosGroup 创建，已得到了 FPGA、DSP、 GPU等广大的设备企业支持，是一个真正意义上的异构计算标准29。OpenCL标准简介2008年，苹果在全球开发者大会上提出OpenCL规范，通过提供开放免费的 API,推动手机上GPU通用计算的发展。2009年，KhronosGroup组织在苹果提案 的基

56、础上发布OpenCL 1.0标准，并成立相应的异构计算工作组。经过5年的发展， OpenCL标准已经陆续推出4个版本，现在是OpenCL2.0版本。如今，OpenCL阵 容已经相当强大，芯片厂商方面有AMD、NVIDIA, Intek ARM等国际巨头，FPGA 方面有Altera和Xilinx这两个最强大的FPGA厂商,设备商有Freescle、IBM Th Apple.三星、NOKIA.摩托罗拉等。可以说是除了微软之外，基本上所有的大型 相关企业都对OpenCL进行了支持，是事实上的异构计算行业标准。OpenCL为异构平台提供了一个通用的编程框架，它提供任务并行和数据并行 两种并行机制，大

57、大扩展了这些异构平台的应用范围，不再局限于传统的应用领域。 OpenCL的语言主要由两部分组成：编写内核程序的类C语言、管理平台的API。如今大部分的高端计算机系统基本上都引入了高性能的CPU、GPU和其他类 型的加速器。这就为软件开发提出了一个内在的要求，即必须保证编写的软件能够 在各种异质平台上进行移植，并且能充分合理的利用整个计算机系统的所有资源。OpenCL正是为了满足用户的这个要求而设计的，OpenCL可以很轻松地在多 个平台之间进行移植。它应用广泛，从嵌入式消费类软件的开发到高性能计算解决 方案，都可以通过其完成。OpenCL提供一个可移植的抽象层模型和APL各设备 厂商自行开发设

58、计底层硬件驱动，这样就为OpenCL开发人员提供了一个与平台 独立的开发工具，以及丰富的平台开发库。与传统的软件编程不一样,OpenCL并不隐藏硬件，而是通过显式地定义平台、 上下文来调度不同的设备进行工作。因而，OpenCL编程可以分为两部分：一是主 机程序，负责管理各种加速设备，为每个加速设备创建相应的运行环境，并为之准 备数据；二是加速程序，在加速器设备上运行，采用并行方式执行，以获得很好的 加速性能，这是与传统的软件编程最大的不同之处。OpenCL 架构OpenCL作为开放性的异构计算行业标准，计算平台可以是GPU、CPU,也可 以是FPGA、DSP等，OpenCL将这些计算设备组织成

59、一个统一的混合计算平台。 OpenCL是一个完整的并行编程框架，为OpenCL开发人员提供了硬件抽象层API 和面向内核的异构编程环境，便于开发者更方便地开发和优化他们的应用331。OpenCL框架主要包含4个模型，本节将分别对它们进行介绍：平台模型执行模型内存模型编程模型2.3.1平台模型OpenCL平台模型定义了异构平台的组织方式。如图2-1所示，OpenCL平台 由两部分构成：宿主机和OpenCL设备。宿主机是异构计算的主控机，一般由CPU 扮演该角色，只能存在一个宿主机。OpenCL设备主要进行数据运算操作，作为从 设备接收宿主机的指令进行数据处理，可以是CPU、GPU、DSP或FPG

60、A,以及 OpenCL开发商支持的任何其他处理器，平台中可以有多个OpenCL设备。OpenCL设备内的计算资源由多个计算单元（ComputeUnit,简称CU）构成， 这些计算单元可以进一步划分成多个更小的处理单元（Processing Element,简称 PE）,处理单元是OpenCL设备进行计算操作的最小单元。计算单元OpenCL设备图2-1 OpenCL平台模型OpenCL宿主机负责管理所有的外部计算设备，计算任务通常都由宿主机发起, 选择特定的OpenCL外设并为之建立相应的执行环境，将计算任务和数据通过PCIe 接口发送给OpenCL外设,外设会同时调用内部的多个计算单元对数据进