Chemical Reaction Optimization for Task Mapping in Heterogeneous Embedded Multiprocessor Systems

Abstract:

With different task mapping and scheduling will lead to different time consumption and energy consumption on heterogeneous multiprocessor systems, using appropriate task mapping and scheduling algorithms can save more energy. In this paper, we propose a new method to solve the task mapping problem. The algorithm consists of two elements: An intelligent approach to assign the execution orders of tasks by task level, and an allocation algorithm based on chemical-reaction-inspired metaheuristic called Chemical Reaction Optimization (CRO) to map processors to tasks. The results show that it can use less time to reduce more energy consumption.

• Periodical: Advanced Materials Research (Volumes 712-715)
• Pages: 2604-2610
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.712-715.2604
• Online since: June 2013
• Authors: Cheng Xu, Tao Li
• Keywords: Chemical Reaction Optimization, DAG, Energy-Aware Scheduling, Heterogeneous Multiprocessor, Power Management, Task Mapping

References

[1] A.Lam and V.Li, Chemical-Reaction-Inspired Metaheuristic for Optimization, Evolutionary Computation, IEEE Transactions on, 14(3):381-399, june 2010.

DOI: 10.1109/tevc.2009.2033580

[2] B.Gorjiara, N.Bagherzadeh and P.Chou, Ultra-Fast and Efficient Algorithm for Energy Optimization by Gradient-Based Stochastic Voltage and Task Scheduling, ACM Trans. Design Automation of Electronic system, vol.12, Article 39, no.4, Sept.2007.

DOI: 10.1145/1278349.1278352

[3] A.Andrei, M.T. Schmitz, P.Eles, Z.Peng and B.M.Al-Hashimi, Overhead-Conscious Voltage Selection for Dynamic and Leakage Energy Reduction of Time-Constrainted systems, IEEE Proc.-Computers and Digital Techniques, vol.152, no.1, pp.28-38, Jan.2005.

DOI: 10.1049/ip-cdt:20045055

[4] B.Gorjiara, N.Bagherzadeh and P.Chou, An Efficient Voltage Scaling Algorithm for Complex SoCs with Few Number of Voltage Modes, Proc. Int'l Symp. Low Power Electronic and Design(ISLPES'04), pp.381-386,2004.

DOI: 10.1145/1013235.1013326

[5] A.Lam and V.Li, Chemical Reaction Optimization for Cognitive Radio Spectrum Allocation, In GLOBECOM 2010, 2010 IEEE Global Telecommunications Conference, pages 1-5, dec.2010.

DOI: 10.1109/glocom.2010.5684065

[6] J.Sun, Y.Wang, J.Li and K.Gao, Hybrid Algorithm based on Chemical Reaction Optimization and Lin-kernighan Local Search for the Traveling Salesman Problem, In Natural Computation(ICNC), 2011 Seventh International Conference on, volume 3,pages 1518-1521, July 2011.

DOI: 10.1109/icnc.2011.6022378

[7] R.Mishra, N.Rastogi, D.Mosse and R.G. Melhem, Energy Aware Scheduling for Distributed Real-time Systems, Proc.17th Int'l Parallel and Distributed Systems(IPDPS'03), Apr.2003.

DOI: 10.1109/ipdps.2003.1213099

[8] D.Zhu, N.AbouGhazaleh, D.Mosse and R.G. Melhem, Power Aware Scheduling for AND/OR Graphs in Multi-Processor Real-Time Systems, Proc.31th Int'l Conf. Parallel Processing(ICPP'02), pp.593-601, Aug.2002.

DOI: 10.1109/icpp.2002.1040917

[9] Y.Zhang, X.Hu and D.Z. Chen, Task Scheduling and Voltage Selection for Energy Minimization, Proc.39th Design Automation Conf.(DAC'02), pp.183-188, June 2002.

DOI: 10.1145/513918.513966

[10] J.Xu, A.Lam and V.Li, Chemical reaction optimization for task scheduling in grid computing, Parallel and Distributed Systems, IEEE Transactions on, 22(10):1624-1631, Oct.2011.

DOI: 10.1109/tpds.2011.35

[11] Kenli Li,Zhimin Zhang and Yuming Xu, Chemical Reaction Optimization for Heterogeneous Computing Environments. Proc.10th Parallel and Distributed Processing with Applications(ISPA'12), pp.17-23, July 2012.

DOI: 10.1109/ispa.2012.11

[12] M.T. Schmitz , B.M. Al-hashimi and P.Eles, Energy-Efficient Mapping and Scheduling for DVS Enabled Distributed Embedded Systems, Proc. Design, Automation and Test in Europe Conf. and Exposition (DATE'02), pp.514-521, Mar.2002.

DOI: 10.1109/date.2002.998349

[13] A.P. Chandrakasan, S.Sheng and R.W. Brodersen, Low-Power CMOS Digital Design, IEEE J.Solid-State Circuits, vol.27, no.4, pp.473-484, Apr.1992.

DOI: 10.1109/4.126534

[14] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman,1979.

[15] L.K. Goh, B.Veeravalli and S.Viswanathan, Design of Fast and Efficient Energy-Aware Gradient-Based Scheduling Algorithms for Heterogeneous Embedded Multiprocessor Systems, Parallel and Distributed Systems, IEEE Transactions on, 20(1):1-12, Jan.2009.

DOI: 10.1109/tpds.2008.55