An efficient parallel construction of optimal independent spanning trees on hypercubes

作者：Werapun Jeera****^*; Intakosum Sarun; Boonjing Veera

来源：Journal of Parallel and Distributed Computing, 2012, 72(12): 1713-1724.

DOI：10.1016/j.jpdc.2012.07.003

• ISTs (independent spanning trees)
• Double pointer jumping
• Hypercube interconnection networks
• Reliable and fault-tolerant broadcasting
• Parallel computers
• Multicomputers
• Multicores

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 IST. 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 not equal 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).

• 出版日期2012-12