基于机群的并行匹配算法

《基于机群的并行匹配算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、维普资讯http://www.cqvip.com第31卷第6期测绘科学Vo1．31N62006年11月ScienceofSurveyingandMapping基于机群的并行匹配算法张春玲①。邱振戈②(①河南省测绘局，郑州450052；②中国测绘科学研究院重点实验室，北京100039)【摘要】随着卫星遥感技术的发展，需要快速地将卫星遥感图像数据转化为用户需要的信息，并行图像处理技术是解决“快速”的重要途径。并行程序的性能与计算机体系结构密切相关，不但取决于CPU，还与系统架构、指令结构、存储部件的存取速度等因

2、素有关。一般意义上，提高并行程序的性能采用粗粒度并行，指令级优化(ILP)和存储优化等技术。作为尝试，本文讨论了在工业标准化机群上采用软件式共享存储系统做的并行影像匹配方法，以影像匹配算法为例子，讨论了如何在粗粒度并行、指令级优化(ILP)和存储优化三个方面提高图像处理的计算速度。【关键词】影像匹配；粗粒度并行；指令级优化(ILP)；和存储优化；机群【中图分类号】研51【文献标识码】A【文章编号】1009—2307(2006)06—0127-03伽为与(uIIlg0，Rimg0)关联的匹配算子；(Limgl

3、，Rimgl，1引言1)映射到处理器P；⋯⋯，(Limg7，Rimg7，q~／)映射到处随着计算机处理器的多核化发展，高性能计算正在以理器。由，，⋯⋯．，8个处理器并行计算。前所未有的势头开始普及，低成本高性能计算将普及到低端计算机用户，为用户提供廉价的几个到几十个CPU的计3不同节点上的访问局部性分析算平台。高性能并行计算的普及为遥感图像处理提供了一在机群系统中，如果对内存的访问在本机不命中，远个新的发展空间。程取数的代价大；因为在节点不命中时P。就要从其他机本文从影像匹配算法的粗粒度并行性、不同节点上的

4、器上将相应数据取到本机，此过程有一定的时延。如果数访问局部性、单节点上的存储优化、基于SIMD的指令级影据分配不合理，本机不命中率高，并行计算效率会很低，像匹配加速方面，讨论了在工业标准化机群上用软件式共大量时间用在通讯上，计算时间的比例很低。在本文设计享存储系统做的并行影像匹配算法的方法，并给出了计算的影像匹配并行算法中，每个处理器在对其边界数据进行效率的实验结果。计算时会出现本机不命中，如图2所示，在上的相应的2影像匹配算法的粗粒度并行性分析匹配算子4J0对Limg0，RimgO的边界计算时要用到FLo

5、，通常的影像匹配算法，从程序设计的角度可以看成一FRO所标记的区域数据，而FLO，FRO所标记的区域不在上，在P上，如图2中的FL1和FR1；这时发出调页请求，系统从P上将数据复制到本机的虚拟Cache(VCache)中，数据操作如图3所示，P。将P的Home中的数图3本机和远程据复制到本机的VCache中。数据访问为了减小本机不命中率，要加大VCache的尺寸，让VCache能装下FL1，FR1的全部数据，这种情况下匹配算子伽在对LimsO，RimsO的边界计算时只出现一次本机不命中，计算效率大为提高。4

6、单节点上的存储优化分析与飞速发展的CPU主时钟频率相比，CPU和主储器之间的速度差距仍在不断扩大，主存储器主要器件的DRAM已成为高速计算机的主要瓶颈。因此，充分利用存储层次结构的特图1影像匹配数据操作图2并行匹配域分解点，是提高应用程序性能的另一个重要途径。缓存是计算机存如图2所示，我们将按行把Limg、Rimg分成8块进行并储层次结构的核心，高速缓冲存储器Cache是位于CPU与内存行匹配计算。将(LimsO，RimsO，伽)映射到处理器，其中之间的临时存储器，它的容量比内存小但交换速度快。Cache中

7、的数据是内存中的一小部分，这-／b部分是短时间内CPU作者简介：张春玲(1964一)，女，本科，即将访问的数据，CPU要读取一个数据时，首先从Cache中查工程师，主要从事航空摄影测量、高性找，如果找到就立即读取并送给CPU处理；如果没有找到，能计算方面的研究。就用相对慢的速度从内存中读取并送给CPU处理，同时把这E—mail：zhangchunling06@sina．tom个数据所在的数据块调入Cache中，这使得以后对该块数据的读取在Cache中进行，不必再调用内存。‘收稿日期：2006—04—20如图

8、4所示，计算机内的数据是顺序存放的，CPU每次读人一块数据到Cache中，在影像匹配计算时，每行数据在计算时是被一块块读人，所以在调入Cache后，计算用到的相邻数据是Cache命中的(图中实心黑点)，而换行维普资讯http://www.cqvip.com128测绘科学第31卷5．3基于SIMD的指令级影像匹配加速关键步骤SIMD扩展指令集中相关SIMD指令有：MOVUPS用于将128位数据从内存传输到SIMD浮