علوم رایانش و فناوری اطلاعات

زمان‌بندی انرژی وظایف بی‌درنگ موازی اولویت-ثابت در سیستم‌های سایبر-فیزیکی چند هسته‌ای

نویسندگان

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

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

3 دانشگاه تحصیلات تکمیلی علوم پایه، زنجان، ایران

چکیده

امروزه با افزایش نیاز محاسباتی سیستم‌های سایبر-فیزیکی، توجه به سیستم‌های چندهسته‌ای افزایش چشمگیر داشته است. نقش وظایف موازی که به‌صورت برنامه‌های چندنخی پیاده‌سازی می‌شوند در بهره‌گیری از امکانات پردازنده‌های چندهسته‌ای و پاسخ به نیازهای روز افزون محاسباتی بسیار پر اهمیت است؛ در برخی موارد بدون استفاده از پردازش موازی امکان رعایت موعدهای زمانی وجود ندارد. از سوی دیگر، بسیاری از سیستم‌های سایبر-فیزیکی در ماموریت‌هایی به کار گرفته می‌شوند که آن‌ها را در دریافت انرژی محدود می‌سازد. در این سیستم‌ها باید با مدیریت مناسب انرژی ورودی، وظایف را به نحوی زمانبندی کرد که بتوان با توجه به بودجه انرژی تمامی موعدهای زمانی را رعایت نمود. در این مقاله، ابتدا تحلیلی از عدم‌قطعیت مصرف انرژی وظایف موازی ارائه می‌شود و سپس یک روش برای زمانبندی وظایف بی‌درنگ موازی اولویت-ثابت در سیستم‌های سایبر-فیزیکی چندهسته‌ای با محدودیت انرژی ارائه می‌گردد. نتایج آزمایش‌ها تاثیر مثبت موازی سازی وظایف در زمانبندی‌پذیری را نشان می‌دهد. به طوری‌که در الگوریتم ارائه شده با کاهش طول مسیر بحرانی به کمتر از ۴۰ درصد، زمانبندی‌پذیری وظایف به صورت چشمگیری افزایش می‌یابد.

کلیدواژه‌ها

  • [1] R. (Raj) Rajkumar, I. Lee, L. Sha, J. Stankovic, “Cyber-physical systems,” Proc. 47th Des. Autom. Conf. - DAC ’10, p. 731, 2010.
  • [2] H. El Ghor, M. Chetto, R. H. Chehade, “A real-time scheduling framework for embedded systems with environmental energy harvesting,” Comput. Electr. Eng., vol. 37, no. 4, pp. 498–510, Jul. 2011.
  • [3] C. Moser, D. Brunelli, L. Thiele, L. Benini, “Real-time scheduling for energy harvesting sensor nodes,” Real-Time Syst., vol. 37, no. 3, pp. 233–260, Oct. 2007.
  • [4] C. Moser, D. Brunelli, L. Thiele, L. Benini, “Real-time scheduling with regenerative energy,” Proc. - Euromicro Conf. Real-Time Syst., pp. 261–270, 2006.
  • [5] M. Chetto, A. Queudet, “A note on EDF schedulingfor real-time energy harvesting systems,” IEEE Trans. Comput., vol. 63, no. 4, pp. 1037–1040, Apr. 2014.
  • [6] M. Chetto, D. Masson, S. Midonnet, “Fixed priority scheduling strategies for ambient energy-harvesting embedded systems,” Proc. - IEEE/ACM Int. Conf. Green Comput. Commun. GreenCom, pp. 50–55, 2011.
  • [7] Y. Abdeddaïm, Y. Chandarli, D. Masson, “The optimality of PFPasap algorithm for fixed-priority energy-harvesting real-time systems,” Proc. - Euromicro Conf. Real-Time Syst., pp. 47–56, 2013.
  • [8] R. Y. Tsai, R. K. Lenz, “Real time versatile robotics hand/eye calibration using 3D machine vision,” Proceedings. IEEE Int. Conf. Robot. Autom., pp. 554–561, 1988.
  • [9] J. Li, J. J. Chen, K. Agrawal, C. Lu, C. Gill, A. Saifullah, “Analysis of Federated and Global Scheduling for Parallel Real-Time Tasks,” Proc. - Euromicro Conf. Real-Time Syst., pp. 85–96, 2014.
  • [10] D. Moss, P. Pittsburgh, “Scheduling of Frame-based Embedded Systems with Rechargeable Batteries,” Work. Power Manag. Real-time Embed. Syst. (in conjunction with RTAS), pp. 1–8, 2001.
  • [11] J. Lin, A. M. K. Cheng, “Real-time task assignment in rechargeable multiprocessor systems,” Proc. - 14th IEEE Int. Conf. Embed. Real-Time Comput. Syst. Appl. RTCSA, pp. 279–284, 2008.
  • [12] C. Moser, D. Brunelli, L. Thiele, L. Benini, “Lazy scheduling for energy harvesting sensor nodes,” IFIP Int. Fed. Inf. Process., vol. 225, pp. 125–134, 2006.
  • [13] R. Jayaseelan, T. Mitra, X. Li, “Estimating the worst-case energy consumption of embedded software,” Real-Time Technol. Appl. - Proc., pp. 81–90, 2006.
  • [14] H. El Ghor, M. Chetto, R. H. Chehade, “A real-time scheduling framework for embedded systems with environmental energy harvesting,” Comput. Electr. Eng., vol. 37, no. 4, pp. 498–510, Jul. 2011.
  • [15] Y. Chandarli, Y. Abdeddaïm, D. Masson, “The fixed priority scheduling problem for energy harvesting real-time systems,” Proc. - 18th IEEE Int. Conf. Embed. Real-Time Comput. Syst. Appl. RTCSA - 2nd Work. Cyber-Physical Syst. Networks, Appl. CPSNA, pp. 415–418, 2012.
  • [16] K. Faramarzi, M. Hasanloo, M. Kargahi, “The PFPASAP algorithm for energy harvesting real-time systems with a non-ideal supercapacitor,” 5th Int. Conf. Comput. Knowl. Eng., pp. 279–284, 2015.
  • [17] M. Shirazi, M. Kargahi, L. Thiele, “Performance maximization of energy-variable self-powered (m, k)-firm real-time systems,” Real-Time Syst., vol. 56, no. 1, pp. 64–111, Jan. 2020.
  • [18] A. Saifullah, S. Fahmida, V. P. Modekurthy, N. Fisher, Z. Guo, “CPU energy-aware parallel real-time scheduling,” Leibniz Int. Proc. Informatics, LIPIcs, vol. 165, 2020.
  • [19] H. Nishikawa, K. Shimada, I. Taniguchi, H. Tomiyama, “Energy-aware scheduling of malleable fork-join tasks under a deadline constraint on heterogeneous multicores,” ACM SIGBED Rev., vol. 16, no. 3, pp. 57–62, Oct. 2019.
  • [20] B. Barzegar, H. Motameni, A. Movaghar, “EATSDCD: A green energy-aware scheduling algorithm for parallel task-based application using clustering, duplication and DVFS technique in cloud datacenters,” J. Intell. Fuzzy Syst., vol. 36, no. 6, pp. 5135–5152, Jan. 2019.
  • [21] D. S. Garey, Michael R.; Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979.
  • [22] R. D. Blumofe, C. F. Joerg, B. C. Kuszmaul, C. E. Leiserson, K. H. Randall, Y. Zhou, “Cilk: An efficient multithreaded runtime system,” J. Parallel Distrib. Comput., vol. 37, no. 1, pp. 55–69, Aug. 1996.
  • [23] “Intel CilkTM Plus Language Extension Specification.” [Online]. Available: https://www.cilkplus.org/sites/default/files/open_specifications/Intel_Cilk_plus_lang_spec_1.2.htm. [Accessed: 05-Sep-2020].
  • [24] O. Tardieu, H. Wang, H. Lin, “A work-stealing scheduler for X10’s task parallelism with suspension,” ACM SIGPLAN Not., vol. 47, no. 8, pp. 267–276, 2012.
  • [25] G. M. Amdahl, “Validity of the single processor approach to achieving large scale computing capabilities,” AFIPS Conf. Proc. - Spring Jt. Comput. Conf. AFIPS, pp. 483–485, 1967.
  • [26] Y. He, C. E. Leiserson, W. M. Leiserson, “The Cilkview scalability analyzer,” Annu. ACM Symp. Parallelism Algorithms Archit., pp. 145–156, 2010.
  • [27] T. B. Schardl, B. C. Kuszmaul, I. T. A. Lee, W. M. Leiserson, C. E. Leiserson, “The Cilkprof scalability profiler,” Annu. ACM Symp. Parallelism Algorithms Archit., pp. 89–100, 2015.
  • [28] Y. Abdeddaïm, Y. Chandarli, D. Masson, “The optimality of PFPasap algorithm for fixed-priority energy-harvesting real-time systems,” Proc. - Euromicro Conf. Real-Time Syst., pp. 47–56, 2013.
  • [29] M. Chetto, D. Masson, S. Midonnet, “Fixed priority scheduling strategies for ambient energy-harvesting embedded systems,” Proc. - IEEE/ACM Int. Conf. Green Comput. Commun. GreenCom, pp. 50–55, 2011.
  • [30] J. Li, J. J. Chen, K. Agrawal, C. Lu, C. Gill, A. Saifullah, “Analysis of Federated and Global Scheduling for Parallel Real-Time Tasks,” Proc. - Euromicro Conf. Real-Time Syst., pp. 85–96, 2014.
  • [31] A. Mirhoseini, F. Koushanfar, “HypoEnergy: Hybrid supercapacitor-battery power-supply optimization for Energy efficiency,” Proc. -Design, Autom. Test Eur. DATE, pp. 887–890, 2011.
علوم رایانش و فناوری اطلاعات
دوره 18، شماره 1
بهار و تابستان
اردیبهشت 1399