确定性并行技术

由于执行个体之间的同步、竞争和干扰,并行程序的执行存在着不确定性问题,即程序在相同输入下多次执行可能得到不同的结果.不确定性给并行程序在开发、调试、测试、容错和安全等方面都带来了挑战,严重降低了并行程序的可靠性,阻碍了并行程序的发展.确定性并行技术通过控制并行程序执行个体间的同步、竞争和干扰,使程序的执行结果仅依赖于输入.确定性并行技术能够从根本上解决了目前并行程序存在的诸多问题,提升了并行程序的可靠性,给并行程序的发展带来了新的机遇.文中调查、分析和比较了目前主流的确定性并行技术和方法,分析了弱内存一致性对确定性并行系统的影响,并对未来确定性并行技术的发展趋势做出了展望.     

域：支持并行程序概念设计的一种抽象手段

1 引言长期以来,并行计算机在其潜在高性能和现实性能以及简单易用性之间存在着巨大的鸿沟,原因之一在于并行程序设计方法学的滞后导致大量的并行程序设计实践沿袭着传统串行程序开发的思路,而另一个重要的瓶颈在于并行程序的开发缺乏高效编程环境的支持。目前,并行程序的构造主要采取以下两种方式:(一)依据并行算法编写并行程序。这种方式构造的并行程序,一般能达到较高的并行效率,但对广大应用领域的用户要求太高。(二)利用并行化工具对串行程序进行并行改造。由于串行计算机上己经积累了大量成熟的应用程序,通过自动并行编译工具将串行程序移植到并行计算机上运行,无疑具有极为重要的现实意义。并行化方法由于对并行编译的对象缺乏高层的全局信息和并行信息,并行粒度较细,并行效率往往不     

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

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

PPCDS集成开发环境的设计与实现

PPCDS(并行程序概念设计系统)是一个将数据并行高层建模语言、并行识别方法、并行程序自动构造和人机交互界面技术集成在一起的并行程序设计环境,能简化并行程序设计,有效缩短并行程序开发周期,提高并行计算效率。PPCDS集成开发环境是PPCDS的重要组成部分,文中就PPCDS集成开发环境的设计和实现进行了简单介绍。     

二维宏观拟颗粒并行模拟程序通信性能优化策略

随着粒子模拟并行计算在相关领域应用的不断深入和并行节点计算能力的不断增强,粒子模拟并行程序中通信耗时对整体性能的影响越来越显著,甚至成为主要性能瓶颈.本文在分析影响并行程序通信性能多种因素的基础上,从进程划分方式选择、通信协议优化的角度,对1个典型粒子模拟并行程序——二维宏观拟颗粒并行模拟程序在千兆以太网环境下的通信性能的优化策略进行了测试研究,通过改进并行进程划分方式,采用用户级通信协议等方法,使测试程序通信性能获得明显提高,进而提出了粒子模拟并行程序通信性能优化的思路和建议.     

面向嵌入式多核的OpenMP扩展方法

为多核平台开发一种有效的编程方法已经成为并行软件研究的一个重要目标.在嵌入式多核平台上进行了OpenMP并行程序的有效的实施运行.针对嵌入式具有有限内存资源的特点,提出了通过扩展OpenMP自定义制导语句tiling来提高并行程序在嵌入式多核平台上的运行效率.扩展后的OpenMP并行程序支持循环分片,从而能够充分利用层...     

并行调试的可扩展性研究

并行调试在并行程序开发环境中非常重要。本文基于当前流行的并行计算机体系结构,为并行调试工具研究一种"一对多调试"组件,以此克服传统方法面对越来越大的MPP系统的不适应。     

运用变异测试的并行程序测试用例最小化算法

在并行程序测试中,测试输入和线程交互时序是影响并行错误检测的两个关键因素。以缩减并行错误检测的输入空间为目标,给出一种基于变异测试的测试用例最小化算法。首先对并行程序进行研究,选取与并行错误密切相关的9个变异算子,并以此为基础为待测程序生成多种变异体;采用JPF作为线程调度工具来执行测试用例,根据变异评分与平均时间成本对测试用例进行排序,在优化后的测试用例集中选取检测能力不重复的测试用例,从而得到面向并行错误检测的最小测试用例集。实验结果证明,该方法能有效减小测试用例集的规模,并大幅缩短运行时间,从而提高了并行程序的测试效率。     

多模式并行I/O测试程序Jetter的研究与实现

并行I/O系统有多种存取模式,它们有各自的存取特点和适用范围。为了获得不同模式下的系统性能,并行I/O测试中往往要综合使用多种微测试程序。这不仅要求用户深入了解并行I/O的特点,而且要求他们熟悉各种并行I/O微测试程序的输入与输出。提出并实现了一个并行I/O测试Jetter,它从接口类型、存取模式和进程－文件关系的角度划分了并行I/O接口,不仅能够测试I/O系统在上述模式下的性能,而且简化了测试工作。实际应用Jetter表明,并行I/O系统对不同模式的支持效果不同,最高差异可以达到两个数量级以上,这些测试结论有助于用户开发高质量的并行程序。     

一种基于并行对象的可视化描述

一、前言随着并行计算机应用的深入,人们对并行程序的开发需求不断增加。相对于串行程序而言,并行程序必须考虑同步、互斥、通信等问题,使得并行程序设计难度较大,要求科技研究人员具备编写高效的并行程序的能力,影响了并行机的应用水平。将并行机制引入面向对象语言构成并行面向对象语言已成为当前面向对象技术的一个重要研究方向。利用面向对象的特点来有效实现并行任务的划分、数据的分配、并行进程间的通信和同步,可以降低并行程序设计难度。我们设计的适用于MPP机或集群系统的并行C~++语言(SPC~++),是一个面向对象的并行程序设计语言,充分体现了C~++语言面向对象的程序设计思想和特点,将对象机制和并行机制有机结合起来,大大降低并行程序设计难度。SPC~++利用了C~++语言的对象封装性、函数重载、操作符重载等功能对对象消息传递模型进行抽象,简化消息函数的使用。     

一种并发程序依赖性分析方法

并发程序的依赖性分析是并发程序分析，理解，调试，测试和维护的重要手段，由于并发程序执行的不确定性，目前，尚有很多难点有待解决，针对Ada任务机制，首先提出了一种简洁，有效的并发程序表示方法－并发程序流图，然后讨论了由任务间同步引起的同步依赖和由访问共享变量引起的任务数据依赖，建立了并发程序依赖图，并在此基础上给出了一种有效的并发程序依赖性分析算法，得到一个比较精确的依赖性，较好地解决了并发程序依赖关系不可传递性问题。     

基于事件结构的并发程序可视化调试方法

在多核和并发技术得到广泛应用的今天,如何有效地调试并发程序,成为一个重要且亟待解决的研究课题.并发程序的不确定性及其行为的复杂性,使得传统的调试技术难以得到有效的应用;而软件维护场景中错误发现与错误调试过程的分离使得错误重现难以实现,面向缺陷报告的调试需求使得自动的错误定位技术难以应用,加剧了调试的困难.针对软件维护阶段由缺陷报告导向的程序调试场景,提出了可视化的并发程序调试方法.该方法能够根据缺陷报告中的信息对程序进行切片,缩小需要分析的代码范围;通过静态分析构造出程序行为的全局视图,帮助程序员发现隐含的程序执行路径;根据事件结构的语义简化程序行为视图,使得行为模型规模可控;根据图形中的分支,引导用户关注路径中的关键操作,从而更快地发现程序中的缺陷.与动态调试方法相比,该方法能够避免错误重现的代价.借助缺陷报告中的信息以及事件结构模型的特点,该方法能够尽量减少状态爆炸的发生.已开发出的交互式并发程序调试工具原型JESVis Debugger,初步实现了所提出的方法.     

Toward Automatic Concurrent Debugging Via Minimal Program Mutant Generation with AspectJ

Debugging is one of the most time-consuming activities in program design. Work on automatic debugging has received a great deal of attention and there are a number of symposiums dedicated to this field. Automatic debugging is usually invoked when a test fails in one situation, but succeeds in another. For example, a test fails in one version of the program (or scheduler), but succeeds in another. Automatic debugging searches for the smallest difference that causes the failure. This is very useful when working to identify and fix the root cause of the bug.A new testing method instruments concurrent programs with schedule-modifying instructions to reveal concurrent bugs. This method is designed to increase the probability of concurrent bugs (such as races, deadlocks) appearing. This paper discusses integrating this new testing technology with automatic debugging. Instead of just showing that a bug exists, we can pinpoint its location by finding the minimal set of instrumentations that reveal the bug.In addition to explaining a methodology for this integration, we show an AspectJ-based implementation. We discuss the implementation in detail as it both demonstrates the advantage of the adaptability of open source tools and how our specific change can be used for other testing tools.     

基于遗传编程的学生程序修正方法

学生程序的自动修正是程序设计类大规模网络公开课亟需解决的关键问题。结合学生程序在线评测的需求,提出了基于遗传编程的学生程序修正模型,设计并实现了基于Web的便于教师和学生使用的程序自动修正系统。基于测试用例集实现程序在线评测,对评测结果中满足自动修正条件的学生程序进行错误定位,在此基础上实现自动修正。应用结果表明,该系统可以有效管理、测试学生程序、并为学生修正含有缺陷的程序提供参考,减轻了教师的负担。     

通信下推系统的一种有界可达算法

Qadeer首次针对并发下推系统提出一种有界可达算法,通过限定上下文切换的次数使得算法可终止,可有效地分析过程间并发程序。但是并发下推系统以全局变量模拟同步,不适应于当前广泛使用的基于事件驱动的并发程序。针对通信下推系统,提出一种基于双重调度的有界可达算法,通过限定同步调度的次数,结合线程间的同步调度和线程内的路径调度解决通信下推系统的可达性问题,从而为事件驱动的过程间并发程序分析提供了算法基础。     

基于确定性重演的并发程序调试

并发程序执行的不确定性导致了程序错误的不可再现性,后续的执行无法再现前次执行的错误,这使得以反复执行程序,重复再现故障为核心的循环调试方法变得不再可用。本文提出了一种基于确定性重演的并发程序的调试方法,确定化并发程序的执行轨迹,重现程序初始运行的错误状态。     

一种新的并行Java程序的监护模型

提出了一种新的并行Java程序异常处理的监护模型。该模型针对并行Java程序异步信息传递方式进行异常处理。当并行Java程序的某个线程出现异常时,该线程的监护模块把检测到的异常情况的信息传递到其它线程的监护模块,每个线程根据当前事项与异常事项的向量时钟关系,对当前事项进行回滚或停止操作,以达到对并行Java程序的保护。过去一些并行程序的监护方案是在信息交换的基础上把并行程序结构化为许多原子行为,把多个并行异常当作单个异常进行处理,具有较大的局限性。提出的监护模型是从全局上对并行Java程序的异常情况进行处理,并指导每个线程根据自身情况作出相应反映。实验证明提出的新的并行Java程序监护模型具有较强的实际操作性,并能有效地保护并行Java程序。     

A formal semantics for debugging synchronous message passing-based concurrent programs

In this paper, we propose a semantic framework to debug synchronous message passing-based con- current programs, which are increasingly useful as parallel computing and distributed systems become more and more pervasive. We first design a concurrent programming language model to uniformly represent exist- ing concurrent programming languages. Compared to sequential programming languages, this model contains communication statements, i.e., sending and receiving statements, and a concurrent structure to represent com- munication and concurrency. We then propose a debugging process consisting of a tracing and a locating procedure. The tracing procedure re-executes a program with a failed test case and uses specially designed data structures to collect useful execution information for locating bugs. We provide for the tracing procedure a struc- tural operational semantics to represent synchronous communication and concurrency. The locating procedure backward locates the ill-designed statement by using information obtained in the tracing procedure, generates a fix equation, and tries to fix the bug by solving the fix equation. We also propose a structural operational semantics for the locating procedure. We supply two examples to test our proposed operational semantics.     

基于Adaboost模型的并发程序数据竞争语句级检测

针对并发程序数据竞争检测时准确率低和开销大的问题,基于Adaboost模型设计并发程序数据竞争语句级检测方法。对多线程并发程序进行插桩操作,记录指令的相关内存信息,并对提取出的指令集做语句级转化处理,利用语句对相关属性特征构建并发程序Adaboost数据竞争检测模型,实现多线程程序数据竞争检测工具ADR。实验结果表明,相比于Eraser、Djit+和Thread Sanitizer工具,ADR能够在降低时间及内存开销的同时,有效提高分类准确率,验证了所提方法的有效性。