An efficient parallel construction of optimal independent spanning trees on hypercubes

Reliable data broadcasting on parallel computers can be achieved by applying more than one independent spanning tree (IST). Using kk-IST-based broadcasting from root rr on an interconnection network (N=2k)(N=2k) provides kk-degree fault tolerance in broadcasting, while construction of optimal height kk-ISTs needs more time than that of one IST. In the past, most research focused on constructing kk ISTs on the hypercube QkQk, an efficient communication network. One sequential approach utilized the recursive feature of QkQk to construct kk ISTs working on a specific root (r)=0(r)=0 in O(kN)O(kN) time. Another parallel approach was introduced for generating kk ISTs with optimal height on QkQk, based on HDLS (Hamming Distance Latin Square), single pointer jumping, which is applied for a source (r)=0(r)=0 in O(k2)O(k2) time for successful broadcasting in O(k)O(k). For broadcasting from r≠0r≠0, those existing approaches require a special routine to reassign new nodes’ IDs for logical r=0r=0. This paper proposes a flexible and efficient parallel construction of kk ISTs with optimal height on QkQk, a generalized approach, for an arbitrary root (r=0,1,2,…r=0,1,2,…, or 2k−12k−1) in O(k)O(k) time. Our focus is to introduce the more efficient time (O(k))(O(k)) of preprocessing, based on double pointer jumping over O(k2)O(k2) of the HDLS approach. We also prove that our generalized parallel kk-IST construction (arbitrary rr) with optimal height on QkQk is correctly set in efficient O(k)O(k) time. Finally, experiments were performed by simulation to investigate the fault-tolerance effect in reliable broadcasting. Experimental results showed that our efficient ISTs yielded 10%–20% fault tolerance for successful broadcasting (on N=16–1024N=16–1024 PEs).

► We propose efficient and flexible parallel construction of kk ISTs on hypercubes for reliable broadcasting.
► Our approach is flexible for broadcasting from any root rr (=0,1,2,…=0,1,2,…, or 2k−12k−1), while there exists root r=0r=0.
► Our time complexity is efficient (O(k))(O(k)), based on double-pointer-jump preprocessing.
► Proof of correctness (optimal height) and time complexity analysis are provided.
► In experiments, our efficient ISTs yield 10%–20% fault tolerance in broadcasting.