Synchronous and asynchronous implementations of relaxation algorithms for nonlinear network optimization

Emmanuel D. Chajakis, Stavros A. Zenios

Research output: Contribution to journalArticlepeer-review

15 Scopus citations

Abstract

We discuss a parallel dual relaxation algorithm for network optimization. Synchronous and asynchronous implementations of the algorithm are developed on a shared memory multiprocessor, the Alliant FX/8. Alternative designs for parallel computing that tradeoff synchronization delays with computations are proposed. Their performance is analyzed empirically with computational experiments. It is demonstrated that the most effective parallel implementation is an asynchronous one, for which speedup factors of up to 7.2 are achieved on an 8 processor system.

Original languageEnglish
Pages (from-to)873-894
Number of pages22
JournalParallel Computing
Volume17
Issue number8
DOIs
StatePublished - Oct 1991

Keywords

  • Nonlinear network optimization
  • parallel implementation
  • partitioning
  • relaxation algorithms
  • scheduling
  • shared memory multiprocessor
  • synchronization

Fingerprint

Dive into the research topics of 'Synchronous and asynchronous implementations of relaxation algorithms for nonlinear network optimization'. Together they form a unique fingerprint.

Cite this