A Task Mapping and Scheduling Algorithm based on Genetic Algorithm for Embedded System Design
Subject Areas :mohadese nikseresht 1 , Mohsen Raji 2 *
1 - University student
2 - Shiraz University
Keywords: Embedded Systems, Task Scheduling, Multi-Objective optimization, Genetic Algorithm,
Abstract :
Embedded system designers face numerous design requirements and objectives (such as runtime, power consumption and reliability). Since meeting one of these requirements mostly contradicts other design requirements, it seem to be inevitable to apply multi-objective approaches in various stages of designing embedded systems, including task scheduling step. In this paper, a multi-objective task mapping and scheduling in the design stage of the embedded system is presented. In this method, tasks are represented by task graphs assuming that the hardware architecture platform is given and determined. In order to manage the dependencies between tasks in the task graph, a segmentation method is used, in which the tasks that can be executed simultaneously are specified in a segment and is considered in the scheduling process. In the proposed method, the task mapping and scheduling problem is modeled as a genetic algorithm-based multi-objective optimization problem considering execution time, energy consumption, and reliability. In comparison to similar previous works, the proposed scheduling method respectively provides 21.4%, 19.2%, and 20% improvement in execution time, energy consumption, and reliability. Applying a multi-objective helps the designer to pick out the best outcome according to different considerations.
Salimi, Maghsood, et al. "Multi-objective Optimization of Real-Time Task Scheduling Problem for Distributed Environments." Proceedings of the 6th Conference on the Engineering of Computer Based Systems. ACM, 2019.
J. Balcarek, P. Fiser, and J. Schmidt, “Test patterns compression technique based on a dedicated SAT-based ATPG,” In Digital System Design: Architectures, Methods and Tools (DSD) 13th Euromicro Conference, pp. 805-808, 2009
Majd, Amin, et al. "NOMeS: Near-optimal metaheuristic scheduling for MPSoCs." 2017 19th International Symposium on Computer Architecture and Digital Systems (CADS). IEEE, 2017.
A. Czutro, I. Polian, M. Lewis, P. Engelke, S. Reddy and B. Becker, “Thread parallel integrated test pattern generator utilizing satisfiability analysis,” Int J Parallel Progr, pp. 185-202, 2012.
H. Marijn , M. Järvisalo and A. Biere, “Efficient CNF simplification based on binary implication graphs,” International Conference on Theory and Applications of Satisfiability Testing, pp. 201-215, 2011.
P. Jackson and D. Sheridan, “Clause form conversions for boolean circuits,” International Conference on Theory and Applications of Satisfiability Testing, Berlin Heidelberg, 2004.
Salimi, Maghsood, et al. "Multi-objective Optimization of Real-Time Task Scheduling Problem for Distributed Environments." Proceedings of the 6th Conference on the Engineering of Computer Based Systems. ACM, 2019.
Majd, Amin, et al. "NOMeS: Near-optimal metaheuristic scheduling for MPSoCs." 2017 19th International Symposium on Computer Architecture and Digital Systems (CADS). IEEE, 2017.
Topcuoglu, S. Hariri and Min-You Wu, "Performance-effective and low-complexity task scheduling for heterogeneous computing", IEEE Transactions on Parallel and Distributed Systems, vol. 13, no. 3, pp. 260-274, 2002.
G. Tseitin, On the complexity of derivation in propositional calculus, Berlin Heidelberg: Springer , 1983.
L. T, “Test pattern generation using boolean satisfiability,” IEEE Transactions on Computer-Aided Design, pp. 4-15, 1992.
Z. Wang and T. Fang, "Task Scheduling Model Based on Multi-Agent and Multi-Objective Static Scheduling Algorithm", Journal of Networks, vol. 9, no. 6, 2014. Available: 10.4304/jnw.9.6.1588-1595
L. Zhou, "Integrated Multi-objective Scheduling for Multi-task on Perishable Products", Journal of Information and Computational Science, vol. 12, no. 18, pp. 6653-6664, 2015.
M. Davis and H. Putnam, “A computing procedure for quantification theory,” Journal of the ACM (JACM), Vol. 7, No. 3, pp. 201-215, 1960.
S. Eggersglüß and R. Drechsler, High Quality Test Pattern Generation and Boolean Satisfiability, Berlin: Springer Science & Business Media, 2012.
Akbari, M., Rashidi, H. and Alizadeh, S. (2017). An enhanced genetic algorithm with new operators for task scheduling in heterogeneous computing systems. Engineering Applications of Artificial Intelligence, 61, pp.35-46.
P. Beame, H. Kautz and A. Sabharwal, “Towards understanding and harnessing the potential of clause learning,” Journal of Artificial Intelligence Research, Vol. 22, N0. 1, pp. 319-351, 2004.
W. Lin and X. Jin, "Toward The Flexible Operation Of Integrated Community Energy System: A Two-Stage Multi-Objective Scheduling Method", Science Trends, 2018.
J. Sanders and E. Kandrot, CUDA by example: an introduction to general-purpose GPU programming, Addison-Wesley Professional, 2010.
S. AlEbrahim and I. Ahmad, "Task scheduling for heterogeneous computing systems", The Journal of Supercomputing, vol. 73, no. 6, pp. 2313-2338, 2016. Available: 10.1007/s11227-016-1917-2.
S. Parikh, S. Shah, N. M Patel, "Multi-objective Prediction based Task Scheduling Method in Cloud Computing", International Journal of Recent Technology and Engineering, vol. 8, no. 4, pp. 9388-9394, 2019. Available: 10.35940/ijrte.d9702.118419.
M. Bushnell, V. Agrawal, Essentials of electronic testing for digital,memory and mixed-signal VLSI circuits, Boston, USA: Kluwer, 2000.
K. Deb, S. Agrawal, A. Pratap, and T. Meyarivan, “A fast and elitist multiojective genetic algorithm: NSGA-II,”IEEE Trans. On Evolutionary Computation, 2002.
M. C. Hansen, H. Yalcin and J. P. Hayes,“Unveiling the ISCAS-85 benchmarks: A case study in reverse engineering,” IEEE Design & Test , Vol. 16, No. 3, pp. 72-80, 1999.
G. E. Moore, “Cramming more components onto integrated circuits," IEEE Solid-State Circuits Newsletter, 1996.
I. Meedeniya, A. Aleti, and L. Grunske, “Architecture-driven reliability optimization with uncertain model parameters”, J.of Systems and Software, 2012.