روشي براي بهبود الگوريتم بهينه سازي اجتماع ذرات با استفاده از CUDA بر روي پردازنده گرافيكي

An approach to Improve Particle Swarm Optimization Algorithm Using CUDA

همواره زمان صرف‌شده براي حل مسائل سنگين محاسباتي، يكي از دغدغه‌هاي برنامه‌نويسان كامپيوتر بوده است. الگوريتم PSO، الگوريتمي فرا‌ابتكاري است كه به‌دليل ساد‌گي پياده‌سازي، براي حل مسائل سنگين محاسباتي استفاده مي‌شود ولي با وجود ساد‌گي، اين الگوريتم براي حل مسائل سنگين واقعي ناكارآمد است. از طرفي، وجود ويژگي تعاملات محلي ذرات در الگوريتم PSO، اين الگوريتم را براي موازي‌سازي مناسب كرده است؛ از طرف ديگر، NVIDIA با اختراع پردازنده‌گرافيكي و معرفي معماري CUDA، تحولات بنيادي را در حل اين نوع مسائل، از طريق پياده‌سازي آن بر روي پردازنده‌گرافيكي ايجاد كرده است. با وجود تمام تحقيقات انجام‌گرفته در زمينه پياده‌سازي، برخي از جنبه‌هاي تكنيكي موازي‌سازي به‌منظور پياده‌سازي الگوريتم به‌صورتي كه تسريع و بازدهي مناسب بر روي تمام پردازنده‌هاي گرافيكي NVIDIA را داشته باشد، رعايت نشده است. در اين مقاله سعي شده با انتخاب Geforce GT 525M كه پردازنده‌گرافيكي نسبتاً ضعيفي است، جنبه مقياس‌پذيري روش پيشنهادي رعايت شود؛ به‌طوري كه با رسيدن به بيشينه تسريع الگوريتم پياده‌سازي‌شده بر روي اين پردازنده، به بازدهي قابل قبول براي اجرا بر روي ساير پردازنده‌هاي ‌گرافيكي رسيد. براي نيل به اين هدف، از مدل چند‌كرنلي ارائه‌شده استفاده شده است. نتايج حاصل از انجام آزمايش‌ها رسيدن به بيشينه تسريع 15/98 براي حل تابع Rastrigin را نشان مي‌دهد.

The time consumption in solving computationally heavy problems has always been a concern for computer programmers. Due to simplicity of its implementation, the PSO (Particle Swarm Optimization) is a suitable meta-heuristic algorithm for solving computationally heavy problems. However, despite the simplicity, the algorithm is inefficient for solving real computationally heavy problems but the presence of local interactions between particles has made this algorithm suitable for parallelization. On the other hand, by the invention of GPU (Graphical Processor Unit) and introducing the CUDA architecture as a GPU in the NVIDIA graphical processor, fundamental changes has been made in solving this type of problems. Despite all the research done in the field of implementing the algorithms through GPUs, some aspects of parallelization have not been addressed for suitable speedup and efficiency on NVIDIA GPUs. By considering the Geforce GT 525M, which is a relatively weak GPU, this paper tries to achieve the maximum speedup of the algorithm by implementing on this GPU. This experience led to reaching the acceptable efficiency on other GPUs. To reach the achievement, the multi-kernel model was used. The results show the speedup of 15.98 in solving the Rastrigin function.