（计算机应用技术专业论文）并行系统性能评估技术研究.pdf

r e s e a r c h o n p e r f o r m a n c e e v a l u a t i o n f o r p a r a l l e l s y s t e m s ab s t r a c t p e r f o r m a n c e e v a l u a t i o n i s v e ry i m p o rt a n t t o t h e d e s i g n , c o n s t r u c t a n d u s e o f p a r a l l e l s y s t e m s . i n o r d e r t o d o r e s e a r c h o n t h e t e c h n o l o g y , t h i s p a p e r fi r s t l y e x p o u n d s k in d s o f i s s u e s t h a t m u s t b e c o n s i d e r e d w h e n e v a l u a t e a p a r a l l e l s y s t e m s p e r f o r m a n c e , d i s c u s s e s a n d c o m p a r e s t h o s e 帅i c a l t e c h n o l o g y u s e d i n p e r f o r m a n c e e v a l u a t i o n a n d s u r v e y s t h o s e o n g o i n g r e s e a r c h w o r k i n t h i s fi e l d . a n e w k i n d o f c l u s t e r t h a t i s n o t f o r s p e c i a l u s e i s n o w a n i m p o r t a n t r e s e a r c h o r i e n t a t i o n a n d h a s a b r i g h t f u t u r e . f o r t h i s h e t e r o g e n e o u s a n d d y n a m i c p a r a l l e l s y s t e m , t h i s p a p e r p r o p o s e s a s i m u l a t i o n s y s t e m t o e v a l u a t e i t s p e r f o r m a n c e . t h i s s i m u l a t i o n s y s t e m u s e s a s m a l l - s c a l e h o s t c l u s t e r t o s i m u l a t e a l a r g e r s c a l e t a r g e t c l u s t e r . i t h a s f o l l o w i n g f e a t u r e s : f i r s t , a d o p t s a n e x e c u t a b l e e d i t i n g t e c h n i q u e f o r b e n c h m a r k s ; s e c o n d , s im u l a t e s t h e t a r g e t n e t w o r k e n v i r o n m e n t b y a c e n t r a l l y c o n t r o l l e d m a t r i x ; t h i r d , u s e s fl e x i b l e p v m t o a s s i s t c o n s t r u c t i n g t h e h o s t c l u s t e r a n d a s t h e u n d e r l y i n g c o m m u n i c a t i o n l a y e r . c o m p a r e d w it h c u r r e n t s i m u l a t o r s f o r c l u s t e r s , t h i s s i m u l a t i o n s y s t e m c a n s im u l a t e t h i s n e w k i n d t a r g e t c l u s t e r c o m p u t i n g e n v i r o n m e n t b e t t e r a n d h a s b e t t e r p o rt a b i l i t y k e y w o r d s : p a r a l l e l s y s t e m , p e r f o r m a n c e e v a l u a t i o n , s i m u l a t i o n , c lu s t e r 第一章引言 第一章引言 随着计算机科学的发展， 计算机系统的功能变得越来越强大。 根据不同的应 用需求， 制造商们设计制造了从微型计算机到超级计算机的不同的系统。 这些系 统有不同的体系结构。 根据指令流和数据流的观点， 不同的计算机体系结构可以 被分为四大类: s i s d , s 工 m d , m 工 m d ， 和m 工 s d 。 在进行通常意义的计算时， 这四种机 器模型中m i m d 使用得最为广泛。 m i m d 并行计算机可以被进一步划分为基于共享 内存的多处理器和基于消息传递的多计算机。 并行计算的根本意义是将两个或多个计算单元连接起来，共同解决一些计算 问题。 从2 0 世纪9 0 年代以来， 昂贵而特制的并行超级计算机向工作站网络转换 的趋势越来越强。 高性能工作站和网络部件的商品化成为促成这种转换的驱动因 素。 技术的发展使计算机 ( p c 机， 工作站或s m p ) 网络所构成的集群成为并行处 理的理想工具，从而导致了低价商品化超级计算的出现。 这种趋势有许多优势， 包括可以按照给定的任务建造平台， 以适应较大型的应用程序和工作负荷。 并行 应用的许多工具和命令的标准化是使集群进入现实应用的一个重要因素， 这些标 准的范例包括消息传递库m p i 和数据并行语言h p f . 按照构建集群的方式可以将集群系统分成专用集群和非专用集群两大类。专 用集群一般是在企业或研究机构内部专门 使用。 而非专用集群是在目 前网络的开 放环境下，计算资源自由组合构成的集群系统。 目 前，国际上正在形成一种计算资源的买卖市场，以 刺激资源拥有者加入网 上集群。 此外， 由 于当前网络通信速度和质量的瓶颈所限以及由于通信竞争造成 的网络不确定性的存在，对非专用集群技术提出了更高的要求，如对进程迁移、 负载平衡等技术的需求。 但此类系统最为贴近普通用户， 可以充分利用网上无穷 无尽的资源， 而组建投资几乎可忽略不计. 可以 预见， 随着网络瓶颈问 题的缓解， 非专用集群必然是极有发展前途的一种计算形式。 针对每种并行系统，我们需要知道:系统的性能如何，系统运行的方式是什 么，评估其性能的标准有哪些，以 及要得到系统的性能指数应当 使用何种技术。 回答这些问题正是性能评估的目的. 性能评估技术对于并行系统的设计、 制造和 使用有非常重要的意义. 自 从 1 9 6 5年性能评估技术诞生以 后，这个领域的研究发生了巨大的进步。 它己经变成一门独立于其他学科的截然不同的学科。 性能评估可以被定义成: 对 被研究的系统给予一个能反映其性能的量值。 性能包含了许多方面。下面是一些必须被考虑的因素:功能， 可靠性， 速度， 第一章引台 和代价。 首先， 功能是最重要的。 所有成功的系统都必须能完成设计者们要它完 成的工作。第二， 这个系统必须尽可能的可靠。 给这个系统一个服务请求， 存在 两种可能结果: 系统正确或不正确地完成这个服务请求。 如果失败了， 那么需要 研究这种错误发生的概率。 如果这个概率太高， 不能满足设计要求， 那么这个系 统就应当被重新设计或者改进直到错误发生的概率降低到某个合理的水平。第 三， 如果系统正确地完成了服务请求， 那么它如何快速和有效地完成任务变得很 重要 ( 速度因素) 。由于功能和可靠性是所有设计者们在设计的初期都己经考虑 和解决了的两个基本问题， 在性能评估研究中速度变成最经常研究的领域。 速度 通常反映为响应时间和吞吐率; 而效率则通常反映为利用率。 第四， 一个系统要 完成它的服务首先需要花费一定的成本来设计和实现该系统。 具体的说， “ 代价” 就是要考虑如何用最低的成本来设计和实现该系统。 要评估一个系统的性能或者要比较几个系统的性能，首先必须选择一些标 准。 这些标准被称为基准。 不同的基准可能导致完全不同的性能指标。 选择合适 的基准来公正地评估系统的性能并不是件容易的事。 性能研究的开始首先要了解 选择的基准， 它们之间的关系以 及它们对性能参数的影响。 然后， 选择合适的负 载同样很重要。 一个系统常常被设计成在特定的环境和特定的负载下工作， 所以 研究其性能应当要考虑到负载。 在选择了合适的基准和负载之后，必须要考虑应当使用哪种或者哪些技术。 性能评估中常常采用三种技术， 它们是测量， 建模分析和仿真。 所有这些技术在 性能评估中有同样重要的地位， 而且各有其优缺点。 通过不同的技术得到的结果 的精度往往很不一样。 要选择某种或者某些技术来评估一个系统， 必须考虑许多 因素。 必须清楚想要得到什么结果和在什么阶段使用何种技术。 例如， 在设计的 初期阶段， 此时系统还没有被制造出来， 测量很明显是不可能的， 然而， 一个简 单的分析模型是可行的。随着设计的进行，可以得到越来越多的系统细节信息。 在这个阶段， 可以使用仿真或者更复杂的建模分析技术。 最后， 当系统设计完成 和一个真正的系统被制造出来后， 进行测量成为可能。 为了使评估结果对于系统 用户更可信，常常是这些技术被同时采用。 为了对并行系统的性能评估技术进行进一步的研究， 本文在第二章和第三章 试图阐述对并行系统进行性能分析必须考虑的各种问 题， 评论和比较性能评估中 应用的典型技术， 以 及调查这个领域中 现在进行的工作。 在本文的第四章针对新 兴的具有异构和动态特征的非专用集群并行系统， 提出了对其进行性能评估的一 个仿真系统的设计。 这个系统采用一个小规模的宿主集群来仿真更大规模的目 标 非专用集群。 这个系统的特征有: 第一， 采用了针对作为基准程序的可执行程序 的直接编辑技术; 第二， 对网络环境采取集中式矩阵模拟; 第三， 采用灵活性非 第一章引台 常好的p v m 技术来进行宿主集群的构建以及作为底层通信支持。 通过采用这些技 术， 这个系统和现有的一些集群仿真系统相比， 能够对目 标非专用集群并行计算 环境进行更好的模拟，并且能够得到更好的可移植性。 第二章并行系统性能评估的 基本问题 第二章并行系统性能评估的基本问题 2 . 1 建模 为了研究一个系统，第一步必须构造一个能够表征这个系统的模型。然后研 究这个系统的行为和通过使用仿真或者理论分析解答这个模型来了解这个系统。 这个方法适用于自 然科学和社会科学的所有分支。性能评估也不例外。 系统的一个模型可以非正式地被定义为“ 一些属性以及控制着这些属性相互 作用的规则的集合”川 。 构造一个对特定问题真正有效的好模型需要许多仔细的考虑和艰苦的工作。 一个好的模型至少有两个特点。 第一， 它必须能很好的描述一个系统的行为， 并 且应当尽可能地精确。 第二， 它应当尽可能地简单以便解决。 第一个特点需要这 个模型包含所有定义行为的必要细节。 第二个特点需要这个模型排除尽可能多的 参数。 这两个特点互相矛盾。 这是所有研究者们面对的困境。 包含太多的参数可 以 使模型变得精确然而同时可能过于复杂或者甚至不可解. 解一个过度复杂的模 型所需的代价太高昂， 而一个不可解的模型即 便很精确但对于问题的 研究毫无用 处。因此，应当非常注意地选择参数，并且进行合理的折衷。 在开始工作前，必须清楚的认识:性能研究的目的，感兴趣的是什么结果， 以及研究的是系统的哪些属性。 因此， 对问题的仔细考察和全面理解是非常必要 的。 一个系统的模型就好比 一个公路系统的地图。 模型仅仅表示系统，它不是系 统本身， 它是通过各种各样的假设和不同级别的抽象后得到的。 假设和抽象必须 对应于要研究的系统属性， 着重于那些有用的特点而忽略其他。 一个系统的行为 特征通过参数可以描述。 然而， 不是所有的参数对行为有同样的作用。 所以有必 要首先列出所有的参数， 然后仔细检查和比较它们， 引入那些对系统行为有最重 要影响的来研究。这就是我们所说的抽象。这个过程可以产生一个这样的模型， 它只包含那些刚好描述我们所感兴趣的行为的必要的参数， 而排除了那些无关紧 要的。 一个模型完成以 后， 通常需要被验证和修改以免它的结果和现实世界相去甚 远。 c o l l i e r 概括了 建模过程必须遵从的四 个步骤: 1 、决定要寻找的是什么答案; 2 ,精简在现实世界中问题的复杂性，除去无关的事务以及对无法控制的部 第_章并行系统性能评估的幕本问题 分进行近似处理; 3 、将问题的精华翻译成正式定义的系统，以便进行深入推论; 4 、将推论在现实世界中进行测试，看看该模型是否将问题阐述清楚或者是 否实用。 2 . 2 选择测量指标 为了研究系统的性能或者为了 某种目的要比 较不同的系统， 我们必须先选择 一些标准。 这些标准在性能评估中通常被称作指标。 不同的情况需要不同的指标 集合。 因此， 选择指标和问题高度相关。 进一步说， 同样的指标在不同的情况下 有不同的重要性。例如，响应时间是一个经常使用的指标， 它反映了一个系统完 成特定服务的快慢程度。 然而， 它在一个实时控制系统中比在一个网络系统中更 受重视。后者往往对诸如吞吐量等指标更有兴趣。 在这方面没有标准的指标集合被定义， 并且没有标准的技术被应用。因为对 于不同的问题它的变化太大. 下面讨论选择合适的指标应遵循的一些原则和通常的过程。 所有系统设计来都是为了提供服务的。 对于向系统提交的一个特定的服务请 求，有三种可能的结果。 1 、系统正确地完成服务; 2 、系统完成了服务，但有错误; 3 、系统运行服务失败; 在对可能的结果进行分类后， 接下来的工作变得容易些。由于每种情况需要 单独的指标集，它们可以被分开来考虑。 对第一种情况，性能可以被用 “ 时间一速率一资源” 指标来测量，它表示 了系统完成服务所用的时间，以何种速度，以及需要的资源。在真实的例子中， 他们可以是响应时间，吞吐量和利用率。这些指标在性能研究中被广泛使用。 对第二种情况，发生错误的概率应当被测量. 在许多实例中，需要对错误进 行分类，并且单独地研究每种类型。 对最后一种情况， 失败的 概率也是我们所感兴趣的。 一个系统常常由 几个部 分构成。 有时确定失败的根源是很有用的。 如果需要进行进一步的检测， 则底层 的部分 ( 软件和硬件)可以被建模和研究。例如，如果失败是因为c p u ，一个简 单的c p u 模型可以被构建， 使用 “ 开” 和 “ 关” 两种状态。 如果我们假定失败时 第二章并行系统性能评估的基本问题 间和纠正时间各自 遵从参数为 入和 “的指数分布， 那么这个随机过程就是一个 马尔可夫链。然后就可以使用许多已经发展得很好的技术来进一步研究。 针对一些候选的指标， 应当进一步考虑下面的三个特征: 低可变性， 无冗余， 以及完备性 。高可变性需要进一步努力来得到某种程度 的统计置信水平 ( s t a t i s t i c a l c o n f i d e n c e ) 。检查冗余性可以减少指标的数目;选择一个来代 表那些有同样效果的。 例如， 在一个网络路由器系统中 ( 从源节点接收到数据包 并将它们传送给目的节点) ，系统中数据包的平均数目可以通过著名的利特尔法 则 ( l i t t l e s l a w )得到: 万=几z 此处，兄 是平均到达速率，f 是平均等待时间。因此，在万 和z 这两个指标 之间， 选择一个就够了。 完备性就很明显了， 所有被选中的指标的集合应该能够 描述我们感兴趣的和性能相关的所有可能的结果。 2 . 3性能评估技术 有许多技术可以 被用于性能评估。 通常， 这些技术可以被分为三类:测量， 仿真和建模分析【 .; 1 。 有些科学家把仿真和建模分析合并为一类， 称作模拟技术。 这是因为不管我们采用仿真或者建模分析， 都必须首先为被研究的系统构造一个 模型。 仿真被看作是解决复杂模型的有效方法。 这种分类方法是基于测量必须在 现实系统上进行的事实， 也就是说， 被评估的系统必须存在而且可用， 而建模技 术就没有这个要求.为了讨论的方便，我们采用前面的分类方法。 这三种技术的每一种都有许多类型。例如， 测量有软件，硬件和两种混合的 测量;建模分析包含排队网络，p e t r i 网等;以及仿真有模仿， m o n t e c a r l o 仿 真， 踪迹驱动仿真， 执行驱动仿真， 离散事件仿真等。 选择其中合适的一种来研 究问题， 需要许多认真的考虑。 下面， 我们讨论如何选择一个适合于解决某个问 题的技术。 在进行性能评估之前， 考虑下面的因素对于选择合适的技术很有帮助:所处 阶段，精确度和代价。可能最重要的因素就是阶段了。换句话说，在设计的哪个 阶段进行性能评估，因为在不同的阶段需要不同的技术和精确度。 测量技术，基于用软件或 ( 和)硬件监控器直接测量被研究的系统。因此， 此时真实的系统必须可用。所以，当系统在设计阶段还没有被建造出来的时候， 这种技术是不可能被使用的。 因此测量是针对于性能调整( t u n i n g ) 。 仿真和建模 分析都是基于抽象模型而非真实系统。 因为在系统被建造出来之前， 在适当的假 设的基础上， 基于对设计特征的本质的抽象， 模型就可以被构造出来。因此，这 第二章并行系 统性能评估的 幕本问 题 两项技术都是针对性能预测的 ( 虽然有时也被用于性能调整) 。必须指出的是， 在设计周期的早期阶段进行性能预测不仅是有用， 而且是必要的。 因为这将有助 于发现潜在的设计错误以便尽可能早地进行修正， 这样就可以避免在系统己经被 实现后进行改进和重新设计所要付出的昂贵代价。 仿真和建模分析可以在整个设计周期中被使用，而不仅仅是在早期。通常在 设计成熟和更多的系统的细节特征被获得的时候，可以构建出更加精确的模型。 除此之外， 建模分析技术有时在设计的后期是不适合的。 这是因为那个时候模型 常常包含了太多的细节以至于要解决的代价太高， 或者在某些情况下是数学不可 解的。 因为仿真和建模分析都使用了模型，这需要简化和假设， 所以只是对现实问 题的近似表示， 会引入近似错误。 在建模分析技术中尤其如此。 为了使模型数学 可解， 需要高度的抽象和更多的假设。 例如， 在许多建模分析技术中为了考虑时 间分布只允许存在指数分布。当使用仿真的时候， 就没有这个限制。 许多复杂的 非指数分布可以很容易地被使用。 简单地说， 仿真允许更复杂和详细的模型， 这 样可以得到更精确的解决方法 ( s o l u t i o n s ) . 因为测量直接在真实系统上运行， 似乎它在这三种技术中可以得到最精确的 结果。然而事实上常常不是如此。测量中使用的基本技术是使用测试设备 ( i n s t r u m e n t a t i o n ) ， 这将引入执行开销并且可能影响系统的动态行为。 这被称 为设备扰动。 另外测量的精确度也基于测量时间和所采用的负载。 所以， 测量技 术可以提供非常精确的数据也能提供非常不精确的数据， 这都取决于对上面这些 因素的处理。 对于代价来说，由于测量需要额外设备，它是代价最高的方法。建模分析什 么都不需要， 所以它是最便宜的方法。 仿真在这两者之间。 概括地说， 建模分析 代价最低，精确度最低，最好被用于设计初期;仿真，有更高的代价和精确度， 可以在任何阶段中使用; 而测量， 有最高的代价和不定的精确度， 只能在系统建 成之后被使用。 值得指出的是这些技术通常应当被一起使用， 同时或者连续的使用来在任何 可能的时间评估系统。 例如如果输入和参数根据以前的测量结果来决定， 那么仿 真和建模分析的结果会更加可信;并且建模分析可以用仿真来进行验证。 第三章并行系统性能评估技术 第三章并行系统性能评估技术 性能评估中采用的技术通常可以分为三类:测量，建模分析和仿真。 技术的每一种都有许多类型。 例如， 测量有软件， 硬件和两种混合的测量 这三种 :建模 分析包含排队网络，p e t r i 网等;以 及仿真有模仿， m o n t e c a r l o 仿真，踪迹驱 动仿真，执行驱动仿真，离散事件仿真等。 3 . 1 测量 测量是用软件或 ( 和) 硬件监控器来直接测量被研究的系统。它的目的是去 寻找那些我们感兴趣的信息， 它们可以以后被用来改进系统性能。 这个过程常被 称为性能调整。 例如， 通过监控， 可以找到软件中经常被执行的部分。 优化这个 部分可以改进整个程序的性能。 同样地可以得到系统中的资源利用情况， 以便用 来确定性能的瓶颈所在。 这在系统调整的时候是很有用的。 就象前面所说的， 测 量所得的数据在模拟一个系统或者描述负载的时候很有用。 测量同时也是验证一 个系统模型的方法。 监控器是用来观察系统行为的工具。通常来说，一个监控器执行三个任务: 数据获取， 数据分析， 和结果输出。 监控器记录的数据包括硬件相关的数据 ( 例 如程序运行过程中的处理器使用，消息等待时间)和软件数据 ( 例如处理时间， 缓存使用，负载平衡开支) 。监控器传统地被分为软件监控器，硬件监控器和混 合监控器。软件监控器由 检测系统或者指令集状态的程序构成，称为软件探测， 能够进行事件检测。 硬件监控器是电子设备， 它被连接于特定的系统点，以便检 测信号来描述要观察的现象。 混合监控器就是软件和硬件的结合。 每种监控器有 它自己的优点和缺点. 选择一个合适的监控器要考虑许多不同的方面， 例如花费， 额外开销，精确性，有效性， 信息级别等等。 下面我们讨论一些所有监控器设计者们必须仔细考虑的问题和列出一些常 用的术语。 一个事件是一个系统状态的变化。 例如处理上下文切换， 在磁盘上进行查找 的开始，以及一个包的到达。一个踪迹 ( t r a c e )是一个事件日志，通常包括事 件时间，事件类型，和其他一些和事件相关的重要参数。 额外开销 ( o v e r h e a d )是设计一个监控器的关键问题。 所有监控器或多或少 都要消耗系统资源， 或者消耗被测系统的能量。 例如， 测量的数据可能要被记录 在辅助存储器上。并且一个软件监控器需要一些指令来在每次 c p u被激活时执 第三章并行系统性能评估技术 行， 因此要消耗c p u 时间。 这种对系统资源的消耗被称为额外开销。 额外开销依 赖于不同的环境， 有时候很大， 这时就会大大地影响到测量结果的精确性。 因此， 把额外开销减到最小是监控器设计的一个目的。 通常有两种方法来激活一个监控器。 一是使用事件。 当一个事件发生的时候， 监控器被激活来捕捉系统状态数据。这给运行的程序留下了完整的踪迹。因此， 这种技术也叫跟踪， 而且使用这种技术的监控器被称做事件驱动监控器。 另一种 方法是使用记时器。 监控器通过时钟中断来激活。 这种技术叫做采样。 跟踪的主 要问题是它会产生太多的数据。这在包含许多处理器的并行系统中显得特别严 重， 提供的大多数数据都是不必要的， 这使得用户很难专注于和性能相关的少量 数据。因此，减少数据和过滤掉所有不必要的数据对于测量工具来说特别重要。 因为它们的重要性，这里需要提起两个监控器:程序监控器和记帐日志。 这 两种监控器在测量性能的时候经常被用到。记帐日志常常是系统软件的一部分。 虽然主要目的不是为了监控， 它们提供了关于系统使用和性能的有用信息， 因此 被当作软件监控器来使用。 主要的优点是它们是内建的， 不需要花费额外的努力 去开发。主要的缺点是它们是通用的，没有为专门的测量提供信息。 程序执行监控器 ( 也以程序优化器或者程序执行分析器被世人所知)是测量 程序执行的特定细节的工具。 通过精确描述程序在何处花费了时间， 找到程序中 执行的确切路径， 确走哪个子程序被调用等等， 使得它们对改 进程序性能很有帮 助。另外，调试也是它的一个重要目的。 象前面所说的，监控器可以按许多方法被分类。例如，我们可以根据实现， 激发机制，功能等等来进行分类。我们这里着重于监控并行系统。 上面所描述的问题在监控并行程序的时候同样存在。除此以外，又产生了几 个新的问题。 另外， 在并行系统中我们感兴趣和应当测量的性能数据也是不同的。 例如， “ 全局”时钟的选择以便来影响时间戳操作，以及监控过程可能对我们要 测量的系统的动态行为有显著的影响或者干扰。 对于指令干扰来说，干扰的主要来源是执行了额外的指令。然而，其余的干 扰包括: 编译优化失效，内存冲突和额外的操作系统开销。 总的来说， 这些干扰 可以增加被测系统的运行时间， 改变内存访问模式， 事件重新排序，以及寄存器 联锁 ( i n t e r l o c k )的僵局。 在每种监控实验都存在干扰，而且是无法完全去除的，所以使干扰的影响最 小化是进行实验时的关键努力。 千扰无疑是主要问 题， 然而在设计监控并行程序 的工具时还有另外几个问 题必须考虑。 在计算系统中许多并行编程模式， 所以监 控工具必须高度灵活。 建造多处理器系统的主要动机是用较小的代价来有效地改进系统性能。对一 第三章并行系统性能评估技术 个并行体系结构， 我们编程时主要致力于如何有效地使用它的计算能力。 然而实 际上， 高度的并行意味着大的额外开销。 这是所有并行程序员所必须面对的。 这 使得测量并行程序的并行度变成监控并行软件时所主要关心的问题之一。 这有助 于设计者知道程序的哪个部分可以有效地利用处理器，以及哪个部分是瓶颈所 在 。 3 . 2建模分析 存在许多可以被用于并行系统建模的性能建模模式。这些模式可以被分为两 类: 确定模式和概率模式。 在确定模式中， 所有的量值都是固定的。 而在概率模 式中，存在一定程度的不确定性并且包含随机量.我们要讨论的排队网络和 p e t r i 网，都属于后一类。 3 . 2 . 1排队网络 i ) , 概述 排队理论是进行系统定量分析中最强大的数学工具之一。这里所称的系统包 含通常的意义 ( 不仅仅是计算机系统) 。例如，电 话交换系统就是一个例子。 排队网络建模可以被视为排队理论技术中的一个小的子集，它被选择来专用 于模拟计算机系统。 排队系统用来模拟这样的过程:消费者到达，等待轮到它们被服务，服务完 毕，然后离开。为了描述这样的系统，必须详细说明下面的六个部分: i 、内部到达的可能性密度函数; 2 、服务时间的可能性密度函数; 3 、服务器数目; 4 、队列中的缓存空间大小 ( 或称系统容量) ; 5 、对象数目; 6 、排队规则: 在排队理论界常用一个简短的符号来表示这些参数: a / s / m / b / k / s d ， 其中的 每一个域分别和上面列出的六个属性对应。 通常来说， 如果没有缓存空间或者对 象数限制并且排队规则是 f c f s( 先来先服务) ，我们只简单地写为:a / s / m 。对 第三章并行系统性能评估技术 于a 和s ，最广泛使用的分布有: .m : .d : .g : 指数分布 所有的消费者有相同的值 ( 确定的) 一般的 ( 任意分布:a r b i t r a r y d i s t r i b u t i o n ) 例如，m / m / 1表示一个内部到达时间和服务时间都服从指数分布并且只有一 个服务器的排队系统。 排队系统通过状态来描述，而状态通常用系统中的消费者数目 来表示 ( 包含 队列中和服务器中的消费者数目) 。例如，如果系统处于状态 n ，一个新的消费 者的到达将使这个系统转移到状态n + l 。 在计算机系统的性能评估中来说，系统 的状态可以考虑成路由器中的包的数目，在电话交换计算机中的新的呼叫数目， 以 及服务器中的客户请求数目 等等。我们将看到，在分析一个排队系统的时候， 找到系统处于状态 n 的概率 ( 也就是说， 系统中恰恰有 n 个消费者的概率) 是关 键的一步。 这个可能性常常被称为稳定概率 ( e q u i l i b r i u m p r o b a b i l i t y ) 。 许多 别的性能指数可以从这个概率中导出。 2 ) 、 一个单队列的分析 这里，我们要讨论的是只有一个队列的系统。这样的系统可以被用于模拟计 算机系统中的单个资源。 一个生死过程是一个马尔可夫过程，它的状态改变只发生于相邻状态之间。 这是许多排队系统的基础。下面的图显示了一个生死过程的状态迁移图。 稼. 卜 1 图3 . 1 一个生死过程的状态迁移图 当系统处于状态 n的时候，它含有 n 个消费者。新消费者的到达速率是a 服务速率是p 。 。下面这个重要的等式给出了一个生死过程的稳定概率 k: 第三章并行系统性能评估技术 只 。 几 . . . a ,- ， p =一p . , n=1 , 2 , . . . , 0 o pi 户2 p 这里p 。 是在状态0 ( 系统中没有消费者) 的 概率。 考虑到所有概率的和为1 , 那么p 。 可以 用兄 和产 来表 示。 p o = 有: 1/ (1 十 1 -1 l l j=0 a l / p ltl j/ m / m / 1 排队系统是最广泛使用的排队类型。如下图 所示: 离开的消费者 图3 . 2 一个m / m i 1 排队系统 它非凡的属性在于它的无记忆性 ( 由于指数分布) 。这个属性使得分析起来 很容易，同时也对现实情况提供了一种合理的近似。 m / m / 1 系统是生一 死过程的 有下列对应时的一个特例: 凡= a , n = 0 , 1 , . 二 ， 0 0 p = p , n = 1 , 2 , . ., o o 因此，我们有: p = p p o , n “ 1 , 2 , . ., o o 这 里p = 刀p ， 反 映了 通 信强 度。 为了 使系 统 稳定，p 必 须小 于1 ， 否 则， 这 个队列会无限增长 ( 不稳定) .在进行一些置换后，我们有: p= ( 1 一 p ) p , n 二 0 , 1 ,. ., 0 0 有了这个公式，我们可以得到所有有关这个系统的统计量。例如，系统的利 用程 度 通过系 统中 有一 个 或者多 个消费 者的 可能 性 来得 到。 即u = 1 一 p o = p 这就是为什么有些设计者有时称p 为利用率。 这意味着系统中的消费者数目 是: n = e n = n 1 n p- 1 一 p 使用利特尔法则( l i t t l e s l a w ) , n = a t ， 平均响应时间t 可以通过下式得 第三章并行系统性能评估技术 t=丝= 兄六 其他的统计量，包括平均队列长度，平均等待时间，服务器空闲时间，处于 忙状态的时期等等，都可以通过上面的结果很容易地得到。 m / m / m 排队系统是m / m / 1 系统的扩展，其中包含m 个相同的服务器和一个队 列。这可以被用来模拟多处理器系统。 图3 . 3一个助盯 叫卜 队系统 使用下面的对应: a一 a , 。 一 0 ,1 , . , 0 o p . = n p , l _ n p 3 0 ( t 2 ) = fp o ( t3 ) = lp a j 相应的图形如下图: 图3 . 4 一个p e t r i 网的例子 这个网络模拟了一个简单的协议， 其中有一个消息被发送。 它的工作流程如 下。 当一个消息被发送的时候， 一个计时器开始计时。 如果这个消息被接收者正 确接收到， 接收者将向发送者发回一个确认. 如果发送者在超时之前没有接收到 a c k ， 它重新传送那个消息， 重复上面的过程。 这里， t : 表示事件s e n d m e s s a g e 和s t a r t _ t i m e r , t : 表示事件t i m e o u t ， 以 及 t 3 表示事件a c k es r e c e 工 v e d ， 象征 着发 第三章并行系统性能评估技术 送的消息被接收者成功接收到。 系统的初始状态是 u u , t 、 可以实施的条件是在p 。 中有一个标记o f ， 的实施删 除了 p 、 中的标记并且在 p 2 和 p :、 中各放置了一个标记。t :， 实施的条件是在 p 2 和 p :, 都有一个标记， 这定义了这样一个状态: 一个消息己经被发出并且 a c k 还没有被 收到。在这个状态下，t 2 和 t :, 都是可以实施的。如果 t 2 在 t 、 之前实施 ( 意味着 不知是何原因发送的消息或者a c k 被破坏) ，系统返回初始状态，并且t , 不可实 施。 从这个例子中，我们看到 t 2 和 t 。 共享同样的输入位置 p , 。这意味着这两个 变迁是冲突的: 它们中只有一个可以实施， 因为其中的一个实施将使另外一个不 可实施。p e t r i网的这种属性使得它在模拟互斥情况的时候很有用。在 t : 和 t , 之间的选择是不确定的。 这类p e t r i 网( 标准p e t r i 网) 没有规定存在冲突的变 迁的实施顺序。 下面， 我们描述通过在标准p e t r i 网中引入时间扩展的另外一类 p e t r i 网， 其中 提出了 不同的实施规则. 3 ) 、 扩展 p e t r i 网 在p e t r i 网被用来作为真实并行系统的可能模型时， 能够通过多个操作符来 处理异步行为中的所有并行和冲突特征。 在这种情况下， 如果只考虑真实系统中 实体之间的逻辑关系时， 时间是不重要的: 但是当处理以效率为设计目 标的实时 应用时， 时间就是最为重要的了。 标准p e t r i 网只能用于对被模拟的系统进行定 性分析。为了分析量的属性，必须引入时间。 近年来，人们以各种方式把时间引入p e t r i 网，其中最常见的有两种方式: 一是每个位置关联一个时间参数; 二是每个变迁关联一个时间参数。目 前大多数 文献采用后者， 这是因为p e t r i 网作为系统的一种模型， 在系统中一个事件的发 生 ( 通常用一个变迁的实施来表示) 需要一定的时间， 因此将时间与变迁相关联 是比较自 然的。 这个方向上的第一次尝试以e - n e t s 0 。 为代表， 其中每个变迁和一个固定的时 间相关联来规定在使其可实施和实 施之间的延迟。 r a m c h a n d a n i 0 6 l 让在网中的每 个变迁和一个有限的时间范围相关联， 即每个变迁实施的延迟时间有一个最小值 和最大值， 变迁可实施后只能在这个时间段内实施。 标准p e t r i 网的实施规则被 修改来说明实施一个变迁所需的时间。 另外一个修改是一旦一个变迁被设为可实 施时必须立即实施。 这类把固定时间参数引入p e t r i 网的网模型叫做时间p e t r i 网( t i m e d p e t r i n e t s , t p n ) 。 另外一种在p e t r i 网中引入时间参数的方法是:在每个变迁的可实施与实施 第三章并行系统性能评估技术 之间联系一个随机的延迟时间，这种类型的 p e t r i网叫做随机 p e t r i网 ( s t o c h a s t i c p e t r i n e t , s p n ) . s p n 在性能研究中 扮演着重要角色，因为它们是 非常强大的建模工具。而且，它们和马尔可夫链有密切关系，这样就使得分析 s p n 有了坚实的数学基础。 现在提出的几乎所有 s p n 模型之间的不同之处就是它 们修改的实施规则。概述如下: 1 、每个变迁关联一个随机实施时间。 其分布可以 是任意的( a r b i t r a r y ) 或者 是指数分布。因为其无记忆性，后者通常更有用。 2 、定义了新的变迁， 称作瞬时变迁 ( i m m e d i a t e t r a n s i t i o n s ) 。和经典的 变迁不同之处在于一旦成为可实施的它就必须立即实施。如果存在超过 一个瞬时变迁可能同时变为可实施的，对于选择哪一个变迁实施必须规 定一个概率密度函数。 这些变迁通常被称为随机开关( r a n d o m s w i t c h e s ) . 3 、定义了新的弧，例如概率弧和禁止弧。一个概率弧如下图所示: 图3 . 5 含有一个概率弧的蔺机p e t r i 网 变迁t 的实施从p , 中删除标记， 并且或者以 概率p 在p : 中放置一个标记， 或 者以 概率 1 - p 放置在p 。 中。 一个禁止弧从一个位置连到一个变迁。画成一条线 中止于一个小圆圈而不是一个箭头. 图 3 . 6含有一个禁止弧的 p e t r i 网 只有当p 是空的时候变迁t 才变为可实施的。 下面是一些有代表性的例子。 f l o r i n 和n a t k i n 通过在变迁上关联任意分布 的实施时间而提出了s p n 。 在一定条件下，可达图可以 被视为半马尔可夫过程。 d u g a n 的e s p n s ( e x t e n d e d s t o c h a s t i c p e t r i n e t s ) e ， 使用了 额外的 特性，r 匕 如 立即变迁，禁止弧和概率弧。 第三章并行系统性能评估技术 m o l l o y 0 使用服从 指数分 布的 实 施时间 来 和变迁相关联。 m o l l o y 表明 这样扩 展p e t r i 网是因为它和一个连续时间马尔可夫链是同构的， 这样就可以同样地解 决。 这种s p n 的每个标识对应于马尔可夫链 ( m o 的一个状态。 在每个状态的逗 留时间也是一个服从指数分布的变量。 这个模型非常有用并且很方便。 用户需要 做的唯一一件事情是构造这个模型，这样就可以自 动地被转变成 m c ，然后被解 决。 g s p n s ( g e n e r a l i z e d s t o c h a s t i c p e t r i n e t s ) ( 广义随机p e t r i 网) 由a j m o n e m a r s a n 等人提出， 这是最流行和最强大的一类s p n 。 基于m o l l o y 的s p n , g s p n s 通过引入一些额外的特性得到。 主要表现在: 将变迁分为两类: 一类为瞬时变迁， 与随机开关相关联并且实施延时为零: 另一类为时间变迁， 与服从指数分布的随 机实施延时相关联。 允许使用禁止弧， 这样可以减少随机开关的数目. 有形标识 ( t a n g i b l e m a r k i n g ) 只允许时间变迁， 消失标识( v a n i s h i n g m a r k i n g ) 允许瞬时 变迁。 任何消失标识上花的时间确定的都为零。 选择下一个时间变迁来实施稍微 更困难一点，这是由 和变迁相关联的实施速率决定的。可以如下非正式地解释: 每次当一个时间变迁变为可实施的时候， 和它相关联的一个计时器开始按固定的 速度倒计时。 计时器的初始值通过采样相应的随机变量得到， 而这个随机变量服 从指数分布。计时器首先计到零的变迁被选中来实施。一个 g s p n的动态操作和 一个连续时间的随机过程等价。 d s p n s ( d e t e r m i n i s t i c a n d s t o c h a s t i c p e t r i n e t s )( 确定与随机 p e t r i 网) 是另外一类的s p n s ，它允许确定的和随机的实施时间，因此在许多实际情况 中很有用。相应的分析工具也已经被公布。 虽然 s p n s有许多优点，它也存在一些问题。一个全局的 “ 必须”实施规则 改变了网的属性，因此对于时间网相同的无时间p e t r i 网的结果不必是正确的。 另外一个问题是潜在的马尔可夫链的复杂性。为了解决这个问题， 高级模型 ( 例 如:有色图，和p r / t 网)被提出。 现在有色的p e t r i 网受到了更多的重视。对于别的类型的有色网，存在有色 s p n s 和有色g s p n s ， 都是通过引入标记颜色来得到。 颜色被用来模拟系统中实体 的不同行为模式， 和系统中有类似或者等价结构的不同部分。 有色网可以为了分 析的目的被展开( u n f o l d e d ) 成等价的位置一 变迁网。 第三章并行系统性能i t 估技术 3 . 3仿真 3 . 3 . 1概述 仿真是性能评估中广泛应用的一项技术。 它为被研究的系统还没有被完成实 现之前预言它的性能提供了有力的方法。它也可以被用于验证分析模型。 有各种各样的仿真:模仿( e m u l a t i o n ) , m o n t e c a r l o仿真，踪迹驱动 ( t r a c e - d r i v e n ) 仿真， 执行驱 动仿真 和离散事件仿真。 模仿的一个例子是用一个可用的处理器 ( 宿主处理器) 去模仿另一个处理器 ( 目 标处理器) 的指令， 而后者还不可用或者还在设计中。 这种仿真有时被一些 科学家们称为指令级别仿真或者逐周期地( c y c l e - b y - c y c l e ) 仿真。 通过为目 标 处理器写的程序被在宿主处理器上运行的仿真器模仿来研