Abstract
Through eigenanalysis of communication matrices, we develop a new objective function formulation for mapping tasks to parallel computers with cellular networks. This new formulation significantly speeds up the solution process through consideration of the symmetries in the supply matrix of a network and a transformation of the demand matrix of any application. The extent of the speedup is not easily obtainable through analytical means for most production networks. However, numerical experiments of mapping wave equations on 2D mesh onto 3D torus networks by simulated annealing demonstrate a far superior convergence rate and quicker escape from local minima with our new formulation than with the standard graph theory-based one.
Original language | English (US) |
---|---|
Pages (from-to) | 1727-1756 |
Number of pages | 30 |
Journal | Mathematics of Computation |
Volume | 83 |
Issue number | 288 |
DOIs | |
State | Published - 2014 |
Keywords
- Eigenanalysis
- Graph theory
- Large-scale optimization
- Quadratic programming
- Task mapping
ASJC Scopus subject areas
- Algebra and Number Theory
- Computational Mathematics
- Applied Mathematics