مجموعه مستقل حداکثر حافظه سریع توزیع شده (مقاله ترجمه شده)

چکیده

مسئله گراف مجموعه مستقل ماکسیمال (که به اختصار MIS نامیده می‌شود) در بسیاری از برنامه‌های کاربردی نظیر بینایی کامپیوتر ، نظریه اطلاعات ، زیست‌شناسی مولکولی  و زمانبندی ظاهر شده است. مقیاس در حال رشد مسائل MIS پیشنهاد استفاده از سخت‌افزار حافظه توزیع‌شده را به عنوان روشی مقرون به صرفه برای ارائه محاسبات لازم و منابع حافظه را می‌دهد. لوبی  چهار الگوریتم تصادفی برای حل مسئله MIS ارائه کرده است. تمامی این الگوریتم‌ها با تمرکز بر دستگاه‌های حافظه مشترک طراحی شده‌اند و با استفاده از مدل PRAMمورد تجزیه و تحلیل قرار گرفته‌اند. این الگوریتم‌ها دارای پیاده‌سازی‌های کارآمد مستقیم حافظه توزیع‌شده نیستند. در این مقاله، ما دو مورد از الگوریتم‌های  MISبدوی لوبی را برای اجرای حافظه توسعه‌یافته گسترش خواهیم داد که نام آن‌ها Luby (A)و Luby(B)است و عملکرد آن‌ها را ارزیابی می‌کنیم. ما نتایج خود را با پیاده‌سازی «MISفیلتر‌شده » در کتابخانه Combinatorial BLASبرای دو نوع ورودی از گراف‌های مصنوعی مقایسه کردیم.

مقدمه

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فیلترشده است.

کارهای مرتبط

اکثر الگوریتم‌های MIS موازی بر روی حافظه اشتراکی تمرکز داشتند، و از مدل PRAM برای تجزیه و تحلیل پیچیدگی موازی استفاده می‌کردند (برای مثال [5]، [6]، [7]، [8]،[9]، [10] ). در این کار، ما به طور خاص بر روی الگوریتم‌های تصادفی لوبی [2] تمرکز کرده‌ایم (برای جزئیات بیشتر به بخش 3 مراجعه کنید). لوبی یک تحلیل دقیق از الگوریتم‌های خود را با استفاده از مدل دستگاهPRAM ارائه کرد. بعدها، مفاهیم الگوریتم لوبی به منظور پیاده سازی نسخه‌های توزیع‌شده مورد استفاده قرار گرفت. لینچ  و همکاران [11] در مورد یک نسخه توزیع‌شده از الگوریتم لوبی برای شبکه‌های توزیع همزمان را مورد بررسی قرار دادند. متی‌ویر  و همکاران [12] یک نسخه بهبودیافته از الگوریتم لینچ را ارائه دادند که در آن پیچیدگی پیام ارتباطی بهبود یافته بود. کوهن  و همکاران [13] یک الگوریتمMIS توزیع شده قطعی را ارائه دادند. با این حال، آن‌ها یک مدل ارتباطی همزمان را در نظر گرفتند و هیچگونه نتیجه تجربی ارائه نکردند.

الگوریتم‌ های لوبی

الگوریتم‌های لوبی از جمله پر استفاده‌ترین الگوریتم‌ها برای یافتن MIS در حافظه مشترک هستند. لوبی در انتشار اولیه الگوریتم خود در مورد یک طرح تکرارشونده کلی و چهار تغییرات خاص بر اساس آن بحث کرد. طرح کلی تکرارشونده در الگوریتم 1 ذکر شده است، در کل این طرح یک مجموعه مستقل غیرتهی را انتخاب می‌کند (خط5) و آن را با خروجی‌ها (Smis) ادغام می‌کند. سپس، مجموعه مستقلی که انتخاب شده است و همسایه‌های آن از گراف ورودی حذف می‌شوند و زیرگراف حاصل از آن برای تکرار بعدی طرح مورد استفاده قرار می‌گیرد (خطوط 7 الی 9). این فرآیند تا زمانی تکرار می‌شود که زیرگراف حاصل خالی باشد. در هر بار تکرار، طرح کلی تکرارشونده یک مجموعه مستقل جدید را تولید می‌کند. لوبی ثابت کرد است که اجتماع تمامی آن مجموعه‌های مستقل یک مجموعه مستقل ماکسیمال است.

الگوریتم لوبی در حافظه توزیع‌ شده

الگوریتم‌های لوبی مستقیما در اختیار پیاده‌سازی ‌های حافظه توزیع ‌شده موازی قرار نمی‌گیرند. الگوریتم های لوبی باتمرکز بردستگاه ‌های حافظه مشترک و با استفاده ازمدلPRAMمورد تحلیل قرار می‌گیرند. درمدلPRAMتمام پردازنده‌ ها پس از خواندن از حافظه مشترک و همچنین قبل از نوشتن درحافظه مشترک همگام‌ سازی می‌شوند. یک روش طبیعی برای گسترش یک الگوریتم توزیع حافظه لوبی به حافظه توزیع شده،استفاده از رویکرد موازی همگام‌سازی توده‌ای[1](BSP) است، در BSP [17]عملیات‌های حافظه مشترک می‌توانند برای مراحل محاسبه،ارتباطات و هماهنگ‌سازی تبدیل شوند. بااین حال،این رویکرد دربسیاری ازمراحل همگام‌سازی مانع ایجاد می‌کند.

الگوریتم‌ های حافظه توزیع‌ شده موازی لوبی

الگوریتم‌های حافظه توزیع‌شده موازی لوبی از یک توزیع 1 بعدی برای توزیع رئوس گراف در بین رتبه‌های شرکت‌کننده‌ها استفاده می‌کند. هر رتبه یک زیرمجموعه از رئوس و یک زیرمجموعه یال مرتبط با رئوس را دریافت می‌کند. در داخل یک رتبه، یک زیرمجموعه راس و یال‌های تخصیص یافته به آن زیرمجموعه با استفاده از یک نمایه گرافی محلی به شکل زیر نمایش داده می‌شود: ?. یک راس «متعلق به» یک رتبه است و راس‌ها متعلق به رتبه‌های مختلف ارتباطی هستند که به عبور پیام‌ها می‌پردازند. عبور پیام‌های ارتباطی بین رتبه‌ها بر اساس فرآیند BSPطراحی شده است، اما با همپوشانی ارتباطی و محاسباتی برای بهبود کارآیی طراحی شده‌اند.

طرح تکرارشونده توزیع کلی

طرح تکرار شونده توزیع کلی (الگوریتم2) نیاز به محاسبه زیرگراف دارد. اگر چه محاسبه زیر گرافی صریح ممکن است درمحیط های ترتیبی و حافظه مشترک موازی مفید باشد،امادرحافظه توزیع شده به دلیل ایجاد سربار وتوزیع زیرگرافی جدید درهرتکرار،درحافظه توزیع شده ناکارآمداست. قابلیت محاسبه زیرگراف معادل توزیع شده را میتوان با فیلترکردن ریشه‌ها (به عنوان مثال،اعمال یک فیلتر پیش ‌بینی برای نمایش اینکه آیا یک راس درمحاسبات فعلی درنظر گرفته می‌شود). اگرچه با اعمال فیلتر از بیشتر یال‌ها مجددا باید در هر تکرار عبور کرد، اما افزایش راندمان موازی نسبت به هزینه‌های ناشی از این عبورهای غیرضرروی ارزش دارد.

آزمایش‌ ها و نتایج

پیاده‌ سازی

الگوریتم‌های پیشنهادی بر روی یک چهارچوب پیام‌نگاری فعال با نام AM++[3] با استفاده از pthreads برای نخ‌سازی در داخل گره اجرا شده است.

رئوس گراف به طور مساوی بین گره‌های شرکت‌کننده (توزیع 1 بعدی بلاک) توزیع شده‌اند. گراف محلی با استفاده از قالب ردیف اسپارس[1]فشرده (CSR) نمایش داده شده است. هر یال بی‌جهت با استفاده از یال‌های دو طرفه نشان داده است.

نتیجه‌ گیری

بسیاری از تحقیقات فعلی در حوزه MIS بر روی تحلیل تئوری به جای پیاده‌سازی عملی تمرکز داشتند. علاوه بر این، تنها موارد محدودی که در مورد پیاده‌سازی عملی بودند، اکثرا الگوریتم MISلوبی را پیاده‌سازی کرده بودند. MIS لوبی به دلیل سربار همگام‌سازی و سربار محاسبات زیرگرافی، به شکل موثر و بلافاصله‌ای در الگوریتم‌های موازی حافظه توزیع‌شده گسترش نمی‌یافت.

در این مقاله ما نسخه‌های توزیع‌یافته الگوریتم‌های لوبی موازی را ارائه دادیم‌. الگوریتم‌ها به منظور به حداقل‌رسانی سربار همگام‌سازی با همپوشانی ارتباطی و محاسباتی و با به حداقل‌رسانی سربار محاسباتی زیرگراف‌ها با استفاده از فیلتر‌سازی رئوس و با حفظ ساختارهای داده‌های موازی فعالیت می‌کنند. نتایج ما نشان‌دهنده این است که الگوریتم‌هایی که ما ارائه دادیم، چندین برابر سریع‌تر از الگوریتم‌های فعلی MIS هستند.

این مقاله در سال 2017 در نشریه آی تریپل ای و در کنفرانس محاسبات افراطی با عملکرد بالا، توسط آزمایشگاه ملی شمال غربی اقیانوس آرام منتشر شده و در سایت ای ترجمه جهت دانلود ارائه شده است. در صورت نیاز به دانلود رایگان اصل مقاله انگلیسی و ترجمه آن می توانید به پست دانلود ترجمه مقاله مجموعه مستقل حداکثر حافظه سریع توزیع شده در سایت ای ترجمه مراجعه نمایید.