An efficient parallel construction of optimal independent spanning trees on hypercubes

Abstract: Reliable data broadcasting on parallel computers can be achieved by applying more than one independent spanning tree (IST). Using -IST-based broadcasting from root on an interconnection network provides -degree fault tolerance in broadcasting, while construction of optimal height -ISTs needs more time than that of one IST. In the past, most research focused on constructing ISTs on the hypercube , an efficient communication network. One sequential approach utilized the recursive feature of to construct ISTs working on a specific root in time. Another parallel approach was introduced for generating ISTs with optimal height on , based on HDLS (Hamming Distance Latin Square), single pointer jumping, which is applied for a source in time for successful broadcasting in . For broadcasting from , those existing approaches require a special routine to reassign new nodes’ IDs for logical . This paper proposes a flexible and efficient parallel construction of ISTs with optimal height on , a generalized approach, for an arbitrary root (, or ) in time. Our focus is to introduce the more efficient time of preprocessing, based on double pointer jumping over of the HDLS approach. We also prove that our generalized parallel -IST construction (arbitrary ) with optimal height on is correctly set in efficient 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  PEs). [Copyright &y& Elsevier]