下载
加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 雅可比迭代法在图形处理器上实现的研究

雅可比迭代法在图形处理器上实现的研究.doc

雅可比迭代法在图形处理器上实现的研究

叶豫行
2017-09-28 0人阅读 举报 0 0 暂无简介

简介:本文档为《雅可比迭代法在图形处理器上实现的研究doc》,可适用于高等教育领域

雅可比迭代法在图形处理器上实现的研究ComputerEngineeringandApplications计算机工程与应用,()◎研发,设计,测试◎雅可比迭代法在图形处理器上实现的研究张健,涂永明,涂晓明ZHANGJian,TUYongming,TUXiaoming南京工程学院通信工程学院,南京东南大学电子科学与工程学院,南京东南大学混凝土及预应力混凝土结构教育部重点实验室,南京中国人民解放军部队分队SchoolofCommunication,NanjingInstituteofTechnology,Nanjing,ChinaSchoolofElectronicScienceandEngineering,SoutheastUniversity,Nanjing,ChinaKeyLabofConcreteandPrestressedConcreteStructureofMinistryofEducation,SoutheastUniversity,Nanjing,ChinaUnitofArmyForceoftheChinesePLAEmail:zhangjiannjiteducnZHANGJian,TUYongming,TUXiaomingInvestigationofimplementofJacobiiterationonGPUComputerEngineeringandApplications,,():Abstract:JacobiiterationisthebasicmethodtosolvethelargescalelinearequationsInthispaper,thepartsofJacobiiteration,whichneedsalotoftimeforcalculation,aretransplantedonGraphicsProcessingUnit(GPU)torun,inordertoimprovethespeedtosolvethelargescalelinearequationswiththeparallelprocessingcapabilitiesofGPUThetwofactors,whicheffectthespeed,areanalyzed:ThedataexchangebetweenCPUandGPUandtheaccessingofsharedmemoryTheexperimentshowswhentheorderoflinearequationsis,thespeedofcalculationimprovesmorethantimesKeywords:JacobiiterationGraphicsProcessingUnit(GPU)dataexchangebetweenCPUandGPUsharedmemory摘要:雅可比迭代法是求解大型线性方程组的基本方法利用GPU(GraphicsProcessingUnit,图形处理器)的并行处理能力,将雅可比迭代求解线性方程组过程中运算量较大的部分移植到GPU上执行,以提高运算速度并分析了影响运算速度的两个因素:CPUGPU数据交换和共享变量的访问实验结果表明采用单个thread访问共享变量判断迭代是否收敛时,线性方程组的阶数为o,速度可以提高倍以上关键词:雅可比迭代图形处理器CPUGPU数据交换共享变量DOI:jissn文章编号:()文献标识码:A中图分类号:TPl引言求解线性方程组是解决许多数值计算问题的核心因此,对大规模线性方程组的求解在科学计算中显得非常重要线性方程组求解算法大体可分为两类:直接法和迭代法由于迭代法具有程序逻辑简单,占用存储空间小的特点,因此更适用于具有大型系数矩阵的线性方程组求解I当前对迭代算法的研究已经较为成熟,但如何使之适合新体系结构模型,以获得更好的性能加速一直是应用和体系结构设计者关心的问题近年来,由于在GPU(GraphicsProcessingUnit,图形处理器)中加入可编程内部处理器,使GPU具备很高的运算性能运算过程中GPU相当于大量的并行处理器相比CPU而言,GPU硬件结构采用了更多的ALU(ArithmetictogicUnit,运算逻辑部件)参与数据处理,而不是被用在数据缓存和流程控制,所以GPU更适合那些相同程序并行处理大量数据的并行计算利用GPU的这一特性在GPU上实现迭代法求解线性方程组,以期获得更高的运算速度GPU编程框架NVIDIA公司针对GPU的通用运算,提出的GPU与CUDA(ComputeUnifiedDeviceArchitecture,计算统一设备体基金项目:国家自然科学基金(theNationalNaturalScienceFoundationofChinaunderGrantNo)教育部博士点基金新教师项目(No)江苏省自然科学基金(theNaturalScienceFoundationofJiangsuProvinceofChinaunderGrantNoBK)华南理工大学亚热带建筑科学国家重点实验室开放研究项目(NoKB)作者简介:张健(一),男,博士,讲师收稿日期:,O修回日期:,()ComputerEngineeringandApplications计算机工程与应用图CUDA逻辑架构及其与设备内存的对应关系系结构)相结合进行并行运算的方法【,可以通过片上(on一输入:系数矩阵A一常数向量s,初始解向量x…chip)上百个处理器同步协作,从而快速解决复杂的运算问题BeginCUDA是把GPU作为并行运算设备进行程序发布和管理()diff=~运算,不需要将计算映射到图形应用程序接口的硬件和软件的)whiletd"do架构为了实现这一功能,CUDA定义了相应的逻辑架构,并于'山GPU设备相对应,如图所示其中,Thread是最小的逻辑运儿d算单位,多个Thread组成Block这些Thread可以处理相同或::"一u,i不同的运算过程,每个Thread在Block中有唯一的标识符,通ffth过标识符来在程序中进行判断,就可以让某个或某些特定位置n:一嘞蕾的数据得到相同或不同的运算处理endifendfor实现方法与结果分析(iii)newFnewx雅可比迭代的基本方法与在GPU上的实现endfor雅可比迭代是计算线性方程组的一种基本方法,对于求解)tori=don阶线性方程组A,将原方程组的每一个方程啦l"{山"j改写为未知向量的分量的形式:"…一b广产生韭一all然后使用第k步所计算的变量"来计算第步的的值:,』生生一k啦这里,为第k次迭代得到的近似解向量"':(,…,:)的第i个分量取适当初始解向量代入上述迭代格式中,可得到X…,再由X…得到X,依次迭代下去得到近似解向量序列}若原方程组的系数矩阵按行严格对角占优,则"}收敛于原方程组的解实际计算中,一般认为,当相邻两次的迭代值与:注(,,…,)很接近时,'与准确解中的分量置也很接近,因此,一般用maxI(k)~tI判断'n迭代是否收敛程序基本流程如下所示:endwhileEnd输出:解向量X其中共有两个嵌套的循环处理,分别为判断迭代收敛的循环()和其中嵌套的求n个neWX的循环()结合GPU适合并行处理的单指令多数据(SIMO)程序的特性~l,可以将其中的循环(),改在GPU上运行,并将迭代得到的误差返回CPU,再作判断是否需要继续迭代还是输出结果,避免了并行程序中需要判断迭代是否结束,而产生的相互通信的需要,简化了程序【改进后的程序流程如下所示:输入:系数矩阵A,常数向量,初始解向量‰Begin()diff=eCPU上运行()while(diff~)d()diff=(i)newx=bGPU上并行运行(ii)forj=ltodoif(')then张健,涂永明,涂晓明:雅可比迭代法在图形处理器上实现的研究newxi~ewxi唧母endifendfor(iii)newx=new吼(iv)diffi=lnewxrxI()fortoldoCPU上运行(i)diff=max{dif~}(ii)FneendforendwhileEnd输出:解向量X在GPU上的运行时间如表所示,与CPU上的运行时间相比,速度并没有明显地提高,特别是在方程阶数较小时,CPU上运行的速度比GPU更快这是因为每次计算完的新值后,需要将相邻两次迭代值的差输出给CPU作进一步的处理,这会耗费较多的时间在方程阶数较高时,速度也仅提高了倍左右(GPU:NVIDIAGeForeeGTXCPU:IntelPentiumDCPUGHz,以下相同)如表所示,其中CPUGPU表示程序在CPU上运行的时间与程序在GPU上运行的时间之比(以下相同)表迭代法求解方程组时间的比较lGPU上实现的改进上述方法,都是需要将判断是否结束迭代的工作,放在CPU上执行,从而使在GPU和CPU之间交换大量的数据,导致速度下降利用CUDA定义的共享内存(多个Thread可以访问),可以在GPU上完成这项工作改变后的程序流程如下所示:输入:系数矩阵A,常数向量s,初始解向量X…Ben()申明sharedboolflagflag=ture()while(flag)do()flag=false(i)newxi=b(ii)forj=ltondoif(,)thennew=Ilew一耳endifendfor(iii)new=newxJ~(iv)ifInewxl)and(flag=false)flag=tureendwhileEnd输出:解向量X…这个过程中除了输入,输出数据外所有程序都在GPU上执行,减少了CPU和GPU之间数据的交换,但是在这个过程中所有thread在每次迭代开始前都需要读取共享变量flag以判断是否需要进行迭代在完成一次迭代后,根据结果需要还需对共享变量赋值由于多个处理器都要对共享变量进行写操作,因为并行处理的同步要求,大量处理器需要等待,浪费大量时问,运算速度与上述的GPU实现没有明显的提高(如表所示)考虑到雅克比迭代过程中,只要有一个变量的误差大于阈值,所有变量都需要重新计算因此,对共享变量赋值过程中,只要有一个thread进行了写操作,其余的不必再做重复的操作可以节约大量的时间,速度明显地提高特别是当方程阶数较大时,速度提高的倍数可以达到倍以上图,图分别给出了在不同情况下雅克比迭代法的运行时间,随着方程阶数的增加,时间都在增加,但是利用GPU运行所需的时间与CPU相比增加的速度更慢特别是当方程的阶数较高时,更能充分的利用GPU的多处理器并行运行,从而得到更好的加速效果(如图所示)方程的阶数图迭代法求解方程组时间结论通过以上分析可知采用单个thread访问共享变量判断迭代是否收敛的方法可以得到最高的运算速度特别是方程阶数越大,效果越是明显随着图形处理器性能的提高,特别是其浮点数处理能力的提高,利用GPU的并行处理能力,实珊陕速的数据处理,在科学计算领域,有着广泛的应用前景表迭代法求解方程组时间的比较(下转页),()ComputerEngineeringandApplications计算机工程与应用使用的TLOHC上的数值HS中间节点就可以利用最新的HSI来验证之后传递的消息过程如下:()源节点向基站发送消息RQSTB:StBIGo(日)lcI(,,…,n)这里的HS是中间节点收到此消息时,它先通过验证C来确定消息来自源节点如果验证成功则保存G和,并继续传递此消息给下个节点如果失败就做丢弃处理基站收到此消息时,也先做认证,认证成功后,解密得到HS()基站向每个节点发布新的月s明文消息RACKBS:BISIHSo节点收到消息后先利用H(HSllG)与保存的c进行比较如果相同,节点就用新收到的来验证之后的数据包这样,每个节点只用做一次认证就可以完成认证工作大大节约了时间…路径更换当路径更改后,新中间节点不能认证消息中的HS,若每更换一次路径都重新发布此值,耗费非常大因此提出两种更换路径方法此处沿用了DengJ等方案叫的方法()基站主动发布OHC值当基站曰发布初始值OHC,以及更新OHC数值时,中间节点的邻居节点也可以同时得到这些值因此,当变更路径时,可以直接验证消息而不需要重新发布()惰性OHC发布也可以不是每次路径更换时就发布OHC因为虽然加入了几个新节点,但由于其他大部分节点仍可以认证数据包的合法性,因此可以当新加入的节点到达一定阀值时再重新发布OHC的最新值性能分析和结论提出了使用TLOHC抵御PDoS攻击的方案,利用TLOHC,基站和中问节点不用存储大量的Hash链,认证计算只需要一次与DengJ等提出的方案相比,有了更高的效率和扩展性具体表现在以下方面:()新方案中的TLOHC的维护阶段中,为了重新连接断裂的TLOHC,基站不用再为每个与它通信的源节点保存一条Hash链,节省了存储空间,提高了计算效率DengJ等的方案中基站曰与源节S需要共享另外一条OHC这种设计使得基站的负荷量大,不利于方案的扩展()更新TLOHC时,当消息从基站B返回源节S时,每个中间节点对消息只进行了一次认证,而DengJ等的方案中每个节点需要对消息做两次认证新方案的时间缩短了一半,提高了传输的效率,节约了中间节点的能量消耗()方案中每个Hash值大小为byte,当基站向源节点发送RACKBS消息时,由于不用再发送Hash值,所以每个消息负荷减小byte方案还改变了初始化消息的发布方式,解决了基站如何得到初始Hash值HS的问题参考文献:【周贤伟,覃伯平,徐福华无线传感器网络与安全【M北京:国防工业出版社,】YeFStatisticalenroutedetectionandfilteringofinjectedfalsedatainsensornetworksCIEEEINFOCM【】ZhusAninterleavedhopbyhopauthenticationschemeforfilteringofinjectedfalsedatainsensornetworksCIEEESymposiumonSecurityandPrivacy,Oakland,USA,DengJDefendingagainstpathbasedDoSattacksinwirelesssensornetworksCProceedingsofthethACMConferenceonComputerandCommunications,Alexandria,Virginia,:HuYCEfficientconstructionsforonewayhashchainsCProceedingsofAppliedCryptographyandNetworkSecurity,NewYark,(上接页)方程的阶数图不同方法与CPU相比速度的变化目前,GPU主要的问题在于GPU与CPU之间数据通信的瓶颈,提高两者之间的数据交换速度,使其能满足大量数据处理的要求,是GPU需要解决的下个问题参考文献:】胡家赣线性代数方程组的迭代解法M北京:科学出版社,【】杨本立线性方程组大数法快速并行解法J】四川大学:自然科学版,,():MacedoniaMTheGPUenterscomputing'SmainstreamJIEEEComputer,,():【KrtigerJ,WestermannRLinearalgebraoperatorsforGPUinnlplementationofnumericalalgorithmsJACMTransOnGraphics,,():】吴恩华,柳有权基于图形处理器(GPU)的通用计算『J】计算机辅助设计与图形学,,():CudaProgrammingGuideVersion【MS】:NVIDIACorporation,QuinnMJParallelprogramminginCwithMPIandOpenMPMS】:TheMcGrawHillCompaniesInc,】TomovS,McGuiganM,BennettR,etaBenchmarkingandimplementationofprobabilitybasedsimulationsonprogrammablegraphiescardsJComputersGraphics,,():】ThompsonCJ,HahnS,OskinMUsingmoderngraphicsarchitecturesforgeneralpurposecomputing:A~ameworkandanalysisC#ProcoftheInt'lSymponMicroarchiteeture,:【】SkillicornDB,DomenicoTModelsandlanguagesforparaUecomputationJACMComputingSurveys,,():GoodnightN,WangR,HumphreysGComputationonprogrammablegraphicshardwareJComputerGraphicsandApplications,,():董琳{u

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/12

雅可比迭代法在图形处理器上实现的研究

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利