دانلود مقاله ترجمه شده الگوریتم های کارآمد اسکن موازی برای GPU ها

اسکن و الگوریتم های بخش بندی شده اسکن، بلوک های ساختاری مهمی برای یک الگوریتم خوب با داده های موازی بسیار است. اسکن بخش بندی شده و اشیای اولیه مربوطه نیز پشتیبانی لازم برای تبدیل هموار کننده را فراهم می کنند که این به برنامه های داده موازی تودرتو اجازه می دهد تا به صورت زبان های داده موازی تخت کامپایل شوند. در این مقاله، ما طراحی اسکن کارامد و اصول اسکن موازی بخش بندی شده در CUDA را برای اجرا روی GPU ها توضیح می دهیم. الگوریتم های ما با استفاده از یک رویکرد تقسیم و تصرف طراحی می شوند که همه اشیای اولیه اسکن را در بالای یک مجموعه از روتین های اسکن درون ریسمانی اولیه می سازد. ما ثابت می کنیم که این روش طراحی به روتین هایی می انجامد که ساده، بسیار موثر و بدون الگوهای دسترسی بی قاعده که به تضادهای بانک حافظه منجر می شود، هستند. این الگوریتم ها اساس نسخه های کنونی و آتی کتابخانه بسیار رایج CUDPP را شکل می دهند.

1-مقدمه

عملیات اسکن بخش بندی شده و اسکن موازی ، اشیای اولیه داده موازی هستند که اهمیت گسترده آنها آشکار است. فشردگی دنباله، دسته بندی پایه، دسته بندی سریع، ضرب بردار ماتریس پراکنده و ساخت درخت پوشای مینیمم، تنها چند تا از الگوریتم های بسیاری هستند که می توانند بطور موثر بر حسب عملیات اسکن، پیاده سازی شوند. این عملیات ها هم ارز مدارهای پیشوند موازی (13) هستند که تاریخچه ای طولانی دارند و در زبان های مجموعه گرای که به APL (12) بر می گردد، پرکاربرد هستند. همچنین آنها اساس نگاشت موثر زبان های داده موازی تو در تو نظیر NESL را روی ماشین های داده موازی تخت شکل می دهند...