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