Type
Text
Type
Dissertation
Advisor
Deng, Yuefan | Lindquist, William Brent | Mitchell, Joseph S.B.McGuigan, Michael | Chen, Dong
Date
2011-12-01
Keywords
interconnection network, interlaced bypass torus, optimization, parallel computer, parallel computing, task mapping | Applied mathematics
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/70917
Publisher
The Graduate School, Stony Brook University: Stony Brook, NY.
Format
application/pdf
Abstract
This dissertation focuses on two aspects of parallel computing, i.e. | development and applications of parallel computers. First, we introduce a new technique by strategically interlacing bypass rings to torus (iBT network) for generating more efficient grid-like interconnection networks. Second, we derive an algebraic formulation of mapping tasks to parallel computers with complex network architectures for realizing their potentials. Compared to the widely adopted mesh and torus network topologies, our new iBT network has many superior characteristics: (1) its network diameter and average node-to-node distances are significantly reduced; (2) the simplicity of a grid-like layout is preserved; (3) it outperforms other bypass torus networks; and (4) it has far more flexible network sizes. A mathematical model is further devised to analyze the dependencies of the iBT network diameters on bypass schemes, thus enabling discovery of a class of the most efficient bypass schemes for a given node degree and network size. Additionally, a pipelined broadcast algorithm for the all-port nodal ability is present and analyzed, demonstrating the collective performance. The iBT networks is finding broad applications in designing higher-dimensional and larger-scale parallel computers as the 3-D torus networks have done for parallel computers with fewer processors. We have developed a new formulation for the task mapping in efficient application of a parallel computer with complex networks such as iBT. The fact that the supply matrix, characterizing the network topologies, exhibits enormous symmetries allows us the transformation of the demand matrix measuring the communication demands of applications to derive a hop-byte objective function in terms of the eigen properties. This new eigen-based formulation dramatically reduces the complexity of finding the solutions for the objective functions from the conventional and widely adopted graph theory-based formulations. Numerical experiments with simulated annealing demonstrate such gains. This formulation enables solution of critical task mapping problems on large-scale parallel computers. | 95 pages
Recommended Citation
Zhang, Peng, "A Methodology for Design and Applications of Parallel Computers" (2011). Stony Brook Theses and Dissertations Collection, 2006-2020 (closed to submissions). 125.
https://commons.library.stonybrook.edu/stony-brook-theses-and-dissertations-collection/125