计算机性能分析与评价.doc

西安交通大学计算机性能分析与评价报告 姓名：苑仁群班级：* 学号：*目录1 概述31.1引言31.2 研究现状及方向32基于排队论对计算机性能分析与评价综述42.1理论基础42.1.1概率论基础42.1.2随机过程62.1.3排队论模型72.2排队论在计算机性能分析与评价中的应用介绍113结论14参考文献15141 概述1.1引言伴随着社会信息化的快速发展，对计算机的性能要求是永无止境的，从而就需要对计算机的性能进行分析和评测，能够对计算机的性能进行定量化和精确化的分析和评测。传统的基于理论峰值的评测计算机性能的方法，如MIPS、CPI、FLOPS等，不能完全反映计算机的性能状况。伴随着计算机相关领域的知识理论的成熟，渐渐的产生了计算机性能分析与评测。计算机性能分析与评测是指通过基准的评测程序获得特定计算机系统运行预定义任务或任务集时的性能特征。进行计算机性能分析与预测主要有以下三个目的：1. 选择：在众多的系统中选择一个最适合的系统，达到较好的性能/价格比。2. 改进：对已有系统的性能缺陷和瓶颈进行改进和提高，优化计算机的性能。3. 设计：对未来设计的系统进行性能预测，在性能成本方面实现最佳设计或配置。本文主要是介绍计算机性能分析与评价的理论知识和方法，以及排队论在计算机评价中的简单应用。1.2 研究现状及方向在国外，计算机评测相对国内来说起步较早，计算机性能分析与评测是计算机硕士生的必修课程，所有做计算机体系结构和系统研究的学术机构和组织都有自己的性能评测研究，同时所有研究计算机系统硬件和系统软件的厂商都有自己的评测研究，形成了许多对计算机性能评测的基准方法。在国内，也出现了对计算机性能进行分析和评测的结构和组织，例如：国家智能计算机研究开发中心，侧重于高性能计算机系统、计算机体系结构、性能评测，面向计算机系统、兼顾各个子程序，侧重性能评测方法的研究；清华大学软件学院的TPC-C评测程序；清华大学网络研究所使用Petri网模型分析网络系统的性能；国防科技大学计算机系中间件系统的研究和测试；计算机世界报性能评测实验室；赛迪评测中心的NC系统的评测。计算机性能分析与评测主要的研究方向如下：1. 相关理论的研究：泊松分布、排队论、自相似理论、MaKov模型、Monte Carlo模拟。2. 负载特性的研究：商业负载(Commercial Workload)、技术负载(Technical Workload)。3. 基准程序Benchmark的研究。4. 性能指标的研究：生命周期、服务协议等级、服务质量、总拥有价格（TCO）、总拥有性能（TPO）、吞吐率、可靠性、可用性、可扩展性、QoS等。5. 性能评测与体系结构的结合。6. 模拟器的研究：SimpleScalar、SimOS、SandOS等。7. 测试系统的研究：Benchmark Factory、ServerScope、Benchmark Studio、 LoadRunner、Forecast toolset等。8. 监控系统的研究：Intel Vtune、 EMon、TeamQuest Lite、 ServerScope-Monitor、 Grid-View等。2基于排队论对计算机性能分析与评价综述2.1理论基础本部分主要总结在计算机性能分析与评测过程中用到的概率论基础、随机过程和常用的排队论模型，根据这些理论知识，为对计算机各个部件的性能分析、优化和改进奠定基础。2.1.1概率论基础1.条件概率和独立性条件概率公式：P(A|B)=P(AB)/p(B),此时假定事件B已经发生，事件A在事件B发生的条件下的概率。独立性：如果P(AB)=P(A)P(B),事件A和B叫做相互独立的事件，独立性的概念可以推广到三个或多个事件。2.全概率公式和贝叶斯定理给定一组互斥的事件E1,E2,En,这些事件的并集包括所有可能的结果，同时给任一个事件A，那么全概率公式可以表示为：贝叶斯公式：又称为后验概率公式，是在已知结果发生的情况下，用来求导致这种结果的某种原因的可能性的大小。3.重要的概率分布1）0-1分布概率分布为：PX=1=p, PX=0=1-p，它描述一次贝努里实验中，成功或失败的概率。2）二项分布公式为：PX=k=Cnk pk (1-p)n-k，k=0,1,2,，n用来描述n次贝努里实验中事件A出现k次的概率。3）几何分布公式为：PX=k=p(1-p)k-1, k=1,2, 描述在k次贝努里实验中首次出现成功的概率。其有一个很重要的性质-无后效性，即在前n次实验未出现成功的条件下，在经过m次实验首次出现成功的概率，等于恰好需要进行m次实验出现首次成功的无条件概率，与过去历史无关的性质称为马尔可夫特性。它可以描述某一任务的服务持续时间。4）泊松分布（Poisson）公式为：PX = k = k e-/ k!， k=0,1,2,在实际系统模型中，一般都要假定任务（或顾客）的到来是泊松分布的。5）K-爱尔朗分布概率密度函数为：f(x)=(kx)n-1ke-kx /(n-1)!， x0 f(x)=0， x0具有K-爱尔朗分布的随机变量可以看作具有同一指数分布的独立的k个随机变量之和。其在排队模型中，得到了广泛的应用。6）指数分布指数分布是一种连续的概率分布，其概率密度公式为： f（x）=e-x ， x0 f（x）=0 ， x0在连续型随机变量中，只有指数分布具有无后效性。在排队理论和随机Petri网中，指数分布是很重要的。2.1.2随机过程设(O,T,P)为一概率空间，T为一实数集，如果对于每个tT,都有定义于(O,T,P)上的随机变量X(t,s)与之对应，则称依赖t的随机变量族X(t,s),tT为一个随机过程。随机过程论与其他数学分支如位势论、微分方程、力学及复变函数论等有密切的联系，是在自然科学、工程科学及社会科学各领域研究随机现象的重要工具。随机过程论目前已得到广泛的应用，在诸如天气预报、统计物理、天体物理、运筹决策、经济数学、安全科学、人口理论、可靠性及计算机科学等很多领域都要经常用到随机过程的理论来建立数学模型。以下为主要的随机过程：1.计数过程令N(t)表示在时间段0,t)内的某种事件发生的次数。N(t)称为该事件的计数过程。例如事件：数据包到达路由器、顾客到达商店等都可以看作一个计数过程。计数过程有以下性质：1）N(0)=0; 2)N(t)非负；3）如果st, N(s)=0如果满足以下条件，则被称为参数为的泊松过程, 称为泊松过程的速率：1） 独立时间段上的事件发生的个数是独立的（即独立增量过程）；2） 在任意一段时间内发生的事件的个数的分布是不变的（即平稳过程）；3） 在一小段时间h内发生一个事件的概率为h+O(h)；4） 在一小段时间h内发生多于一个事件的概率为O(h).一般N(t)表示在时间间隔0,t中到达某服务台的顾客数。3.伯努力过程设随机序列N(n),n=0,如果它满足以下三个条件:1)N(0)=0，2)N(n),n=0具有独立增量性，3）N(m +n)-N(m)B(n, ),其中m，n均为非负整数，则称该随机序为参数是（01）的伯努力过程。4.马尔可夫过程对于随机过程X(t)|tT，如果对于任意的参数t0t1t21.2)连续时间生灭过程一个连续时间齐次马尔可夫链X(t),t=0,状态空间0,1,2,称为生灭过程。6.更新过程设N(t),t0是一个计数过程，x n (n=1)表示第n-1次事件和第n次事件的时间的间隔，再设x1，x2，为非负、同分布的随机变量序列，则称计数过程N(t),t0为更新过程。其主要特点是根据事件间隔的特征（独立、同分布）定义。泊松过程中事件之间的时间间隔是呈负指数分布的，泊松过程是更新时间间隔呈负指数分布的更新过程。2.1.3排队论模型排队论又称为随机服务系统，是运筹学的重要组成部分，是具有特殊应用价值的现代应用数学的分支之一，其应用范围很广，它适用于一切服务系统，尤其在通信系统、交通系统、计算机存储系统和生产管理系统等方面应用的最多。1.排队系统的组成部分1)输入过程与到达规则。输入过程一般是用顾客到达间隔时间来描述的。根据到达的间隔时间所服从的分布，输入过程可以分为定长输入、负指数输入、爱尔朗输入、几何输入、负二项输入与一般输入。顾客到达的时间间隔可以是确定型的，也可以是随机型的，顾客刀客可以相互独立，也可以相互无关。顾客可以单个到达、成批到达、依时到达、移态到达。2）排队规则。排队规则一般分为等待制、损失制和混合制，在等待制和混合制中通常又分为FCFS、LCFS、ROS、优先非抢占服务、优先抢占服务等，在混合制中又分为队长容量有限、等待时间有限。此外，还有顾客服务后反馈以及共同占用、占而不用等。3）服务机构的结构。服务机构的结构可分为单服务台、有限个服务台与无限多个服务台。在多个服务台中又可分为并联、串联两种。4）服务时间与服务规则。服务时间是指服务一个顾客所用的时间。根据其分布，一般分为定长分布、指数分布、几何分布与一般分布。服务规则分为有假时间与无假时间两类。还可以分为单个服务与成批服务。2.排队模型系统的格式排队模型的格式为：A/B/n/S/Z,各个符号的含义如下表： 符号含义A顾客到达规律B服务时间分布n服务员的数目S队列容量的大小Z服务规程A和B可以用以下的参数符号表示：M：如果用于描述到达，表示泊松到达过程，到达时间间隔符合指数分布；如果用于描述服务，则指具有指数分布的时间，M表示Markov的第一个字母。G：一般分布。表示到达间隔时间或服务时间服从一般分布。Ek：k-爱尔朗分布。表示到达间隔时间或服务时间服从k-爱尔朗分布。H：超几何分布。L：H项式分布。Z代表的典型服务规程如下表所示：服务简写含义FCFS先来先服务LCFS后来先服务RSS随机选择服务PR优先权服务GD一般规约服务Ba集体（批量）服务排队论使用的主要数学符号及含义如下表所示：数学符号意义平均到达速率，顾客数/秒Ts每个顾客（任务）的平均服务时间Ts服务时间的标准差利用率，服务员忙所占的时间比例平均服务速率Q系统中的顾客数量（包括等待的和正在 被服务的顾客）q系统中的平均顾客数量（包括等待的和正在 被服务的顾客）TQ一个顾客在系统中花费的时间Tq一个顾客在系统中花费的平均时间（排除时间）qq的标准差TqTq的标准差等待服务的平均顾客数量T一个顾客等待服务的平均时间Td等待顾客（不包括等待时间为零的顾客）的平均等待时间的标准差N服务员的数量mx(r)在r%的时间，x值小于mxr；又称为第r百分位3.常用的排队论模型1) M/M/1排队模型任何一个排队过程都包括以下三个过程：到达过程，排队过程，服务过程。如果一个排队系统仅有一个服务系统，请求的个数不受限制，队列的长度不受限制，到达顾客数服从泊松分布，服务时间服从负指数分布和FIFO排队过程，则该系统被称为M/M/1系统。设M/M/1模型的到达率为l，服务率为m，则该模型的数量指标公式如下：a) 系统服务强度r=l/m，b) 系统中没有任务的概率P0=1-l/m，c) 系统中有n个任务的概率Pn =(1-r)rn ，n=0,1,2,d) 系统中平均任务数量 E(n)=r/(1-r)，e) 系统平均响应时间 E(R)=(1/m)/(1-r)，f) 队列中平均任务数 E(nq)=r2/(1-r)，g) 任务在队列中的平均等待时间 E(W)= r/m(1-r)。在使用M/M1排队模型的时候，可以直接使用上面的这些指标公式，不用给出证明过程。2）M/M/m排队模型该队列系统的顾客到达为泊松流，到达速率为l，有m个服务员，每个服务员的服务速率为m，服务规则为FCFS，所有的服务员共享一个公用的队列，该队列是一个生灭过程模型。该模型的数量指标公式如下：a) 系统服务强度r=l/mm，b) 系统中没有任务的概率：p0=1+mmm!1-+n=1m-1mnn!-1，c) 系统中有n个任务的概率：pn=fx=p0mnn!, &n=WT时，任务将会出现明显丢失，所以为了满足邮件的顺利发送，应该满足WsWT，则根据公式（2），则有：1/(m-l)WT，可得：lm-1/ WT 公式（3）所以，应该根据服务器的服务速率m和服务器的逗留门限WT来调整邮件的发送速率，以保证邮件的发送成功率。在大多数情况下，采用匀速发送，由于服务器端的参数测量起来难度较大，实践中，通常采用首先根据经验预估一个初始发送速度，并不断采用折半测试的方法寻找最佳的发送速度。一旦确定后，便可在一段时间内采用这个标准发送。2.基于排队论的多核处理器对共享总线争用延时分析多核处理器中目前比较主流的通信机制有两种：一种是基于片上网络进行多核之间的通信，另一种是基于共享总线的结构。Intel公司有在使用基于共享总线的体系结构。在使用共享总线的结构中，多个处理器会对总线的争用造成时间开销，并且带来使用总线的延迟。为了分析总线争用对多核处理器性能的影响，可以引入排队论对总线争用延时进行定量分析，从而得到总线争用延时与多核处理器中诸多因素的量化关系。各个处理器核对总线的请求可以看成是排队论系统中顾客的到达速率，排队规则可以认为是总线的仲裁协议，其协议就是一个FCFS机制，服务机构就是总线接口部件。所以可以用M/M/1的排队系统对多核处理器对共享总线争用延时的分析。设在M/M1系统中，多核请求服务的平均到达率为，总线处理请求的速率为，则可以得到服务强度：，各个处理器核在缓冲区的平均等待时间Wq： Wq =-. 的求解过程如下：多核在访问私有cache不命中的时候，才去访问共享的cache，这时候需要去使用共享总线和外部存储器，则对总线请求的到达率可以表示为：=1-p1 IPC， （1）其中p1表示私有cache的命中率，IPC是多核处理器单位时间执行的指令数，是多核处理器的持续性能。占用一次总线系统的平均时间的求解过程如下：根据体系机构所采用的总线仲裁机制，在多核处理器中某个处理器核占用一次总线时间包括：共享cache的查找时间、总线系统的传输时间、以及当共享cache没有命中，访问片外存储器的时间开销和外围接口的传输时间，可以求得占用一次总线系统的平均时间为：T=p2Tcache查找时间+T总线传输时间+1-p2T访问外存时间+T外围接口传输时间，（2）则由公式（2）可以得出总线处理的平均速率：=1T ，（3）综合公式（1）（2）（3）可以得出一次请求在缓冲区的平均等待时间为：wq=-=T21-p1IPC1-T1-p1IPC , (4)根据公式（4）可以看出，在其他参数不变的情况下，私有cache的命中率越高，平均等待时间就越短，对共享总线的竞争就越小。因为命中率越高访问共享cache的次数就越少。在私有cache命中率和总线操作时间不变的情况下，IPC的值越大，每一次请求在缓冲区的等待时间越长，多核处理器需要处理的指令就越多，则需要访问共享