This paper tackles the cache thrashing problem caused by the non-deterministic scheduling feature of bulk synchronous parallel (BSP) execution in GPUs. In the BSP model, threads can be executed and interleaved in any order before reaching a barrier synchronization point, which requires the entire working set to be in cache for maximum data reuse over time. However, it is not always possible to fit all the data in cache at once. Thus, we propose a locality-aware software throttling framework that throttles the number of active execution tasks, prevents cache thrashing, and enhances data reuse over time. Our locality-aware software throttling framework focuses on an important class of applications that operate on sparse matrices (graphs). These applications come from the domains of linear algebra, graph processing, machine learning and scientific simulation. Evaluated on over 200 real sparse matrices and graphs that suffer from cache thrashing in the Florida sparse matrix collection, our technique achieves an average of 2.01X speedup, a maximum of 6.45X speedup, and a maximum performance loss ≤5%.
References
2018
USENIX ATC
Locality-Aware Software Throttling for Sparse Matrix Operation on GPUs
Yanhao Chen, Ari B. Hayes, Chi Zhang, and
2 more authors
In Proceedings of the 2018 USENIX Conference on Usenix Annual Technical Conference, Jun 2018
This paper tackles the cache thrashing problem caused by the non-deterministic scheduling feature of bulk synchronous parallel (BSP) execution in GPUs. In the BSP model, threads can be executed and interleaved in any order before reaching a barrier synchronization point, which requires the entire working set to be in cache for maximum data reuse over time. However, it is not always possible to fit all the data in cache at once. Thus, we propose a locality-aware software throttling framework that throttles the number of active execution tasks, prevents cache thrashing, and enhances data reuse over time. Our locality-aware software throttling framework focuses on an important class of applications that operate on sparse matrices (graphs). These applications come from the domains of linear algebra, graph processing, machine learning and scientific simulation. Evaluated on over 200 real sparse matrices and graphs that suffer from cache thrashing in the Florida sparse matrix collection, our technique achieves an average of 2.01X speedup, a maximum of 6.45X speedup, and a maximum performance loss ≤5%.
@inproceedings{chenetalatc18,author={Chen, Yanhao and Hayes, Ari B. and Zhang, Chi and Salmon, Timothy and Zhang, Eddy Z.},title={Locality-Aware Software Throttling for Sparse Matrix Operation on GPUs},year={2018},isbn={9781931971447},publisher={USENIX Association},address={USA},booktitle={Proceedings of the 2018 USENIX Conference on Usenix Annual Technical Conference},pages={413–425},numpages={13},location={Boston, MA, USA},series={USENIX ATC '18}}