Skip to Main content Skip to Navigation

Path list traversal: a new class of SIMT flow tracking mechanisms

Sylvain Collange 1 Nicolas Brunie 2
1 PACAP - Pushing Architecture and Compilation for Application Performance
Inria Rennes – Bretagne Atlantique , IRISA-D3 - ARCHITECTURE
Abstract : The SIMT execution model implemented in GPUs synchronizes groups of threads to run their common instructions on SIMD units. This model requires hardware or software mechanisms to keep track of control-flow divergence and convergence among threads. A new class of such algorithms is gaining popularity in the literature in the last few years. We present a new classification of these techniques based on their common characteristic, namely traversals of the control-flow graph based on lists of paths. We then compare the implementation cost on an FPGA of path lists and per-thread program counters within the Simty processor. The sorted list enables significantly better scaling starting from 8 threads per warp.
Keywords : GPU SIMT FPGA
Complete list of metadatas
Contributor : Caroline Collange <>
Submitted on : Monday, June 5, 2017 - 5:45:29 PM
Last modification on : Tuesday, February 25, 2020 - 8:08:10 AM
Document(s) archivé(s) le : Wednesday, September 6, 2017 - 12:23:32 PM


Files produced by the author(s)


  • HAL Id : hal-01533085, version 1


Sylvain Collange, Nicolas Brunie. Path list traversal: a new class of SIMT flow tracking mechanisms. [Research Report] RR-9073, Inria Rennes - Bretagne Atlantique. 2017. ⟨hal-01533085⟩



Record views


Files downloads