Yang Liu

Type

Text

Type

Dissertation

Advisor

Hong, Sangjin | Robertazzi, Thomas G. | Tang, Wendy | Arkin, Esther.

Date

2017-08-01

Keywords

Communication overhead | Electrical engineering -- Computer engineering. | Data transfer tasks | Divisible computing tasks | Optmization | Parallel processing | Task completion time

Department

Department of Electrical Engineering.

Language

en_US

Source

This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree

Identifier

http://hdl.handle.net/11401/78164

Publisher

The Graduate School, Stony Brook University: Stony Brook, NY.

Format

application/pdf

Abstract

Parallel processing techniques for modern networks have gained increasing research interest with the rapid growth of data intensive computing applications. Two types of tasks are studied in this context: (a) data transfer tasks and (b) divisible computational tasks. 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. For divisible computational 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. In this dissertation, for type (a) tasks, we mainly focus on studying 3 problems: (1) multi-path coflow routing and bandwidth allocation in a FatTree data center network; (2) single-path coflow routing and bandwidth allocation in a FatTree network; (3) the trade-off analysis: energy-aware multi-path scheduling. We build programming models for each of these problems, and provide corresponding solving schemes. For (3) we introduce an iterative algorithm. Extensive simulation results verify the performances of our proposed approaches. For type (b) 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. | 172 pages

Download

Share

COinS