Repository logo

Termination detection for fine-grained message-passing architectures

Accepted version


Conference Object

Change log


Naylor, Matthew 
Mokhov, Andrey 
Thomas, David 
Beaumont, Jonathan 


Barrier primitives provided by standard parallel programming APIs are the primary means by which applications implement global synchronisation. Typically these primitives are fully-committed to synchronisation in the sense that, once a barrier is entered, synchronisation is the only way out. For message-passing applications, this raises the question of what happens when a message arrives at a thread that already resides in a barrier. Without a satisfactory answer, barriers do not interact with message-passing in any useful way.

In this paper, we propose a new refutable barrier primitive that combines with message-passing to form a simple, expressive, efficient, well-defined API. It has a clear semantics based on termination detection, and supports the development of both globally-synchronous and asynchronous parallel applications.

To evaluate the new primitive, we implement it in a prototype large-scale message-passing machine with 49,152 RISC-V threads distributed over 48 FPGAs. We show that hardware support for the primitive leads to a highly-efficient implementation, capable of synchronisation rates that are an order-of-magnitude higher than what is achievable in software. Using the primitive, we implement synchronous and asynchronous versions of a range of applications, observing that each version can have significant advantages over the other, depending on the application. Therefore, a barrier primitive supporting both styles can greatly assist the development of parallel programs.



4606 Distributed Computing and Systems Software, 46 Information and Computing Sciences, 4612 Software Engineering

Journal Title

2020 IEEE 31st International Conference on Application-specific Systems, Architectures and Processors (ASAP)

Conference Name

The 31st IEEE International Conference on Application-specific Systems, Architectures and Processors

Journal ISSN


Volume Title




All rights reserved
Engineering and Physical Sciences Research Council (EP/N031768/1)
Funded by EPSRC grant EP/N031768/1 (POETS project)
Is supplemented by: