Doctoral Defense

Task Scheduling and Flow Routing for Parallel Processing in a Variety of Network Topologies

Yang Liu

July 14, 2017
2:00PM
Light Engineering room 250
Advisor: Thomas Robertazzi

Parallel Processing techniques for modern networks has gained increasing research interest as with the rapid growth of data intensive computing applications. Two types of tasks are widely concerned in this context: (a) divisible computing tasks and (b) data transfer task. For divisible computing tasks, the major research focus lies in analyzing how to wisely divide and place the sub-tasks on different processors, so that goals like overall tasks completion time, communication overhead, etc. are optimized. The nature of this computing task, network topology, processing speed and link speed are all necessary factors to be taken into account. For data transfer tasks, minimizing the completion time of tasks is the primary goal. It is critical to jointly analyze both flow routing and bandwidth allocation, to generate the optimal routing and scheduling strategy.

In this dissertation, for type (a) tasks, we specifically study the problem of large scale matrix multiplication on heterogeneous processor platforms. By utilizing the property of matrix multiplication, we find a new task division method: layer based partition, in contrast to the traditional rectangular partition method. We show that our layer based partition achieves much smaller communication overhead than traditional method, while keeping almost the same tasks completion time. We further analyze how to apply layer based partition in tree network and mesh. For tree network we provide analytical solutions. For mesh network, we formulate this problem as a mixed integer programming problem, where we provide a 3-phase algorithm and a heuristic to solve it. For type (b) tasks, we mainly focus on studying 3 problems: (1) multi-path coflow routing and bandwidth allocation in fat tree data center network; (2) single-path coflow routing and bandwidth allocation in fat tree network; (3) the trade-off analysis: energy-aware multi- path scheduling. We build convex optimization model for each of these problem, and provide corresponding solving schemes. For (3) we introduce an iterative solver. Extensive simulation results verify the performances of our proposed approaches.