Progressive Load Balancing of Asynchronous Algorithms
Author/Presenters
Event Type
Workshop
Applications
Architectures
Graph Algorithms
SIGHPC Workshop
TimeMonday, November 13th10:55am -
11:20am
Location507
DescriptionSynchronisation in the presence of noise and hardware
performance variability is a key challenge that prevents
applications from scaling to large problems and
machines. Using asynchronous or semi-synchronous
algorithms can help overcome this issue, but at the cost
of reduced stability or convergence rate. In this paper
we propose progressive load balancing to manage progress
imbalance in asynchronous algorithms dynamically. In our
technique the balancing is done over time, not
instantaneously.
Using Jacobi iterations as a test case, we show that, with CPU performance variability present, this approach leads to higher iteration rate and lower progress imbalance between parts of the solution space. We also show that under these conditions the balanced asynchronous method outperforms synchronous, semi-synchronous and totally asynchronous implementations in terms of time to solution.
Using Jacobi iterations as a test case, we show that, with CPU performance variability present, this approach leads to higher iteration rate and lower progress imbalance between parts of the solution space. We also show that under these conditions the balanced asynchronous method outperforms synchronous, semi-synchronous and totally asynchronous implementations in terms of time to solution.
Author/Presenters
