梯形图数据依赖关系分析与并行提取

程序依赖关系分析在对程序进行测试、维护、分析和优化过程中起着重要作用。梯形图(LD)程序中数据定义和数据引用会导致梯级之间存在数据依赖关系和潜在并行性。针对该问题,通过构造数据依赖关系有向图构建数据依赖关系,提取LD图梯级间的数据流和数据依赖信息,并从数据依赖关系有向图中获得LD图并行梯级。实验结果表明,通过并行提取可使LD图的扫描周期缩短至原来的20%~50%。     

Sigma系统中数据依赖关系分析的完善与增强

文中在分析了Ｓｉｇｍａ系统中数据依赖关系测试算法的基础，修正了其算法中的不足，同时，为提高测试的精确度，针对距离量法提出了边界测试的思想，针对消元提出了将消元法和Ｂａｎｅｒｊｅｅ不等式相组的思想，为提高系统效率，提出了不相交子方程组的思想。     

并行化编译器中基于工作量的条件并行化研究

并行化编译器通过发掘串行程序中的并行性来提高程序的运行性能。但当可并行的工作量与并行的线程数目之比较小时，有可能采用并行执行反而会降低程序的整体性能。本文工作基于SUIF结构．研究精确的工作量计算方法，并实现了基于工作量的条件并行化技术．有效地提高了并行程序的执行性能。     

一种基于特征的程序可并行点发现方法

并行编译技术的首要问题就是程序中可并行点的发现。以程序执行时间、程序中的循环部分、数据依赖性分析以及程序执行时间与循环次数比等特征来表征程序的可并行性,并采用SVM根据以上特征进行程序中的可并行点的挖掘。实验证明,该方法更能符合实际应用的需要,发现的可并行点做并行化后有可观的性能加速比。     

并行识别中的依赖关系与通信优化研究

通信开销是阻碍并行程序效率提高的关键因素,降低并行程序的通信开销可以有效地提高程序的运行效率.主要讨论了在并行识别中如何利用依赖关系信息来降低自动并行识别所生成的并行程序的通信开销,包括计算与通信重叠、消除冗余通信代码、消除冗余通信等,并给出了测试结果,试验表明具有较好的优化效果.     

向量化中数据依赖关系的强化

本文以数组项为结点的循环向量化分析方法,对“如果一个语句的所有结点(数组的每次出现)都不在递归回路中,则这个语句就能写成向量形式”的论点提出了反面例证,并通过对数据依赖关系进行强化的方法对循环体的部分向量化问题做了重新论述。     

串行程序的依赖关系分析和向量化

本文提出了两种新的数据依赖关系分析方法——系数判别法和实分析方法,其中,系数判别法在GCD方法基础上,给出数组项之间精确的依赖关系,并直接给出依赖的方向.实分析方法没有目前其他分析方法所要求的下标为循环控制变量的线性函数的限制.并且,很自然地解决了Coupled subscr-ipts及隐关系的分析问题.另外,本文探讨了破除数据依赖关系的方法及向量化的问题.文中的算法均己在UNIX环境下实现.     

一种基于非正规域的区域依赖关系分析法

在自动并行编译中，并行性的识别主要集中在循环及语句级，而许多程序实际上可通过挖掘子程序级这种“任务“并行性来提高性能。本文提出了基于非正规域的区域依赖分析方法，旨在发掘这类并行性，它能精确地刻划程序中的数据访问区域。克服了现有区域分析技术中趋于保守的弱点，从而提出了并行度，依赖关系的测试算法简单而有效。     

对象类之间依赖关系度量分析

类之间的依赖关系,对于面向对象系统分析、设计和测试都有重要的意义。该文首先对类之间的依赖关系进行了定义和说明,并细分其为数据依赖和方法依赖,在此基础上,提出依赖度和被依赖度两种度量方法,并进行了严格的语义分析和说明。最后,文章提出依据这两种度量方法来确定类的规模大小的算法。     

面向对象系统的类之间依赖关系度量研究

类之间的依赖关系,对于面向对象系统分析、设计和测试都有重要的意义。本文首先对类之间的依赖关系进行了定义和说明,并细分其为数据依赖和方法依赖,在此基础上。提出依赖度和被依赖度两种度量方法,并进行了严格的语义分析和说明。     

基于SUIF自动产生具有OpenMP编译指示的并行程序

介绍了如何基于SUIF实现具有OpenMP编译指示的自动并行化工作,即利用SUIF系统所提供的遍(pass)、注释(annotation)和C抽象语法树等技术,通过对类Ctrec的修改,把并行注释转化为OpenMP编译指示,实现由串行程序到并行C程序的自动生成。     

基于SUIF2的静态死锁检测方法研究

死锁是并发程序中常见的错误之一,且由于并发程序运行的不确定性使得死锁难以检测。针对该问题,通过对C多线程程序死锁的分析,提出了一种基于SUIF2的静态死锁检测方法,设计了基于SUIF2的C多线程程序静态死锁检测的框架结构和锁集分析算法。最后通过一个实例说明了该检测方法的有效性。     

基于SUIF2的程序特征分析技术研究

程序特征尤其是存储特征和循环特征对计算机系统及编译器的设计和优化至关重要,但庞大的软件系统和程序分析本身的复杂性使得实现程序特征提取和分析的自动化十分困难.针对这个问题,提出了一种新的基于SUIF2的程序特征分析方法,并以SUIF2为平台设计和实现了一个C程序特征分析工具.首先介绍了工具的设计思想和整体结构,然后详细说明了各部分的功能和实现原理,接着总结了该工具的特点,最后给出了SPEC2000中2个基准程序188.ammp和177.mesa的测试结果及分析.     

Evaluating automatic parallelization in SUIF

This paper presents the results of an experiment to measure empirically the remaining opportunities for exploiting loop-level parallelism that are missed by the Stanford SUIF compiler, a state-of-the-art automatic parallelization system targeting shared-memory multiprocessor architectures. For the purposes of this experiment, we have developed a run-time parallelization test called the Extended Lazy Privatizing Doall (ELPD) test, which is able to simultaneously test multiple loops in a loop nest. The ELPD test identifies a specific type of parallelism where each iteration of the loop being tested accesses independent data, possibly by making some of the data private to each processor. For 29 programs in three benchmark suites, the ELPD test was executed at run time for each candidate loop left unparallelized by the SUIF compiler to identify which of these loops could safely execute in parallel for the given program input. The results of this experiment point to two main requirements for improving the effectiveness of parallelizing compiler technology: incorporating control flow tests into analysis and extracting low-cost run-time parallelization tests from analysis results     

基于SUIF的函数内联技术

从基于调用图的函数内联技术、函数参数的映射技术和内联使用的不同策略3个方面讨论基于SUIF系统的内联技术的实现。根据KAP系统需求,提出叶节点的内联算法,以满足并行性分析的需要,降低全内联引起的代码膨胀问题。测试结果表明,该算法能够有效地内联NPB测试集中的一些函数,经函数内联后,加速比最高可提高15．78％。     

GCC4．1数据依赖分析器的分析与改进

本文深入分析了GCC4．1的数据依赖分析器，针对它在分析Fortran程序的线性化数组访问时的不足，给出了两点改进：一是初步实现了一个非仿射数组下标依赖分析算法；二是提出并实现了分裂递归链的仿射数组下标数据依赖分析方法。实验表明，这两点改进增强了GCC4．1的数据依赖分析能力，为进行循环变换如循环交换提供了更准确的数据依赖信息。     

SUIF2平台下MOD分析算法的设计与实现

MOD问题是指在进行过程调用时哪些信息可能在被调用的过程中被修改。针对C语言,本文提出了一种基于流敏感、上下文敏感指针分析结果的MOD分析算法。该算法通过计算表达式在指向图中的左值,得到所有可能被修改的内存位置,从而计算出所有可能在被调用过程中被修改的表达式。我们在SUIF2平台下实现了该算法,得到了预期的实验结果。     

Padhye TCP吞吐量模型分析及改进性研究

在充分研究Padhye模型的基础上，利用Gilbert模型从另外一个角度计算了TCP吞吐量原理公式，计算结果与原有Padhye模型完全一致．同时定性分析了Padhye模型中各主要参数在丢包率较大时的误差情况，以及造成的Padhye模型在高网络负载下与实际结果的误差情况．基于这种状况，我们提出了一种分段的精确Padhye模型(Ex-Padhye模型)，试验结果表明，Ex-Padhye模型在丢失指示率较高的情况下仍能够较好的与精确值相拟合，在精确度上比Padhye模型有了很大的改善。     

位归约识别的研究与实现

尽管归约识别及并行化技术已经不是一个新的技术,但现有的并行化编译器的归约识别功能还不能满足实际应用的需要。通过对归约操作识别及并行化的分析和研究,在SUIF的基础架构上通过修改中间表示语言,实现了对位归约操作的识别功能。