یک روش توأم زمان‌بندی و نگاشت وظایف در سیستم‌های چندپردازنده‌ای روی تراشه با هدف بهبود چالش‌های طراحی
الموضوعات :آتنا عبدی 1 , حمیدرضا زرندی 2 , شاهرخ جلیلیان 3
1 - دانشگاه امیرکبیر
2 - دانشگاه صنعتی امیرکبیر
3 - پژوهشگاه فضایی ایران
الکلمات المفتاحية: سیستم چندپردازنده‌ایزمان‌بندیقابلت اطمینانتوان مصرفیدمابهینه‌سازی چندهدفیپوسته Pareto,
ملخص المقالة :
در این مقاله روش مکاشفه‌ای زمان‌بندی و نگاشت وظایف ایستا به منظور بهینه‌سازی زمان اجرا، قابلیت اطمینان، توان مصرفی و دما به عنوان اساسی‌ترین چالش‌های طراحی سیستم‌های چندپردازنده‌ای ارائه شده است. روش ارائه‌شده بر پایه زمان‌بندی لیستی بوده و تکرار وظایف، مقیاس پویای ولتاژ و فرکانس و افزودن زمان‌های خالی با هدف بهبود قابلیت اطمینان، توان مصرفی و دمای سیستم و گسترده‌کردن فضای جواب با هدف جستجوی مؤثرتر در آن در نظر گرفته شده است. به دلیل رابطه متخاصم و ناهمسوی مابین پارامترهای ذکرشده، فرایند بهینه‌سازی چندهدفی بسیار پیچیده بوده و در روش پیشنهادی از راهکار استخراج پوسته Pareto استفاده شده است. همچنین در این روش، مدل‌سازی جامعی از تمامی اهداف صورت گرفته و وابستگی‌های آنها لحاظ شده است. آزمایش‌های متعدی به منظور بررسی کارایی و قابلیت‌های روش پیشنهادی در بهینه‌سازی هم‌زمان اهداف مسئله و تولید جواب‌های درست انجام گرفته است. بررسی‌ها و مقایسه روش پیشنهادی با یک روش مکاشفه‌ای مؤثر پیشین بهبود میانگین 19% در پارامترهای طراحی مورد هدف مسئله را نشان می‌دهد.
[1] W. Wolf, A. A. Jerraya, and G. Martin, "Multiprocessor system-on-chip (MPSoC) technology," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 10, pp. 1701-1713, Oct. 2008.
[2] A. B. Abdallah, Advanced Multicore Systems-On-Chip, Springer, 2017.
[3] F. Ferrandi, P. L. Lanzi, C. Pilato, D. Sciuto, and A. Tumeo, "Ant colony heuristic for mapping and scheduling tasks and communications on heterogeneous embedded systems," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 29, no. 6, pp. 911-924, Jun. 2010.
[4] J. Ahmed, et al., Fuzzy Logic Based Power-Efficient Real-Time Multi-Core System. Springer, 2017.
[5] I. Assayad, A. Girault, and H. Kalla, "Tradeoff exploration between reliability, power consumption, and execution time for embedded systems," International J. on Software Tools for Technology Transfer, vol. 15, no. 3, pp. 229-245, 2013.
[6] H. F. Sheikh and I. Ahmad, "Sixteen heuristics for joint optimization of performance, energy, and temperature in allocating tasks to multi-cores," ACM Trans. on Parallel Computing, vol. 3, no. 2, Article No.: 9, 29 pp., Aug. 2016.
[7] A. K. Das, A. Kumar, B. Veeravalli, and F. Catthoor, "Literature survey on system-level optimizations techniques," in Reliable and Energy Efficient Streaming Multiprocessor Systems, pp. 33-44, Springer, 2018.
[8] A. Das, A. Kumar, B. Veeravalli, C. Bolchini, and A. Miele, "Combined DVFS and mapping exploration for lifetime and soft-error susceptibility improvement in MPSoCs," in Proc. Design, Automation and Test in Europe Conf. and Exhibition, DATE’14, 6 pp., Dresden, Germany, 24-28 Mar. 2014.
[9] 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 the 50th Annual Design Automation Conf., 10 pp., Austin, TX, USA, 29 May-7 Jun. 2013.
[10] L. Huang, F. Yuan, and Q. Xu, "Lifetime reliability-aware task allocation and scheduling for MPSoC platforms," in Proc. IEEE/ACM Design, Automation, and Test in Europe, DATE’09, pp. 51-56, Nice, France, 20-24 Apr. 2009.
[11] A. Girault and H. Kalla, "A novel bicriteria scheduling heuristics providing a guaranteed global system failure rate," IEEE Trans. on Dependable and Secure Computing, vol. 6, no. 4, pp. 241-254, Oct./Dec. 2009.
[12] T. Chantem, R. P. Dick, and X. S. Hu, "Temperature-aware scheduling and assignment for hard real-time applications on MPSoCs," in Proc. of the Conf. on Design, Automation and Test in Europe, DATE’08, pp. 288-293, Munich, Germany, Mar. 2008.
[13] M. Ammar, et al., "On exploiting energy-aware scheduling algorithms for mde-based design space exploration of MP2SoC," in Proc. 24th Euromicro Int. Conf. on the Parallel, Distributed, and Network-Based Processing, PDP’16, pp. 643-650, Heraklion, Greece, 17-19 Feb. 2016.
[14] Z. Ekhtiyari, V. R. Moghaddas, and H. Beitollahi, "A temperature-aware and energy-efficient fuzzy technique to schedule tasks in heterogeneous MPSoC systems," The J. of Supercomputing, vol. 75, no. 8, pp. 5398-5419, 2019.
[15] L. Huang and Q. Xu, "Energy-efficient task allocation and scheduling for multi-mode MPSoCs under lifetime reliability constraint," in Proc. of the Conf. on Design, Automation and Test in Europe, DATE’10, pp. 1584-1589, Leuven, Belgium, Mar. 2010.
[16] P. Kumar and L. Thiele, "Thermally optimal stop-go scheduling of task graphs with real-time constraints," in Proc.16th Asia and South Pacific Design Automation Conf., pp. 123-128, Yokohama, Japan, 25-28 Jan. 2011.
[17] S. Zhuravlev, J. C. Saez, S. Blagodurov, A. Fedorova, and M. Prieto, "Survey of energy-cognizant scheduling techniques," IEEE Trans. on Parallel and Distributed Systems, vol. 24, no. 7, pp. 1447-1464, Jul. 2013.
[18] A. Das, A. Kumar, B. Veeravalli, C. Bolchini, and A. Miele, "Combined DVFS and mapping exploration for lifetime and soft-error susceptibility improvement in MPSoCs," Proc. of the Conf. on Design, Automation and Test in Europe, DATE’14, 6 pp., Dresden, Germany, Mar. 2014.
[19] A. Abdi and H. R. Zarandi, "A meta heuristic-based task scheduling and mapping method to optimize main design challenges of heterogeneous multiprocessor embedded systems," Microelectronics J., vol. 87, pp. 1-11, May 2019.
[20] V. T'kindt and J. C. Billaut, Multicriteria Scheduling: Theory, Models, and Algorithms, Springer Science & Business Media, 2006.
[21] M. Rausand, Reliability of Safety-Critical Systems: Theory and Applications, Wiley, 2014.
[22] D. Zhu, R. G. Melhem, and D. Mosse, "The effects of energy management on reliability in real-time embedded systems," in Proc. IEEE /ACM Int. Conf. on Computer Aided Design, 2004. ICCAD’04, pp. 35-40, San Jose, CA, USA, 7-11 Nov. 2004.
[23] B. Zhao, H. Aydin, and D. Zhu, "Generalized reliability-oriented energy management for real-time embedded applications," in Proc. 48th ACM/EDAC/IEEE Design Automation Conf., DAC’11, pp. 381-386, San Diego, CA, USA, 5-9 Jun. 2011.
[24] A. Das, A. Kumar, and B. Veeravalli, "Aging-aware hardware-software task partitioning for reliable reconfigurable multiprocessor systems," in Proc. Int Conf. on Compilers, Architecture and Synthesis for Embedded Systems, pp. 1-10, Montreal, Canada, Sept. 2013.
[25] J. Srinivasan, S. V. Adve, P. Bose, and J. A. Rivers, "Exploiting structural duplication for lifetime reliability enhancement," in Proc. 32nd Int. Symp. on Computer Architecture, ISCA'05 ISCA, pp. 520-531, Madison, WI, USA, 4-8 Jun. 2005.
[26] J. S. S. T. Association, "Failure mechanisms and models for semiconductor devices," jep122e, JEDEC Publication, 2016.
[27] T. Chantem, Y. Xiang, X. S. Hu, and R. P. Dick, "Enhancing multicore reliability through wear compensation in online assignment and scheduling," in Proc. IEEE/ACM Design, Automation, and Test in Europe, DATE’13, pp. 1373-1378, Grenoble, France, Mar. 2013.
[28] B. Ouni, I. Mhedbi, C. Trabelsi, R. B. Atitallah, and C. Belleudy, "Multi-level energy/power-aware design methodology for MPSoC," J. of Parallel and Distributed Computing, vol. 100, pp. 203-215, 2016.
[29] T. C. Hu, "Parallel sequencing and assembly line problems," Operations Research, vol. 9, no. 6, pp. 841-848, 1961.
[30] Embedded system synthesis benchmark suite (e3s), http://ziyang.eecs.umich.edu/ dickrp/e3s/, accessed: 2019-08-27.
[31] D. Rhodes, R. Dick, and K. Vallerio, Task Graphs for Free, http://ziyang.eecs.umich.edu/ dickrp/tgff, accessed: 2019-08-27.
