Yuxiang Gao

Type

Text

Type

Dissertation

Advisor

Deng, Yuefan | Xiangmin Jiao | Lindquist, Brent | Hong Qin.

Date

2010-12-01

Keywords

Applied Mathematics | eigen analysis, simulated annealing, symmetry, task mapping

Department

Department of Applied Mathematics and Statistics

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/70864

Publisher

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

Format

application/pdf

Abstract

Task mapping has been explored intensively by computer and computational scientists for the purposes of maximizing utilization of computing resources by reducing communication and load imbalance. Task mapping is known to be NP-complete as a combinatorial optimization problem and, thus, many efforts intending to search for optimal solutions are not succeeding. All proposed mapping models to date represent parallel computers and applications as graphs with the networking capability abstracted as a supply matrix whose entries represent the inter-node communication costs and the communication requirements of the sub-tasks abstracted as a demand matrix whose entries represent the inter-subtask communication loads. The model is to minimize the objective function, defined as the hop-bytes metric. However, this hop-bytes metric is always written as a sum of the element-by-element products of the network supply and application demand matrices. This native and somewhat naive approach completely neglects the enormous symmetries in most networks and many applications and thus requires a huge number of unnecessary optimization steps. This thesis proposes a new formulation to investigate static task assignment. We develop a new formulation, by aid of eigen-analysis, to alleviate this very shortcoming of the past models. As expected, our formulation helps reduce the optimization steps in finding solution of the objective function. The extent of the speedup is not easily obtainable through analytical means but numerical experiments of mapping a suite of benchmarks, HPCC and NPB, onto 3D torus networks demonstrated that the simulated annealing process converges substantially faster with our new simulation than with the standard graph theory-based ones.

Download

Share

COinS