基于数组私有化的规约识别方法研究与设计

《基于数组私有化的规约识别方法研究与设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据分类号UDC密级学位论文基于数组私有化的规约识别方法研究与设计作者姓名：指导教师：申请学位级别：学科专业名称：论文提交日期：学位授予日期：评阅人：陈剑乔建忠教授东北大学信息科学与工程学院硕士学科类别：工学计算机软件与理论2014年6月论文答辩日期：2014年6月2014年7月答辩委员会主席：赵海教授徐久强教授孙建伟研究员东北大学2014年6月万方数据AThesisinComputerSoftwareandTheoryResearchandDesignonReductionRecognitionMethodsBasedonArrayPriv

2、atizationByChenJianSupervisor：ProfessorQiaoJianzhongNortheasternUniversity—June2014万方数据独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我～同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢=ft，鼠。学位论文作者签名：陆．磊立日期：己夕／7-．‘．1．S-学位论文版权使用授权书本学位论文作者和指导教师完

3、全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年口～年口一年半口两年∥学位论文作者签名：】f；每．亏．j签字日期：b，牛．‘．2厂导师签名：签字日期：万方数据东北大学硕士学位论文摘要基于数组私有化的规约识别方法研究与设计摘要串行程序并行化的目标是将串行程序转换为等价的可以在并行环境下执行的程序。等价的含义是指串行程序与转换后并行程序的执行结果完全

4、相同。在整个转换过程中，识别出更多的可以并行执行的部分是提升转后并行程序在并行环境下执行效果的关键，而对于循环的并行识别尤为重要。将不能并行的循环转换可并行的循环的技术一般称为循环并行化技术。数组私有化是当前重要的并行化技术，该技术发展的较为成熟。而通过规约操作使循环并行化的技术还有较大的发展潜力。本文在数组私有化的研究成果基础上，结合规约操作过程的特点，对数据处理的规约操作的各个要素进行了分析，总结出了可规约运算、可规约变量的概念，分析证明了其性质并且证明了其判断准则。然后基于这些结论，设计了适用于不同情境的规约识别算法。本文的主要工作如下：首

5、先，通过对数组私有化理论的研究与学习以及对规约操作过程的分析，提出了可规约运算以及可规约变量的概念，对其性质进行了分析，提出并证明了可规约运算以及可规约变量的判断准则；其次，以可规约变量以及可规约变量的相关理论为基础，基于数组私有化的相关成果，设计了适用于程序段的局部规约识别算法。并以其为基础，设计了对循环各迭代规约变量信息进行处理的循环规约识别算法。基于当前的规约识别策略，设计了计算量较少的静态循环规约识别算法。基于相关．覆盖方法设计了数组私有化、规约识别统一算法。最后，本文通过实验测试了局部规约识别算法、循环规约识别算法、静态规约识别算法以及

6、基于相关．覆盖方法的数组私有化及规约识别统一算法的正确性，并将其与现有算法进行对比，说明了这些算法能识别出更多类型的存在规约变量的循环，本文中的算法优于现有算法。关键词：并行计算；串行程序并行化；循环并行识别；规约识别万方数据东北大学硕士学位论文AbstractResearchandDesignonReductionRecognitionMethodsBasedonArrayPrivatizationAbstractThegoalofserialprogramcollateralizationistoconverttheserialprogram

7、equivalentlytoprogramwhichcanbeexecutedinaparallelenvironment．Themeaningofequivalenceisthattheresultsofthenewprogramareexactlyequivalenttotheresultsofserialprogram．Intheconversionprocess，thekeytoimprovetheefficiencywhenthenewprogramisexecutedinparallelenvironmentistorecognise

8、morepartsoforiginalprogramwhichcallbeexecutedparallel，anditisparticu