Eigen analysis-based task mapping on parallel computers with cellular networks

Peng Zhang, Yuxiang Gao, Janet Fierson, Yuefan Deng

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)1727-1756
Number of pages30
JournalMathematics of Computation
Volume83
Issue number288
DOIs
StatePublished - 2014

Keywords

  • Eigenanalysis
  • Graph theory
  • Large-scale optimization
  • Quadratic programming
  • Task mapping

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Computational Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Eigen analysis-based task mapping on parallel computers with cellular networks'. Together they form a unique fingerprint.

Cite this