مجله علمی  رایانش نرم و فناوری اطلاعات

مجله علمی رایانش نرم و فناوری اطلاعات

بهبود روش های همگام سازی بین بلاکی در کودا

نوع مقاله : مقاله پژوهشی فارسی

نویسندگان
1 گروه مهندسی کامپیوتر، دانشکده مهندسی دانشگاه فردوسی مشهد، مشهد، ایران.
2 دانشکده مهندسی، دانشگاه فردوسی مشهد، مشهد، ایران.
چکیده
چکیده- عدم پشتیبانی صریح همگام‌سازی بین بلاکی در مدل برنامه‌نویسی کودا، باعث تضعیف کارآیی در برخی از برنامه‌های کاربردی شده است. بنابراین در چنین برنامه‌هایی، همگام‌سازی بین بلاکی باید به‌صورت نرم‌افزاری پیاده‌سازی شود. روش‌های باقفل و بدون قفل برای این مسئله پیاده‌سازی شده‌اند. در همگام‌سازی باقفل، زمان اجرا با افزایش تعداد بلاک رشد چشمگیری دارد و در روش همگام‌سازی بدون‌قفل، محدودیت تعداد بلاک‌ها وجود دارد. در این مقاله، دو روش همگام‌سازی بین بلاکی پیشنهاد می‌شوند. اولین روش مبتنی‌بر همگام‌سازی باقفل است که با گروه‌بندی مناسب بلاک‌ها، تاثیر افزایش تعداد بلاک بر زمان اجرا را کاهش می-دهد. دومین روش پیشنهادی همگام‌سازی بدون قفل است که با ایجاد یک سلسله‌مراتبی درختی از بلاک‌ها، محدودیت تعداد بلاک-ها در این همگام‌سازی را مرتفع می‌کند. این روش‌ها برای همگام‌سازی بین بلاکی در الگوریتم‌های اسمیت واترمن و مرتب‌سازی بایتونیک به کار گرفته شده‌اند. نتایج آزمایش‌ها نشان می‌دهند که روش باقفل پیشنهادی، زمان اجرای همگام‌سازی را بهبود می‌بخشد و تسریع 1.84 در الگوریتم اسمیت واترمن و 2.24 را در الگوریتم مرتب‌سازی بایتونیک ثبت کرده است. همچنین نتایج نشان می‌دهند که در روش پیشنهادی بدون قفل نیز با انتخاب درست تعداد سطوح سلسله‌مراتب درختی، هر تعداد بلاک می‌توانند همگام شوند و بنابراین محدودیت تعداد بلاک‌ها مرتفع شده است.
کلیدواژه‌ها

[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.