Refereed journal article or data article (A1)
Realizing multioperations and multiprefixes in Thick Control Flow processors
List of Authors: Forsell Martti, Roivainen Jussi, Leppänen Ville, Träff Jesper L.
Publisher: Elsevier B.V.
Publication year: 2023
Journal: Microprocessors and Microsystems
Journal name in source: Microprocessors and Microsystems
Article number: 104807
Volume number: 98
DOI: http://dx.doi.org/10.1016/j.micpro.2023.104807
URL: https://doi.org/10.1016/j.micpro.2023.104807
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/179035044
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 log N factor with reasonable hardware costs.
Downloadable publication This is an electronic reprint of the original article. |