Shortest-path routing for optimal all-to-all personalized-exchange embedding on hierarchical hypercube networks

摘要

Hypercube (HC) networks (N=2~n) provide efficient communication for parallel-and-distributed computing (PDC) but the HC-based multi-processor (MP) system is costly and not scalable, while hierarchical hypercube (HHC) networks (N=2~n, n=2~m+m) are less expensive and more scalable. However, the traditional HHC-routing easily conflicts, especially when executing multiple tasks ( k ＞ 2~m nodes-per-task). In the past, the node-disjoint-path routing could be used to avoid the conflict but that reliable (S, D) routing limited S(source)=0. Later, the parallel N2N (node-to-node) disjoint-path was proposed for reliable routing but limited (m+1)/2 pairs-of-nodes. Therefore, this study proposes the generalized N2N shortest-path (SP) routing (with arbitrary S) and the parallel N2N SP-routing, based on our hypothesis "the shortest-path routing and the proper HHC-partitioning can avoid the HHC-conflict directly". Next, our innovation and contribution are 1. the CCD (grouping of cross dual-cube) partitioning to solve the HHC-conflict for k ≤ 2~(m+1) nodes-per-task, and 2. the SP-ATAPE (all-to-all personalized exchange) embedding on the HHC-MPs. The correctness of the SP-routing was proven and the ATAPE communication was experimented to validate our conflict solution. The ATAPE results confirmed that in any group the GCD mapping could make all tasks [k = 2~(m+1) nodes-per-task), synchronized with the same control, working without the conflict.