Realizing multioperations and multiprefixes in Thick Control Flow processors

Multioperations are primitives of parallel computation by which threads perform reductions, e.g., additions, on values provided by multiple threads into a single value in a constant number of steps. Multiprefixes resemble multioperations, but return to each participating thread a cumulative ordered...

Full description

Saved in:
Bibliographic Details
Published in:Microprocessors and microsystems 2023-04, Vol.98, p.104807, Article 104807
Main Authors: Forsell, Martti, Roivainen, Jussi, Leppänen, Ville, Träff, Jesper Larsson
Format: Article
Language:English
Subjects:
Multioperation
Multiprefix
Multiprocessor architecture
Parallel computing
Thick Control Flow
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Multioperations are primitives of parallel computation by which threads perform reductions, e.g., additions, on values provided by multiple threads into a single value in a constant number of steps. Multiprefixes resemble multioperations, but return to each participating thread a cumulative ordered reduction of all preceding values. Algorithmically, multioperations and multiprefixes can speed up parallel programs by a logarithmic factor over their single operation counterparts. In this paper, we introduce architectural techniques for realizing multioperations and multiprefixes in so-called Thick Control Flow (TCF) processors. A thick control flow is a computational construct that bundles homogeneous threads following the same control path into a data parallel entity. Our proposed processors optimized for executing TCFs feature a frontend-backend structure with low-latency processing of TCF-common computations and high-throughput execution of data parallel parts. Our solution relies on step caches and equally sized multioperation scratchpads, while on the memory side, we make use of active memory modules. The idea is to compute partial results in backend units to reduce the traffic to the referred shared memory location. The final multioperation result is then computed in the active memory unit of the target memory module. Multiprefixes use an additional phase where the final results are computed with a help of backend-wise prefixes. According to our evaluation, the proposed techniques indeed speed up certain N data element algorithms by a logN factor with reasonable hardware costs.
ISSN:0141-9331
1872-9436
DOI:10.1016/j.micpro.2023.104807