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
Document type :
Complete list of metadatas
Contributor : Sylvain Collange <>
Submitted on : Monday, June 5, 2017 - 5:45:29 PM
Last modification on : Thursday, November 15, 2018 - 11:58:57 AM
Long-term archiving on : 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