A Method for Order/Degree Problem Based on Graph Symmetry and Simulated Annealing with MPI/OpenMP Parallelization
A Method for Order/Degree Problem Based on Graph Symmetry and Simulated Annealing with MPI/OpenMP Parallelization
复制标题
DOI：
10.1145/3293320.3293325
复制
发表时间：
2019-01
期刊：
影响因子：
--
通讯作者：
M. Nakao;H. Murai;M. Sato
中科院分区：
文献类型：
--
作者：
M. Nakao;H. Murai;M. Sato
各种系统中的网络拓扑结构，例如大规模数据中心、高性能计算系统和片上网络，与网络延迟密切相关。在图论中，通过将网络拓扑建模为无向图，可以将设计具有低延迟的网络拓扑定义为序/度问题（ODP）。本文提出了一种基于图对称性和模拟退火算法的ODP求解方法。该方法使网络拓扑结构具有对称性，从而提高了模拟退火算法的解搜索性能，大大减少了计算时间。所提出的方法被应用到几个问题，从一个国际竞争的ODP称为图高尔夫找到网络拓扑具有足够低的延迟。其中一个问题的计算速度提高了31.76倍。此外，为了减少计算时间，所提出的方法扩展到使用MPI和OpenMP的混合并行化。结果，在由400个CPU核心组成的20个计算节点上实现了209.80倍的最大速度提升。通过结合基于并行计算和混合并行化，实现了更快的性能。
The network topology in various systems, such as large-scale data centers, high-performance computing systems, and Network on Chip, is strongly related to network latency. Designing a network topology with low latency can be defined as an order/degree problem (ODP) in graph theory by modeling the network topology as an undirected graph. This study proposes a method for efficiently solving ODPs based on graph symmetry and simulated annealing (SA). This method makes the network topology symmetrical, thereby improving the solution search performance of SA and drastically reducing the calculation time. The proposed method is applied to several problems from an international competition for ODPs called Graph Golf to find network topologies with sufficiently low latency. The symmetry-based calculation achieves a speed up of 31.76 times for one of the problems. Furthermore, to reduce calculation time, the proposed method is extended to use hybrid parallelization with MPI and OpenMP. As a result, a maximum speed up of 209.80 times was achieved on 20 compute nodes consisting of 400 CPU cores. Even faster performance was achieved by combining the symmetry-based calculation and hybrid parallelization.