ارائه روش نوین موازی سازی الگوریتم یافتن مجموعه غالب متصل در گراف با استفاده از کتابخانه OpenMp

موازی کردن الگوریتم های مختلف به طور مداوم در حال تحول می باشد که محققان به عنوان یک تکنولوژی جدید با آن مواجه هستند. در دهه ی گذشته، مدل های جدیدی از الگوریتم ها، سخت افزارهای جدید برای اجرای موازی و چالش های جدید در حل مسائل پیچیده، باعث پیشرفت در این زمینه شده است. استفاده از روش های موازی سازی برای مقابله با برخی از موضوعات در حال رشد می باشد. مجموعه غالب متصل حداقلی یک مجموعه غالب متصل با حداقل گره های ممکن در شبکه است. یافتن مجموعه غالب متصل حداقلی برای گراف، یک مسئله NP-Hard است. بنابراین تاکنون الگوریتم بهینه ای برای یافتن این مجموعه غالب پیدا نشده است. این مسئله کاربردهای بسیاری در زمینه مسیریابی و رایانش های توزیع شده یا خوشه ای دارد. در این پژوهش یک نسخه موازی جدید از یافتن مجموعه غالب متصل در گراف ارائه خواهد شد که در بخش محاسبه زیر درخت های گراف دارای قابلیت اجرای موازی است و این بخش بر اساس کتابخانه موازی OpenMP اجرا می گردد که در آن هر یک از بخش های موازی تحت عنوان یک نخ تعریف شده و از قدرت اجرای موازی سیستم های چندپردازنده بهره می برد. این تحقیق با مدنظر قرار دادن کتابخانه موازی سازی OpenMp، در پی ارائه روشی جدید بوده که سرعت و دقت الگوریتم یافتن مجموعه غالب متصل در گراف را برای مسایل بهینه سازی با استفاده از این فناوری افزایش دهد. ایده اصلی در اینجا استفاده از نخ های چندگانه در شکل یک نخ واحد بوده که احتمال همگرایی برای به دست آوردن یک راه حل بهینه را افزایش می دهد. روش پیشنهادی شبیه سازی شده و بر روی چهار مجموعه دادهگراف مختلف آزمایش گردیده است. نتایج روش پیشنهادی به خوبی مشخص است با افزایش تعداد هسته های پردازنده مورد استفاده، کارایی افزایش می یابد و با افزایش تعداد واحدهای اجرایی موازی در کتابخانه OpenMP نیز شاهد افزایش در میزان تسریع به حالت یافتن مجموعه غالب متصل گراف در حالت سریال می باشیم. این امر کارایی روش پیشنهادی را نشان می دهد.

Keywords:

پردازش گراف , یافتن مجموعه غالب متصل , موازی سازی , کاهش زمان اجرا , کتابخانه OpenMP