CWLP: coordinated warp scheduling and locality-protected cache allocation on GPUs

Yang ZHANG; Zuo-cheng XING; Cang LIU; Chuan TANG

doi:10.1631/FITEE.1700059

Your Location：

Home >

Browse articles >

CWLP: coordinated warp scheduling and locality-protected cache allocation on GPUs

Regular Papers | Updated：2022-05-19

- CWLP: coordinated warp scheduling and locality-protected cache allocation on GPUs
- CWLP：一种在GPU中协同的线程束调度和局部性保护的高速缓存分配策略
- Frontiers of Information Technology & Electronic Engineering Vol. 19, Issue 2, Pages: 206-220(2018)
- Affiliations：
  
  National Laboratory for Parallel and Distributed Processing, National University of Defense Technology, Changsha 410073, China
- Author bio：
  
  Yang ZHANG, E-mail: zhangyang@nudt.edu.cn
- Funds：
- DOI：10.1631/FITEE.1700059
  CLC： TP368.1
- Received：19 January 2017，
  
  Revised：2018-;2-14，
  
  Published：2018-02
- Accepted：
Scan QR Code
Yang ZHANG, Zuo-cheng XING, Cang LIU, et al. CWLP: coordinated warp scheduling and locality-protected cache allocation on GPUs[J]. Frontiers of Information Technology & Electronic Engineering, 2018, 19(2): 206-220.
DOI：

Yang ZHANG, Zuo-cheng XING, Cang LIU, et al. CWLP: coordinated warp scheduling and locality-protected cache allocation on GPUs[J]. Frontiers of Information Technology & Electronic Engineering, 2018, 19(2): 206-220. DOI： 10.1631/FITEE.1700059.

摘要

随着我们正在接近百亿亿次超级计算机的时代，一个拥有强大运算能力和低能耗的均衡的计算机系统变得越来越重要。GPUs是在最近投入运营的超级计算机中被广泛使用的加速器。它采用大规模多块程来隐藏长访存延迟，同时它拥有高能效。相对于其强大的运算能力，GPUs的每个流多核处理器只有几兆的片上资源。面向吞吐率的执行模型与它的高速缓存层次结构设计不匹配，使得GPUs缓存表现出较差的运行效率。由于片上存储器的严重缺少，受较差的缓存性能影响，GPU的计算能力急剧下降，限制了系统性能和能效。提出一种协同的线程束调度和局部性保护的缓存分配策略（CWLP），以充分利用数据局部性和隐藏延迟。首先，设计了一种基于指令PC的局部性保护方法（LPC）以提升GPU性能。使用一个基于PC的收集器收集每个高速缓存块的重用信息。在获取缓存块的动态重用信息后，采用一个智能缓存分配单元（PCAU），它结合了重用信息和LRU（最近最少使用）替换策略，以找到拥有最少局部性的缓存块并将其逐出。此外，局部性信息被线程束调度器用来实现一个智能的重排序策略，用以获取局部性和隐藏延迟。实验结果表明，CWLP能够提供高达19.8%的性能加速比和超过基准策略平均8.8%的性能提升。

Abstract

As we approach the exascale era in supercomputing

designing a balanced computer system with a powerful computing ability and low power requirements has becoming increasingly important. The graphics processing unit (GPU) is an accelerator used widely in most of recent supercomputers. It adopts a large number of threads to hide a long latency with a high energy efficiency. In contrast to their powerful computing ability

GPUs have only a few megabytes of fast on-chip memory storage per streaming multiprocessor (SM). The GPU cache is inefficient due to a mismatch between the throughput-oriented execution model and cache hierarchy design. At the same time

current GPUs fail to handle burst-mode long-access latency due to GPU's poor warp scheduling method. Thus

benefits of GPU's high computing ability are reduced dramatically by the poor cache management and warp scheduling methods

which limit the system performance and energy efficiency. In this paper

we put forward a coordinated warp scheduling and locality-protected (CWLP) cache allocation scheme to make full use of data locality and hide latency. We first present a locality-protected cache allocation method based on the instruction program counter (LPC) to promote cache performance. Specifically

we use a PC-based locality detector to collect the reuse information of each cache line and employ a prioritised cache allocation unit (PCAU) which coordinates the data reuse information with the time-stamp information to evict the lines with the least reuse possibility. Moreover

the locality information is used by the warp scheduler to create an intelligent warp reordering scheme to capture locality and hide latency. Simulation results show that CWLP provides a speedup up to 19.8% and an average improvement of 8.8% over the baseline methods.

关键词

Keywords

references

A Bakhoda , , , G Yuan , , , W Fung , , , 等 . . Analyzing CUDA workloads using a detailed GPU simulator . . ISPASS IEEE Int Symp on Performance Analysis of Systems and Software , , 2009 . . p.163 - - 174 . . DOI: 10.1109/ISPASS.2009.4919648 http://doi.org/10.1109/ISPASS.2009.4919648 . .

S Che , , , M Boyer , , , J Meng , , , 等 . . Rodinia: a benchmark suite for heterogeneous computing . . IISWC IEEE Int Symp on Workload Characterization , , 2009 . . p.44 - - 54 . . DOI: 10.1109/IISWC.2009.5306797 http://doi.org/10.1109/IISWC.2009.5306797 . .

J Chen , , , X Tao , , , Z Yang , , , 等 . . Guided region-based GPU scheduling: utilizing multi-thread parallelism to hide memory latency . . IEEE 27 th Int Symp on Parallel & Distributed Processing , , 2013 . . p.441 - - 451 . . DOI: 10.1109/IPDPS.2013.95 http://doi.org/10.1109/IPDPS.2013.95 . .

X Chen , , , L Chang , , , C Rodrigues , , , 等 . . Adaptive cache management for energy-efficient GPU computing . . Proc 47 th Annual IEEE/ACM Int Symp on Microarchitecture , , 2014 . . p.343 - - 355 . . DOI: 10.1109/MICRO.2014.11 http://doi.org/10.1109/MICRO.2014.11 . .

W Dally , , , F Labonte , , , A Das , , , 等 . . Merrimac: supercomputing with streams . . Proc ACM/IEEE Conf on Supercomputing , , 2003 . . Article 35 DOI: 10.1145/1048935.1050187 http://doi.org/10.1145/1048935.1050187 . .

Y Drew . . A closer look at GPUs . . Commun ACM , , 2008 . . 51 ( ( 10 ): ): 50 - - 57 . . DOI: 10.1145/1400181.1400197 http://doi.org/10.1145/1400181.1400197 . .

W Fang , , , B He , , , Q Luo , , , 等 . . Mars: accelerating mapreduce with graphics processors . . IEEE Trans Parall Distr Syst , , 2011 . . 22 ( ( 4 ): ): 608 - - 620 . . DOI: 10.1109/TPDS.2010.158 http://doi.org/10.1109/TPDS.2010.158 . .

M Gebhart , , , D Johnson , , , D Tarjan , , , 等 . . Energyefficient mechanisms for managing thread context in throughput processors . . Proc 38th Annual Int Symp Computer Architecture , , 2011 . . p.235 - - 246 . . DOI: 10.1145/2000064.2000093 http://doi.org/10.1145/2000064.2000093 . .

S Gupta , , , P Xiang , , , H Zhou . . Analyzing locality of memory references in GPU architectures . . Proc ACM SIGPLAN Workshop on Memory Systems Performance and Correctness , , 2013 . . Article 12 DOI: 10.1145/2492408.2492423 http://doi.org/10.1145/2492408.2492423 . .

M Harris . . Maxwell: the Most Advanced CUDA GPU Ever Made . . https://devblogs.nvidia.com/parallelforall/maxwell-most-advanced-cuda-gpu-ever-made https://devblogs.nvidia.com/parallelforall/maxwell-most-advanced-cuda-gpu-ever-made , , 2014 . . .

W Jia , , , K Shaw , , , M Martonosi . . MRPB: memory request prioritization for massively parallel processors . . IEEE 20 th Int Symp on High Performance Computer Architecture , , 2014 . . p.272 - - 283 . . DOI: 10.1109/HPCA.2014.6835938 http://doi.org/10.1109/HPCA.2014.6835938 . .

A Jog , , , O Kayiran , , , C Nachiappan , , , 等 . . OWL: cooperative thread array aware scheduling techniques for improving GPGPU performance . . ACM SIGARCH Comput Arch News , , 2013 . . 41 ( ( 1 ): ): 395 - - 406 . . DOI: 10.1145/2490301.2451158 http://doi.org/10.1145/2490301.2451158 . .

M Lee , , , S Song , , , J Moon , , , 等 . . Improving GPGPU resource utilization through alternative thread block scheduling . . IEEE 20 th Int Symp on High Performance Computer Architecture , , 2014 . . p.260 - - 271 . . DOI: 10.1109/HPCA.2014.6835937 http://doi.org/10.1109/HPCA.2014.6835937 . .

S Lee , , , A Arunkumar , , , C Wu . . CAWA: coordinated warp scheduling and cache prioritization for critical warp acceleration of GPGPU workloads . . Proc 42 nd Annual Int Symp on Computer Architecture , , 2015 . . p.515 - - 527 . . DOI: 10.1145/2872887.2750418 http://doi.org/10.1145/2872887.2750418 . .

V Narasiman , , , M Shebanow , , , CJ Lee , , , 等 . . Improving GPU performance via large warps and two-level warp scheduling . . Proc 44 th Annual IEEE/ACM Int Symp on Microarchitecture , , 2011 . . p.308 - - 317 . . DOI: 10.1145/2155620.2155656 http://doi.org/10.1145/2155620.2155656 . .

C Nugteren , , , G van den Braak , , , H Corporaal , , , 等 . . A detailed GPU cache model based on reuse distance theory . . IEEE 20 th Int Symp on High Performance Computer Architecture , , 2014 . . p.37 - - 48 . . DOI: 10.1109/HPCA.2014.6835955 http://doi.org/10.1109/HPCA.2014.6835955 . .

NVIDIA . . NVIDIA's next generation CUDA compute architecture: FERMI.v1.1 . . http://www.nvidia.com/content/PDF/fermi_white_papers/NVIDIA_Fermi_Compute_Architecture_Whitepaper.pdf http://www.nvidia.com/content/PDF/fermi_white_papers/NVIDIA_Fermi_Compute_Architecture_Whitepaper.pdf , , 2009 . . .

NVIDIA . . NVIDIA CUDA C Programming Guide v7.5 . . http://developer.nvidia.com/nvidia-gpu-computingdocumentation http://developer.nvidia.com/nvidia-gpu-computingdocumentation , , 2015 . . .

M Rhu , , , M Sullivan , , , J Leng , , , 等 . . A locality-aware memory hierarchy for energy-efficient GPU architectures . . Proc 46 th Annual IEEE/ACM Int Symp on Microarchitecture , , 2013 . . p.86 - - 98 . . DOI: 10.1145/2540708.2540717 http://doi.org/10.1145/2540708.2540717 . .

T Rogers , , , M O'Connor , , , T Aamodt . . Cache-conscious wavefront scheduling . . Proc 45 th Annual IEEE/ACM Int Symp on Microarchitecture , , 2012 . . p.72 - - 83 . . DOI: 10.1109/MICRO.2012.16 http://doi.org/10.1109/MICRO.2012.16 . .

T Rogers , , , M O'Connor , , , T Aamodt . . Divergence-aware warp scheduling . . Proc 46 th Annual IEEE/ACM Int Symp on Microarchitecture , , 2013 . . p.99 - - 110 . . DOI: 10.1145/2540708.2540718 http://doi.org/10.1145/2540708.2540718 . .

A Sethia , , , D Jamshidi , , , S Mahlke . . Mascar: speeding up GPU warps by reducing memory pitstops . . IEEE 21 st Int Symp on High Performance Computer Architecture , , 2015 . . p.174 - - 185 . . DOI: 10.1109/HPCA.2015.7056031 http://doi.org/10.1109/HPCA.2015.7056031 . .

X Xie , , , Y Liang , , , G Sun , , , 等 . . An efficient compiler framework for cache bypassing on GPUs . . IEEE/ACM Int Conf on Computer-Aided Design , , 2013 . . p.516 - - 523 . . DOI: 10.1109/ICCAD.2013.6691165 http://doi.org/10.1109/ICCAD.2013.6691165 . .

X Xie , , , Y Liang , , , Y Wang , , , 等 . . Coordinated static and dynamic cache bypassing for GPUs . . IEEE 21 st Int Symp on High Performance Computer Architecture , , 2015 . . p.76 - - 88 . . DOI: 10.1109/HPCA.2015.7056023 http://doi.org/10.1109/HPCA.2015.7056023 . .

X Xie , , , Y Liang , , , X Li , , , 等 . . Enabling coordinated register allocation and thread-level parallelism optimization for GPUs . . IEEE/ACM Int Symp on Microarchitecture , , 2017 . . p.395 - - 406 . . DOI: 10.1109/TC.2017.2776272 http://doi.org/10.1109/TC.2017.2776272 . .

Y Zhang , , , Z Xing , , , L Zhou , , , 等 . . Locality protected dynamic cache allocation scheme on GPUs . . IEEE Trustcom/BigDataSE/ISPA , , 2017 . . p.1524 - - 1530 . . DOI: 10.1109/TrustCom.2016.0237 http://doi.org/10.1109/TrustCom.2016.0237 . .

Z Zheng . . Research on Key Technologies for Cache Power and Performance Optimization on Many-Core Heterogeneous Architecture . . PhD Thesis, National University of Defense Technology, Changsha, China (in Chinese) , , 2014 . . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰