Journal of Soft Computing and Information Technology

Journal of Soft Computing and Information Technology

Improving the inter-block synchronization methods in CUDA

Document Type : Persian Original Article

Authors
Abdorreza Savadi 1
Mohaddeseh salavatizadeh 2
Ali Riahi 2
1 Assistant Professor Department of Computer Engineering Faculty of Engineering Ferdowsi University Of Mashhad (FUM)
2 Computer Engineering Department, Ferdowsi University of Mashhad, Mashhad, Iran
Abstract
Abstract- The lack of explicit support for inter-block synchronization in the CUDA programming model has weakened performance in some applications. Therefore, in such applications, inter-block synchronization must be implemented in software. Lock-based and lock-free methods have been implemented for this problem. In lock-based synchronization, the execution time increases significantly with the increase in the number of blocks, and in the lock-free methods, there is a limit to the number of blocks. In this paper, two inter-block synchronization methods are proposed. The first method is lock-based, which reduces the impact of increasing the number of blocks on the execution time by grouping the blocks. The second proposed method is lock-free synchronization, which removes the limitation of the number of blocks in synchronization by creating a tree hierarchy of blocks. These methods were used for inter-block synchronization in Smith-Waterman and Bitonic algorithms. Experimental results show that the proposed lock-based method improves the execution time of the synchronization and recorded a speedup of 1.84 in the Smith-Waterman algorithm and 2.24 in the Bitonic sorting algorithm. Also, the results show that in the proposed lock-free method, any number of blocks can be synchronized by correctly choosing the number of levels of the tree hierarchy, and therefore the limitation of the number of blocks has been removed.
Keywords
GPU
CUDA
Inter-block Synchronization
Lock-based and Lock-free Synchronization
[1] Gao, Lan, Jing Wang, and Weigong Zhang. "Adaptive contention management for fine-grained synchronization on commodity GPUs." ACM Transactions on Architecture and Code Optimization (TACO), Vol.19, No.4, pp 1-21, 2022.
[2] Xi, Rong-Ping, et al. "An Asynchronous Parallel Implementation of Multilevel Fast Multipole Algorithm on GPU Cluster for 3D Electromagnetic Scattering Problems." In 2021 International Applied Computational Electromagnetics Society (ACES-China) Symposium. IEEE, 2021.
[3] Al-Mouhamed, Mayez A., Ayaz H. Khan, and Nazeeruddin Mohammad. "A review of CUDA optimization techniques and tools for structured grid computing." Computing, Vol.102, No.4, pp 977-1003, 2020
[4] Yan, Shengen, Guoping Long, and Yunquan Zhang. "StreamScan: fast scan algorithms for GPUs without global barrier synchronization.", In Proceedmorphings of the 18th ACM SIGPLAN symposium on Principles and practice of parallel programming, 2013.
[5] Dufrechou, Ernesto, Pablo Ezzatti, and Gabriel Usera. "Avoiding synchronization to accelerate a CFD solver in GPU." In 31st International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD). IEEE, 2019.
[6] Jørgensen, Jakob Rødsgaard, et al. "GPU-FAST-PROCLUS: A Fast GPU-parallelized Approach to Projected Clustering." Advances in Database Technology-EDBT, 2022.
[7] Li, Ruipeng, and Chaoyu Zhang. "Efficient parallel implementations of sparse triangular solves for GPU architectures." In Proceedings of the 2020 SIAM Conference on Parallel Processing for Scientific Computing. Society for Industrial and Applied Mathematics, 2020.
[8] NVIDIA, "CUDA C best practices guide", 2019
[9] Peng, Yuanfeng, Vinod Grover, and Joseph Devietti. "CURD: a dynamic CUDA race detector." ACM SIGPLAN Notices, Vol.53, No.4, pp 390-403, 2018.
[10] Bikov, Dusan, and Ilija Bouyukliev. "Parallel fast Walsh transform algorithm and its implementation with CUDA on GPUs." Cybernetics and Information Technologies, Vol.18, No.5, pp 21-43, 2018.
[11] Petrovič, Filip, et al. "A benchmark set of highly-efficient CUDA and OpenCL kernels and its dynamic autotuning with Kernel Tuning Toolkit." Future Generation Computer Systems, Vol.108, pp 161-177, 2020.
[12] Lopes, Paulo AC, et al. "Fast block distributed CUDA implementation of the Hungarian algorithm." Journal of Parallel and Distributed Computing, Vol.130, pp 50-62, 2019.
[13] Xiao, Shucai, Ashwin M. Aji, and Wu-chun Feng. "On the robust mapping of dynamic programming onto a graphics processing unit." In 15th International Conference on Parallel and Distributed Systems. IEEE, 2009.
[14] Xiao, Shucai, and Wu-chun Feng. "Inter-block GPU communication via fast barrier synchronization." In IEEE International Symposium on Parallel & Distributed Processing (IPDPS). IEEE, 2010.
[15] Hagedorn, Christopher, et al. "GPU Acceleration for Information-theoretic Constraint-based Causal Discovery." In the KDD'22 Workshop on Causal Discovery. PMLR, 2022.
[16] Feng, Wu-chun, and Shucai Xiao. "To GPU synchronize or not GPU synchronize?." In IEEE International Symposium on Circuits and Systems (ISCAS). IEEE, 2010.
[17] NVIDIA, "NVIDIA Turing GPU Architecture: Graphics reinvented.", 2018.
[18] Wang, Chuan-Chi, et al. "cuPSO: GPU parallelization for particle swarm optimization algorithms." In Proceedings of the 37th ACM/SIGAPP Symposium on Applied Computing. 2022.
[19] Luo, Lijuan, Martin Wong, and Wen-mei Hwu. "An effective GPU implementation of breadth-first search." In Design Automation Conference. IEEE, 2010.
[20] Komura, Yukihiro, and Yutaka Okabe. "GPU-based single-cluster algorithm for the simulation of the Ising model." Journal of Computational Physics Vol.231, No.4, pp 1209-1215, 2012.
[21] Nasre, Rupesh, Martin Burtscher, and Keshav Pingali. "Atomic-free irregular computations on GPUs." In Proceedings of the 6th Workshop on General Purpose Processor Using Graphics Processing Units. 2013.
[22] Batcher, Kenneth E. "Sorting networks and their applications." In Proceedings of the April 30--May 2, 1968, spring joint computer conference. 1968.
[23] Greb, Alexander, and Gabriel Zachmann. "GPU-ABiSort: Optimal parallel sorting on stream architectures." Proceedings 20th IEEE International Parallel & Distributed Processing Symposium. IEEE, 2006.
[24] Smith, Temple F., and Michael S. Waterman. "Identification of common molecular subsequences." Journal of molecular biology, Vol.147, No.1, pp 195-197, 1981.
[25] Manavski, Svetlin A., and Giorgio Valle. "CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment." BMC bioinformatics Vol.9, pp 1-9, 2008.
Journal of Soft Computing and Information Technology
Volume 12, Issue 2 - Serial Number 40
Summer
Summer 2023
Pages 48-59