中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 中科院软件所  > 中科院软件所
题名:
基于路径符号执行的数据相关性分析
作者: 王晓亮
答辩日期: 2004
专业: 计算机软件与理论
授予单位: 中国科学院软件研究所
授予地点: 中国科学院软件研究所
学位: 博士
关键词: 数据相关性 ; 静态测试 ; 动态测试 ; 路径 ; 符号执行
摘要: 本文的工作主要是进行数据相关性测试的研究,作者首先回顾了数据相关性研究的传统方法,以及并行编程与数据相关性的关系。进而提出了基于路径分析和符号执行的静态测试和动态测试方法,来研究串行程序中循环内部数组变量的数据相关性,该方法对于下标表达式为线性表达式时有很好的效果,而且能够处理一些复杂的数组下标表达式,比如数组下标表达式含有输入变量和非线性下标表达式的情况。数据相关性的静态测试中,我们首先生成程序的流程图,在遍历流程图的同时生成这个程序的扩展有限状态机(EFSM),然后调用路径分析工具对EFSM的路径进行分析。我们采用了遍历程序路径和对路径进行符号执行的策略,这样可以尽可能早的发现程序中的不可执行路径,从而提高分析的效率。数据相关性的静态测试可以精确处理数组下标表达式为线性表达式的情况,而且还可以精确求解数组下标中含有输入变量的情况。静态测试在限定的范围内是精确测试。同时,我们还提出了判断数据相关性的动态测试。动态测试就是在解释执行程序的同时,记录串行程序对数组元素的访问,如果发现数据相关就终止测试。动态测试是基于我们假设如果循环中存在数据相关,那么在循环的有限几次迭代中就会出现数据相关。动态测试能够处理数组下标表达式较为复杂的清况,也可以处理非线性表达式。
英文摘要: In this thesis, we will review some traditional methods of detecting data dependence and analyze the relation between the data dependence and the mechanism of parallelism. Based on path analysis and symbolic execution, we describe two methods, static analysis and dynamic analysis, for detecting data dependence of array variables in loops of sequential programs. In static analysis, we generate the control flow graph of the sequential program and convert the graph to an extended finite state machine (EFSM). By analyzing the paths of the EFSM, we can find whether there is data dependence in the program or not. We can also find unexecutable paths of the sequential program. When we find them we will stop the analysis. We enhance the capability of the traditional methods of detecting data dependence. We can deal with the programs that contain some input variables, the programs with control structures and unexecutable paths. With our method more information will be acquired and the accuracy of the analysis will be improved. In some sense, our data dependence analysis is an exact method. We also describe a dynamic method of detecting data dependence. While executing the program, we memorize all the values of each array variable. The analysis will stop if data dependence is found. Although it is not an exact method in data dependence analysis, it can also process some difficult problems, for example, programs with complex subscripts in loops.
语种: 中文
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/6700
Appears in Collections:中科院软件所

Files in This Item:
File Name/ File Size Content Type Version Access License
LW014048.pdf(2980KB)----限制开放-- 联系获取全文

Recommended Citation:
王晓亮. 基于路径符号执行的数据相关性分析[D]. 中国科学院软件研究所. 中国科学院软件研究所. 2004-01-01.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[王晓亮]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[王晓亮]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace