毕业设计（论文）-图像处理算法的并行程序设计.doc

中北大学2015届毕业设计说明书目 录1 绪论11.1 课题研究背景11.2 并行处理的意义21.2.1 提升计算速度21.2.2 提升计算精度21.2.3 满足时效性要求21.3 图像并行处理的研究现状31.3.1基于多核的图像并行研究31.3.2 基于GPU的图像并行研究41.4 本文的主要研究方法与内容51.5论文的结构与安排62 并行编程模型概述72.1 多核CPU并行库OpenMP72.1.1 OpenMP执行模式72.1.2 OpenMP编程模型72.1.3 OpenMP任务调度82.1.4 OpenMP数据环境控制102.1.5 OpenMP编程约束102.2 CUDA并行模型概述112.2.1 CUDA模型简介122.2.2 CUDA程序结构122.2.3 CUDA线程结构122.2.4 CUDA内存模型142.2.5 CUDA硬件结构152.3 本章小结153 图像处理算法的并行程序设计163.1 中值滤波并行算法设计163.1.1 中值滤波基本原理163.1.2 中值滤波的OpenMP算法设计17 3.1.3 中值滤波的CUDA算法设计183.2 Laplace锐化并行算法设计203.2.1 Laplace锐化基本原理203.2.2 Laplace锐化的OpenMP算法设计213.2.3 Laplace锐化的CUDA算法设计213.3 修正的各向异性扩散PM模型223.3.1 各向异性扩散Perona-Malik模型223.3.2 Perona-Malik模型计算233.3.3 修正的各向异性扩散PM模型243.3.4 修正的PM模型CUDA算法设计263.4本章小结284 实验结果分析294.1 实验环境294.1.1 实验硬件环境294.1.2 实验软件环境294.2 并行算法的性能评价294.2.1 运行时间294.2.2 加速比294.3 实验结果304.3.1 中值滤波结果304.3.2 Laplace锐化324.4 实验结果分析344.4.1 OpenMP对于CPU的加速比344.4.2 CDUA对于CPU的加速比364.5 本章小结385 总结与展望395.1课题总结395.2课题展望39参考文献40致谢42全套设计加扣 3012250582第 III 页,共III页1 绪论1.1 课题研究背景 数字图像处理技术(Digital Image Processing)是随着计算机科学和大规模集成电路的发展而兴起的一门具有跨学科性的工程学科，其涵盖了许多学科的理论，综合性较强，应用前景广泛，对人类社会的进步产生了重大的影响。 计算机对图像进行处理最早可以追溯到20世纪60年代，位于美国加利福利亚的喷气式推进实验室在某空间项目中利用计算机技术对拍摄的月球图像进行了处理1。此后，数字图像处理技术开始在环境监测、测控遥感、航天技术、医学影像等科学领域受到重视和应用，并得到了快速的发展。例如磁共振成像技术的产生与应用，使得医生可以获取病人身体内部的高清晰图像，其在医学诊断领域做出了巨大的贡献。随着数字图像处理技术在各个社会层面的应用，人们越来越注意到数字图像处理技术的前景和优势，并将这项技术移植于其他领域，使得数字图象处理技术开始与其他学科融合并发展。 随着现代计算机技术的普及与发展，以及数字图像处理技术的应用面越来越宽泛，人们对数字图像处理提出了更高的要求。例如图像的实时采集处理，大规模图像的快速处理等。例如，在空间遥感技术领域中，随着对于图像的精确度要求的提升，图像的数据量也越来越大，并且处理的过程也越来越复杂；在机械控制或是自动化行业中，对于图像的快速处理与实时响应要求越来越迫切。从上述情况可知，如何快速完成数字图像的处理已经显然成为了制约这些领域一个瓶颈。特别是针对大规模图像以及处理高复杂度的算法，图像处理性能的问题就越发突出。 为了提升数字图像处理的速度，人们提出了很多的办法。一方面，在现有的硬件基础上对算法进行优化，减少运算过程中产生的中间量，或是压缩待处理图像，减少图像处理的数据量。另一方面，随着计算机技术与电子制造业的升级与发展，计算机对于数据的并行处理显得游刃有余。随着多核CPU技术的普及与可编程GPU的产生，各大软件厂商与硬件厂商相互协作，推出了各种实现并行处理的相关技术。例如OpenMP架构评审委员会牵头提出的OpenMP，APPLE牵头提出的OpenCL，显卡制造商NVIDIA提出的适用于NVIDIA显卡的CUDA技术等。数字图像处理算法以像素点或视频帧作为处理对象，具有很强的并行性，特别适用于并行处理技术。将并行计算技术应用到图像处理中，将会大幅提升图像处理的效率与性能，具有广泛深远的意义2。1.2 并行处理的意义 现代计算机的工作速度相比于10年前，速度得到了极大的提升，但是仍然无法满足大数据的时代。虽然开发者会针对某些问题进行大量的优化，但是现有的计算机设备仍需要工作相当长的时间去处理大量的数据。传统的串行处理无法完全利用现有的硬件设备，但并行处理能够在完全利用硬件设备的同时极大的提升处理速度，获得更高的计算性能。并行处理具有以下几个方面的意义。1.2.1 提升计算速度 随着现代电子制造业的升级与发展，多核CPU与可编程GPU的产生为并行处理提供了硬件基础。并行处理在充分利用硬件的同时，可以极大的提升处理速度，缩短计算时间。例如，人类染色体所携带的信息量是十分巨大的，采用传统的串行处理计算方式将会耗费大量的时间，如果能够将并行计算应用到医学领域，则会大幅度缩减处理时间，并可能会带动医学界的发展。1.2.2 提升计算精度 在大型的工程或是科学计算中，为了提升计算精度，往往需要考量更多的参数并将其加入计算中，这将会使得计算的数量呈现几何式的增长，而这种大规模的复杂计算往往是任何单机系统无法处理的，故使用多机系统处理才可。例如，对大型油气藏进行数值模拟时，为了使结果更具备准确性，对于具有上万口油井的油田，在模拟时每口油井至少取样3000个点，其模拟过程中的样本则会高达几千万口，处理如此庞大的数据是一般设备难以实现的，所以需要使用并行系统进行计算。1.2.3 满足时效性要求无论是大型的工程或是科学计算，还是现代工业中，对于数据的快速处理以及实时响应都有着很强的需求。例如，在气象预报方面，就需要处理速度快、容量高的高性能并行计算设备。为了提升气象预报的精准度，需要采样大量的数据。一般会在大气层方向以及经、纬度三个方向采取网格点。 例如，为了进行未来一到十天的天气预报，可能需要处理600多万个网格点的数据，其数据总量高达20T，并要求在几小时内处理完毕3。传统的单机处理是无法完成如此大量的数据，所以必须使用高性能并行设备才可能实现。1.3 图像并行处理的研究现状对于数据的并行处理，到目前为止，国内外对并行研究均取得了不同程度的成果。美国和日本对于超级计算机的研发十分重视，其在相关方面的投入资金高达几十亿美元。我国也对高性能计算的十分重视，各大院校与科研所都对高性能计算进行研发，国家也投入了相当大的资金支持。而在GPU并行计算领域，国外利用GPU并行计算实现了模型构建、大规模数据处理、方程求解等4。在国内，中科院自行研发的超级计算机，实现了每秒千万亿次浮点运算，国防科大研发的“天河一号”超级计算机排名世界第一，以及目前正在研发的“天河二号”超级计算机，充分的说明了我国对于高性能并行计算的重视。但总的来说,对于并行计算领域来说，我国仍处于相对落后的状态，仍有许多内容需要我们进行研究。 由于图像本身具备大量数据，并且图像处理算法复杂度越来越提升。因此，将图像处理技术与并行技术相结合将能够实现大规模图像数据处理的快速化。现在常见的图像并行处理研究有两类，分别是基于多核的图形并行处理研究6和基于GPU的图形并行处理研究7。1.3.1基于多核的图像并行研究所谓多核技术，是指在一枚处理器中集成两个或多个完整的计算引擎(内核)，多核技术可以在同一时间完成多个任务，也就是我们所说的并行处理6。早期，对于CPU的性能提升无非是通过提高主频、超标量、超流水线等方式，但是这些提升将会带来高功耗、高发热、软件兼容性等问题。于是各大CPU制造厂商(Intel、AMD等)开始向着多核构架与超线程技术(Hyper-Threading，简称HT技术)发展，在同一个CPU内放置多个核心(如图1.1所示，分别是AMD和Intel早期双核构架图)。多核处理器以其独特的体系结构，在降低功耗的同时，提升了处理器的性能与工作效率，成为了CPU后续发展的方向，同时也为CPU实现并行处理提供了硬件支持。目前市场上常见的处理器已经达到四核、八核甚至十六核。为了迎接多核时代的到来，软件开发者不能仅仅沉浸于原有的单核心串行执行，而应是充分利用多核心的优势，提升算法执行能力。对于开发者而言，手工创建线程将会增加开发负担。对此，各大软件厂商相互协作，提出了许多在多核环境下的并行算法库，降低了多核并行编程的难度。例如OpenMP、TBB等并行库。但由于并行算法库可能存在着分配不均的问题，所以人们对于负载平衡和任务调度的问题也越来越关注。文献8,9中对于多核构架下的多线程负载的平衡问题进行了一些讨论。图1.1 AMD Opteron双核构架示意图(左图)以及Intel奔腾至尊版双核构架示意图(右图)对多核并行处理的研究,也为传统多机集群系统的研发提供了新的思路10。目前，基于多核集群混合编程模型的被很多学者研究。随着硬件的更新换代，多核集群则会越来越常见。目前，应用多核技术对图像并行处理的技术手段相对成熟，并取得了一定的研究成果。文献11利用OpenMP技术在多核平台上实现了图像的空间域增强，并得到了在多核并行处理下，空间域增强处理效率得到了相当的提升。文献12,13则是利用多核并行技术实现对图像的边缘检测，取得了良好的加速效果。1.3.2 基于GPU的图像并行研究图形处理单元(Graphic Processing Unit)，是一个与CPU相对应的概念。GPU概念的产生，源于英伟达公司在1999年发布旗下高性能显卡GF256时所提出的23。随着微软开发的视窗系统的推广普及，显卡开始逐步的出现在计算机中。这些显卡分担了部分的CPU计算，并能获得更好的显示效果，起到了很好的辅助效果。20世纪90年代中期，随着3D图形技术的普及与各种游戏的推广，显卡制造厂商也逐步提升技术，随后各种图形处理芯片开始不断产生，并进入到了高速发展的时期。现代的GPU发展速度已经达到了每912月就更新换代一次，性能提升来得比CPU还快。显卡(GPU)是计算机系统中专门对图像进行处理和显示，其最初设计的主要目的是替代CPU执行图像处理过程中涉及到的大量计算，如果这些全部在CPU上执行的话，则会严重形象计算机的性能。在早期，GPU通过内部的像素着色器对数据进行计算。像素着色器通过对输入的颜色信息、纹理坐标信息等属性来进行合成，并计算得出最终的颜色值14。由于输入的颜色和纹理的计算是开发者自行定义的，因此输入的“颜色”实际上可以是任何数据，并将着色器计算的结果读取，实现GPU的计算。 由于早期对GPU编程实现计算十分复杂，极大的限制了GPU计算的发展。2006年，显卡制造公司NVIDIA推出了一款基于自家GPU的并行编程模型统一计算构架模型(Computer Unified Device Architecture，即CUDA)，该技术的提出使得GPU编程变得更加容易，并拥有良好的并行执行能力。2009年，苹果公司提出了开放运算语言（Open Computer Language)跨平台标准库并行编程的规范，其目的是为开发者提供一个通用的接口函数便于开发并行计算。该规范不仅可以应用到核心处理器上，也可以应用到图形处理器上。从上述可知，现代技术的发展为GPU计算提供了很多便捷，这使得GPU计算更具有普遍性。 目前，可通过GPU对图像进行处理研究的平台大多数都是基于前面提到的CUDA并行模型和OpenCL并行编程库。对于CUDA模型来说，文献15,16是利用CUDA并行编程模型，实现了适用于CUDA的并行高斯平滑算法，得到了良好的加速比。文献17则是利用CUDA并行编程模型，实现了高斯平滑算法的GPU并行执行，得到了良好的加速比。同样的，OpenCL实现GPU计算也有很多显著的成果。例如，文献18是利用OpenCL实现了对Laplace图像增强算法的优化，获得了良好的加速比。1.4 本文的主要研究方法与内容 本课题着眼于图像算法的并行程序设计，在通过实现CPU串行处理图像的基础上，通过两种不同并行平台对图像进行加速处理，并在对图像的处理速度上与执行结果上进行比对，获得相关结论。 本课题研究的并行编程方法有两种，分别是基于多核CPU的OpenMP以及基于GPU的CUDA并行技术。通过对上述两种并行算法的研究，将不同的算法应用于两种模型上，从而获得不同图像算法在不同并行平台上的并行加速效果。 为了实现对图像算法的并行设计，并比较不同平台的加速结果，分析不同平台的加速机制，本文的主要研究内容将从以下几个方面进行。 (1)学习上述两种平台的编程方法，分析两种平台的并行机制； (2)选取两个经典的图像处理算法并加以学习，在实现CPU串行处理的基础上，利用上述平台实现并行编程处理，分析现象； (3)选取一计算量大、计算过程复杂的图像处理算法，在实现CPU串行处理的基础上，利用上述平台实现并行编程处理，分析现象； (4)根据上述分析结果，总结得出基于上述并行平台上图像并行处理的实现规范。1.5论文的结构与安排 本文通过对Laplace锐化、中值滤波、修正的各向异性扩散PM模型算法在上述的两种并行处理平台上的应用，在对图像算法实现并行加速的同时，对比加速结果。论文的结构安排如下： 第一章为绪论，主要简单的介绍了对于并行处理的国内外研究现状，并阐明了并行处理在图像处理方面的应用，提出了图像并行处理的背景与主要研究内容。 第二章为并行编程模型概述，简单的介绍了OpenMP库与CUDA技术的基本原理与编程思想。 第三章为图像处理算法并行设计，简单的介绍了Laplace锐化、中值滤波、各向异性扩散PM模型以及修正模型，并将OpenMP和CUDA模型应用到图像处理算法中，研究了几种图像处理算法的并行设计。第四章为实验结果分析与总结，针对第三章中图像并行处理的方法，通过实验现象，对比不同算法平台下不同并行模型的加速效果，并对结果进行分析。第五章为总结与展望，总述课题研究的内容，并为后续工作提出了方向。2 并行编程模型概述能够实现并行算法的方法有很多，本文主要利用的是基于多核CPU的OpenMP技术以及基于NVIDIA公司GPU的CUDA技术。下面就相关的关键技术的基本内容进行概述。2.1 多核CPU并行库OpenMPOpenMP标准诞生于1997年，是一种面向共享内存及分布式共享内存的多处理器多线程并行编程语言，同时也是一种能够被用于显示指导多线程、共享内存并行的应用程序编程接口(API)，OpenMP具有良好的移植性，支持多种编程语言，同时能够支持多种平台，包括大多数的类UNIX系统以及Windows系统19。OpenMP支持多种语言，如常见的C/C+或是Fortran语言，编写程序时只需任意选择其中一种即可。本课题中采用微软开发的VS2010，其支持OpenMP并行库，只需对VS2010进行相关配置，就可以进行OpenMP编程。 OpenMP提供了一系列的接口函数，精简了开发流程。只需写出提示性语句，OpenMP可自行完成创建线程，初始化线程等工作，这种自动调度的方式减少了很多工作量。2.1.1 OpenMP执行模式OpenMP采用fork-join的执行模型，其中fork创建新的线程或者唤醒已有的线程，join则是多个线程的汇合19。OpenMP程序在刚开始执行的时候，只有一个线程运行，我们称其为“主线程”。在主线程执行的过程中，当遇到并行计算任务时，系统会自动地派生出线程来执行任务。在并行处理数据的过程中，所有线程同时工作，当并行处理任务结束后，系统将会停止派生线程的工作，只保留主线程继续执行后续任务。其具体流程如图2.1所示2.1.2 OpenMP编程模型 OpenMP编程模型以线程为基础，通过编译制导指令显式地指导并行化19。在C/C+程序中，OpenMP的所有编译制导指令是以#pragma omp开始，后面跟具体的功能指令或命令。其具体形式如下。 #pragma omp 指令 字句 ,字句 ,字句 其中，常见的指令有parallel，for，parallel for,section,sections等。外层并行域(Level=0)内层并行域(Level=1)并行域joinforkjoinforkjoinforkjoinforkjoinfork图2.1 OpenMP并行库fork-join并行执行模型子句部分是可选的，其可以设置线程数量等环境变量。根据以上内容，下面的例子简述了OpenMP的指令格式。 #pragma omp parallel for for(int i=0;i10;i+) printf(i=%d ,i); 其输出结果为i=0 i=5 i=1 i=6 i=2 i=7 i=3 i=8 i=4 i=9 之所以出现这样的结果，是因为for循环语句中的内容被并行执行了。当然，执行结果可能根据计算机的配置不同而不同。2.1.3 OpenMP任务调度 OpenMP易于使用和组合，在一些不支持 OpenMP 的平台上,OpenMP相关指令将被忽略，程序将按照串行方式执行，不会影响程序的执行过程19。 OpenMP的任务分担中，任务的划分称为调度。在程序执行的过程中，传统的CPU串行只能被一个CPU核心执行，而并行计算应当让所有的核心全部参与运算。但由于并行算计中每次迭代过程中产生的数据量可能不同，如果只是简单的分配给各个线程相同次数的迭代量，可能会造成线程之间的负载不均衡问题，即某些线程执行的较快，某些线程执行的较慢。当较快的线程执行完毕后，需要等待其他线程执行完，影响了执行的效率。OpenMP提供了几种优化任务的调度方法，分别是static、dynamic、runtime和 guided。 OpenMP中通常使用子句实现循环任务的调度。#pragma omp for schedule (type,size) 其中表示调度类型；参数是可选参数，其表示以循环迭代次数计算的划分单位，每个线程所承担的计算任务对应于个或若干个次循环，参数必须为整数。 (1)static静态调度在OpenMP中，若未使用子句时，则编译系统一般默认采用的静态调度。其具体原理如下，假设某一循环任务需要次迭代，执行此次循环任务的线程数为，那么每个线程理论上获得次迭代计算。当结果不是整数的时候，各个线程获得的迭代次数可能存在正负一次的偏差。在计算机运行的过程中，若多个线程同时寻址访问同一内存单元中的数据，则会产生访问冲突，使得访问速度下降，甚至造成程序无法继续执行24。而静态调度能够防止这种情况的发生，其原理是将原先顺序执行的部分分配到各个线程上并行执行，大大的降低了重叠访问的可能性。 (2)dynamic动态调度 动态调度是将迭代次数动态地分配到各个线程中19。同样的，参数对于动态调度也是一个可选项。当指定参数时，系统会给各个线程每次分配迭代。当未指定参数时，系统则会根据每个线程实际执行状态动态的将迭代任务进行分配。所以，执行速度较快的线程将获得的迭代次数更多一切；相反的，执行速度较慢的线程则会获得较少的迭代任务。例如有一个程序需要执行120次迭代任务，假设设置的大小为16，则划分情况为16,16,16,16,16,16,16,8分成8次。从上述可知，dynamic动态调度可以充分利用线程资源，尽量保证所有线程都有任务在执行，当某一线程执行任务完成后，继续申请另一个任务。 (3)guided调度guided调度是一种采用指导性的启发式自调度方法19。并行任务执行时，各个线程首先会获得一个较大的迭代块，之后随着迭代任务的进行，获得的迭代块大小会逐渐减少，直到迭代块的大小下降到大小19。如果未指定参数，则其最终会下降到1。guided调度策略的循环划分公式如下。 (2.1) 例如，某循环迭代，N=3，size=80，那么循环的划分为133,111,93,80,80,80,80,80,63。guided调度与dynamic动态调度相比，相对开销较小，无需一次性开设很多很大的线程，处理的性能有稍许提升。 (4)runtime调度 runtime调度与上述几种调度方式不同，runtime调度并不是真实的调度方式，而是系统运行过程中，其根据环境变量OMP_SCHEDULE来确定调度类型，最终使用的调度类型实际上是上述的三种调度类型中的一种19。2.1.4 OpenMP数据环境控制 一般情况下，OpenMP是建立在共享存储结构的计算机之上的，使用操作系统提供的线程作为并发执行的基础，所以线程之间的全局变量和静态变量是共享的，而局部变量、自动变量是私有的19。开发者在编程的过程中，需要自行指定OpenMP各个线程的变量是共享还是私有。常用的共享或是私有化指令是shared与private。 (1)shared子句 shared子句用来声明一个或多个变量是共享变量，其用法如下。shared(list) 在并行域内使用共享变量时，需要特别注意的是，如果对共享变量存在读与写同时的操作，要注意到变量的保护，尽量将共享变量转换为私有变量。 (2)private子句private子句用于将一个或多个变量声明为线程的私有变量。当某变量被设置为私有后，该变量只能由此线程访问，其它线程将会被禁止访问此变量。即使在并行域外有同名共享变量，其在并行域内也不会起到任何作用，同理的，并行域内的操作也不会影响到外部的共享变量。2.1.5 OpenMP编程约束 在程序执行的过程中，并不是所有的语句都适合并行执行。同样的，OpenMP需要满足一些约束下，才可以实现并行执行。 (1)执行过程中的迭代需要满足独立性，即循环迭代部分是独立完成的，前一次的循环结果对后一次的循环没有影响。 (2)满足循环语句的递减性。在循环过程中，作为循环约束变量，其应满足递减性，以防止死循环的发生。(3)循环必须满足单入单出的特性。在循环内部余循环外部不会产生任何的跳转。2.2 CUDA并行模型概述自2003年以来，半导体行业在设计微处理器时形成了两个主要方向，多核方向以及多线程方向。从前文可知，多核方向试图在保持原有串行执行顺序的基础上，将串行执行的程序应用在多核CPU上；而多线程方向则更侧重于执行并行应用程序时的吞吐量。 2003年，多线程处理器(尤其是GPU)已经成为了提升浮点运算性能的引领者。到2012年，GPU与多核CPU在峰值浮点运算的吞吐量比率已经达到了10:120。GPU在双精度浮点运算的情况下，其执行速度可以达到1.5万亿次每秒。而造成多核CPU和多线程GPU性能差距如此之大的原因是两种处理器的设计理念的差异。如图2.2所示，CPU设计的主要目的是为了提升串行代码的性能，其具有复杂的控制逻辑，用指令控制单线程执行程序的并行执行20。而相比于CPU，GPU内绝大部分是可用于执行程序的部分，这为GPU的并行执行打下了基础。当程序包含了大量线程时，具有较高执行吞吐量的GPU能获得比CPU更高的性能，所以GPU更适合执行数据密集的计算。2007年，NVIDIA推出了CUDA编程模型，提供了GPU可编程模型，为GPU计算的简化与推广产生了很大的意义。图2.2 CPU和GPU的内部简化模型2.2.1 CUDA模型简介 CUDA即统一计算设备架构的英文缩写，是NVIDIA公司推出的一套基于GPU的并行编程模型。推出CUDA模型是为了解决原先GPU的通用计算编程过程中难度大、过程复杂的特点，为科学人员提供一种简化的编程方法。CUDA模型的出现降低了GPU编程的难度，科学人员可以使用扩展的C/C+语言编程进行编程。CUDA 的架构提供了细粒度的数据并行化和线程并行化，并可以嵌套于粗粒度的数据并行化和任务并行化之中，这样的架构有益于指导程序员将问题分解为更小的片段，以便通过并行的方法来解决问题5。这样的分解有利于各个线程在处理问题的时候相互协作，同时使得处理过程变得更加透明，提升了处理问题的效率。程序员只需要提前对操作设备进行一定的了解，便可以在任何支持CUDA的设备上进行处理。2.2.2 CUDA程序结构CUDA程序由主机代码和设备代码组成。其中主机代码是指在CPU上执行串行执行的代码；而设备代码，是指在GPU上执行的代码。主机代码一般进行数据的初始化、对内存进行管理以及进行逻辑操作；而设备代码一般进行数据计算，对传给GPU的数据进行大规模并行计算。 一个基本的CUDA程序由以下步骤执行 (1)主机设备初始化，产生待处理数据，并分配相关的存储空间； (2)主机设备将数据拷贝到GPU部分，并在拷贝完成后计算数据； (3)GPU部分完成计算，将计算结果传输回主机设备，并进行后续处理。2.2.3 CUDA线程结构图2.3是一个典型的CUDA线程结构。CUDA程序中，kernel函数是最主要的组成部分。CUDA中网格(grid)由许多线程组成，线程是网格组成的基本单位，其依靠各自唯一的坐标来区分并确认各自需要处理的数据。CUDA中每个网格包含若干个线程块，每个线程块中包含若干个线程。 一个线程块中包含的所有线程共享一个线程索引，可以通过内置的变量访问。同样的，每个线程都有一个线程索引，可以通过内置的变量访问。当线程启核函数时，其可以通过访问、来确定线程的具体位置。 一般情况下，一个网格是由线程块组成的三维数组，而一个线程块是由线程组成的三位数组。如果需要较低的维度时，可以通过将不用的维度设置为1的方法实现。网格与线程块的配置是kernel函数启动语句中的配置参数决定的。前一个配置参数指定了网格的维度和线程块的数量，后一个参数指定了线程块的维度和块内线程数目。图2.3 CUDA线程结构 以矩阵的乘法为例，一个典型的kernel函数如下。 _global_ void kernelfuntion(float* am,float* an,float ap,int width) /计算线程坐标int c=blockIdx.x*blockDim.x+threadIdx.x;int r=blockIdx.y*blockDim.y+threadIdx.y;/计算矩阵乘法if(rwidth)&(cwidth)float p=0;for(int k=0;kwidth;+k)p+=amr*width+k*ank*width+c;apr*width+c=p; 2.2.4 CUDA内存模型 我们定义CUDA程序执行时浮点运算与全局存储器访问操作之间的比值为CGMA(Compute to Global Memory Access)20。显然，程序CGMA的数值越大，其执行速度越快。CUDA包含有多种类型的存储器，程序员可以利用相关的存储器实现CGMA比值的提升。图2.4 CUDA存储模型 如图2.4所示，其展现了一个标准的CUDA存储模型。从图中可知CUDA存储结构具有以下特性。(1)每个线程拥有一个私有的寄存器，仅供其自行访问；每个线程拥有一块共享内存，可以被线程块中的任何线程访问；全局存储器可以被所有线程访问 (2)全局存储器与GPU并不位于同一芯片上，所以其访问速度相对较慢。但由于共享内存内置于芯片上，所以访问时具有更低的延迟和更高的带宽，相对于全局存储器。2.2.5 CUDA硬件结构 如图2.5所示，该图显示了一个基于CUDA技术的典型GPU体系结构。这种体系结构是由一个高度集成化的多核流处理器阵列组成。每个多核流处理器又包含了多个流处理器。CUDA程序中，每个线程依附于SP对数据进行处理，实现数据的并行处理。图2.5 基于CUDA技术的GPU体系结构2.3 本章小结本章主要研究了OpenMP、CUDA两种并行平台模型的特性及其并行编程方法。从上述内容了解到了基于多核CPU的OpenMP技术以及基于NVIDIA公司GPU的CUDA技术。本章通过学习、了解这两种并行编平台的异同，为后续实现图像算法并行处理提供了基本的理论依据与技术准备。3 图像处理算法的并行程序设计3.1 中值滤波并行算法设计中值滤波作为一种基于排序的非线性滤波图像复原手段，其利用选取邻域内中间值的方法滤除噪声，成功地用于保留所需图像结构并同时消除脉冲噪声。3.1.1 中值滤波基本原理图像的中值滤波输出可由式(3.1)来表示。 (3.1)其基本思想是将图像序列中某一像素点的值用与其相邻像素序列的中值替代。例如对于一个大小为的模板，将图像像素的灰度值装入模板后，对模板中的灰度值进行排列，中值滤波的结果即为第个灰度值。一般情况下，图像中过亮或是过暗的点经过中值滤波后都会被消除。所以，如果图像中某一点像素点与其周围的像素点灰度值相差比较大，对其进行中值滤波后，会使得其与周围像素值接近。所以中值滤波更适合于处理含有孤立噪声的图像，例如受到椒盐噪声干扰的图像。由于其不类似于均值滤波，故不会使图像变得模糊。综上所述，中值滤波既能够消除噪声又能较好的保持图像的细节。中值滤波的效果一般情况下与选取模板的种类以及参与运算的图像像素个数有关。本课题选取模板，有如下像素矩阵。 (3.2)则其中值滤波的结果为 (3.3)其中为模板窗口内各个像素的值，为中值滤波后的结果，并放置于内，为获取像素值序列的中值。将图像内部的每一个像素都进行滤波，便可得到中值滤波后的结果。3.1.2 中值滤波的OpenMP算法设计上一章中我们简述了OpenMP的基本原理，由于我们采用的编程平台为Visual Studio 2010，而VS2010中自带了OpenMP库，所以只需要进行简单的设置即可实现OpenMP编程的环境配置。利用OpenMP库实现图像的中值滤波步骤如下。(1)寻找中值滤波算法中适合于并行处理的部分。由于OpenMP采用fork-join模式，所以需要人为的分配指定某一部分实施并行处理。很显然，中值滤波中适合于并行处理的部分就是图像的中值选取;(2)选择适合的调度方式。由于中值滤波操作单一，所以采用静态调度的处理方式即可;(3)定义执行过程中CPU核心的数目。一般情况下选取的线程数等于处理器的核心数目。如果定义的线程数超过处理器核心数目，并不能提升执行效率。其类似于单核处理器执行多线程任务一样，单线程通过切换来实现执行不同任务，虽然表面上是并行处理，但在时间上的开销仍是串行处理所需的时间；(4)编写OpenMP指令，一般以#pragma omp作为引导执行开头，并紧跟着循环语句在其后。简化后的OpenMP实现图像的中值滤波的算法如下。#pragma omp parallel for private(pixel,mid) num_thread(8)for(int j=1;jlHeight-1;j+)for(int i=1;ilWidth-1;i+) /获取模板中像素的数值，并存放于数据pixel中 /调用GetMid()函数，实现获取模板的中值mid=GetMid(pixel);3.1.3 中值滤波的CUDA算法设计CUDA是基于GPU的并行编程模型，由于GPU主要用于处理计算机显示的各种图形，其本身结构固有大量的并行计算单元。目前CUDA技术仅支持NVIDIA制造的显卡。利用GPU执行CUDA模型的具体步骤如下。(1)定义线程的数量和线程块的数量。 dim3 blocks(32,32); dim3 threads(16,16);本课题中定义了个大小为的线程块。其大小以及数量需要根据实际情况来决。(2)主机为设备分配内存。由于编写程序的过程中，设备并不能自动的为数据分配内存，故需要人工的在主机端为设备分配内存。分配的内存大小根据数据的大小而定。CUDA中，主机为设备分配内存的函数为cudaMalloc()，其具有两个参数。前一个参数是指针变量的地址，后一个参数则类似于C语言中malloc()函数的参数size类似。本课题的程序中，编写了如下程序。cudaMalloc(void*)&dev_OldMar,(lW*lH)*sizeof(BYTE);cudaMalloc(void*)&dev_NewMar,(lW*lH)*sizeof(BYTE);其中，lW和lH为图像的长宽，dev_OldMar与dev_NewMar设备中的分配内存的指针。(3)。在第一步为设备分配内存后，需要将存储于主机上的数据复制到设备上执行。其利用CUDA函数cudaMemcpy()即可将数据复制到设备上。cudaMemcpy(dev_OlaArray,OldArray,(lWidth*lHeight)*sizeof(BYTE),cudaMemcpyHostToDevice);其中，OldArray为设备上的数据的指针，(lWidth*lHeight)*sizeof(BYTE)为拷贝数据的大小，cudaMemcpyHostToDevice表明了拷贝方向是设备向主机方向拷贝。(4) 调用kernel函数。按照上述步骤执行完毕后，需要调用kernel函数对数据进行处理。图3.1简述了kernel函数执行的过程，其表示了一个一个大小的图片。假定某程序分配了12个线程块，每个线程块内部包含个线程，则一共使用了32个线程。可以看出，图片的大小远超过线程的数量，所以线程每次仅能够处理图像的一部分。分配的线程最先执行图片的1、4部分，执行完毕后另图像向左平移(相当于线程块“向右平移”)，对后续的图像进行处理。123456图3.1 kernel函数执行过程 简化的kernel函数如下(省略了大部分程序)。_global_ void CUDAZZ(BYTE* OldArray,BYTE* NewArray,int lWidth, int lHeight) /计算起始坐标 while(offset(lWidth*lHeight) if(xlWidth-1) /获取大小的灰度值，存放到BYTE pixel9内 /调用函数，获得中值并保存 BYTE mid=CUDAZZFun(pixel); /x方向平移x+=512;else /x方向平移完毕，向y方向平移y+=512;x=xOrrigin;3.2 Laplace锐化并行算法设计Laplace锐化属于图像增强算法的一种。其能够对原始图像进行增强，使之看起来更加清晰。Laplace算法不仅可以用于图像的噪声抑制，对于图像的边缘检测也有着广泛的用途。3.2.1 Laplace锐化基本原理Laplace算子是一种各向同性微分算子，其具有旋转不变形23。二维图像的Laplace变换是各向同性的二阶导数，其定义为 (3.4)为了更适合于处理数字图像，对于图3.2(a)中的模板，其离散形式为 (3.5)用模板表示式可得到下述Laplace算子模板(图3.2所示)。图3.2中还展示了几种其他的Laplace模板，其中(b)表示其扩展的Laplace模板，(c)(d)表示其他两种Laplace实现模板。 (a) (b) (c) (d)图3.2 Laplace模板从模板上看出，对于图像中较亮的像素点来说，经过Laplace运算后该像素点会变得更亮。由于图像边缘具有灰度跳变的特性，故对图像使用Laplace锐化模板可以获得图像的边缘。Laplace算子同时也对于孤立的像素点较为敏感，所以其可以突出图像中的孤立像素点或是孤立线。对图像进行锐化处理其主要目的是为了增强图像的灰度反差，从而获得更清晰的图像。一般情况下，图像模糊的主要原因是受到了平均运算或是积分运算。而图像复原的实质就是对其进行逆运算。对图像进行微分运算，其可以使图像变得清晰。由于Laplace运算实际是一种微分运算，所以其对于模糊图像处理较为有效。因此，锐化处理可以用Laplace算子对原图像进行处理，再将处理结果与原始图像叠加产生锐化图像。其具体表达式可由下述式子描述。 (3.6)图像经过Laplace变换后，将处理后的图像与原始图像叠加，可以在保留图像灰度值的同时，增加了图像的对比度，同时使得图像的细节得以更加的凸显。3.2.2 Laplace锐化的OpenMP算法设计在3.1中我们简单的介绍了OpenMP算法设计的步骤。Laplace锐化程序中，适合于并行执行的部分就是各个像素点与Laplace模板进行运算。其简化后的算法如下(省略了大部分程序)。#pragma omp parallel for private(fResult) for(j=tempMY;jlHeight-tempH+tempMY+1;j+)for(i=tempMX;ilWidth-tempW+tempMX+1;i+)/Step1：像素点与模板运算，结果保存在fResult中/Step2：原始像素值与Laplace运算结果做计算，并保存 lpNewDIBBitsj*lWidth+i=lpNewDIBBitsj*lWidth+i-fResult;3.2.3 Laplace锐化的CUDA算法设计在3.1中我们简单的介绍了CUDA算法设计的步骤。Laplace锐化程序中，适合于并行执行的部分就是各个像素点与Laplace模板进行运算。CUDA中最核心的部分是kernel函数，简化后的kernel函数如下(省略了大部分程序)。_global_ void CUDAZZ(BYTE* OldArray,BYTE* NewArray,，) /计算线程与起始坐标 while(offset(lWidth*lHeight) if(xlWidth-1) /对图像进行Laplace运算，保存至fResult中 /与原始图像进行叠加NewArrayy*lWidth+x=BYT