嵌入一致图语法的依赖图

图语法将字符串上的形式文法扩充为图上的形式文法,提供一种能够使用精确的数学方法来模拟图变换的机制.提出了几种新的基于一致图语法的方法来表示控制流图、数据流图、控制数据流图、二分图和超图,并说明如何通过图重写来自动生成依赖图并挖掘并行性,从而协助并行编译器和并行语言的设计和实现.     

DO循环并行性识别的实现

本文主要研究顺序FORTRAN程序的并行转挨系统中的并行性识别和划分问题。着重探讨了DO-LOOP内语句的相关性问题和DO-LOOP的并行识别和划分,包括:相关性识别理论,A(ai+b)类型数组元素的判定算法以及DO-LOOP的大模块并行性划分方法。 在词法分析、语法分析、数据流分析后生成的PDG图基础上,用程序实现了单重DO-LOOP的大模块并行划分,生成的是并行划分后的PDG图,进而得到进程流程图。 本文还研究了多重DO-LOOP的并行性识别和并行性划分的基本原理和方法。     

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

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

JAPS中的任务划分与粒度控制

程序并行化为了达到缩短程序运行时间的目的 ,需要关注两方面的问题 :1,任务之间并行性的挖掘 ;2 ,粒度控制 ;如何协调这两方面的关系以及如何自动的完成这个任务是现在工作的重点 .本文详细讨论了如何在 CDDG图上决定合适的任务粒度 ,提出基于关键路径的任务粒度控制理论 ;并描述了在 JAPS中实现的自动任务划分与粒度控制算法 .涉及的主要问题包括结点的分布 ,任务的粒度控制 ,任务的划分 ,并对它的实践结果进行分析     

顺序程序的并行性识别—一种基于变量活动域的方法

本文提出了一种新的顺序程序并行性的识别方法——基于变量活动域的识别方法,这种方法在程序转换的基础上,系统地削弱了语句之间的数据相关性,提高了程序的并行性;并在变量活动域的基础上将转向控制相关转化为数据相关,最终生成一有条件的数据流图,而不带来任何额外副作用;另外,本文对此识别方法的正确性给出了严格证明。     

图形化编程中模块间并行性的自动挖掘

在基于模块组合的图形化编程中,存在大量互不依赖的模块,这些模块具有并行执行的性质。翻译程序以拓扑排序算法遍历该有向无环图,为每个模块产生一个线程,为每条输入线产生一个信号量,以同步有依赖关系的模块的执行顺序,最终产生一个可并行执行的多线程程序,从而达到自动挖掘并行性、提高所生成程序的运行效率的目的。     

一种精确的调用图生成技术

调用图是过程间分析和程度自动并行化的基础。生成精确调用图可以进一步开发程序的并行性。此文针对Ｆｏｒｔｒａｎ程序，提出了一项完全消除哑过程，产生精确调用图的技术与相应的算法。该算法已在面向ＭＰＰ Ｆｏｒｔｒａｎ的程序自动并行化工具中实现。     

基于Define-Use图的MPI通信求解算法

针对分布存储计算机系统并行编译过程中,为维持数据一致性而产生冗余通信的问题,提出一种优化的通信求解算法。该算法基于依赖关系分析和过程间数据流分析,通过遍历Define-Use图,获得更精确的通信数据,消除过程调用时产生的冗余通信。实验结果表 明,将算法所得结果作为后端生成MPI通信代码的依据,可以有效减少通信量,加速比接近手工MPI并行程序。     

X10程序的差别分析方法

程序差别分析是程序调试的常见手段,其主要用于分析程序不同版本之间的差异信息.然而,将现有程序差别分析算法扩展到并行程序语言还面临众多挑战.其主要原因在于并行程序复杂性较高,且存在支持并行活动的特殊机制,如地址(或线程)、活动、同步等,从而为有效进行程序差别分析设置了障碍.文中研究基于PGAS模型的X10并行程序的程序差别分析方法,并设计了一种语句级的、针对X10程序的程序差别分析算法X10Diff.X10Diff包括下列步骤:(1)匹配原程序和修改后程序中的类、接口、方法及地址;(2)为待分析程序片段构建基于地址的程序流图,并建立相应简化图;(3)迭代扩展并比较简化图,并将差别信息定位到代码中.     

多处理器结构实现并行推理初探

推理机是第五代计算机的核心,扩展的PROLOG 语言是第五代计算机的核心语言,基于PROLOG 语言的推理机的研究,已引起了越来越多的人的兴趣。本文首先简要介绍了PROLOG 程序中的五种固有并行性:“与”并行性、“或”并行性,搜索并行性,流并行性和变量匹配并行性。然后着重分析了实现“与”并行和“或”并行必须要解决的问题。“与”并行中的关键问题是确定体中各目标的执行顺序和对目标的所有解进行相容性检测。“或”并行中的关键问题是设计好的子句排序算法和根据求解要求自动中止某些求解进程。一个好的一致化算法也是加速求解进程的关键问题。文中提出了相容性检测算法和子句排句算法的设计规则,同时也介绍了Conery 和Kibler 在并行中确定目标执行顺序的一个定序算法。文中最后给出了一种实现并行推理的多处理器结构。该处理器结构同时执行“与”并行和“或”并行,“或”并行中又包含并行和流水。该处理器结构简单清楚,处理器之间相互独立,通信少,便于扩充,控制也比较方便。     

有向图并行计算中的多目标剖分算法

在以离散网格为基础的某些数值模拟中,网格间的数据依赖关系可以抽象为有向图．如何剖分这些有向图成多个子图,将各子图对应的数值模拟任务映射到不同的处理机,是该类数值模拟并行计算的基础．剖分算法中,需要综合考虑连通性、并行度、负载平衡、通信开销四个目标．文章在传统有向图剖分算法的基础上,提出了一个权衡这四个目标的有向图多目标剖分区域分解算法．应用于二维非结构网格上的柱对称中子输运并行计算中,通量扫描并行算法在该区域剖分算法上获得的并行效率比原来的无向图区域剖分算法高50％以上．     

图依赖研究与应用综述

图依赖是用于解决图数据的数据一致性问题的数据质量规则。基于图依赖提升数据一致性的过程通常分为图依赖定义与形式化、图依赖自动挖掘、基于图依赖的数据一致性提升三步。介绍了针对数据一致性的图依赖理论,并根据拓展类型将图依赖分为基于结构约束拓展、基于语义约束拓展和基于外部约束拓展的图依赖;综述并对比了从图数据中自动挖掘图依赖及其拓展的算法;分析了应用图依赖提高数据一致性的研究现状;总结了当前研究中仍存在的问题,并依据问题展望了图依赖在数据质量领域的应用前景。     

并行程序验证的调度策略

针对形式化程序验证中的并行调度问题,提出了基于依赖集的算法。通过引入依赖图和依赖集概念,以形式化方式描述程序语句间的依赖关系,然后给出了从语法分析树构造依赖图和依赖集的算法;最后在此基础上设计了并行调度算法并应用于计算机辅助程序验证系统。实验结果表明,该方法具有较高的并行效率。     

A join algorithm for combining AND parallel solutions in AND/OR parallel systems

When two or more literals in the body of a Prolog clause are solved in (AND) parallel, their solutions need to bejoined to compute solutions for the clause. This is often a difficult problem in parallel Prolog systems that exploit OR and independent AND parallelism in Prolog programs. In several AND/OR parallel systems proposed recently, this problem is side-stepped at the cost of unexploited OR parallelism in the program, in part due to the complexity of the backtracking algorithm beneath AND parallel branches. In some cases, the data dependency graphs used by these systems cannot represent all the exploitable indenpendent AND parallelism known at compile time.In this paper, we describe the compile time analysis for an optimizedjoin algorithm for supporting independent AND parallelism in logic programs efficiently without leaving any OR parallelism unexploited. We then discuss how this analysis can be used to yield very efficient runtime behavior. We also discuss problems associated with a tree representation of the search space when arbitrarily complex data dependency graphs are permitted. We describe how these problems can be resolved by mapping the search space onto the data dependency graphs themselves. The algorithm has been implemented in a compiler for parallel Prolog based on the Reduce-OR process model. The algorithm is suitable for the implementation of AND/OR systems on both shared and nonshared memory machines. Performance on benchmark programs exhibiting AND and OR parallelism on one shared memory machine and one message passing machine is presented.This work was supported in part by NSF Grants CCR-87-00988 and CCR-89-02496.A shorter version of this paper appears in theProceedings of NACLP 1990.     

基于基本块标识方法的控制流图生成器设计

设计一个实用的程序控制流分析工具需要解决非结构程序中goto等语句的控制流图构造问题。C语言程序控制流图生成器CfgGen的设计采用基于基本块标识的控制流图构造方法解决该问题。CfgGen程序基于规则,通过语法制导翻译标识基本块、构造控制流图,易移植和维护。CfgGen构造的控制流图标识了基本块,可以很方便地用于程序分析和优化。     

Coordinating Heterogeneous Parallel Systems with Skeletons and Activity Graphs

Large scale parallel programming projects may become heterogeneous in bothlanguage and architectural model. We propose that skeletal programmingtechniques can alleviate some of the costs involved in designing and portingsuch programs, illustrating our approach with a simple program which combinesshared memory and message passing code. We introduce Activity Graphs as asimple and practical means of capturing model independent aspects of theoperational semantics of skeletal parallel programs. They are independent oflow level details of parallel implementation and so can act as an intermediatelayer for compilation to diverse underlying models. Activity graphs providea notion of parallel activities, dependencies between activities, and theprocess groupings within which these take place. The compilation processuses a set of graph generators (templates) to derive the activity graph. Wedescribe simple schemes for transforming activity graphs into message passingprograms, targeting both MPI and BSP.     

Coordinating Programs in the Network of Tasks Model

The Network of Tasks (NOT) model allows adaptive node programs written in a variety of parallel languages to be connected together in an almost acyclic task graph. The main difference between NOT and other task graphs is that it is designed to make the performance of the graph predictable from knowledge of the performance of the component node programs and the visible structure of the graph. It can therefore be regarded as a coordination language that is transparent about performance. For large-scale computations that are distributed to geographically-distributed compute servers, the NOT model helps programmers to plan, assemble, schedule, and distribute their problems.     

并行分布计算中条件分支的静态调度

并行程序中的不确定性给任务调度带来了困难，采用动态调度的方法有时开销很大。本文以并行程度设计中的条件分支为例，介绍了如何利用分支图和前趋图来描述并行程序，并通过对这两种任务图的归约把不确定性转化为确定怀，然后根据确定性图的调度技术，来构造珠调度方案。     

基于静态检测的C++内存泄漏分析

C++是一种非常流行的计算机编程语言,在使用的过程中容易出现内存泄漏问题,而该问题往往难以识别。给出了一种对C++内存泄漏问题进行分析的方法,该方法得到C++源代码的抽象语法树,从抽象语法树中提取程序控制流图,然后将类的构造函数、普通成员函数以及析构函数的程序控制流图相互连接形成新的程序控制流图,并设计算法对控制流图进行检测。最后通过一些内存泄漏的典型实例进行测试,实验表明本方法有效。     

Predicting metamorphic relations for testing scientific software: a machine learning approach using graph kernels

Comprehensive, automated software testing requires an oracle to check whether the output produced by a test case matches the expected behaviour of the programme. But the challenges in creating suitable oracles limit the ability to perform automated testing in some programmes, and especially in scientific software. Metamorphic testing is a method for automating the testing process for programmes without test oracles. This technique operates by checking whether the programme behaves according to properties called metamorphic relations. A metamorphic relation describes the change in output when the input is changed in a prescribed way. Unfortunately, finding the metamorphic relations satisfied by a programme or function remains a labour‐intensive task, which is generally performed by a domain expert or a programmer. In this work, we propose a machine learning approach for predicting metamorphic relations that uses a graph‐based representation of a programme to represent control flow and data dependency information. In earlier work, we found that simple features derived from such graphs provide good performance. An analysis of the features used in this earlier work led us to explore the effectiveness of several representations of those graphs using the machine learning framework of graph kernels, which provide various ways of measuring similarity between graphs. Our results show that a graph kernel that evaluates the contribution of all paths in the graph has the best accuracy and that control flow information is more useful than data dependency information. The data used in this study are available for download at http://www.cs.colostate.edu/saxs/MRpred/functions.tar.gz to help researchers in further development of metamorphic relation prediction methods. Copyright © 2015 John Wiley & Sons, Ltd.