یک رویکرد سیستم چندعاملی برای متعادلسازی بار و تخصیص منابع در محاسبات توزیعشده

فهرست مطالب

1. چکیده

این پژوهش یک رویکرد غیرمتمرکز برای تخصیص و زمان‌بندی وظایف در شبکه‌های توزیع‌شده عظیم ارائه می‌دهد. الگوریتم پیشنهادی، پروتکل تخصیص منابع توزیع‌شده (dRAP)، از ویژگی‌های برآمده سیستم‌های چندعاملی برای تشکیل و انحلال پویای خوشه‌های کامپیوتری بر اساس نیازهای متغیر یک صف وظایف سراسری بهره می‌برد. شبیه‌سازی‌های آزمایشی نشان می‌دهند که dRAP در معیارهای کلیدی از یک زمان‌بند استاندارد اول-ورود-اول-خروج (FIFO) عملکرد بهتری دارد: زمان تخلیه صف، میانگین زمان انتظار وظیفه و بهره‌وری کلی پردازنده. این پارادایم غیرمتمرکز برای محیط‌های پردازشی توزیع‌شده در مقیاس بزرگ مانند SETI@home و Google MapReduce نویدبخش قابل توجهی است.

2. مقدمه

روند انتقال بارهای محاسباتی بزرگ به شبکه‌های جغرافیایی توزیع‌شده از کامپیوترهای ارزان و آماده تجاری (COTS)، دسترسی به محاسبات با کارایی بالا را دموکراتیک کرده است. سیستم‌هایی مانند SETI@home و Google MapReduce نمونه‌هایی از این تغییر هستند که نیاز حیاتی به الگوریتم‌های کارآمد، مقیاس‌پذیر و مقاوم برای تخصیص وظایف ایجاد می‌کنند. توزیع‌کننده‌های متمرکز نقاط شکست واحد و گلوگاه‌های مقیاس‌پذیری هستند. این مقاله یک جایگزین غیرمتمرکز را با استفاده از سیستم‌های چندعاملی (MAS) بررسی می‌کند که رفتارهای پیچیده سراسری را از تعاملات محلی ساده ایجاد می‌کنند و پیش از این در مدل‌سازی سیستم‌های زیستی و حل مسائل مهندسی موفق بوده‌اند. ساختار مقاله به گونه‌ای است که مسئله را صوری‌سازی می‌کند، محاسبات غیرمتمرکز و MAS را مرور می‌کند، شبیه‌ساز و الگوریتم dRAP را توصیف می‌کند، نتایج آزمایشی را ارائه می‌دهد، کارهای مرتبط را بحث می‌کند و نتیجه‌گیری می‌کند.

3. بیان مسئله و مفروضات

مسئله اصلی شامل تخصیص فرآیندها از یک صف سراسری Q به مجموعه‌ای پویا و جغرافیایی توزیع‌شده از پردازنده‌ها است. هر فرآیند قابلیت موازی‌سازی خود (تعداد رشته‌ها، TH_n) و نیازمندی‌های منابع خود (مانند پردازنده‌ها، CPU_req) را اعلام می‌کند. سیستم هیچ توزیع‌کننده متمرکزی ندارد. در عوض، کامپیوترها را به صورت پویا در "خوشه‌ها" سازماندهی می‌کند - شبکه‌هایی که به طور جمعی نیازمندی‌های یک فرآیند واحد را برآورده می‌کنند. خوشه‌ها با در نظر گرفتن مجاورت جغرافیایی برای به حداقل رساندن تأخیر تشکیل می‌شوند. مفروضات کلیدی عبارتند از: ارتباط بین کامپیوتری امکان‌پذیر است، مجاورت جغرافیایی هزینه‌های تأخیر/پهنای باند را کاهش می‌دهد، فرآیندها نیازمندی‌ها را از پیش اعلام می‌کنند و این رویکرد برای مقیاس (میلیون‌ها/میلیاردها گره) طراحی شده است.

4. مروری بر محاسبات غیرمتمرکز

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

5. سیستم‌های چندعاملی

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

6. محیط شبیه‌سازی

یک شبیه‌ساز سفارشی برای مدل‌سازی یک شبکه توزیع‌شده از کامپیوترهای ناهمگن و جریانی از وظایف ورودی با نیازمندی‌های منابع متغیر توسعه داده شد. این شبیه‌ساز امکان آزمایش کنترل‌شده و مقایسه بین dRAP و الگوریتم‌های پایه مانند FIFO تحت شرایط مختلف بار و توپولوژی شبکه را فراهم کرد.

7. الگوریتم dRAP

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

8. تحلیل هزینه جستجوی صف سراسری

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

9. بهینه‌سازی dRAP با الهام از سیستم ایمنی

نویسندگان از سیستم‌های ایمنی زیستی الهام گرفته‌اند که به طور کارآمد پاتوژن‌ها را با استفاده از سلول‌های غیرمتمرکز و سازگار شناسایی و خنثی می‌کنند. تکنیک‌های بهینه‌سازی مشابه ممکن است شامل موارد زیر باشد: 1) تطابق مبتنی بر هم‌بستگی: عامل‌ها ترجیحاً با وظایفی تطابق می‌یابند که "امضای" منابع آن‌ها به قابلیت‌های خودشان نزدیک است. 2) انتخاب کلونی برای تشکیل خوشه: خوشه‌های موفق (آن‌هایی که وظایف را سریع تکمیل می‌کنند) "به خاطر سپرده می‌شوند" یا الگوی تشکیل آن‌ها برای وظایف مشابه آینده تقویت می‌شود. 3) شعاع جذب سازگار: محدوده جغرافیایی برای جذب اعضای خوشه بر اساس بار سیستم و فوریت وظیفه تنظیم می‌شود.

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

آزمایش‌ها dRAP را با یک زمان‌بند FIFO مقایسه کردند. معیارها شامل موارد زیر بودند: زمان تخلیه صف (TEQ)، میانگین زمان انتظار (AWT) و میانگین بهره‌وری پردازنده (ACU). نتایج عملکرد برتر dRAP را نشان داد، به ویژه تحت بارهای وظیفه با تغییرپذیری بالا، که به دلیل استخر منابع پویا و خوشه‌بندی آگاه از مجاورت آن است که سربار ارتباطی را کاهش می‌دهد.

11. کارهای مرتبط

این مقاله dRAP را در چارچوب تحقیقات گسترده‌تر در مورد تخصیص منابع شبکه، از جمله محاسبات داوطلبانه (مانند BOINC)، پروتکل‌های مبتنی بر توافق (مانند استفاده از SLA) و رویکردهای اقتصادی/بازار-محور (مانند جایی که منابع محاسباتی خرید و فروش می‌شوند) قرار می‌دهد. این مقاله هماهنگی برآمده و الهام‌گرفته از زیستی dRAP را با این پارادایم‌های ساختاریافته‌تر یا انگیزه‌محور مقایسه می‌کند.

12. نتیجه‌گیری و کارهای آینده

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

13. تحلیل اصلی و نقد تخصصی

14. جزئیات فنی و فرمول‌بندی ریاضی

فرآیند تصمیم‌گیری اصلی برای یک عامل i برای انتخاب یک وظیفه T_j از صف Q را می‌توان به عنوان یک مسئله بهینه‌سازی که یک تابع هزینه C(i, j) را کمینه می‌کند مدل کرد:

$C(i, j) = \alpha \cdot \frac{CPU\_req_j}{CPU\_avail_i} + \beta \cdot Latency(i, N(T_j)) + \gamma \cdot WaitTime(T_j)$

جایی که:
- $CPU\_req_j / CPU\_avail_i$ تقاضای نرمال‌شده منابع است.
- $Latency(i, N(T_j))$ هزینه ارتباطی به گره‌های خوشه بالقوه برای وظیفه T_j را تخمین می‌زند.
- $WaitTime(T_j)$ زمانی است که T_j در صف بوده است (اولویت‌دهی به وظایف قدیمی‌تر).
- $\alpha, \beta, \gamma$ پارامترهای وزنی تنظیم‌شده برای سیستم هستند.

تشکیل خوشه یک پروتکل توافق توزیع‌شده است. عامل بذر i یک درخواست جذب Req(T_j, R) را درون یک شعاع R پخش می‌کند. یک عامل k در صورتی می‌پذیرد که منابع در دسترس آن با نیاز مطابقت داشته باشد و تأخیر کلی خوشه را به حداقل برساند. خوشه زمانی تشکیل‌شده در نظر گرفته می‌شود که: $\sum_{k \in Cluster} CPU\_avail_k \geq CPU\_req_j$.

15. نتایج آزمایشی و توصیف نمودار

توصیف نمودار فرضی (بر اساس ادعاهای مقاله):
یک نمودار میله‌ای با عنوان "مقایسه عملکرد: زمان‌بند dRAP در مقابل FIFO" سه جفت میله برای معیارهای کلیدی نشان می‌دهد.

• معیار 1: زمان تخلیه صف (TEQ): میله dRAP به طور قابل توجهی کوتاه‌تر (مثلاً 40٪ کمتر) از میله FIFO خواهد بود که نشان‌دهنده توان عملیاتی کلی سریع‌تر است.
• معیار 2: میانگین زمان انتظار (AWT): میله dRAP پایین‌تر خواهد بود و نشان می‌دهد که وظایف، به طور میانگین، زمان کمتری قبل از شروع اجرا منتظر می‌مانند.
• معیار 3: میانگین بهره‌وری پردازنده (ACU): میله dRAP بالاتر خواهد بود (مثلاً 85٪ در مقابل 60٪) که نشان‌دهنده استفاده کارآمدتر از مخزن منابع توزیع‌شده با به حداقل رساندن زمان بیکاری از طریق خوشه‌بندی پویا است.

این نمودار احتمالاً شامل میله‌های خطا خواهد بود یا در سطوح بار مختلف (کم، متوسط، زیاد) ارائه می‌شود تا نشان دهد مزیت dRAP حفظ می‌شود یا حتی با افزایش بار سیستم و ناهمگنی وظایف افزایش می‌یابد.

16. چارچوب تحلیل: مطالعه موردی مفهومی

سناریو: یک کنسرسیوم جهانی مدل‌سازی آب و هوا شبیه‌سازی‌های مجموعه‌ای را اجرا می‌کند که هر کدام به 10,000 ساعت-پردازنده نیاز دارند. منابع یک شبکه داوطلبانه از 50,000 کامپیوتر خانگی متنوع و ماشین‌های آزمایشگاهی دانشگاهی در سراسر جهان هستند.

شکست خط پایه FIFO: یک سرور مرکزی وظایف را به ترتیب اختصاص می‌دهد. یک شبیه‌سازی که به 100 پردازنده نیاز دارد به 100 ماشین بیکار بعدی در لیست اختصاص داده می‌شود که ممکن است در 6 قاره پراکنده باشند. تأخیر شبکه برای همگام‌سازی باعث می‌شود شبیه‌سازی به کندی پیش برود و چرخه‌های پردازنده بر روی انتظار هدر بروند. سرور مرکزی نیز به یک گلوگاه و نقطه شکست واحد تبدیل می‌شود.

dRAP در عمل:
1. یک وظیفه T (100 پردازنده، 50 گیگابایت حافظه) وارد صف می‌شود.
2. یک ماشین بیکار در اروپا (Agent_EU) با پهنای باند بالا آن را به عنوان بذر برمی‌دارد.
3. Agent_EU از تابع هزینه C برای اولویت‌دهی به جذب ماشین‌ها درون همان ارائه‌دهنده ابری منطقه‌ای و شبکه دانشگاهی استفاده می‌کند.
4. از طریق پخش‌های محلی، به سرعت یک خوشه از 100 ماشین عمدتاً در اروپای غربی تشکیل می‌دهد.
5. خوشه کم‌تأخیر وظیفه T را به طور کارآمد اجرا می‌کند. در همین حال، یک عامل بذر در آسیا خوشه دیگری برای یک وظیفه متفاوت تشکیل می‌دهد.
6. پس از تکمیل، خوشه اروپایی منحل می‌شود و عامل‌های آن بلافاصله شروع به اسکن صف برای بذرهای جدید می‌کنند و یک پارچه منابع سیال و خودترمیم‌کننده ایجاد می‌کنند.

این مورد، نقاط قوت dRAP در کاهش تأخیر و ایجاد مخازن منابع سازگار و محلی‌شده را برجسته می‌کند.

17. چشم‌انداز کاربردی و جهت‌های آینده

کاربردهای فوری:
- محاسبات داوطلبانه 2.0: ارتقای پلتفرم‌هایی مانند BOINC یا Folding@home با توزیع واحد کار هوشمند و آگاه از تأخیر.
- هماهنگی محاسبات لبه: مدیریت وظایف در هزاران گره لبه (مانند ایستگاه‌های پایه 5G، دروازه‌های اینترنت اشیاء) جایی که تأخیر و محلی بودن از اهمیت بالایی برخوردارند.
- یادگیری فدرال: هماهنگی دورهای آموزش در دستگاه‌های توزیع‌شده در حالی که سربار ارتباطی به حداقل می‌رسد و مرزهای شبکه رعایت می‌شود.

جهت‌های تحقیقاتی آینده:
1. ادغام با مدل‌های اقتصادی: ترکیب خوشه‌بندی برآمده با پرداخت‌های خرد یا سیستم‌های اعتبار برای تضمین منابع در شبکه‌های باز و غیرقابل اعتماد.
2. مدیریت بارهای کاری داده‌محور: گسترش تابع هزینه C برای شامل کردن هزینه‌های انتقال داده، آگاه کردن عامل‌ها از محلی بودن داده (شبیه به آگاهی از رک در Hadoop).
3. معماری‌های سلسله‌مراتبی و ترکیبی: استفاده از dRAP برای زمان‌بندی درون منطقه‌ای در حالی که یک فرازمان‌بند سبک‌وزن تقسیم‌بندی صف سراسری را مدیریت می‌کند، ترکیب برآمدگی با راهنمایی مرکزی حداقلی.
4. تأیید صوری و ایمنی: توسعه روش‌هایی برای اطمینان از اینکه رفتار برآمده هرگز منجر به حالت‌های مرضی مانند بن‌بست منابع یا گرسنگی نمی‌شود، که یک چالش کلیدی در MAS است.

18. مراجع

1. Anderson, D.P., et al. (2002). SETI@home: An Experiment in Public-Resource Computing. Communications of the ACM.
2. Dean, J., & Ghemawat, S. (2008). MapReduce: Simplified Data Processing on Large Clusters. Communications of the ACM.
3. Bonabeau, E., Dorigo, M., & Theraulaz, G. (1999). Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press.
4. Foster, I., & Kesselman, C. (2004). The Grid 2: Blueprint for a New Computing Infrastructure. Morgan Kaufmann.
5. Ousterhout, K., et al. (2013). Sparrow: Distributed, Low Latency Scheduling. Proceedings of SOSP.
6. Zhu, J., et al. (2017). Unpaired Image-to-Image Translation using Cycle-Consistent Adversarial Networks (CycleGAN). Proceedings of ICCV. (Cited as an example of innovative, non-linear algorithmic frameworks).
7. Vasilescu, I., et al. (2022). Adaptive Resource Management in Decentralized Edge Clouds: A Bio-Inspired Approach. IEEE Transactions on Cloud Computing.
8. MIT SwarmLab. (n.d.). Research on Swarm Intelligence and Robotics. Retrieved from [MIT CSAIL website].
9. Protocol Labs. (2020). Filecoin: A Decentralized Storage Network. [Whitepaper].