学位论文 > 优秀研究生学位论文题录展示

消息传递并行程序的测试及其通信环境

作　者: 梁煜
导　师: 韩承德
学　校: 中国科学院研究生院（计算技术研究所）
专　业: 计算机组织与系统结构
关键词: 并行程序消息传递事件同步序列测试测试覆盖率
分类号: TP311.11
类　型: 博士论文
年　份: 1998年
下　载: 252次
引　用: 0次
阅　读: 论文下载

内容摘要

测试是软件开发中一个不可缺少的重要阶段。本文主要探讨有关并行程序测试的规律和方法。消息传递和共享内存是两种常用的并行编程模型，在这里我们将以消息传递并行程序为主要研究对象。出于可移植性和可伸缩性方面的考虑，目前的分布式应用系统大多建立在通用的消息传递环境之上而独立于具体物理运行环境(计算机、网络和操作系统等)。为了阐明消息传递并行程序的工作机制，本文对当前比较有代表性的消息传递编程环境如MPI(Message Passing Interface)、PVM(Parallel Virtual Machine)和BLACS(Basic Linear Algebra Communication Subprograms)等的功能、通信效率等进行了细致的研究和分析。并行程序中的差错可以分为控制流差错和时序差错。根据其性质，时序差错又可以进一步分为时序逻辑差错和时序性能差错。由于这三类差错之间不存在直接的因果关系，因此并行程序测试可以划分成三个相对独立的步骤——控制流测试、时序逻辑测试和时序性能测试。针对控制流测试，本文以我们自行开发的ParCT(Parallel C-language Testing tools)为例介绍了并行程序控制流测试的实现方法、关键技术和主要功能。此工具具有易使用、可移植性强、C语言与FORTRAN语言混编、运行记录所占硬盘空间较小、测试工具对被测对象的环境及性能影响较小等优点。建模是实现测试的第一步。本文采用了事件驱动技术来描述并行程序的运行状态和路线。事件表示能够被外界环境所察觉的、即时的和同步的操作(occurrence)，在时序测试中事件被限定为与通信有关的操作并被称为同步事件(SYN-event)。本文中有关消息传递并行程序时序测试的研究均建立在粗粒度同步序列模型的基础上，其最大特点是以消息的一次发-收操作对偶作为原同步事件，亦即测试系统所能感知的最小单位。面向共享内存并行程序的同步序列模型是以对共享变量的读写作为原同步事件。时序逻辑测试的目的在于判别程序是否按正确的数据相关性所要求的时序来运行，关于并行程序时序逻辑测试本文主要讨论了同步序

全文目录

致谢  3-5
摘要  5-7
Abstract  7-14
第一章前言  14-18
  1.1 问题的提出  14-15
  1.2 关于本文  15-18
    1.2.1 本文的主要工作内容  15-17
    1.2.2 本文的组织结构  17-18
第二章并行软件开发及其测试  18-40
  2.1 并行程序编程  18-25
    2.1.1 计算问题的分类  18-19
    2.1.2 并行软件开发所面临的主要技术问题  19-21
    2.1.3 并行软件的开发流程  21-23
    2.1.4 并行编程模型  23
    2.1.5 并行程序的结构  23-25
  2.2 并行软件通信环境  25-26
  2.3 并行程序测试  26-40
    2.3.1 软件测试中的基本概念  26-28
    2.3.2 事件和程序的正确性判别策略  28-30
    2.3.3 并行程序中差错的分类  30-32
    2.3.4 面向并行程序进程内部差错的控制流测试  32-33
    2.3.5 消息传递并行程序的时序逻辑测试  33-37
    2.3.6 消息传递并行程序的时序性能测试  37
    2.3.7 共享内存并行程序的时序测试  37-40
第三章面向消息传递模型并行计算的通信环境  40-60
  3.1 PVM通信环境  40-43
    3.1.1 PVM的主要功能和特点  40-41
    3.1.2 PVM的通信性能  41-43
  3.2 MPI通信环境  43-46
    3.2.1 MPI的基本概念  44-45
    3.2.2 MPI的不同实现  45-46
  3.3 PVM和MPI比较  46-49
    3.3.1 PVM和MPI在功能方面的差异  46-47
    3.3.2 MPI1.1与PVM3.3.12的性能比较  47-49
  3.4 BLACS——面向线性代数计算的消息传递环境  49-60
    3.4.1 ScaLAPACK系统简介  49-50
    3.4.2 PVM BLACS的概念和性质  50-52
    3.4.3 BLACS中通信的拓扑结构  52-54
    3.4.4 充分发挥PVM BLACS在Hitachi SR2201上的使用效率  54-56
    3.4.5 根据Hitachi SR2201的软硬件环境改进PVM BLACS  56-57
    3.4.6 对PVM BLACS的小结  57-60
第四章并行程序的控制流测试  60-78
  4.1 关于ParCT的背景知识  60-63
    4.1.1 ParCT软件测试系统中的主要概念、术语  60-62
    4.1.2 ParCT的主要特点、功能  62-63
  4.2 ParCT的工作原理  63-68
    4.2.1 ParCT的工作机制  63-66
    4.2.2 ParCT的操作流程  66-68
  4.3 将来需要改进的地方  68-73
    4.3.1 为ParCT增配并行实时监控机制  69
    4.3.2 改进ParCT使其支持多线程  69-70
    4.3.3 测试用例的自动产生  70-73
  4.4 测试实验结果分析  73-78
    4.4.1 对BLACS的测试结果分析  73-75
    4.4.2 对PBLAS的测试结果分析  75-77
    4.4.3 小结  77-78
第五章消息传递并行程序的时序逻辑测试  78-102
  5.1 消息传递并行程序的时序特性  78-79
  5.2 消息传递并行程序的时序模型  79-84
    5.2.1 LOTOS：时序规范语言  79-81
    5.2.2 同步序列模型  81-84
  5.3 并行程序测试模型  84-94
    5.3.1 同步序列的正确性判断原则  84-85
    5.3.2 消息传递并行程序中的同步事件的本质  85-87
    5.3.3 同步序列规范的形式描述  87-89
    5.3.4 线性同步和非线性同步并行程序  89-90
    5.3.5 两个比较有代表性的聚类操作——广播和归并  90-94
  5.4 并行程序时序测试方法  94-102
    5.4.1 常见的并行程序时序测试方法  94-96
    5.4.2 层次事件测试策略  96-102
第六章消息传递并行程序的时序性能测试和测试覆盖率  102-122
  6.1 并行程序测试覆盖率计算的通用公式  102-104
  6.2 聚类操作的有效同步序列数的计算方法  104-111
    6.2.1 树型聚类操作的有效序列数的通用计算公式  104-107
    6.2.2 完全树型拓扑聚类操作的|Valid(P,X)|的计算公式  107-111
  6.3 消息传递并行应用程序的有效同步序列数的分析  111-116
    6.3.1 高斯消去法  111-113
    6.3.2 5点差分迭代法  113-116
    6.3.3 消息传递并行程序的有效同步序列数  116
  6.4 并行程序的测度(testability)  116-117
  6.5 消息传递并行程序时序测试中亟待解决的问题  117-119
    6.5.1 消息传递并行程序中的死锁  117-118
    6.5.2 统一时钟  118
    6.5.3 减少插装负作用  118-119
  6.6 小结  119-122
第七章结束语  122-126
  7.1 本文的主要工作  122-124
  7.2 今后的任务  124-126
参考文献  126-136
附录A 共享内存并行程序时序测试  136-152
  A.1 共享内存并行程序的时序模型  137-138
  A.2 共享内存并行程序的测试模型  138-143
    A.2.1 同步序列的合法性分析  138
    A.2.2 根据控制流和消息流进行时序的合法性分析  138-140
    A.2.3 根据数据相关性进行同步序列的有效性分析  140-141
    A.2.4 时空图(Space-time Diagram)  141-143
  A.3 共享内存并行程序的测试覆盖率  143-150
    A.3.1 共享内存并行程序的时序测试覆盖率的计算公式  143
    A.3.2 共享内存并行程序有效同步序列数的通用计算方法  143-144
    A.3.3 高斯消去法的有效同步序列数  144-148
    A.3.4 有限个处理器条件下的有效同步序列数  148-150
  A.4 消息传递和共享内存并行程序测试规模的比较  150-152
攻读博士学位期间的主要工作成果  152-156
作者简历  156

消息传递并行程序的测试及其通信环境

内容摘要

全文目录

相似论文