并行化分析（精选八篇）
并行化分析 篇1
并行性分析作为自动并行化系统的重要组成部分,它的基础是前端分析和数据依赖关系的分析。前端分析就是对读入的程序进行扫描分析;数据依赖分析的是语句及变量的之间的数据依赖关系。程序并行化就是在扫描中对程序进行初步并行性分析,然后根据数据依赖关系,判断循环并行的可能性。
文中探讨了人工智能扫描策略,并且对已有策略进行改进。为了实现大型程序中循环级并行性检测得到可靠的、精确的数据依赖关系分析,文中针对传统从数据依赖关系分析的不足研究了精确的数据依赖关系分析技术——数组数据流分析技术。
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.
公务员职务与职级并行政策影响分析 篇2
中共XX区委组织部
中央全面深化改革领导小组第7次会议审议通过《关于县以下机关建立公务员职务与职级并行制度的意见》，这是中央深改组自成立以来，推出的又一个重镑改革方案，让基层公务员再一次看到了职级上升的通道和希望。《意见》的出台，有利于调动广大基层公务员的积极性，是为基层公务员办好事、办实事，一定要把好事办好。综合各类媒体报道，结合我区实际，现就职务与职级并行政策影响作一分析。
一、《意见》实施对基层的积极影响
（一）增加基层公务员收入。多年来，公众就有一种错误认识，认为公务员群众属于高薪阶层，工资高、隐性收入多。其实，公务员尤其是基层公务员，不仅工资不高、待遇较差、工作环境恶劣，而且晋升渠道狭窄，很多基层公务员熬到退休还只是一个科员。最近一两年，给公务员涨工资的呼声日渐高涨，而每当有人提出这个问题，必然引发社会上出现截然相反的声音。十八届三中全会决定明确，要建立公务员的职务与职级并行、职级与待遇挂钩制度。这次深改小组审议通过的《意见》，是对三中全会《决定》和深化收入分配制度改革若干意见的进一步细化和落实。据公开资料显示，目前我国公务员队伍中，有超过90%的公务员属于科员及以下职务，有60%是在县级以下党政机关。而在现行公务员管理体制下，行政级别决定公务员地位的高低及其相关薪酬待遇，一个单位的规格又决定了其领导级别，导致很多基层公务员感到钱途渺茫、当长无望。以前，公务员确实有很多福利和隐性收入，但对基层公务员来说，完全不是这样，他们的工资和收入几乎可以划等号。随着中央八项规定等一系列组合拳的实施，公务员越来越不好当了，一段时间甚至出现了公务员离职潮。近年举行的国考，报考人数和参考人数双双下降，也印证了公务员不再是香馍馍的传言。县以下机关建立公务员职务与职级并行制度，让基层公务员不升职也可涨工资，不但让基层公务员看到了钱途，而且可能改变他们千军万马挤独木桥去争当长的局面，让基层公务员有了想头和奔头。
（二）吸引优秀人才选择基层。《意见》使公务员晋升方式更趋合理，对于基层公务员岗位留住优秀人才是一项利好政策。从近两年的基层公务员参考情况来看，基层公务员难于晋升以及衍生出的待遇不易增长问题，进一步加剧了公考时很多基层职位遇冷的问题，相关岗位不仅招不到优秀人才，甚至连报名者都寥寥无几甚至零报考。由于入职后多年无法晋升提高自身待遇，使得不少基层公务员岗位成为了一些大学生的跳板，工作一两年要么寻求上调机会，要么转行另行择业，优秀人才很难踏踏实实地长期坚持下去。目前在一些地区，市级公务员经常三五年就能实现一级晋升，而县以下公务员明显存在晋升慢的问题。虽然《意见》没能抹平这种差距，但已经有效缩短了这一差距，使得公务员相关管理制度正向更公平的趋势发展。《意见》以直接增加公务员基本工资的方式实施，只要符合任职年限等条件，基层公务员都可享受到这一政策的优惠。《意见》的出台体现了政策正加大向基层公务员倾斜力度，也有助于公务员工资制度改革的整体推进。《意见》的实施，将吸引更多的优秀人才到基层一线工作，促进基层经济社会发展快步前进。
（三）稳定基层公务员队伍。大多数的公务员在基层，数以百万计，但现有制度供其升职的领导职务非常有限，由于职务晋升的僧多粥少，以及公务员薪水与职务的绑定，使得很多基层公务员待遇长期维持在较低水平。一边是大部分基层公务员的注定升职无望，以及薪酬待遇在职务提不上去的情况下的长期走低，另一边则是包括生活压力、社会评价压力在内的各种煎熬、忍耐或者离开，成为可能性最大、但也最消极的无奈选择。基层留不住人才，积累够一定工作经验要么再考，要么离开，这与国家层面长期以来反复重申重视基层的决心相较，显得非常不匹配。职务与职级的并行制度，就是在提拔之外，尝试给基层公务员另一条路。不当官也可以涨待遇，于普通公务员来说，安于本职工作、立足基层同样可以得到考核、晋升机制的肯定，这是在给注定要做分母的大多数基层公务员多一种可预期的希望。同时，因为职级薪酬在职务序列之外的按步骤调整，有助于改善基层公务员的收入水平，这也与目前公务员涨薪幅度侧重基层相吻合。随着这项制度的推广和普及，县以下公务员的职业生涯发展通道问题将得到有效解决，这有利于基层公务员安心在基层长期工作，也有利于减少基层公务员腐败的问题。
二、需要解决的几个问题
（一）解决好考核走过场的问题。《意见》中明确规定，任现职级或职务期间每有1个年度考核为优秀等次，任职年限条件缩短半年；每有1个年度考核为基本称职等次，任职年限条件延长半年。现有的公务员考核办法，每年都是进行打勾的方式进行，往往碍于面子，在年终考核时大家都会你好，我好，大家好，都在基本称职或以上的等级。因此，就需要注意，如果不建立完善科学管用的业绩考核机制，晋升职级仍然是一件模糊的和没有依据的事情，而造成的后果又会是一把手有更大的话语权，为腐败现象滋生带来机会。
（二）解决好财政负担问题。全市各县区财力有限，难以承担挂钩后的财政压力，也是需要认真思考的一个问题。而事关财力的问题，是需要根据职务与职级并行这一具体细化的政策，来通过财政渠道配以相应的资金，更需要统筹设计顶层安排，这样才能为基层公务员的职务与职级并行改革解决另外一个后顾之忧。
（二）引导好社会误解问题。公务员职务与职级并行，肯定是基层公务员重大利好。诚如中央深改会议指出，在全国县以下机关实施这项改革，有利于调动广大基层公务员的积极性，是为基层公务员办好事、办实事，一定要把好事办好。要把好事办好，应防对此举误读。不少媒体将职务与职级并行制度解读为不当官也能享官员待遇。其实，这是一种误读。县以下机关建立公务员职务与职级并行制度，相当于打破了目前职务决定待遇局面，为基层公务员多开辟了一条更易上升更为宽阔的通道。然而，但绝不等于不当官也能享受官员待遇。因为，无论你是什么层级的公务员，不当官也能享受官员待遇只是一种制度可能，并不意味着人人都能梦想成真。实行公务员职务与职级并行，根本目的并非像某些媒体所渲染的，是为了不当官也能享受官员待遇，而是意在推进公务员分类改革，建立公务员职务与职级并行制度。事实上，公务员职务与职级并行，让不当官也能享受官员待遇成为基层公务员实现职业梦的同时，随着加强考核等相关配套制度的跟进，也对公务员履职尽责岗位表现提出了更高的要求。公务员职务与职级并行，与其说是福利诱惑，实质是压力动力。
三、几点建议
（一）突破单位级别限制。就制度改革本身而言，首先，应解剖现行制度积弊的体制性成因。一直以来，公务员的职级与职务是紧紧挂钩的。弊端之一是，没有职务，职级就无法晋升。县以上有处级的调研员、巡视员等虚职；科级及其以下没有虚职。弊端之二是，公务员职级过度依赖其单位的级别，导致庙大和尚大、庙小和尚小，一个能干的基层公务员到退休可能只是科级，而国家部委中的能力普通者退休前至少是处级，明显不公平。这是体制性问题，须进行制度设计上的调整。其次，应尽可能明确这项改革的目标：处级目标应是职级与职务相对分离，分开考评、升降，并建立相应待遇制度。职级对应的考评、调整，应主要以德、能、实绩、资历为依据，但也要考虑其所在单位的级别。县以下公务员的职级，可以到县处级，特别突出者可以到地厅级；或者按公务员分级，合理确定职级的上下区间。
（二）完善相关制度机制。公务员职级改革，还需诸多关联性制度改革措施的配套。应健全公务员的退出机制，取消事实上的铁饭碗。对每个公务员职位，须作尽可能明确的职责规定，并对其履职状况进行内外部评价。比照事业单位的聘期制，对部分公务员也实行聘期、任期制，打破终身制。应对不同种类的、同职级的公务员，应按照公务的复杂性、危险性、紧迫性程度，实行合理的差别待遇：如刑警的待遇应高于大多数种类的公务员。另一重难点是公务员的考评、奖惩、升降的公平性及相关激励机制问题。应严格约束长官意志，建立民主评定、申诉和调查、举证义务、责任追究等制度。在提升干部的职级时，应公开对组织、公众承担证明义务，并对被晋级者的德、能、绩及法治意识、守法状况承担担保责任；对于不公平、不正当的升降，应严格追究负责人的责任。概言之，在此项改革中，要注重对症下药、方法缜密、公开公平、厉行法治，特别是管束好各级负责人，丝毫不能含糊。
并行化分析 篇3
随着计算机科学技术的飞速发展,计算机软件使用的越来越广泛,规模也不断变大,调试和维护变的越来越困难,如何程序中有效的找出漏洞和错误是当前开发者必须要面对的一个关键问题,尤其是在一些对安全性要求很高的领域(如医疗、航空等)。 C语言作为一门主流的编程语言,在操作系统、编译器、嵌入式软件等领域得到广泛使用,这些软件的安全性问题直接影响整个软件领域的安全。与其他语言相比,C语言具有指针、动态存储分配、无数组越界动态检查等语言特性,导致C程序容易出现空指针脱引用、内存泄漏、缓冲区溢出等诸多内存安全漏洞。这些内存安全问题给软件系统带来性能影响,甚至会有安全隐患、运行崩溃等问题。
就目前来说,静态分析是较为经济、有效地提高程序安全性的一种重要方法。相比于软件测试, 程序静态分析可以做到更早、更全面、较高效和低成本地检测到程序中的缺陷,提高程序的可靠性。静态分析通常不需要修改源代码,不需要执行程序, 并且能够给用户更好地反馈,比如出错行号、出错原因等等。
符号执行[1,2]是目前使用较多的静态分析技术。 符号执行的思想是,用抽象的符号表示程序中变量的值来模拟程序的实际执行。目前基于符号执行技术的静态分析工具有KLEE[3]、Clang Static Analyzer[4]等。工具Shape Checker基于编译器框架LLVM[5]和KLEE,采用符号执行技术设计、实现而成。它读取待分析程序的LLVM字节码,经过符号执行引擎分析后,将错误和警告等信息反馈给用户。
对于Shape Checker和市面上其他的静态分析工具来说,分析性能是一项重要的指标。性能直接影响工具的可缩放性和实用性。如果静态分析工具使用并行化分析技术,充分使用多个处理器来分析程序,就可以有效地提升工具的分析性能,增强工具的实用性。
本文主要讨论工具分析的并行化,主要的贡献在于:
在Shape Checker中设计实现了符号执行调度算法。
Shape Checker从函数与路径两个层次上分析程序,需要有相应的调度算法去选择可分析的函数和路径,再由符号执行引擎去分析这些函数和路径。
在Shape Checker中设计实现了函数层次和路径层次上的并行化分析算法。在Shape Checker中, 函数层次和路径层次是两个可以采用并行化技术的分析层次,在这两个层次上进行并行化,可以提升Shape Checker的分析性能。
实现了Shape Checker原型系统。原型系统支持对单链表、双链表、树等形状的分析,主要寻找C程序中与内存相关的错误。目前系统可以分析规模在万行左右的C程序,可以找出代码中空指针脱引用、缓冲区溢出、内存泄露等错误。
本文的结构和组织如下:第1节整体介绍我们的工具Shape Checker;第2节着重描述并行化分析的设计与实现;第3节列举实验数据和分析结果;第4节是相关工作比较及总结。
1.ShapeChecker工具介绍
S h a p e C h e c k e r是我们在K L E E的基础上基于LLVM开发的一款专门分析C内存安全的静态分析工具。它主要用来分析C语言中的一些常见的内存错误如:空指针脱引用、内存泄漏、多次释放以及数组越界等。图1是Shape Checker的工具框架图:
图1工具框架图 (参见右栏)
从整体上看,它的工作流程如下:首先由Clang[6]将待分析的程序翻译成LLVM字节码;然后Shape Checker的前端的参数解析和代码管理部分将字节码读取进去,并进行一系列的初始化工作。随后由符号执行引擎分析每个函数和函数内的每条路径。 对于每个函数,最终都会获得相应的分析结果,然后以较为友好的方式将信息打印出来。
KLEE是一款使用符号执行技术生成测试例的静态分析工具。与它相比,Shape Checker主要在以下这几个方面进行改进:
引入断言和库函数模型更好地描述函数行为。每个函数都有一组行为,每个行为包括执行函数前参数满足的前条件、不同函数行为应该满足的守护条件以及函数执行之后的后条件等断言。
加入形状分析,可处理链表、树等形状。
符号执行引擎以函数和路径为分析单位,可以在这两个层次上使用并行化分析技术,提升工具的分析性能。
在讨论工具在函数层次和路径层次上的并行化分析前,先介绍在Shape Checker中每个函数和函数内的每条路径的分析过程。1.1节介绍在工具中每个函数的分析过程;1.2节介绍在工具中函数的每条路径的分析过程。限于篇幅,更详细的介绍可以在[7]中找到。
1.1函数分析过程
在Shape Checker中分析每个函数时,根据函数的每组前条件,分析得到对应的后条件。每个函数的前条件主要由自身的指针参数的有效性构造得到。
以图2的程序为例。在函数swap中,num1和num2为两个指向int类型的指针,按照num1与num2是否为有效指针进行讨论,我们需要分4种情况来构造前条件,也就是生成了4组不同的前条件。 每组前条件可以分析得到对应的后条件。每组前条件、后条件等组成一组函数行为,多组函数行为组成一个函数规范。这里swap的函数规范包含4组函数行为。这样的好处是,每个函数仅需分析一次, 然后在调用点处,根据分析时的上下文,选择对应的函数行为。以函数main为例,它调用了swap函数, 传递了两个非法地址(即两个无效指针)给swap函数,那么直接应用swap函数对应的函数行为,继续往下分析。
上面并没有说明swap函数和main函数的被分析次序,这依赖于不同的分析策略。如果工具沿调用链分析每个函数,那么符号执行引擎先分析main函数。 然后在调用点发现swap函数没有生成对应的函数规范时,会暂停分析main函数,转而去分析swap函数, 等swap分析完成后再继续分析main函数。也就是说函数的被分析次序与程序实际的运行次序一致。
1.2路径分析过程
下面介绍在Shape Checker中是如何分析函数中每条路径的。对于函数内的每条路径,都有一个分析状态(记录各种分析信息)和一个路径约束(Path Constraints)相对应。每个状态维护着大量的运行、 分析信息,如执行到哪条指令、当前函数分配了哪些内存空间等。而路径约束则是记录分析每条路径过程中所遇到的约束关系,这些约束关系被求解器用来求解表达式。每执行一条指令,当前状态和约束就会被更新。当路径约束不满足时,对应的路径分析就会终止。如果函数内部没有分支语句,那么从开始分析此函数到分析结束,都只有一条路径, 也就是只有一个状态和路径约束。如果有分支语句出现且判断条件不确定,那么就会产生新的状态与路径约束。
在图3的例子中,初始时函数有一个状态S和空路径约束C。当分析到第一个if语句时,由于a与b都是符号值,并不能判定a与b的大小关系,将S和C分别复制一个副本,S'与C'。然后将a<b加入到路径约束C中,a >=b加入到路径约束C'中。然后使用状态S与路径约束C分析真值对应的代码(路径),状态S' 与路径约束C'分析假值对应的代码(路径)。
然后在第二个if语句处,由于不能判断a < c是否成立,因此与上面类似,复制、生成新的状态与路径约束。此时会有4个不同的状态与路径约束,也就是有4条路径需要分析。分析switch语句也会类似地复制、生成新的状态与路径约束(依据case的个数)。当在循环中出现分支语句时,路径的数量会增长的非常快,对应的状态与路径约束数量也会非常多。
在实际分析路径时,对约束求解器的查询操作是很频繁的。函数内不同的路径在分析时,可能会有相同的约束求解查询操作。为了避免冗余的查询操作,原型工具封装了一层约束求解查询缓存,记录已查询的操作。这样可以充分利用分支之间的关联性,避免约束求解器反复进行相同的约束求解操作。
2.并行化分析的设计与实现
基于前面介绍了工具分析函数和路径的过程, 本节主要讨论工具Shape Checker在函数层次和路径层次上的并行化分析的设计与实现。首先说明在函数层次和路径层次使用并行化分析技术的原因。
根据1.1节介绍的函数分析过程,工具能在函数层次开展并行化分析的原因在于:
每个函数是一个独立的分析单元。
每个函数仅需分析一次。在调用点,调用者可以根据分析时的上下文条件选择被调用函数对应的函数行为。
根据1.2节介绍的路径分析过程,工具可以在路径层次展开并行化分析的原因在于:
函数中每条路径是相互独立的,每条路径都拥有自己的状态与路径约束。
原型工具封装了一层约束求解查询缓存,避免在分析每条路径时进行重复的查询操作,充分利用分支之间本身存在的关联性,约束求解器不会进行冗余的约束求解操作。
下面介绍并行化分析的设计与实现:2.1节首先介绍并行化调度算法,这部分负责将函数层次和路径层次的分析任务交给符号执行引擎去分析;2.2节介绍函数层次并行化分析的设计与实现;2.3节介绍路径层次并行化分析的设计与实现。
2.1并行化调度算法
工具在函数层次和路径层次上展开并行化,需要有调度模块将要分析的函数或路径交给符号执行引擎去分析。工具在函数层次维护一个函数等待队列, 将等待分析的函数放入队列中;在路径层次维护一个状态与路径约束队列,将等待分析的路径的对应的状态和路径约束加入到队列中;在调度模块维护一个任务队列,将要分析的任务加入到队列中。每一个等待分析的函数或者等待分析的路径都有一个对应的分析任务。调度算法如图4所示。
初始时,任务队列为空。每当任务队列为空时, 调度模块就会从函数等待队列和状态与路径约束队列中取出所有的待分析的函数和状态与路径约束, 并为每个函数或状态与路径约束对应的路径创建对应的分析任务,然后将这些任务加入到任务队列中。 如果函数等待队列和状态与路径约束队列都为空, 那么调度模块会去检查是否所有的函数都已分析。 如果是,说明分析完成,否则继续等待新的分析任务。调度模块在没有超过工具最大的并行化分析数量的情况下(可参数制定),从任务队列中取出任务,交给符号执行引擎去分析。这个过程一直持续到所有的函数都分析完成。
2.2函数层次并行化
从1.1节可以知道,函数之间的调用关系会影响到符号执行引擎分析函数的次序。在Shape Checker中,函数层次的并行化需要函数调用图信息。生成函数调用图的难点在于对函数指针的分析。工具原型采用了Chris Lattner[8]提出的算法来分析函数指针, 进而构造整个的函数调用图。然后将库函数和一些LLVM内置函数从函数调用图中移除。对于这些函数,要么我们的工具不进行检查(如LLVM中的llvm.dbg.declare函数),要么为其建立了相应的函数规范(如strcmp函数)。
图5函数层次并行化算法(参见右栏)
拥有调用图信息后,按照调用图,自底向上的分析每个函数。我们维护一个函数等待队列,将可以分析的函数加入到这个队列中。同时对每个函数维护一个对应的分析状态,如果函数还未加入队列, 那么将函数标记为初始状态。当函数加入到队列中但是还未分析时,记为未分析状态。若函数正在分析,那么标记为正在分析状态。最后函数分析完成后,标记为已分析状态。相关算法如图5所示。
开始分析时,我们将所有的没有调用其他函数的函数和递归函数加入到等待队列中,因为前一类函数不需要应用其他函数的函数行为,而递归函数由符号执行引擎单独处理。函数等待队列中的函数会由调度模块取出,制定对应的函数分析任务后, 加入到任务队列中。在某一时刻,调度模块会将任务取出交给符号执行引擎去分析。当此函数任务分析完成时,对应的函数就完成了分析。
从函数调用图中可以获得每个函数的所有调用者的信息,每分析完一个函数后,就检测它的调用者中是否有函数可以进行分析。这样不断地更新每个函数状态,并将新的可分析函数加入队列,直到所有的函数都已分析。另外递归函数需要特殊处理, 在分析前将递归函数标记出,分析引擎会直接处理整条递归链上的函数。
函数层次并行化分析的实质就是同时分析多个相互之间不存在调用关系的函数,达到提升工具分析性能的目的。
图6示例程序和调用图(参见下页)
以图6(a)中的示例程序为例说明具体的分析过程。依据图6(b)的函数调用图信息,初始时将函数func1加入到函数等待队列中,因为func1没有调用其他函数。待func1分析完成后,会检查func1的调用者f u n c 2和f u n c 3是否可以加入等待队列。这里函数func2和func3是可以加入到等待队列中,因为它们所有调用的函数都已被分析。然后可以并行地分析函数func2和func3。函数func2和func3分析完成后,也会去检查自己所有的调用者是否能加入到等待队列 。最后将main函数加入到等待队列。当main函数完成分析时整个分析过程就结束了。
2.3路径层次并行化
在路径层次展开并行化使用的算法是:为每个函数维护一个队列,放置每条路径的状态与路径约束。调度模块会从队列中取出状态与路径约束,制定对应的路径分析任务,并将任务加入到任务队列中。在某一时刻,再由调度模块将任务交给符号执行引擎去分析,此时开始分析对应的路径。当执行过程中产生新的状态约束对时,将其加入到状态与路径约束队列中。相关算法如图7所示。
开始时,将初始的状态和路径约束存入队列。 每当遇到if或者switch语句时,如果产生了新的状态、约束对,那么将其加入到队列中。当队列为空时,会等待新的状态和路径约束加入。当所有的已分析或正在分析的路径都执行到函数的return语句且队列为空时,那么完成了对这个函数内的所有路径的分析。
在工具实际运行时,有可能会从命令行参数设定状态与路径约束的最大个数。如果发现队列中的状态与路径约束的数量已经达到上限值,那么就会限制新的状态与路径约束加入到队列中。当函数分析所用的时间超过设定时间时,需要将队列中所有的状态与路径约束删除,然后停止分析。
以1.2节图3中的branch函数为例说明路径层次的并行化分析过程。初始时队列中仅包含初始的状态与路径约束(状态为初始状态,路径约束为空)。 当初始的状态与路径约束被取出后,开始分析branch函数。当遇到第一个if语句时,会产生一个新的状态与路径约束,将其插入到队列中,然后继续往下分析。在第二个if语句处,也是如此。队列中其余的状态与路径约束会在某个时刻被取出,然后符号执行引擎会分析对应的路径。
3.实验结果
3.1实验数据
实验的主要目的是为了测试并行化分析技术能否有效地提升工具的分析性能。测试程序采用的是GNU Coreutils[9,10]中的程序,这些程序是Linux操作系统下常见的命令行程序,如ls、cd等。我们在搭载Intel(R) Xeon(R)CPU E5645@ 2.40GHz处理器的12核服务器平台上进行测试。我们分别测试工具使用单线程、四线程和八线程分析程序时的分析性能。源代码规模是指程序的实际C代码规模,字节码规模是指程序编译后的LLVM字节码规模。分析时间是指分析过程结束时,总的使用时间。在运行时设定的参数条件为:max-solver-time=2 analysis-time=600max-loop-br=6。其中max-solver-time指定求解器的最大求解时间,analysis-time指定每个函数的最大分析时间,而max-loop-br指定每个循环所产生的最大状态数量,限制状态的进一步增多。为了在分析时能够有效地控制状态的规模,指定上面的一组数据。 表1是实际的测试数据。表2是性能加速比图。
表1实验数据(参见下页)
3.2数据分析
表2由表1中的数据计算而成。表2的纵轴为加速比,以工具使用单线程分析程序时的分析性能为基准,计算工具使用4线程以及8线程分析程序时带来的分析性能加速比。从表2中可以看出,工具使用4线程分析程序时的分析性能为使用单线程时1.5至2.3倍,使用8线程时的分析性能为使用单线程时的2.8至3.9倍。从上面的分析可以看出,在函数层次和路径层次采用并行化分析技术确实能有效地提升分析性能。
4.相关工作比较及总结
本文主要在一个基于KLEE的C语言静态分析工具上,设计并实现了函数层次和路径层次上的并行化技术,这提高了工具的分析性能。使工具有更好的实用性和可伸缩性。
我们将Shape Checker与Parfait[9]静态分析工具进行比较。Parfait是Oracle公司开发的一款专门分析C/C++程序中缓冲区溢出、指针相关错误和字符串相关错误的静态分析工具。Parfait针对错误和漏洞类型设计并行化分析技术,提升分析性能。Parfait为每种不同的错误和漏洞建立对应的工作列表,然后为每个工作列表进行程序切片。再对每组程序切片进行分析,找出程序中特定的错误和漏洞。 Parfait通过并行地分析这些程序切片来提升分析性能。与Parfait相比,Shape Checker则是在函数层次和路径层次上使用并行化分析技术。
尽管目前采用并行化的分析方案后,能有效地提升分析性能,但还可以从以下几个地方进行改进和优化:
(1)改进函数指针分析算法,获取更加精确的调用图。函数并行化分析方案依赖于函数调用图信息,调用图信息越精确,对函数的并行化分析的帮助就越大。目前调用图信息不精确的地方在于不能有效地分析出函数指针数组,这可能导致函数调用图中函数之间的相互调用数量多于实际值,不利于在函数层次展开并行化分析。
(2)结合路径合并技术,更有效地提升路径层次的分析性能。前面可以看到,当分支语句较多时,状态数量会变得很多,如果能有效使用路径合并、状态合并等技术,减少重复性或者与分析无影响的状态,那么可以更加有效地提升路径层次的分析性能。
参考文献
[1]James C.King,Symbolic execution and program testing[J].Communications of the ACM,1976,19(07):385-394.
[2]Cristian Cadar,Koushik Sen.Symbolic execution for software testing:three decades later[J].Communications of the ACM,2013,56(02):82-90.
[3]Cristian Cadar,Daniel Dunbar,Dawson Engler.KLEE:Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs[C]//USENIX Symposium on Operating Systems Design and Implementation(OSDI 2008).USENIX Association,2008.
[4]The LLVM development team.Clang Static Analyzer[EB/OL].(2015-2)//[2015-2-5].http://clang-analyzer.llvm.org.
[5]The LLVM development team.The LLVM Compiler Infrastructure[EB/OL].(2015-3)//[2015-3-10].http://www.llvm.org.
[6]The LLVM development team.Clang:A C Language Family Frontend For LLVM[EB/OL].(2015-2)//[2015-3-2].http://clang.llvm.org.
[7]The Shape Checker development team.Shape Checker[EB/OL].(2015-2)//[2015-03-13].http://kyhcs.ustcsz.edu.cn/~shapechecker/.
[8]Chris Lattner.Macroscopic Data Structure Analysis and Optimization[D].Urbana-Champaign:University of Illinois at Urbana-Champaign,2005.
[9]The GNU Coreutils development team.GNU Coreutils Project Archives[EB/OL].(2015-3)//[2015-3-5].http://ftp.gnu.org/gnu/coreutils/.
[10]The wikipedia development team.GNU Core Utilities[EB/OL].(2015-2)//[2015-3-16].http://en.wikipedia.org/wiki/GNU_Core_Utilities.
[11]Cristian Cifuentes,Bernhard Scholz.Parfait-Designing a Scalable Bug Checker[C]//Proceedings of the2008 workshop on Static analysis.Communications of the ACM,2008.
动态碰撞网格的DSMC及其并行化 篇4
1.1 DSMC算法的背景
通常气体动力学中对气体的处理采用连续介质假设, 但当气体密度很低时, 气体的粒子效应会变得十分显著, 从而破坏连续介质假设。这种情况下需要采用稀薄气体动力学的方法才能得到正确的结果。在导弹、飞船和航天器的设计中, 稀薄气体动力学有着重要的应用。
稀薄气体的运动规律由波尔兹曼方程描述, 但这是一个带积分项的偏微分方程, 除了某些特殊情况, 极难得到解析解。并且由于带有积分项, 因此偏微分方程数值算法也不能很好地适用, 这使通过数学模型方法来研究稀薄气体问题陷入困境。
DSMC方法是由Bird[1,2,3]提出。该方法没有从波尔兹曼方程出发, 而是直接通过模拟分子的运动和分子间相互碰撞, 得到气体的宏观情况。与传统的模型方法相比, 它简化了模型, 易于引入各种物理和化学模型, 且得到了实验数据的很好验证。现在DSMC已经成为了求解稀薄气体问题的一种全能算法。
1.2 DSMC算法简介
DSMC方法用大量模拟分子来模拟真实气体中分子的运动过程。由于气体分子运动的确定性计算量非常大, DSMC通过对分子运动和分子间碰撞进行解耦, 且在计算中采用了Monte Carlo方法, 减小了计算量, 使大数据量的分子模拟成为可能。
图1为DSMC的算法流程图, 其中的具体步骤说明如下:
1) 初始设置 根据流场的初始条件 (温度、密度、初始速度等) , 以及模拟分子的条件 (模拟比例、能量模型等) , 设置模拟分子的位置、速度、能量。并根据流场和固壁的条件划分网格, 使网格中的分子数量及网格的大小在一个合理的范围之内。
2) 分子移动 计算分子在其当前速度下, 经过一个时间t之后的位置, 分子的移动采用确定性的算法。同时, 在这一步要考虑分子与固壁的碰撞和能量交换, 分子与固壁的碰撞计算采用Monte Carlo算法, 保证碰撞过程前后动量和能量的期望守恒。
3) 分子标定 根据分子移动后的新位置, 标记其所属的网格。
4) 分子碰撞 对流场中的每一个网格, 根据网格的信息计算碰撞次数N。然后随机选取网格中的N对模拟分子, 按照碰撞模型重新计算分子对的速度和能量分布。
5) 判断结束 重复以上2) -4) 步直到满足结束条件。
6) 输出宏观量 采样网格中的分子信息, 计算得到整个流场的宏观性质。
1.3 DSMC算法的不足
尽管DSMC算法的优点很多, 但其缺点也是很明显的, 主要有两点:
1) 网格处理复杂 DSMC方法中的网格是固定的。为了保证计算结果的准确性, 对网格的大小及网格中的分子数都有一定的要求。但实际中流场的情况千变万化, 实际计算中需要根据算例的情况采用复杂的网格生成算法甚至是手工生成网格。在流场发生变化时, 还需要不断调整并重新划分网格, 十分不方便。
2) 计算量大 除了网格问题, 实际使用中DSMC方法最大的问题就是计算量大、计算时间长, 以至于到了现有单机无法承受的地步。一个典型的DSMC算例需要计算几万个时间步长, 计算几十万的网格和几百万的模拟分子, 这样的计算量在单个CPU上所花费的计算时间是无法承受的。
1.4 本文对DSMC算法的改进
针对DSMC方法存在的不足, 本文在两方面对DSMC算法进行了改进。 (1) 将原先DSMC算法中的固定碰撞网格部分改为动态生成网格, 使DSMC算法可以做到对复杂流场和流场变化自适应。 (2) 对动态网格的DSMC进行了共享内存模型的并行化, 提高了其在单机上的计算效率。
2 DSMC网格和并行化相关工作
根据网格的不同, 现有的DSMC方法大致可以分为两类, 一类是非结构的适体网格程序, 另一类是以位置元方案为主的直角结构网格[3]。 这两种方法各有优缺点。 非结构网格可以适应复杂的流场条件, 但是追踪分子的算法复杂且效率低下。位置元方法是直角坐标网格的进一步改进, 但存在分子与表面元的碰撞判断复杂低率的问题, 且影响了DSMC的精度和准确性。
在DSMC的动态网格方面, 就笔者所知, 仅有Olson等人研究了无网格 (动态网格) 的DSMC方法[7]。该文使用八叉树 (Octree) 作为动态空间划分的结构, 但其对网格的处理较为繁复, 也未对无网格算法的性能进行比较实验。
在DSMC算法的并行方面, 由于实际应用中对DSMC算法的需要以及DSMC本身所要求的大量计算, 对DSMC算法的并行化研究很早就展开了, 如文献[4,5,6]。随着计算机硬件的发展, 多核CPU成为发展的趋势。如何使DSMC算法充分利用现有多核架构的计算能力已经成为新的研究课题。
3 DSMC的动态网格算法
3.1 DSMC中网格的分析
DSMC方法的重要实质是将分子的运动与分子间的碰撞解耦。而碰撞网格的作用就是划分模拟分子。根据文献[1], 理想的DSMC方法中的网格需要满足如下条件:
1) 很好的计算效率;
2) 能适合复杂的流场和固壁条件;
3) 网格可以自适应流场局部的梯度及分子自由程;
4) 当流场发生变化时, 网格能自适应地调整;
5) 可以有效地降低碰撞分子对的平均距离;
6) 可以高效地确定分子所属的网格。
传统的DSMC算法中使用固定的碰撞网格, 显然难以满足以上要求。而对固定网格算法的改进也集中在对已有网格进行局部修改, 当流场变化剧烈时无法适用。
3.2 DSMC的动态网格算法
通过对DSMC算法的分析可以发现, 碰撞网格和采样网格可以分开, 且每一轮的计算中只涉及到碰撞网格。碰撞网格的作用是为了有效地计算分子碰撞数以及选取分子碰撞对, 因此碰撞网格从概念上可以作为碰撞过程中的一部分。在DSMC算法的每一轮的分子碰撞过程中, 先根据分子的分布情况动态构建网格, 标记分子所属网格, 再遍历所有的动态网格计算分子碰撞, 即得到动态网格算法。整个算法流程图如图2所示。
动态划分算法采用kd-tree算法。具体的划分算法如下:
算法1 划分网格算法
输入: 网格根节root, 分子数组moles。
输出: kd-tree, 叶子节点为碰撞网格及其所属分子。
步骤:
1) 如果moles的分布和数量以及root的属性满足构成一个碰撞网格的条件, 则将root的左右子节点设为空, 设置root中指向moles的数据, 返回root。
2) 根据空间划分策略, 计算空间划分的轴和划分位置。
3) 根据第2步的结果, 将moles分成两部分:moles-left和moles-right。
4) 构造两个新的kd-tree节点node-left和node-right, 并设置相应属性。
5) 在node-left、node-left和node-right、 node-right上递归调用划分网格算法, 并设置node的左右子节点为node-left和node-right, 返回root。
该算法中仍有两点需要确定, (1) 如何决定输入的节点和模拟分子是否可以构成一个碰撞网格, 即终止条件。 (2) 如何有效地进行空间划分。本文采用的终止条件为分子数小于30个分子;空间划分策略为按网格最大维度的几何中心为划分平面。
根据分子动力学, 单个网格在Δtm时间进行分子碰撞数为:
其中Nm是网格中的分子数,
其中
3.3 算法的复杂度分析
根据上述的动态网格划分算法, 设该算法的复杂度为T (N) , N为总的分子数, 则复杂度的递推式为:
T (N) =P1 (N) +P2 (N) +T (N1) +T (N2) N1+N2=N
其中P1 (N) 为计算划分维度和划分位置的开销, P2 (N) 为划分模拟分子的开销, T (N1) 和T (N2) 则为分别递归划分两部分分子的开销。根据算法, 采用网格最大维度上的几何中心作为划分位置, 则P1 (N) =O (1) , 线性划分分子的开销为P2 (N) =O (N) , 则有:
T (N) =O (N) +T (N1) +T (N-N1)
上式的解为T (N) =O (Nlog2N) (平均情况下) , 这个复杂度是可以接受的。同时注意到, 在简单直角网格的情况下, 标定分子的时间复杂度为O (N) , 因此动态划分网格的复杂度显然大于固定网格算法。但通过良好的程序实现, 可以使得动态划分网格的DSMC算法的速度在可接受的范围之内。
4 DSMC的多核并行
DSMC算法是一个非常适用于共享内存并行的算法。在分子移动和分子碰撞的计算中, 不同的分子和不同的网格之间不存在相关性, 因此可以简单地分别对分子和网格的规模进行分解, 然后分别计算, 达到很好的并行效果。具体算法这里略去。
在动态网格划分的算法中, 由于划分模拟分子需要对内存进行写入, 因此针对每一趟划分进行并行比较困难, 但显然一旦划分完毕, 则划分得到的两部分分子可以分别进行再划分, 互相之间不存在相关性。以一百万分子、四核并行为例, 设t为单步划分所需时间, 易得串行程序的运行时间为20t, 而并行程序理论上的运行时间为6t, 加速比3.33, 并行效率为83%, 并行效率是比较高的。
5 实验结果及讨论
实验的算例为超音速横掠平板流动问题[1], 具体设置如下:
超音速氮气流过一热平板, 计算区域尺寸L=1m, H=0.6m, 底部的平板长度L=0.9m, 来流气体速度为4.0Ma, 温度300K, 平板的温度为500K。划分采样网格数为100×60, 模拟比例为0.175×1016, 流场稳定时模拟分子数约为3.7×104, 每一轮计算时间约为4.0×10-6秒, 迭代计算10000次。
5.1 DSMC动态网格算法的正确性验证
将DSMC动态网格算法与原有DSMC固定网格算法所得到的结果进行对比如图3-图8所示。可以看出, 动态网格的实验结果与固定网格的实验结果吻合得很好。
5.2 DSMC动态网格算法的单机性能
将动态网格的DSMC算法 (C++) 与Bird的DSMC程序 (FORTRAN) 进行对比。在Intel Core平台上进行实验结果如表1所示。
从表1可以看出, 静态网格比动态网格要快75%左右, 这一差异是可以接受的。通过对动态网格程序实现进行优化 (更好的数学库, 更好的随机数生成器以及优化内存存取) , 这一差异还可以进一步缩小。
5.3 DSMC动态网格算法的并行性能
在Windows平台上使用Windows Thread API进行DSMC动态网格算法的并行化, 在Intel Quad Core平台上进行实验, 得到的运行时间以及DSMC算法的各步骤运行时间如表2所示。
从表2可以看出, 网格构建和分子碰撞这两个过程的加速性能明显好于分子移动。这是因为分子移动的计算量较小, 此时瓶颈在于内存带宽, 并行加速有限。另外, 通过对该程序进行性能剖析表明, 有大量CPU运算在随机数上, 而要实现线程安全的随机数生成器, 需要频繁地进行同步, 影响了性能。这就是理论上加速比较低的网格构建反而有较高的加速比的原因 (网格构建不需要随机数) 。通过换用更好的线程安全的随机数生成器可使DSMC算法的并行性能可以得到进一步的提高。
6 结论及未来工作
本文分析了传统的固定网格算法的DSMC方法的特点和不足, 提出了一种新的动态构建网格的DSMC算法, 改进了固定网格算法无法应付复杂流场的缺点。本文通过与固定网格算法的对比实验, 进一步验证了该算法的有效性和正确性, 通过实验肯定了动态网格的速度性能。最后, 为了进一步提高该算法的性能, 本文对该算法在共享内存模型下进行了并行化, 得到了比较满意的结果。
尽管多核CPU可以有效地提高DSMC算法的计算效率, 但是实际的DSMC算例的计算量还是大大超过了单机可以承受的范围。通过多机并行来提高DSMC算法的效率已是必然要求。 但多机并行DSMC算法面临着通信量大、通信频率高和负载同步等一系列问题。本文提出的动态网格的DSMC算法, 在多机并行的环境下可以省去同步网格的开销, 有效地降低了多机并行中的通信量, 并且降低了负载平衡的难度。相信动态网格的DSMC算法可以为多机并行DSMC效率的提高提供新的思路。
摘要：DSMC (Direct Simulate Monte Carlo) 方法是处理稀薄气体问题的一种有效的方法, 但现有的DSMC存在着网格生成及处理复杂、算例需进行大量人工调整、计算量大、耗时长等缺点。分析DSMC方法中对网格的要求以及网格在整个DSMC方法中所起的作用, 提出了动态划分碰撞网格的DSMC算法, 有效地解决了复杂流场条件下网格自适应的问题, 并通过实验验证了该算法的正确性。同时, 针对DSMC算法计算量大的特点, 利用共享内存的并行模型对动态网格的DSMC算法进行了并行化, 得到了较好的结果。
关键词：DSMC,动态网格,并行化
参考文献
[1]BIRD G A.Molecular Gas Dynamics[M].Oxford:Clarendon Press, 1976.
[2]BIRD G A.Molecular Gas Dynamics and the direct simulation of gasflow[M].Oxford:Clarendon Press, 1994.
[3]BIRD G A.Application of the DSMC method to the full shuttle geome-try[R].AIAA-90-1692.
[4]LAUX M.Optimization and parallelization of the DSMC method on un-structured grids[R].AIAA-97-2512.
[5]KIMMG, KIMHS.A parallel cell based DSMC method with dynamicload balancing using unstructured Adaptive meshes[R].AIAA2003-1033.
[6]姜恺, 黄良大.直接模拟蒙特卡洛 (DSMC) 方法的并行化[J].高性能计算发展与应用, 2005 (2) .
[7]Olson S E, Christlieb AJ.Gridless DSMC[J].Journal of Computation-al Physics, 2008, 227 (17) .
基于聚类算法的并行化研究 篇5
由于数据挖掘是从海量数据中提取有用信息,处理效率问题成了对海量数据处理的瓶颈之一,传统的单机串行算法效率较低;由于部分聚类算法中蕴涵并行性,所以为了解决处理效率问题,将并行化的程序设计思想(并行处理)引入聚类算法,同时降低算法的复杂度,使用机群系统进行并行计算,从而有效的缩短聚类的时间。
1 K-means算法
1.1传统K-means聚类算法
K-means算法以k为输入参数,把包含n个对象的集合分为k个簇,使得结果簇内的相似度高,而簇间的相似度低。簇的相似度是关于簇中对象的均值度量,可以看做簇的质心或重心[2]。
传统K-means算法的处理流程如下:
输入:k:簇的数目
D:包含n个对象的数据集
输出:k个簇的集合
方法:
1)从D中任意选择k个对象作为初始簇重心
2)Do
3)根据簇中对象的均值,将每个对象(再)指派到最相似的簇
4)更新簇均值,即计算每个簇中对象的均值
5)while数据集中所有对象的平方误差和E不再发生变化
通常,采用平方误差准则,其定义如下:
其中,E是数据集中所有对象的平方误差和,p是空间中的点,即给定对象,mi是簇Ci的均值(p和mi都是多维的)。换言之,对于每个簇中的每个对象,求对象到簇中心距离的平方再求和。这个准则试图使得生成的k个结果簇尽可能的紧凑和独立。
1.2并行化K-means改进算法
随着并行处理技术的快速发展,越来越多的研究人员尝试将并行处理方法应用于提高聚类算法的效率,通过研究发现K-means算法具有很大的并行性。首先,可将待挖掘的数据集N划分为t个数据子集,t为并行处理环境中处理机的数目;然后将划分后t个数据子集分别发送到t台处理机进行数据聚类处理;最后主机将收到的节点机的聚类结果计算平方误差准则函数E的值,并将前后两次结果做差,如果差的绝对值小于阈值10-6,则处理结束,否则继续循环处理。并行K-means算法的流程如图1所示。
1.3实验结果与分析
我们搭建工作站机群系统,通过以太网卡等连接5台PC机(Intel P4.17GHz、256MB RAM,安装LINUX redhat OS),采用Master/Slave模式的数据并行策略,建立基于消息传递的工作站机群系统,用MPI进行算法编程验证实验。
本实验的主要目的是验证并行化后的K-means算法的执行时间和效率,所以为了简单起见,本实验中的数据是通过计算机随机产生的整型数据。同时,我们将并行与串行算法的实验结果相比较,当进行算法比较时,把程序运行10次并取平均值进行作图比较(如图2)。
从图2中我们可以看出并行K-means在数据集较大时表现出比串行K-means更好的执行效率,而当数据集较小时,主要由于并行计算中PC间通信时耗较大,所以单机串行算法表现出相对更高的执行效率。实验可以证明K-means算法在并行机群上具有了良好的并行性和可扩展性。
2 PAM算法
2.1 PAM聚类算法
PAM是k中心点(k-medoid)算法之一,它试图确定n个对象的k个划分。在随机选择k个初始代表对象之后,该算法反复试图选择簇的更好的代表对象。分析所有可能的对象对,每对中的一个对象看作是代表对象,另一个看做非代表对象。对于每个这样的组合,计算结果聚类的质量。对象oj被那个可以使误差值减少最多的对象所取代。再一次迭代中产生的每个簇中最好的对象集合成为下次迭代的代表对象。最终集合中的代表对象便是簇的代表中心。PAM算法的处理流程如下[2]:
输入:k:结果簇的个数
D:包含n个对象的数据集合
输出:k个簇的集合
方法:
1)从D中任意选取k个对象作为初始的对象或种子
2)repeat
3)将每个剩余对象指派到最近的代表对象所代表的簇
4)随机地选取一个非代表对象Orandom
5)计算用Orandom交换代表对象Oj的总代价S
6)if S<0 then用Orandom替换Oj,形成新的k个代表对象的集合
7)until不在发生变化
2.2并行化PAM改进算法
为了使问题简单化,首先我们选择任意的当前k个对象作为节点{Ol,…,Ok}。对于PAM算法,当每一步结束时,一种情况是找到一个代价最小的相邻节点,另一种情况是算法结束(当前节点代价最小)[3]。如果我们需要从当前节点移动到一个新的节点,我们必须交换一个已选对象和一个未选对象。为了保证已选对象在前k位,我们交换他们的下标。这样{Ol,…,Ok}会一直作为当前节点,而且不会受到当前节点移动的影响。
PAM的主要任务是检查当前节点的所有相邻节点,而且必须在划分的同时检查[3]。假设在p个进程(记为p1,p2,…,pp)上运行PAM算法。算法描述为:
1)将所有相邻节点写在列表中并按下标(升序)排序;
2)前[k(n-k)/p]个相邻节点指派给p1,接着的[k(n-k)/p]个相邻节点指派给p2,…,最后的[k(n-k)/p]个相邻节点指派给process p;
3)p个进程并行,并且报告各自相邻节点n1,…,np;
4)如果没有相邻节点被报告,算法结束(当前节点的代价最小);
5)从n1,…,np中选择代价最小的节点,将此节点改为当前节点,重复第一步。
下面举一个例子简单说明该算法,给定一个对象集{1,2,3,4,5,6,7},假设k=4,“1234”相邻节点为(用上述方法得到):1235,1236,1237(i=4);1245,1246,1247(i=3);1345,1346,1347(i=2);2345,2346,2347(i=1)。
每个进程被指派任务后,各自查找代价最小的节点,最后所有的进程(除了p1)将得到的节点报告给p1,由p1作比较工作。
2.3实验结果与分析
利用2.3中搭建的工作站机群系统,此时用3台PC机,进行PAM算法的执行效率验证,并对比串行和并行PAM的执行时间(如图3),由于PAM算法不适用于大量数据集的处理,所以实验n取1000以内的数值。
从图3中我们可以看出并行PAM的执行时间比串行PAM的执行时间长,并没有提高算法的执行效率,由此我们可知K-means算法有比PAM更好的并行性和可扩展性。
3具有并行性的其他聚类算法
聚类算法中除了上述K-means、PAM算法具有潜在的并行性和可扩展性外,还有一些算法可以进行并行化处理例如:并行硬聚类算法中的K-mediods,面向大规模数据库系统的BIRCH算法,处理非数值属性聚类的CACTUS算法,子空间聚类算法ENCLUS等[4],以及模糊聚类算法中的FCM等算法,理论上也具有在并行机群上的加速性。
4进一步研究方向与展望
近年来诞生了聚类算法中的一个崭新分支和研究热点—谱聚类算法,谱聚类算法建立在谱图理论之上,其实质是将聚类问题转化为图的最优划分问题,相对于传统的聚类算法有许多优势,并在实践中取得了很好的效果。由于谱聚类算法一般可以归纳总结为三个步骤[5]:
步骤一:构造数据集表示矩阵Z;
步骤二:计算Z的前k个特征值和特征向量,构造特征值的向量空间;
步骤三:利用K-means或其它传统聚类算法对特征向量进行聚类。
由于谱聚类算法研究中可以运用K-means算法等具有并行性的聚类算法进行特征向量的聚类,所以本文对K-means算法并行化的研究也可以运用于谱聚类的并行化,提高谱聚类算法的执行效率,是很有前景的研究问题。
参考文献
[1]Tan P N,Steinbach M,Kumar V.Introduction to Data Mining[M].Beijing:POSTS&TELECOM PRESS,2006.
[2]Jia W H,Micheline Kamber.Data Mining Concepts and Techniques[M].Beijing:China Machine Press,2006.
[3]Yan Z P,Shao X L,Zhang F.Parallel Clustering Methods for Data Mining[J].Acta Scientiarum Naturalium Universitatis Nankaiensis,2008(4):106-111.
并行化分析 篇6
GPU已经不再局限于3D图形处理了, 由最早以游戏为主要代表的图形应用, 到现在大规模并行超级计算机和处理大批量并行浮点运算, 尤其在动画渲染、气象研究、能源勘探、生物医疗、金融分析、地理信息系统等各个领域发挥着重要作用。“天河一号A”超级计算机是GPU应用的典型代表, 它采用了GPU和CPU混合架构, 并使用了超过14000颗CPU, 其中配备了2048颗我国自主研发的飞腾FT-1000八核心处理器, Tesla M2050 GPU7168颗, 总运算能力2.5PFLOPS, 曾在2010年11月获得全球速度最快超级计算机的头衔。它的成功已经充分证明了GPU在数据计算方面的重要性。
为了提高DCT变换的速度以及扩展更多的应用, 文中主要分析面向Open CL模型的DCT变换的并行化。通过结合Open CL语言和GPU的并行特性, 充分发掘其中可以并行计算的部分, 针对基于GPU的DCT变换的性能进行优化。
1 Open CL
随着GPU可编程性不断增强, 各种编程工具的不断推出, 例如Nvidia的CUDA、AMD的Brook+、Apple的Open CL、IBM的CBE、Intel的Larrabee, 这些工具使GPU通用计算编程的复杂性大幅度降低, 已逐步成为一种新型可编程高性能并行计算资源。对于编程人员来说他可以选择不同的语言或者API进行编程, 文中选用Open CL编程。
1.1 Open CL的组成
Open CL最早是由Apple公司提出, 在Intel、AMD、NVIDIA等巨头的参与下, 2008年12月已形成第一版标准。Open CL全称Open Computing Language[3,4], 即“开放计算语言”, 为编写跨平台的GPU计算的程序提供了方便。
Open CL的组成包含三个部分, 如下:
1) Open CL编程语言。又被称为Open CL C编程语言。它是基于ISO C99标准的一个扩展子集, 主要用来编写Kernel程序的语言, 能运行在任何类型的微处理器上。
2) Open CL平台API。它定义了协同执行的单个处理器程序找到Open CL设备所用的函数和函数的功能, 以及Open CL应用创建上下文的函数。
3) Open CL运行时API。它用于管理上下文进行命令队列的创建和运行时发生的其他操作。
图形里面也有很多API, 比如Open GL、Direct X是针对图形的, Open CL是针对并行计算的API。这些构成便于主机程序启动Kernel程序, 并为并行计算提供了一个有效的开发平台。Open CL作为业界公认的第一个异构计算开发语言标准, 正逐渐被各主要计算平台所采用。文中采用的异构处理平台为多核CPU和GPU。
1.2 Open CL平台模型
Open CL平台模型为开发人员提供了在计算设备上执行的Open CL C函数。主机 (Host) 是Open CL平台模型中的核心设备, 它能够连接一个或多个Open CL计算设备 (Compute Device) 。其中每个Open CL计算设备又由一个或多个计算单元 (Compute Unit) 组成, 每个计算单元由一个或多个处理单元 (Processing Element) 组成, 各种计算操作都是在处理单元中完成的。例如AMD Radeon HD7970包含有32组CU, 每组CU包含64个PE。Host端是Open CL程序的入口和出口, 控制着计算设备中处理单元需要进行的计算, 从而实现管理平台模型中所有计算资源。计算命令通过应用程序从Host端向各个Open CL计算设备的处理单元进行传送。GPU通过单指令多数据 (SIMD) 指令类型来支持数据并行计算。在单指令多数据流的结构中, 单一控制部件向每条流水线分派指令, 同样的指令被所有处理部件同时执行。
Open CL采用存储器类型的层次结构, 如图1所示[5], 开发人员可以利用这些存储器来编程。这些存储器类型包括:全局、常数、局部和私有存储器。全局存储器可以由主机程序动态地分配, 并支持主机和设备的读写访问操作。常数存储器支持主机的读写访问操作, 并且支持设备的只读访问操作。局部存储器可以由主机动态地分配, 也可以由设备代码静态地分配。主机不能访问Open CL中的局部存储器。私有存储器在计算单元内部, 与处理单元能交换数据。
2 DCT在GPU上的并行化实现
为了方便开发人员在GPU平台上进行编程, 提高开发效率, 目前, 各大厂商提供了很多高效、直观的开发平台, 即CAL、Brook+、CUDA、Open CL等, 这些平台有各自的特点。文中主要从Open CL角度进行分析DCT变换的并行化。
2.1 DCT变换的工作原理
1974年, Ahmed, Natarajan和Rao首先提出了DCT (Discrete Cosine Transform) 算法, DCT全称为离散余弦变换[6,7,8]。DCT变换与K-L变换的准最优正交变换非常相似, 能将图像的大部分能量集中到直流系数中, 并且其算法快速有效, 因而有利于软件和硬件实现。K-L变换 (Karhunen-Loeve Transform) , 由卡尔胡宁 (Karhumen) 与勒夫 (Loeve) 分别提出[9]。其具有将图像能量集中于某些系数中的能力, 一个能把最多的能量集中于最少的系数上的变换所产生的重建误差最小, 但是采用实际电路完成十分困难。因此, 目前在MPEG-4和JPEG2000的静态纹理编码中主要采用DWT变换实现, 而其他多数图像和视频编码中选择采用DCT变换进行实现。
针对二维图像的DCT变换, 其变换过程如下:
1) 对图像块的每行进行一维DCT变换。
2) 对经行变换的块的每列再进行一维DCT变换。
其中, 一维DCT变换采用线性变换Y=HX实现, 它将N维向量X通过变换矩阵H转换成新的N维向量Y。公式如式 (1) 所示[10]:
DCT变换的变换核H第k行第n列的元素定义如公式 (2) 所示:
其中k=0, 1, 2..., N-1, n=0, 1, 2..., N-1
从式 (2) 可以证明得到, DCT变换核Hkn是为无理数, H是正交矩阵且DCT完全可逆的, 变换对于输入的整数图像数据而言, 进行DCT变换时需要进行大量的浮点运算, 容易导致图在像轻微失真, 另外还需要进行大量的乘法和除法运算, 软件和硬件不易实时实现, 这将不利于在实时的多媒体和视频领域的广泛应用, 尤其是在医学图像、遥感成像等特定领域是不允许的。
2.2 DCT变换的并行化
DCT变换在GPU上的实现步骤, 如下:
1) 将原始数据从Host端的内存传送到Device端的显存, 将原始图像分成8×8的块, 每个线程根据对应的索引号读取显存中某个块中的一列到GPU的内存中。
2) 每个线程根据对应的索引号先对某个块中的一列做一维8点DCT快速正变换, 再对变换以后的块中的某行做一维8点DCT快速正变换, 结果为变换后的块。
3) 每个线程根据对应的索引号把某个块中的一列从GPU的内存传送到显存中。
2.3 DCT变换的并行化实现
Open CL的执行模型可以分为两部分, 如图所示。一部分是在Host上执行的主程序, 另一部分是在Open CL设备上执行的Kernel程序, Open CL通过主程序来定义上下文并管理内核程序在Open CL设备的执行。
1) 主程序
执行在Host端的主程序, 如下:
2) Kernerl程序
执行在OpenCL设备上的Kernerl程序, 如下:
3 实验结果及分析
1) 测试环境
文中采用的的硬件和操作系统等配置如下:
(1) Windows 7 X64位操作系统;
(2) Intel (R) Core (TM) i7-3770 4核;内存8GB;500G硬盘;
(3) 显卡:AMD Radeon HD 5650、AMD Radeon HD 6950和AMD Radeon HD 7970。
2) 构建环境
构建OpenCL环境的具体步骤如下:
第1步:下载。
下载最新的AMD driver, AMD APP SDK。本实验中采用:
(1) AMD SDK:AMD-APP-SDK-v2.8-Windows-64.exe
(2) AMD Driver:12-10_win7_win8_64_dd_ccc_whql.exe
第2步:安装。
依次安装AMD Driver和AMD APP SDK。AMD APP SDK目前支持的IDE有:Visual Studio。在安装过程中会自动添加一部分环境变量。
第3步:查看。
在程序→运行→cmd中键入clinfo, 查看输出信息, 如果所有计算设备都能找到, 则安装成功。
第4步:编译。
编译SDK Sample中的样例。在$ (AMDAPPSDKSAMPLESROOT) samplesopencl目录下的Open CLSamples.sln解决方案, 包含了多个Open CL工程。用户可根据需要选择相应工程, 并设置为启动项目, 然后进行build和debug。可执行文件保存在$ (AMDAPPS-DKSAMPLESROOT) samplesopenclbin相应目录下。
第5步:当开发人员创建自己的Open CL项目时, 可以通过两种方法进行编译。
(1) 在解决方案资源管理器中按照向导建立工程, 并按照步骤4进行编译和调试。
(2) 用户可以在SDK中的模板工程 (Template) 对源码进行修改并编译执行。
3) 实验结果
实验结果如表1所示, 单位:ms。
通过测试, 实验结果表明, DCT并行化变换速度比原来常用的DCT变换速度有明显提高, 并且显卡性能越好, 采用并行化后, 速度提高越多, 节省了大量的时间。
4 结论
GPU作为一种非常有潜力的计算工具, 仍在不断发展。文中通过对面向Open CL模型的DCT变换的并行化方法的分析和实现, 探讨了Open CL的关键技术, 并且提出了一种把传统串行DCT快速变换映射到GPU的并行化方法, 在实验过程中, 对比采用C语言和Open CL语言编写的DCT变换, 基于Open CL开发的应用程序可以最佳地调用异构系统中的所有计算资源, 最大化发挥计算能力, 真正体现异构计算的高效节能优势。
参考文献
[1]Youngsub Ko, Youngmin Yi, Soonhoi Ha.An efficient parallelization technique for x264 encoder on heterogeneous platforms consist ing of CPUs and GPUs.Journal of Real-Time Image Processing, 2013 (01) .
[2]Changmin Lee, Won Woo Ro, Jean-Luc Gaudiot.Boosting CUDA Applications with CPU–GPU Hybrid Computing[J].International Journal of Parallel Programming.2013 (05) .
[3]Cheong Ghil Kim, Yong Soo Choi.A high performance parallel DCT with OpenCL on heterogeneous computing environment[J].Multi media Tools and Applications.2013.05 (64) :475-489.
[4]陈钢, 吴百锋.面向OpenCL模型的GPU性能优化[J].计算机辅助设计与图形学学报, 2011 (04) :571-580.
[5]李焱, 张云泉, 王可, 等.异构平台上基于OpenCL的FFT实现与优化[J].计算机科学, 2011 (08) :284-296.
[6]阮军, 韩定定.基于CUDA的DCT快速变换实现方法[J].微电子学与计算机, 2009 (08) :201-210.
[7]Wei-Jhe Hsu, Hsueh-Ming Hang, Yi-Fu Chen.Motion Estimation and DCT Coding Combined Scheme for H.264/AVC Codec[C].In ternational Computer Symposium.2013 (21) :413-421.
[8]Dariusz Rafal Augustyn, Sebastian Zederowski.Applying CUDA Technology in DCT-Based Method of Query Selectivity Estimation[J].Advances in Intelligent Systems and Computing.2013 (185) :3-12.
并行化分析 篇7
视频压缩编码是图像处理领域的热门方向。为得到较高的压缩率使得图像数据易于存取和传输, 需要大量复杂的运算, 使得在CPU处理器上难以进行大尺寸图像的实时编码。
为此, 出现了许多实现高速运算的解决方案。当前的主流方案平台是基于ASIC、DSP, 并且已有基于这些平台的编码器相关实例。如TI公司的DM642 DSP[1], 可实现40fps的CIF格式视频图像编码;富瀚微公司的多通道视音频编码芯片FH8735, 具有1路1080p, 2路720p或者8路标清的实时编码能力。但DSP运算能力有限, 无法实现高清画质视频的实时编码;ASIC虽然运算能力较强, 但开发周期长、前期投入大、风险高、灵活性差, 无法适应市场多样性的需求。
GPU是目前发展迅速的高速处理器, 主流GPU的单精度浮点处理能力已达到933GFlops, 为同期CPU的10倍左右;其外部存储器带宽141MB/s, 为同期CPU的5倍左右。2007年NVIDIA公司推出了CUDA平台, 利用CUDA平台, DCT变换可实现8倍速度的性能提升[2];Canny边缘检测可实现22倍速度的性能提升[3];而H.264编码中的ME模块运算速度可提高12倍[4]。CUDA平台开发成为大数据量计算、存储的最优方案, 在性能和开发时间上都具有巨大的优势, 资源的利用率大大提高。
本文基于CUDA平台实现了一种高度并行化MPEG-2高清视频编码器, 无论从系统架构上, 还是模块算法与内存管理上, 都进行了最优于并行化的处理, 并在CUDA平台上予以实现, 从大数据量的运算和传输两个方面上达到了实时要求。
1 并行化编码系统
本文方案选用MPEG-2视频标准作为并行化编码的对象, 其主要原因在于:第一, MPEG-2相对MPEG-4, H.264以及AVS来说, 具有相对较低的复杂度[5], 而对于现在发展迅速的网络带宽以及海量存储, 完全可以适应码率较高的MPEG-2[6]码流。第二, 在MPEG-2中, 宏块间独立性很强, 便于并行化, 非常适合CUDA平台的架构。第三, 由于MPEG-2标准已被ATSC, DVB和ISDB等多个HDTV标准采纳, 作为HDTV节目的信源压缩算法, 在工业界已被广泛的使用。因此, 对其研究具有实际的意义和价值。本文方案综合MPEG-2编码系统以及CUDA平台并行资源的特点, 从系统架构设计层面以及模块算法层面均做了并行化设计, 以满足大数据量实时运算的要求。
1.1 分级并行编码
CUDA平台具有不同级别的并行运算单元。其最小并行运算单元为Thread;若干个Thread组成一个Block, 而Block与Block间同样为并行执行的运算单元;若干个Block组成一个Grid, 每个Grid顺序执行各自的kernel编码模块主函数。对于可并行化的每个编码主模块, 将一帧图像映射到CUDA的一个Grid中。从而在GPU内部实现了两个级别的并行, 即Block级和Thread级。在MPEG-2编码器的系统架构中, 由于不存在帧内预测, 除了VLC模块, 其余编码模块宏块间无相关性, 可做并行化设计。且在各编码模块内部, 算法同样具有可并行化之处。因此, 将待编码图像的不同运算单元映射到CUDA平台的相应并行运算单元中去, 便可实现最优的并行化设计。
本文方案分别针对编码器系统采用了3个级别的并行化处理, 最大限度地利用可并行资源。
1.1.1 处理器级并行
根据CPU与GPU两处理器间的异构并行特性, 本文方案采用两者并行处理系统架构。CPU负责逻辑性强的事务处理和以及读写数据的串行计算, 而GPU负责高度并行化的数据处理。两处理器之间的通信主要通过以下两方面工作完成:一是CPU调用在GPU端执行的kernel函数, 实现指令的调度和执行;二是CPU与GPU间相互的内存复制, 实现数据的交换。
图1为并行化编码系统架构设计图, 虚线左侧为CPU执行部分, 负责系统模块的调度, 以及视频图像序列帧数据的读取、输出码流的写回等工作。虚线右侧为GPU执行部分, 依次执行几个编码主模块的并行运算工作。而数据交换的过程和CPU函数以及GPU的kernel函数的执行是相互异步的, 即用GPU的kernel函数的执行时间来掩盖另外两个过程的执行时间。
将视频图像序列的数据读入CPU内存的时间和VLC输出码流写回的过程是必须在CPU端完成的事务, 若按照原编码流程, 将有很大一部分时间GPU处于闲置状态, 等待CPU端完成上述工作。因而, 本文方案根据CPU与GPU各自的优点, 采用协同工作的方法, 利用两者的异步特性来掩盖部分CPU执行时间, 提高整体编码速度。
由于ME、MC以及VLC模块是在GPU上运行的相对耗时部分, 因而本文方案使用当前帧的VLC执行时间来掩盖下一帧的图像数据读入时间;且使用下一帧的ME执行时间来掩盖当前帧输出码流的写回时间。采用这样的系统设计架构, 使得CPU与GPU能够获得最大限度的占用率, 减少各自的闲置时间, 实现了处理器级的并行化。
1.1.2 Block级并行
MPEG-2编码器的主模块在编码过程中, 同一帧的宏块间大多无相关性, 从而为并行运算的实现提供了可能。因此, 本文方案去掉了需要双向预测的B帧以及场图, 以高并行度的高速运算来弥补压缩率的少量损失。对于ME、MC、DCT/IDCT、Q/IQ模块, 将一帧图像中每一个宏块分别映射到CUDA平台一个Block中, 从而使得图像中所有宏块的编码运算并行执行。而对于VLC模块, 由于其包含了差分编码, 当前宏块与前一宏块有一定的相关性, 相邻宏块间独立性不佳。针对VLC模块, 本文方案将图像每一行宏块数据映射到一个Block中, 使得行与行之间并行地进行运算。从而实现了Block级的并行化。
1.1.3 Thread级并行
CUDA的一个Block可有多个并行执行的Thread, 根据不同编码模块的算法特点, 合理地设置Block维度以及分配使用Thread资源, 是提高GPU资源占用率以及计算速度的关键。在CUDA中, SM的指令是以warp为单位发射的, 即一个warp中的Thread是同步执行的。因此, 设计过程中, 应尽量使得Block中Thread数为warp内最大Thread数的整数倍, 以获得更好的资源占用率。针对此特性, 本文方案采用如下的Thread级并行算法。
如表1所示, 针对不同的模块, 为其分配合适的Block维度。对于ME模块, 将一个搜索窗中各个参考宏块映射到当前Block的各个Thread中去, 在各Thread中分别进行其与当前宏块的匹配计算, 从而使得每个参考宏块与当前宏块匹配的计算并行执行。而对于MC模块, 为进一步提高并行度, 将一个宏块的Y分量划为32个4×2块, 然后映射到一个Block的32个Thread中去。
DCT/IDCT的运算, 相当于原始图像矩阵与变换核矩阵的相乘运算;而对于Q/IQ的运算可转化为高度并行化的矩阵运算。对于码率控制部分, 本文方案沿用复杂度较低, 易于并行化的TM5参考算法。因此, 本文方案将每一个像素点的计算都映射到一个Thread中去 (一个宏块划为4个8×8块, 即4×8×8个像素点) 。每个Thread分别读取A与B两矩阵的一行与一列, 计算出结果矩阵C的一个点, 从而实现高度并行化的矩阵相乘运算。
熵编码VLC模块完成在GPU上的查表工作, 对于每一行图像, 采用80个Thread使系统能为该行内全部宏块并行地查询储存在常数存储器中的表, 以达到行内的并行, 并利用GPU中cache资源提高读取速度。
采用上述一系列的设计方案, 从处理器级、Block级以及Thread级三方面依次对编码器进行并行化处理, 使得系统资源利用率和编码速度大大提高。
1.2 ME并行快速搜索算法
MPEG-2编码标准中采用了ME全搜索算法, 在预先定义的搜索区域内, 把当前宏块与所有参考宏块进行匹配运算, 寻找最佳匹配参考宏块。由于CUDA平台Block内可并行Thread最多仅能有32个, 全搜索法的覆盖范围远超过32个点, 这使得每个参考宏块的匹配过程需要多次并行才能完成, 该算法在得到最大搜索精度的同时也带来了较长的运算时间。而目前速度最快的Four Step search (FSS) 四步搜索法[7]每个搜索窗内仅有25个 (5×5模板) 或9个 (3×3模板) 参考宏块, 均小于CUDA平台上一个warp内的Thread数32, 这使得部分Thread被闲置, 并行度不高。且FSS搜索算法最大搜索覆盖范围为垂直和水平方向 (-7, +7) , 运算精度剧烈下降。因此, 本文方案提出一种基于CUDA平台的快速ME并行搜索算法, 最大程度利用可并行资源, 搜索模板如图2所示, 包含粗搜索用大模板以及细搜索用小模板。两种模板的参考点均为32个, 保证了CUDA平台warp内32个Thread全部并行地进行运算, 充分利用了资源, 并且提高了搜索精度。
1.2.1 算法步骤
本文方案提出的算法搜索最佳匹配参考宏块过程分为以下几步完成。
Step 1:以当前帧当前宏块左上顶点像素点位置为初始搜索起点。
Step 2:应用大模板在前一帧进行第一次搜索, 此为粗搜索, 在较大的覆盖范围内搜索最接近当前宏块的参考宏块可能位置区域, 得到当前宏块的最佳匹配参考宏块。
Step 3:以Step 2中得到的最佳匹配参考宏块左上顶点像素点为第二次搜索的初始搜索起点, 并应用小模板进行搜索。经过以上步骤, 最终得到最匹配参考宏块, 搜索结束。
本文方案提出的搜索算法可覆盖区域较大, 搜索范围达到了垂直方向 (-17, +17) , 水平方向 (-17, +18) , 相比FSS搜索法其搜索精度大大提高;且整个过程仅需要两步搜索, 每一步的匹配运算都是完全并行的, 从而本文方案搜索算法相比全搜索法, FSS搜索法, 速度有了大幅度提高。
1.2.2 实验结果
通过在CUDA平台上对几种ME搜索算法的实现, 对于不同运动程度的测试序列, 所得到的ME搜索所需时间以及相应PSNR如表2所示。
实验结果表明, 从搜索速度上来说, 本文方案所提出的快速ME并行搜索算法相比全搜索算法快至少6倍以上, 而相比FSS搜索算法快至少3.4倍以上。从编码质量上来说, 采用全搜索算法的编码图像质量最好, 搜索精度最高;采用本文方案算法的编码图像质量稍有下降, 但仍优于FSS搜索算法。即本文方案提出的并行化搜索算法充分利用了CUDA平台的并行资源, 搜索速度快, 搜索范围广, 得到了较高性能。
2 内存管理
为满足高清视频图像数据的实时传输存取, 无论在CPU与GPU间的数据传输上, 或是GPU内部的内存分配管理上, 都需要足够的带宽。对于720p视频图像 (灰度) , 其每帧所产生的数据量为1280×720×8/8=900kB, 每秒所产生的数据量为25×900KB=22.5MB。GPU与CPU通过PCI-E接口进行通信, 实验用PCI-E通道提供了上下行各4GB/s的带宽, 满足了两处理器之间大数据量高速传输的条件。而GPU的GDDR内存带宽为141MB/s, 使得数据可以高速地在GPU的内存间进行传输。
表3与描述了再编码过程中CPU与GPU的内存通信管理的过程。本文方案使用了Pinned memory, 在尽可能小地影响CPU运行性能的情况下, 得到了较高的CPU与GPU之间的内存复制速度。且将编码中所用到的固定参数以及熵编码查找表存入GPU端只读的Constant memory, 相比Global memory得到更高的GPU内部内存复制速度。每个SM运算单元通过存取Constant memory和Global memory中自己所需数据, 来完成块级编码, 最终通过Global memory输出码流至CPU端。
3 实验结果
为验证本文所提出的并行编码系统的性能, 选取了7个高清格式 (720p) 标准测试序列进行了测试。序列帧数为200帧, 帧格式为IPPP, GOP (Group of Pictures) 长度为15帧 (1个I帧和14个P帧) , 码率8Mbps。实验环境为: (1) CPU运行平台AMD Sempron 2800+, 主频为1.60GHz, 内存为512M的DDR; (2) GPU采用NVIDIA GeForce GTX285显卡; (3) Microsoft Windows XP sp2; (4) Microsoft Visual Studio 2005; (5) CUDA Toolkit and SDK 2.2。
表4给出了本文方案与单CPU方案的性能对比。可以看到, 单CPU方案编码速度不超过0.13fps, 距离视频序列的实时编码存在巨大差距。而本文方案的编码速率相比单CPU方案有了大幅度提升, 对于运动剧烈程度不同的测试序列, 编码速率达到26fps～35fps, 实现了高清视频序列的实时编码。
与此同时, 本文方案得到了较好的编码图像质量, 如图3所示, 对于实验中7个测试序列, 图像的平均PSNR值均大于33.5dB。相对单CPU方案, 图像质量略有下降, 究其原因, 主要是由于, 第一, 本文方案提出的利于并行运算的ME搜索算法, 相比原MPEG-2编码器的全搜索算法搜索精度下降;第二, 由于是高度并行的编码, 对于量化步长的确定是基于帧级别的, 而在原始CPU端进行的量化是串行基于宏块级的。这都对计算精度产生了一定的影响, 但其主观画质评价并未有明显下降, 失真属于人眼可接受程度。
4 结束语
本文首先分析了MPEG-2编码器的可并行性, 并基于CUDA平台的软硬件体系, 利用GPU的高存储带宽以及并行运算能力, 提出了一种具有高并行度的高速视频编码系统设计方案;其次, 对各编码主模块在CUDA平台上做了并行化优化设计, 并提出了一种具有高并行度、高搜索覆盖率的快速ME搜索算法;最后, 优化的系统模块调度以及资源分配, 使得CPU与GPU之间具有高度的并行性, 并且各编码模块内部的运算也具有不同级别的并行性。此外, 合理的内存管理, 使得大数据量的实时传输以及运算速度满足需求。最终, 测试结果显示, 基于CUDA平台的ME并行算法无论是在运算速度上还是搜索精度上都取得了优异的性能。且在测试环境下的CPU+GPU方案编码速度远高于单CPU方案, 对于720p格式视频编码速度达到25fps以上;同时保持了编码图像质量;在极小的硬件代价和开发时间的情况下, 便实现了高清视频实时编码的目标。
摘要：HD视频的编码技术具有广阔的应用前景, 为解决其大数据量实时处理的瓶颈问题, 提出一种基于CUDA平台的并行编码系统架构。根据CUDA平台软硬件结构特性, 采用三级并行机制;并提出一种高并行化快速ME搜索算法;同时合理分配内存空间, 实现大数据量的实时运算与存取。实验结果表明, 方案具有高并行度, 高编码速率的特点, 对HD视频可达到实时编码要求。
关键词：CUDA,并行计算,视频编码,ME
参考文献
[1] Lin Daw-Tung, Yang Chung-Yu. H.264/AVC Video Encoder Rea-lization and Acceleration on TI DM642 DSP[J]. PSIVT 2009, LNCS 5414, 2009:910-920.
[2] Yang Zhiyi, Zhu Yating, Pu Yong. Parallel Image Processing Based on CUDA[C]. Proceedings-International Conference on Computer Science and Software Engineering (CSSE 2008) , 2008, 3:198-201.
[3]Seung In Park, Sean P Ponce, Jing Huang, et al.Francis Quek.Low-cost, high-speed computer vision using NVIDIA’s CUDA ar-chitecture[J].Proceedings-Applied Imagery Pattern RecognitionWorkshop, 2008.
[4]Chen Wei-Nien, Hang Hsueh-Ming.H.264/AVC motion estimationimplementation on compute unified device architecture (CUDA) [C].International Conference on Multimedia and Expo 2008 (IC-ME2008) , 2008:697-700.
[5] Ishfaq Ahmad, Yong He, Ming L Liou. Video compression with parallel processing[J]. Parallel Computing.2002, 28 (7-8) :1039-1078.
[6] Le Gall, Didier. MPEG: a video compression standard for multimedia application[J]. Communications of the ACM, 1991, 34 (4) :46-58.
并行化分析 篇8
关键词：虚拟手术,碰撞检测,CUDA,并行化,AABB,层次包围盒
1 引言
虚拟手术系统在医学手术排练演习、手术教学、手术技能训练等方面有着非常重要的作用, 它靠术前获得的医学影像信息, 建立三维模型, 在计算机建立的虚拟的环境中设计手术过程、进刀的部位、角度, 从而提高手术的成功率。由于在虚拟手术环境中尽可能满足沉浸感和真实感, 因而实行性要求非常高。碰撞检测作为虚拟手术中的重要一环, 承担大量复杂的计算, 是制约实时性的最主要因素。
碰撞检测是游戏、虚拟现实中重点研究的问题, 对于能否产生真实感的场景至关重要。研究学者对此进行了许多有意义的工作, 针对不同的应用场景, 采用不同的方法提出了很多实用的碰撞检测算法。这些算法主要分为以下四类:
(1) 基于层次包围盒的碰撞检测算法。
(2) 基于空间层次分割的碰撞检测算法。
(3) 基于CPU多核多线程的碰撞检测算法。
(4) 基于GPU的碰撞检测算法。
其中, 基于层次包围盒的算法根据包围盒类型的不同, 又可分为包围球、轴对齐包围盒 (AABB) 、方向包围盒 (OBB) 、离散方向凸包围盒 (k-dop) 和凸包的层次树算法。基于空间层次分割的碰撞检测是将整个虚拟空间划分为体积相等的单元格, 只对占据同一单元或领域的单元格的对象进行相交测试。常用的空间分割方法有K-D树、八叉树、BSP树等。基于CPU多核多线程和基于GPU的的算法是在这些碰撞检测算法的基础上进行的一种改进, 然而, 前者效率提升并不十分明显, 后者算法的实现较为复杂, 且有很大的提升空间。
随着虚拟系统的规模越来越大, 模型也越来越复杂, 很多算法将无法满足实时性的要求。本文在分析了已有算法的基础上, 利用GPU可以大量并行计算的优点, 对碰撞检测算法分成两个阶段进行并行处理, 同时采用CUDA平台简化算法的实现, 使之较传统的基于CPU算法, 效率提升了3-5倍, 完全满足虚拟手术中实时性的要求。
2 并行碰撞检测算法的思想
本文采用基于AABB的层次包围盒的并行碰撞检测算法。该方法是利用体积略大而形状简单的包围盒把复杂的几何对象包裹起来。在进行碰撞检测时, 首先进行包围盒之间的相交测试, 当包围盒之间相交时, 再进行几何对象之间精确的碰撞检测。基于AABB的层次包围盒的碰撞检测算法由于具有良好的计算性能, 适用于复杂环境中的碰撞检测, 因而得到了广泛的关注。具体而言, 对于虚拟场景中的两个对象, 首先分别生成层次包围盒树, 然后通过递归遍历层次包围盒树来确定发生碰撞的区域。另外, 在虚拟手术过程中, 由于要实时地对标定的干扰点或区域进行剔除, 因而在下一次进行碰撞检测前应对包围树进行更新, 实时地生成包围盒树。通过实验和分析, 生成包围盒树和遍历包围盒树执行多次重复的代码, 每次处理不同的数据, 因此, 可以采用多线程的方式, 在同一时刻同时执行相同的代码, 同时完成处理不同的数据。由于CPU处理器数量有限, 而GPU处理流非常多且每个处理流可以作为一个计算单元, 因而可以利用GPU流处理单元进行并行计算, 从而可以大幅缩减计算的时间。
2.1 并行生成包围盒树
常用的生成包围盒树有两种方法, 分别是自顶向上和自底向上两种方法。自底向上生成包围盒树的方法与霍夫曼编码类似:
(1) 对于一个含有n个基本几何图元 (一般为三角面片) 的包围盒, 将每个基本几何图元用AABB进行包围, 组成n棵二叉树的集合F={T0, T1, …, Tn}, 其中每棵二叉树Ti中只有一个根结点, 其左右子树均为空。
(2) 遍历F中的每个Ti, 在其余的二叉树中找到与Ti距离最近的Tj, 将Ti与Tj作为左右子树重新合并成一棵新的二叉树, 并更新生成后的二叉树包围盒大小。重复该过程直到F中所有的二叉树被处理完成, 该过程的时间复杂度为O (n2) 。
(3) 每合并一颗二叉树, 将从F中删除原有的二叉树, 并将新生成的树加入到F中。
(4) 重复b和c过程, 直到F中只含有一棵树为止。
上述算法的时间复杂度为O (n2log2n) 。从上述算法的描述过程中可以看出, 遍历与合并都是做着重复的工作, 只是处理的数据不同, 因此, 可以使用并行的方式进行改进:
(1) 根据n个基本几何图元的包围盒构成n棵二叉树的集合F={T0, T1, …, Tn}, 初始时, 每棵二叉树只有一个根结点, 且其左右子树均为空。
(2) 从F中取出Ti, 并行计算其余根结点到Ti的距离, 再用并行的方式找到与Ti距离最小的根结点Tj, 然后将这两个节点合并为一个节点, 并以此节点并行计算到其他节点的距离。
重复该过程直到F中只含有一棵树为止。
上述过程如图1所示。
由并行树生成过程可知, 对于有n个基本几何元素的模型, 该算法在计算根节点之间距离的时间复杂度为O (n) , 在每一次寻找最小的距离根节点采用二分查找算法, 时间复杂度为log2n, 因而整个算法的时间复杂度为O (nlog2n) 。
2.2 并行遍历包围树
原始的遍历算法可以用图2所示伪代码进行描述。
从图2中可以发现, 对于含有n个模型的复杂场景, 假设每个模型平均含有m个多边形, 则此碰撞检测算法的时间复杂度为O (n2m2) , 即使问题退化到只含有几个模型的场景, 其复杂度也为O (m2) 。这对于实时性要求高的虚拟手术场合是无法满足的。很多研究者在此算法的基础上进行了深入的研究, 在权衡精度与速度之间提出了很多改进的算法, 但只满足一定场景的情形。
经过分析, 算法在遍历的过程中, 总是将每一个多边形 (可以用AABB进行近似, 简化计算) 串行与另一个模型的每一个多边形进行计算判断, 这个过程完全可以通过多线程的方式并行计算。因此, 对于将要发生碰撞的两个模型, 我们只对其中一个进行生成AABB包围盒树, 然后用另一个模型中的每个基本图元的包围盒并行的对这个包围盒树进行遍历, 从而获取碰撞信息, 并将其结果存放在一个数组中返回。
并行遍历包围树的过程如图3所示。
算法伪代码如下图4所示。
3 测试结果与性能分析
NVIDIA公司开发了一种称为CUDA通用并行计算架构, 它是一种基于NVIDIA图形处理器的并行计算体系架构, 并使用标准的C语言作为其编程语言, 因此很容易将上述算法在CUDA平台上进行实现。采用实验室配有的PC机及配置的GTX480显卡, 它含有480个SP (Streaming Processor) 基本处理单元, 对并行算法进行测试。为了对比说明效果, 分别采用了开源的碰撞检测库coldet和CUDA进行了对比测试, 测试结果如表1所示。
通过实验结果表明, 在虚拟手术仿真的过程中, 采用CUDA的并行加速算法的帧率达到60帧以上, 完全满足实时性的要求, 而采用coldet的开源碰撞检测库, 在整个过程中有明显的滞留感。
4 总结
本文对碰撞检测进行了分析, 将算法进行了并行化处理, 并采用CUDA对算法进行实现, 最后在虚拟手术系统中进行了测试, 结果表明, 采用CUDA的并行碰撞检测算法明显缩短了系统的耗时, 完全满足虚拟手术系统实时性的要求。该算法具有很好的通用性, 因此也可以用于视频游戏, CAD等场景。
参考文献
[1]马登武, 孙隆和, 佟明安.虚拟场景中的碰撞检测算法[J].火力与指挥控制.2004, 29 (4) :45-48.
[2]芦鸿雁.基于层次包围盒的碰撞检测算法研究[J].计算机与数字工程, 2008, 36 (2) :23-25.
[3]Tang M, Manocha D, Tong R.MCCD:Multicore collision detection between deformable models using front-based decomposition[C].SIAM/ACM Joint Conference on Geometric and physical modeling, 2009:355-360.
[4]A.Greβ, M.Guthe, R.Klein.GPU-based Collision Detection for Deformable Parameterized Surfaces[J].Eurographi cs, 2006, 25 (3) :497-506.
[5]Kim D, Heo J P, et al.HPCCD:Hybrid parallet continuous collision detection using CPUs and GPUs[J].Compter Graphics Forum, 2009, 28 (7) :1791-1800.
【并行化分析】相关文章：
并行分析算法06-07
输油管道并行敷设间距设计分析与探讨09-10
论电力用户侧大数据分析与并行负荷预测09-10
浅议“四个能力建设”与“户籍化管理”并行对消防管理产生的影响01-20
并行检测05-01
双轨并行05-04
并行配置05-17
并行开发05-22
网络并行计算05-11
三维并行电法05-22