TY - JOUR
T1 - Synchronous and asynchronous implementations of relaxation algorithms for nonlinear network optimization
AU - Chajakis, Emmanuel D.
AU - Zenios, Stavros A.
PY - 1991/10
Y1 - 1991/10
N2 - 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.
AB - 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.
KW - Nonlinear network optimization
KW - parallel implementation
KW - partitioning
KW - relaxation algorithms
KW - scheduling
KW - shared memory multiprocessor
KW - synchronization
UR - http://www.scopus.com/inward/record.url?scp=0026243515&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0026243515&partnerID=8YFLogxK
U2 - 10.1016/S0167-8191(05)80072-9
DO - 10.1016/S0167-8191(05)80072-9
M3 - Article
AN - SCOPUS:0026243515
SN - 0167-8191
VL - 17
SP - 873
EP - 894
JO - Parallel Computing
JF - Parallel Computing
IS - 8
ER -