A Task Scheduling and Mapping Approach to Enhance the Main Design Challenges of Multiprocessor Systems on Chip
Subject Areas : electrical and computer engineering1 , حمیدرضا زرندی 2 * , 3
1 -
2 - Amirkabir Univ of Tech
3 -
Keywords: Multiprocessor systemsschedulingreliability, power consumptiontemperaturemulti-objective optimizationPareto front,
Abstract :
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.