Optimizing non-coalesced memory access for irregular applications with GPU computing

Ran ZHENG; Yuan-dong LIU; Hai JIN

doi:10.1631/FITEE.1900262

Your Location：

Home >

Browse articles >

Optimizing non-coalesced memory access for irregular applications with GPU computing

Regular Papers | Updated：2022-05-19

- Optimizing non-coalesced memory access for irregular applications with GPU computing
- 运用GPU计算面向非规则应用的非合并内存访问优化
- Frontiers of Information Technology & Electronic Engineering Vol. 21, Issue 9, Pages: 1285-1301(2020)
- Affiliations：
  
  National Engineering Research Center for Big Data Technology and System, Huazhong University of Science and Technology, Wuhan 430074, China
  Services Computing Technology and System Lab, Huazhong University of Science and Technology, Wuhan 430074, China
  Cluster and Grid Computing Lab, Huazhong University of Science and Technology, Wuhan 430074, China
  School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China
- Author bio：
  
  [ "" ]
  [ "Ran ZHENG received her MS and PhD degrees from Huazhong University of Science and Technology (HUST), China in 2002 and 2006, respectively. She is currently an Associate Professor of Computer Science and Engineering at HUST. Her research interests include distributed computing, cloud computing, high-performance computing, and their applications. E-mail: 1531364016@qq.com" ]
  [ "", "Hai JIN is a Cheung Kung Scholars Chair Professor of Computer Science and Engineering at Huazhong University of Science and Technology (HUST) in China. He received his PhD degree in Computer Engineering from HUST in 1994. In 1996, he was awarded a German Academic Exchange Service fellowship to visit the Technical University of Chemnitz in Germany. He worked at the University of Hong Kong between 1998 and 2000, and was a visiting scholar at the University of Southern California between 1999 and 2000. He was supported by the National Science Fund for Distinguished Young Scholars in 2001. He is the Chief Scientist of ChinaGrid, the largest grid computing project in China, and the Chief Scientist of National 973 Basic Research Program Project of Virtualization Technology of Computing System, and Cloud Security. He is an editorial board member of Frontiers of Information Technology & Electronic Engineering. His research interests include computer architecture, virtualization technology, cluster computing and cloud computing, peer-to-peer computing, network storage, and network security. E-mail: hjin@hust.edu.cn" ]
- Funds：
- DOI：10.1631/FITEE.1900262
  CLC： TP319
- Received：24 May 2019，
  
  Revised：2020-;8-10，
  
  Published：2020-09
- Accepted：
Scan QR Code
Ran ZHENG, Yuan-dong LIU, Hai JIN. Optimizing non-coalesced memory access for irregular applications with GPU computing[J]. Frontiers of Information Technology & Electronic Engineering, 2020, 21(9): 1285-1301.
DOI：

Ran ZHENG, Yuan-dong LIU, Hai JIN. Optimizing non-coalesced memory access for irregular applications with GPU computing[J]. Frontiers of Information Technology & Electronic Engineering, 2020, 21(9): 1285-1301. DOI： 10.1631/FITEE.1900262.

摘要

通用图形处理器（GPGPU）可大大提升规则应用的计算性能。然而，很多应用中存在非规则内存访问模式，大大限制了GPU的性能优势。近年来，一些研究提出解决方案来移除静态非规则内存访问。然而，利用软件消除动态非规则内存访问仍然面临严峻挑战。本文提出一种纯软件解决方案用于消除动态非规则内存访问，尤其是间接内存访问，无需硬件扩展和离线分析。提出数据重组和索引重定向以减少内存访问次数，从而提高GPU内核性能。为提高数据重组效率，卸载重组数据操作至GPU以降低开销并传输数据。通过并发执行数据重组和数据处理内核的统一计算设备架构（CUDA）流，可降低数据重组开销。完成这些优化后，相比于CUSPARSE基准测试，使用该方法GPU内核的内存数据传输减少了16.7%-50%；同时，NVIDIA Tesla P4 GPU上的内核性能提高了9.64%-34.9%。

Abstract

General purpose graphics processing units (GPGPUs) can be used to improve computing performance considerably for regular applications. However

irregular memory access exists in many applications

and the benefits of graphics processing units (GPUs) are less substantial for irregular applications. In recent years

several studies have presented some solutions to remove static irregular memory access. However

eliminating dynamic irregular memory access with software remains a serious challenge. A pure software solution without hardware extensions or offline profiling is proposed to eliminate dynamic irregular memory access

especially for indirect memory access. Data reordering and index redirection are suggested to reduce the number of memory transactions

thereby improving the performance of GPU kernels. To improve the efficiency of data reordering

an operation to reorder data is offloaded to a GPU to reduce overhead and thus transfer data. Through concurrently executing the compute unified device architecture (CUDA) streams of data reordering and the data processing kernel

the overhead of data reordering can be reduced. After these optimizations

the volume of memory transactions can be reduced by 16.7%-50% compared with CUSPARSE-based benchmarks

and the performance of irregular kernels can be improved by 9.64%-34.9% using an NVIDIA Tesla P4 GPU.

关键词

Keywords

references

M Alandoli , , , M Shehab , , , M Al-Ayyoub , , , 等 . . Using GPUs to speed-up FCM-based community detection in social networks . . Proc 7 th Int Conf on Computer Science and Information Technology , , 2016 . . p.1 - - 6 . . DOI: 10.1109/CSIT.2016.7549467 http://doi.org/10.1109/CSIT.2016.7549467 . .

MM Baskaran , , , R Bordawekar . . Optimizing Sparse Matrix-Vector Multiplication on GPUs Using Compile-Time and Run-Time Strategies . . IBM Research Report , , 2008 . . RC24704 (W0812-047) . .

MM Baskaran , , , U Bondhugula , , , S Krishnamoorthy , , , 等 . . A compiler framework for optimization of affine loop nests for GPGPUs . . Proc 22 nd Annual Int Conf on Supercomputing , , 2008 . . p.225 - - 234 . . DOI: 10.1145/1375527.1375562 http://doi.org/10.1145/1375527.1375562 . .

P Bhatotia , , , R Rodrigues , , , A Verma . . Shredder: GPU-accelerated incremental storage and computation . . Proc 10 th USENIX Conf on File and Storage Technologies , , 2012 . . p.14 . .

M Burtscher , , , R Nasre , , , K Pingali . . A quantitative study of irregular programs on GPUs . . Proc IEEE Int Symp on Workload Characterization , , 2012 . . p.141 - - 151 . . DOI: 10.1109/IISWC.2012.6402918 http://doi.org/10.1109/IISWC.2012.6402918 . .

A Danalis , , , G Marin , , , C McCurdy , , , 等 . . The scalable heterogeneous computing (SHOC) benchmark suite . . Proc 3 rd Workshop on General-Purpose Computation on Graphics Processing Units , , 2010 . . p.63 - - 74 . . DOI: 10.1145/1735688.1735702 http://doi.org/10.1145/1735688.1735702 . .

TA Davis , , , YF Hu . . The university of Florida sparse matrix collection . . ACM Trans Math Softw , , 2011 . . 38 ( ( 1 ): ): 1 DOI: 10.1145/2049662.2049663 http://doi.org/10.1145/2049662.2049663 . .

WS Fan , , , B Wang , , , JC Paul , , , 等 . . An octree-based proxy for collision detection in large-scale particle systems . . Sci China Inform Sci , , 2013 . . 56 ( ( 1 ): ): 1 - - 10 . . DOI: 10.1007/s11432-012-4616-5 http://doi.org/10.1007/s11432-012-4616-5 . .

WW Fung , , , I Sham , , , G Yuan , , , 等 . . Dynamic warp formation and scheduling for efficient GPU control flow . . Proc 40 th Annual IEEE/ACM Int Symp on Microarchitecture , , 2007 . . p.407 - - 420 . . DOI: 10.1109/MICRO.2007.12 http://doi.org/10.1109/MICRO.2007.12 . .

S Lee , , , S Min , , , R Eigenmann . . OpenMP to GPGPU: a compiler framework for automatic translation and optimization . . ACM SIGPLAN Not , , 2009 . . 44 ( ( 4 ): ): 101 - - 110 . . DOI: 10.1145/1594835.1504194 http://doi.org/10.1145/1594835.1504194 . .

KL Li , , , WD Yang , , , KQ Li . . Performance analysis and optimization for SpMV on GPU using probabilistic modeling . . IEEE Trans Parall Distrib Syst , , 2015 . . 26 ( ( 1 ): ): 196 - - 205 . . DOI: 10.1109/TPDS.2014.2308221 http://doi.org/10.1109/TPDS.2014.2308221 . .

KL Li , , , WD Yang , , , KQ Li . . A hybrid parallel solving algorithm on GPU for quasi-tridiagonal system of linear equations . . IEEE Trans Parall Distrib Syst , , 2016 . . 27 ( ( 10 ): ): 2795 - - 2808 . . DOI: 10.1109/TPDS.2016.2516988 http://doi.org/10.1109/TPDS.2016.2516988 . .

JY Meng , , , D Tarjan , , , K Skadron . . Dynamic warp subdivision for integrated branch and memory divergence tolerance . . ACM SIGARCH Comput Arch News , , 2010 . . 38 ( ( 3 ): ): 235 - - 246 . . DOI: 10.1145/1816038.1815992 http://doi.org/10.1145/1816038.1815992 . .

R Mokhtari , , , M Stumm . . BigKernel-high performance CPU-GPU communication pipelining for big data-style applications . . Proc IEEE 28 th Int Parallel and Distributed Processing Symp , , 2014 . . p.819 - - 828 . . DOI: 10.1109/IPDPS.2014.89 http://doi.org/10.1109/IPDPS.2014.89 . .

BP Pickering , , , CW Jackson , , , TRW Scogland , , , 等 . . Directive-based GPU programming for computational fluid dynamics . . Comput Fluids , , 2015 . . 114 242 - - 253 . . DOI: 10.1016/j.compfluid.2015.03.008 http://doi.org/10.1016/j.compfluid.2015.03.008 . .

A Sabne , , , P Sakdhnagool , , , R Eigenmann . . Scaling large-data computations on multi-GPU accelerators . . Proc 27 th Int ACM Conf on Supercomputing , , 2013 . . p.443 - - 454 . . DOI: 10.1145/2464996.2465023 http://doi.org/10.1145/2464996.2465023 . .

W Song , , , D Wu , , , R Wong , , , 等 . . A real-time interactive data mining and visualization system using parallel computing . . Proc 10 th Int Conf on Digital Information Management , , 2015 . . p.10 - - 13 . . DOI: 10.1109/ICDIM.2015.7381890 http://doi.org/10.1109/ICDIM.2015.7381890 . .

M Sourouri , , , T Gillberg , , , SB Baden , , , 等 . . Effective multi-GPU communication using multiple CUDA streams and threads . . Proc 20 th IEEE Int Conf on Parallel and Distributed Systems , , 2014 . . p.981 - - 986 . . DOI: 10.1109/PADSW.2014.7097919 http://doi.org/10.1109/PADSW.2014.7097919 . .

SZ Ueng , , , M Lathara , , , SS Baghsorkhi , , , 等 . . CUDA-Lite: reducing GPU programming complexity . . Proc 21 st Int Workshop on Languages and Compilers for Parallel Computing , , 2008 . . p.1 - - 15 . . DOI: 10.1007/978-3-540-89740-8_1 http://doi.org/10.1007/978-3-540-89740-8_1 . .

L Wang , , , R Spurzem , , , S Aarseth , , , 等 . . NBODY6++GPU: ready for the gravitational million-body problem . . Mon Not R Astron Soc , , 2015 . . 450 ( ( 4 ): ): 4070 - - 4080 . . DOI: 10.1093/mnras/stv817 http://doi.org/10.1093/mnras/stv817 . .

Y Wang , , , A Davidson , , , YC Pan , , , 等 . . Gunrock: a high-performance graph processing library on the GPU . . ACM SIGPLAN Not , , 2015 . . 50 ( ( 8 ): ): 265 - - 266 . . DOI: 10.1145/2858788.2688538 http://doi.org/10.1145/2858788.2688538 . .

B Wu , , , ZJ Zhao , , , EZ Zhang , , , 等 . . Complexity analysis and algorithm design for reorganizing data to minimize non-coalesced memory accesses on GPU . . ACM SIGPLAN Not , , 2013 . . 48 ( ( 8 ): ): 57 - - 68 . . DOI: 10.1145/2517327.2442523 http://doi.org/10.1145/2517327.2442523 . .

Y Yang , , , P Xiang , , , JF Kong , , , 等 . . A GPGPU compiler for memory optimization and parallelism management . . ACM SIGPLAN Not , , 2010 . . 45 ( ( 6 ): ): 86 - - 97 . . DOI: 10.1145/1809028.1806606 http://doi.org/10.1145/1809028.1806606 . .

EZ Zhang , , , YL Jiang , , , ZY Guo , , , 等 . . On-the-fly elimination of dynamic irregularities for GPU computing . . ACM SIGARCH Comput Arch News , , 2011 . . 39 ( ( 1 ): ): 369 - - 380 . . DOI: 10.1145/1961295.1950408 http://doi.org/10.1145/1961295.1950408 . .

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.

⁰