基于GPU平台的KLU并行算法的研究与实现预处理及回代求解.pdf

《基于GPU平台的KLU并行算法的研究与实现预处理及回代求解.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、类号DC论文题目密级编号基于GPU平台的KLU并行算法的研究与实现：预处理及回代求解研究生：武瞳红指导教师：．值童强教援．专业：让簋扭丕统结捡研究方向：差堑让箕所在学院：让簋扭堂院；：、2011年6月9日原创性声明·本人声明：所呈交的学位论文是本人在导师的指导下进行的研究工作及取得的研究成果。除本文已经注明引用的内容外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得内鏊直太堂及其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论支作者签名：立氐殖红日、期：型2隼笸盈!生丑指导教师签名

2、：锄玺日期：2口If垒笸目￡丝目在学期间研究成果使用承诺书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：内蒙古大学有权将学位论文的全部内容或部分保留并向国家有关机构、部门送交学位论文的复印件和磁盘，允许编入有关数据库进行检索，也可以采用影印、缩印或其他复制手段保存、汇编学位论文。为保护学院和导师的知识产权，作者在学期间取得的研究成果属于内蒙古大学。作者今后使用涉及在学期间主要研究内容或研究成果，须征得内蒙古大学就读期间导师的同意；若用于发表论文，版权单位必须署名为内蒙古大学方可投稿或公开发表。学位论文作者签名：盘盔壁垒日期：塑厶2笸：!丝指导教师签名：翅

3、望蠡日期：型址旦红名．内蒙古大学硕士学位论文基于GPU平台的KLU并行算法的研究与实现：预处理及回代求解摘要在大型电路模拟中，Ax=b形式的线性方程组的求解是影响电路模拟效率的关键问题。为了解决这一问题，目前已经存在许多针对大型电路模拟矩阵的求解器，例如sparce1．3、superLU、KLU等。实验表明，与其他算法相比，KLU算法效率更高、更适合于处理大型电路模拟矩阵。KLU(ClarkKentLU)，是由ClarkKent专门针对大型电路模拟矩阵设计的一种新型的稀疏矩阵求解算法。KLU算法共分为四个阶段：预处理阶段、分解阶段、再分解阶段、求解阶段。本文重点在GP

4、U平台上，对KLU算法中的预处理阶段(btf_strongcomp算法、)和求解阶段(klusolve算法)进行并行性研究与实现。在预处理阶段，利用btf算法将矩阵转化为上三角块的形式。btf算法包括两个部分：btf—maxtrans算法和btf_strongcomp算法。对btf_strongcomp算法在GPU平台上的可并行性作了详细的研究与探讨，提出了几种可并行的方案：深度优先搜索算法、可达矩阵算法、zdec算法的并行，并对DCSC算法在GPU平台上的可并行性作了研究。研究结果表明，在GPU平台上实现btf__strongcomp算法的并行，会导致算法性能下降，

5、进而降低KLU算法的整体效率。但是对于某些矩阵而言，在使用zdec算法将矩阵转化为上三角块的形式后，可以提高KLU算法的整体效率。求解阶段可分为两部分：顺序消元和回代求解。’由于在顺序消元的过程中存在很强的依赖性，本文只对klusolve算法的回代求解部分在GPU平台上实现了并行。对于大部分矩阵而言，并行实现的klusolve算法在NvidiaGeforceGT勉75平台上的运行时间，是串行klusolve算法在IntelPentiumD2．80GHzCPU平台上运行时间的10倍以上。基王鱼呈旦兰鱼箜型堑堑篁鲨竺婴窒兰窒婴：堡竺堡垦旦垡查堡．——--_-●_●————

6、-—-———_—————————_-—_————-—————_-_———-_————_●_———————_———————————————一本文通过分析电路模拟矩阵和GPU平台的特点，并将KLU算法中的btf_strongcomp算法和l(1u-solve算法在GPU平台上实现了并行。实验结果表明，KLU算法中的预处理阶段和求解阶段不适合在GPU平台上实现并行。关键字：KLU；btf；amd；GPU；矩阵求解内蒙古大学硕士学位论文RESEARCHANDIMPLEMENTATIoNoFKLUALGORITHMBASEDONGPU：PREPROCESSANDBACK．SUB

7、STITUTEABSTRACTInlargecircuitsimulation，thekeyissuewhichaffectstheefficiencyofcircuitsimulationissolutionoflinearequationsinformAx=b．Tosolvethisproblem，therearemanysolversforlargecircuitsimulationmatrix，forexample，sparce1．3，superLU，andKLU．ExperimentresultsshowthatKLUalgorithmwh