الگوریتم کاهش انرژی مصرفی پویا برای سیستم‌های بی‌درنگ بحرانی-مختلط با پردازنده‌های چندهستهای
محورهای موضوعی : مهندسی برق و کامپیوتر
1 - گروه کامپیوتر و فناوری اطلاعات، دانشگاه پیام نور، ایران
کلید واژه: سیستم‌های تعبیه‌شده بحرانی- مختلط, پردازنده‌های چندهستهای, انرژی مصرفی, تغییر پویای ولتاژ و فرکانس,
چکیده مقاله :
امروزه برخلاف سیستم‌های تعبیه‌شده سنتی که دارای وظایف با درجه اهمیت یکسان هستند، بسیاری از سیستم‌های تعبیه‌شده، بحرانی- مختلط می‌باشند و بیشتر مورد استفاده قرار می‌گیرند. سیستم‌های بحرانی- مختلط، سیستم‌های تعبیه‌شده بی‌درنگی هستند که برای تجمیع برنامه‌های ایمنی- بحرانی و ایمنی- غیربحرانی بر روی یک بستر مشترک سخت‌افزاری معرفی شده‌اند. پردازنده‌های چندهستهای، قابلیت تجمیع کاربردهای متفاوت بر روی یک سخت‌افزار را فراهم کرده و می‌توانند انتخاب مناسبی برای سیستم‌های تعبیه‌شده بحرانی- مختلط باشند. با این حال، کاهش انرژی مصرفی در این سیستم‌ها به‌دلیل حجم بالای پردازش و طراحی عموماً مبتنی بر باتری آنها یک نیاز ضروری است؛ بنابراین در این مقاله، یک روش زمان‌بندی ابتکاری به‌منظور کاهش انرژی مصرفی در سیستم‌های بحرانی- مختلط متشکل از پردازنده چندهستهای معرفی می‌شود. این الگوریتم ضمن تضمین اجرای به‌موقع وظایف بحرانی، انرژی مصرفی سیستم را با تغییر پویای ولتاژ و فرکانس (DVFS) کاهش خواهد داد. نتایج به‌دست‌آمده از شبیه‌سازی‌ها نشان مي‌دهند که انرژي مصرفي الگوریتم پیشنهادی در مقايسه با روش‌هاي مشابه تا 30% بهبود مي‌يابد.
Today, unlike traditional embedded systems that have tasks with the same degree of importance, many critical embedded systems are mixed and are used more often. Mixed critical systems are real-time embedded systems introduced to consolidate critical safety and non-critical safety programs on a common hardware platform. Multi-core processors provide the ability to integrate different applications on one hardware and can be a suitable choice for mixed critical embedded systems. However, reducing the energy consumption in these systems is a necessary requirement due to the high volume of processing and their generally battery-based design. Therefore, in this paper, an innovative scheduling method is introduced to reduce energy consumption in mixed critical systems consisting of multi-core processors. This algorithm will reduce the energy consumption of the system by DVFS, while ensuring the timely execution of critical tasks. The results obtained from the simulations show that the energy consumption of the proposed algorithm is improved by 30% compared to similar methods.
[1] س. ح. صادق‌زاده و ی. صداقت، "زمان‌بندی آگاه از انرژی مصرفی برای سیستم‌های بی‌درنگ تک‌پردازنده‌ای بحرانی- مختلط،" نشریه علمی- پژوهشی نشريه مهندسي برق و مهندسي كامپيوتر ايران، سال 16، شماره 4، صص. 334-327، زمستان 1397.
[2] D. Zhu, "Reliability-aware dynamic energy management in dependable embedded real-time systems," ACM TECS, vol. 10, no. 2, Article ID: 26, 27 pp., Dec. 2011.
[3] P. Marwedel, Embedded System Design: Embedded Systems Foundations of Cyber-Physical Systems, Berlin, Germany: Springer, 2010.
[4] H. Kopetz, Real-Time Systems: Design Principles for Distributed Embedded Applications, Springer Science & Business Media, 2011.
[5] S. Baruah, et al., "Scheduling real-time mixed-criticality jobs," IEEE Trans. on Computers, vol. 61, no. 8, pp. 1140-1152, Aug. 2012.
[6] F. Santy, L. George, P. Thierry, and J. Goossens, "Relaxing mixedcriticality scheduling strictness for task sets scheduled with FP," in Proc. Euromicro Conf. on Real-Time Systems, ECRTS’12, pp. 155-165, Pisa, Italy, 11-13 Jul. 2012.
[7] S. Baruah, et al., "The preemptive uniprocessor scheduling of mixed-criticality implicit-deadline sporadic task systems," in Proc. Euromicro Conf. on Real-Time Systems, ECRTS'12, pp. 145-154, Pisa, Italy, 11-13 Jul. 2012.
[8] P. Taeju and K. Soontae, "Dynamic scheduling algorithm and its schedulability analysis for certifiable dual-criticality systems," in Proc. Int. Conf. Embedded Software, EMSOFT'11, pp. 253-262, Taipei Taiwan, 9-14 Oct. 2011.
[9] S. Baruah, H. Li, and L. Stougie, "Towards the design of certifiable mixed-criticality systems," in Proc. 16th IEEE Real-Time and Embedded Technology and Applications Symp., pp. 13-22, Stockholm, Sweden, 12-15 Apr. 2010.
[10] P. Huang, H. Yang, and L. Thiele, "On the scheduling of fault-tolerant mixed-criticality systems," in Proc. Design Automation Conf. (DAC), ACM/EDAC/IEEE, DAC'14, 6 pp., 1-5 Jun. 2014.
[11] S. Baruah and S. Vestal, "Schedulability analysis of sporadic tasks with multiple criticality specifications," in Proc. Euromicro Conf. on Real-Time Systems, ECRTS'08, pp. 147-155, Prague, Czech Republic, 2-4 Jul. 2008.
[12] Z. Lia, C. Guo, X. Hua, and S. Ren, "Reliability guaranteed energy minimization on mixed-criticality systems," J. of Syst. and Software, vol. 112, pp. 1-10, Feb. 2016.
[13] H. Su, D. Zhu, and S. Brandt, "An elastic mixed-criticality task model and early-release EDF scheduling algorithms," ACM TODAES, vol. 22, no. 2, Article ID: 28, 28 pp., Apr. 2017.
[14] A. Thekkilakattil, R. Dobrin, and S. Punnekkat, "Fault-tolerant scheduling of mixed-criticality real-time tasks under error bursts," Procedia Computer Science, vol. 46, pp. 1148-1155, 2015.
[15] P. Ekberg and W. Yi, "Bounding and shaping the demand of mixed-criticality sporadic tasks," in Proc. 24th Euromicro Conference on Real-Time Systems, ECRTS, pp. 135-144, Pisa, Italy, 11-13 Jul. 2012.
[16] S. Vestal, "Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance," in Proc. 28th IEEE Int. Real-Time Systems Symp., pp. 239-243, Tucson, AZ, USA, 3-6 Dec. 2007.
[17] J. Lin, A. M. K. Cheng, D. Steel, and M. Yu-Chi Wu, "Scheduling mixed-criticality real-time tasks in a fault-tolerant system," International Journal of Embedded and Real-Time Communication Systems, vol. 6, no. 2, 22 pp., 2015.
[18] C. Kamienski, et al., "Application development for the Internet of Things: a context-aware mixed criticality systems development platform," Computer Communications, vol. 104, pp. 1-16, 15 May 2017.
[19] A. Taherin, M. Salehi, and A. Ejlali, "Reliability-aware energy management in mixed-criticality systems," IEEE Trans. on Sustainable Computing, vol. 3, no. 3, pp. 195-208, Jul.-Sept. 2018.
[20] M. Salehi, A. Ejlali, and B. M. Al-Hashimi, "Two-phase low-energy N-modular redundancy for hard real-time multi-core systems," IEEE TPDS, vol. 27, no. 5, pp. 1497-1510, May 2015.
[21] S. Baruah, C. Bipasa, L. Haohan, and S. Insik, "Mixed-criticality scheduling on multiprocessors," Real-Time Systems, vol. 50, no. 1, pp. 142-177, Jan. 2014.
[22] C. Gu, G. Nan, D. Qingxu, and Y. Wang, "Partitioned mixed-criticality scheduling on multiprocessor platforms," in Proc. Design, Automation & Test in Europe Conf. & Exhibition, DATE'14, 6 pp., Dresden, Germany, 24-28 Mar. 2014.
[23] Y. Zhang and K. Chakrabarty, "Dynamic adaptation for fault tolerance and power management in embedded real-time systems," ACM Trans. on Embedded Computing Systems, vol. 3, no. 2, pp. 336-360, May 2004.
[24] L. Benini, A. Bogliolo, and G. De Micheli, "A survey of design techniques for system-level dynamic power management," IEEE Trans. VLSI Sys., vol. 8, no. 3, pp. 299-316, Jun. 2000.
[25] T. D. Burd, T. A. Pering, A. J. Stratakos, and R. W. Brodersen, "A dynamic voltage scaled microprocessor system," IEEE J. Solid-State Circuits, vol. 35, no. 11, pp. 1571-1580, Nov. 2000.
[26] M. A. Haque, H. Aydin, and D. Zhu, "On reliability management of energy-aware real-time systems through task replication," IEEE Trans. Parallel Distrib. Syst., vol. 28, no. 3, pp. 813-825, Mar. 2017.
[27] Y. Zhang and R.Chen, "A survey of energy-aware scheduling in mixed-criticality systems," Journal of Systems Architecture, vol.1, no.17, Article ID: 102524, Jun. 2022.
[28] J. Chen and C. Kuo, "Energy-efficient scheduling for realtime systems on dynamic voltage scaling (dvs) platforms," in Proc. Embedded and Real-Time Computing Systems and Applications, RTCSA'07, pp. 28-38, Daegu, South Korea, 21-24 Aug. 2007.
[29] A. Burns and R. I. Davis, Mixed-Criticality Systems: A Review, Tech. Rep., Dept. Comput. Sci. Univ. York, 61 pp. 1-61, 2016.
[30] S. Narayana, P. Huang, G. Giannopoulou, L. Thiele, and R. V. Prasad, "Exploring energy saving for mixed-criticality systems on multi-cores," in Proc. IEEE Real-Time and Embedded Technology and Applications Symp., RTAS'16, 12 pp., Vienna, Austria, 11-14 Apr. 2016.
[31] P. Huang, P. Kumar, G. Giannopoulou, and L. Thiele, "Energy efficient DVFS scheduling for mixed-criticality systems," in Proc. Int. Conf. Embedded Software, EMSOFT'14, 10 pp., Uttar Pradesh, India, 12-17 Oct. 2014.
[32] V. Moghaddas, M. Fazeli, and A. Patooghy, "Reliability-oriented scheduling for static-priority real-time tasks in standby-sparing systems," Microprocessors and Microsystems, Pt A, vol. 45, pp. 208-215, Aug. 2016.
[33] V. Legout, M. Jan, and L. Pautet, "Mixed-criticality multiprocessor real-time systems: energy consumption vs deadline misses," in Proc. 1st. Workshop on Real-Time Mixed Criticality Syst., ReTiMiCS'13', 6 pp., Taipei, Taiwan. Aug. 2013.
[34] M. Völp, M. Hähnel, and A. Lackorzynski, "Has energy surpassed timeliness? scheduling energy-constrained mixed-criticality systems," in Proc. IEEE Real-Time and Embedded Technology and Applications Symp., RTAS'14, pp. 275-284, Berlin, Germany, 15-17 Apr. 2014.
[35] F. Zhang and A. Burns, "Schedulability analysis for real-time systems with EDF scheduling," IEEE Trans. on Computers, vol. 589, no. 9, pp. 1250-1258, Sept. 2009.
[36] N. Audsley, Optimal Priority Assignment and Feasibility of Static Priority Tasks with Arbitrary Start Times, Dept. of Comp. Sci., University of York, UK, 1991.
[37] A. K. Singh, M. Shafique, A. Kumar, and J. Henkel, "Mapping on multi/many-core systems: Survey of current and emerging trends," in Proc. of 50th ACM/EDAC/IEEE Design Automation Conf., DAC'13, pp. 275-284, Austin, TX, USA, 29 May-7 Jun. 2013.
[38] A. Bastoni, B. B. Brandenburg, and J. H. Anderson, "An emperical comparison of global, partitioned and clustered multiprocessor EDF mchedulers," in Proc. 31st IEEE Real-Time Systems Symp., RTSS'10, San Diego, CA, USA, 30 Nov.-3 Dec. 2010.
نشریه مهندسی برق و مهندسی کامپیوتر ایران، ب- مهندسی کامپیوتر، سال 22، شماره 2، تابستان 1403 129
مقاله پژوهشی
الگوریتم کاهش انرژی مصرفی پویا برای سیستم‌های بی‌درنگ بحرانی- مختلط با پردازنده‌های چندهستهای
سید حسن صادق‌زاده
چکیده: امروزه برخلاف سیستم‌های تعبیه‌شده سنتی که دارای وظایف با درجه اهمیت یکسان هستند، بسیاری از سیستم‌های تعبیه‌شده، بحرانی- مختلط می‌باشند و بیشتر مورد استفاده قرار می‌گیرند. سیستم‌های بحرانی- مختلط، سیستم‌های تعبیه‌شده بی‌درنگی هستند که برای تجمیع برنامه‌های ایمنی- بحرانی و ایمنی- غیربحرانی بر روی یک بستر مشترک سخت‌افزاری معرفی شده‌اند. پردازنده‌های چندهستهای، قابلیت تجمیع کاربردهای متفاوت بر روی یک سخت‌افزار را فراهم کرده و می‌توانند انتخاب مناسبی برای سیستم‌های تعبیه‌شده بحرانی- مختلط باشند. با این حال، کاهش انرژی مصرفی در این سیستم‌ها به‌دلیل حجم بالای پردازش و طراحی عموماً مبتنی بر باتری آنها یک نیاز ضروری است؛ بنابراین در این مقاله، یک روش زمان‌بندی ابتکاری به‌منظور کاهش انرژی مصرفی در سیستم‌های بحرانی- مختلط متشکل از پردازنده چندهستهای معرفی می‌شود. این الگوریتم ضمن تضمین اجرای به‌موقع وظایف بحرانی، انرژی مصرفی سیستم را با تغییر پویای ولتاژ و فرکانس (DVFS) کاهش خواهد داد. نتایج به‌دست‌آمده از شبیه‌سازی‌ها نشان مي‌دهند که انرژي مصرفي الگوریتم پیشنهادی در مقايسه با روش‌هاي مشابه تا 30% بهبود مي‌يابد.
کلیدواژه: سیستم‌های تعبیه‌شده بحرانی- مختلط، پردازنده‌های چندهستهای، انرژی مصرفی، تغییر پویای ولتاژ و فرکانس.
1- مقدمه
بسیاری از سیستم‌های نهفته2 در کاربردهای ایمنی- بحرانی3 به‌کار گرفته می‌شوند که در ارتباط مستقیم با حیات انسان‌ها، محیط‌زیست و یا اقتصاد و امنیت کشورها هستند. از جمله این کاربردها می‌توان به صنایع پزشکی، هوایی و فضایی، ارتباطی و نظامی اشاره کرد [1] تا [4]. نیازهایی همچون کاهش هزینه تولید، وزن و اندازه، منجر به طراحی سیستم‌هایی با قابلیت‌های4 متفاوت بر روی یک بستر مشترک سخت‌افزاری شده
است. این سیستم‌ها به‌دلیل یکپارچه‌سازی قابلیت‌های ایمنی- بحرانی
با قابلیت‌های ایمنی- غیربحرانی، سیستم‌های بحرانی- مختلط5 نامیده می‌شوند [5] تا [11]. بنابراین سیستم‌های بحرانی- مختلط، گسترش‌یافته سیستم‌های ایمنی- بحرانی بوده و نسل بعدی سیستم‌های نهفته در نظر گرفته می‌شوند [12] تا [15]. نیاز و تمایل صنعت به سیستم‌های نهفته بحرانی- مختلط (به‌ویژه صنعت خودروسازی [1] و [2] و هوافضا [16] و [17])، طراحی و پیاده‌سازی این سیستم‌ها را گسترش داده و استفاده از آنها در سال‌های اخیر به‌صورت گسترده مورد توجه قرار گرفته است. سیستم‌های سایبر- فیزیکی 6(CPS) و اینترنت اشیا 7(IoT) مفاهیمی هستند که مبتنی بر سیستم‌های بحرانی- مختلط معرفی گردیده‌اند [18]. این سیستم‌ها دارای وظایفی با درجه اهمیت متفاوت هستند و از این رو وظایف با توجه به درجه اهمیت تقسیم می‌شوند. اگر وظایف مهم‌تر باشند، آنها به‌عنوان وظایف با اهمیت بالا (وظایف ايمني- بحراني) و اگر وظایف کم‌اهمیت‌تر باشند، به‌عنوان وظایف با اهمیت پایین (وظایف ايمني- غیربحراني) طبقه‌بندی می‌شوند [5] و [19]. در سیستم‌های بحرانی- مختلط، وظایف ايمني- بحراني علاوه بر طراح سیستم8، توسط صادرکننده گواهی9 ارزیابی و اعتبارسنجی10 می‌شوند. این در حالی است که وظایف ايمني- غیربحراني تنها توسط طراح سیستم مورد ارزیابی و اعتبارسنجی قرار می‌گیرند. صادرکننده گواهی، شرایط محافظه‌کارانه‌تری11 را برای ارزیابی بدترین زمان اجرای وظایف 12(WCET) مد نظر قرار می‌دهد (ازجمله درنظرگرفتن زمان اجرای فرایند بازیابی از خطا) و از روش‌های متفاوتی نسبت به طراح استفاده می‌کند [10]. بنابراین در اغلب موارد بدترین زمان اجرای وظایف ايمني- بحراني توسط صادرکننده گواهی از زمان اجرای محاسبه‌شده توسط طراح بیشتر می‌باشد.
به‌عنوان نمونه‌ای بارز از سیستم‌های بحرانی- مختلط می‌توان به وسایل نقلیه هوایی بدون سرنشین 13(UAV) اشاره کرد که در این وسایل، وظایف به دو گروه ايمني- بحراني (شامل کنترل پرواز و مسیریابی) و ایمنی- غیربحرانی (شامل ردیابی شیء برای نظارت و گرفتن عکس) تقسیم می‌شوند [11]. این سیستم‌ها بی‌درنگ14 هستند و باید مهلت زمانی15 خود را در هر شرایط محیطی رعایت کنند. بنابراین عدم انجام وظایف ایمنی- بحرانی می‌تواند عواقب فاجعه‌باری داشته باشد؛ در حالی که عدم انجام وظایف ایمنی- غیربحرانی فقط می‌تواند منجر به کاهش خدمات به کاربر شوند و قابل تحمل هستند [10]. بنابراین هدف اصلی این سیستم‌ها، اجرای به‌موقع وظایف ایمنی- بحرانی است که در بعضی از مواقع (در بخش 3 به‌طور کامل به این موضوع خواهیم پرداخت) وظایف ایمنی- غیربحرانی برای تضمین رفتار به‌موقع وظایف ایمنی- بحرانی، قربانی می‌شوند.
پردازنده‌های چندهستهای به‌دلیل افزایش کارایی و قدرت محاسباتی بالا به‌طور گسترده در سیستم‌های نهفته مورد استفاده قرار گرفته‌اند [20] و [21]. همچنین این پردازنده‌ها قابلیت تجمیع کاربردهای متفاوت بر روی یک سخت‌افزار را فراهم کرده و می‌توانند انتخاب مناسبی برای سیستم‌های نهفته با بحرانیت مختلط باشند [22]. با این حال، میزان انرژی مصرفی16 به‌دلیل سیار و قابل حمل‌بودن17 این سیستم‌ها بسيار حائز اهميت بوده و وابسته به طول عمر باتری آنهاست [12]. علاوه بر آن در بسیاری از کاربردها تعویض یا شارژ باتری در محیط عملیاتی سیستم‌های نهفته بسیار دشوار است [23]. از این گذشته برای سیستم‌هایی که مشکل تأمین انرژی ندارند، افزایش توان و انرژی مصرفی باعث توليد گرما شده و گرماي توليدشده مخصوصاً در واحدهای پردازشی موجب تأخیر در مدارها و خرابی و کاهش قابلیت اطمینان18 قطعات سیستم می‌شود [1]، [2] و [14]. این امر باعث شده که در کنار انجام به‌موقع وظایف، مصرف انرژی به‌عنوان یکی از مهم‌ترین ملاحظات در طراحی سیستم‌های نهفته‌ای مطرح شود که از منابع محدود انرژی استفاده می‌کنند [12] و [19].
از مهم‌ترین روش‌های سطح سیستم برای مدیریت انرژی، مدیریت پویای توان 19(DPM) [24] و تغییر پویای ولتاژ تغذیه و فرکانس 20(DVFS) [25] است. این روش‌ها از زمان بیکاری موجود در سیستم برای کاهش مصرف انرژی استفاده می‌کنند. روش DPM در مواقعی که بخشی از سیستم به‌صورت موقت مورد نیاز نباشد، آن بخش را به حالت غیر فعال برده و یا خاموش می‌کند. روش DVFS، هنگامی که زمان بیشتری نسبت به زمان مورد نیاز برای انجام کار فعلی در اختیار باشد، ولتاژ تغذیه (و فرکانس کاری) واحد مورد نظر را کاهش می‌دهد تا مصرف انرژی و توان پویای21 سیستم را کاهش دهد؛ اما ثابت می‌شود این روش‌ها به‌دلیل افزایش زمان اجرای وظیفه مي‌توانند در سيستمهاي بي‌درنگ منجر به نقض مهلت‌هاي زماني و سبب بروز فاجعه شوند [26]. بنابراین بین روش‌هایی که برای کاهش مصرف انرژی و فراهم‌کردن بی‌درنگی مورد استفاده قرار می‌گیرند، تضاد قابل توجهی وجود دارد [15]. از این رو، یکی از الزامات اساسی این سیستم‌ها دستیابی به زمان‌بندی مناسب همراه با انرژی مصرفی کم می‌باشد.
در این مقاله سعي گردیده تا با کمک پردازنده‌های چندهستهای، الگوریتمی برای بهبود انرژی مصرفی با استفاده از زمان‌های بیکاری ایجادشده در حین اجرای وظایف ارائه گردد. هدف، کاهش مصرف انرژی و تضمین اجرای به‌موقع وظایف بحرانی در یک سیستم چندهستهای است. این الگوریتم از روش زمان‌بندی برخط22 معرفی‌شده در آخرین پژوهش ما (ارائه‌شده در یک سیستم تک‌پردازنده‌ای [1])، الهام گرفته و
از این رو نتایج با نگاشت مناسب وظایف در سیستم‌های چندهستهای گسترش می‌یابد. بنابراین این الگوریتم، ضمن تضمین اجرای به‌موقع وظایف بحرانی، انرژی مصرفی یک سیستم چندهستهای را در مقايسه با روش‌هاي مشابه به‌طور چشم‌گیری کاهش می‌دهد. در این مقاله، منظور از وظایف بحرانی، وظایف ایمنی- بحرانی و منظور از وظایف غیربحرانی، وظایف ایمنی- غیربحرانی می‌باشد.
بخش‌بندی مقاله به این ترتیب است که بخش 2 مروری کلی از کارهای مرتبط را فراهم می‌کند و در بخش 3، مدل سیستم بیان می‌شود. بخش 4 ضمن بیان راهکار پیشنهادی، زیرمسائل لازم برای حل مسئله اصلی را معرفی می‌کند. نتایج به‌دست‌آمده از پیاده‌سازی در بخش 5 نشان داده شده و در بخش 6 نتیجه‌گیری نهایی تشریح خواهد شد.
2- مروری بر کارهای مرتبط
مطالعات زیادی در زمینه کاهش انرژی مصرفی در سیستم‌های بی‌درنگ انجام شده است (برای اطلاعات بیشتر به مقالات مروری [27]
و [28] مراجعه شود). در این مطالعات، درجه اهمیت وظایف یکسان در نظر گرفته شده‌اند؛ اما همان طور که قبلاً اشاره شد در سیستم‌های نهفته بی‌درنگ بحرانی- مختلط، برنامه‌های مختلف بر روی یک تراشه در کنار هم و با درجه بحرانی متفاوت قرار می‌گیرند. وجود وظایف با درجه بحرانیت متفاوت باعث می‌شود که مطالعات ذکرشده برای سیستم‌های بحرانی- مختلط کارا نبوده و مباحث مطرح، به‌ویژه بی‌درنگی و مدیریت انرژی مصرفی نیاز به دقت نظر بیشتری دارد. مفهوم بحرانیت مختلط اولین بار در سال 2007 توسط وستال23 معرفی گردید [16]. در این مقاله نشان داده شده که به‌دلیل وجود وظایف با بحرانیت‌های متفاوت، روش‌های رایج زمان‌بندی در سیستم‌های نهفته بی‌درنگ (مانند 24RM
و 25DM) بهینه نیست و به همین علت در [9] الگوریتم OCBP، در
[8] الگوریتم CBEDF و در [7] الگوریتم EDF-VD برای زمان‌بندی سیستم‌های بحرانی- مختلط معرفی گردیده‌اند.
بررسي‌هاي بيشتر نشان مي‌دهند كه اخیراً برای کاهش انرژی مصرفی در سیستم‌های نهفته بی‌درنگ بحرانی- مختلط نيز مطالعاتی انجام شده است (برای اطلاعات بیشتر به مقالات مروری [29] مراجعه شود). در اکثر این مطالعات، راه حلی برای کاهش‌دادن انرژی مصرفی در سیستم تک‌پردازنده‌ای ارائه گرديده است. در [30] نویسندگان در یک سیستم چندهستهای، راه حلی برای کاهش انرژی مصرفی معرفی کرده‌اند. در این مقاله بعد از نگاشت وظایف، طبق الگوریتم ارائه‌شده در [31] فرکانس کاری هر وظیفه به‌صورت ایستا مشخص شده و وظایف بر اساس این فرکانس اجرا می‌شوند؛ اما به‌دلیل ایستابودن این الگوریتم نمی‌توان از زمان‌های بیکاری ایجادشده در حین اجرای وظایف برای کاهش بیشتر فرکانس کاری وظایف استفاده نمود. در آخرین کار ما [1] از زمان‌های بیکاری ایجادشده به‌صورت پویا برای کاهش بیشتر فرکانس استفاده می‌شود؛ اما این راه حل در سیستم تک‌پردازنده‌ای ارائه شده است. همچنین در بیشتر این مطالعات فقط توان مصرفي دینامیک در نظر گرفته شده و از توان مصرفي ایستا که مربوط به جریان‌های نشتی می‌باشد [32] صرف نظر شده است. این در حالی است که در مدارات دیجیتال امروزی و با کاهش ابعاد، توان مصرفي ایستا و دینامیک از اهمیت یکسانی برخوردار هستند. بنابراین در این پژوهش هر دو توان مصرفي ایستا و دینامیک در نظر گرفته شده است. علاوه بر این، وضعیت سیستم و میزان انرژی
[1] این مقاله در تاریخ 4 تیر ماه 1401 دریافت و در تاریخ 30 آذر ماه 1402 بازنگری شد.
سید حسن صادق‌زاده (نویسنده مسئول)، گروه کامپیوتر و فناوری اطلاعات، دانشگاه پیام نور، تهران، ایران، (email: Sadeghzadeh@pnu.ac.ir) .
[2] . Embedded Systems
[3] . Safety-Critical
[4] . Functionalities
[5] . Mixed-Criticality Systems
[6] . Cyber-Physical Systems
[7] . Internet of Things
[8] . System Designer
[9] . Certificate Authority
[10] . Validate
[11] . Conservative
[12] . Worst Case Execution Time
[13] . Unmanned Aerial Vehicle
[14] . Real-Time
[15] . Deadline
[16] . Energy Consumption
[17] . Portable
[18] . Reliability
[19] . Dynamic Power Management
[20] . Dynamic Voltage and Frequency Scaling
[21] . Dynamic Power
[22] . Online
[23] . Vestal
[24] . Rate Monotonic
[25] . Deadline Monotonic
جدول 1: خلاصه‌ای از راهکارهای ارائه‌شده برای کاهش انرژی مصرفی در سیستم‌های بحرانی- مختلط.
منبع | درجه بحرانی وظايف | راهکار ارائه‌شده برای کاهش انرژی مصرفی | معايب |
[2]، [19]، [26] و [32] | یکسان | به‌دلیل وجود وظایف با درجه اهمیت یکسان، راهکار ارائه‌شده در این مطالعات برای سیستم‌های بحرانی- مختلط کارا نیست. | وجود وظایف با درجه اهمیت یکسان |
[1] | متفاوت | زمان‌بندی دینامیک و استفاده از DVFS | تک‌پردازنده‌ای |
[19] | متفاوت | زمان‌بندی ایستا و استفاده از DVFS | تک‌پردازنده‌ای |
[30] | متفاوت | زمان‌بندی ایستا و استفاده از DVFS (چندهستهای) | عدم استفاده از زمان‌های بیکاری ایجادشده در حین اجرای وظایف |
[31] | متفاوت | زمان‌بندی ایستا و استفاده از DVFS | تک‌پردازنده‌ای |
[33] | متفاوت | حذف وظایف غیربحرانی، (چندهستهای) | در این مقاله مشخص شده که مصالحه‌ای بین حذف وظایف غیربحرانی و کاهش مصرف انرژی وجود دارد (عدم استفاده از زمان‌های بیکاری). |
[34] | متفاوت | حذف وظایف غیربحرانی برای کاهش انرژی مصرفی و استفاده از DPM | تک‌پردازنده‌ای |
مصرفی در هر دو حالت بحرانی و غیربحرانی مورد بررسی و ارزیابی قرار می‌گیرد. خلاصه‌ای از مطالبی که در این بخش گفته شد و چند کار دیگر در جدول 1 آمده است.
3- مدل سیستم
3-1 مدل وظیفه و سیستم
وظایف در کاربردهای بی‌درنگ به‌طور ذاتی به‌صورت دوره‌ای هستند؛ از این رو مجموعه‌ای شامل وظیفه دوره‌ای بی‌درنگ 
در نظر گرفته می‌شود [4]. وظایف بر روی یک سیستم چندهستهای که قابلیت DVFS دارد، اجرا می‌شوند. سیستم باید دارای 
سطح فرکانس 
باشد. برای سادگی، سطوح فرکانس نسبت به حداکثر فرکانس 
نرمالیزه می‌شوند؛ یعنی 
. 
درجه بحرانی هر وظیفه را نمایش می‌دهد به‌طوری که وظایف بحرانی با 
و وظایف غیربحرانی با 
نشان داده می‌شوند. دو زمان اجرای 
و 
برای وظایف بحرانی در نظر گرفته شده است به‌طوری که 
و برای وظایف غیربحرانی یک زمان اجرای در نظر گرفته می‌شود. وظایف در این سیستم‌ها مانند سیستم‌های سنتی موعد مقرر ضمنی1 دارند که برای هر وظیفه با دوره زمانی2 آن
برابر می‌باشد 
؛ بنابراین هر وظیفه 
توسط پارامترهای 
توصیف می‌شود که 
زمان انتشار وظیفه، 
زمان اجرای وظیفه، 
دوره تناوب (که متناسب با موعد مقرر است) و درجه بحرانی هر وظیفه است. بهره‌وری وظیفه 
به‌صورت 
تعریف شده و برای وظایف بحرانی 
و 
و برای وظایف غیربحرانی که فقط یک زمان اجرا دارند می‌باشد. بهره‌وری یک مجموعه وظیفه مشخص از جمع بهره‌وری‌های آن مجموعه وظیفه به‌دست می‌آید [29].
سیستم دو وضعیت مختلف دارد که 
وضعیت سیستم در حالت غیربحرانی و 
وضعیت سیستم در حالت بحرانی را نشان می‌دهد. سیستم در حالت عادی و در وضعیت شروع به کار کرده و چنانچه یکی از وظایف بحرانی به زمانی بیشتر از نیاز داشته باشد، سیستم وضعیت عملیاتی خود را به تغییر می‌دهد. در این حالت برای تضمین اجرای وظایف بحرانی، وظایف غیربحرانی حذف خواهند شد [4] تا [6]؛ بنابراین در حالت عادی وظایف غیربحرانی به‌طور کامل اجرا شده و از زمان رزرو وظایف بحرانی برای کاهش انرژی مصرفی استفاده خواهد شد.
3-2 مدل انرژی مصرفی
انرژی مصرفی یک سیستم، توان مصرفی3 آن سیستم را در زمان سپری‌شده برای اجرای کار نشان می‌دهد. توان مصرفی در حالت فعال به دو بخش توان مصرفي ایستا4 
و توان مصرفي پویا5 
تقسیم می‌شود. توان ایستا مربوط به جریان نشتی در سیستم است و تنها با قطع ولتاژ تغذیه و خاموش‌کردن کل سیستم حذف می‌شود [1] و [32]. توان پویا شامل توان پویای وابسته به فرکانس6 
و توان پویای مستقل از فرکانس7 
می‌شود [32]؛ در نتیجه میزان توان مصرفی مشابه آنچه در [1] و [32] آمده است به‌صورت (1) خواهد بود
(1)
که در آن 
فرکانس عملیاتی (پردازشی)، 
ظرفیت متوسط خازن سوئیچ‌زنی و 
ولتاژ تغذیه است. از آنجا که برای کاهش انرژی مصرفی علاوه بر فرکانس، ولتاژ تغذیه نیز باید تنظیم شود، در ادامه و برای سادگی از کلمه «فرکانس» به‌عنوان نماینده «فرکانس و ولتاژ» استفاده می‌شود. از این رو رابطه بالا با پارامتر 
(که نشان‌دهنده رابطه خطی فرکانس و ولتاژ است [1] و [32]) به‌صورت (2) بازنویسی می‌شود
(2)
که ضریب 
از ضرایب ثابت وابسته به سیستم است؛ به عبارت دیگر رابطه تقریباً خطی ولتاژ و فرکانس را مدل می‌کند. با توجه به اینکه انرژی، انتگرال توان در زمان است، انرژی مصرفی یک وظیفه در فرکانس به‌صورت (3) می‌باشد
(3)
از این رو مصرف کل انرژی وظیفه هنگامی که در فرکانس اجرا می‌شود می‌تواند به‌صورت (4) درآید
(4)
3-3 زمان‌بندی در سیستم‌های بحرانی- مختلط
در سیستم‌های بحرانی- مختلط و بر طبق ادعاي مطرح‌شده در [16]، وجود وظایف با درجه بحرانی متفاوت باعث می‌شود که روش‌های رایج زمان‌بندی مثل 8EDF [35] کارا نباشند. بنابراین در سیستم‌های بحرانی- مختلط به الگوریتمی برای زمان‌بندی نیاز است که ضمن اجرای به‌موقع وظایف، شرایط لازم را برای اجرای وظایف بحرانی در صورت تغییر وضعیت سیستم فراهم نماید و به همین علت الگوریتم‌های مختلفی برای زمان‌بندی سیستم‌های بحرانی- مختلط معرفی شده‌اند. الگوریتم OCBP [9] یک الگوریتم اولویت ثابت بر اساس درجه بحرانیت وظایف است. این الگوریتم توسعه‌یافته الگوریتم اولویت ثابت Audsley9 [36] بوده که برای اولویت‌بندی وظایف، درجه بحرانی‌بودن آنها را هم در نظر می‌گیرد. الگوریتم CBEDF [8] با هدف استفاده از زمان بیکاری وظایف بحرانی، برای اجرای وظایف غیربحرانی معرفی شده است. این الگوریتم شامل دو زیرالگوریتم می‌باشد که یکی برای مشخص‌کردن زمان‌های بیکاری قبل از اجرا و دیگری زمان‌بندی وظایف در طول اجراست که خود، شامل
دو صف یکی برای وظایف بحرانی و دیگری برای وظایف غیربحرانی می‌باشد. در آخر نشان داده شده که این الگوریتم بهتر از OCBP عمل می‌کند. همچنین EDF-VD [7] با هدف ایجاد مهلت زمانی مجازی 10(VD) جهت تضمین اجرای به‌موقع وظایف بحرانی معرفی شده است. این الگوریتم پارامتر 
را به کمک بهره‌وری11 وظایف محاسبه می‌نماید و با ضرب این مقدار در مهلت زمانی وظایف بحرانی، یک مهلت زمانی مجازی برای این وظایف در نظر گرفته و سپس تمام وظایف طبق الگوریتم EDF زمان‌بندی می‌شوند. در این الگوریتم چنانچه وظایف بحرانی نیاز به زمانی بیشتر از آنچه طراح مشخص کرده، داشته باشند، وظایف غیربحرانی به جهت تضمین رفتار به‌موقع وظایف بحرانی، قربانی می‌شوند. برخلاف روش‌های زمان‌بندی ذکرشده که در صورت تغییر سیستم از حالت غیربحرانی به حالت بحرانی، وظایف غیربحرانی حذف می‌شوند، [19] با ارائه الگوریتم ER-EDF از زمان بیکاری وظایف بحرانی برای اجرای وظایف غیربحرانی استفاده کرده است. این الگوریتم با افزایش دوره تناوب وظایف غیربحرانی (که توسط حداقل نیاز سرویس12 وظیفه مشخص می‌شود) و بدون دخالت در اجرای وظایف بحرانی، آنها را زمان‌بندی می‌کند. نتایج این پژوهش در مقایسه با روش‌های زمان‌بندی ذکرشده، اجرای وظایف بیشتری را نشان داده است. در این پژوهش مشابه با [5]، [30] و [31] از الگوریتم EDF-VD برای زمان‌بندی وظایف استفاده گردیده است. این زمان‌بندی با ذکر مثالی در [1] بیشتر توضیح داده شده است.
4- راهکار پیشنهادی
طبق آنچه بیان شد، علاوه بر زمان‌بندی درست سیستم‌های بحرانی- مختلط، از آنجا که این سیستم‌ها عموماً مبتنی بر باتری هستند، کاهش مصرف انرژی یک نیاز ضروری است. در آخرین کار ما [1] با ارائه یک الگوریتم پویا، از زمان رزروشده برای وظایف بحرانی 
برای کاهش بیشتر فرکانس و بهبود انرژی مصرفی استفاده شده است.
در این الگوریتم در صورت اجرای موفق وظایف بحرانی (در زمان )، از زمان بیکاری به‌وجودآمده برای کاهش بیشتر فرکانس استفاده شده است. اما این راه‌حل در سیستم تک‌پردازنده‌ای معرفی گردیده است. از این رو، این پژوهش گسترش‌یافته آخرین مطالعه ما [1] با نگاشت مناسب وظایف در سیستم‌های چندهستهای می‌باشد. بنابراین مسئله اصلی به این صورت بیان می‌شود که در یک سیستم نهفته بی‌درنگ با بحرانیت مختلط در محیط متشکل از پردازنده چندهستهای، وظایف چگونه زمان‌بندی شوند تا ضمن استفاده از تکنیک تغییر پویای ولتاژ برای کاهش انرژی مصرفی، محدودیت زمانی وظایف نیز ارضا شود. برای رسیدن به این هدف مراحل زیر انجام خواهد شد:
1) نگاشت وظایف
2) محاسبه پارامترهای لازم (محاسبه فاکتور و فرکانس کاری وظایف) برای زمان‌بندی وظایف با بحرانیت مختلط
3) دخیل‌نمودن زمان‌بندي در کنار روش کاهش انرژی مصرفی
در اولین مرحله، روش‌های ارائه‌شده برای نگاشت وظایف در سیستم‌های بحرانی- مختلط چندهستهای معرفی شده و روش پیشنهادی با تمام این روش‌ها ارزیابی می‌گردد. در مرحله دوم که به‌صورت ایستا می‌باشد، پارامترهای لازم برای زمان‌بندی در سیستم‌های بحرانی- مختلط به‌دلیل وجود وظایف با درجه اهمیت متفاوت محاسبه می‌شود. در آخرین مرحله که قسمت دینامیک روش پیشنهادی می‌باشد با روش زمان‌بندی برخط معرفی‌شده در [1] و استفاده از زمان‌های بیکاری ایجادشده (که در حین اجرای وظایف ایجاد می‌شود)، فرکانس کاری و انرژی مصرفی کاهش می‌یابد. بنابراین راهکار پیشنهادی در ابتدا نیازمند بازنمایی13 مسئله و سپس حل زیرمسائل مختلف است که در ادامه معرفی خواهند شد.
4-1 بازنمایی مسئله
برای زمان‌بندی صحیح وظایف و کاهش مصرف انرژی در سیستم‌های بحرانی- مختلط، ابتدا باید عامل‌های اصلی مسئله را معرفی نمود. این بازنمایی باید به‌گونه‌اي باشد که بتوان پارامترهاي دخیل در مسئله را بیان و زمان‌بندی و کاهش انرژی مصرفی را به‌عنوان توابعی از این پارامترها تعریف کرد. بنابراین مسئله در قالب پنج‌تایی زیر بیان می‌شود
(5)
که پارامترهاي مختلف آن عبارتند از
- مدل وظیفه 
: نشان‌دهنده وظایفی است که اجرا خواهند شد. این وظایف در بخش 3-1 به‌طور کامل توضیح داده شده است.
- وضعیت سیستم 
: وضعیت سیستم را نشان می‌دهد. برای سیستم بحرانی- مختلط با دو وضعیت کاری مختلف، وضعیت سیستم در حالت غیربحرانی با و وضعیت سیستم در حالت بحرانی با نشان داده می‌شود. ابتدا سیستم در شروع به کار کرده و چنانچه وظیفه بحرانی به زمانی بیشتر از نیاز داشته باشد سیستم وضعیت خود را تغییر داده و می‌شود. در این حالت وظایف غیربحرانی برای تضمین اجرای وظایف بحرانی حذف خواهند شد.
- فرکانس کاری وظیفه 
: فرکانس هر وظیفه در وضعیت‌های مختلف سیستم را نشان می‌دهد. بنابراین در حالت یک فرکانس کاری برای وظایف غیربحرانی 
و یک فرکانس کاری برای وظایف بحرانی 
در نظر گرفته می‌شود. در حالت که وظایف غیربحرانی حذف شده‌اند، فقط یک فرکانس کاری برای وظایف بحرانی 
در نظر گرفته می‌شود.
- تعداد هسته‌ها 
: نشان‌دهنده تعداد هستههای سیستم است. وجود هستههای اضافه منجر به ایجاد زمان بیکاری بیشتر برای کاهش انرژی مصرفی می‌شود؛ لذا تعداد هسته‌ها تأثیر بسزایی بر ارزیابی طرح پیشنهادی دارد.
- انرژی سیستم 
: انرژی مصرفی یک وظیفه، توان مصرفی در زمان سپری‌شده برای اجرای وظیفه است که به‌صورت (6) می‌باشد
(6)
که 
نشان‌دهنده انرژی مصرفی در بوده و از (7) محاسبه می‌شود
(7)
و 
نشان‌دهنده انرژی مصرفی در بوده و از (8) محاسبه می‌شود
(8)
بنابراین وظایف برای یک ابردوره14 (كوچك‌ترين مضرب مشترك دوره همه وظايف) زمان‌بندی و مقدار انرژی مصرفی (در یک ابردوره) محاسبه می‌شود.
4-2 فازهای لازم برای حل مسئله اصلی
برای حل مسئله کاهش مصرف انرژی و تضمین اجرای به‌موقع وظایف در سیستم‌های بحرانی- مختلط متشکل از پردازنده‌های چندهستهای، بعد از بازنمایی مسئله حل فازهای زیر ضروری است:
- نگاشت وظایف
- محاسبه فاکتور برای تولید موعد مقرر مجازی (VD) برای وظایف بحرانی
- محاسبه فرکانس برای وظایف غیربحرانی در با توجه به مهلت زمانی وظایف
- محاسبه فرکانس برای وظایف بحرانی در و برای همین وظایف در با توجه به مهلت زمانی وظایف
- دخیل‌نمودن زمان‌بندي در کنار روش کاهش انرژی مصرفی
4-2-1 نگاشت وظايف در سيستم‌های بحرانيت مختلط
برای نگاشت وظایف بی‌درنگ در سیستم‌های چندهستهای، الگوریتم‌های زیادی وجود دارند که این روش‌ها به دو دسته سراسری15 و بخشبندیشده16 تقسیم می‌شوند [37] و [38]. در نگاشت سراسری، یک وظیفه ممکن است بر روی پردازنده‌های مختلفی اجرا شود؛ اما در نگاشت بخشبندیشده، وظیفه بر روی یک پردازنده خاص اجرا می‌شود. به‌خاطر سادگی و کارایی، الگوریتم‌های بخشبندیشده به الگوریتم‌های سراسری ترجیح داده می‌شوند [38]. نکته مهمی که باید در نظر گرفته شود این است که راهکارهای مدیریت انرژی سیستم به میزان زمان بیکاری موجود وابسته است و هنگامی که این زمان بیکاری ناکافی باشد (مهلت زمانی ضیق17 باشد)، راهکارهای مدیریت انرژی به‌خوبی نمی‌توانند انرژی مصرفی را کاهش دهند. بنابراین روشی برای نگاشت وظایف در سیستم‌های بحرانی- مختلط نیاز است که ضمن درنظرگرفتن وظایف با درجه بحرانیت مختلط با متعادل‌کردن وظایف بر روی پردازنده‌ها بیشترین زمان بیکاری را برای کاهش‌دادن انرژی مصرفی ایجاد نماید. روش‌هایی برای نگاشت وظایف در سیستم‌های بحرانی- مختلط وجود دارد [21]، [22] و [30] که در ادامه بررسی می‌شوند. به‌منظور مقایسه و پیداکردن بهترین روش (که بیشترین زمان بیکاری را ایجاد می‌کند)، از تمام این روش‌ها در قسمت ارزیابی استفاده خواهد شد. مرجع [21] (Baruah's method) با استفاده از زمان‌بندی بخشبندیشده، وظایف را بین پردازنده‌ها تقسیم و برای زمان‌بندی هر پردازنده از الگوریتم EDF-VD استفاده می‌کند. در این مقاله، ابتدا تمام وظایف بحرانی بر روی پردازنده‌های متفاوت توسط روش اولین برازش18 و سپس وظایف غیربحرانی بر روی پردازنده‌های باقیمانده توسط روش اولین برازش تقسیم می‌شوند. این روش به‌خاطر استفاده از الگوریتم اولین برازش، بهره‌وری سیستم را افزایش می‌دهد؛ ولی برای کاهش انرژی مصرفی که نیازمند زمان بیکاری است، مناسب نیست. مرجع [22] (Gu's method) نیز مشابه [21] از زمان‌بندی بخشبندیشده برای تقسیم وظایف بین پردازنده‌ها بهره برده و برای زمان‌بندی هر پردازنده از الگوریتم زمان‌بندی [7] استفاده کرده است. در این روش ابتدا تمام وظایف بحرانی بر روی پردازنده‌های متفاوت توسط روش بدترین برازش19 و سپس وظایف غیربحرانی بر روی پردازنده‌های باقیمانده توسط روش اولین برازش تقسیم می‌شوند. این روش به‌دلیل استفاده از الگوریتم اولین برازش برای وظایف غیربحرانی، بهره‌وری سیستم را افزایش داده است؛ اما برخلاف [21] به‌دلیل توزیع متعادل وظایف بحرانی بر روی هسته‌ها و وجود زمان بیکاری بیشتر برای کاهش انرژی مصرفی مناسب است. بنابراین در [30] (3EM) با متعادل‌کردن وظایف بر روی پردازنده‌ها و به‌منظور ایجاد بیشترین زمان بیکاری برای کاهش انرژی مصرفی، تمام وظایف توسط روش بدترین برازش بر روی پردازنده‌های متفاوت نگاشت می‌شوند. ابتدا تمام وظایف بحرانی و سپس وظایف غیربحرانی بر روی پردازنده‌های باقیمانده نیز تقسیم می‌شوند.
4-2-2 محاسبه فاکتور X و فرکانس کاری وظايف
طبق بخش 3-3، این مقاله از الگوریتم EDF-VD برای زمان‌بندی وظایف استفاده می‌کند که در آن با محاسبه پارامتر ، یک مهلت زمانی مجازی برای وظایف بحرانی در نظر گرفته شده و سپس تمام وظایف طبق الگوریتم EDF زمان‌بندی می‌شوند. از آنجا که بر اساس زمان اجرا و بهره‌وری وظایف محاسبه می‌گردد و استفاده از DVFS منجر به افزایش زمان اجرای وظایف می‌شود، بعد از اعمال روش DVFS، محاسبه مجدد 
ضروری است. بنابراین 
از (9) محاسبه می‌شود
(9)
شکل 1: انرژی مصرفی بر اساس بهره‌وری وظایف.
که در آن 
بهره‌وری وظایف بعد از اعمال روش DVFS می‌باشد و از (10) محاسبه می‌شود
(10)
همچنین طبق آنچه در بخش 4-1 در مورد وضعیت سیستم و فرکانس کاری وظایف توضیح داده شد، سیستم در دو وضعیت بحرانی 
و غیربحرانی 
فعالیت خواهد داشت. بر همین اساس در حالت یک فرکانس کاری برای وظایف غیربحرانی و یک فرکانس کاری برای وظایف بحرانی در نظر گرفته می‌شود. در حالت که وظایف غیربحرانی حذف شده‌اند، فقط یک فرکانس کاری برای وظایف بحرانی در نظر گرفته می‌شود. از آنجا که انرژی سیستم وابسته به فرکانس و زمان اجرای وظیفه است با کاهش فرکانس، انرژی مصرفی سیستم کاهش چشم‌گیری خواهد داشت. بنابراین می‌توان از زمان رزرو در نظر گرفته شده برای وظایف بحرانی برای کاهش بیشتر فرکانس وظایف استفاده نمود. از این رو در حالت این زمان رزرو به زمان بیکاری سیستم افزوده می‌شود که برای کاهش بیشتر فرکانس و کاهش انرژی مصرفی سیستم مناسب است. بنابراین اگر 
بهره‌وری به‌روزشده وظایف در صورت اتمام وظایف بحرانی در و 
فرکانس بحرانی یا فرکانس انرژی کارآمد باشد [1]، فرکانس جدید پردازنده 
طبق (11) محاسبه می‌شود
(11)
5- ارزیابی راهکار پیشنهادی
روش ارائه‌شده مشابه [1] و [19] با شبیه‌سازی بر روی وظایفی که به‌صورت تصادفی تولید شده و نیز وظایف کاربردی 20FMS [30] (که شامل 7 وظیفه با بحرانیت بالا و 4 وظیفه با بحرانیت پایین می‌باشد) ارزیابی شده است. ویژگی وظایفی که به‌صورت تصادفی تولید می‌شوند مشابه [19] می‌باشد که از روش‌های معروف تولید وظایف در سیستم‌های بحرانی- مختلط هستند. بنابراین با توجه به این ویژگی‌ها، موعد مقرر وظایف بین 10 تا 100 و بهره‌وری وظایف بین 2/0 تا 4/0 در نظر گرفته شده است. سپس بر اساس موعد مقرر و بهره‌وری انتخاب‌شده، زمان اجرای وظایف محاسبه می‌شود. برای وظایف بحرانی، مقدار زمان رزرو به‌صورت 
تعریف می‌شود که 
(زمان
شکل 2: انرژی مصرفی بر اساس زمان رزرو سیستم (پارامتر 
).
رزرو سیستم و نسبت به است) بین 5/1 تا 5/2 می‌باشد. بنابراین در هر بار شبیه‌سازی، 1000 مجموعه تصادفی وظايف تولید شده و مقدار انرژی مصرفی در یک ابردوره به‌صورت نرمال‌شده در سیستم با 4 هسته محاسبه می‌گردد. سپس روش پيشنهادي با استفاده از روش‌های نگاشت وظایف معرفی‌شده بخش 4-2-1 ارزیابی و در انتها با روش ارائه‌شده در [30] مقایسه خواهد گردید.
5-1 مقدار انرژی مصرفی بر اساس بهره‌وری وظايف
شکل 1 انرژی مصرفی را بر اساس بهره‌وری وظایف که از 1/1 تا 7/2 متغیر است (با روش‌های مختلف نگاشت وظایف) نشان می‌دهد. همان طور که مشاهده می‌شود با افزایش بار کاری سیستم، انرژی مصرفی در تمام روش‌ها افزایش می‌یابد. علت این امر، کاهش زمان بیکاری به‌دلیل افزایش بار کاری سیستم می‌باشد. لازم به ذکر است که هرچه زمان بیکاری کمتر باشد، کاهش فرکانس برای صرفه‌جویی انرژی مصرفی نیز اندک خواهد بود. با این حال با افرایش بهره‌وری وظایف، انرژی مصرفی روش 3EM نسبت به سایر روش‌ها کمتر است که علت اصلی آن، متعادل‌کردن بار کاری پردازنده‌ها است که منجر به استفاده بهینه از زمان بیکاری می‌شود.
5-2 مقدار انرژی مصرفی بر اساس زمان رزرو سیستم (پارامتر µ )
شکل 2 انرژی مصرفی را برای مقادیر مختلف (5/1 تا 5/2) با فرض 
و 
نشان می‌دهد. همان طور که مشاهده می‌شود با افزایش زمان رزرو که منجر به افزایش بار کاری سیستم خواهد شد، انرژی مصرفی در تمام روش‌ها افزایش می‌یابد. علت این امر، کاهش زمان بیکاری به‌دلیل افزایش بار کاری سیستم است (هرچه زمان بیکاری کمتر باشد، کاهش فرکانس برای صرفه‌جویی انرژی مصرفی نیز اندک خواهد بود). همان طور که در شکل دیده می‌شود با افزایش ، میزان انرژی مصرفی در روش 3EM نسبت به سایر روش‌ها کمتر می‌شود. علت این امر متعادل‌بودن بار کاری پردازنده‌ها در روش 3EM و استفاده بهینه از زمان بیکاری است.
5-3 مقدار انرژی مصرفی بر اساس تعداد وظایف
شکل 3 انرژی مصرفی را بر اساس تعداد وظایف در شرایطی که 
و 
است، نشان می‌دهد. ملاحظه می‌شود که افزایش وظایف، تأثیر چندانی بر انرژی مصرفی ندارد. علت این امر وابسته‌بودن انرژی مصرفی به بهره‌وری وظایف است و نه تعداد وظایف.
شکل 3: انرژی مصرفی بر اساس تعداد وظایف.
شکل 4: انرژی مصرفی بر اساس احتمال تغيير وضعيت سيستم.
5-4 مقدار انرژی مصرفی بر اساس احتمال تغيير وضعيت سيستم
با توجه به احتمال قرارگرفتن سیستم در حالات مختلف، بررسی انرژی سیستم تنها در مناسب نیست و به همین علت با گذشت زمان، احتمال تغییر وضعیت (از به ) افزایش پیدا می‌کند. به‌منظور بررسی‌کردن انرژی در حالات مختلف سیستم، پارامتر 
برای و پارامتر 
برای
در نظر گرفته می‌شود؛ به‌طوری که 
می‌باشد. این پارامترها، انرژی مصرفی را در حالات مختلف سیستم نشان می‌دهند. در ، 
و به‌طور مشابه در ، 
است؛ بنابراین با توجه به (6)، انرژی مصرفی سیستم طبق (12) تعریف می‌شود
(12)
شکل 4 انرژی مصرفی سیستم را به‌ازای مقادیر مختلف 
با طول گام 1/0 نشان می‌دهد. همان طور که مشاهده می‌شود با افزایش پارامتر ، انرژی مصرفی سیستم کاهش می‌یابد. علت این امر آن است که با افزایش از 0 به 1، سیستم بیشتر در فعال بوده که در این حالت از تکنیک DVFS برای کاهش انرژی مصرفی استفاده می‌شود.
5-5 مقدار انرژی مصرفی بر اساس تعداد هسته‌ها
تعداد هسته‌ها یکی از پارامترهای ارزیابی است که تأثیر بسزایی در ایجاد زمان بیکاری و کاهش انرژی مصرفی دارد. در بخش‌های قبلی به ارزیابی سیستم با 4 هسته (با توجه به پارامترهای معرفی‌شده در ارزیابی)
شکل 5: انرژی مصرفی بر اساس تعداد هسته‌ها.
شکل 6: انرژی مصرفی بر اساس اثر انرژی استاتیک.
پرداخته شد. اکنون اثر تعداد هسته‌ها بر انرژی مصرفی سیستم، ارزیابی می‌شود. شکل 5 انرژی ذخیره‌شده سیستم را با هستههای مختلف نشان می‌دهد. همان طور که مشاهده می‌شود در روش‌های Baruah و Gu تعداد هسته‌ها بر انرژی مصرفی سیستم اثر مستقیمی ندارد. علت این امر استفاده از الگوریتم اولین برازش برای نگاشت وظایف است. این الگوریتم بهره‌وری سیستم را افزایش می‌دهد؛ ولی برای کاهش انرژی مصرفی که نیازمند زمان بیکاری است، مناسب نیست. اما میزان انرژی مصرفی در روش 3EM نسبت به سایر روش‌ها کمتر می‌باشد. علت این امر استفاده از الگوریتم بدترین برازش و استفاده بهینه از زمان بیکاری است.
5-6 مقدار انرژی مصرفی بر اساس اثر انرژی استاتیک
در این قسمت اثر توان مصرفی استاتیک بر انرژی مصرفی سیستم ارزیابی می‌شود. شکل 6 انرژی ذخیره‌شده سیستم با درنظرگرفتن 
[19] و [26] را نشان می‌دهد که 
از 2/0 تا 1 با طول گام 2/0 متغیر می‌باشد. همان طور که مشاهده می‌شود توان مصرفی استاتیک نقشی بسزا در ذخیره انرژی مصرفی دارد و با افزایش این مقدار، میزان انرژی ذخیره‌شده تا 20 درصد کاهش می‌یابد.
5-7 مقایسه با روش ارائه‌شده در [30]
در بخش‌های قبلی، انرژی مصرفی سیستم با استفاده از روش‌های متفاوت نگاشت وظایف (معرفی‌شده در بخش 4-2-1) ارزیابی شده است. در [30] روشی برای کاهش انرژی مصرفی در سیستم چند‌پردازنده‌ای ارائه گردیده است. در این مقاله بعد از نگاشت وظایف، طبق الگوریتم ارائه‌شده در [31] فرکانس کاری هر وظیفه به‌صورت ایستا مشخص شده و وظایف بر اساس این فرکانس اجرا می‌شوند. اما به‌دلیل ایستابودن این الگوریتم،
شکل 7: انرژی مصرفی با استفاده از وظایف FSM.
جدول 2: پارامترهای وظایف کاربردی FMS.
|
|
| Criticality |
|
21 | 15 | 5000 | HI |
|
36 | 25 | 200 | HI |
|
22 | 16 | 1000 | HI |
|
28 | 20 | 1600 | HI |
|
35 | 20 | 100 | HI |
|
24 | 17 | 1000 | HI |
|
21 | 15 | 1000 | HI |
|
100 | 100 | 1000 | LO |
|
180 | 180 | 1000 | LO |
|
140 | 140 | 1000 | LO |
|
100 | 100 | 1000 | LO |
|
نمی‌توان از زمان‌های بیکاری ایجادشده در حین اجرای وظایف برای کاهش بیشتر فرکانس کاری وظایف استفاده نمود. شکل 7 انرژی مصرفی را با استفاده از وظایف FSM به‌ازای مقادیر مختلف از 0 به 1 نشان می‌دهد. این وظایف طبق جدول 2 هستند. با توجه به این شکل، انرژی مصرفی روش پیشنهادی در مقایسه با [30] کمتر می‌باشد. علت آن است که در روش پیشنهادی با يك روش زمان‌بندی برخط از زمان بیکاری ایجادشده (که در حین اجرای وظایف ایجاد می‌شود) برای کاهش بیشتر فرکانس کاری وظایف استفاده می‌شود که کاهش انرژی مصرفی را به دنبال دارد.
6- نتيجه‌گيري
سیستم‌های بحرانی- مختلط در حوزه‌های مختلفی کاربرد دارند و اجرای به‌موقع وظایف با محدودیت زمانی و کاهش انرژی مصرفی به‌عنوان مسائل مهم در این سیستم‌ها مطرح است. به‌علاوه پردازنده‌های چندهستهای به‌دلیل قدرت محاسباتی بالا و افزایش کارایی به‌طور گسترده در سیستم‌های نهفته مورد استفاده قرار گرفته‌اند و انتخاب مناسبی برای سیستم‌های نهفته با بحرانیت مختلط هستند. از این رو به‌منظور دستیابی به زمان‌بندی بی‌درنگ همراه با کاهش انرژی مصرفی، یک روش زمان‌بندی ابتکاری برای کاهش انرژی مصرفی در این سیستم‌ها معرفی شده است. این الگوریتم انرژی مصرفی سیستم را با تغییر پویای ولتاژ و فرکانس (DVFS) کاهش داده و از زمان‌های بیکاری ایجادشده در حین اجرای وظایف برای کاهش بیشتر فرکانس استفاده می‌نماید. در این مقاله هر دو توان مصرفي ایستا و دینامیک در نظر گرفته شد. علاوه بر این، وضعیت سیستم و میزان انرژی مصرفی در هر دو حالت بحرانی و غیربحرانی مورد بررسی و ارزیابی قرار گرفت. نتایج شبیه‌سازی‌ها نشان مي‌دهند که زمان‌بندی پیشنهادی در مقايسه با روش‌هاي مشابه، عملکرد بهتری از خود نشان داده و انرژی مصرفی را تا 30 درصد بهبود مي‌بخشد.
مراجع
[1] س. ح. صادق‌زاده و ی. صداقت، "زمان‌بندی آگاه از انرژی مصرفی برای سیستم‌های بی‌درنگ تک‌پردازنده‌ای بحرانی- مختلط،" نشریه علمی- پژوهشی نشريه مهندسي برق و مهندسي كامپيوتر ايران، سال 16، شماره 4،
صص. 334-327، زمستان 1397.
[2] D. Zhu, "Reliability-aware dynamic energy management in dependable embedded real-time systems," ACM TECS, vol. 10, no. 2, Article ID: 26, 27 pp., Dec. 2011.
[3] P. Marwedel, Embedded System Design: Embedded Systems Foundations of Cyber-Physical Systems, Berlin, Germany: Springer, 2010.
[4] H. Kopetz, Real-Time Systems: Design Principles for Distributed Embedded Applications, Springer Science & Business Media, 2011.
[5] S. Baruah, et al., "Scheduling real-time mixed-criticality jobs," IEEE Trans. on Computers, vol. 61, no. 8, pp. 1140-1152, Aug. 2012.
[6] F. Santy, L. George, P. Thierry, and J. Goossens, "Relaxing mixedcriticality scheduling strictness for task sets scheduled with FP," in Proc. Euromicro Conf. on Real-Time Systems, ECRTS’12, pp. 155-165, Pisa, Italy, 11-13 Jul. 2012.
[7] S. Baruah, et al., "The preemptive uniprocessor scheduling of mixed-criticality implicit-deadline sporadic task systems," in Proc. Euromicro Conf. on Real-Time Systems, ECRTS'12, pp. 145-154, Pisa, Italy, 11-13 Jul. 2012.
[8] P. Taeju and K. Soontae, "Dynamic scheduling algorithm and its schedulability analysis for certifiable dual-criticality systems," in Proc. Int. Conf. Embedded Software, EMSOFT'11, pp. 253-262, Taipei Taiwan, 9-14 Oct. 2011.
[9] S. Baruah, H. Li, and L. Stougie, "Towards the design of certifiable mixed-criticality systems," in Proc. 16th IEEE Real-Time and Embedded Technology and Applications Symp., pp. 13-22, Stockholm, Sweden, 12-15 Apr. 2010.
[10] P. Huang, H. Yang, and L. Thiele, "On the scheduling of fault-tolerant mixed-criticality systems," in Proc. Design Automation Conf. (DAC), ACM/EDAC/IEEE, DAC'14, 6 pp., 1-5 Jun. 2014.
[11] S. Baruah and S. Vestal, "Schedulability analysis of sporadic tasks with multiple criticality specifications," in Proc. Euromicro Conf. on Real-Time Systems, ECRTS'08, pp. 147-155, Prague, Czech Republic, 2-4 Jul. 2008.
[12] Z. Lia, C. Guo, X. Hua, and S. Ren, "Reliability guaranteed energy minimization on mixed-criticality systems," J. of Syst. and Software, vol. 112, pp. 1-10, Feb. 2016.
[13] H. Su, D. Zhu, and S. Brandt, "An elastic mixed-criticality task model and early-release EDF scheduling algorithms," ACM TODAES, vol. 22, no. 2, Article ID: 28, 28 pp., Apr. 2017.
[14] A. Thekkilakattil, R. Dobrin, and S. Punnekkat, "Fault-tolerant scheduling of mixed-criticality real-time tasks under error bursts," Procedia Computer Science, vol. 46, pp. 1148-1155, 2015.
[15] P. Ekberg and W. Yi, "Bounding and shaping the demand of mixed-criticality sporadic tasks," in Proc. 24th Euromicro Conference on Real-Time Systems, ECRTS, pp. 135-144, Pisa, Italy, 11-13 Jul. 2012.
[16] S. Vestal, "Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance," in Proc. 28th IEEE Int. Real-Time Systems Symp., pp. 239-243, Tucson, AZ, USA, 3-6 Dec. 2007.
[17] J. Lin, A. M. K. Cheng, D. Steel, and M. Yu-Chi Wu, "Scheduling mixed-criticality real-time tasks in a fault-tolerant system," International Journal of Embedded and Real-Time Communication Systems, vol. 6, no. 2, 22 pp., 2015.
[18] C. Kamienski, et al., "Application development for the Internet of Things: a context-aware mixed criticality systems development platform," Computer Communications, vol. 104, pp. 1-16, 15 May 2017.
[19] A. Taherin, M. Salehi, and A. Ejlali, "Reliability-aware energy management in mixed-criticality systems," IEEE Trans. on Sustainable Computing, vol. 3, no. 3, pp. 195-208, Jul.-Sept. 2018.
[20] M. Salehi, A. Ejlali, and B. M. Al-Hashimi, "Two-phase low-energy N-modular redundancy for hard real-time multi-core systems," IEEE TPDS, vol. 27, no. 5, pp. 1497-1510, May 2015.
[21] S. Baruah, C. Bipasa, L. Haohan, and S. Insik, "Mixed-criticality scheduling on multiprocessors," Real-Time Systems, vol. 50, no. 1, pp. 142-177, Jan. 2014.
[22] C. Gu, G. Nan, D. Qingxu, and Y. Wang, "Partitioned mixed-criticality scheduling on multiprocessor platforms," in Proc. Design, Automation & Test in Europe Conf. & Exhibition, DATE'14, 6 pp., Dresden, Germany, 24-28 Mar. 2014.
[23] Y. Zhang and K. Chakrabarty, "Dynamic adaptation for fault tolerance and power management in embedded real-time systems," ACM Trans. on Embedded Computing Systems, vol. 3, no. 2, pp. 336-360, May 2004.
[24] L. Benini, A. Bogliolo, and G. De Micheli, "A survey of design techniques for system-level dynamic power management," IEEE Trans. VLSI Sys., vol. 8, no. 3, pp. 299-316, Jun. 2000.
[25] T. D. Burd, T. A. Pering, A. J. Stratakos, and R. W. Brodersen, "A dynamic voltage scaled microprocessor system," IEEE J. Solid-State Circuits, vol. 35, no. 11, pp. 1571-1580, Nov. 2000.
[26] M. A. Haque, H. Aydin, and D. Zhu, "On reliability management of energy-aware real-time systems through task replication," IEEE Trans. Parallel Distrib. Syst., vol. 28, no. 3, pp. 813-825, Mar. 2017.
[27] Y. Zhang and R.Chen, "A survey of energy-aware scheduling in mixed-criticality systems," Journal of Systems Architecture, vol.1, no.17, Article ID: 102524, Jun. 2022.
[28] J. Chen and C. Kuo, "Energy-efficient scheduling for realtime systems on dynamic voltage scaling (dvs) platforms," in Proc. Embedded and Real-Time Computing Systems and Applications, RTCSA'07, pp. 28-38, Daegu, South Korea, 21-24 Aug. 2007.
[29] A. Burns and R. I. Davis, Mixed-Criticality Systems: A Review, Tech. Rep., Dept. Comput. Sci. Univ. York, 61 pp. 1-61, 2016.
[30] S. Narayana, P. Huang, G. Giannopoulou, L. Thiele, and R. V. Prasad, "Exploring energy saving for mixed-criticality systems on multi-cores," in Proc. IEEE Real-Time and Embedded Technology and Applications Symp., RTAS'16, 12 pp., Vienna, Austria, 11-14 Apr. 2016.
[31] P. Huang, P. Kumar, G. Giannopoulou, and L. Thiele, "Energy efficient DVFS scheduling for mixed-criticality systems," in Proc. Int. Conf. Embedded Software, EMSOFT'14, 10 pp., Uttar Pradesh, India, 12-17 Oct. 2014.
[32] V. Moghaddas, M. Fazeli, and A. Patooghy, "Reliability-oriented scheduling for static-priority real-time tasks in standby-sparing systems," Microprocessors and Microsystems, Pt A, vol. 45, pp. 208-215, Aug. 2016.
[33] V. Legout, M. Jan, and L. Pautet, "Mixed-criticality multiprocessor real-time systems: energy consumption vs deadline misses," in Proc. 1st. Workshop on Real-Time Mixed Criticality Syst., ReTiMiCS'13', 6 pp., Taipei, Taiwan. Aug. 2013.
[34] M. Völp, M. Hähnel, and A. Lackorzynski, "Has energy surpassed timeliness? scheduling energy-constrained mixed-criticality systems," in Proc. IEEE Real-Time and Embedded Technology and Applications Symp., RTAS'14, pp. 275-284, Berlin, Germany, 15-17 Apr. 2014.
[35] F. Zhang and A. Burns, "Schedulability analysis for real-time systems with EDF scheduling," IEEE Trans. on Computers, vol. 589, no. 9, pp. 1250-1258, Sept. 2009.
[36] N. Audsley, Optimal Priority Assignment and Feasibility of Static Priority Tasks with Arbitrary Start Times, Dept. of Comp. Sci., University of York, UK, 1991.
[37] A. K. Singh, M. Shafique, A. Kumar, and J. Henkel, "Mapping on multi/many-core systems: Survey of current and emerging trends," in Proc. of 50th ACM/EDAC/IEEE Design Automation Conf., DAC'13, pp. 275-284, Austin, TX, USA, 29 May-7 Jun. 2013.
[38] A. Bastoni, B. B. Brandenburg, and J. H. Anderson, "An emperical comparison of global, partitioned and clustered multiprocessor EDF mchedulers," in Proc. 31st IEEE Real-Time Systems Symp., RTSS'10, San Diego, CA, USA, 30 Nov.-3 Dec. 2010.
سید حسن صادق‌زاده تحصيلات خود را در مقاطع كارشناسي و كارشناسي ارشد کامپیوتر بهترتيب در سالهاي 1385 و 1388 پايان رسانده است. ایشان دانشجوی دکتری رشته کامپیوتر و عضو آزمایشگاه ﺳﯿﺴﺘﻢﻫﺎي ﻧﻬﻔﺘﻪ ﺗﻮزﯾﻊﺷﺪه اﺗﮑﺎﭘﺬﯾﺮ (DDEmS) دانشگاه فردوسی مشهد می‌باشد. ایشان هماکنون هیأت علمی دانشكده مهندسي كامپيوتر دانشگاه پیام نور ميباشد. زمينههاي تحقيقاتي مورد علاقه ايشان عبارتند از: سیستم‌های نهفته اتکاپذیر، تحمل پذیری اشکال، قابلیت اطمینان، زمان‌بندی و طراحی سیستم‌های کمتوان.
[1] . Implicit Deadline
[2] . Period
[3] . Power Consumption
[4] . Static Power Consumption
[5] . Dynamic Power Consumption
[6] . Frequency-Dependent Active Power
[7] . Frequency-Independent Active Power
[8] . Early Deadline First
[9] . Audsley's Priority-Based Real-Time Scheduling
[10] . Virtual Deadlines
[11] . Utilization
[12] . Minimum Service Requirement
[13] . Representation
[14] . Hyperperiod
[15] . Global
[16] . Partitioned
[17] . Tight
[18] . First-Fit
[19] . Worst-Fit
[20] . Flight Management System