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

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

基于区域平均执行时间和数据依赖信息的可能并行区域识别

随着多核处理器逐渐成为处理器发展的新趋势,为了持续提高程序性能,必须并行执行应用程序.传统的自动并行技术能够很好地并行科学计算应用中的规则循环,但对于含有大量函数调用和指针引用的不规则程序,目前还不能有效地对其实施并行.针对这一现状,文中提出了基于区域平均执行时间和数据依赖信息的可能并行区域识别方法来对一些不规则程序实施高效并行,主要贡献如下:(1)自动识别程序中的多种并行性,不仅包括传统并行性分析中的循环迭代间的细粒度并行性,而且也包括传统并行性分析尚不能有效处理的循环体和函数调用点间的粗粒度并行性.对于程序中蕴含的众多并行性,文中基于区域平均执行时间实施收益分析来选择合适的并行区域实施并行;(2)自动识别可能并行区域间数据依赖关系的数量、类型以及导致数据依赖关系的程序变量.基于文中的分析结果,作者使用面向行为的投机并行系统(behavior oriented parallelism)对SPEC2006中的4个测试用例实现了并行化.并行化后的程序在Intel和AMD多核处理器上分别得到了300%和260%的平均性能加速.     

组网雷达估测降水系统并行化方案的设计与实现

国家气象局天气组网雷达定量估测降水系统不仅拥有较大的计算量,而且具有较大的数据吞吐量,同时对实时性要求较高。如果缩短其执行时间,无疑将会带来巨大的收益。鉴于这些特点,使用VTune Amplifer XE对串行程序进行了热点分析和并行性分析,得出程序中有较多线程级并行性,从而制定了相应的并行化方案;然后使用Win32多线程和OpenMP两种技术对该程序在Intel四核处理器平台上进行了并行化。程序主要由单站处理和组网处理两部分组成。由于计算资源的限制,并行后的单站处理程序只有大约10%的性能提升,而组网处理程序则可以达到近似线性的性能提升。通过调整计算负载,并行化版本的加速比可以达到5.5。最后,可以得出该并行化方法适用于计算密集且数据吞吐量较大的一类应用。     

并行化编译中的一种集成优化方法

本文提出了一种面向分布存储器多机系统的并行化编译方法．针对分布存储并行系统的特点，作者采用的基本优化策略是：折衷并行性与数据引用局部性；减少和隐藏通信开销．通过对基于仿射函数的程序分解方式所导致的数据通信性质的分析，得到了适合分布存储结构特殊要求的并行性开发方法．为了在保持并行性的前提下最小化通信数据总量，提出了基于齐次线性方程组求解的程序全局优化分解方法．为了优化数据通信的组织，提高结点代码的效率，又提出了一种以线性不等式组作为工具的更加实用的通信优化和结点代码生成方法.     

出口分支语句的向量化方法

传统的向量化方法和超字并行方法依靠数据依赖关系分析确定程序中的并行性,而依赖关系分析无法处理非结构化控制流语句,现有的编译器对该类语句的向量化能力有限。为此,给出一种面向SIMD扩展体系结构的出口分支语句向量化方法,该方法针对一个向量因子内的出口分支语句,能够有效地进行自动向量化处理。测试结果表明,该方法既充分发掘了程序数据流中的并行性,又保证了控制流语义的正确性。     

嵌入式应用中的循环级线程推测并行性分析

如何有效利用多核提供的丰富晶体管资源对串行程序的执行进行加速是当前研究中的热点问题。线程级推测（thread-level speculation,TLS）技术旨在充分利用多核资源,最大化地开发出串行代码中存在的潜在并行性。目前TLS技术已经在多种串行应用的并行化工作中得到有效利用,但嵌入式应用程序仍未在推测并行化方面进行有效的分析。因此,选取了八个具有代表性的嵌入式应用,对其在循环级推测并行化中的性能提升潜力和运行时特征（数据依赖、线程粒度和并行覆盖率）进行探讨。实验结果表明,利用线程级推测并行化嵌入式应用的加速效果优于指令级并行技术,实验中的最大加速比达到了13.29;在嵌入式应用领域,该技术可以有效地利用4到8核的计算资源。     

二维弹塑性流体力学LSPIC并行程序研究

针对二维弹塑性流体力学非结构网格拉氏应用程序(LSPIC),应用双线性插值、点排序和网格排序三种方法对计算区域进行分解。基于格式所需邻区网格的个数实现区与区之间的消息传递,建立一种非结构网格拉氏程序并行化方法,实现二维弹塑性流体力学拉氏应用程序(LSPIC)程序的并行化。同时进行程序测试和并行效率分析。     

面向CFD的交互式并行化系统Paractive

该文介绍了面向计算流体力学(CFD)的交互式并行化系统Paractive以及Paractive系统实现时所采用的关键技术。该文根据CFD程序及其并行化的特点提出了CFD程序并行化的区域计算模型以及区域相关的概念。区域计算模型将CFD程序看成区域操作的有序组合,区域相关则以区域操作为基本单位,区域操作本身所具有的对大块数据进行整体操作的特点,使得区域计算模型和区域相关非常适合开发CFD程序中蕴含的数据并行性。另外,该文还介绍了基于程序对象树的增量分析技术以及CFD程序并行化的静态性能预测技术,并在最后给出了使用Paractive并行化CFD实际算例的测试数据。     

一种基于代价子图的子字并行指令选择算法

子字并行能够充分利用多媒体算法的数据精度小、内部循环处理形式规则的特点,是加速多媒体处理的有效方式。然而,如何充分挖掘多媒体应用中的子字并行仍然是一个难题。本文说明传统的并行技术可以有效地开发循环中的子字并行性,同时提出一种基于代价子图的子字并行指令自动识别的方法。与其他方法相比,该方法利用代价模型对子子字并行指令选择进行定量评估。本文在TTA体系结构框架下实现了这一方法。实验结果表明,该方法可以充分地提取循环中的子字并行性。     

一种基于前向计算的动态程序切片方法

动态程序切片技术是一种重要的程序分析技术,在软件分析、测试与调试过程中有着广泛的应用。给出一种基于前向计算的动态程序切片方法,该方法首先在对当前执行语句进行定义使用分析的基础上计算该语句定义变量的影响集,其次计算该语句的直接动态依赖关系,最后计算当前执行语句中变量的动态切片。根据该方法设计并实现了一个Java动态程序切片系统,基于一组基准测试程序开展了切片实验,并与已有的切片方法进行了比较。实验结果表明,该方法可以得到比较精确的动态程序切片结果。     

一种分析和理解程序的方法--程序切片

程序切片是一种分析和理解程序的技术,是通过对源程序中每个兴趣点分别计算切片来达到对程序的分析和理解。程序中某个兴趣点的程序切片不仅与该点定义和使用变量有关,而且与影响该变量的值的语名和谓词以及受该变量的值影响的语名的谓词有关。文中详细阐述了程序切片技术的研究与进展情况,并对目前存在各种程序切片方法和工具进行了比较;简单介绍了文中提出的面向对象的分层切片方法及其算法的思想;最后分析了程序切片技术目前     

一种面向对象程序的过程间切片算法

程序切片是一种程序分析技术，它通过把程序减少到只包含与某个特定计算相关的那些语句来分析程序，过程间切片作为图形可达性问题时，需要扩展过程内切片所用的程序依赖图（PDG）成系统依赖图（SDG），然后利用两阶段图形可达性算法计算比较精确的切片，目前程序切片技术的研究以面向对象程序切片为主，文中讨论了一种合适面向对象程序的分层切片方法，并综合分层切片方法和两阶段图形可达性算法提出了一种简化的计算面向对象程序过程间切片的算法。     

Granularity-Driven Dynamic Predicate Slicing Algorithms for Message Passing Systems

Program Slicing is a well-known decomposition technique that transforms a large program into a smaller one that contains only statements relevant to the computation of a selected function. In this paper, we present two novel predicate-based dynamic slicing algorithms for message passing programs. Unlike more traditional slicing criteria that focus only on parts of the program that influence a variable of interest at a specific position in the program, a predicate focuses on those parts of the program that influence the predicate. The dynamic predicate slices capture some global requirements or suspected error properties of a distributed program and computes all statements that are relevant. The presented algorithms differ from each other in their computational approaches (forward versus backward) and in the granularity of information they provide. A proof of correctness of these algorithms is provided. Through the introduction of dominant states and dominant events, critical statement executions are identified that change the value of the global predicate. Under this formulation, optimizing dynamic predicate slicing becomes a meaningful goal as well. Finally, we present how predicate slices can be applied to support comprehension tasks for analyzing and maintaining distributed programs.     

Using program slicing to simplify testing

Program slicing is a technique for automatically identifying the statements of a program which affect a selected subset of its variables. A large program can be divided into a number of smaller program (its slices), each constructed for different variable subsets. The slices are typically simpler than the original program, thereby simplifying the process of testing a property of the program which only concerns the corresponding subset of its variables. However, some aspects of a program's computation are not captured by a set of variables, rendering slicing inapplicable. To overcome this difficulty a program can be rewritten in a self-checking form by the addition of assignment statements to denote these ‘implicit’ computations. Initially this makes the program longer. However, slicing can now be applied to the introspective program, forming a slice concerned solely with the implicit computation. The simplification power of slicing is then improved using program transformation. To illustrate this approach, the implicit computation which dictates whether or not a program is robust is taken as an example. Whether or not a program is robust is not generally decidable making the approach described here particularly appealing because the slices constructed are approximate answers to the undecidable question ‘Is the program p robust?’.     

Using program slicing in software maintenance

Program slicing is applied to the software maintenance problem by extending the notion of a program slice (that originally required both a variable and line number) to a decomposition slice, one that captures all computation on a given variable, i.e., is independent of line numbers. Using the lattice of single variable decomposition slices ordered by set inclusion, it is shown how a slice-based decomposition for programs can be formed. One can then delineate the effects of a proposed change by isolating those effects in a single component of the decomposition. This gives maintainers a straightforward technique for determining those statements and variables which may be modified in a component and those which may not. Using the decomposition, a set of principles to prohibit changes which will interfere with unmodified components is provided. These semantically consistent changes can then be merged back into the original program in linear time     

程序切片技术浅析

程序切片技术是一种重要的程序分析理解方法,可以帮助开发人员和维护人员理解程序的结构和作用。随着编程语言逐渐趋于人性化、多功能化和复杂化,为了适应编程语言的这种进步,程序切片技术也在不断的演化发展着。文章中主要介绍了程序切片技术的一些基本的准则,介绍了程序切片的一些类型,以及如何利用源程序和图形进行程序切片,并且进行了举例说明。     

程序切片技术浅析

程序切片技术是一种重要的程序分析理解方法，可以帮助开发人员和维护人员理解程序的结构和作用。随着编程语言逐渐趋于人性化、多功能化和复杂化，为了适应编程语言的这种进步，程序切片技术也在不断的演化发展着。文章中主要介绍了程序切片技术的一些基本的准则，介绍了程序切片的一些类型，以度如何利用源程序和图形进行程序切片，并且进行了举例说明。     

Dynamic slicing of lazy functional programs based on redex trails

Tracing computations is a widely used methodology for program debugging. Lazy languages, however, pose new demands on tracing techniques because following the actual trace of a computation is generally useless. Typically, tracers for lazy languages rely on the construction of a redex trail, a graph that stores the reductions performed in a computation. While tracing provides a significant help for locating bugs, the task still remains complex. A well-known debugging technique for imperative programs is based on dynamic slicing, a method for finding the program statements that influence the computation of a value for a specific program input. In this work, we introduce a novel technique for dynamic slicing in first-order lazy functional languages. Rather than starting from scratch, our technique relies on (a slight extension of) redex trails. We provide a notion of dynamic slice and introduce a method to compute it from the redex trail of a computation. We also sketch the extension of our technique to deal with a functional logic language. A clear advantage of our proposal is that one can enhance existing tracers with slicing capabilities with a modest implementation effort, since the same data structure (the redex trail) can be used for both tracing and slicing.     

基于程序切片技术的回归测试方法研究

软件测试是软件开发过程的一个重要组成部分,是进行软件有效性检查、提高软件质量的重要手段。随着软件规模的不断增大、复杂度的不断提高,传统的软件测试技术在处理大规模复杂软件系统时会出现许多问题。程序切片是一种程序分解术,主要是通过寻找程序内部的相关性来分解程序,从而达到快速错误定位或理解程序的目的。主要探讨将程序切片技术引入到软件测试中,尤其是分析在回归测试中切片方法是如何提高效率的。