异构并行工作站机群系统的性能评价指标

1、计 算 机 研 究 与 发 展com pu t er r e sea r ch & d ev el o pm en tv o l135, n o 13m a r. 1998第 35 卷 第 3 期1998 年 3 月异构并行工作站机群系统的性能评价指标申俊郑纬民( 清华大学计算机科学与技术系 北京 100084)摘 要 文中在对矩阵乘法进行实验研究的基础上, 分析了异构性对工作站机群系统性能的影响,描述了异构性的数学模型, 扩展了加速比和效率等性能指标的定义, 使之能同时适用于同构、异构 两种并行系统的性能评价.关键词 并行计算, 异构性, 加速比, 效率中图法分类号 t p 302m od

2、el ing pa rall el com put ing perfo r-m a nce fo r hetero geneo us w o rksta t io n cl usterssh en j u n an d zh en g w e im in(d ep a r tm en t of c om p u ter s cience and t ech nology , t sing h u a u n iv ersity , b eij ing 100084)a bstrac t sp eedup and eff ic iency a re w ide ly u sed to eva l

3、ua te th e p e rfo rm ance o f p a ra lle l com p u t ingsy stem s. h ow eve r, th ey w o rk w e ll o n ly in hom o geneo u s p a ra lle l sy stem s. t h e in t ro duc t io n o f h e te ro gene ity in w o rk sta t io n c lu ste r s m ak e s th em no t su itab le fo r p a ra lle l com p u t ing. t o

4、cop e w ith th is p ro b lem , th e h e te ro gene ity o f w o rk sta t io n c lu ste r s is quan t if ied, and th e sp eedup and eff i2 c iency a re redef ined o n th e ba sis o f tw o m a t r ix m u lt ip lica t io n exp e r im en t s. t h e se new m o de ls a re gene ra l eno ugh to co ve r p e r

5、fo rm ance eva lua t io n o f bo th hom o geneo u s and h e te ro geneo u s com p u ta2t io n s.key words p a ra lle l com p u t ing, h e te ro gene ity, sp eedup , eff ic iencyc la ss n um ber t p 302引言1并行计算机系统通常使用加速比、效率两个指标对其性能进行评价, 但这些性能指标是在系统同构的条件下定义的. 只有当组成系统的机器性能基本一样, 并行算法的负载基本平衡时, 它们才能比较有效地分析

6、 并行系统、并行算法的通信开销以及负载分配策略对系统的影响. 由于过去使用的并行系统, 如 sm p , m p p多数是同构并行系统, 因此这些定义一直被广泛使用. 但是随着工作站机群系统的兴起和推广, 而这种系统原稿收到日期: 1996211205; 修改稿收到日期: 1997203220. 本课题得到国家“863”高科技计划基金资助. 申俊, 博士研究生, 主要从事并行机群系统通信技术的研究. 郑纬民, 教授, 博士生导师, 主要从事并行机群系统及多机处理技术的研究.2矩阵乘法实验研究我们的实验系统是一个由 10m b s 以太网构成的机群系统, 系统上有三种工作站: 8 台 spa r

7、 c 20、2 台r s6000530 和 2 台 r s6000590. 在这个系统上我们实现了两种不同的并行矩阵乘法: 一种是负载平均分配 算法, 这种算法是为了分析同构、异构对加速比性能的影响; 另一种是负载平衡算法, 它主要用于分析负载平衡对提高异构机群系统效率的作用.2. 1负载平均分配算法在一个由 m 台工作站组成的机群系统上, 运行 n n 矩阵并行乘法运算, 可把这两个 n n 矩阵 a 和 b按水平方向均匀分成 m 块, 分别放在 m 个结点上, 如图 1所示, 假设 n %m = 01, 2 .当处理机 p i 计算完 a i b i 后, 把 b i 发送给下一个结 点

8、p i+ 1 , 并等待接收上一个结点 p i- 1 送来的数据作为新的b i , 再计算 a i b i. 这样的过程重复 m -1 次, 于是每个结点上都得到了矩阵乘的部分和. 最后各结点把部分和汇总到 m a ste r 结点上.我们用这 种 算 法 运 行 一 个 600 600 双 精 度 矩 阵 乘 法, 矩阵乘法的数据规模不大于 10m , 保证算法对内存的图 1 并行矩阵乘法要求在三种工作站的内存范围之内. 所得到的实验数据如表 1、表 2 和表 3 所示.表 1单机执行时间表 22 结点执行时间表 34 结点执行时间2. 2负载平衡算法从上面的实验数据看, 负载平均分配策略在

9、异构系统上得到的效果较差, 其关键原因在于系统中性能最慢的结点成了整个并行计算的瓶颈. 如果采用负载平衡策略, 其效果又会如何? 为此我们设计了一种简单的 负载平衡算法, 其基本思路是根据各结点机的相对运算速度确定在每一结点上分配的进程数, 性能越好的机4 台 spa rc 202 台 spa rc 202 台 r s60005302 台 spa rc 202 台 r s60005902 台 r s60005302 台 r s6000590105. 48 秒112. 76 秒102. 95 秒110. 53 秒2 台 spa rc 201 台 spa rc 201 台 r s60005301

10、台 spa rc 201 台 r s60005901 台 r s60005301 台 r s6000590191. 11 秒248. 06 秒189. 05 秒249. 2 秒spa rc 20r s6000530r s6000590360. 685 秒575. 42 秒120. 825 秒3 期申 俊等: 异构并行工作站机群系统的性能评价指标195器得到的进程数越多, 这样就基本达到了负载平衡的目的.表 4 是用负载平衡算法得到的测试数据, 其测试条件与前者相同.表 4 4 结点执行时间3性能指标的定义3. 1加速比 ( speedup)加速比是用于度量并行处理效果常用的性能指标, 其数学描

11、述形式为1 :s p (a ) =t 1 (a ) t p (a ).(1)其中 s p (a ) 代表加速比; t 1 (a ) 代表算法 a 在单台处理机上串行执行需要的实际时间; t p (a ) 表示使用 p台处理机时算法 a 并行执行所需的时间.在这个定义中没有规定选用哪台处理机来确定 t 1 (a ) , 而无形中已经默认各处理机的计算能力相同, 是 一个同构并行计算机系统. 在异构系统中由于机种不同, 它们具有各自不同的性能, 这就导致了一个问题: 应 该选择什么样的机器作为确定 t 1 (a ) 的标准, 才能最为有效地反映出整个并行系统的加速性能? 比如是运算 最快的机器、最

12、慢的机器, 还是它们性能的平均加权值. 为了确定哪种选择更有效, 我们以负载平均分配算法 在两结点上的结果进行对比, 见表 5.表 5 两结点加速比对比如果以最慢的单机为标准, 得到的加速比数值往往很好. 但有可能出现这样的情况: 并行计算花费的时间比在系统中性能最好的单机上的运行时间还多. 比如 1 台 r s6000530 和 1 台 r s6000590 组成的系统,并行计算时间是 24912 秒, 比在 1 台 r s6000590 上运行需要的时间还多, 而其加速比竟高达 2131, 属于超 线性加速比, 可见这样的性能指标对并行系统的评价是没有实际意义的. 同样, 如采用性能平均加

13、权值作为确定加速比的标准, 当系统中速度慢的机器比例比较大时, 也可能会出现不能反映实际情况的超线性加速比 现象. 如果选择性能最好的结点作为参考对象, 从表 5 中的数据可看出, 它不仅比较真实地反映了异构并行系统加速性能的好坏, 而且还反映了异构性对整个并行系统的影响.根据以上的分析, 我们采用系统中单机运行最快的机器作为确定 t 1 (a ) 的标准3统中加速比定义变为如下形式:, 则异构工作站机群系m in j = 1 t (a ,m j ) ms p (a ) =.(2)t (a , h n )在上式中, h n 代表一个异构工作站机群系统, 假设它由 m 台工作站组成; t (a

14、, h n ) 表示在机群系统 h n下 运 行 程 序 a 所 需 的 总 时 间; t (a , m j ) 表 示 程 序 a 在 某 一 台 单 机 m j 上 运 行 需 花 费 的 时 间, 其 中j = 1, , m .标准2 台 spa rc 201 台 spa rc 201 台 r s60005301 台 spa rc 201 台 r s60005901 台 r s60005301 台 r s6000590最快1. 891. 450. 640. 48最慢1. 892. 321. 912. 31平均1. 891. 891. 271. 404 台 spa rc 202 台 spa

15、 rc 202 台 r s60005302 台 spa rc 202 台 r s60005902 台 r s60005302 台 r s600059082. 69 秒129. 33 秒63. 25 秒68. 87 秒了与加速比定义相同的方法, 也以系统中运算速度最快的机器为参考点, 计算每台机器的相对计算能力. 例如, 对一台工作站m i , 当运行应用程序 a 时, 其相对计算能力w i (a ) 可被定义为:m inm 1 t (a ,m j ) j =w i (a ) =(3), i = 1, , m .t (a ,m)i(2) 异构性的度量在异构机群系统中, 可以用各结点机计算能力的差

16、异来度量系统的异构性. 能够反映这种差异的方法有 好几种. 不过采用哪种方法作为异构性的度量标准, 就得仔细考虑, 因为异构性不仅要体现系统中各结点机 计算能力的变化, 而且可以反映系统中某些关键部分改变所带来的影响, 如计算速度最快或最慢的结点性能 的变化对整个系统的异构性影响较大, 或者是当系统中有几台机器的速度与其它机器相差较大时, 系统的异构性也较大. 下面就几种度量方法进行比较, 分析一下它们的优缺点: 标准偏差法 ( standa rd dev ia t io n)标准偏差法定义异构性的公式是:mj = 12.w -w jh stand =(4)mmj = 1w j m .其中w

17、是系统的平均计算能力, 即w = 平均绝对偏差法 (m ean ab so lu te dev ia t io n)mj = 1w -w jh m ean =.(5)m 以系统中运算最快的结点为参考点的平均偏差法, 其公式为:mj = 11 - (a )w j(6)h =.m这三种定义异构性的方法在一定程度上都可以反映系统中各结点计算能力的变化大小, 其中前两种方法是以系统的平均计算能力为参考点来评定计算能力的差异, 这种方法在各结点性能差异不大时能较好地 体现系统的异构性, 但当差异较大时就不能充分反映整个系统的异构性了. 例如, 一个由 100 台工作站组成 的机群系统, 其中一台的速度最

18、快, 其相对计算能力为 1, 剩下 99 台工作站的性能都一样, 假设计算能力为015. 当性能最好的机器速度再提高一倍时, 由于速度快的工作站计算能力仍然为 1, 则其它机器的相对计算能力降为 0125. 用标准偏差法或平均绝对偏差法计算这两种条件下的变化情况, 可以得到其异构性的变化 不到 1% , 假设任务分配方案保持不变的话, 系统的加速比实际上降低了大约 50%. 因此这两种方法不能正 确反映异构性与系统加速比的关系.最后一种方法克服了前两种方法的缺点, 它采用与加速比定义相一致的参考点, 因此我们最终也采用这种方法定义并行系统的异构性, 其正确性可用上面的例子加以验证. 初始情况下

19、异构性 h = 015, 当最快的 工作站速度增加一倍时, h = 0175, 说明了系统的异构性增加了 50% , 这与加速比的下降幅度相一致.(3) 并行度并行计算中每个结点的 c pu 时间均可分成两部分: 一部分是有效计算时间 t act , 用于完成并行任务; 另j一部分是空闲时间, 它主要是并行任务之间通信、空闲等待所需要的时间开销. 因此还用并行度来反映有效计算时间在整个并行计算时间中所占的比例, 其定义如下1 :mj = 1 t jactp deg (a ) =.(7)t (a , h n )3 期申 俊等: 异构并行工作站机群系统的性能评价指标197(4) 加速比与异构性的关

20、系由加速比的定义可知, 异构性会影响系统的加速比性能, 因此我们来研究一下它们之间的关系. 假设应 用程序 a 在工作站m i ( 1im ) 上运行需要的时间为: t (a ,m i ) = |a | s i , 其中|a | 表示程序 a 的规模; s i代表每台工作站的速度. 用每台工作站的速度 s i 定义整个异构系统的平均速度 s = p deg (s 1 + s 2 +s m ) m , 则总的并行计算时间 t (a , h n ) 可表示为:+|a | =m |a |t (a , h n ) =.msp deg i= 1s i因此由加速比的定义可得:|a |m inm 1mp d

21、eg i= 1s ii=s is p =p deg (1 -h ).(8)m |a |m m axm 1 s i i=mp deg i= 1s i公式 (8) 给出了加速比、异构性之间的关系, 它说明了异构并行系统的一些性能特点: 对于一个给定的并行系统来说, 如果能增大系统的并行度, 则并行计算的加速比相应增大. 这点可在同构系统中得以较为明显的体现. 如果并行度保持不变, 当异构性 h 增加时, 系统加速比随之下降; 反之异构性 h降低时, 加速比则会增加. 由于异构性的引入增加了对加速比性能进行预测的困难. 因为即使保持 h同的算法可能有不同的并行度, 使得加速比有所变化.图 2 是两种

22、矩阵乘法的加速比曲线. 虽然采用算法不同, 但 在异构机群系统中, 加速比都是随异构性的增大而降低. 当异构性 相同时, 负载平衡算法的加速比一般都比平均分配算法要好, 这是因为负载平衡算法提高了系统的并行度, 改善了加速比性能.3. 3效率 (ef f ic ien cy)效率用来度量在并行计算中整个系统的资源利用率. 同构并 行系统中效率可简单地定义为加速比与处理器结点数之比1 , 即e = s p p. 异构机群系统由于参加并 行 计 算 的 结 点 运 算 速 度 不的值不变, 由于不图 2 四机加速比曲线同, 不能简单地使用结点数 p 来计算并行效率. 不过根据前面分析可知, 我们定

23、义异构机群系统的性能评价指标都是以系统中运算最快的机器为参考点, 按照这一思路, 我们采用系统中单机相对计算能力的加权值代替结点数 p , 即me = s p j = 1w j.(9)很明显, 如果每个结点性能相同, 则w j = 1, 上式可简化为: e= s p p , 这和同构系统中的定义完全一致. 图 3 是负载平均 分配算法和负载平衡算法的效率曲线. 与加速比曲线相比,效率曲线就要复杂些. 加速比是随异构性的增大而减小, 但 效率反而可能出现增大的情况. 如负载平均分配算法在异构性 h = 0119 时, 效率比同构时的还高, 这是因为当异构性从0 增加到 0119 时, 运行时间从

24、 105148 秒增加到 112176 秒,增长了 619% , 而其总的计算能力却从 4 降低为 3125, 降低了1818% , 由于总计算能力下降的幅度大, 导致异构时的效率图 3 四机效率曲线反而增高. 可见加速比并不能精确评价异构并行工作站机群系统性能的好坏, 它只是反映并行系统或算法的总体变化趋势, 让使用者更明显、更直观地了解异构系统的性能. 加速比之所以不能精确反映异构机群系统 的性能, 关键在于它总是以系统中单机运行最快的机器作为确定 t 1 (a ) 的标准, 而效率则以系统的总计算能力来修正结点个数 p , 因此效率对并行系统、算法的评价比加速比要精确些.析了它们之间的关

25、系及各自的特点, 并且通过实验方法对此进行验证, 为今后异构机群系统性能预测的研究打下了基础.参考文献12黄铠. 高等计算机系统结构: 并行性, 可扩展性, 可编程性. 北京: 清华大学出版社, 1995g ram a a y, gup ta a , kum a r v. iso eff ic iency: m ea su r ing th e sca lab ility o f p a ra lle l a lgo r ithm s and a rch itec tu re s. ie e e p a ra lle l & d ist r ibu ted t ech no lo gy, 19

26、93, 1 ( 2) : 12_ 21m echo so c r , f a r ra ra j d , sp ah r j a. a ch iev ing sup e r linea r sp eedup o n a h e te ro geneo u s, d ist r ibu ted sy stem. ie e e p a ra lle l & d ist r ibu ted t ech no lo gy, 1994, 2 ( 2) : 57_ 61zh ang y y. m o de ling and ch a rac te r izing p a ra lle l com p u t ing p e rfo rm ance o n h e te