دانلود رایگان ترجمه مقاله حداکثر حافظه سریع توزیع شده (آی تریپل ای ۲۰۱۷)

مبتدی (مناسب برای درک مفهوم کلی مطلب) 

ASelect یکی از ساده‌ترین الگوریتم‌ها است. تمامی رئوس (Vs) در زیرگراف را به عنوان مجموعه‌های مستقل در نظر می‌گیرد. سپس، یک عدد تصادفی به شکل را به هر کدام از رئوس زیرگراف تخصیص می‌دهد. سپس برای هر یال در زیرگراف (یال‌ها در Es)، ASelect رئوسی در گراف که دارای مقادیر تصادفی بیشتر باشد را حذف می‌کند.
بر خلاف ASelect، BSelectتمامی رئوس در زیرگراف را به عنوان مجموعه‌ مستقل در یک تکرار در نظر نمی‌گیرد. به جای آن BSelect از یک منغیر تصادفی ( Coin) برای تصمیم‌گیری در مورد اینکه آیا رئوس در زیرگراف باید به مجموعه‌ای مستقل انتخاب شوند یا خیر استفاده می‌کند. مقدار Coin بر اساس توزیع احتمالات با استفاده از درجه توزیع زیرگراف تعریف شده است. به طور دقیق‌تر، اگر d(v) درجه تخصیص‌یافته به یک راس v ∈ V`باشد، آنگاه به احتمال d(v)2/1 خواهیم داشت که: Coin(V)=1. اگر d(v) =0 باشد آنگاه Coin(v) همواره ۱ خواهد بود. برای جزئیات بیشتر در مورد الگوریتم B، می‌توانید به لوبی اصلی که در [۲] منتشر شده بود مراجعه کنید.

A. الگوریتم لوبی در حافظه توزیع‌شده
الگوریتم‌های لوبی مستقیما در اختیار پیاده‌سازی ‌های حافظه توزیع ‌شده موازی قرار نمی‌گیرند. الگوریتم های لوبی باتمرکز بردستگاه ‌های حافظه مشترک و با استفاده ازمدلPRAMمورد تحلیل قرار می‌گیرند. درمدلPRAMتمام پردازنده‌ ها پس از خواندن از حافظه مشترک و همچنین قبل از نوشتن درحافظه مشترک همگام‌ سازی می‌شوند. یک روش طبیعی برای گسترش یک الگوریتم توزیع حافظه لوبی به حافظه توزیع شده،استفاده از رویکرد موازی همگام‌سازی توده‌ای (BSP) است، در BSP [17]عملیات‌های حافظه مشترک می‌توانند برای مراحل محاسبه،ارتباطات و هماهنگ‌سازی تبدیل شوند. بااین حال،این رویکرد دربسیاری ازمراحل همگام‌سازی مانع ایجاد می‌کند.
یکی دیگر از مشکلات «طرح تکرار شونده کلی» (الگوریتم ۱) وابستگی به محاسبات زیرگرافی است. یعنی در هر بار تکرار، الگوریتم یک زیرگراف جدید، با حذف رئوس و یال‌های مجموعه‌ مستقلی که در تکرار فعلی از گراف بودند، ایجاد می‌کند. ساخت یک زیرگراف در هر بار تکرار در حافظه توزیع شده بسیار ناکارآمد است زیرا شامل ارتباطات و همگام‌سازی‌ها است حتی اگر زیرگراف به طور ضمنی از طریق پوشاندن رئوس حفظ و نگهداری شود.
علاوه بر این، الگوریتم Select A نیاز به انتخاب جدیدی از اعداد تصادفی در هر تکرار دارد. محدوده اعداد بستگی به تعداد رئوس باقی‌مانده در زیرگراف دارد. بنابراین، تولید اعداد تصادفی، نیاز به کاهش تعداد رئوس در زیرگراف دارد و این یک مانع در هر تکرار است. علاوه بر این، تولید عدد تصادفی دارای سربار محاسباتی قابل توجهی است.
در بخش بعدی، ما در مورد چگونگی گسترش الگوریتم لوبی به اجرای توزیع‌شده بحت خواهیم کرد و در عین حال از نقایصی که در بالا مطرح شد نیز اجتناب خواهیم کرد. در الگوریتم پیشنهادی، سربار مانع مراحل همگام‌سازی که با همپوشانی محاسباتی و ارتباطی همراه بوده است در اینجا به حداقل رسیده است. محاسبه زیرگراف از طریق فیلترسازی راس بدست خواهد آمد. با این حال فیلترسازی راس، توانایی تکرار در طی ساختار داده گراف به شکل موازی را از کار خواهد انداخت. بنابراین، در پیاده‌سازی ما، ما از یک ساختار داده موازی استفاده کردیم. همچنین نوعی از الگوریتم SelectA را ارائه داده‌ایم که از تولید اعداد تصادفی در هر تکرار جلوگیری می‌کند و از اعداد تصادفی که در آغاز تولید شده بود استفاده می‌کند.

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

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

طرح تکرار شونده توزیع کلی (الگوریتم۲) نیاز به محاسبه زیرگراف دارد. اگر چه محاسبه زیر گرافی صریح ممکن است درمحیط های ترتیبی و حافظه مشترک موازی مفید باشد،امادرحافظه توزیع شده به دلیل ایجاد سربار وتوزیع زیرگرافی جدید درهرتکرار،درحافظه توزیع شده ناکارآمداست. قابلیت محاسبه زیرگراف معادل توزیع شده را میتوان با فیلترکردن ریشه‌ها (به عنوان مثال،اعمال یک فیلتر پیش ‌بینی برای نمایش اینکه آیا یک راس درمحاسبات فعلی درنظر گرفته می‌شود). اگرچه با اعمال فیلتر از بیشتر یال‌ها مجددا باید در هر تکرار عبور کرد، اما افزایش راندمان موازی نسبت به هزینه‌های ناشی از این عبورهای غیرضرروی ارزش دارد.
برای کاهش محاسبات زیرگراف در حافظه توزیع شده،ازدوساختاردادهاستفاده می‌کنیم:
۱) یک بافر ضمیمه (append buffer) (Buffer)- برای دسترسی موازی کارآمد و
۲)یک ساختار مجموعه (set structure) (حذف مجموعه).
این دو ساختارداده توسط طرح تکراری کلی ایجادشده وبه یکی ازالگوریتمSelect A یا Select B منتقل می‌شود. الگوریتم Select مسئول پرکردن با فرضمیمه است و مجموعه راحذف می‌کند.هنگامی که الگوریتم Selectتصمیم می‌گیردکه یک رأس یک نامزدحضوردرMISباشد،رأس رابه بافر ضمیمه می‌کند. سپس، بعد ازاینکه بافرحاوی مقادیر اولیه رئوس احتمالی MISاست،تمام رأس ‌هایی که یک همسایه بایک مقدار تصادفی کمتراختصاص داده شده دارند،درمجموعه حذف قرارمیگیرند. طرح کلی تکراری به طورموازی بافرضمیمه می‌کند و بررسی می‌کندکه آیا یک رأس درمجموعه حذف شده است یا خیر. اگررأس درمجموعه حذف حضور ندارد،پس رأس بهMISحاصل ضمیمه می‌شود. برای کاهش تردی ددرهنگام استفاده ازمجموعه حذف،مجموعه حذف را به عنوان کلسکسیونی ازمجموعه
‌ها اجر امی‌کنیم،که درآن هر نخ یک مجموعه محلی را به نخ نگه می‌دارد.
افزودن به یک مجموعه حذف، محلی برای فراخوانی نخ است. زمانی که در حال انجام کوئری یک عنصر از یک مجموعه حذف هستیم، ابتدا باید بررسی کنیم که آیا عنصر در مجموعه نخ محلی قرار دارد یا خیر، و سپس باید به دنبال عنصری در مجموعه‌های متعلق به سایر نخ‌ها بپردازیم. در طی مرحله جست‌وجو، مجموعه‌ها تنها خوانده می‌شوند، تا آن‌ها را به شکلی ایمن بتوان بین نخ‌ها به اشتراک گذاشت. طراحی دو مرحله‌ای (بافر و مجموعه حذف) سبب محدودیت‌ مشاجره نخ‌ها بر روی موضوع ورودی سربار کم بر روی بافر ضمیمه می‌شود.
در طی محاسبه،یک رأس می‌تواند دریکی از سه حالت زیر باشد (که دریک نقش هم الکیت ذخیره می‌شود):
۱) IN-vertexدرMISاست؛
۲) OUT-vertexدرMISنیست؛و
۳) NIL-vertexهنوزپردازش نشده است.
درابتداتمامرأس‌هادرحالتNILقراردارند. هنگامی که الگوریتم متوقف می‌شود،تمام حالت‌های رأس بهINیاOUTتغییرمی‌کنند.
اینکه آیا حالت راس باید از NIL به IN یا از NIL به OUT تغییر پیدا کند در داخل طرح تکرارشونده کلی تصمیم‌گیری می‌شود (LubyIterate در الگوریتم۲). نخست، طرح‌شونده کلی،الگوریتممناسبSelect، Selectfnراانتخاب می‌کند (SelectA یا SelectB). الگوریتم انتخابی مشخص مسئول آپلود بافر ضمیمه و مجموعه حذف است (خط ۵). طرح کلی تکرارشونده ازطریق بافر ضمیمه به صورت موازی بازنگری می‌کند و بررسی می‌کندکه آیا رأسی درمجموعه حذفوجوددارد (خطوط ۷-۱۱). اگررأسی درمجموعه حذف وجود نداشته باشد، حالت راس به IN بروزرسانی می‌شود (خط۹). هنگامی که حالت یک راس به حالتINتغییرمی‌کند،تمام حالت‌های همسایه ‌های آن به حالتOUTتغییرمی‌کنند(خط ۱۱). عملیات ارسال تعیین می‌کنند که کدام پیام باید براساس رأس مقصدو توزیع گراف قرارگیرد. پیام‌های فرستاده شده ازطریقSend از طریق Reveive (خط ۱۴-۱۵) دریافت می‌شوند. پیمایش بین رأس‌ها دربافرضمیمه صورت می‌گیردوبه‌روز‌رسانی حالت های رأس دریک مرحله فوقالعاده تک (به عنوان مثال،دری کدوره تک) اتفاق می‌افتد.