کاهش بار شبکه با نگاشت برنامه کابردی در شبکه روی تراشه با استفاده از الگوریتم شاهین هریس گسسته
محورهای موضوعی :الهام حاجبی 1 , وحید ستاری نائینی 2
1 - دانشجوی کارشناسی ارشد، بخش مهندسی کامپیوتر، دانشگاه شهید باهنر کرمان، کرمان، ایران
2 - دانشیار، بخش مهندسی کامپیوتر، دانشگاه شهید باهنر کرمان، کرمان، ایران
کلید واژه: شبکه روی تراشه- نگاشت هسته پردازشی - تأخیر شبکه - بهره¬وری از لینک¬ - الگوریتم شاهین هریس گسسته,
چکیده مقاله :
کاهش بار و مصرف انرژی در سیستم های شبکه روی تراشه از اهمیت بسیاری برخوردار است و يكي از مهم‌ترين مباحثي که برای افزايش کارايي شبكه روی تراشه مطرح است، موضوع نگاشت يک برنامه کاربردی در شبكه روی تراشه است. حل مسئله نگاشت برنامه کاربردی برای يافتن بهترين نگاشت، يک موضوع پيچيده و زمانبر است و تاثير بسيار زيادی بر تأخير و انرژی مصرفي شبكه دارد. در اين مقاله با استفاده از الگوريتم شاهین هریس توانسته ايم روشی را برای نگاشت هسته های پردازشي به روی شبكه روی تراشه ارائه کنيم تا بار روی شبکه و در نتیجه ازدحام در لینک ها را کاهش داده و عملکرد شبکه بهبود ببخشیم. نتايج شبيه‌سازی نشان می دهد که اين الگوريتم عملکرد بهتری در مقايسه با الگوريتم-های پايه دارد.
Reducing load and power consumption in on-chip network systems is very important and one of the most important issues to increase the efficiency of on-chip network is the issue of mapping an application on the chip network. Solving the application mapping problem to find the best mapping is a complex and time consuming issue and has a huge impact on network latency and power consumption. In this paper, using the Harris hawk algorithm, we have been able to provide a method for mapping processing cores to the network on chip to reduce the load on the network and thus congestion in the links and improve network performance. The simulation results show that this algorithm performs better than the basic algorithms.
]1] A. V. Bhaskar and T. Venkatesh, "Performance analysis of network-on-chip in many-core processors," Journal of Parallel and Distributed Computing, vol. 147, pp. 196-208, 2021.
[2] اسدی بهاره، رشادی میدیا، خادم زاده احمد، کرباسی مصطفی،"مدل های چرخشی تطابقی و الگوهای ترافیکی جهت کاهش اتلاف نوری در شبکه های روی تراشه ی نوری"، فصلنامه فناوری اطلاعات و ارتباطات ایران، 10(36 و 35) ، 26-15، 1397.
]3] W. Amin et al., "Performance evaluation of application mapping approaches for Network-on-Chip designs," IEEE Access, vol. 8, pp. 63607-63631, 2020.
]4] A. K. Singh, W. Jigang, A. Kumar, and T. Srikanthan, "Run-time mapping of multiple communicating tasks on MPSoC platforms," Procedia Computer Science, vol. 1, no. 1, pp. 1019-1026, 2010.
]5] S. Kaushik, A. K. Singh, and T. Srikanthan, "Computation and communication aware run-time mapping for NoC-based MPSoC platforms," in 2011 IEEE International SOC Conference, 2011, pp. 185-190: IEEE.
]6] M. Obaidullah and G. N. Khan, "Application mapping to mesh NoCs using a Tabu-search based swarm optimization," Microprocessors and Microsystems, vol. 55, pp. 13-25, 2017.
]7] B. Xie, T. Chen, W. Hu, X. Tang, and D. Wang, "An energy-aware online task mapping algorithm in NoC-based system," The Journal of Supercomputing, vol. 64, no. 3, pp. 1021-1037, 2013
]8] C. Wang, Y. Zhu, J. Jiang, X. Liu, and X. Han, "A dynamic contention-aware application allocation algorithm for many-core processor," in 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security, and 2015 IEEE 12th International Conference on Embedded Software and Systems, 2015, pp. 308-315: IEEE.
]9] T. Maqsood et al., "Energy and communication aware task mapping for MPSoCs," Journal of parallel and distributed computing, vol. 121, pp. 71-89, 2018.
]10] A. A. Heidari, S. Mirjalili, H. Faris, I. Aljarah, M. Mafarja, and H. Chen, "Harris hawks optimization: Algorithm and applications," Future Generation Computer Systems, vol. 97, pp. 849-872, 2019 .
]11] R. Abbassi, A. Abbassi, A. A. Heidari, and S. Mirjalili, "An efficient salp swarm-inspired algorithm for parameters identification of photovoltaic cell models," Energy conversion and management, vol. 179, pp. 362-372, 2019.
]12] H. Faris et al., "An intelligent system for spam detection and identification of the most relevant features based on evolutionary random weight networks," Information Fusion, vol. 48, pp. 67-83, 2019.
]13] G. Wu, "Across neighborhood search for numerical optimization," Information Sciences, vol. 329, pp. 597-618, 2016.
]14] J. Dréo, A. Pétrowski, P. Siarry, and E. Taillard, Metaheuristics for hard optimization: methods and case studies. Springer Science & Business Media, 2006.
]15] E.-G. Talbi, Metaheuristics: from design to implementation. John Wiley & Sons, 2009.
]16] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, "others. 1983," Optimization by simulated annealing. science, vol. 220, no. 4598, pp. 671-680, 1983.
]17] H. John, "Holland. genetic algorithms," Scientific american, vol. 267, no. 1, pp. 44-50, 1992.
]18] J. Luo, H. Chen, Y. Xu, H. Huang, and X. Zhao, "An improved grasshopper optimization algorithm with application to financial stress prediction," Applied Mathematical Modelling, vol. 64, pp. 654-668, 2018 .
]19] Q. Zhang, H. Chen, J. Luo, Y. Xu, C. Wu, and C. Li, "Chaos enhanced bacterial foraging optimization for global optimization," IEEE Access, vol. 6, pp. 64905-64919, 2018.
]20] M. Mafarja et al., "Evolutionary population dynamics and grasshopper optimization approaches for feature selection problems," Knowledge-Based Systems, vol. 145, pp. 25-45, 2018.
]21] I. Aljarah, M. Mafarja, A. A. Heidari, H. Faris, Y. Zhang, and S. Mirjalili, "Asynchronous accelerating multi-leader salp chains for feature selection," Applied Soft Computing, vol. 71, pp. 964-979, 2018.
]22] S. Salcedo-Sanz, "Modern meta-heuristics based on nonlinear physics processes: A review of models and design procedures," Physics Reports, vol. 655, pp. 1-70, 2016.
]23] L. F. Bittencourt, E. R. Madeira, and N. L. Da Fonseca, "Scheduling in hybrid clouds," IEEE Communications Magazine, vol. 50, no. 9, pp. 42-47, 2012.
]24] Q. Le, G. Yang, W. N. Hung, X. Song, and X. Zhang, "Pareto optimal mapping for tile-based network-on-chip under reliability constraints," International Journal of Computer Mathematics, vol. 92, no. 1, pp. 41-58, 2015.
]25] Y. Ben-Itzhak, E. Zahavi, I. Cidon, and A. Kolodny, "HNOCS: modular open-source simulator for heterogeneous NoCs," in 2012 international conference on embedded computer systems (SAMOS), 2012, pp. 51-57: IEEE.
]26] J. Huang, C. Buckl, A. Raabe, and A. Knoll, "Energy-aware task allocation for network-on-chip based heterogeneous multiprocessor systems," in 2011 19th International Euromicro Conference on Parallel, Distributed and Network-Based Processing, 2011, pp. 447-454: IEEE.
]27] G. Juve, A. Chervenak, E. Deelman, S. Bharathi, G. Mehta, and K. Vahi, "Characterizing and profiling scientific workflows," Future Generation Computer Systems, vol. 29, no. 3, pp. 682-692, 2013.
دو فصلنامه علمي فناوري اطلاعات و ارتباطات ایران | سال چهاردهم، شمارههای 51 و 52 ، بهار و تابستان 1401 |
|
کاهش بار شبکه با نگاشت برنامه کابردی در شبکه روی تراشه با استفاده از الگوریتم شاهین هریس گسسته
الهام حاجبی* وحید ستاری نائینی**
* دانشجوی کارشناسی ارشد، بخش مهندسی کامپیوتر، دانشگاه شهید باهنر کرمان، کرمان، ایران
** دانشیار، بخش مهندسی کامپیوتر، دانشگاه شهید باهنر کرمان، کرمان، ایران
تاریخ دریافت: 04/12/1399 تاریخ پذیرش: 03/06/1400
نوع مقاله: پژوهشی
چکیده
کاهش بار و مصرف انرژی در سیستمهای شبکه روی تراشه از اهمیت بسیاری برخوردار است و يكي از مهم‌ترين مباحثي که برای افزايش کارايي شبكه روی تراشه مطرح است، موضوع نگاشت يک برنامه کاربردی در شبكه روی تراشه است. حل مسئله نگاشت برنامه کاربردی برای يافتن بهترين نگاشت، يک موضوع پيچيده و زمانبر است و تاثير بسيار زيادی بر تأخير و انرژی مصرفي شبكه دارد. در اين مقاله با استفاده از الگوريتم شاهین هریس توانستهايم روشی را برای نگاشت هستههای پردازشي به روی شبكه روی تراشه ارائه کنيم تا بار روی شبکه و در نتیجه ازدحام در لینکها را کاهش داده و عملکرد شبکه بهبود ببخشیم. نتايج شبيه‌سازی نشان میدهد که اين الگوريتم عملکرد بهتری در مقايسه با الگوريتمهای پايه دارد.
واژگان کلیدی: شبکه روی تراشه- نگاشت هسته پردازشی - تأخیر شبکه - بهرهوری از لینک - الگوریتم شاهین هریس گسسته
1. مقدمه
در سیستم روی تراشه1 برای ارتباط میان اجزای سیستم، از تکنولوژی گذرگاه مشترک استفاده میکردند، با افزایش تعداد هستههای پردازشی روی تراشه و کوچکتر شدن اندازه نیمههادیها، تکنولوژی گذرگاه مشترک نمیتوانست از پهنای باند ارتباطی میان هستهها پشتیبانی کند. شبکه روی تراشه2 به عنوان یک بستر ارتباطی قابل استفاده مجدد و مقیاسپذیر برای سیستمهای روی تراشه پیشنهاد شد. NoC اجازه میدهد تعداد زیادی از هستهها در توپولوژیهای مختلف شبکه متصل شوند و بستهها را از طریق مسیریابها و لینکها تحت توپولوژی به کار رفته، در شبکه منتقل کنند و همچنین امکان ارتباطات موازی میان هستهها در NoC میسر میشود. توپولوژيهاي محبوب NoC که توسط محققان مورد استفاده قرار ميگيرند عبارتند از: حلقه، مش، توروس، درخت و مکعب است.
شبکه روی تراشه جزئی جدایی ناپذیر از سیستمهای چند پردازندهای است، بنابراین عملکرد شبکه روی تراشه مستقیماً بر عملکرد پردازندهها تأثیر می گذارد[1]. در شبکه روی تراشه چالشهایی مطرح شده است به طور مثال، پهنای باند ارتباطی بالا در شبکههای روی تراشه به معنی واقعی به ارتباط میان هستههای پردازشی مربوط میشود. افزایش یافتن پهنای باند ارتباطی، مصرف توان و تأخیر انتقال به عنوان یک گلوگاه در شبکه روی تراشه مطرح شد. یک راه حل آن استفاده از شبکههای روی تراشه نوری است]2[ اما راه حل دیگر، کم کردن حجم ارتباطی میان هستههای پردازشی است و این راه حل با نگاشت وظایف برنامهکاربردی روی هستههای پردازشی انجام میگیرد و خود نگاشت نیز یکی از چالشهای مطرح در سیستمهای چند پردازندهای مبتنی بر NoC است در نتیجه، عملکرد و کارایی سیستم را تحت تأثير قرار میدهد. نگاشت وظایف به دو صورت استاتیک یا پویا انجام میشود. نگاشت پویا در زمان اجرا انجام میشود و زمانبر میباشد. نگاشت استاتیک در زمان طراحی انجام و برای سیستمهای چندپردازندهای این نوع نگاشت توصیه میشود [3]{Belkebir, 2019 #40;Amin, 2020 #65}. نگاشت به عنوان یک مشکل رده سخت شناخته شده است. روشهای مختلفی برای نگاشت برنامه کاربردی روی NoC ارائه شده است که تعدادی از این روشها به صورت دستهبندی شده در مرجع[3] ذکر شده و هر کدام از این روشها معیارهای متفاوتی در نظر گرفتهاند. بیشتر روشهایی که انجام شده و در ادامه به آنها میپردازیم، هدف کاهش سربار ارتباطی و مصرف انرژی سیستم روی تراشه بوده است. برای مثال، در مرجع [4]، برای کاهش سربار ارتباطی، مصرف انرژی ارتباطی و ازدحام شبکه برای MPSoCs مبتنی بر NoC، یک نگاشت پویا اکتشافی وظایف را پیشنهاد میکند و تلاش میکند تا چندین وظیفهی ارتباطی را به همان و یا نزدیکترین عنصرهای پردازشی نگاشت کند. بااین‌وجود، روش پیشنهادی بار را در بین عنصرهای پردازشی موجود متعادل نمیکند. علاوه بر این روش پیشنهادی، بهینهسازی کلی سربارهای ارتباطی را تضمین نمیکند، زیرا تنها گرههای همسایه اصلی و فرعی برای قرار دادن در همان عنصر پردازشی در نظر گرفته میشود. این تجزیه‌وتحلیل بر روی شبکه روی تراشه با توپولوژی مش 8 × 8 و عناصر پردازشی همگن انجام‌شده است. برای غلبه بر مشکلات فوق، در مرجع [5] یک روش پیشپردازشی پیشنهاد دادند که تلاش میکند تا سربارهای ارتباطی را کاهش دهد و بار را در بین عنصرهای پردازشی موجود به‌طور مساوی متعادل کند. روش پیشنهادی، زمان اجرای برنامه کاربردی، مصرف انرژی و استفاده از منابع را بهبود میبخشد. با این حال، روش پیشپردازش منجر به محاسبات اضافی میشود و نتایج را در زمان اجرای الگوریتم افزایش میدهد. علاوه بر این، تجزیه‌وتحلیل با تعداد محدودی از وظایف بر روی شبکههای روی تراشه کوچکتر انجام‌شده است.
در مرجع [6] با ترکیب روشهای جستجوی ممنوعه3 و مبادله هستهها بر اساس حجم ارتباطی و بهینهسازی ازدحام ذرات گسسته4 (DPSO) یک نگاشت برای هستهها روی کاشیهای NoC ارائه شده است. هدف الگوریتم تاخیر ارتباطی حداقل شود. فضای جستجو نشاندهنده تمام ترکیبات هستهای است که به کاشیهای مختلف NoC اختصاص داده شده است. DPSO به‌عنوان روش اصلی بهینهسازی استفاده میشود و در آن حرکت ازدحامی ذرات تحت تاثیر بهترین مکان محلی5، بهترین مکان سراسری6 و بهینهسازی حجم ارتباطات است. در این روش از یک لیست جهت ممنوع کردن نقاط جستجویی که ذرات قبلا بازدید کردهاند، استفاده میشود. این روش هزینه ارتباطی، زمان تاخیر و انرژی مصرفی را کاهش میدهد. عملکرد این روش ترکیبی بهتر از روش DPSO است.
در مرجع [7] یک الگوریتم آنلاین انرژی آگاه برای نگاشت وظایف روی NoC پیشنهاد میکند. هدف الگوریتم کاهش مصرف انرژی ارتباطی است. اولین گام الگوریتم این است که وضعیت ارتباطات برنامههای کاربردی را در زمان اجرا تجزیه‌وتحلیل کند و وظیفهی با بالاترین میزان ارتباط انتخاب میکند. وظیفه انتخاب‌شده برای اولین بار نگاشت میشود. در مراحل بعدی، وظایف همسایه‌ی وظیفه انتخاب‌شده، بر اساس حجم ارتباطی مرتب شده و به نزدیکترین عناصر پردازشی نگاشت میشوند. به عنوان یک نتیجه از نگاشت انجام‌شده توسط این الگوریتم، وظایف با حجم ارتباطی زیاد نزدیکتر به یکدیگر قرار میگیرند، اما وظایفی که حجم ارتباطی کمی دارند ممکن است نادیده گرفته و از هم جدا شوند.
در مرجع [8] یک الگوریتم نگاشت برنامه کاربردی با توجه به رقابت NoC پیشنهاد کردند. الگوریتم پیشنهاد شده در دو مرحله کار میکند. در مرحله اول، یک منطقه مستطیلی از اندازه مورد نیاز برای نگاشت یک برنامه کاربردی ورودی شناسایی شده است. در مرحله بعدی، وظایف برنامه کاربردی به عنصرهای پردازشی در منطقه مشخص‌شده، با توجه به حجم ارتباطی لبههای متصل به وظایف وابسته اختصاص داده میشود. نتایج تجربی نشاندهنده برتر بودن الگوریتم پیشنهاد شده در مقایسه با الگوریتمهای FF و NN است. هدف ما در این مقاله، با کاهش حجم ارتباطی روی لینکهای میان مسیریابها در شبکه روی تراشه، ازدحام شبکه تحت تأثير قرار میگیرد. هرچه حجم ارتباطی میان هستهها کمتر باشد، احتمال ازدحام در شبکه کمتر خواهد شد. به همین دلیل ما از الگوریتم VEBAP 7 که از روش بستهبندی8 استفاده میکنیم و در مرجع [9] ارائه شده است، برای نگاشت وظایف روی هستههای پردازشی استفاده کردهایم تا بیشترین بهرهوری را از منابع داشته باشیم. وظایفی که حجم ارتباطی میان آنها زیاد است با قرار دادن در یک bin (اصطلاح bin در این روش به جای هستههای پردازشی استفاده میشود.)، میتوان حجم ارتباطی روی لینکها را کاهش داد. سپس با استفاده از الگوریتم شاهین هریس[10] و تابع هدفی که برای این الگوریتم در نظر گرفتیم، قصد داریم به نگاشتی با انرژی مصرفی کمتر و همچنین پراکندگی بار کمتر برسیم. انحراف معیار از جمله معیارهای پراکندگی که در این کار استفاده شده است. انحراف معیار میزان پراکندگی در تمام دادهها اما دامنه چارکی میزان پراکندگی در نیمی از دادههای میانی محاسبه میکند.
بخش‌بندی این مقاله به شرح زیر است. بخش 2 کارهای انجام شده در خصوص نگاشت آورده شده است. در بخش 3 مدل شبکه روی تراشه و گراف وظایف توصیف کردیم. و در بخش 4 به روش پیشنهادی ارائه شده میپردازیم و در نهایت در بخش 5 محیط شبیهسازی و نتایج حاصل از این مقاله شرح میدهیم و نتیجه حاصل از کار ارائه شده در بخش 6 آوردهایم.
2. پیش زمینه
بسیاری از مسائل دنیای واقعی در حوزه یادگیری ماشین و هوش مصنوعی به طور کلی ماهیت پیوسته، گسسته، محدود یا نامحدود دارند[11, 12]. با توجه به این ویژگیها، نمیتوان با استفاده از روشهای گرادیان مزدوج، برنامهریزی درجه دوم متوالی و روشهای شبه نیوتن، به حل بعضی از این مسائل پرداخت[13]. زیرا این روشها به اندازه کافی کارآمد نبودند. بر این اساس الگوریتمهای فراابتکاری به عنوان یک روشی برای حل این مسائل، طراحی و مورد استفاده قرار گرفتهاند. مزایای این الگوریتمها، سادگی و روند اجرای آنها در حل مسائل بهینهسازی است و معایب برخی از این الگوریتمها، نسبت به تنظیم پارامترها حساس میباشند و ممکن است همیشه به جواب بهینه سراسری همگرا نباشند [14].
به طور کلی، دو نوع الگوریتم فراابتکاری داریم [15]؛ نوع اول مبتنی بر یک راه حل مانند شبیهسازی تبریدی [16]، نوع دوم مبتنی بر جمعیت مانند الگوریتم ژنتیک است [17]. در نوع اول تنها یک راه حل در مرحله بهینهسازی پردازش میشود، در حالیکه در نوع دوم، شامل مجموعهای از راه حلها (یعنی جمعیت) در هر تکرار از روند بهینهسازی میشود. روشهای مبتنی بر جمعیت اغلب یک راه حل بهینه یا نزدیک به آن را پیدا میکنند که یا همان جواب دقیق مسئله میباشد که به آن جواب بهینه سراسری و یا جوابی نزدیک به آن، بهینه محلی گویند. الگوریتمهای فراابتکاری مبتنی بر جمعیت عمدتاً از پدیدههای طبیعی تقلید میکنند[18, 19]. این الگوریتمها فرآیند بهینهسازی را با تولید مجموعهای از افراد (جمعیت) شروع میکنند، به طوری که هر یک از افراد در جامعه نماینده یک راه حل انتخابی برای مسئله بهینهسازی هستند. با جایگزینی جمعیت فعلی با جمعیت تازه تولید شده با استفاده از برخی از عملگرهای غالباً تصادفی، این جمعیت به طور تکراری تکامل مییابد[20]. فرآیند بهینهسازی تا رسیدن به یک معیار توقف (یعنی حداکثر تعداد تکرارها) انجام میشود[21].
تمام الگوریتمهای فرااکتشافی دارای یک ویژگی مشترک هستند: مراحل جستجو دارای دو مرحله اکتشاف و بهرهبرداری است [22]. هر الگوریتم تکاملی جدیدی که معرفی میشود برای اثبات قدرت خود در بهینهسازی باید بر روی دو مرحله مهم یعنی اکتشاف (Exploration) و بهرهبرداری (Exploitation) تمرکز خوبی داشته باشد و بتواند تعادل خوبی بین این دو مرحله ایجاد کند. سپس بر روی مسائل معیار مختلف آزمایش شود و نتایج آن با الگوریتمهای قدیمیتر مقایسه شود.
ایده اصلی الگوریتم HHO، رفتار مشارکتی و سبک تعقیب شاهین هریس در طبیعت است، که به نام حمله غافلگیرانه شناخته میشود. در این راهکار هوشمندانه، چندین شاهین هریس به صورت مشارکتی و با همکاری همدیگر تلاش میکنند تا یک طعمه را از جهتهای مختلف غافلگیر کنند. شاهین هریس، میتواند الگوهای تعقیب و گریز متنوعی را براساس ماهیت پویای سناریوها و الگوهای شکار از خود نشان دهد. این الگوریتم به خوبی تعادل بین مراحل اکتشاف و بهرهبرداری را ایجاد میکند[10]. از دیگر مزایای این الگوریتم، نیاز به تنظیم پارامتر همانند الگوریتمهایی چون PSO، TLBO و ... ندارد و همچنین، نتایج این الگوریتم نسبت به الگوریتمهای قدیمی روی مسائل معیار بهتر بوده است. به همین دلیل ما از الگوریتم HHO استفاده کردهایم.
شبه کد الگوریتم شاهین هریس در شکل 1 آورده شده است.
(HHO)الگوریتم شاهین هریس | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Inputs: The population size N and maximum number of iterations T
Outputs: The location of rabbit and its fitness value
Initialize the random population Xi(i=1,2,3,…,N) While (stopping condition is not met) do Calculate the fitness values of hawks Set Xrabbit as the location of rabbit (best location) For (each hawk (Xi)) do Update the initial energy E0 and jump strength J E0=2rand()-1, J=2(1-rand()) Update the E using Eq.2 If (|E| Update the location vector using Eq.1 If (|E| If (r Update the location vector else If (r Update the location vector else If (r with progressive rapid dives Update the location vector else If (r besiege with progressive rapid dives Update the location vector Return Xrabbit
شکل 1. شبه کد الگویتم شاهین هریس[10] 3. مدل سیستم ارائه شده
1.3 مدل NoC یک گرافی است که با NG=(P,L) نشان داده میشود. P شامل مجموعهای از کاشی9ها که هر کاشی دارای یک شناسه است و هر کدام شامل یک عنصر پردازشی10 (PE) که از طریق یک رابط شبکه11 (NI) به یک مسیریاب (R) متصل است. L شامل مجموعهای از لینکهای 2.3 گراف هسته
شکل 2.(آ) مدل NoC (ب) گراف هسته - نگاشت هستههای پردازشی به کاشیهای NoC 3.3 گراف برنامه کاربردی
شکل 4. شبه کد الگوریتم شاهین هریس گسسته در ادامه هر یک از مراحل را توضیح میدهیم. 4_1_1 مرحله اکتشاف در این گام الگوریتم به دنبال کشف فضای جستجو میباشد و بهروزرسانی موقعیت شاهینها براساس عملگر تصادفی و یا براساس موقعیت سایر شاهینها صورت میگیرد.
شکل 5. مثالی از بدست آوردن موقعیت جدید شاهین با انجام عملیات (آ) 4_1_2 مرحله بهرهبرداری در این گام، الگوریتم به دنبال بهبود جوابهای پیدا شده میباشد و از عملگرهای محاصره سخت12 و محاصره نرم13 استفاده میکند. فرض کنید که r شانس طعمه در فرار موفقیتآمیز یا فرار ناموفق قبل از حمله غافلگیرانه باشد. در حالی که طعمه فرار میکند، شاهینها ، محاصره سخت یا نرم را برای گرفتن طعمه شکل میدهند. به این معنی که آنها بر اساس انرژی باقیمانده طعمه، حلقه محاصره را به صورت سخت یا نرم تنگتر میکنند. 4_1_2_1 محاصره نرم: jump_strength، یک عدد تصادفی بین 0 تا اندازه جمعیت شاهینها است. در این گام، اگر 4_1_2_2 محاصره سخت: ابتدا مقدار 4_1_2_3 محاصره نرم با شیرجههای پیشرو14: در این گام، اگر 4_1_2_4 محاصره سخت با شیرجههای پیشرو15 : در این گام، 4_1_3 انتقال از مرحله اکتشاف به مرحله بهرهبرداری برای انتقال از مرحله اکتشاف به مرحله بهرهبرداری با توجه به معادله زیر انجام میشود. به طور خلاصه، اکتشاف هنگامی اتفاق میافتد که 1≤E||، در حالی که بهرهبرداری زمانی که 1˂E|| باشد، اتفاق میافتد. E0انرژی اولیه طعمه است.
E انرژی فرار طعمه را نشان میدهد، E0 انرژی اولیه و مقدار آن بین 1 و 1- میباشد. T برابر با تعداد کل تکرارها است[10]. 4_2 تعیین تابع هدف الگوریتم HHO یک تکنیک بهینهسازی مستقل از گرادیان و مبتنی بر جمعیت میباشد، بنابراین میتوان از این الگوریتم برای حل مسائل بهینهسازی به شرط وجود یک تابع هدف مناسب، استفاده کرد. تعیین تابع هدف بستگی به مسئله مورد نظر دارد. در این مقاله هدف کاهش انرژی مصرفی و بهتر شدن عملکرد سیستم است و با توجه به اینکه با کاهش فاصله میان وظایف مرتبط میتوان انرژی ارتباطی را کاهش داد. در تابع هدف مقدار ENoC را محاسبه و با نگاشت اولیه که به صورت تصادفی تعیین میشود، مقایسه میکنیم و بعد از T تکرار الگوریتم شاهین هریس، مقدار ENoC بهینهتر میشود. با توجه به معادله 1 که برای محاسبه انرژی ارتباطی شبکه به کار میرود میتوان به صورت زیر به ساده کرد:
در محاسبه انرژی ارتباطی میتوان انرژی مسیریاب، لینک و هسته را ناچیز در نظر گرفت به این دلیل که مقدار حجم ارتباطی و تعداد گام تأثیر بیشتری در محاسبه بار شبکه دارند و از آنجا که میتوان وزن هر لینک با استفاده از رابطه 3 محاسبه کرد. در نتیجه برای محاسبه بار شبکه در تابع هدف میتوان از ساده شده معادله 1 یعنی معادله 9 استفاده کرد. تعادل بار لینک نه تنها میتواند ازدحام شبکه و تأخير در صف را کاهش دهد بلکه از ایجاد نقاط داغ نیز جلوگیری میکند [24]. ما در نظر داریم تا حد امکان وظایف ارتباطی را در لینکهای مختلف توزیع کنیم. اگر بیشتر وظایف ارتباطی از تعداد محدودی از لینکها استفاده کنند، ممکن است ازدحام شبکه و نقاط داغ افزایش یابد. بنابراین با محاسبه جذر واریانس ( انحراف معیار) بار هر لینک طبق معادله زیر، تعادل بار را ارزیابی میکنیم.
در این معادله loadi بار لینک i و ما در این قسمت توابع هدف را مطابق با اهداف گفته شده، تعریف میکنیم. هدف ما در این قسمت، تعیین تابع هدف درست میباشد. 4_2_1 VARYANCE در الگوریتمی که VARYANCE نام گذاری کردهایم، تابع هدف را به صورت زیر قرار دادیم و نتایج آن را در بخش بعدی میتوان مشاهده کرد. (ENoC > ENoCrandom || load > loadrandom ) 4_2_2 CHARAK ما از دامنه میان چارکی که از جمله معیارهای پراکندگی میباشد، استفاده کردیم. IQR=Q3−Q1 Q1چارک اول و Q3 چارک سوم است. در الگوریتم CHARAK تابع هدف را به صورت زیر قرار دادهایم. (ENoC > ENoCrandom || IQR > IQR random) 4_2_3 OR در الگوریتم OR تابع هدف به صورت زیر تعریف کردهایم. (ENoC > ENoCrandom || load > loadrandom || IQR > IQR random) 4_2_4 &OR در الگوریتم &OR تابع هدف به صورت زیر تعریف کردهایم. (ENoC > ENoCrandom || (load > loadrandom && IQR > IQR random)) شبه کد تابع هدف &OR در شکل 6 آورده شده است.
شکل 6. شبه کد تابع هدف 4_3 محاسبه پیچیدگی الگوریتم پیچیدگی الگوریتم برابر با O (T×N× نتایج هر چهار تابع هدف در بخش بعد برای مقدار انرژی مصرفی 50 گراف مختلف نشان داده شده است. 5. محیط شبیهسازی و ارزیابی آزمایشها 5-1 محیط شبیهسازی محیط شبکه روی تراشه با مش دو بعدی در چارچوب جاوا و با استفاده از Eclipse IDE را شبیهسازی کردهایم. و برای ارزیابی عملکرد روش ارائه شده از آن استفاده میکنیم. HNOCS یک شبیهساز NoC منبع باز و مبتنی بر OMNeT++ است. HNOCS مخفف Heterogeneous Network-on-Chip Simulator است. این شبیهساز یک چارچوب منبع باز، مقیاس پذیر، قابل توسعه و کاملا قابل پارامترسازی برای مدلسازی انواع NoC است [25]. شبیهساز HNOCS از توپولوژی مش، سوئیچینگ خزشی16 با کانالهای مجازی، کنترل جریان مبتنی بر اعتبار و از الگوریتم مسیریابی XY برای مسیریابی بستهها استفاده میکند. HNOCS مجموعهای از اندازهگیریهای آماری، مانند توان عملیاتی و تأخيرهای مختلف را در سطح فلیت و بسته ارائه میدهد و ما از این شبیهساز استفاده کردیم، زیرا دارای ساختاری مدولار است که اصلاح و افزودن به آن در مقایسه با سایر شبیهسازها آسان‌تر میکند.
جدول 1. تنظیم پارامترهای HNOCS
در حالت ساده این شبیهساز برای هستههای همگن طراحی شده و میتوان هستههای ناهمگن نیز به آن اضافه کرد اما در این کار همان حالت اولیه را در نظر گرفتیم و فایل خروجی بدست آمده از Eclipse IDE را در این شبیهساز اجرا کردیم. روش پیشنهادی را با الگوریتمهای FF، NN [7] و SA [26] مقایسه کردیم. 5_2 جریانهای کاری ساختگی کار ارائه شده را برای 50 جریان کاری با اندازه مش NoC از 5×5 تا 10×10، تعداد bin از 25 تا 100 و تعداد وظایف در گراف برنامهکاربردی از 300 تا 1000، مورد آزمایش قرار دادیم.
شکل 7. میانگین انرژی مصرفی برای اندازههای مختلف NOC در شکل 7، میانگین انرژی مصرفی در اندازههای مختلف NoC نشان داده شده است. در روش OR انرژی مصرفی نسبت به روش &OR بیشتر است. در روش OR به دلیل اینکه الگوریتم باید نگاشتی را که هم انرژی مصرفی و هم انحراف معیار بار و دامنه چارکی بار کمتری دارد را بیابد، در نگاشتهای بهینه محلی اولیه متوقف میشود. اما در روش &OR به دلیل اینکه باید هم انرژی مصرفی و هم انحراف معیار بار یا دامنه چارکی بار کمتری دارد را بیابد، نگاشتهای محلی بهتری را مییابد و پراکندگی بار کمتری دارند. همانطور که مشاهده میشود روش &OR نسبت به روشهای دیگر انرژی مصرفی کمتری دارد. در سه شکل زیر بهرهوری از لینک، تأخير انتها به انتها و تأخير شیکه برای گرافهای وظایف در چهار روش FF، NN، SA و &OR نشان داده شده است. هر چه فاصله منهتن کمتر به عبارت دیگر وظایف به یکدیگر نزدیکتر باشند، انرژی ارتباطی و در نتیجه انرژی مصرفی کل کاهش مییابد. همچنین برای متعادل کردن بار لینکها از معیارهای پراکندگی استفاده شده است. به همین دلیل در این روش علاوه بر کاهش انرژی ارتباطی، کاهش میزان پراکندگی بار نیز در نظر گرفته شده است تا به یک نگاشت با انرژی مصرفی کم و میزان پراکندگی بار کم برسیم.
شکل 8. میانگین بهرهوری از لینکها در اندازههای مختلف NoC در شکل 8 میانگین بهرهوری از لینکها را در چهار روش مختلف نشان میدهد که روش &OR نسبت به سه روش دیگر میانگین بهرهوری کمتری داشته به این دلیل که با کاهش بار ارتباطی در شبکه و تعادل در میزان پراکندگی بار در لینکهای شبکه بهرهوری از لینکها کاهش مییابد.
شکل 9. میانگین تأخير شبکه در اندازههای مختلف NoC
شکل 10. میانگین تأخير انتها به انتها در اندازههای مختلف NoC در شکلهای 9 و 10 نتایج روش &OR نسبت به سه روش دیگر مشاهده میشود. تأخیر تحت تأثیر بار روی لینکها در NoC به عبارتی دیگر با کاهش میزان بار ارتباطی روی لینکها میتوان تا حدودی تأخیر را کاهش داد. در روش &OR هدف کاهش بار ارتباطی شبکه و تعادل در میزان پراکندگی بار میباشد به همین دلیل در مقایسه با سه روش دیگر توانسته تأخیر در شبکه نسبت به تأخیر انتها به انتها را بیشتر کاهش دهد. 5_3 جریانهای کاری واقعی علاوه بر اینکه کار ارائه شده را روی جریانهای ساختگی بررسی کردیم از چند جریان کاری واقعی همچون Cybershake، Genome، Montage وLigo [27] برای ارزیابی این روش استفاده میکنیم. در جدول زیر اطلاعات مورد نیاز برای اجرای جریانهای کار آورده شده است. جدول 2- اطلاعات مورد نیاز برای اجرای جریانهای کار
ما برای یک نمونه از اجرای جریانهای کاری در روشهای SA و &OR مقدار بهرهوری از لینک، تأخير انتها به انتها و تأخير شبکه را با اجرا در HNOCS محاسبه کردیم. در جداول زیر مقدار مصرف انرژی و انحراف معیار بار نیز آورده شده است. جدول 3. مقدار انرژی مصرفی برای هریک از جریانهای کاری در الگوریتمهای مختلف
در جدول 3، مقدار انرژی مصرفی برای هر یک از جریانهای کار محاسبه شده است. روش &OR مقدار انرژی مصرفی کمتری نسبت به روشهای FF، NN و SA داشته است.
جدول 4. مقدار انحراف معیار بار لینک برای هریک از جریانهای کاری در الگوریتمهای مختلف
در جدول 4، مقدار انحراف معیار بار لینک برای هر یک از جریانهای کار محاسبه شده است. و روش &OR مقدار انحراف معیار کمتری نسبت به روشهای FF، NN و SA داشته است.
شکل 11. بهرهوری از لینک برای نمونهای از جریانهای کاری با متعادل کردن بار روی لینکها و کاهش انرژی ارتباطی میتوان بهرهوری از لینکها را کاهش داد. در شکل 11، روش &OR نسبت به سه روش دیگر میزان بهرهوری از لینک را کاهش داده است.
شکل 12. تأخير انتها به انتها برای نمونهای از جریانهای کاری در شکل 12، تأخير انتها به انتها برای جریانهای کاری نشان داده شده است. روش &OR نسبت به سه روش دیگر میزان تأخير انتها به انتها را کاهش داده است. در جریان کاری LIGO کاهش تاخیر انتها به انتها نسبت به سه جریان کاری دیگر بیشتر مشاهده میشود.
شکل 13. تأخير شبکه برای نمونهای از جریانهای کاری در شکل 13، تأخير شبکه برای جریانهای کاری نشان داده شده است. روش &OR نسبت به سه روش دیگر تأخير شبکه را کاهش داده است که نتیجه کاهش انرژی ارتباطی و میزان پراکندگی بار میباشد. همان طور که مشاهده میشود، کاهش انرزی ارتباطی تأثیر بیشتری در کاهش تأخیر شبکه نسبت به تأخیر انتها به انتها دارد.
6. نتیجهگیری نگاشت وظایف روی شبکه روی تراشه یک مسئله رده سخت است. در این مقاله سعی بر آن شد که با استفاده از الگوریتم شاهین هریس، بتوان نگاشتی را برای هستههای پردازشی بر روی NoC انتخاب کرد که علاوه بر اینکه انرژی مصرفی کمتری داشته باشد، میزان پراکندگی بار کمتری داشته تا بهرهوری از لینکهای NoC متعادل و همچنین تأخير کمتری در شبکه داشته باشد. همانطور که نشان داده شد، روش &OR در مقایسه با الگوریتمهای پایه، عملکرد بهتری دارد.
مراجع ]1] A. V. Bhaskar and T. Venkatesh, "Performance analysis of network-on-chip in many-core processors," Journal of Parallel and Distributed Computing, vol. 147, pp. 196-208, 2021. [2] اسدی بهاره، رشادی میدیا، خادم زاده احمد، کرباسی مصطفی،"مدل های چرخشی تطابقی و الگوهای ترافیکی جهت کاهش اتلاف نوری در شبکه های روی تراشه ی نوری"، فصلنامه فناوری اطلاعات و ارتباطات ایران، 10(36 و 35) ، 26-15، 1397. ]3] W. Amin et al., "Performance evaluation of application mapping approaches for Network-on-Chip designs," IEEE Access, vol. 8, pp. 63607-63631, 2020. ]4] A. K. Singh, W. Jigang, A. Kumar, and T. Srikanthan, "Run-time mapping of multiple communicating tasks on MPSoC platforms," Procedia Computer Science, vol. 1, no. 1, pp. 1019-1026, 2010. ]5] S. Kaushik, A. K. Singh, and T. Srikanthan, "Computation and communication aware run-time mapping for NoC-based MPSoC platforms," in 2011 IEEE International SOC Conference, 2011, pp. 185-190: IEEE. ]6] M. Obaidullah and G. N. Khan, "Application mapping to mesh NoCs using a Tabu-search based swarm optimization," Microprocessors and Microsystems, vol. 55, pp. 13-25, 2017. ]7] B. Xie, T. Chen, W. Hu, X. Tang, and D. Wang, "An energy-aware online task mapping algorithm in NoC-based system," The Journal of Supercomputing, vol. 64, no. 3, pp. 1021-1037, 2013 ]8] C. Wang, Y. Zhu, J. Jiang, X. Liu, and X. Han, "A dynamic contention-aware application allocation algorithm for many-core processor," in 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security, and 2015 IEEE 12th International Conference on Embedded Software and Systems, 2015, pp. 308-315: IEEE. ]9] T. Maqsood et al., "Energy and communication aware task mapping for MPSoCs," Journal of parallel and distributed computing, vol. 121, pp. 71-89, 2018. ]10] A. A. Heidari, S. Mirjalili, H. Faris, I. Aljarah, M. Mafarja, and H. Chen, "Harris hawks optimization: Algorithm and applications," Future Generation Computer Systems, vol. 97, pp. 849-872, 2019 . ]11] R. Abbassi, A. Abbassi, A. A. Heidari, and S. Mirjalili, "An efficient salp swarm-inspired algorithm for parameters identification of photovoltaic cell models," Energy conversion and management, vol. 179, pp. 362-372, 2019. ]12] H. Faris et al., "An intelligent system for spam detection and identification of the most relevant features based on evolutionary random weight networks," Information Fusion, vol. 48, pp. 67-83, 2019. ]13] G. Wu, "Across neighborhood search for numerical optimization," Information Sciences, vol. 329, pp. 597-618, 2016. ]14] J. Dréo, A. Pétrowski, P. Siarry, and E. Taillard, Metaheuristics for hard optimization: methods and case studies. Springer Science & Business Media, 2006. ]15] E.-G. Talbi, Metaheuristics: from design to implementation. John Wiley & Sons, 2009. ]16] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, "others. 1983," Optimization by simulated annealing. science, vol. 220, no. 4598, pp. 671-680, 1983. ]17] H. John, "Holland. genetic algorithms," Scientific american, vol. 267, no. 1, pp. 44-50, 1992. ]18] J. Luo, H. Chen, Y. Xu, H. Huang, and X. Zhao, "An improved grasshopper optimization algorithm with application to financial stress prediction," Applied Mathematical Modelling, vol. 64, pp. 654-668, 2018 . ]19] Q. Zhang, H. Chen, J. Luo, Y. Xu, C. Wu, and C. Li, "Chaos enhanced bacterial foraging optimization for global optimization," IEEE Access, vol. 6, pp. 64905-64919, 2018. ]20] M. Mafarja et al., "Evolutionary population dynamics and grasshopper optimization approaches for feature selection problems," Knowledge-Based Systems, vol. 145, pp. 25-45, 2018. ]21] I. Aljarah, M. Mafarja, A. A. Heidari, H. Faris, Y. Zhang, and S. Mirjalili, "Asynchronous accelerating multi-leader salp chains for feature selection," Applied Soft Computing, vol. 71, pp. 964-979, 2018. ]22] S. Salcedo-Sanz, "Modern meta-heuristics based on nonlinear physics processes: A review of models and design procedures," Physics Reports, vol. 655, pp. 1-70, 2016. ]23] L. F. Bittencourt, E. R. Madeira, and N. L. Da Fonseca, "Scheduling in hybrid clouds," IEEE Communications Magazine, vol. 50, no. 9, pp. 42-47, 2012. ]24] Q. Le, G. Yang, W. N. Hung, X. Song, and X. Zhang, "Pareto optimal mapping for tile-based network-on-chip under reliability constraints," International Journal of Computer Mathematics, vol. 92, no. 1, pp. 41-58, 2015. ]25] Y. Ben-Itzhak, E. Zahavi, I. Cidon, and A. Kolodny, "HNOCS: modular open-source simulator for heterogeneous NoCs," in 2012 international conference on embedded computer systems (SAMOS), 2012, pp. 51-57: IEEE. ]26] J. Huang, C. Buckl, A. Raabe, and A. Knoll, "Energy-aware task allocation for network-on-chip based heterogeneous multiprocessor systems," in 2011 19th International Euromicro Conference on Parallel, Distributed and Network-Based Processing, 2011, pp. 447-454: IEEE. ]27] G. Juve, A. Chervenak, E. Deelman, S. Bharathi, G. Mehta, and K. Vahi, "Characterizing and profiling scientific workflows," Future Generation Computer Systems, vol. 29, no. 3, pp. 682-692, 2013.
[1] نویسنده مسئول: وحید ستاری نائینی vsnaeini@uk.ac.ir System-on-Chip (SoC)
[2] Network-on-Chip (NoC) [3] Tabu-search [4] Discrete Particle Swarm Optimization [5] local best [6] global best [7] Variable bEnefit Bin pAcking Problem [8] bin packing [9] tile [10] Processing Element [11] Network interface [12] Hard besiege [13] Soft besiege [14] Soft besiege with progressive rapid dives [15] Hard besiege with progressive rapid dives [16] Wormhole switching Reduction of network load by mapping the application in the network on a chip using the discrete Harris hawk algorithm
Abstract: Reducing load and power consumption in on-chip network systems is very important and one of the most important issues to increase the efficiency of on-chip network is the issue of mapping an application on the chip network. Solving the application mapping problem to find the best mapping is a complex and time consuming issue and has a huge impact on network latency and power consumption. In this paper, using the Harris hawk algorithm, we have been able to provide a method for mapping processing cores to the network on chip to reduce the load on the network and thus congestion in the links and improve network performance. The simulation results show that this algorithm performs better than the basic algorithms.
Keyword: Network-on-chip, Core-mapping, Latency, Utilization of link, HHO رایمگ
سامانه رایمگ تمامی فرآیندهای دریافت، ارزیابی و داوری، ویراستاری، صفحه‌آرایی و انتشار الکترونیکی نشریات علمی را به انجام می‌رساند
پیوندهای سایتمراکز مرتبطپشتیبانی
صفحات رسمی
حقوق این وب‌سایت متعلق به سامانه مدیریت نشریات رایمگ است. |
