Abstract
Scan and segmented scan algorithms are crucial building blocks for a great many data-parallel algorithms. Segmented scan and related primitives also provide the necessary support for the flattening transform, which allows for nested data-parallel programs to be compiled into flat data-parallel languages. In this paper, we describe the design of efficient scan and segmented scan parallel primitives in CUDA for execution on GPUs. Our algorithms are designed using a divide-and-conquer approach that builds all scan primitives on top of a set of primitive intra-warp scan routines. We demonstrate that this design methodology results in routines that are simple, highly efficient, and free of irregular access patterns that lead to memory bank conflicts. These algorithms form the basis for current and upcoming releases of the widely used CUDPP library
چکیده
اسکن و الگوریتم های بخش بندی شده اسکن، بلوک های ساختاری مهمی برای یک الگوریتم خوب با داده های موازی بسیار است. اسکن بخش بندی شده و اشیای اولیه مربوطه نیز پشتیبانی لازم برای تبدیل هموار کننده را فراهم می کنند که این به برنامه های داده موازی تودرتو اجازه می دهد تا به صورت زبان های داده موازی تخت کامپایل شوند. در این مقاله، ما طراحی اسکن کارامد و اصول اسکن موازی بخش بندی شده در CUDA را برای اجرا روی GPU ها توضیح می دهیم. الگوریتم های ما با استفاده از یک رویکرد تقسیم و تصرف طراحی می شوند که همه اشیای اولیه اسکن را در بالای یک مجموعه از روتین های اسکن درون ریسمانی اولیه می سازد. ما ثابت می کنیم که این روش طراحی به روتین هایی می انجامد که ساده، بسیار موثر و بدون الگوهای دسترسی بی قاعده که به تضادهای بانک حافظه منجر می شود، هستند. این الگوریتم ها اساس نسخه های کنونی و آتی کتابخانه بسیار رایج CUDPP را شکل می دهند.
1-مقدمه
عملیات اسکن بخش بندی شده و اسکن موازی ، اشیای اولیه داده موازی هستند که اهمیت گسترده آنها آشکار است. فشردگی دنباله، دسته بندی پایه، دسته بندی سریع، ضرب بردار ماتریس پراکنده و ساخت درخت پوشای مینیمم، تنها چند تا از الگوریتم های بسیاری هستند که می توانند بطور موثر بر حسب عملیات اسکن، پیاده سازی شوند. این عملیات ها هم ارز مدارهای پیشوند موازی (13) هستند که تاریخچه ای طولانی دارند و در زبان های مجموعه گرای که به APL (12) بر می گردد، پرکاربرد هستند. همچنین آنها اساس نگاشت موثر زبان های داده موازی تو در تو نظیر NESL را روی ماشین های داده موازی تخت شکل می دهند...