Near-Optimal Scalability: A Pratical Scalability Metric
Jun Chen · Chinese Journal of Computers · 2001
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.