Exploration of Heterogeneous Resources in Embedded Systems

Aissam Berrahou; Nassim Sefrioui; Ouafaa Diouri; Mohsine Eleuldj

doi:10.15866/irecos.v9i9.3160

Exploration of Heterogeneous Resources in Embedded Systems

Aissam Berrahou^(1*), Nassim Sefrioui⁽²⁾, Ouafaa Diouri⁽³⁾, Mohsine Eleuldj⁽⁴⁾

^(*) Corresponding author

Authors' affiliations

DOI: https://doi.org/10.15866/irecos.v9i9.3160

Abstract

In this article we will address the multi-objective exploration problem of heterogeneous resources in embedded systems. The solution searched is to minimize the cost of execution and communication based on the following constraints: tasks with precedence constraints, deterministic scheduling (the execution time of each task is known), communication model, distributed platform with uniform cores, load balancing, size of memories associated... For this, we used linear programming with boolean variables communally know by BIP (Binary Integer Programming) as a method of multi-objective optimization to find the optimal solutions. The choice of such a method is motivated by the fact that it allows the realization of solutions called high-performance Pareto. Although this problem is NP-complete, this method provides optimal solutions in reasonable computation time. It determines in a single execution an optimal solution and this even if the problems are not convex.
Copyright © 2014 Praise Worthy Prize - All rights reserved.

Keywords

Multi-Objective Optimization; Embedded System; Mapping; Scheduling; Accurate Method; Binary Integer Programming

Full Text:

PDF

References

Rose, A.V.V., Ramachandran, R.S., Genetic algorithm based optimization of vertical links for efficient 3D NoC multicore crypto processor, (2013) International Review on Computers and Software (IRECOS), 8 (5), pp. 1082-1090.

Aditya, H., Ravishankar, K., Kunal, T., Udi, W., Minimum makespan scheduling with low rank processing times, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms(Page: 937 Year of Publication: 2013 ISBN: 978-1-611972-51-1).
http://dx.doi.org/10.1137/1.9781611973105.67

Akturk, I., ILP-Based Communication Reduction for Heterogeneous 3D Network-on-Chips, 21st Euromicro International Conference on Parallel, Distributed and Network-Based Processing (Page: 514 Year of Publication: 2013 ISBN 978-1-4673-5321-2).
http://dx.doi.org/10.1109/pdp.2013.83

Berrahou, A. Raji, Y., Rafi.M, Eleuldj, M., Framework For Mixed Systems, 21th International Conference on Microelectronics (Page: 336 Year of Publication: 2009 ISBN 978-142445816-5).
http://dx.doi.org/10.1109/icm.2009.5418616

Berrahou, A., Sefrioui, N., Diouri, O., Eleuldj, M., CoMMix Profile for Modeling and Analysis Embedded Systems, The 4th International Conference on Multimedia Computing and Systems(Page: 336 Year of Publication: 2014 ISBN 978-142445816-5).
http://dx.doi.org/10.1109/icmcs.2014.6911357

Chien-chung, S., Wen-hsiang, T., A Graph Matching Approach to Optimal Task Assignment in Distributed Computing Systems Using Minimax Criterion, IEEE Transactions on Computers, (Page: 34 Year of Publication: 1985 ISSN 0018-9340).
http://dx.doi.org/10.1109/tc.1985.1676563

Chinneck, J. W.. Practical optimization: A gentle introduction, ,2004. http://www.sce.carleton.ca/faculty/chinneck/po/Chapter13.pdf.

E. Ilavarasan, P. Thambidurai, Genetic Algorithm for Task Scheduling on Distributed Heterogeneous Computing System, (2006) International Review on Computers and Software (IRECOS), 1 (3), pp. 233-242.
http://dx.doi.org/10.1109/ispdc.2005.39

F. Rammig, M. Ditze, P. Janacik, T. Heimfarth, T. Kerstan, S. Oberthuer, K. Stahl, Basic concepts of real time operating Systems, W. Ecker, W. Müller and R. Dömer (Ed.), Hardware-Dependent Software, 2 (Netherlands: Springer; 2009, 15-45).
http://dx.doi.org/10.1007/978-1-4020-9436-1_2

Gao, C., Liu, J. W. S., Railey, M., Load Balancing Algorithms in Homogeneous Distributed Systems, International Conference on Parallel Processing (Page: 302 Year of Publication: 1984).

J.Fournier, Theorie des graphes et applications: Avec exercices et problèmes (Hermes Science Publications).

Gurobi solver, http://www.gurobi.com

Marshall, L., Fisher, The Lagrangian Relaxation Method for Solving Integer Programming Problems, Management Science, Vol. 50, n. 12, pp. 1861-1871, 2004.
http://dx.doi.org/10.1287/mnsc.1040.0263

Perng-Yi, R., Edward Y. S. Lee, Masahiro, T., A Task Allocation Model for Distributed Computing Systems, IEEE Transactions on Computers (Page: 41 Year of Publication: 1984 ISSN 0018-9340).

Price C.C., Salama M. A. Scheduling of Precedence-Constrained Tasks on Multiprocessors, The Computer Journal, Vol. 33, n.3, pp. 219-229, 1990.
http://dx.doi.org/10.1093/comjnl/33.3.219

Rafael, A., Luis, L., Sharing Jobs among Independently Owned Processors, In Proceedings of the 8th International Conference Systems (Page: 282 Year of Publication: 1988).
http://dx.doi.org/10.1109/dcs.1988.12528

Stuart, J., Artificial Intelligence: A Modern Approach (Prentice Hall/Pearson 2010).
http://dx.doi.org/10.1017/s0269888900007724

Stone, H. ,Multiprocessor Scheduling with the aid of Network Flow Algorithms, IEEE Transactions on Software Engineering, Vol. 3, n.1, pp.85-93, 1977.
http://dx.doi.org/10.1109/tse.1977.233840

Refbacks

» —

Username
Password
Remember me