可扩展数据驱动并行算法研究及应用

《可扩展数据驱动并行算法研究及应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据ADissertationPresentedtotheGraduateSchoolofChineseAcademyofEngineeringPhysics(CAEP)inPartialFulfillmentoftheRequirementsoftheDegreeofDoctorofSciencebyAdvisor：Prof．ZeYaoMo!ns!i!坠!星Q￡△PP!i曼鱼￡hY§i坌§垒旦鱼￡QmP坠!垦!iQn垒!△』垒!h皇堕垒!i鱼§，旦星Uing，gbin鱼：May，2009万方数据论文独创性声明11Y121910ULIl7illBol7lll

2、iollIIIlY2907070本人声明所呈交的学位论文是本人在导师的指导下进行的研究工作及取得的研究成果。据我所知，除了论文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中国工程物理研究院或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的声明并表示谢意．作者签名：鳓签字日期：2翌2生互旦!兰旦论文使用授权声明本学位论文作者完全了解并接受中国工程物理研究院研究生部有关保留、使用学位论文的规定，允许论文被查阅、借阅和送交国家有关部门或机构，同时授权中国工程物理研究院研究

3、生部可以将学位论文全部或部分内容编入有关数据库进行检索，可以影印、缩印或扫描等复制手段保存、汇编论文。保密的论文在解密后遵守此规定。作者签名：趟签字日期：j生笃溘_王地导师签名签字日期：上塑字j三￡业万方数据可扩展数据驱动并行算法研究及应用摘要在高性能科学计算中，计算区域通常被离散成网格，微分方程在网格上由计算方法离散。从相邻网格间数据依赖关系的角度，计算方法可以分为两种类型：无向数据依赖和有向数据依赖。对于前者，网格单元的计算可以通过引用相邻网格单元的已知量而独立进行；对于后者，网格单元的计算依赖于某些相邻网格单元的最新计算结果，也就是说，只有所有这些相邻网格

4、单元计算完毕，才能开始该网格单元的计算。对无向数据依赖的计算方法，计算区域可以分解为多个子区域并分配到不同处理器中，高效并行算法可以按粗粒度的BSP模型进行设计。但是，对有向数据依赖的计算方法，这种并行算法设计模式无法适应，需要考虑细粒度的并行计算模型和相应的并行算法。细粒度的并行计算对并行机的通信延迟提出了很高的要求，但是，随着现代高性能计算机的快速发展，处理器间的通信延迟可以降低到几个微秒，这使得细粒度的高效有向数据依赖并行算法的设计成为可能。本文以求解粒子输运方程的离散纵标(SN)计算方法及其它若干有向数据依赖关系计算方法为背景，围绕刻画有向数据依赖关系的

5、并行计算模型、基于模型的通用并行算法、并行算法的性能优化、并行算法的实际应用等方面进行了系统深入的研究，取得如下主要研究成果：(一)通过分析典型科学计算应用计算方法的有向数据依赖关系，基于有向图，归纳总结并提出了一种刻画有向数据依赖关系的数据驱动并行计算模型，将计算方法的并行计算问题等价地转化为模型的并行计算问题。(二)针对数据驱动并行计算模型，提出了统一形式的数据驱动并行算法，以及相应的性能评价方法。该算法由三部分组成：有向图剖分、结点优先级策略和并行流水线算法。(三)针对二维辐射输运问题，实现具体的数据驱动并行算法，通过对程序LARED．R．1的并行化，在上

6、百个处理器上，取得了可扩展的并行性能。万方数据II可扩展数据驱动并行算法研究及其应用(四)针对数据驱动并行算法，提出一种具有普适性的新的结点优先级策略，可用于充分挖掘并行度。理论证明和实际应用表明，该策略在数百个处理器上效果明显。(五)针对并行自适应结构网格应用支撑软件框架(JASMIN)，提出并实现了适合数据驱动并行算法的三层软件体系结构。该体系结构大幅降低了有向数据依赖关系计算方法并行程序的研制难度。并且2048个处理器上的性能测试表明，这种实现是相当有效的。关键词：有向图、并行计算模型、并行算法、粒子输运方程。万方数据searchonScalablePar

7、allelDatavenAlgorithmsandApplicationsAbstractForthescientificcomputation，thecomputationaldomainisusuallydiscretizedintogrids，andthedifferentialequationsarediscretizedonthegrids．Accordingtothedatadependencyofneighboringgridcells，thecomputationalmethodsareclassifiedintotwotypes：oneisun

8、directionala