One-to-Many Node Disjoint Paths Routing in Generalized Hypercube and Gaussian Interconnection
Networks In parallel systems, the probability of faults becomes higher because of the continuous increase in the
number of cores. Therefore, it is critical to find mutually node disjoint paths (NDP) in order to establish communication routes under such a faulty environment. Routing from a single source node
to multiple destination nodes using NDP is called one-to-many NDP routing. This routing is fundamental and essential for ensuring fault tolerance in parallel systems. Also, it has many important
applications. For example in one-to-many personalized communications algorithm, a node sends different messages to different nodes, and so efficient algorithms can be designed based on NDP.

The cores in parallel systems are connected using interconnection networks. Some of the topologies are hypercube, mesh, torus, tree,
De Bruijn, etc. In this work, we consider the Generalized Hypercube (GH) and Gaussian interconnection networks. Unlike the existing types of hypercube, the GH interconnection networks support any
number of nodes. However, they possess a small average message distance and a low traffic density, thereby making it highly fault tolerant. The Gaussian interconnection networks can accommodate
more nodes with less communication latency while maintaining a regular grid-like structure and a low node degree.

In this work, we first design efficient algorithms that find NDP from a single source node to the maximum number of destination nodes
in GH and Gaussian interconnection networks. Then, we prove that these algorithms always return a solution. Also, we derive the lower bound and upper bound of the path lengths and the time
complexity of the algorithms. For the GH interconnection networks, we show via simulation that most of the time the upper bound is less than the theoretical upper bound.

Major Advisor: Bechir Hamdaoui Co-Major Advisor: Bella
Bose Committee: Huaping Liu Committee:
Eduardo Cotilla-Sanchez GCR: Harold Parks