Extending Parallel Computing with Constraint of Fixed Structure by Adjusting Graph

ABSTRACT

Adding the number of computing nodes is a common approach to achieving higher performance in a parallel computing system. However, with constraint of fixed system architecture and fixed algorithm structure, it is difficult to improve the performance of parallel computing only by extending its scale absolutely. To realize such extension with fixed structure, we analyze key factors from architecture and parallel task, which affect the scalability, and then use the weighted graph to model architecture as well as parallel task. Especially, focusing on the case that architecture graph and parallel task graph are homogeneous, we propose the extension method of graph similarity; for the case that architecture graph and parallel task graph are heterogeneous, a critical-path-unchanged scaling method is proposed. Actually, the above two extending methods do not change the graph's structure. They only adjust the node weight and edge-weight in the relevant graph. Furthermore, through mathematical derivation, some conclusions about the new scaling methods are drawn. Finally, in order to verify the effectiveness, some simulative experiments are conducted on the platform SimGrid. The experimental results show that the proposed methods can realize iso-speed-efficiency extension, and can guide practical extensions for parallel computing.

KEYWORDS:

• Algorithm and machine
• critical path
• extending method
• fixed structure
• graph model
• graph similarity
• parallel computing

Additional information

Funding

This work was supported by the National High-Tech Research and Development Plan of China [grant number 2009AA012201]; the National Natural Science Foundation of China [grant number 61462037], [grant number 61402244], [grant number 61272107], [grant number 61202173], [grant number 61103068]; the Natural Science Foundation of Jiangxi Province [grant number 20151BAB207040], [grant number 20142BAB217014]; the Program of Shanghai Subject Chief Scientist [grant number 10XD1404400]; the Huawei Innovation Research Project [grant number IRP-2013-12-03]; the State Key Laboratory of High-end Server & Storage Technology [grant number 2014HSSA10].

Notes on contributors

Huanliang Xiong

HuanLiang Xiong was born in 1977 and received his MS degree from Nanchang University in 2006. Now he is a PhD candidate in the Department of Computer Science and Technology, Tongji University, China. His research interests are focused on parallel distributed processing and cloud computing.

E-mail: [email protected]

Guosun Zeng

Guosun Zeng was born in 1964 and received his BS, MS, and PhD degrees in computer software and application all from the Department of Computer Science and Engineering, Shanghai Jiao Tong University, China. Currently, he is working in Tongji University as a faculty of the Department of Computer Science and Technology, and a supervisor of PhD candidates in computer software and theory. He has published more than 90 papers in national or international key journals such as Science in China, Chinese Journal of Computers, and Journal of Software.

E-mail: [email protected]

Chunling Ding

Chunling Ding obtained her Master's degree from Tongji University. Currently she is working in Tongji University as a faculty of the Department of Computer Science and Technology. Her research interests are focused on parallel distributed processing and cloud computing.

E-mail: [email protected]

Canghai Wu

Canghai Wu was born in 1979 and received her Master's degree from Jiangxi Normal University in 2007. Currently, she is a lecturer in the Software College, Jiangxi Agricultural University, China. Her main research interests are focused on parallel distributed processing and cloud computing.

E-mail: [email protected]

Wei Wang

Wei Wang was born in 1979 and received his PhD degree in computer software and theory from the Department of Computer Science and Technology, Tongji University, China. Currently, he is working in Tongji University as a faculty of the Department of Computer Science and Technology. His research interests include mobile computing, cloud computing, and information security. He was awarded R. L. Zhang Scholarship and HP Chinese Best Student Scholarship in 2006. In 2007, he was granted IBM PhD Fellowship. He has published more than 30 papers in national or international key journals.

E-mail: [email protected]