基于数组私有化的规约识别方法研究与设计
本文关键词:基于数组私有化的规约识别方法研究与设计,由笔耕文化传播整理发布。
【摘要】:串行程序并行化的目标是将串行程序转换为等价的可以在并行环境下执行的程序。等价的含义是指串行程序与转换后并行程序的执行结果完全相同。在整个转换过程中,识别出更多的可以并行执行的部分是提升转后并行程序在并行环境下执行效果的关键,而对于循环的并行识别尤为重要。将不能并行的循环转换可并行的循环的技术一般称为循环并行化技术。数组私有化是当前重要的并行化技术,该技术发展的较为成熟。而通过规约操作使循环并行化的技术还有较大的发展潜力。本文在数组私有化的研究成果基础上,结合规约操作过程的特点,对数据处理的规约操作的各个要素进行了分析,总结出了可规约运算、可规约变量的概念,分析证明了其性质并且证明了其判断准则。然后基于这些结论,设计了适用于不同情境的规约识别算法。本文的主要工作如下:首先,通过对数组私有化理论的研究与学习以及对规约操作过程的分析,提出了可规约运算以及可规约变量的概念,对其性质进行了分析,提出并证明了可规约运算以及可规约变量的判断准则;其次,以可规约变量以及可规约变量的相关理论为基础,基于数组私有化的相关成果,设计了适用于程序段的局部规约识别算法。并以其为基础,设计了对循环各迭代规约变量信息进行处理的循环规约识别算法。基于当前的规约识别策略,设计了计算量较少的静态循环规约识别算法。基于相关-覆盖方法设计了数组私有化、规约识别统一算法。最后,本文通过实验测试了局部规约识别算法、循环规约识别算法、静态规约识别算法以及基于相关-覆盖方法的数组私有化及规约识别统一算法的正确性,并将其与现有算法进行对比,说明了这些算法能识别出更多类型的存在规约变量的循环,本文中的算法优于现有算法。
【关键词】:并行计算 串行程序并行化 循环并行识别 规约识别
【学位授予单位】:东北大学
【学位级别】:硕士
【学位授予年份】:2014
【分类号】:TP338.6
【目录】:
- 摘要5-6
- Abstract6-10
- 第1章 绪论10-14
- 1.1 研究背景和意义10-11
- 1.2 当前国内外研究现状11-12
- 1.3 本文主要内容12-13
- 1.4 本文组织结构13-14
- 第2章 相关研究介绍14-28
- 2.1 依赖关系14-16
- 2.1.1 控制依赖概念14
- 2.1.2 数据依赖概念14-16
- 2.2 数组私有化16-23
- 2.2.1 数组私有化概念17-19
- 2.2.2 基于定义点的数组私有化判定准则19-20
- 2.2.3 数据相关数组私有化方法20-21
- 2.2.4 数据流依赖分析方法21
- 2.2.5 相关-覆盖方法21-23
- 2.3 当前规约识别研究现状23-24
- 2.4 全部私有化以及选择私有化操作介绍24-26
- 2.4.1 全部私有化(Array Privatization)24-25
- 2.4.2 选择私有化(Selective Privatization)25-26
- 2.5 本章小结26-28
- 第3章 可规约变量识别研究28-46
- 3.1 循环可并行准则研究28-30
- 3.2 可归约准则30-43
- 3.2.1 可归约运算分析32-36
- 3.2.2 对于可规约运算的识别的讨论36-38
- 3.2.3 可归约变量分析38-40
- 3.2.4 初值复制40-43
- 3.3 基于规约以及数组私有化的循环并行化准则43-44
- 3.4 本章小结44-46
- 第4章 相关算法设计46-58
- 4.1 规约识别算法设计46-54
- 4.1.1 局部规约变量的判断算法46-49
- 4.1.2 已获得循环迭代可归约变量信息的循环规约判断算法设计49-53
- 4.1.3 静态循环规约识别算法设计53-54
- 4.2 基于相关-覆盖的包含规约识别、数组私有化识别的循环并行识别算法54-56
- 4.3 本章小结56-58
- 第5章 实验58-62
- 5.1 实验设计58
- 5.2 局部规约判断正确性判断以及与其它方法对比58-60
- 5.3 已知各迭代归约信息的循环规判断算法正确性检测60-61
- 5.4 静态识别算法、基于相关-覆盖的数组私有化及规约统一识别算法的正确性分析正确性判断以及与Cetus原方法对比61
- 5.5 本章小结61-62
- 第6章 总结与展望62-64
- 参考文献64-68
- 致谢68
【相似文献】
中国期刊全文数据库 前10条
1 江文毅,庞丽萍,高兰,韩宗芬;串行程序的并行划分算法研究[J];华中科技大学学报;2000年12期
2 蒋作;高毅;;关于串行程序并行化[J];云南民族大学学报(自然科学版);2007年03期
3 罗昕,王庆超,李莲治;串行程序的并行划分算法及其正确性证明[J];宇航学报;1994年04期
4 C.V.Ramamoorthy;W.H.Leung;查良钿;;一个串行程序的并行执行方案[J];电子计算机动态;1979年03期
5 吴悦;雷超付;杨洪斌;;选择性循环的并行方法[J];计算机工程;2010年09期
6 曾扬;串行程序的依赖关系分析和向量化[J];计算机学报;1993年02期
7 罗昕,于月芬,罗静敏;串行程序在大粒度级的并行分解及可并行执行包的形成[J];小型微型计算机系统;1996年08期
8 孙立斌;邓蓉;陈闳中;;串行程序的任务DAG图构造算法[J];计算机系统应用;2012年09期
9 王义和,王振宇,郭福顺;面向分布式系统的串行程序的并行分解与运行[J];哈尔滨工业大学学报;1991年03期
10 乐晓波,黄敏;用Petri网分析串行程序的并行性[J];小型微型计算机系统;2001年11期
中国重要会议论文全文数据库 前1条
1 张晓霞;;SGI对MPI的优化与调整[A];中国工程物理研究院科技年报(2002)[C];2002年
中国博士学位论文全文数据库 前1条
1 林英;多核软件形式化建模、验证及性能评价方法研究[D];云南大学;2013年
中国硕士学位论文全文数据库 前9条
1 武慧冬;基于GPU的激光与等离子体互作用PIC/MCC模拟并行研究[D];电子科技大学;2015年
2 张朋;多核平台下串行程序的并行化改造[D];电子科技大学;2015年
3 陈剑;基于数组私有化的规约识别方法研究与设计[D];东北大学;2014年
4 曹婷婷;基于多核处理器串行程序并行化改造和性能优化[D];西南交通大学;2009年
5 姚辉萍;串行程序并行化及其在桌面网格中的应用[D];苏州大学;2010年
6 孙岩;片上多核处理器体系结构下的串行程序加速方法[D];内蒙古大学;2011年
7 王磊;基于MPI的串行程序自动并行化的应用研究[D];安徽理工大学;2013年
8 闫玉忠;串行程序并行化技术研究与一种新实现构想[D];西南交通大学;2003年
9 卢风顺;海洋资料变分同化系统优化及并行实现[D];国防科学技术大学;2007年
本文关键词:基于数组私有化的规约识别方法研究与设计,由笔耕文化传播整理发布。
,本文编号:338188
本文链接:https://www.wllwen.com/kejilunwen/jisuanjikexuelunwen/338188.html