Doctoral Seminar: Meghriz Terzian

Speaker: Meghrig Terzian

Supervisor: Dr. H. Harutyunyan

Supervisory Committee:
Drs. D. Goswami, B Jaumard, M. R. Soleymani

Title:  Multicasting in 2D Torus Networks and a New Approach for Finding an OMP

Date: Thursday, March 10, 2016

Time: 10:15 a.m.

Place: EV 3.309

ABSTRACT

Multicast is message propagation from a source node to a number of destination nodes in a network, used in collaborative applications and parallel computing. When multicast communication is not efficient, it degrades the performance of collaborative applications and deteriorates the capabilities of supercomputers.

The main parameters for evaluating multicast are time and traffic, which are negatively correlated. Existing multicast algorithms are path based or tree based. Tree based multicast has high efficiency on both time and traffic.
On the latest list of the TOP500, the second fastest supercomputer Titan, a Cray XK7 system, uses a 3D torus topology. In addition, the third and fifth entries on the list, IBM BlueGene/Q Sequoia and Mira, respectively use 5D torus topology.

We propose 3-additive approximation algorithm for multicast time in wormhole-routed 2D torus networks. HMDIAG (Hybrid Modified DIAGonal) divides the 2D torus into four 2D meshes and performs preprocessing at the source node to create the Diagonal Paths (DP), along which the message is sent in each mesh. At the source node and every intermediate node, another process is performed to send the message to a subset of destination nodes along a path branching from the DP. HMDIAG is a tree based multicast algorithm that uses two startup times. Simulation results show that the multicast time, latency, and coefficient variation of multicast time of HMDIAG is better than TASNEM and Multipath-HCM.

Given a set of points Q = {q1, q2, … , qn} on a road network G = (V,E), an OMP is the point p that minimizes a cost function defined over the distances from p to all points in Q. There are two variants of this problem known as min-max and min-sum. A min-sum OMP minimizes the total travel distance of all points, while a min-max OMP minimizes the elapsed travel time. The query is widely used in location based services and games.

We propose a novel approach for finding Optimal Meeting Points (OMP) for a given query set Q on road networks. The algorithm is based on O(Q) A* searches, with much lower complexity than existing algorithms.