近优可扩展性:一种实用的可扩展性度量

Near-Optimal Scalability: A Pratical Scalability Metric

良好的可扩展性是并行算法和并行机设计人员追求的一项重要性能指标 .以往的可扩展模型都只是孤立地考虑了问题的某个侧面 ,比如某种性能或最大可利用资源 ,而没有从整体上进行权衡 .这些可扩展模型可以满足计算机研究人员的需要 ,因为他们关注于更高的效率和利用率 .但应用科学家更强调短小的执行时间 .文中提出的近优可扩展模型 ,它同时考虑了并行系统的效率和执行时间两个因素 .在一个典型 MPP上的两个算法实例分析表明 ,该可扩展模型不仅可以描述并行算法的可扩展能力 ,而且 ,当按照适当的可扩展曲线扩展时 ,可以使得执行时间接近最短 ,而效率不低 .这对算法和并行机的最优匹配有指导作用 ,同时有益于并行算法设计和改进 .

Scalability of parallel algorithms and parallel machines is one of the most important performance targets that the parallel algorithms designers and the high performance machine designers seek for. The previous scaling models, such as the iso efficiency scaling model, fixed time scaling model, and the iso speed scaling model and so on, only consider of one side of a problem, namely, one side performance or the whole utility of one kind of resources. They did not balance two important sides of the problem, just like the efficiency and the execution time of the combinations. The computer researchers focus on the higher efficiency and higher utility of resources, so the previous scaling models can satisfy their needs. But the application scientists have more interested in the shorter execution time and the previous scaling models are not enough for them. In this paper, we propose a near optimal scaling model. It considers both of the efficiency and execution time, and users can choose the appropriate constant factor according to their need and get the right scaling curve. At last we use this scalability analysis method to analyze the scalability of the combinations of some parallel algorithms and a typical massively parallel processing machine. Results show that this model can describe the scaling ability of the combinations of the parallel algorithms and the parallel machines. Results also show that it can be attained that the execution time is near to the shortest time and the efficiency is not too low when the system size and the problem size scales according to the right near optimal constant factor. It can guide the optimal matching of the parallel applications and the parallel machines, and is beneficial to the design and improvement of the parallel algorithms.