چکیده
مسئله گراف مجموعه مستقل ماکسیمال (که به اختصار MIS نامیده می‌شود) در بسیاری از برنامه‌های کاربردی نظیر بینایی کامپیوتر ، نظریه اطلاعات ، زیست‌شناسی مولکولی و زمانبندی ظاهر شده است. مقیاس در حال رشد مسائل MIS پیشنهاد استفاده از سخت‌افزار حافظه توزیع‌شده را به عنوان روشی مقرون به صرفه برای ارائه محاسبات لازم و منابع حافظه را می‌دهد. لوبی چهار الگوریتم تصادفی برای حل مسئله MIS ارائه کرده است. تمامی این الگوریتم‌ها با تمرکز بر دستگاه‌های حافظه مشترک طراحی شده‌اند و با استفاده از مدل PRAMمورد تجزیه و تحلیل قرار گرفته‌اند. این الگوریتم‌ها دارای پیاده‌سازی‌های کارآمد مستقیم حافظه توزیع‌شده نیستند. در این مقاله، ما دو مورد از الگوریتم‌های MISبدوی لوبی را برای اجرای حافظه توسعه‌یافته گسترش خواهیم داد که نام آن‌ها Luby (A)و Luby(B)است و عملکرد آن‌ها را ارزیابی می‌کنیم. ما نتایج خود را با پیاده‌سازی «MISفیلترشده » در کتابخانه Combinatorial BLASبرای دو نوع ورودی از گراف‌های مصنوعی مقایسه کردیم.
1. مقدمه
G = (V, E) را به عنوان گرافی در نظر بگیرید که در آن V نشان‌دهنده مجموعه‌ای از راس‌ها و E نشان‌دهنده مجموعه‌ای از یال‌ها است. یک مجموعه مستقل درGمجموعه‌ای از رئوسی در یک گراف است که هیچ دو راسی در مجموعه، مجاور نیستند. بزرگترین مجموعه‌های مستقل (که ممکن است بیش از یک باشد) ماکسیمم مجموعه‌های مستقل نامیده می‌شود. بنابراین یافتن ماکسیمم مجموعه مستقل ان‌پی-سخت است، اکثر برنامه‌های کاربردی برای یافتن یک مجموعه مستقل ماکسیمال تنظیم شده‌اند. یک مجموعه مستقل ماکسیمال (MIS) از یک گراف یک مجموعه مستقل است که زیرمجموعه‌ای از مجموعه مستقل دیگر نیست (شکل 1 را ببینید). یافتن یک MIS یک مسئله مهم گراف است زیرا در بسیاری از برنامه‌های کاربردی از جمله بینایی کامپیوتر، نظریه اطلاعات، زیست‌شناسی مولکولی و زمانبندی فرآیند ظاهر شده است. اگرجه الگوریتم‌های موثر MISشناخته شده‌اند[1]، مقیاس در حال افزایش برنامه‌های کاربردی حساس به داده پیشنهاد استفاده از سخت‌افزار حافظه توزیع‌شده (خوشه‌ها ) را می‌دهد، که به نوبه خود نیاز به الگوریتم‌های توزیع حافظه دارند.
از الگوریتم‌های MIS، لوبی مونت کارلو [2] برای پیاده‌سازی MIS به شکل موازی استفاده می‌شود. الگوریتم‌های MIS لوبی با تمرکز بر دستگاه‌های حافظه مشترک طراحی شده‌اند و با استفاده از مدل دستگاهی با دسترسی تصادفی موازی PRAMمورد تجزیه و تحلیل قرار گرفته‌اند. الگوریتم‌های لوبی بلافاصله خود را به الگوریتم‌های موازی توزیع شده موثر قرض نمی‌دهند زیرا ممکن است سربار در اثر هماهنگ‌سازی و محاسبات زیرگراف توزیع‌شده رخ دهد. در این مقاله، نسخه‌های توزیع‌شده الگوریتم‌های لوبی مونت کارلو (الگوریتم A و B) ارائه شده است که سبب به حداقل‌رسانی این سربارها می‌شود. علاوه بر این، ما یک متغیر از Luby (A)را مشتق کرده‌ایم که از تکرار محاسبه اعداد تصادفی در هر تکرار جلوگیری می‌کند. تمامی الگوریتم‌ها در زمان اجرای AM++[3] پیاده‌سازی شده‌اند و عملکرد آن‌ها ارزیابی شده است. نتایج ما نشان می‌دهد که الگوریتم‌های پیشنهادی به خوبی در تنظیمات توزیع‌شده قرار می‌گیرد. ما همچنین نتایج خود را با پیاده‌سازی MISفیلترشده در کتابخانه Combinatorial BLASمقایسه کرده‌ایم [4] و نشان داده‌ایم که پیاده‌سازی‌های ما چندین برابر سریع‌تر از الگوریتم MISفیلترشده است.
این مقاله در نشریه آی تریپل ای منتشر شده و ترجمه آن با عنوان حافظه توزیع شده در سایت ای ترجمه به صورت رایگان قابل دانلود می باشد. جهت دانلود رایگان مقاله فارسی و انگلیسی روی عنوان فارسی (آبی رنگ) کلیک نمایید.
منبع:
