并行程序分析（精选七篇）
并行程序分析 篇1
近年来,多核处理器技术快速发展,并呈现向众核方向发展的趋势。Intel以及AMD都相继推出了多核的高端处理器,Intel的Knights Corner处理器核数可以达到50核,甚至更多。与此同时,Pthreads、OpenMP、MPI这些传统的并行编程语言已日渐成熟,CIlk、TBB等一些并行编程模型也逐渐面向市场。在这些并行编程语言及模型中,多线程仍是实现并行的主要方式。线程的分配数量、任务的派发以及在硬件资源上的调度与并行程序的执行性能密切相关。
在并行应用程序中,受到环境、并行程序之间、并行程序内部不同线程之间的影响,执行过程具有不确定性。并行线程独立的数据及其操作促成了并行程序性能的提升。但是,同时存在并行单元的资源共享和竞争,这是影响并行程序性能的关键。例如,一个加锁操作可能导致一段时间内一个线程运行而其他线程阻塞的情形,使得程序性能下降很多。资源的共享和竞争形成了并行线程之间的通信,主要有锁操作、信号量、同步等,使得某些线程之间存在着一定的制约关系,影响了其并行的完全性。
本文提出的工具PPAT正是在线分析程序不同线程的锁、信号量及同步操作,记录相关行为信息并对其进行分析。除了资源的共享和竞争外,程序执行过程中的一些硬件行为同样可以反映程序的执行性能,例如访存次数、cache命中率等。工具针对每个线程,抓取了相应的硬件行为信息来分析线程的性能。信息的获取采用了源代码插桩以及静态采样相结合的方式。最后,工具对分析结果提供了可视化的功能,便于上层开发理解和分析。可视化部分将线程之间的关系以通信图的形式展示出来,从不同角度,以不同形式展示了线程间的通信情况。此外,PPAT采用了动态可视化以及基于聚类算法的多图层分析,保证了在众核环境,线程数较多的情况下可视化的效果。
1 相关工作
由于资源共享和竞争的因素,应用程序实际运行有很多的不确定性,运行的效果也可能大相径庭。因此,从性能优化的角度,提出了若干资源适配的方法来改善调度。文献[1]针对CMP结构,采用了一种周期性采集运行时信息以预测所需处理器核数的方法,动态对线程进行分组来适应底层硬件资源。文献[2,3]针对非对称处理器,将高负载线程分配到能力强的核上,通过差异性来改善应用性能。这些是在线程数量确定的情况下,考虑如何合适地分配资源。另一个角度是根据资源动态调整并行粒度。文献[4]提出了一个框架FDT(Feedback-Driven Threading),通过运行时捕获线程数量及性能关系,分析合适的线程数,在程序的后继实行过程中动态调整线程数量。文献[5]提出了一种基于profiling的方法,它利用硬件性能计数器产生的事件对预运行的应用程序进行分析,获得达到最佳性能与功耗平衡的并发线程数量。文献[6]也用到了profiling的方法,但重点在于发掘程序的并行性。Thread Tailor[7]采用了一种离线分析技术来获取二进制代码文件中线程的通信和同步关系,并利用动态编译技术,在运行时根据当前硬件资源的情况对应用原有线程进行合并。
关于对并行程序进行分析及调试的工具, Intel开发了很多如VTune Amplifier[8]、PinPlay[9]等的工具来对并行应用程序的性能进行分析,VTune Amplifier能够帮助程序员找出程序中最耗时的、调用频繁的关键函数,显示程序CPU的利用率以及锁的使用情况及等待时间。Intel的大部分工具都用到了Pin,所以工具的负载比较大。
文献[10]提出了通过任务图的分析,预测共享存储的并行程序的性能。任务图记录了任务的详细执行顺序以及彼此的依赖关系,通过任务图,调度函数,提供并行程序定量分析的合适抽象,对重要性能进行评估。很多并行程序的分析都用到了图的概念[11,12],形式和规模各异,本文所述工具中也涉及到了图。
HPCToolkit[13,14]是一种既有串行又有并行的程序性能分析工具。对并行程序进行分析时,通过测量和分析并行程序中的并行空闲(线程阻塞)以及并行负载(线程并未执行有效计算),指明应用程序应当何时何地进行并行粒度的调整。
相对于这些工具而言,本文介绍的分析工具有两方面特点:首先,重点关注线程之间的通信关系,即线程之间资源共享及竞争的关系,便于从降低线程间通信的额外开销的角度优化并行程序;其次,性能数据分析与可视化的设计考虑到了线程动态运行及未来众核环境下线程个数众多的特点,可实现线程间关系随执行时间动态变化的可视化,以及基于聚类算法的大量线程通信分图层显示。
2 关键问题分析
2.1 线程相关性能参数
为了分析线程之间对资源的共享和竞争关系,需要一些参数来表示线程的动态行为并在程序执行时获取相关信息。鉴于资源共享及竞争产生的特殊操作主要包括:锁操作、信号量、同步操作。PPAT选择对进行这些特殊操作的事件进行监听,然后捕获信息,包括特殊操作的标记、线程编号以及操作前后的具体时间等。在Pthreads编写的并行程序中,需要监听的事件列表如表1所示。
2.2 参数获取方法
动态获取程序执行信息的方法有很多,常见的有插桩、动态测量等。动态测量是在不影响源程序的情况下,在程序执行过程中收集底层数据来计算或分析得出所需信息。该方法所获取的信息不够精确,有些信息很难经过分析得到。插桩则是通过插桩点来捕获程序执行时的状态信息,是软件测试中常用的一种技术。插桩技术又分为静态插桩、动态插桩,文献[7,8]提到的pin即是一种动态插桩技术,在程序执行相关指令时动态插入代码获取信息。该方法多用于分析较为底层的指令,例如访存指令等,能非常详细地列出访存的类型、时间及数目等信息,代价就是运行时间会很长,负载较大。
本文需要监听的事件并非一些频繁的底层操作,插桩点相对整个程序来说较少,因此PPAT采用了静态插桩的方式,在程序执行前即完成了的代码的插入。代码的插入既可以在目标代码进行,也可以在源代码进行。因为要对目标代码进行的分析相对复杂,而源代码语义又相对清晰,所以PPAT选择了在源代码级别对特殊事件进行了包装。
2.3 性能数据可视化
获取的性能数据需要进行可视化处理,来直观、形象的展示线程运行的过程。在硬件平台由多核向众核发展的情况下,并行程序的执行线程数可以设置至几十甚至成百上千个,展示众多线程信息会使图像会变得极为复杂,降低了用户的可视性。
PPAT将获取的性能数据转化为线程通信图,以节点、边的形式的通信图直观显示线程之间的关系。PPAT的可视化提供了依据获取信息动态形成通信图的方式,方便了解线程之间的通信是如何逐次发生的。对于提高多线程数下的可观性问题,工具采用了聚类算法,对线程按照某属性聚类,根据聚类结果分图层显示数据。
对线程的聚类,根据层次聚类的思想,从底部开始逐层向上进行聚合,假定线程集T={t1,t2,…,tn}共n个线程。
(1) 初始化,每个线程ti为一类,共有n个类。
(2) 找出通信最密集的两类。
合并,将ts与tt合并为一个新类,总类数减一。
(3) 若类数降低到可视化水平,或是各类间已无通信,则终止,否则继续步骤(2)。
聚类后的结果为可视化图层中的最高层,每类中的通信图为更加底层的内部图层。可视化的通信图将显示最高图层,然后按照需要显示各类内部图层。
3 性能分析工具设计
3.1 系统构成
分析工具的整体构成如图1所示。工具分为静态分析、动态捕获、分析以及可视化等主要部分。
静态分析的工作是在源代码中,根据资源共享及竞争产生的众多特殊事件进行代码的插桩,以便程序执行时捕获相关的共享及竞争信息。动态捕获模块在程序运行时动态捕获两方面信息,一方面是由于共享及竞争产生的线程间通信信息,另一方面是通过周期性采样模块获取的执行时硬件反馈信息。为了降低对源程序执行的干扰,我们开启了源程序之外的帮助线程[15]来对数据进行分析,实验显示,PPAT硬件信息获取对源程序执行的负载几乎为零。分析模块对捕获的信息进行详细的分析。统计分析的数据一方面通过与调度器定义的接口传递给运行时的控制调度部分,另一方面则生成可视化的数据格式,保存在数据库中。可视化管理模块可以根据用户的定制对数据进行摘取、处理然后显示在界面中。分析及可视化部分相对于信息的获取是独立的,并且是跨平台的,这样便于扩展信息的获取方式以及支持不同的并行编程模型。
3.2 事件捕获及分析
PPAT替换了源程序中对pthread.h的引用,在新的头文件中定义了对特殊事件的新的包装函数。如图2所示,当用户需要调用特殊事件的函数时,工具将函数重定义到包装后的函数调用,在新的包装中调用初始的调用函数,在调用初始函数的前后会插入轻量级的捕获代码,捕获事件的状态,主要是函数的参数信息。
PPAT将捕获的信息最终分锁冲突及同步等待。锁冲突代表了不同线程间对共享变量的访问冲突情况,同步等待则表示了线程在同步过程中的额外开销。
(1) 锁冲突
Pthreads中将锁的操作分为两类,互斥锁以及读写锁。我们首先定义一个冲突区间(时间单位),在互斥锁的使用中,当不同线程对同一锁进行操作时,如果操作时间在冲突区间内就说明线程间存在一次变量访问冲突。考虑到读写锁的情况,只有在读-写,写-读,写-写的顺序下会发生冲突,通过对锁的访问时间及类型分析,得出冲突区间内的锁冲突次数。
(2) 同步等待
信号量的使用也是同步机制中的一种,线程开始等待的时间至另一线程发出信号的时间差为两线程之间的同步等待时间。barrier同步中,最后到达的线程与其余线程到达的时间差是其余线程的等待时间。join中,在调用时,仍未执行完成的线程均是调用线程的等待线程。
3.3 硬件性能信息选取及分析
程序执行时的一些硬件信息,反映了程序执行的一些客观情况,通过对一些硬件信息进行抓取分析,可得出程序执行过程中的CPU利用率、cache命中率等信息来分析程序的性能。基于硬件支持的性能计数器很好地支持了对程序性能进行优化分析研究。在此,我们选取了cache利用率、访存次数等来表示线程在资源访问方面的性能。
在较新的内核版本中,有一个perf_event的封装,提供了若干对性能计数器的操作接口,可以将获取的数据量化到指定ID的线程。PPAT采用了此技术得出单个线程的cache利用率及访存次数等。根据这些硬件信息可以分析出哪些线程需要进行更好的资源分配和调度。调度器可以根据相关的信息对程序进行优化。
硬件信息的获取不需要通过事件的触发,PPAT通过静态采样的方式获取,只要采样周期设置得尽量频繁,采样的数据便足以表示整个执行过程的状态。采样周期可以设置为纳秒级别,程序员的观察点时间粒度相对较高,我们通过这其中若干个周期采样的平均值表示该时刻的硬件信息。
3.4 线程通信图
3.4.1 通信图元素
PPAT重点关注多线程之间的共享及竞争,为了便于直观展示及分析线程之间的关系,PPAT将线程之间的通信转化为通信图的形式。通信图中的节点表示单个的线程,权值有:执行函数,POSIX线程ID,创建时间、结束时间、硬件性能信息。边的权值包括锁冲突次数以及同步等待时间,分别通过无向边与有向边表示。通信图的设计分为三类:
(1) 创建依赖关系图
线程之间的创建关系,通过有向边连接线程的父线程及子线程,表示线程之间的创建及结合关系。
(2) 完整通信图
图中节点以及边的权值在程序执行完成后统计而成,反映了从整个程序的执行状态,哪些线程之间的通信较为密集,哪些线程的行为比较独立。
(3) 阶段通信图
按照节点创建、冲突以及同步状态的记录顺序,动态地将冲突信息反映在通信图中,反映了程序的冲突是如何一步一步积累的。
3.4.2 动态及多图层通信图
通信图的初始信息是经过分析的线程间冲突及同步信息,按照时间戳顺序逐条记录的,便于通过不同分析画出不同的效果。动态通信图的实现采用了定时器的机制,每个一定的时钟周期从记录中取出下一条记录,与当前的通信图信息进行统计融合,然后根据新的权值进行通信图效果渲染,最后重新布局显示。定时器的时间周期可动态调整,加快或减慢动态图生成步伐,便于清晰了解动态效果。
在通信图的线程数目超过某个阈值时,会触发聚类算法,如图3所示,首先将需要展示的通信图的逐条记录信息进行权值的整合。将所有边的信息按照权值由最大到最小的顺序排序,然后依此遍历每条边,将该边连接的两端节点所在的类归为一类。同在一类的节点被打下group标签,表示线程在同一组中。可视化显示时,先按照group为单位显示组后的图层,扩展group后方可显示组内图层。
考虑到通信图信息可以进行后续的分析,工具另一方面将线程通信图的信息保存在文件中,考虑到每次创建线程的ID不相同,文件中的通信图信息在原有信息的基础上添加了创建ID,工具采用图4的方式记录线程的创建ID,0表示主线程,在每层中,每个线程创建线程的顺序是确定的,故从左至右依次编号。
4 实验与测试
4.1 工具实现
性能分析工具目前基于Linux系统实现,并在Intel多核处理器系统上使用基准测试集PARSEC[16]进行了实验与测试。测试环境如表2所示。
图5依次展示了启动8个线程情况下blackscholes、fluidanimate的线程通信图(输入均为simsmall)示意图。图中节点由线程执行函数,POSIX线程ID标示,其余包括调用者、硬件信息等通过tooltips表示,main节点表示程序的主线程。无向边表示线程间的锁冲突次数,有向边表示线程同步关系,后者等待前者的时间。边的粗细以及明暗变化表示了冲突的程度及等待时间的长短,由深到浅表示冲突程度增加、等待时间加长。为了便于随时间关注线程间通信情况,PPAT提供了动态通信图,图6即是ferret动态生成通信图中某些阶段的状态。图中显示了某次执行中程序开始0.2s、0.25s、0.3s、0.4s的时间时,各线程累积的通信状态。从图中可以看出,线程的通信在本次执行中集中在0.4s之前,其之后创建的线程基本均在独立执行。统计多次执行的结果,对ferret程序而言,通信集中在程序执行的前42%左右。
在线程数较多情况下,PPAT会依据聚类算法分图层显示通信信息,图7为64个线程数目下swaptions的分组情况,依据边的关系分出了组1,由于组内线程数目依旧庞大,则根据边权值将组内线程进行在分组,结果共有3个图层。
4.2 工具性能分析
PPAT通过在源代码中包装插入捕获代码实现执行信息的获取,插桩分为不同的级别,用户指定插桩的不同事件。
程序blackscholes、ferret以及swaptions在不同输入规模,捕获不同参数,不同线程数目下,插入捕获代码后与插入前的执行时间比如图8、图9、图10 所示。从图中可以看出,关于硬件参数的捕获对原始程序带来的干扰非常小,原因是硬件参数的获取是在源程序之外的额外线程获取的,两者之间的交互只限于创建线程时传递线程在内核的执行ID。
在输入较大的情况下,如native,捕获的干扰较小,执行时间比在1.1以内。线程之间的竞争及同步通信相对整个程序的计算部分所占比例较小,尤其是在输入较大的情况下,大量的计算隐藏了捕获通信的开销。在线程数较小的情况下,如4个线程,捕获的干扰也较小,特殊事件的监听是对每个线程进行的,线程数量小,监听的负载也较小。线程数较大时,监听的负载会相对提高,尤其是在输入较小,计算时间较快的情况。
对竞争的捕获干扰与对同步的捕获干扰程序相近,在blackscholes中,并未使用任何锁,然而关于竞争的捕获干扰与同步仍然相近。通过对比分析,干扰的主要来源是线程创建时一些公用信息的处理以及最后捕获信息的存档,其次是竞争、同步等相关特殊事件的信息捕获。下一步对工具的完善过程中将会进一步降低捕获过程带来的干扰。
4.3 同其他工具比较
我们在试验机器上安装了Intel的试用版Vtune,Vtune也可以对锁的使用及等待情况进行分析,它的分析结果展示了由于锁的使用而造成的等待结果较长的函数,通常即为加锁操作。PPAT做了进一步的分析,展示出的是由于锁的竞争产生的不同线程之间的等待同步关系,更便于分析优化线程间的调度分配。
5 结 语
本文介绍了一个在多核/众核环境下的并行程序线程性能分析工具PPAT,对并行程序的多线程之间的数据共享及竞争等通信信息以及单个线程的硬件反馈信息进行捕获分析,形成线程通信图帮助进行程序的分析和优化。工具的可视化部分以不同的方式从不同的角度展示了线程间的通信关系,加入了聚类算法对线程进行分类、分图层显示,保证了众核环境下线程数较多的可视化效果。
工具的分析及可视化部分独立于编程模型以及操作系统,关于信息的获取我们目前实现的是基于pthread的插桩技术,下一步要做的就是扩展信息的获取,包括windows下的多线程,获取信息的方式以及对信息的定制等。同时进一步优化分析及可视化部分。
摘要：随着多核/众核处理器技术的快速发展,程序需要越来越多地采用多线程并行技术以提升性能。随着线程个数的增多,线程并行运行过程中相互间同步/互斥及资源竞争关系更加复杂,导致程序性能优化的难度增大。为了使编程人员直观地了解线程的动态运行过程,特别是线程间同步及资源共享带来的影响,帮助其进行程序性能优化,设计实现了一种面向Pthread的并行程序线程性能分析工具PPAT(Pthreads program analysis tool),该工具可在程序运行过程中动态获取线程运行及线程间互斥/同步信息,生成线程通信图,并以多种可视化的方法显示,为编程人员优化程序性能提供依据。
并行程序分析 篇2
并行性分析作为自动并行化系统的重要组成部分,它的基础是前端分析和数据依赖关系的分析。前端分析就是对读入的程序进行扫描分析;数据依赖分析的是语句及变量的之间的数据依赖关系。程序并行化就是在扫描中对程序进行初步并行性分析,然后根据数据依赖关系,判断循环并行的可能性。
文中探讨了人工智能扫描策略,并且对已有策略进行改进。为了实现大型程序中循环级并行性检测得到可靠的、精确的数据依赖关系分析,文中针对传统从数据依赖关系分析的不足研究了精确的数据依赖关系分析技术——数组数据流分析技术。
1 智能扫描分析
前端分析就是对读入的串行程序进行扫描,由于程序有很多分支,扫描时就可以分多次扫描,每次扫描的不同内容就是相当于搜索路径不同,可以通过人工智能搜索来实现。本文采用的扫描方法是iterative hil climbing method,算法思想是:
(1)随机选取一个解,从此解的所有相邻解中选择最优的解来代替原有解,然后从这个新解开始,重复这个过程,直到一个解的所有相邻解都差于它时,这个解就成为局部最优的解;
(2)对上述过程重复n次后,找出到目前为止最好的局部最优解,那么这个局部最优解就可以作为全局最优解的近似。算法实现如下:
本文还对此算法进一步改进,在此算法中加入深度优先搜索和广度优先搜索的选择,在对程序进行扫描的时候,选取的新点邻域中可以根据评估函数中控制搜索方向的参数,根据参数的取值范围选择进行广度还是深度优先搜索。
本文构造的启发式函数如下:f(x)=g(x)+ph(x)根据p值在取值变化的调节性,搜索会选择向深度还是广度搜索进行。当p→0时,则有ph(x)→0,从对整个函数的影响方面看,是减弱的,这样搜索向广度优先搜索的方向进行。当p→∞时,则有ph(x)→∞,ph(x)对整个评价函数的影响就会变得很大,这时候搜索是会按照向深度方向进行。
从一般的情况进行考虑,p的值是不会接近∞的,固应该设置一个临界值。在程序并行化智能搜索中,制定如下策略:初始阶段的搜索,控制p值使其偏大,在程序的搜索过程中向深度方向进行,目的是为尽快接近目标;当进入到一定阶段,搜索到一定程度后,应调整使p值变小,广度方向应成为搜索方向的选择,目标结点要避免错过,直至搜索成功完成。
2 数据依赖分析
在程序中,如果事件(或动作)A必须发生在事件(或动作)B发生前,则称B依赖于A,这是依赖关系[1]的定义。数据依赖关系是由于读/写同一数据引起的。
传统的数据依赖分析的方法有GCD测试和极限测试[2]。在GCD测试中,关于多维数组的数据依赖测试简单的总结为建立一个线性方程组,前提条件是要满足一组线性不等式的约束,寻求整数解的存在与否。循环索引变量是线性方程组的变量,循环边界产生不等式约束,然而对于一维数组只有一个方程需要测试[3]。例如:
数据依赖测试需要做的工作是:确定约束条件为1≤i<20,i+1≤k<20,0≤j
终写树其实是对读/写引用间的精确依赖关系用二叉树进行描述[4]。实例分析如图2所示。
建立LWT树的方法是可以实现将依赖关系精确到具体数值的,这样就为循环嵌套数组分析程序自动并行化提供了更高效的方法,同时也成为代码生成和通信优化的关键依据。
3 结语
本文介绍的人工智能扫描方法中,针对已优化的算法进行进一步改进,在其中探讨了基于评估函数的结合深度和广度搜索的智能搜索算法,在一定程度上解决了花费时间较多、占用很大存储空间的问题。并且还探讨了优于传统数据依赖关系分析的算法——数组数据流分析算法,根据其算法流程图就终写树和写写树进行了实例分析。这两方面技术的改进能够很好的提高程序并行化的效率。
参考文献
[1]王姗姗,赵荣彩,张平.对SUIF中依赖关系分析技术的研究与改进[J].计算机工程,2006,32(7):89-91.
[2]Stanford Compiler Group.SUIF compiler system [M].Version l.0.US:Standford University,1994.
[3]DONG Chun-li,ZHAO Rong-cai.An improving computation and data decomposition [C]// Proceedings of DCABES.[S.l.]:DCABES,2006:111-116.
[4]张平.并行化编译器中并行程序自动生成和性能优化技术研究[D].郑州:信息工程大学,2006.
[5]龚雪容,生拥宏,沈亚楠.串行程序并行化中计算代码与同步通信代码的自动生成[J].计算机应用与软件,2008(1):91-92.
[6]沈志宇.并行编译方法[M].北京:国防工业出版社,2000.
并行程序分析 篇3
死锁的问题是一个严重和复杂的并发系统。建立一些方法来自动检测并发系统中的死锁已成为一个重要的课题。至于自动死锁的并发程序的检测方法和工具, 可分为两个类别:静态检测方法和动态检测方法。
至于静态检测方法, 我们试图寻找一个潜在的死锁形式与目标程序来使实际运行。由于他们的目的是找出所有可能的死锁, 那些不能出现在实际环境, 多线程的执行时间和输入数据可以包含在结果。大部分这类工具基于形式化分析和模型检查。
至于动态检测的方法, 我们试图通过运行实际, 与一些探测器通过某种方法使其目标在实际执行中查找死锁的发生。我们打算在实际的环境中发生死锁检测时间的多线程的执行, 并输入数据。
一种理想的动态检测方法应满足以下三个基本要求: (1) 完整性:方法必须是能够检测出任何死锁。 (2) 健全性:该方法必须报告任何存在的死锁。 (3) 效率性:该方法必须能够得到执行, 以便它可以检测到死锁的位置。
至于效率, 我们是既要执行它, 要尽可能减少成本。死锁检测组件应列入目标系统本身, 为了准确地检测到死锁, 我们的想法是基于自我实现的高度可靠的测量原理并发系统。
有对java的动态死锁检测多种产品。我们坚持他们没有足够的完整性。尤其是, 大部分不是正确识别的通知等关系。通过这一原因, 其中大部分无法检测的文件不能将Java死锁的文件检测清单表达出来。
Java平台特有的问题是依赖性:现有的手段是平台依赖新生凹痕, 因为它们取决于特定的虚拟机。既然是独立于平台的Java最显著特点, 有工作的工具之Java程序也希望将平台独立, 它是重要的自我检测的测量原理。
动态检测方法是目前最好的, 从死锁检测领域的角度看, 这是非常类似Java的并发设施, 我们应对与Java特有问题时的Java程序中的死锁检测问题应用此方法。我们将在本文中介绍方法、推行工具死锁报告的一个示例。
2 在Java多线程程序中的死锁
死锁的并发Java程序这样表示:两个或多个线程互相阻塞, 而试图访问所需的同步锁继续他们的活动。在Java死锁通常被视为形成一个公正锁观点, 换句话说, 我们必须意识到我们处理这个问题时的同步等待关系不是只有中止显示器。现在我们需要更严格地定义此问题。
定义1一个线程被认为是阻止处于执行状态的并发Java程序, 如果它在一个或多个线程的同步某些同步点等待着一或多个线程等待状态, 并且将保留此等待状态, 直到出现了同步, 否则该线程已停止。
定义2死锁是一个并发Java程序同步等候在那里的一些阻塞的线程之间的执行状况形成一个周期, 因而在周期所涉及的线程被认为发生死锁。
定义3在一个并发Java程序执行状态被阻塞的线程被认为是如果正在等待同步与死锁的线程被阻止, 但不是涉及周期中的死锁涉及被死锁的线程。
请注意死锁的线程应该被认为被阻止的线程等待不能改变任何被死锁的线程的死锁状态。
定义4一个活锁是一个Java程序的每个线程组的成员一组线程都保持线程组中的沟通, 并因此可以永远不会响应任何外界线程的同步请求, 否则在小组中的任何线程被认为是死锁。
定义5如果一个并发Java程序的执行状态是它正在等待与活锁的线程同步被阻塞就被认为是死锁。
请注意, 它也是重要的区别陷入僵局的形式活锁的线程的封锁, 因为打破了一活锁, 阻塞的线程等候不能改变任何陷入僵局线程死锁状态的线程。
3 运行时死锁检测器中使用Java虚拟机分析器界面
我们开发了基于Java程序的运行时死锁检测仪。它必须能够监视某种目标Java程序运行时所发生的事件。还有其他办法, 一个是运行时环境支持的方法, 而另一种是源代码转换的做法。
Java程序运行在Java虚拟机, 它很容易得到一些运行时间环境的信息。具体地说, Java虚拟机分析器界面 (JVMPI) 是我们的工具, 是监察的Java程序的行为。该JVMPI是在Java虚拟机和一个进程分析器界面, 用于我们的死锁检测的方法过程中探查器代理之间的接口。该死锁探测器部分包括本机代码 (不是字节代码) , 它在Java虚拟机进程运行。当与死锁检测有关每个事件发生时, 有关信息通过JVMPI传递给死锁检测仪。
运行时死锁检测仪使用源代码转换
我们开发了一个运行在死锁探测器上的源代码转换的方法, 目标在Java程序P是由一个预处理器到另一个Java程序P1'中, 使得P1当前行为和执行过程中的P沟通。运行时, 实时监测每个并发事件的P和P1, 并通过有关的运行信息实时监测事件发生的有关事件的信息传递到运行时显示器。
此事件通知时, 探测器需要一个线程被创建, 开始, 结束, 只是要求事件通知和直接进入同步的方法, 只是对接后转出和前后直接等待、加入或通知的所有方法被都调用。
4 此方法的优点和缺点
此方法的优点是它的平台独立性:任何目标程序的工具只不过是一个Java程序, 可以工作更在任何Java虚拟机。从独立测试原则的角度看, 它对测量有耐久性的优势, 因为它可以在任何虚拟机上。但是, 这一问题得到解决, 才能成为我们能够使用我们的僵局探测器上使用任何虚拟机JVMPI。
缺点是运算性能降低。其监测方案使用Java编写的, 其性能降低会比在运行时环境多。
5 结束语
我们研究Java程序中的死锁问题时讨论了如何在运行时及时地发现。同时, 我们制定了两个办法同时基于Java的程序运行时死锁探测器。我们成功的探测计划, 包括从一并发同步所有类型的等待关系陷入死锁。采用哪种方法应由设备的性能和平台独立性来权衡决定。
摘要：关于并行JAVA程序的可靠性, 死锁是最为严重和复杂的问题。在这篇论文中, 我们讨论了在并行JAVA程序运行时如何动态地检测死锁, 并提出了在一个JAVA程序的执行过程中, 处于等待状态的一个同步象征, 被称为JAVA线形等待图表。我们描述了各种类型的死锁, 并提出了一种计算程序来检测死锁和执行方法。
关键词：死锁,检测器,程序
参考文献
[1]卢超, 卢炎生, 谢晓东, 等.一种基于依赖分析的并发程序潜在算法[J].小型微型计算机系统, 2007, 28 (5) :841-844.
并行程序分析 篇4
关键词：可视化,并行程序设计,软件事务性内存,扩展性
0引言
随着计算机硬件技术的发展,多核已经成为目前主流的处理器架构,由于传统的串行程序设计不能充分发挥多核处理器的优势,所以并行程序设计方法的研究成为了一个热点[1]。并行程序一直被用来处理大规模计算和复杂计算等问题,虽然多核计算机的普及给并行计算的应用奠定了良好的硬件基础,但是并行程序设计方法却没有跟上计算机硬件的发展速度,并行编程效率低成为了制约并行程序广泛应用的一个瓶颈。为了解决这个难题,国内外学者在并行程序设计模型及语言方面进行了许多的研究。共享内存和消息传递等并行程序设计方法逐渐进入人们的视野,在一定程度上简化了程序设计人员的开发过程,但是这些模型还是集中在底层功能的调用,要掌握它们还需要进行系统的学习。与此同时,国内外学者在并行程序设计方法领域也做了各个方面的探索,例如并行设计模式、并行结构骨架、算法骨架以及可视化并行程序设计的理论。这些抽象程度更高的理论对于简化并行应用程序的开发有更大的实际意义。在已有的可视化并行程序设计方法中,虽然能够按照一些指定的代码模板进行并行程序设计,但是它的可扩展性和通用性较差。如果用灵活的底层设计方式进行程序开发,开发难度又会大大增加,开发效率也自然会变低。
近年来,软件事务性内存[2]作为一种新兴的并行程序设计模型被越来越多的研究与使用,它接口简单且可扩展性非常强,如果将可视化的编程方法与STM模型相结合,设计一种满足可视化编程要求的STM模型,可以为并行程序的设计提供一种可行的方法,使得并行程序的开发效率有一定的提高。
1相关工作
可视化程序设计[7]是指将程序、数据、系统结构或者系统的动态行为用可视的表现形式来表达。良好的可视化编程模式能够简化系统设计的复杂度,提高程序开发的效率。目前,针对串行应用程序的可视化建模方法和技术已经比较成熟,但是在并行程序设计方面尚且没有统一的标准。从编程模型的角度看,现有的可视化并行程序设计方法可以分为基于模板的、基于数据流的、基于进程的三类。基于模板的可视化并行程序设计通过提供一些用于进程交互的代码模板来构建并行应用程序。并行程序中进程的交互方式和通信结构一般由预先采用的模板决定,程序设计人员只需要提供应用程序的细节处理过程,并将这些细节填充到相应的模板之中,就可以使被整合在一起的程序编程完整地并行应用程序。基于数据流的可视化并行程序设计主要使用数据流图来进行并行程序设计,基于进程的可视化并行程序设计则是让程序开发者自己定义进程结构和显示的消息传递操作。由于传统的基于模板的可视化并行程序设计中模板的单一性和不可变性[8],使得基于模板的可视化并行程序设计方式相对死板,不易变通,如HeNCE是一个利用PVM为开发网络并行程序而设计的并行编程环境,但它的子任务之间不能有数据依赖使得它可用性不强。DPnDP是采用MIMD结构的并行开发模型,但是它不提供创建新模板的工具,只有在一个指定的C++框架内才能建议模板。VPE是为IBM RS6000工作站开发的一个小型可视化并行程序开发环境,虽然功能完善,但是它针对特定的硬件平台。而软件事务性内存具有良好的可扩展性和易用性且接口简单,在STM模型上运行的并行程序进程之间的通信方式和同步策略均可以非常方便的进行扩充和修改。基于STM模型的可视化并行程序设计会使得并行程序设计流程变得简单,增加开发效率,并且由于STM的可扩展性和易用性,使得基于此模板的可视化并行程序设计方法的通用性大大增强,只需要选定不同的仲裁策略和同步方法,就可以使得STM并行程序设计模板满足大多数并行程序设计的要求。
软件事务性内存的执行过程[3]一般分为事务的初始化和启动、事务的执行、事务的提交三个阶段。事务具有ACDI特性,不同事务在执行的过程中彼此独立,在提交阶段进行确认检测防止冲突的发生而影响数据的正确性。STM模型就是通过这种机制保证并行程序的正确执行。在典型的事务性内存模型中,事务对内存对象的访问有读和写两种方式。在一个事务读取内存单元时,它可以采取两种不同的策略,分别是读透明和读可见策略。所谓读透明策略就是事务之间的读取操作彼此独立,一个事物的读取操作不影响其他事务的执行;而读可见策略指的是一个事务读取一个对象时其他事务不能同时对这个共享对象进行读取操作,事务之间的读操作是彼此可见的。与事务的读操作不同,事务的写操作一般都是可见的,不同的事务不能同时对共享对象进行写操作。在面向可视化的并行编程过程中,一方面,用户图形接口要设计的简洁灵活,以保证实际程序开发过程中的可扩展性,另一方面,模型的算法实现要设计的严谨稳定,以保证并行程序运行时的正确定和安全性。ASTM是一种面向对象的软件事务性内存,面向可视化并行程序设计的STM模型是在它的基础上增加了可视化程序设计的必要因素来设计的。
2VPP STM设计
VPP STM模型的架构如图1所示,下面介绍可视化STM模型的实现算法。
2.1事务粒度
事务粒度是事务控制并发程序访问的最小数据单元[4],粗粒度的访问方式会制约多事务的并发执行,事务会由于频繁的访问冲突而回滚或访问失败,而细粒度的访问方式会限制一个事务的执行效率,并且由于共享数据单元划分的太小会导致冲突的检测时间增长,从而影响STM模型整体的效率。在目前常见的程序设计方法中,面向对象的程序设计方法已经成为最重要的开发方式,程序中的数据访问其实是对实例对象属性的访问,这种访问粒度是以对象为单位的,为了保持访问粒度的一致性,我们的STM模型也将采用面向对象的程序设计方法,以对象作为事务粒度的单位进行模型的设计。
定义1 定义事务集合为T(T1,T2,…,Tn),模型中任何活动事务Tx∈T;共享数据对象所在集合为 O(O1,O2,…,On) ,一个事务Tx从启动到提交过程中所访问的数据对象集合为T0∈0。
2.2版本控制与冲突检测
不同的并发事务同时执行的时候,事务与事务之间的操作可能会产生冲突,为了防止事物之间的冲突影响共享数据的正确性,需要版本控制与冲突检测来进行事务之间的并发控制。事务之间的冲突可以分为读后写、写后读、写后写三种。
定义2 每一个共享对象Ox∈O都维护有自身的版本信息集合 V(V1,V2,…) ,每一个版本 Vx都有一个时间戳timestamp作为标识,一个共享对象的版本序列 (V1,V2,…)中的timestamp按版本下标序号严格递增。
定义3 当一个事务Tx对Ox进行写操作并且成功提交后O中的Ox就会被成功修改到最新版本Vnew,此时其他事务就可以看到Tx对Ox修改后的状态了。如果Tx在执行之后提交失败,那么O中的Ox还是维持Tx修改前版本Vold不变。
不同的版本控制策略对STM系统维护的版本数量要求不一样[9],一方面,可以将一个共享内存对象生命周期内被访问的版本数据都保存下来以便事务在提交失败后可以查找指定的版本进行回滚恢复操作,另一方面,也可以用一些临时的存储单元对事务操作共享数据进行一个拷贝,如果事务提交成功,则用拷贝最新的数据对象替换之前的副本,如果事务提交失败,则用临时存储单元之中的数据副本恢复共享数据单元。
为了增强可视化并行程序设计方法的可扩展性,面向可视化的STM采用基于快照[5]的临时数据存储方式,在并发事务较多的情况下避免了数据版本冗长难以维护的缺点。当并发执行的事务在提交过程中检测到了冲突,就要采取一定的策略来选择须要正确提交的事务或者应该回滚的事务[6],仲裁策略通常以时间或者优先级作为仲裁的参考要素,在面向可视化的并行编程模型中,用户通过拖拽图形接口的方式进行建模,不同的程序可能要求不同,例如实时性的控制程序需要以时间作为重要的参考条件而一些内核调度程序需要以优先级作为事务提交成败的标准。在可视化的STM模型中可以用不同的图标代表不同的仲裁策略,在用户需要的时候可以按需要进行并行程序的建模,如图2所示。把可视化程序设计的通用性和直观性与STM的灵活性与可扩展性结合起来,会对提高并发程序的开发效率有很实际的帮助。
2.3事务同步
一个事务在成功提交之后,它对共享数据作出的修改后便对全体事务可见,在它正确提交之后任何事务再对同一共享对象的读写操作都是在这个对象新版本的基础上进行的。这就要求要有一个全局的统一时钟来标识对象的新旧版本,这个时钟对STM系统的全体事务都是一致的,一个事物在访问一个对象时只需要拿这个对象当前版本的时间戳和系统的当前时间作比较就可以知道这个对象是否处在一个一致性状态。
2.4图形接口与算法实现
用户图形接口采用UML类图设计中的活动图来进行设计。活动是某件事情正在进行的状态,它在状态机中表现为有一系列动作组成的非原子的执行过程。活动图的图标包含对活动的描述,如果一个活动引发下一个活动,两个活动的图标之间用带箭头的直线连接,活动图中的一个活动代表一个事务,每一个活动都有一个开始时间,记作代表此活动事务的时间戳。UML活动图中包含的图形元素有动作状态、活动状态、动作流、分叉与汇合等。动作状态是指执行原子的、不可中断的动作,并在此动作完成后通过完成转换转向另一个状态。因为事务具有ACDI的特性,所以活动图中的动作状态对应到VPP STM系统中是指一个事务生命周期中执行的所有动作。一个活动图有很多动作或者活动状态,活动图通常开始于初始状态,这时VPP STM系统要进行初始化操作,即在视图模型搭建好之后,根据UML活动图中用户输入的数据对象初始化整个STM系统的数据集合O。这时启动VPP STM中的第一个事务Tstart:初始化事务的读写数据集合T0,记录事务开始的时间戳 timestamp。之后事务开始执行读写操作并提交,如果提交成功,那么更新T0中所有数据对象的版本信息V0。由于对象在运行时可能会存在两个或者多个并发运行的控制流,为了对并发的控制流建模,在UML中引入了分叉与汇合的概念。分叉用于将动作流分为两个或者多个并发运行的分支,而汇合则用于同步这些并发分支,以达到共同完成一项事务的目的。分叉可以用来描述并发线程,每个分叉可以有一个输入转换和两个或多个输出转换,每个转换都可以是独立的控制流。在VPP STM中,会在每一个分支结点根据结点的出度初始化所需的事务集合T(T1,T2,…),并将每个事务所需要执行的数据操作写入这个事务的读写集合,完成初始化后记录事务开始的时间戳。进入UML的分支后,每一个事务就单独执行自己的任务,在进行读写操作之前,事务首先要申请对共享对象的访问权限:在申请所有权时如果这个Ox现在被其他的Tx拥有, 则比较两个事务的timestamp,终止timestamp较大的(晚开始的)事务。否则获得这个Ox的所有权,并且在这个Ox的V(V1,V2,…) 中寻找一个时间戳小于此事务时间戳且最新的Vnew生成这个Ox的快照。申请到了访问权事务开始对共享数据对象的快照副本进行读写操作:进行读操作时,先在此事务的写集中查找,有则返回。如果没有就返回申请到的Vnew的值。进行写操作时,如果当前事务拥有这个Ox,就直接在事务的写集中进行修改。否则会先进行冲突检测,如果无冲突就申请这个Ox的所有权,若申请成功则把修改值添加到事务的写集中。在UML活动图中,汇合代表两个或多个并发控制流同步发生,当所有的控制流都打到汇合点后,控制才能继续往下进行。每个汇合可以有两个或多个输入转换和一个输出转换。相对的,在VPP STM系统中,事务读写操作完成后,如果没有冲突发生就确认提交:为相应的T0分配新版本,如果有数据更新则将 快照中的值写入新版本,记录提交的时间戳,并将新版本放入这个共享数据对象的版本信息集合中。如果遇到冲突则选用给定的仲裁策略进行事务的回滚操作,事务回滚后此事务的所有操作不对共享对象产生任何影响,在UML中,相当于重新回到分支点再进行一次事务的初始化操作。当所有的事务均提交成功后,整个UML活动图的执行任务才算完成。
3测试用例及实验结果
3.1测试用例
实验用Linklist benchmark来进行测试,在Linklist benchmark中,设定链表元素个数为2000、链表写操作占总操作数作百分比为20%。除了设定不同的账户和存取操作之外,VPP STM还可以用不同的仲裁策略进行设计。用VPP STM 对Linklist benchmark进行建模结果如图3所示。
3.2实验结果
实验环境:处理器:Inter Core 2 Duo CPU (2.66GHz) 内存:2.00GB操作系统:32位Windows 7专业版在上述硬件环境下对用VPP STM建模的Linklist benchmark进行测试,实验结果如图4所示。
用不同的冲突检测策略进行Linklist benchmark的测试结果如表1所示。
4结语
VPP STM将软件事务性内存用到可视化并行编程中,使得可视化并行编程变得相对简单并且灵活,通过对Linklist基准测试程序进行建模测试可以看出VPP STM可以解决实际的并行处理问题,对不同的用例采用不同的冲突控制策略可以更好地满足实际运用的不同要求。同时,实验结果表明,如果开启的线程过多,事务提交时发生冲突导致事务回滚的性能损耗会超过多线程并行处理所带来的性能提升,从而使得系统整体性能相对下降,如何提高事务提交的成功率也是今后研究工作中需要解决的一个问题。
参考文献
[1]Olukotun K,Hammond L.The Future of Microprocessors[J].ACM Queue,2005,3:26-29.
[2]Nir Shavit,Dan Touitou.Software transactional memory[C]//Sysmpos-ium on Principles of Distributed Computing,1997,10:99-116.
[3]Pascal Felber,Christof Fetzer,Patrick Marlier,et al.Time-Based Software Transactional Memory[J].IEEE Trans on Parallel and dis-tributed systems,2010,21:1793-1805.
[4]Maurice Herlihy,Victor Luchangco,Mark Moir,et al.Software trans-actional memory for dynamic-sized data structures[M].ACM Press,2003:92-101.
[5]Christopher Cole,Maurice Herlihy.Snapshots and Software Transac-tional Memory[J].Elsevier Science,2005.
[6]Zhang X Q,Peng L,Xie L G.Lowering Conflicts of High Contention Software Transactional Memory[C]//2008International Conference on Computer Science and Software Engineering.2008.
[7]胡长军,丁良,常晓东,等.面向并行程序设计的扩展UML建模[J].计算机工程,2007,34(1):86-93.
[8]徐祯.面向并行程序设计的可视化建模系统的研究与实现[D].天津大学,2007.
分布并行算法分析与设计 篇5
在过去计算机并行处理技术发展缓慢, 主要原因是计算机电子设备处理器价格比较贵, 网络通信处于前期发展阶段不太成熟, 使用并行技术开发的软件功能和应用上不完善。在20 世纪后期, 随着网络通信技术的迅速发展, 高位数处理器的开发和应用, 给并行处理技术提供了很好的发展空间。在计算机产业中, 人们意识到计算机的处理计算的能力在高科技的技术发展中被人们越来越重视, 并行处理技术是高性能计算机处理技术未来主要技术, 并行处理技术可以大大提高计算机的整体性能。 现代科学技术和全球经济的发展都离不开计算机技术, 计算机技术已经改变了人们的生活方式, 存在各个领域, 计算机技术的发展比其他科学技术的发展要快, 对人类的影响比较深远。 工程领域对计算机计算的需求是无限的, 然而计算机的单机计算是有限的, 这两个关系决定了分布式并行计算方法必然称为计算机计算方法的主导。
2 研究现状
国内在国防和国家科技的建设上, 并行处理技术起着重要作用, 我国对高性能计算机的发展非常重视, 尤其在石油、气象、 航空等大范围领域的研究逐年增加, 我国在并行处理技术领域比其他领域发展显著主要是因为并行处理技术领域的高性能计算机。 国内的科技工作者正努力研究多种并行处理的计算方法, 软件发展的重心主要体现在算法能力上面, 我国研发的数据库并行处理系统处于世界同领域的领先地位, 并行体系结构、 并行系统软件、 并行算法是并行处理技术的3个方面, 我国在高性能计算机的研制方面投入多, 在系统开发方面投入较少, 低成本延迟高带宽、 并行应用软件和并行算法是我国研发的重点。
国外美国、 日本在并行计算方面发展出力领先水平, 美国在商业领域已经应用高性能计算, 并行检索技术, 在并行计算方面的研究资料国外设计的也比较全。 国内外差距大, 我国发展高性能计算机技术不能再等, 算法是研究的重要内容。
3 并行计算机分类和计算环境
3.1 并行计算机的分类
并行算法能够运行的基础主要是并行计算环境和并行计算机, 并行算法的设计和实现取决并行计算机环境和并行计算机, 并行计算机从最初的向量机, 如今并行计算机主要是机群系统, 并行计算机分为SIMD型并行计算机、 共享存储MIMD并行机、 分布式存储MIMD并行机、 分布共享存储MIDI。
SIMD型并行计算机是单指令流多数据流并行机, 在指令流执行的时候, 处理机对多组数据执行相同指令流, 也就是说SIMD并行机无论怎样运行它的指令只有一条, 同步性、 确定性是SIMD型并行计算机的特征, SIMD型并行机已经不能满足并行技术的发展, 是早期产品, 如今已经不被使用。
共享存储MIMD并行机是多指令流多数据, 所有处理机执行统一程序, MIMD并行机是现在并行算法中普遍使用的编码方式。
分布式存储MIMD并行多处理机解决了共享存储MIMD并行处理机的瓶颈问题, 在整个系统中, 每个节点都有自己的存储器, 在访问的时候只能自己访问自己的存储器, 不能互相访问, 各个节点通过网络作为传输介质连接到一起, 分布式存储扩展性强, 但是编程复杂, 在节点之间的信息传递不是通明的, 分不知存储MIDI并行处理机分两类, 大规模处理机和群集系统。
分布共享存储MIDI并行机在系统中每个处理机有自己的存储器, 共享地址空间由各个局部存储器连接组成。
3.2 并行计算机的计算环境
并行计算机体系结构, 并行算法的效率直接受并行计算机体系结构的影响, 在这个系统中处理机的连接方式构成并行计算机体系结构。 并行处理机互连方式主要是网络直径和等份宽度两个重要因素。 网络系统中两个距离较远的处理机之间的具体构成网络直径, 两个距离远的处理机在消息传递的时候出现时间的延迟用网络直径这个参数来衡量。 等份宽度是网络系统中两个相等距离所去掉的网络边的条数。 判断并行体系结构性能重要原则是小的网络直径和大的等份宽度。集群系统中处理机的连接方式用总线结构表示, 在总线结构中, 各处理机连接在一个总线上面, 靠一个总线进行传输, 在消息进行传输时要判断先后顺序, 总线结构图如图1 所示。
并行计算机的软件环境包括编码语言、 操作系统、 计算环境3 部分, 用于消息传递的并行环境常用的是PVM和MPI。PVM并行计算环境叫做并行虚拟机系统, 系统规模小通用性强, 在TCP/IP协议环境下也适用, PVM特点支持多用户同时执行多个应用程序, 提供通信原语, 多个进程组成一个进程组, 同一个进程可以属于多个进程组, 在不同的网络系统中可以使用, 兼容性强, 容错功能强。 MPI并行计算环境是消息传递界面的一种方式, MPI并行计算环境特点实现的开发工具方式多, 消息的发送和接收可以重叠, 对消息缓存区可以有效管理, 可靠地运行在集群系统中, 保证其他软件可以正常运行, 标准平台上也可以使用。
4 并行算法定义及分类
算法是解决某个特定类型问题的解题方法的一系列规则, 并行算法是在解决问题方面相互联系起协调作用的可以并行执行的过程的集合。 并行算法是在并行处理机上把多个问题和任务映射到多处理机进行求解的处理数据的一种方法。 传统的算法树是一维问题的串行算法, 靠算增加算法树的深度来进行大型计算机计算, 并行算法减少时间上的复杂性, 计算量增加, 算法步骤减少, 把时间上的复杂性转化为空间上的复杂性。
并行算法分类, 并行算法根据运算对象不同分为数值并行算法和非数值并行算法两类, 数值并行算法有线性方程组和多项式求解等, 非数值并行算法指排序、 选择、 分类等设计。 并行进程执行顺序不同分为同步并行算法、 异步并行算法、 独立并行算法, 同步并行算法指进程执行要等待其他进程的计算方法, 异步并行算法指进程在执行的时候彼此不用相互等待, 独立并行算法指进程在执行的时候是独立执行的。
5 并行算法设计
用并行处理机系统进行并行计算求解问题一般遵守需要解决的问题本身提出满足需要的特定的并行算法, 或者在相似的问题上把已有的并行算法改变下, 来解决问题原则。 常用的并行算法技术有流水线技术、 分治策略和加速级连策略等。
流水线技术是重要的并行计算技术, 在VLSI并行算法中, 基本设计是把一个任务设置为A, 然后分成几个小的子任务A1、 A2、 …AN, 在执行的时候按顺序执行, 先执行A1再执行后面子任务, 计算速度是一样的。
分治策略就是把问题分解多个特征相同的子问题, 计算机单个结点平均分摊计算机的负载提高工作效率, 子问题的类型和原问题的类型一样, 采用分而治之的原则。
加速级连策略是采用最优算法来解决问题, 开始使用最优算法, 当任务规模缩小到一个值的时候, 使用最快非最优的方式接续完成任务解决问题, 使用最优串行算法并发解决子问题。
并行计算模型把并行机的基本抽象特征表现出来, 从计算模型中可以看出来并行计算模型、 并行算法设计、 并行机三者关系, 并行算法映射到并行机上, 基于并行机进行算法的设计。 计算机模型为并行算法提供了框架和物理基础, 使用多种并行机。 并行计算模型如图2 所示。
并行算法评价标准是加速比和效率, 并行算法在并行机上求解实际问题,
并行算法的加速比
TA串行算法在单处理机上最优运行时间
TB并行算法使用B台处理机的计算时间
并行算法的效率定义
B为处理机台数
在处理台数规模不变的特定情况下并行算法加速比SB和处理机台数B成正比, 也叫算法线性加速比, 如果SB比B多, 那么该算法是超线性加速比。
设计高性能计算机并行算法要充分考虑到并行算法的扩展性, 这也是再设计并行算法结构时要充分考虑到的问题, 扩展性有3 种分别是资源扩展、 技术扩展和应用扩展, 扩展性主要是并行算法在对处理机数目的有效利用的一个度量, 并不是算法内在的通信和并行性需求。
加速比、 效率和扩展性是评价并行算法性能的3 个指标, 加速比是最优串行算法运行时间和B太处理机并行运行时间的比值, 效率是加速比与B的比值, 我们在设计并行算法的时候要充分考虑到加速比、 效率和扩展性3 个指标。
6 结语
从理论和设计方法两方面对分布式并行算法进行了简单的描述, 随着计算机技术的发展, 人们对计算机的数据处理性能有很高的要求, 最初的计算机处理能力已经不能满足计算机领域的发展, 并行处理技术可以提高计算机大数据的并行处理性能, 从国内外并行算法的应用上分析出我国对并行处理能力要加大投入, 才能追上技术领先国家。 分布式并行算法提高计算机的数据处理能力, 在计算机技术领域发挥着重要的作用。 并行处理技术分硬件技术和软件技术, 目前硬件方面有很大的提高, 但是在软件方面还存在问题需要解决, 算法是软件的核心, 要推动并行处理技术的发展, 必须要先重点研究并行算法。
摘要：计算机计算方法从单机技术发展到多机并行技术, 这是计算机计算模式适应未来科技发展的趋势, 国家的科技发展需要并行处理技术的推动, 并行处理技术能快速地发展, 源动力来自于人们对工程计算机能力的需求。在这几年, 并行处理技术得到很大的推动与发展, 并行算法处理技术的应用提高了计算机大数据处理的能力。介绍并行算法应用情况的背景和研究现状, 阐述了并行算法技术的分类及设计方法。
关键词：分布式,并行算法,计算机计算方法
参考文献
[1]许林.群智能算法可并行性分析及其FPGA实现[J].journal6, 2010, 46 (33) :54-57.
视频并行处理系统分析与设计 篇6
关键词：非透明桥,PCI-E协议,并行运算,视频,同步机制
引言
图像与人们的生产生活息息相关, 是人类获取和交换信息的主要来源, 据统计人类有80%以上的信息来自于图像。随着数字化进程的加速普及, 人们对视频的需求提出了更高要求, 电视、内容、数字摄像机等提供的各种形式视频正在向高清转变。高清晰度的视频在各个领域的应用越来越广, 3D技术也日趋成熟, 需要对海量视频数据进行复杂处理的应用越来越多, 这对视频处理技术提出了一个新的挑战。传统的视频处理多采用GPU (Graphic Processing Unit图形处理器) 进行, 限于目前单个显卡的处理能力有限, 需要同时对一个大屏幕的高清视频数据进行纹理映射、颜色混合、3D渲染等操作的场合已经很难胜任了。近年来, 对于视频并行运算的研究取得了很多进展, 提出了很多的解决办法, 但是这些办法都是仅仅解决了视频处理中的某一个问题。例如目前利用网络进行并行运算的计算机系统, 虽然其并行运算的能力较强, 但是对于海量的视频数据, 其数据传输能力有很大的局限性;网络带宽不足以实时地传输信号, 这导致出现图像无法流畅显示的问题, 随着目前需要处理的视频数据量的增加, 这种缺陷已越来越严重。
1 非透明桥技术
非透明桥顾名思义是一座连接两端处理器的桥梁, 且两端的处理器均有独立的地址空间, 桥两端的主机不能看到另外一个主机完整的地址或者I/O空间。在非透明桥环境中, PCI Express系统需要在从一个内存地址空间穿越到另一个地址空间时进行地址翻译。每一个非透明桥 (NTB) 端口都有两套基地址寄存器 (BAR) , 一套是给主设备端用的, 另一套是给从设备端用的。基地址寄存器可用来定义在非透明桥另一端的内存地址空间的地址翻译窗口, 并允许这个翻译被映射到本地的内存或I/O空间。
非透明桥允许桥两边的主机通过便笺寄存器、门铃寄存器和心跳消息来交换一些状态信息。便笺寄存器在非透明桥的两端都是可读写的, 但是, 便笺寄存器的数量在具体的实现中是可以不同的。他们可以被桥两边的设备用来传送一些状态信息, 也可作为通用的可读可写寄存器使用。门铃寄存器被用来从非透明桥的一边向另一边发送中断。非透明桥的两边一般都有软件可以控制的中断请求寄存器和相应的中断屏蔽寄存器。这些寄存器在非透明桥的两边都是可以被访问的。心跳消息一般来自主设备端往从设备端的主机, 可用来指示它还活着。从设备主机可监控主设备主机的状态, 如果发现出错, 它就可以采取一些必要的措施。通过门铃寄存器可以传送心跳消息。当从设备主机没有收到一定数量预先规定好的心跳消息时, 就可以认为主设备的主机出错了[1]。
2 视频处理系统架构
本文提出了一种并行视频处理的系统架构, 具体见图1, 该并行视频处理系统包括了多个视频处理系统, 一个非透明桥和一个视频输出系统。视频处理系统主要完成规定的各种视频处理, 视频输出系统负责完成视频数据对屏幕的输出。非透明桥 (NTB) 用于连接视频处理系统和视频输出系统, 控制数据和视频数据的交互通过非透明桥芯片实现;非透明桥为系统之间提供一个高速的数据交换通道和通信的桥梁。多个视频处理系统和一个视频输出系统通过PCI-E总线和非透明桥 (NTB) 相连接, 利用NTB的交换 (switch) 功能, 实现多个视频系统之间的点对点通信。各个视频处理系统之间相互连接, 每个视频处理系统都可以单独和任意一个视频处理系统之间通信和进行海量数据传输;视频输出系统通过非透明桥的连接, 也可以和任意一个视频处理系统连接, 视频处理系统可以将任意一个视频处理系统的数据输出给屏幕显示。每个视频处理系统具有一个或多个外围设备相关联的信息处理模块, 外围设备信息通过PCI-E协议进出传输。
数据传输中采用了高速的PCI-E传输通道, 该并行架构系统解决了海量视频数据传输的瓶颈问题, 为并行处理提供了硬件基础。单通道的PCI-E总线[2]带宽可以达到10Gbps, 该总线有X1、X2、X4、X8和X16、X32 (X32目前还不支持) 通道规格可选, 如果采用X4, 通道的总带宽可以达到40Gbps (PCI-E 2.0协议) , 单方向带宽可以达到20Gbps。超宽的PCI-E数据传输通道为海量视频数据提供了高速通道。例如逐行扫描制式, 帧率通常为60Hz的1080P无压缩视频, 传输需要3Gbps的数据通道, 采用PCI-E通道可以传输多个1080P视频数据, 保证了视频信号传输的流畅。
3 视频并行处理方法
在图像处理的过程中, 需要对图像进行纹理映射[3]、颜色混合、深度缓冲、模板缓冲等步骤。这些串行步骤的执行均需要非常大的计算量, 并且耗时。因此, 在上述的并行视频处理系统的基础上, 提出了一种并行视频处理[4,5]的方法。我们这里将视频图像的处理分成若干个步骤, 分别由不同的视频处理系统来处理, 最后完成视频图像的处理并通过视频输出系统进行输出显示。每个视频处理系统都具备任意一个图像处理步骤的功能, 它根据上一个数据流携带的处理命令来执行相应的处理。我们在传输过程中对视频流数据进行打包, 一包数据可以包含一帧图像或者几十帧图像, 这可以根据实际的需求而定, 原则是数据交换的次数越少越好, 但是数据包也不能太大, 以至于影响到图像处理的时间。在数据包里边, 专门指定了一个位置用于包含视频数据处理命令。该处理命令在该包数据被成功处理后, 该位置的处理命令改为下一个处理命令。若该包数据没有被成功处理, 该处理命令不变。
该方法人为地将需要使用的视频处理过程分为若干个步骤, 每个步骤分块的原则是处理时间基本相等;视频处理步骤的粒度可大可小, 小至包括一个视频数据的深度缓冲或者对数变换, 大至视频数据的整个3D渲染过程;每个视频处理步骤由系统内的单个视频处理系统进行处理, 同时考虑到每个处理步骤的时间差异性问题, 提出了一种同步机制;在处理过程中, 同一个时间内, 每个视频处理步骤是同时在每个视频处理系统进行的, 达到了并行处理的效果;最后处理好的数据统一由高速的PCI-E通道送至视频输出系统进行输出显示。
因为有了各个视频处理系统间的高速PCI-E通道, 所以数据包传送的时间相对于图像处理步骤的时间来说非常少。每个图像处理步骤都包含了一个完整的流程, 如图2所示。
我们可以将图像处理的过程分为A、B、C、D四个步骤, 每个步骤在一个视频处理系统中执行。如图3所示, 我们采用视频处理系统并行做图像处理。
在T1时间周期内, 由视频处理系统1发起图像处理的命令, 并且将完成了图像处理步骤A后的数据打包, 同时加上图像处理步骤B的处理命令, 发送到视频处理系统2。发送完数据以后, 视频处理系统1继续对后续进来的视频流信号做处理。在T2时间周期内, 视频处理系统2接收到视频处理系统1发送过来的数据包后, 首先分析其图像处理命令, 发现是图像处理的步骤B, 便完成步骤B, 同时打包该处理完的数据并加上图像处理步骤C的处理命令, 将数据发送到视频处理系统3。发送完数据后视频处理系统2继续完成其后续视频流的处理。在T3时间周期内, 视频处理系统1和视频处理系统2在进行视频图像处理的同时, 视频处理系统3接收到发过来的视频数据包后, 对处理步骤命令进行分析, 完成步骤C的处理;处理完毕, 数据打包并添加步骤D的处理命令后发送到视频处理系统4。视频处理系统3继续完成后续的视频流的处理。在T4时间周期内, 视频处理系统1和视频处理系统2在进行视频图像处理的同时, 视频处理系统3接收到发过来的视频数据包后, 对处理步骤命令进行分析, 完成步骤C的处理;处理完毕, 数据打包并添加步骤D的处理命令后发送到视频处理系统4。视频处理系统3继续完成后续的视频流的处理。在T4的时间周期内, 视频处理系统1、视频处理系统2和视频处理系统3同时在做视频图像处理;视频处理系统4接收到数据后, 判断处理命令, 完成步骤D的处理, 此时该包图像全部处理完毕, 便送视频输出系统进行显示。
上述的处理过程只是一个基本视频数据并行处理方法, 它的一个关键在于整个图像处理步骤时间的合理安排, 要求每个操作步骤的划分合理。如果前级操作时间恰好等于后级的操作时间, 则最为简单, 前级的输出直接汇入后级的输入即可;如果前级操作时间大于后级的操作时间, 则需要
对前级的输出数据适当缓存才能汇入到后级输入端;如果前级操作时间恰好小于后级的操作时间, 则必须通过复制逻辑, 将数据流分流, 或者在前级对数据采用存储、后处理方式, 否则会造成后级数据溢出。
4 同步机制与异常处理
为了解决数据溢出问题, 本文在对图像处理步骤进行划分时, 尽量使得每个步骤的处理时间都相同, 这样可以很大程度上缓解前后级之间处理时间不一致造成的矛盾;同时引入同步机制[6], 在多个视频处理系统之间建立一个同步信息传递机制, 每个视频数据包被处理后往同步处理模块发送一个值, 当在一个时间周期内所有的处理步骤往同步处理模块发送了处理完毕的值后, 由同步处理模块发送视频数据流统一下传的命令。
图4为同步模块处理流程, 每次进入一个新的视频图像处理流程后, 同步模块开始计数;在同步模块计数器件, 图像处理的每个步骤处理完毕后, 视频处理系统均会发出处理完毕命令;同步模块接收该命令, 并对此进行判断在该图像处理周期中所有的处理步骤是否处理完毕;如果处理完毕则发出下个处理步骤的同步信号;若没有处理完毕则通过计数器判断该次处理周期时间是否达到T, 如果达到时间T则强制完成该处理周期, 发出下一个处理步骤的同步信号, 如果没有达到时间T则转入判断所有步骤是否处理完毕的流程中。
当强制同步信号到来时, 由于某种特殊情况, 视频处理系统对于本系统的图像处理步骤无法完成, 如图5所示, 在T3周期, 视频处理系统3处理出错。此时, 为了不影响整个处理流程的时间, 将数据包继续往下一级发送, 并且执行相同的处理步骤。在T3时间周期, 本来由视频处理系统3完成的处理步骤C, 出错后, 在T4时间周期, 由视频处理系统4完成。上述提到图像处理步骤A、B、C、D可以根据不同的应用来定义, 处理步骤的粒度可大可小。对于一些比较大粒度的功能分工, 如3D处理和GIS等, 也可以采用上述提到的并行处理方法完成。如图3所示, 可以用步骤A表示3D处理, 步骤B表示GIS处理, 由两个视频处理系统分别完成, 同时在视频输出进行叠加显示;并采用方法中提到的同步机制使得两个系统处理后的图像能同时显示。
5 结果与分析
本文根据目前一些海量数据并行处理的应用限制, 提出了通过非透明桥连接的多CPU并行出现系统架构, 并提出了一种并行处理的方法。该并行处理方法在笔者设计的系统平台中得到了实际应用和验证, 运行效果良好, 突破了单个高性能CPU计算能力, 大大提高了海量视频信号的处理能力;而且该处理方法不会单纯地依靠硬件技术如CPU处理速度等的发展, 可以通过合理调节视频处理步骤来实现快速视频处理的功能, 具有很高的产品推广价值。
参考文献
[1]李才华.PCI_Express非透明桥在智能系统中的应用设计[J];电子元器件应用.2009 (8)
[2]樊博, 王延杰, 孙宏海, 基于PCIe的高速图像注入式仿真系统[J];计算机工程与设计.2014 (3)
[3]薛军涛, 贺怀清, 张宇翔, 等, 典型纹理映射实现方法的研究[J].计算机工程, 2005 (3)
[4]易勇, 分布式并行视频服务器设计技术[J].贵州科学, 2000 (12)
[5]谷国太, 肖汉, 并行计算与并行处理技术的应用研究[J].河南理工大学学报, 2009 (10)
北斗并行频率捕获算法研究与分析 篇7
关键词：北斗,捕获系统,FFT,并行频率搜索
0 引言
由于卫星和接收机存在相对运动, 接收机收到的卫星信号中会有一个多普勒频率偏移量。对于传统的顺序搜索的捕获方法而言, 由于多普勒频偏是未知的, 需要对每一个多普勒频移步进进行码相位搜索, 这就是所谓的二维搜索。假设多普勒频率搜索范围为±10 k Hz, 搜索步进为500 Hz, 这就意味着对一颗卫星的信号完成一次完整的搜索需要41次的频率搜索[1], 对于北斗二代B1频点I支路信号而言, 测距码长为2 046, 设步进1 2码片, 在每次频率搜索中又需要进行4 092次的测距码相位搜索。由此可见, 如果要确认一颗卫星的信号不存在, 需要花费41×4 092个单位时间, 考虑到存在虚警概率, 一次完整的搜索往往花费3~4 min。而采用FFT并行频率搜索, 只需要对每个码相位进行一次频率搜索就可以确定多普勒频率偏移量[2], 此外, 采用子相关器分段积分形式可减少FFT模块收集数据的时间开销, 大大缩短信号捕获所花费的时间。
1 捕获原理
1.1 捕获框架
并行频率捕获算法针对于一个码相位进行相关运算, 相关器采用多个子相关器集的结构, 将输出数据合理组合得到分段相关积分值后进行FFT变换, 确认测距码相位是否对齐并估计多普勒频偏。
如图1所示为单个通道的并行频率捕获框图结构, 输入中频信号通过与本机产生的正弦和余弦信号混频分别得到I, Q两个支路信号, 再和产生的测距码进行相关运算, 测距码周期为1 ms, 则设积分时间为1 mms, 之后送入M级的寄存器中[3]。
在一个测距码周期中相关积分值分别存放在m个寄存器中, 每个寄存器相当于一个子相关器, 本文中称该寄存器为子相关器, 其原理框图如图2所示。
在每次输入一个数据后, 寄存器中所有数据右移一位, 根据不同的参数设置输出端口OUTi的抽头位置对连续的几个子相关器求和。输出n个抽头 (不足n个用零作为输出补足) 后送入n点的FFT模块进行FFT变换。在完成一次变换后对FFT输出数据求模, 找到幅值最大的输出值和对应的k值, 将最大值与设定的阈值进行对比, 若小于阈值则认为测距码相位未对齐, 控制测距码发生器延时1 2个测距码相位;如果模值大于阈值则认为捕获到卫星信号且当前码相位就是卫星信号测距码相位, 并利用k值计算出多普勒频移后控制载波NCO进行精确捕获。
1.2 子相关器原理
北斗B1频点I支路信号在加入多普勒频移fd后形如式 (1) :
式中:A为幅度;D (t) 为数据码;C (t) 为测距码;fc为载波中心频率1 561.098 MHz, φ为初始相位, 不同卫星信号用上标j区分。
经过下变频后, 若不考虑初始相位, 并在测距码周期内数据码不会发生跳变, 则信号变为:
根据测距码的自相关特性得知, 当τ不为0时, 相关积分输出值很小认为无信号。当τ=0时, 表示测距码同步, 此时可以忽略测距码的影响, 针对一颗卫星分析, 相关积分结果为:
根据式 (3) 可以看出, 积分器结果是与fd相关的sinc函数有关, 随着fd增大, 积分器输出总体呈减小趋势, 且当积分时间T*fd为0.5的整数倍时, 积分器值为零。因此时域捕获的频率搜索范围很小, 只能对某一频率附近几百Hz的范围搜索。若T为测距码周期1 ms, 多普勒频偏在每个0.5 k Hz的整数倍附近时, 会使积分结果抵消;若减小积分时间, 使T′=T M, 在不考虑式 (3) 中分母fd的影响, 则同样出现上述现象的频率间隔变成M*0.5 k Hz。
那么, 在1 ms的积分时间中分出M个区间, 则每个区间积分时间大大缩短, 使信号无法从噪声中分辨出来, 因此提出通过不同抽头对子相关器求和的结构。如图2中所示, 设M值为8, 抽头数X=3, 则可以设OUT1的抽头为子相关器1~子相关器3, OUT2的抽头为子相关器2~子相关器4, OUT8的抽头为子相关器7、子相关器8和子相关器1。如此设置即可保证积分器的一定幅值又使每个输出都存在一个固定的间隔, 可作为FFT模块的输入数据。
1.3 频率并行搜索原理
同样考虑测距码已经同步的情况下, 不考虑数据跳变, 采样率fs, 测距码周期内采样点数L, 子相关器级数为M, 每段积分时间为1/Mms, 采用N点FFT变换, 第k点的归一化模值结果为[4,5,6]:
对FFT输出模值进行对比, 当其大小超过预设的门限值后, 说明当前的测距码相位和卫星信号的测距码相位是对齐的, 同时记录k值, 用公式 (5) 值估计卫星的多普勒频移[7]。
当k∈[0, N 2]区间内, 直接代入公式 (5) 计算多普勒频移;当k∈ (N 2, N) 区间内, 将k=k-N代入式 (5) 。由此可见, 对于该系统的最大频率搜索范围是[8]:
2 仿真与性能分析
2.1 子相关器性能
利用Matlab软件, 建立传统的分段积分模型和图1中相关器模型, 前者M值为8, 不采用抽头方式直接选取对应的M作为FFT输入;后者设置M值为8, 抽头数X=3, 抽头方式如1.2节所述。设置fd=1 k Hz, FFT点数N=1 024。如图3所示的FFT输出模值, 传统的相关器模型和改进后的相关器模型在多普勒频移点都有峰值输出, 但改进后的峰值更加明显的区别于其余k值所对应的输出, 这将有利于阈值设定, 降低虚警概率。
2.2 频率分辨率分析
由公式 (5) 得出该捕获系统的多普勒频率估计值的分辨率如公式 (7) , 其频率步进与积分分段数M成正比, 与总积分时间T和FFT点数成反比。
在fd=1 k Hz, T=1 ms的情况下, 分别对以下三组数据仿真:
仿真结果如图4所示, 第一组数据对应峰值在k=124处, 分辨率约为8.0 Hz;第二组数据对应的峰值在k=32处, 分辨率约为31.25 Hz;第三组数据峰值在k=63处, 分辨率约为15.87 Hz。和Δf的理论计算值基本吻合。
2.3 频率搜索范围分析
根据1.3节中的结论, 多普勒频移搜素范围跟子相关器数量M有关, 当总积分时间为1 ms时, 搜索范围为±M k Hz。设置参数M=8, N=1 024, 理论搜索范围为±4 k Hz。使fd以50 Hz的步进从0~10 k Hz递增, 记录FFT输出模值的最大值, 归一化后如图5所示, 当fd大于4 k Hz后输出模值都较小, 基本符合理论计算, 认为该参数下的截止频率为±4 k Hz。此外, 从图中可以看出在带内, 输出的最大模值也会因fd的不同呈现波动, 这种被称为扇贝损失的现象使得某些频点的峰值受到抑制, 造成信号漏补。为减小该损失的影响, 可以通过加窗等方式进行弥补[9,10], 有兴趣的读者可查阅相关资料, 本文不再说明。
3 关键模块的FPGA实现
捕获系统采用多通道并行处理方式, 每个通道原理框图如图1所示, 分为载波模块, 测距码生成模块, 混频模块, 相关器模块和FFT模块及其控制模块。
3.1 多级子相关器设计
上一节中提到的由多个子相关器组成的相关器结构, 在具体实现中每个通道都大量使用相关器, 造成硬件开销的成倍增长。考虑到资源因素, 在设计中采用一个传统相关器对总积分时间T分成M次积分, 每次输出结果输送给对应时刻的寄存器中。而FFT的输入端根据选择不同抽头的组合实现图1的结构。图6为M=8, X=2子相关器的部分RTL图, 积分区间被分为八段, 结果分别放在sub框内对应寄存器中, 8个OUT端口分别连接2个sub寄存器作为FFT的输入信号。
3.2 捕获控制模块
用QuartusⅡ11.0中的FFT变换IP核来完成该系统中的FFT运算。考虑到硬件资源消耗和时间开销, 参数设置为256点。需加入控制模块对FFT变换后的数据分析和处理。首先从FFT模块中读出所有k值对应的实部和虚部输出, 计算模值后对比找出该轮中的最大值并记录对应k值。完成一次变换后, 将记录的数据与预设的阈值对比, 确定是否存在信号, 若超过阈值则通过k值计算出fd值并控制载波NCO调整本机载波频率。需要注意的是, FFT模块中的输出为倒序输出, 计算fd时要调整k值。
4 结语
采用多级子相关形式分段积分, 减少了由于多普勒频移造成积分时间内相关能量相互抵消的可能性。不同段内的相关结果通过抽头重新组合, 提高了抗噪声性能, 充分利用相关器节约硬件资源, 减少数据采集的时间开销。利用FFT变换只需要执行一次计算就可以完成对设置的范围内所有频率的搜索。采用这种方法可以减少北斗接收机捕获过程中对多普勒频移搜索所花费的时间, 从而有效提高北斗接收机性能。
参考文献
[1]谢钢.GPS原理与接收机设计[M].北京:电子工业出版社, 2009.
[2]邓洪高, 王靖, 纪元法, 等.一种快速FFT捕获算法及其FPGA实现研究[J].电视技术, 2012, 36 (15) :100-103.
[3]LIU Gao-hui, CAO Jia-kun.Acquisition method and performance of high dynamic GPS signal[J].Computer Engineering and Applications, 2010, 46 (7) :142-144.
[4]ZHENG Yong-zhi, ZHANG Yong-xue.An improved segmented match filters with FFT approach for GNSS signal acquisition[C]//2nd International Conference on Computer Technology and Development.[S.l.]:[s.n.], 2010:425-428.
[5]QIU Lei, LI Lei.GPS signal acquisition based on FFT[C]//2010 Second International Conference on Information Technology and Computer.Kiev, Ukraine:IEEE, 2010:110-113.
[6]王凯.BD-2卫星信号快速捕获技术研究[D].西安:西安电子科技大学, 2013.
[7]LI Chuan-jun, YANG Shu-xing, JI Zhen.Performance analysis of fast GPS signal acquisition based on PMF and Window FFT[J].北京理工大学学报 (英文版) , 2012, 21 (3) :5-8.
[8]李菊, 陈禾, 金俊坤, 等.基于FFT的两种伪码快速捕获方案的研究与实现[J].电子与信息学报, 2006, 28 (10) :1778-1781.
[9]齐华, 蒋邦英, 冀乐, 等.PMF-FFT扇贝损失补偿方法的仿真与分析[J].中国新技术新产品, 2011 (4) :56-57.