Oregon State University

Calendar

Calendars

Event Details

PhD Final Oral Examination – Omar Alsaleh


Thursday, December 5, 2013 11:00 AM - 1:00 PM

One-to-Many Node Disjoint Paths Routing in Generalized Hypercube, Dense Gaussian, and Hexagonal Mesh Networks
Routing from a single source node to multiple destination nodes using node disjoint paths (NDP) has many important applications in parallel systems. For example, if a source node wants to send distinct messages to distinct destination nodes, then the one-to-many NDP routing is useful.

Unlike parallel systems with shared-memory, each node in most of the current parallel systems is a standalone processing unit with a processor and memory. The nodes communicate with each other by passing messages using a standard message passing mechanism such as the Message Passing Interface (MPI). The probability of failure in delivering the messages between the nodes directly affects the computing performance. This probability increases as the number of nodes increases. Therefore, it is critical to find a set of mutually node disjoint paths in order to establish communication routes under such a faulty environment. Moreover, the one-to-many NDP routing increases throughput of the networks.

In this work, we provide some novel and efficient routing algorithms that construct a set of NDP from a single source node to the maximum number of destination nodes in three promising interconnection networks. They are Generalized Hypercube, dense Gaussian, and Hexagonal Mesh networks.

In Chapter two, two efficient algorithms that construct a set of NDP from a single source node to the maximum number of destination nodes in Generalized Hypercube networks are given. Also, the lower and upper bounds of the path length from the source node to any destination node are derived. Finally, some simulations of the algorithms are performed and the results show that in most cases the maximum path length is equal to the shortest distance plus one.

In Chapter three and Chapter four, efficient constant time complexity algorithms that construct a set of one-to-many NDP in dense Gaussian and Hexagonal Mesh networks are given, respectively. For the dense Gaussian network, the lower and upper bounds of the sum of the NDP lengths are derived. Also, via execution of the algorithm, it is shown that on average the sum of the lengths of NDP given by the algorithm is only about 10% more than the sum of the lengths of the shortest paths.

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


Kelley Engineering Center (campus map)
4107
Nicole Thompson
1 541 737 3617
Nicole.Thompson at oregonstate.edu
Sch Elect Engr/Comp Sci
This event appears on the following calendars: