Manuscript ID : 1401061639262 Visit : 4549 Page: 231 - 244

Article Type: Original Research

Reduction of network load by mapping the application in the network on a chip using the discrete Harris hawk algorithm

Subject Areas :

Elham Hajebi ¹ , Vahid Sattari-Naeini ^{2
*}

1 - Department of Computer Engineering
2 -

Received: 2021-02-22 Accepted : 2021-05-27 Published : 2022-09-14

Keywords: Network-on-chip, Core-mapping, Latency, Utilization of link, HHO,

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.

References:

]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.

Full-Text:

دو فصلنامه علمي

فناوري اطلاعات و ارتباطات ایران

سال چهاردهم، شمارههای ‌51 و 52 ، بهار و تابستان 1401

صص: 231_244

$E:\E Drive\logo\iicta Logo0.JPG$

کاهش بار شبکه با نگاشت برنامه کابردی در شبکه روی تراشه با استفاده از الگوریتم شاهین هریس گسسته

الهام حاجبی* وحید ستاری نائینی**

* دانشجوی کارشناسی ارشد، بخش مهندسی کامپیوتر، دانشگاه شهید باهنر کرمان، کرمان، ایران

** دانشیار، بخش مهندسی کامپیوتر، دانشگاه شهید باهنر کرمان، کرمان، ایران

تاریخ دریافت: 04/12/1399 تاریخ پذیرش: 03/06/1400

نوع مقاله: پژوهشی

چکیده

کاهش بار و مصرف انرژی در سیستمهای شبکه روی تراشه از اهمیت بسیاری برخوردار است و يكي از مهم‌ترين مباحثي که برای افزايش کارايي شبكه روی تراشه مطرح است، موضوع نگاشت يک برنامه کاربردی در شبكه روی تراشه است. حل مسئله نگاشت برنامه کاربردی برای يافتن بهترين نگاشت، يک موضوع پيچيده و زمانبر است و تاثير بسيار زيادی بر تأخير و انرژی مصرفي شبكه دارد. در اين مقاله با استفاده از الگوريتم شاهین هریس توانستهايم روشی را برای نگاشت هستههای پردازشي به روی شبكه روی تراشه ارائه کنيم تا بار روی شبکه و در نتیجه ازدحام در لینکها را کاهش داده و عملکرد شبکه بهبود ببخشیم. نتايج شبيه‌سازی نشان میدهد که اين الگوريتم عملکرد بهتری در مقايسه با الگوريتمهای پايه دارد.

واژگان کلیدی: شبکه روی تراشه- نگاشت هسته پردازشی - تأخیر شبکه - بهرهوری از لینک - الگوریتم شاهین هریس گسسته

1. مقدمه

در سیستم روی تراشه¹ برای ارتباط میان اجزای سیستم، از تکنولوژی گذرگاه مشترک استفاده میکردند، با افزایش تعداد هستههای پردازشی روی تراشه و کوچک‌تر شدن اندازه نیمههادیها، تکنولوژی گذرگاه مشترک نمیتوانست از پهنای باند ارتباطی میان هستهها پشتیبانی کند. شبکه روی تراشه² به عنوان یک بستر ارتباطی قابل استفاده مجدد و مقیاسپذیر برای سیستمهای روی تراشه پیشنهاد شد. NoC اجازه میدهد تعداد زیادی از هستهها در توپولوژیهای مختلف شبکه متصل شوند و بستهها را از طریق مسیریابها و لینکها تحت توپولوژی به کار رفته، در شبکه منتقل کنند و همچنین امکان ارتباطات موازی میان هستهها در NoC میسر میشود. توپولوژيهاي محبوب NoC که توسط محققان مورد استفاده قرار ميگيرند عبارتند از: حلقه، مش، توروس، درخت و مکعب است.

شبکه روی تراشه جزئی جدایی ناپذیر از سیستمهای چند پردازندهای است، بنابراین عملکرد شبکه روی تراشه مستقیماً بر عملکرد پردازندهها تأثیر می گذارد[1]. در شبکه روی تراشه چالشهایی مطرح شده است به طور مثال، پهنای باند ارتباطی بالا در شبکههای روی تراشه به معنی واقعی به ارتباط میان هستههای پردازشی مربوط میشود. افزایش یافتن پهنای باند ارتباطی، مصرف توان و تأخیر انتقال به عنوان یک گلوگاه در شبکه روی تراشه مطرح شد. یک راه حل آن استفاده از شبکههای روی تراشه نوری است]2[ اما راه حل دیگر، کم کردن حجم ارتباطی میان هستههای پردازشی است و این راه حل با نگاشت وظایف برنامهکاربردی روی هستههای پردازشی انجام میگیرد و خود نگاشت نیز یکی از چالشهای مطرح در سیستمهای چند پردازندهای مبتنی بر NoC است در نتیجه، عملکرد و کارایی سیستم را تحت تأثير قرار میدهد. نگاشت وظایف به دو صورت استاتیک یا پویا انجام میشود. نگاشت پویا در زمان اجرا انجام میشود و زمانبر میباشد. نگاشت استاتیک در زمان طراحی انجام و برای سیستمهای چندپردازندهای این نوع نگاشت توصیه میشود [3]{Belkebir, 2019 #40;Amin, 2020 #65}. نگاشت به عنوان یک مشکل رده سخت شناخته شده است. روشهای مختلفی برای نگاشت برنامه کاربردی روی NoC ارائه شده است که تعدادی از این روشها به صورت دستهبندی شده در مرجع[3] ذکر شده و هر کدام از این روشها معیارهای متفاوتی در نظر گرفتهاند. بیشتر روشهایی که انجام شده و در ادامه به آنها میپردازیم، هدف کاهش سربار ارتباطی و مصرف انرژی سیستم روی تراشه بوده است. برای مثال، در مرجع [4]، برای کاهش سربار ارتباطی، مصرف انرژی ارتباطی و ازدحام شبکه برای MPSoCs مبتنی بر NoC، یک نگاشت پویا اکتشافی وظایف را پیشنهاد میکند و تلاش میکند تا چندین وظیفهی ارتباطی را به همان و یا نزدیکترین عنصرهای پردازشی نگاشت کند. بااین‌وجود، روش پیشنهادی بار را در بین عنصرهای پردازشی موجود متعادل نمی‌کند. علاوه بر این روش پیشنهادی، بهینه‌سازی کلی سربارهای ارتباطی را تضمین نمیکند، زیرا تنها گرههای همسایه اصلی و فرعی برای قرار دادن در همان عنصر پردازشی در نظر گرفته میشود. این تجزیه‌وتحلیل بر روی شبکه روی تراشه با توپولوژی مش 8 × 8 و عناصر پردازشی همگن انجام‌شده است. برای غلبه بر مشکلات فوق، در مرجع [5] یک روش پیشپردازشی پیشنهاد دادند که تلاش میکند تا سربارهای ارتباطی را کاهش دهد و بار را در بین عنصرهای پردازشی موجود به‌طور مساوی متعادل کند. روش پیشنهادی، زمان اجرای برنامه کاربردی، مصرف انرژی و استفاده از منابع را بهبود میبخشد. با این ‌حال، روش پیشپردازش منجر به محاسبات اضافی میشود و نتایج را در زمان اجرای الگوریتم افزایش میدهد. علاوه بر این، تجزیه‌وتحلیل با تعداد محدودی از وظایف بر روی شبکههای روی تراشه کوچکتر انجام‌شده است.

در مرجع [6] با ترکیب روشهای جستجوی ممنوعه³ و مبادله هستهها بر اساس حجم ارتباطی و بهینهسازی ازدحام ذرات گسسته⁴ (DPSO) یک نگاشت برای هستهها روی کاشیهای NoC ارائه شده است. هدف الگوریتم تاخیر ارتباطی حداقل شود. فضای جستجو نشاندهنده تمام ترکیبات هستهای است که به کاشیهای مختلف NoC اختصاص داده شده است. DPSO به‌عنوان روش اصلی بهینهسازی استفاده میشود و در آن حرکت ازدحامی ذرات تحت تاثیر بهترین مکان محلی⁵، بهترین مکان سراسری⁶ و بهینهسازی حجم ارتباطات است. در این روش از یک لیست جهت ممنوع کردن نقاط جستجویی که ذرات قبلا بازدید کردهاند، استفاده میشود. این روش هزینه ارتباطی، زمان تاخیر و انرژی مصرفی را کاهش میدهد. عملکرد این روش ترکیبی بهتر از روش DPSO است.

در مرجع [7] یک الگوریتم آنلاین انرژی آگاه برای نگاشت وظایف روی NoC پیشنهاد میکند. هدف الگوریتم کاهش مصرف انرژی ارتباطی است. اولین گام الگوریتم این است که وضعیت ارتباطات برنامههای کاربردی را در زمان اجرا تجزیه‌وتحلیل کند و وظیفهی با بالاترین میزان ارتباط انتخاب میکند. وظیفه انتخاب‌شده برای اولین بار نگاشت میشود. در مراحل بعدی، وظایف همسایه‌ی وظیفه انتخاب‌شده، بر اساس حجم ارتباطی مرتب‌ شده و به نزدیکترین عناصر پردازشی نگاشت میشوند. به‌ عنوان یک نتیجه از نگاشت انجام‌شده توسط این الگوریتم، وظایف با حجم ارتباطی زیاد نزدیکتر به یکدیگر قرار میگیرند، اما وظایفی که حجم ارتباطی کمی دارند ممکن است نادیده گرفته و از هم جدا شوند.

در مرجع [8] یک الگوریتم نگاشت برنامه کاربردی با توجه به رقابت NoC پیشنهاد کردند. الگوریتم پیشنهاد شده در دو مرحله کار میکند. در مرحله اول، یک منطقه مستطیلی از اندازه مورد نیاز برای نگاشت یک برنامه کاربردی ورودی شناسایی ‌شده است. در مرحله بعدی، وظایف برنامه کاربردی به عنصرهای پردازشی در منطقه مشخص‌شده، با توجه به حجم ارتباطی لبههای متصل به وظایف وابسته اختصاص داده میشود. نتایج تجربی نشان‌دهنده برتر بودن الگوریتم پیشنهاد شده در مقایسه با الگوریتمهای FF و NN است. هدف ما در این مقاله، با کاهش حجم ارتباطی روی لینکهای میان مسیریابها در شبکه روی تراشه، ازدحام شبکه تحت تأثير قرار میگیرد. هرچه حجم ارتباطی میان هستهها کمتر باشد، احتمال ازدحام در شبکه کمتر خواهد شد. به همین دلیل ما از الگوریتم VEBAP ⁷ که از روش بستهبندی⁸ استفاده میکنیم و در مرجع [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|1) then Exploration phase

Update the location vector using Eq.1

If (|E|1) then Exploration phase

If (r 0.5 and |E|0.5) then Soft besiege

Update the location vector

else If (r 0.5 and |E|0.5) then Hard besiege

Update the location vector

else If (r 0.5 and |E|0.5) then Soft besiege

with progressive rapid dives

Update the location vector

else If (r 0.5 and |E| 0.5) then Hard

besiege with progressive rapid dives

Update the location vector

Return Xrabbit

شکل 1. شبه کد الگویتم شاهین هریس[10]

3. مدل سیستم ارائه شده

1.3 مدل NoC

یک گرافی است که با NG=(P,L) نشان داده میشود. P شامل مجموعهای از کاشی ⁹ها که هر کاشی دارای یک شناسه است و هر کدام شامل یک عنصر پردازشی¹⁰ (PE) که از طریق یک رابط شبکه¹¹ (NI) به یک مسیریاب (R) متصل است. L شامل مجموعهای از لینکهای که دارای یک پهنایباند ارتباطی برای عبور دادهها میان کاشیهای و است.

2.3 گراف هسته

گراف هسته، یک گراف جهت‌دار است و با CG=(C,E) نشان داده میشود، Cشامل مجموعهای از هستههای پردازشی که با Ci در شکل 3 قسمت ب نشان دادهایم هر هستههای پردازشی شامل (id, capid, positionid) است که id شناسه، capid ظرفیت محاسباتی و positionid موقعیت هسته پردازشی (در کدام کاشی قرار دارد)، نشان میدهد. E شامل مجموعهای از یالها است و نشان‌دهنده مقدار داده ارتباطی میان دو هسته پردازشی Ci و Cj است. در این مدل هر هسته پردازشی شامل یک یا چند وظیفه است.

شکل 2.(آ) مدل NoC (ب) گراف هسته - نگاشت هستههای پردازشی به کاشیهای NoC

3.3 گراف برنامه کاربردی

از مدل برنامه کاربردی در مرجع [9] که گراف جهت‌دار بدون سیکل است و با AG=(T,R) نشان داده میشود، استفاده کردیم. T شامل مجموعهای از وظایف که هر شامل (id,) است. نیاز محاسباتی برای هر وظیفه نشان میدهد که باید برای اجرا روی هسته پردازشی، ظرفیت باقیمانده آن به اندازه نیاز محاسباتی وظیفه مورد نظر است، قرار بگیرد. R شامل مجموعهای از یالها است نشان‌دهنده حجم ارتباطی میان و است. در شکل 4، یک گراف وظایف یا جریان کاری (workflow)- ترتیب منطقی زیر وظایف (یا وظایف ساده) از یک وظیفه بزرگ را جریان کار مینامند [23]- نشان میدهد. هر کدام از گرههای این گراف یک وظیفه را نشان میدهد و عدد داخل هر گره برابر با نیاز محاسباتی وظیفه مربوطه است و مقدار روی یالهای بین دو وظیفه برابر با حجم ارتباطی میان دو وظیفه است.

شکل 3. گراف وظایف (جریان کاری)

4.3 مدل انرژی

انرژی مصرفی شامل انرژی ارتباطی و انرژی محاسباتی است. انرژی ارتباطی () مقدار انرژی مصرف شده توسط مولفههای شبکه برای انتقال مقدار داده مورد نیاز میان دو هسته پردازشی است[24]. معادله 1 مقدار انرژی ارتباطی به صورت زیر تعریف میکند:

انرژی مصرف شده توسط مسیریاب برای انتقال یک بیت است. و به ترتیب انرژی مصرف شده برای انتقال یک بیت توسط لینک میان دو مسیریاب و لینک میان مسیریاب و هسته پردازشی است. مقدار دادهای که میان دو هسته پردازشی Ci و Cj که در دو کاشی نگاشته شدهاند.، فاصله منهتن، نشان‌دهنده تعداد گامها یا لینکها برای عبور یک بیت میان دو کاشی و است که به صورت زیر محاسبه میشود.

(x, y) موقعیت کاشی در مدل NoC نشان میدهد.

انرژی محاسباتی () از انرژی مصرف شده در هستهها بدست میآید[9]. انرژی مصرفی هر هسته به صورت زیر بدست میآید:

انرژی مصرفی توسط هسته پردازشی j را نشان میدهد. هسته پردازشی در دو حالت در حال پردازش یا بیکار قرار میگیرد. تعداد سیکلهایی که هسته پردازشی j بیکار است و تعداد سیکلهایی که هسته پردازشی j در حال پردازش داده میباشد. و به ترتیب مقدار مصرف انرژی یک هسته پردازشی در حالتهای بیکار و پردازش داده را نشان میدهد[9].

انرژی مصرفی کل با استفاده از معادله 5 بدست میآید:

مقدار کل دادهای است که میان دو کاشی که با فاصله منهتن 1 مبادله میشود با نشان میدهیم و مقدار آن طبق معادله زیر بدست میآید:

مسیر بین دو هسته پردازشی Ci و Cj که در نگاشته شدهاند، شامل مجموعهای از لینکها است که بین این دو کاشی در مسیریابی X-Y قرار گرفتهاند. به عبارتی دیگر هر لینک ممکن است بین چند جفت هسته پردازشی مشترک باشد. برابر است با جمع مقدار دادههایی که از لینک میان ()میگذرد. مقدار برابر با 1 است اگر از لینک میان بگذرد ( اگر عضو مسیر دو هسته پردازشی m و k باشد.)، در غیر این صورت مقدار آن برابر با 0 میباشد.

4. روش پیشنهادی

4_1 الگوریتم شاهین هریس گسسته

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

Algorithm: Proposed Discrete HHO Algorithm Pseudo-Code

Inputs: number of bins(dim), population size N (# haris), #iteration=T

Output: core mapping in NoC

Initialize:

Foreach haris random pos (0, dim)

Rabbit.pos= random pos (0, dim)

While(T) {

Rabbit.pos = pos of minimum fitness of haris

r= random (0, 1)

E=2E0 (1- t/T), -1<E0<1

If(|E|>=1)

Update location of haris using Eq. (7)

else

If(r>= 0.5 && |E|>= 0.5)

Soft besiege

else if (r>= 0.5 && |E|>= 0.5)

Hard besiege

else if (r>= 0.5 && |E|>= 0.5)

Soft besiege with progressive rapid dives

else if (r>= 0.5 && |E|>= 0.5)

Hard besiege with progressive rapid dives

Return Rabbit.pos

شکل 4. شبه کد الگوریتم شاهین هریس گسسته

در ادامه هر یک از مراحل را توضیح میدهیم.

4_1_1 مرحله اکتشاف

در این گام الگوریتم به دنبال کشف فضای جستجو میباشد و بهروزرسانی موقعیت شاهینها براساس عملگر تصادفی و یا براساس موقعیت سایر شاهینها صورت میگیرد.

، یک شاهین که به صورت تصادفی انتخاب شده و موقعیت آن به صورت شیفت چرخشی به چپ تغییر داده و موقعیت جدید شاهین فعلی میشود. ، ابتدا میانگین برآورد موقعیت شاهینها بدست آورده سپس اولین شاهینی که برآورد موقعیت آن کمتر از میانگین است، انتخاب میشود. ، موقعیت طعمه میباشد. با استفاده از تابع اعداد مشابه در درایههای با اندیس یکسان از و مشخص و به صورت تصادفی شیفت چرخشی میدهیم. موقعیت جدید شاهین فعلی بدست میآید. شکل 5 نمونه مثالی از بدست آوردن موقعیت جدید شاهین با استفاده از معادله 7 نشان میدهد.

شکل 5. مثالی از بدست آوردن موقعیت جدید شاهین با انجام عملیات (آ) و (ب)

4_1_2 مرحله بهرهبرداری

در این گام، الگوریتم به دنبال بهبود جوابهای پیدا شده میباشد و از عملگرهای محاصره سخت ¹² و محاصره نرم¹³ استفاده میکند.

فرض کنید که r شانس طعمه در فرار موفقیتآمیز یا فرار ناموفق قبل از حمله غافلگیرانه باشد. در حالی که طعمه فرار میکند، شاهینها ، محاصره سخت یا نرم را برای گرفتن طعمه شکل میدهند.

به این معنی که آنها بر اساس انرژی باقیمانده طعمه، حلقه محاصره را به صورت سخت یا نرم تنگتر میکنند.

4_1_2_1 محاصره نرم:

jump_strength، یک عدد تصادفی بین 0 تا اندازه جمعیت شاهینها است. در این گام، اگر باشد، موقعیت جدید شاهین طبق موقعیت طعمه بدست میآید. به این صورت عدد موجود در درایه با اندیس jump_strength از موقعیت طعمه، در اندیس 0 از موقعیت جدید شاهین قرار بگیرد و باقی درایهها از موقعیت طعمه نیز به درایههای موقعیت جدید انتقال یابند. در غیر این صورت عدد موجود در درایه با اندیس jump_strength از موقعیت طعمه در اندیس آخر از موقعیت جدید شاهین قرار بگیرد.

4_1_2_2 محاصره سخت:

ابتدا مقدار محاسبه میکنیم سپس موقعیت جدید شاهین را طبق موقعیت طعمه و محاسبه میکنیم.

4_1_2_3 محاصره نرم با شیرجههای پیشرو¹⁴:

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

4_1_2_4 محاصره سخت با شیرجههای پیشرو¹⁵ :

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

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 آورده شده است.

Pseudo-code of fitness function

Fitness (haris, bins) {

Noc[i][j] = haris.pos[k] and Set position x=i, y=j of

bin [ haris.pos[k]]

Calculator weight of link of NoC //weight of li, j(Wi, j)

Calculator sqrt of variance

Calculator Middle quarter

load= ENoc

if ((variance > v&& Middle quarter>q) || load> l)

returen 0

else

returen load

}

شکل 6. شبه کد تابع هدف

4_3 محاسبه پیچیدگی الگوریتم

پیچیدگی الگوریتم برابر با O (T×N×) است. Tتعداد تکرار الگوریتم شاهین هریس و N تعداد جمعیت شاهینها و زمان اجرای محاسبه است که به تعداد هستههای پردازشی برای نگاشت بر روی NoC بستگی دارد.

نتایج هر چهار تابع هدف در بخش بعد برای مقدار انرژی مصرفی 50 گراف مختلف نشان داده شده است.

5. محیط شبیهسازی و ارزیابی آزمایشها

5-1 محیط شبیهسازی

محیط شبکه روی تراشه با مش دو بعدی در چارچوب جاوا و با استفاده از Eclipse IDE را شبیهسازی کردهایم. و برای ارزیابی عملکرد روش ارائه شده از آن استفاده میکنیم.

HNOCS یک شبیهساز NoC منبع باز و مبتنی بر OMNeT++ است. HNOCS مخفف Heterogeneous Network-on-Chip Simulator است. این شبیهساز یک چارچوب منبع باز، مقیاس پذیر، قابل توسعه و کاملا قابل پارامترسازی برای مدلسازی انواع NoC است [25]. شبیه‌ساز HNOCS از توپولوژی مش، سوئیچینگ خزشی¹⁶ با کانالهای مجازی، کنترل جریان مبتنی بر اعتبار و از الگوریتم مسیریابی XY برای مسیریابی بستهها استفاده میکند. HNOCS مجموعهای از اندازهگیریهای آماری، مانند توان عملیاتی و تأخيرهای مختلف را در سطح فلیت و بسته ارائه میدهد و ما از این شبیهساز استفاده کردیم، زیرا دارای ساختاری مدولار است که اصلاح و افزودن به آن در مقایسه با سایر شبیهسازها آسان‌تر میکند.

جدول 1. تنظیم پارامترهای HNOCS

پارامترها	مقدار
پهنای باند لینک	16 Gbps
تأخير لینک	0.01 ns
تأخير مسیریاب	2 ns

در حالت ساده این شبیهساز برای هستههای همگن طراحی شده و میتوان هستههای ناهمگن نیز به آن اضافه کرد اما در این کار همان حالت اولیه را در نظر گرفتیم و فایل خروجی بدست آمده از 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- اطلاعات مورد نیاز برای اجرای جریانهای کار

جریان کاری	تعداد وظایف	تعداد bin مورد نیاز برای اجرا	ظرفیت bin
Cybershake	100	16	200
Genome	100	16	10000
Montage	100	25	60
Ligo	100	36	1000

ما برای یک نمونه از اجرای جریانهای کاری در روشهای SA و &OR مقدار بهرهوری از لینک، تأخير انتها به انتها و تأخير شبکه را با اجرا در HNOCS محاسبه کردیم. در جداول زیر مقدار مصرف انرژی و انحراف معیار بار نیز آورده شده است.

جدول 3. مقدار انرژی مصرفی برای هریک از جریانهای کاری در الگوریتمهای مختلف

	Cybershake	Genome	Montage	Ligo
FF	7156.89	149213.34	4365.36	32398.38
NN	9182.7	143102.97	3971.7	31697.73
SA	7959.33	125678.79	4186.62	31342.95
&OR	5310.09	93714.03	2539.08	16445.7

در جدول 3، مقدار انرژی مصرفی برای هر یک از جریانهای کار محاسبه شده است. روش &OR مقدار انرژی مصرفی کمتری نسبت به روشهای FF، NN و SA داشته است.

جدول 4. مقدار انحراف معیار بار لینک برای هریک از جریانهای کاری در الگوریتمهای مختلف

	Cybershake	Genome	Montage	Ligo
FF	963.68	26390.7	292.1	3236.35
NN	1333.93	26489.87	278.54	2283.95
SA	1202.43	23030.31	308.69	2818.83
&OR	656.85	16847.11	162.66	1384.52

در جدول 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:

Keyword: Network-on-chip, Core-mapping, Latency, Utilization of link, HHO

Share To

Article Url

Reduction of network load by mapping the application in the network on a chip using the discrete Harris hawk algorithm