Synchronization in graph analysis algorithms on the Partially Ordered Event-Triggered Systems many-core architecture
Authors
Tarawneh, G
Brown, AD
Publication Date
2022Journal Title
IET Computers and Digital Techniques
ISSN
1751-8601
Publisher
Institution of Engineering and Technology (IET)
Language
en
Type
Article
This Version
AO
VoR
Metadata
Show full item recordCitation
Rafiev, A., Yakovlev, A., Tarawneh, G., Naylor, M., Moore, S., Thomas, D., Bragg, G., et al. (2022). Synchronization in graph analysis algorithms on the Partially Ordered Event-Triggered Systems many-core architecture. IET Computers and Digital Techniques https://doi.org/10.1049/cdt2.12041
Abstract
Abstract: One of the key problems in designing and implementing graph analysis algorithms for distributed platforms is to find an optimal way of managing communication flows in the massively parallel processing network. Message‐passing and global synchronization are powerful abstractions in this regard, especially when used in combination. This paper studies the use of a hardware‐implemented refutable global barrier as a design optimization technique aimed at unifying these abstractions at the API level. The paper explores the trade‐offs between the related overheads and performance factors on a message‐passing prototype machine with 49,152 RISC‐V threads distributed over 48 FPGAs (called the Partially Ordered Event‐Triggered Systems platform). Our experiments show that some graph applications favour synchronized communication, but the effect is hard to predict in general because of the interplay between multiple hardware and software factors. A classifier model is therefore proposed and implemented to perform such a prediction based on the application graph topology parameters: graph diameter, degree of connectivity, and reconvergence metric. The presented experimental results demonstrate that the correct choice of communication mode, granted by the new model‐driven approach, helps to achieve 3.22 times faster computation time on average compared to the baseline platform operation.
Keywords
ORIGINAL RESEARCH
Sponsorship
Engineering and Physical Sciences Research Council (EP/N031768/1)
Identifiers
cdt212041
External DOI: https://doi.org/10.1049/cdt2.12041
This record's URL: https://www.repository.cam.ac.uk/handle/1810/335728
Rights
Licence:
http://creativecommons.org/licenses/by/4.0/
Statistics
Total file downloads (since January 2020). For more information on metrics see the
IRUS guide.