基于改进图划分的异构并行计算模型设计

Design of Parallel Computing Based on Improved Graph Partitioning

摘要:

为了实现大规模计算机集群上的高效分布式并行计算,设计了一种基于改进图划分和量子遗传算法的异构节点并行计算模型；首先,介绍了传统图划分模型并分析了其不足,然后从图的有向性、通信开销计算和负载均衡度等方面对传统的图划分模型进行了改进,从而得到一个改进的图划分模型；最后,以最小化通信开销和优化资源负载均衡为目标,通过设计编码方案,在改进的图划分模型上提出了采用量子遗传算法获取最优任务划分方案的最优解；仿真实验表明:文中方法能有效实现任务的并行计算,与其它方法相比,具有较小的通信开销和较好的负载均衡度,具有很强的可行性。

Abstract:

In order to realize the effective distribute parallel computing in large computer group, a parallel computing model based on improved graph partitioning and quantum genetic algorithm was proposed. Firstly, the traditional graph partitioning model was analyzed and the defects were listed, then the graph partitioning model was improved by changing the direction, communication consumption and load balance and etc, then the improved graph partitioning was obtained. Finally, the coding scheme was designed by minimizing the communication consumption and optimizing resource load balance as the goal, the optimum solution was got by operating the quantum genetic algorithm. The simulation shows the method in this paper can realize task parallel computing, and compared with the other methods, it has less average locating error, and therefore, it has big feasibility.