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

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

improving the inter block synchronization methods in cuda

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.