优先级周期性互换的实时调度算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇优先级周期性互换的实时调度算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：针对以往关于可扩展性研究中未充分考虑并行执行时间因素，可扩展性与并行执行时间的关系仍未研究清楚的问题，深入和全面研究延迟可扩展性和并行执行时间的关系，得出并证明了不同算法机器组合体在相同初始状态下进行延迟扩展后，若执行更快的组合体具有更好的延迟扩展性，则该组合体在扩展后仍将保持更快等重要结论。这些结论丰富了可扩展性和并行执行时间关系的研究内容，为并行计算延迟扩展获得理想扩展性能提供了理论依据。最后，通过对不同算法机器组合体进行扩展实验，进一步验证了结论的有效性。
关键词：并行计算；可扩展性；延迟度量；执行时间
中图分类号： TP338
文献标志码：A
Abstract：
Concerning the problem that previous studies on the scalability do not fully consider parallel execution time， and the relationships between latency scalability and parallel execution time have not been yet studied thoroughly， this paper studied the relationships between latency scalability and parallel execution time deeply and fully. Thereby some important conclusions were drawn， and they were about the relationships between latency scalability and parallel execution time after different algorithmmachines were extended from the same initial state. Then the proof of the above conclusions was given in this paper. The derived conclusions enriched the research content about the relationships between latency scalability and parallel execution time and provided a theoretical basis for obtaining ideal latency scalability of parallel computing. Finally the important conclusions and analytical expressions were verified through experimental results obtained for different algorithmmachines.
Key words： parallel computing； scalability； latency metric； execution time
0引言
在并行计算中，处理器之间的通信开销和负载平衡问题极大影响并行执行时间，并行算法的性能不能随处理节点数量的增加而提高，导致资源的浪费和过剩。当前，高性能计算的发展趋势表明未来的计算机将由越来越多的处理单元组成，处理器规模将会变得异常庞大。因此，扩展性问题已成为并行算法和体系结构设计必须考虑的重要因素。所谓可扩展性（Scalability）[1]，是用来描述和刻画并行算法能否有效利用可扩展处理器资源能力的一个概念和特性，即并行系统随处理节点数目的增加，计算性能也随之增强的能力称为可扩展性。
可扩展性是并行计算的一个重要的性能指标，学者们一直在进行广泛和深入的研究工作，并于1967年发现了Amdahl定律[2]，从此开始了关于效率（Efficiency）和加速比（Speedup）的可扩展性讨论。并行计算扩展过程中，客观存在多种制约因素。针对各种扩展的约束，研究人员提出了多种可扩展的加速比概念，如执行时间受限的加速比、内存受限的加速比和一般化的加速比[3-5]。随着研究的进一步深入，学者们先后又提出了等效率的度量方法[6]、等平均速度度量方法[7]、等平均开销度量方法[8]等。这些度量方法均重点关注某一性能指标，希望该性能指标扩展前后能保持不变。它们考察需要在多大范围内对系统规模和问题规模进行扩展，才能保持该性能指标恒定或者近似不变，从而度量此系统可扩展的程度和好坏[9]，然而这些方法并没有单独考虑并行执行时间这个重要因素。这样如果只关注可扩展性，则可能导致人们选择慢速算法。Sahnl等[10]指出，必须将执行时间作为性能评价方法的首要考虑因素。当然如果仅强调执行时间，则又可能导致人们使用可扩展性较差的算法。表1是Sun[11]在IBM SP2上求解对角占优的三对角方程组的并行对角占优（Parallel Diagonal Dominant， PDD）和并行划分LU（Parallel Partition LU， PPT）算法的结果。表1中：N为系数矩阵的行数，p为处理机台数，算法描述见文献[11]。表1中实验数据表明，PDD算法比PPT算法具有更好的可扩展性，但在处理机数较少时，它的执行时间比后者长。
陈军[14]详细分析了等平均开销可扩展性和并行执行时间的关系。论文推导并证明了结论：两个不同的算法机器组合体的处理器规模均为P，工作负载均为W时，执行时间会不同，即它们用相同规模的处理器完成同一任务的求解，有快有慢。两个组合体均按等平均开销方法扩展，它们的处理器规模均扩展为P′，但工作负载扩展的程度不同，若执行更快的组合体具有更好的等平均开销可扩展性，则该组合体在扩展后仍将保持更快。
2延迟可扩展性与并行执行时间的关系
3实验结果及分析
第2章中经过推导得到的一些重要结论，已经过严谨的理论证明，是正确的。本章进一步通过实验来验证主要结论的有效性。
3.1实验配置
在科学和工程计算中，矩阵运算是非常频繁和重要的操作。矩阵相乘算法由于计算量大、计算和通信比较平衡，经常用来作为并行计算的基准测试程序，许多线性代数中的计算问题最终可以归结到矩阵乘法的计算。n阶矩阵A和B相乘算法的计算负载，即其所需基本操作步数W为n的函数，为表达简洁，本文使用矩阵阶数n表示工作负载。实现矩阵乘法的并行算法有很多，为便于比较，本文选择性能一般的带状划分的行列划分（Row Column Partition， RCP）算法和综合性能较优的棋盘划分佳能（Chessboard Partition Cannon， CPC）算法[16]。
开展实验的系统平台一为同济大学网格中心实验室的Dell PC集群平台，集群平台由64个计算处理节点通过千兆以太网互联组成，每个节点的CPU为Intel Xeon 3.0GHz，缓存4GB，内存32GB；操作系统为Redhat Linux 9.0。另一实验系统平台为实验室的曙光3000，系统节点可扩展到128个节点，节点采用IBM Power3Ⅱ微处理，节点之间通过100/1000Mb/s高速以太网和高速系统网络互联；节点运行完整的IBM AIX操作系统。并行计算软件环境均为MPICH2。
实验中变换两种算法和系统平台的组合，扩展计算负载规模和系统规模。通过测量和计算得到的实验数据如表2～5所示。
4结语
为了充分利用不断扩展的处理器资源，研究人员高度关注并行计算的可扩展性能，深入地开展并行计算可扩展性的研究，提出了一些重要的可扩展性能度量方法。在一个可接受的时间范围内完成并行计算具有重要的现实意义，因此并行执行时间也是衡量并行计算性能的一个重要方面。如果并行计算既有良好的可扩展性能，又能在可接受的执行时间范围内完成，那么这样的扩展是非常理想的扩展。本文在已有的可扩展性和并行执行时间关系的研究基础上，深入地分析了延迟扩展性和并行执行时间的关系，得出并证明了不同算法机器组合体在相同初始状态下进行延迟扩展后，若执行更快的组合体具有更好的延迟扩展性，则该组合体在扩展后仍将保持更快等重要结论，并对实验室不同算法机器组合体应用延迟扩展方法进行了扩展实验。测量得到的并行执行时间和扩展性数据验证了分析所得主要结论的有效性。本文的研究结论丰富了可扩展性和并行执行时间关系的研究内容，为并行计算延迟扩展获得理想扩展性能提供了理论依据。
参考文献：
[1]CHEN G. Parallel computer architecture [M]. Beijing： Higher Education Press， 2002.（陈国良.并行计算机体系结构[M].北京：高等教育出版社，2002.）
[2]AMDAHL G M. Validity of the singleprocessor approach to achieving large scale computing capabilities [C]// Proceedings of the AFIPS Spring Joint Computer Conference. New York： ACM Press， 1967： 483-485.
[3]GUSTAFSON J L， MONTRY G， BENNER R. Development of parallel methods for a 1024processor hypercube [J]. SIAM Journal on Scientific and Statistical Computing， 1988， 9（7）： 609-638.
[4]SUN X H， NI L M. Scalable problems and memorybounded speedup [J]. Journal of Parallel and Distributed Computing， 1993， 19（1）： 27-37.
[5]SUN X H， ZHU J. Performance considerations of shared virtual memory machines [J]. IEEE Transactions on Parallel and Distributed Systems， 1995， 6（11）： 1185-1194.
[6]GRAMA A Y， GUPTA A， KUMAR V. ISOefficiency： measuring the scalability of parallel algorithms and architectures [J]. IEEE Parallel and Distributed Technology， 1993， 1（3）： 12-21.
[7]SUN X H， ROVER D T. Scalability of parallel algorithmmachine combinations [J]. IEEE Transactions on Parallel and Distributed Systems， 1994， 5（6）： 599-613.
[8]WU X. Scalable parallel computing performance model and its application [D]. Beijing： Beijing University of Aeronautics and Astronautics， 1996.（吴幸福.可扩展并行计算性能模型及其应用[D].北京：北京航空航天大学，1996.）
[9]HAO S， ZENG G， TAN Y. Scalability analysis of heterogeneous computing based on computation task and architecture to match [J]. Acta Electronica Sinica， 2010， 38（11）： 2585-2589.（郝水侠，曾国荪，谭一鸣.计算任务与体系结构匹配的异构计算可扩展性分析[J].电子学报，2010，38（11）：2585-2589.）
[10]SAHNL S， THANVANTRI V. Performance metrics： keeping the focus on runtime [J]. IEEE Parallel and Distributed Technology， 1996， 4（1）：43-56.
[11]SUN X H. Scalability versus execution time in scalable systems [J]. Journal of Parallel and Distributed Computing， 2002， 62（2）： 173-192.
[12]MARTIN I， TRIADO F. Relationships between efficiency and execution time of full multigrid methods on parallel computers [J]. IEEE Transactions on Parallel and Distributed Systems， 1997， 8（6）： 562-573.
[13]SUN X H. The relation of scalability and execution time [C]// Proceedings of the 1996 International Parallel Processing Symposium. Washington， DC： IEEE Computer Society， 1996： 457-462.
[14]CHEN J. Parallel computing scalability studies and applications on the distributed memory environments [D]. Changsha： National University of Defense Technology， 2000.（陈军.分布式存储环境下并行计算可扩展性的研究与应用[D].长沙：国防科学技术大学，2000.）
[15]ZHANG X D， YAN Y， HE K. Latency metric： an experimental method for measuring and evaluating parallel program and architecture scalability [J]. Journal of Parallel and Distributed Computing， 1994， 22（3）： 392-410.
[16]LI X. Numerical parallel algorithms and software [M]. Beijing： Science Press， 2007.（李晓梅.数值并行算法与软件[M].北京：科学出版社，2007.）