یک روش توأم زمان‌بندی و نگاشت وظایف در سیستم‌های چندپردازنده‌ای روی تراشه با هدف بهبود چالش‌های طراحی
محورهای موضوعی : مهندسی برق و کامپیوترآتنا عبدی 1 , حمیدرضا زرندی 2 * , شاهرخ جلیلیان 3
1 - دانشگاه امیرکبیر
2 - دانشگاه صنعتی امیرکبیر
3 - پژوهشگاه فضایی ایران
کلید واژه: سیستم چندپردازنده‌ایزمان‌بندیقابلت اطمینانتوان مصرفیدمابهینه‌سازی چندهدفیپوسته Pareto,
چکیده مقاله :
در این مقاله روش مکاشفه‌ای زمان‌بندی و نگاشت وظایف ایستا به منظور بهینه‌سازی زمان اجرا، قابلیت اطمینان، توان مصرفی و دما به عنوان اساسی‌ترین چالش‌های طراحی سیستم‌های چندپردازنده‌ای ارائه شده است. روش ارائه‌شده بر پایه زمان‌بندی لیستی بوده و تکرار وظایف، مقیاس پویای ولتاژ و فرکانس و افزودن زمان‌های خالی با هدف بهبود قابلیت اطمینان، توان مصرفی و دمای سیستم و گسترده‌کردن فضای جواب با هدف جستجوی مؤثرتر در آن در نظر گرفته شده است. به دلیل رابطه متخاصم و ناهمسوی مابین پارامترهای ذکرشده، فرایند بهینه‌سازی چندهدفی بسیار پیچیده بوده و در روش پیشنهادی از راهکار استخراج پوسته Pareto استفاده شده است. همچنین در این روش، مدل‌سازی جامعی از تمامی اهداف صورت گرفته و وابستگی‌های آنها لحاظ شده است. آزمایش‌های متعدی به منظور بررسی کارایی و قابلیت‌های روش پیشنهادی در بهینه‌سازی هم‌زمان اهداف مسئله و تولید جواب‌های درست انجام گرفته است. بررسی‌ها و مقایسه روش پیشنهادی با یک روش مکاشفه‌ای مؤثر پیشین بهبود میانگین 19% در پارامترهای طراحی مورد هدف مسئله را نشان می‌دهد.
In this paper, a static task scheduling and mapping heuristic approach to optimize execution time, reliability, power and temperature of multiprocessor systems on chip is presented. This method is proposed based on the list scheduling approach and utilized task replication, dynamic voltage and frequency scaling, and adding cooling slacks to improve reliability, power consumption and temperature to expand the design space and explore the solution set more efficiently. Due to the existing trade-offs among the considered parameters and their optimization, the optimization process is complicated and our proposed method is used the Pareto front generation technique. Moreover, our proposed method, models the objectives comprehensively to consider their dependency. Several experiments are performed to demonstrate the performance and capability of the proposed method in joint optimization of the parameters and extracting the proper solution set. Compared to the previous research, our proposed method outperforms them in optimizing the considered design parameters and its results is 19% better averagely than an efficient studied heuristic method.
[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.