1 of 1

IExchange: Asynchronous Communication and Termination Detection for Iterative Algorithms

Scientific Achievement

Interleaved asynchronous communication pattern for iterative computations in DIY eliminates global synchronization, boosting performance while being easier to use.

Significance and Impact

Irregular, imbalanced, iterative workloads can be accelerated using IExchange.

Research Details

Asynchronous communication and termination detection, interleaved with computation
Handles non-monotonic progress and/or unknown amount of global work.

Scalability: strong scaling plot shows IExchange 3X faster and 5X higher efficiency for particle tracing in thermal hydraulics application.

Work was performed at LBNL and ANL

Morozov, Peterka, Guo, Raj, Xu, Shen. IExchange: Asynchronous Communication and Termination Detection for Iterative Algorithms, LDAV ‘21.

Profiling: Left: synchronous Exchange, Right: asynchronous IExchange. Gantt charts show that the asynchronous method is several times faster because communication and computation are interleaved.

Performance: strong scaling plot shows iexchange over 100X faster in microparticle tracking application.

Modern data analytics—scientific visualization, machine learning, computational topology and geometry, graph analytics, uncertainty analysis—consist of iterative irregular data-dependent communication. To build these kinds of analyses at scale, needed are high-level asynchronous communication patterns that interleave frequent communication with computation and that do not assume a constant amount of global work nor monotonic progress toward completing the computations and that do not require a global synchronization on every iteration.

DIY’s new iexchange communication pattern meets these criteria.

DIY is our programming model and runtime for block-parallel analytics on distributed-memory machines. Its main abstraction is block parallelism: data are decomposed into blocks; blocks are assigned to processing elements (processes or threads); computation is described as iterations over these blocks, and communication between blocks is defined by reusable patterns. By expressing computation in this general form, the DIY runtime is free to optimize the movement of blocks between slow and fast memories and to concurrently execute blocks residing in memory with multiple threads. This enables the same program to execute in-core, out-of-core, serial, parallel, single-threaded, multithreaded, or combinations thereof. Blocks and their message queues are mapped onto processes and placed in memory/storage by the DIY runtime. Building on the block abstraction, communication patterns and other algorithms can be developed once and reused.

DIY’s existing synchronous exchange protocol expects the computation to be organized in a bulk-synchronous processing (BSP) pattern, where computations iterate over the block through a callback function that executes on each block, followed by a communication phase. The new iexchange() communication pattern is an example of relaxed BSP, programmed by the user in iterations of block callback executions as in the BSP model, but executed by the DIY runtime in asynchronous overlapping fashion.

The user does not need to program a global computation of the total amount of work, leaving termination detection to DIY. DIY implements termination detection in a protocol built on MPI-3 nonblocking collectives, making the loop iterations completely asynchronous. IExchange is available in the latest version of the open-source DIY software.

This work is published and will appear in the 2021 IEEE Large Data Analysis and Visualization (LDAV) Symposium, colocated with the IEEE VIS conference, October 2021 [1].

[1] Morozov, D., Peterka, T., Guo, H., Raj, M., Xu, J., Shen, H.-W.: IExchange: Asynchronous Communication and Termination Detection for Iterative Algorithms. Proceedings of IEEE LDAV’21 Symposium on Large Data Analysis and Visualization, New Orleans, LA, 2021.