优化的数组数据流分析技术的实现.pdf

第34卷第7期 计算机工程 2008年4月 2008 V01．34 No．7 ComputerEngineering April ·软件技术与数据库· 文章编号，loo㈣428(20吣)07_枷64珈3文献标识码：A 中田分类号。TP311 优化的数组数据流分析技术的实现 姜凡，庞建民，赵荣彩，任华 (解放军信息工程大学信息工程学院计算机系，郑州450002) 摘要：精确的数组数据流分析是并行编译技术中的重要步骤。用终写树算法表示精确的数组数据流分析仅针对一对读写引用。该文研究 并在工程上实现了终写树交叉算法，以分析多个写引用与公共读引用之间的精确数据依赖关系，减少了冗余信息并使精确数组数据流分析 技术得到一定程度的优化。 关健诃：精确的数组数据流分析；终写树；LWT树的交叉 of Data-flow ImplementationOptimizedArray Analysis JIANGFan，PANGJian-min，ZHAO Hua Rong-cai。REN ofInformation Information (Dept．ofComputer，CollegeEngineering，PLAEngineeringUniversity,Zhengzhou450002) data-flowisan in an to [Abstract!Precisearray analysisimportantstepparallelizingcompilertechnique．StanfordUniversitypresentsalgorithm calculateanLWTfora ofreadandwritestatements．Thisresearchesand allLWTintersect inordefto singlepair paper implements algorithm data with writesandcommonread．Theresultofthis eliminatesalotofredundant analyzeprecisedependencerelationshipmultiple algorithm informationand the dam-flow improvesprecisearray analysistechnique． data—flow Write LWTs IKeywords!prcci∞array Tree(LWT)；intersect analysis；Last 数据依赖关系分析是并行编译技术的一项重要内容uJ， 称为真依赖。 分析的结果是循环并行化优化的主要依据。传统的数据依赖 通常情况下，用数据流依赖向量、依赖层次等概念来描 关系分析主要是判断在循环嵌套中2个同名数组引用是否会 述依赖关系分析的结果。 访问到相同的存储单元，并给出描述依赖关系的距离向量或 如果存在一个数据流依赖迭代对(iw,i，)，并且i，一i。=d， 方向向量，但具有一定的局限性。精确的数组数据流分析是 则2个引用的数据流依赖向量(data—flow vectors)