Type
Text
Type
Dissertation
Advisor
Robertazzi, Thomas G. | Hong, Sangjin | Milder, Peter | Badr, Hussein.
Date
2014-12-01
Keywords
Computer engineering
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/77497
Publisher
The Graduate School, Stony Brook University: Stony Brook, NY.
Format
application/pdf
Abstract
Though the divisible load scheduling problem has been studied for over two decades, the optimal solution for this problem can be obtained only in a few network topologies by the approach proposed in [6], which recursively equates multiple processing nodes in the network to a super processing node. The limitation of this equivalent approach lies in the fact that a node is required to finishing receiving load from its neighboring nodes simultaneously under this approach, such that linear equations can be established for all nodes in the network. However, the requirement is satisfied in very few network topologies. In this thesis, we address the problem of divisible load scheduling in network topologies where the requirement is not satisfied, and propose a novel analysis method, which formulates divisible load scheduling in these network topologies as a Maximum Finish Time Minimization (MFTM) problem. The MFTM problem minimizes the maximum finish time of all nodes in the network, and further analysis reveals that the MFTM problem can be transformed into the Finish Time Minimization (FTM) problem, which resembles the linear optimization problem, indicating an optimal solution by linear programming. With the novel analysis method, we study divisible load scheduling in a variety of network topologies, including mesh, torus, Gaussian network, the ring and multi-root tree, and propose the corresponding optimal algorithms. Besides, considering the high time complexity of the optimal algorithm in the mesh, torus and Gaussian network, we also propose a heuristic algorithm to reduce the time complexity. Extensive comparison results show that the heuristic algorithm achieves performance extremely close to the optimal algorithm algorithm, and both the optimal algorithm and heuristic algorithm significantly outperform previously proposed divisible scheduling algorithms in the studied network topologies.scheduling in network topologies where the requirement is not satisfied, and propose a novel analysis method, which formulates divisible load scheduling in these network topologies as a Maximum Finish Time Minimization (MFTM) problem. The MFTM problem minimizes the maximum finish time of all nodes in the network, and further analysis reveals that the MFTM problem can be transformed into the Finish Time Minimization (FTM) problem, which resembles the linear optimization problem, indicating an optimal solution by linear programming. With the novel analysis method, we study divisible load scheduling in a variety of network topologies, including mesh, torus, Gaussian network, the ring and multi-root tree, and propose the corresponding optimal algorithms. Besides, considering the high time complexity of the optimal algorithm in the mesh, torus and Gaussian network, we also propose a heuristic algorithm to reduce the time complexity. Extensive comparison results show that the heuristic algorithm achieves performance extremely close to the optimal algorithm algorithm, and both the optimal algorithm and heuristic algorithm significantly outperform previously proposed divisible scheduling algorithms in the studied network topologies. | 133 pages
Recommended Citation
Zhang, Zhemin, "A Novel Analysis Method for Parallel Processing" (2014). Stony Brook Theses and Dissertations Collection, 2006-2020 (closed to submissions). 3309.
https://commons.library.stonybrook.edu/stony-brook-theses-and-dissertations-collection/3309