12859

12859

ارائه الگوريتم خوشه¬بندي موازي جريان¬هاي داده مبتني بر GPU

كارشناسي ارشد

برق- الكترونيك

بهمن ماه 1392

بهمن ماه 1392

دكتر هادي¬شهريار شاه¬حسيني

دكتر مجيد نادري

چكيده جريان داده محيطي چالش¬انگيز در داده¬كاوي مي¬باشد كه در آن داده¬ها با زمان مي¬رسند. نيازمندي همزمان به دقت و سرعت بالا و محدوديت ذخيره¬سازي اين داده¬ها مسائل مربوط به آن را پيچيده‌تر مي¬كند و در حوزه جريان داده نتايج تقريبي توليد مي¬كند. الگوريتم K-means يكي از محبوب¬ترين الگوريتم¬هاي خوشه¬بندي است كه در اينجا به كار گرفته شده است. از جمله راه¬حل¬هايي كه مي¬توان براي اين مسئله در نظر گرفت موازي¬سازي الگوريتم است. كارت¬گرافيك از هسته¬هاي متعددي تشكيل شده است كه استفاده از آن براي سرعت¬دهي كاربردها مورد توجه قرار گرفته است و شاخه¬اي با عنوان GPGPU در حوزه موازي¬سازي به وجود آورده است. در پايان¬نامه يك قالب موازي مبتني بر توانايي¬هاي GPU طراحي شده است كه داراي بحث مقداردهي اوليه، فازهاي برخط و درون¬خط، تصحيح پوياي مراكز و شناسايي مراكز پرت مي¬باشد. قالب طراحي شده توسط چندين جريان همزمان مديريت مي¬شود و توسط پرچم¬ها و گام¬هاي همزمان¬ساز با هم در ارتباط هستند. هسته اصلي خوشه¬بندي به نحوي به صورت موازي طراحي شده است تا علاوه بر دارا بودن سرعت اجراي بالا، از ابعاد بالا پشتيباني كند و پيچيدگي زماني مناسبي داشته باشد. در نتيجه، الگوريتم در هر ورودي مشخصاتي را به صورت پويا تنظيم مي¬كند تا در تكامل داده، زمان اجرا افزايش نيابد و در هر واحد زماني نتايج آماده باشد. علاوه براين با تصحيح پوياي مراكز در فاز برخط، مقدار SSQ نسبت به خوشه¬بندي STREAM با ضريب 1E5 و نسبت به CLUStream با ضريب 1E2 كاهش يافته است. همچنين با توجه به ساختار موازي كه بر تمامي قسمت¬هاي الگوريتم حكم فرما است و تعيين پوياي ضرايب در خوشه¬بندي، مدت زمان پاسخگويي الگوريتم در تكامل داده برابر با 1 واحد زماني مي¬باشد، كه در الگوريتم¬هاي HUE-Stream، Umicro و E-Stream اين زمان برابر با 40، 15 و 11 است. واژه‌هاي كليدي: GPGPU؛ خوشه¬بندي موازي؛ جريان داده؛ ابعاد بالا.