并发系统的并行计算及性能分析

论文摘要

随着并发系统在诸多领域的广泛应用,如何对其性能分析以确保系统的质量,这已成为开发人员及使用者特别关注的问题。在软件工程的早期阶段,对系统建立模型并做性能分析,可以及时发现设计错误,减少后期修改及测试的费用。人们提出了许多形式化建模和性能分析方法,主要有:排队论、随机Petri网(SPN)、随机进程代数(SPA)。这些方法都是基于马尔可夫过程,因此会遇到状态空间爆炸问题。且排队论无法合理描述并发系统的同步、资源共享等现象。由于随机Petri网(SPN)对并发系统具有很强的描述、分析能力,备受人们的青睐。尽管人们提出了许多减小状态空间的技术,然而仍旧存在状态空间爆炸问题。为此,本文借助并行计算,通过并行求解常微分方程组,提出一种大规模并发系统建模及性能分析的方法。主要工作如下:(1)建模。本文引入Petri网描述并发系统,将其连续化,用常微分方程组对系统建模。这样不仅避免了状态爆炸,而且直接利用MATLAB,通过求解方程组就能定量地分析系统的性能。(2)并行计算。当实际系统规模变大时,状态个数将很多,MATLAB显然不够用。针对本文这种具有特殊结构的方程组,给出Petri网到超图的转换规则,根据超图剖分的结果将方程组分块,进而借助软件SUNDIALS并行求解,达到了负载平衡最优化、通讯最小化,解决了并行计算的瓶颈问题。(3)性能分析。结合方程组的解,给出系统性能分析方法及优化性能的建议,并与随机Petri网性能分析的方法及复杂度比较证明。最后通过典型实例具体分析了并行算法的复杂度、系统的性能,进而说明本文方法的优越性。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究的背景及意义
• 1.2 国内外研究现状
• 1.3 主要研究内容
• 1.4 论文组织结构
• 第二章 用Petri网描述并发系统
• 2.1 基本概念
• 2.2 消息传递规则
• 2.3 资源共享规则
• 第三章 建立并发系统的常微分方程模型
• 3.1 连续Petri网
• 3.2 建立常微分方程模型
• 第四章 并行计算微分方程组
• 4.1 Petri网到超图的转换
• 4.1.1 超图的基本概念
• 4.1.2 转换规则
• 4.1.3 常见Petri网对应的超图
• 4.1.4 补充说明
• 4.1.5 超图剖分
• 4.2 并行计算
• 4.2.1 求解的微分方程类型
• 4.2.2 并行算法
• 4.2.3 算法复杂度分析
• 第五章 用常微分方程组分析系统性能
• 5.1 用随机Petri网（SPN）分析系统性能
• 5.2 随机Petri网（SPN）的平均标记数=连续Petri网（CPN）的状态度量值
• 5.3 性能度量
• 5.4 优化性能
• 5.5 复杂度分析
• 5.5.1 连续Petri网（CPN）方法的计算复杂度
• 5.5.2 随机Petri网（SPN）方法的计算复杂度
• 第六章 实例分析
• 6.1 哲学家进餐问题
• 6.1.1 建立Petri网及微分方程模型
• 6.1.2 Petri网转换为超图
• 6.1.3 哲学家问题的超图剖分
• 6.1.4 方程重新分组
• 6.1.5 并行计算
• 6.1.6 算法复杂度分析
• 6.2 远程医疗系统（RHIS）
• 6.2.1 建立Petri网及微分方程模型
• 6.2.2 Petri网转换为超图
• 6.2.3 远程医疗系统的超图剖分
• 6.2.4 方程重新分组
• 6.2.5 并行计算
• 6.2.6 系统性能分析
• 6.2.7 优化系统
• 总结与展望
• 参考文献
• 致谢
• 攻读学位期间的研究成果