ارایه الگوریتم موازی حل مساله پیدا کردن نزدیک ترین همسایه بر روی GPU با استفاده از CUDA

الگوریتم جستجوی نزدیک ترین همسایه کاربردهای فراوانی در علوم کامپیوتر دارد. به عنوان مثال در حوزه داده کاوی تکنیکهای دسته بندی موثر داده ها از حیاتیترین مسایل میباشد. بالا بودن پیچیدگی محاسباتی الگوریتم جستجوی نزدیکترین همسایه ها یک چالش برای زمان اجرا محسوب میشود.طرح این مساله حل آن برای مقدار داده اندک راحت میباشد،اما زمانی که پایگاه داده بزرگ میشود مشکل بنیادی در پردازش سریع داده بوجود می آید.در حوزه هایی مانند داده کاوی که الگوریتم جستجوی نزدیکترین همسایه برای آنها کاربرد دارد تکنولوژیهای متعددی برای انجام دستهبندی داده ها معرفی شده است که با افزایش حجم داده ها انتخاب تکنولوژی مناسب برای دسته بندی آنها اهمیت پیدا میکند. تکنولوژی کودا توسط شرکت انویدیا ارایه شده است فرصتی را برای توسعه دهندگان فراهم میکند تا با استفاده از کارت گرافیک سختافزار سیستم خود، به سادگی با کمترین هزینه، پردازش محاسباتی داده ها را به صورت موازی انجام دهند.در این مقاله از مفهومGPGPUوتکنولوژی کودا برای جستجوی نزدیکترین همسایه استفاده شده است موازیسازی اجرای این الگوریتم بر روی واحد پردازش گرافیکی با دسترسی داشتن به حافظه اشتراکی را با حالتی که برنامه به صورت سریال بر روی پردازنده اجرا میشود وهمچنین با حالتی که برنامه بر روی واحد پردازش گرافیکی به صورت موازی بدون استفاده از حافظه اشتراکی اجرا میشود را مقایسه میکند. نشان داده میشودکه اجرای الگوریتم به صورت موازی بر روی واحد پردازش گرافیکی با استفاده از حافظه اشتراکی نسبت به دو روش دیگر بررسی شده در این مقاله بهتر عمل کرده امکانی را برای توسعه دهندگان فراهم میکند که از راه حلهای مقیاس پذیر کم هزینه برای اجرای موازی پردازشهای محاسباتی سنگین استفاده کنند.

کلیدواژه ها:

نزدیکترین همسایه ، کودا واحد پردازش گرافیکی ، حافظه اشتراکی ، موازی سازی