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 k-IST-based broadcasting from root r on an interconnection network (N = 2~k) provides k-degree fault tolerance in broadcasting, while construction of optimal height k-ISTs needs more time than that of one 1ST. In the past, most research focused on constructing k ISTs on the hypercube Q_k, an efficient communication network. One sequential approach utilized the recursive feature of Q_k to construct k ISTs working on a specific root (r) = 0 in O(kN) time. Another parallel approach was introduced for generating k ISTs with optimal height on Q_k, based on HDLS (Hamming Distance Latin Square), single pointer jumping, which is applied for a source (r) = 0 in O(K~2) time for successful broadcasting in O(k). For broadcasting from r≠ 0, those existing approaches require a special routine to reassign new nodes' IDs for logical r = 0. This paper proposes a flexible and efficient parallel construction of k ISTs with optimal height on Q_k, a generalized approach, for an arbitrary root (r = 0, 1, 2,..., or 2~k - 1) in O(k) time. Our focus is to introduce the more efficient time (O(k)) of preprocessing, based on double pointer jumping over O(k~2) of the HDLS approach. We also prove that our generalized parallel k-IST construction (arbitrary r) with optimal height on Q_k is correctly set in efficient 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-1024 PEs).