Document Type : Original Article
Authors
Department of Computer Engineering, Amirkabir University of Technology
Abstract
In this paper, a task scheduling and mapping method based on multi-objective particle swarm optimization (MOPSO) algorithm is presented to improve lifetime reliability of multiprocessors systems on chip. This method considers power consumption temperature and performance along with the lifetime reliability due to the antagonistic relations of these parameters. These antagonistic and dependent relations make the design space exploration and optimization processes complex. The proposed method is based on MOPSO algorithm and starts with an initial population of candidate solutions which are generated randomly and represents valid task scheduling and mapping solutions. By changing the scheduling and mapping parameters during the MOPSO algorithm, new solutions are produced and the design space is explored based on the objective of the target problem of this method. Several experiments on random and real-life benchmarks are performed to verify the effectiveness of our proposed method. The results demonstrate the capability of the proposed method in effective design space exploration and generating the Pareto front. Moreover, comparisons to the related research show 35%, 23%, 19% and 3% improvements in performance, lifetime reliability, temperature, and power consumption on average.
Keywords
- Multiprocessor embedded systems# Lifetime# Power consumption# Task scheduling and mapping# Multi
- objective optimization# Particle swarm optimization
Main Subjects
- Wolf, W., Jerraya, A., Martin, J. “Multiprocessor system-on-chip (MPSoC) technology,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 27(10), 2008.
- Ahmed, J., et al., Fuzzy Logic Based Power-Efficient Real-Time Multi-Core System, Springer, 2017.
- Abdallah, A.B., Advanced Multicore Systems-On-Chip. Springer, 2017.
- Wolf, W. "The future of multiprocessor systems-on-chips,” Design Automation Conference, 2004.
- Ferrandi, F., et al., “Ant colony heuristic for mapping and scheduling tasks and communications on heterogeneous embedded systems”, IEEE Transactions on Computer-Aided Design, 29(6), 2010.
- Scheffer, L., Lavagno, L., Martin, G. EDA for IC system design, verification, and testing, CRC press, 2016.
- Das, A., Kumar, A., Veeravalli, B., A Survey of Lifetime Reliability-Aware System-Level Design Techniques for Embedded Multiprocessor Systems. National University of Singapore, 2014.
- Lee, E.A., Seshia, S.A. Introduction to embedded systems: A cyber-physical systems approach. MIT, 2016.
- Ammar, M., Baklouti, M., Abid, M., “The Performance-Energy Tradeoff in Embedded Systems Design: A Survey of Existing Design Space Exploration Tools and Trends”. International Journal of Computer Science and Information Security, 14(5), 2016.
- Silberschatz, A., Galvin, P.B., Gagne, G. Operating System Concepts Essentials. Wiley, 2016.
- Singh, A.K., et al. “Mapping on multi/many-core systems: survey of current and emerging trends”. Design Automation Conference, 2013.
- Das, A., et al. “Combined DVFS and mapping exploration for lifetime and soft-error susceptibility improvement in MPSoCs”. Design, Automation and Test in Europe Conference, 2014.
- Ma, Y., et al., “Improving System-Level Lifetime Reliability of Multicore Soft Real-Time Systems”. IEEE Transactions on VLSI Systems, 25(6), 2017.
- Das, A., Kumar, A., Veeravalli, B., “Reliability and energy-aware mapping and scheduling of multimedia applications on multiprocessors”. IEEE Transactions on Parallel and Distributed Systems, 27(3), 2016.
- Zhou, J., et al., “Thermal-aware task scheduling for energy minimization in heterogeneous real-time mpsocs”. IEEE Transactions on Computer-Aided, 35(8), 2016.
- Akbari, M., et al., “An enhanced genetic algorithm with new operators for task scheduling in heterogeneous computing systems,” Engineering Applications of Artificial Intelligence, 61(1), 2017.
- Coello, C., et al., “Handling multiple objectives with particle swarm optimization,” IEEE Transactions on evolutionary computation, 8(1), 2004.
- Wolf, M., High-performance embedded computing: applications in cyber-physical systems and mobile computing, Newnes, 2014.
- Nomura, K., Takashima, Y., Nakamura, Y., “PEVaS: Power and execution-time variation-aware scheduling for MPSoC,” New Circuits and Systems Conference, 2016.
- Ammar, M., et al., “On exploiting energy-aware scheduling algorithms for mode-based design space exploration of mpsoc,” Parallel, Distributed, and Network-Based Conference, 2016.
- Ananthana, G., Sarangi, S., Balakrishnan, M., “Leakage power aware task assignment algorithms for multicore platforms,” VLSI Symposium, 2016.
- Huang, L., Yuan, F., Xu, Q., “Lifetime reliability-aware task allocation for MPSoC platforms,” Design, Automation and Test in Europe Conference, 2009.
- Rathore, V., Chaturvedi, V., Srikanthan, T., “Performance constraint-aware task mapping to optimize lifetime reliability of many-core systems,” Great Lakes Symposium on VLSI, 2016.
- Huang, L., Xu, Q., “Energy-efficient task allocation and scheduling for multi-mode MPSoCs under lifetime reliability constraint,” Design, automation and test in Europe Conference, 2010.
- Sheikh, H., Ahmad, I., “Sixteen heuristics for joint optimization of performance, energy, and temperature in allocating tasks to multi-cores”, ACM Transactions on Parallel Computing, 3 (2), 2016.
- Abdi, A., Zarandi. H., “HYSTERY: a hybrid scheduling and mapping approach to optimize temperature, energy and lifetime of heterogeneous multiprocessor systems,” The Journal of Supercomputing, 74(5), 2018.
- Omara, F., Arafa, M., “Genetic algorithms for task scheduling problem,” Foundations of Computational Intelligence, 3(1), 2009.
- Majd, A., et al., “Nomes: Near-optimal metaheuristic scheduling for mpsocs,” Computer Architecture and Digital Systems Conference, 2017
- Pilato, C., Design Methodologies for Improving Embedded Systems with Hardware Politecnico Di Milano, 2011.
- Lienig, J., Bruemmer, H., Fundamentals of Electronic Systems Design, Springer, 2017.
- Srinivasan, J., et al. “The case for lifetime reliability-aware microprocessors,” ACM SIGARCH Computer Architecture News, 2004.
- Failure Mechanisms and Models for Semiconductor Devices, JEP 122H, 2016.
- Sathyakam, P., Mallick, P., “Towards realisation of mixed carbon nanotube bundles as VLSI interconnects: A review,” Nano Communication Networks, 3(3), 2012.
- Srinivasan, J., et al., “Lifetime reliability: Toward an architectural solution,” IEEE Micro, 25(3), 2005.
- Franco, J., Kaczer, B., Groeseneken, G., Reliability of high mobility SiGe channel MOSFETs for future CMOS applications, Springer, 2014.
- Zhu, D., Melhem, R., Mossé, D. “The effects of energy management on reliability in real-time embedded systems”, Computer Aided Design Conference, 2004.
- Kumar, P.,Thiele, L. “Thermally optimal stop-go scheduling of tasks with real-time constraints,” Asia and South Pacific Design Automation Conference, 2011.
- Liu, Y., et al. “Accurate temperature-dependent integrated circuit leakage power estimation is easy”, Design, automation and test in Europe Conference, 2007.
- Shah, R., Bell, K., handbook of thermal engineering, CRC Press Boca Raton, 2000.
- Embedded system synthesis benchmark suite (e3s), May 2019, http://ziyang.eecs.umich.edu/dickrp/e3s/.
- Rhodes, R. Dick, K. Vallerio, Task graphs for free, May 2019, http://ziyang.eecs.umich.edu/ dickrp/tgff.
- Zitzler, M. Laumanns, and L. Thiele, “SPEA2: Improving the strength Pareto evolutionary algorithm for multiobjective optimization,” in International Conference on Parallel Problem Solving from Nature, 2004.
)