Algoritmo genético permutacional para el despliegue y la planificación de sistemas de tiempo real distribuidos

Ekain Azketa, J. Javier Gutiérrez, Marco Di Natale, Luís Almeida, Marga Marcos

Resumen

El despliegue y la planificación de tareas y mensajes en sistemas de tiempo real distribuidos son problemas NP-difíciles (NP- hard), por lo que no existen métodos óptimos para solucionarlos en tiempo polinómico. En consecuencia, estos problemas son adecuados para abordarse mediante algoritmos genéricos de búsqueda y optimización. En este artículo se propone un algoritmo genético multiobjetivo basado en una codificación permutacional de las soluciones para abordar el despliegue y la planificación de sistemas de tiempo real distribuidos. Además de desplegar tareas en computadores y de planificar tareas y mensajes, este algoritmo puede minimizar el número de computadores utilizados, la cantidad de recursos computacionales y de comunicaciones empleados y el tiempo de respuesta de peor caso medio de las aplicaciones. Los resultados experimentales muestran que este algoritmo genético permutacional puede desplegar y planificar sistemas de tiempo real distribuidos de forma satisfactoria y en tiempos razonables.

Palabras clave

Sistemas de tiempo real; Algoritmos de planificación; Algoritmos genéticos; Optimizaciones multiobjetivo

Texto completo:

PDF

Referencias

Achterberg, T., 2009. SCIP: Solving Constraint Integer Programs. Mathematical Programming Computation 1 (1), 1–41.

Azketa, E., Gutiérrez, J. J., Palencia, J. C., Harbour, M. G., Almeida, L., Marcos, M., 2012a. Schedulability analysis of multi-packet messages in segmented CAN. In: Proceedings of the 17th IEEE International Conference on Emerging Technologies and Factory Automation.

Azketa, E., Uribe, J., Marcos, M., Almeida, L., Gutierrez, J., 2011a. Permuta- ´ tional genetic algorithm for fixed priority scheduling of distributed real-time systems aided by network segmentation. In: Proceedings of the 1st Workshop on Synthesis and Optimization Methods for Real-time Embedded Systems. pp. 13–18.

Azketa, E., Uribe, J., Marcos, M., Almeida, L., Gutiérrez, J., 2011b. Permutational genetic algorithm for the optimized assignment of priorities to tasks and messages in distributed real-time systems. In: Proceedings of the 8th IEEE International Conference on Embedded Software and Systems. pp. 958–965.

Azketa, E., Uribe, J. P., Marcos, M., Almeida, L., Gutierrez, J. J., 2012b. An ´ empirical study of permutational genetic crossover and mutation operators on the fixed priority assignment in distributed real-time systems. In: Proceedings of the IEEE International Conference on Industrial Technology. pp. 598–605.

Boyd, S., Kim, S., Vandenberghe, L., Hassibi, A., 2007. A tutorial on geometric programming. Optimization and Engineering 8 (1), 67–127.

Chen, W., Lin, C., 2000. A hybrid heuristic to solve a task allocation problem. Computers & Operations Research 27 (3), 287–303.

Davare, A., Zhu, Q., Di Natale, M., Pinello, C., Kanajan, S., SangiovanniVincentelli, A., 2007. Period optimization for hard real-time distributed automotive systems. In: Proceedings of the 44th Annual Design Automation Conference. pp. 278–283.

Davis, L., 1991. Handbook of genetic algorithms. Arden Shakespeare.

Deb, K., Pratap, A., Agarwal, S., Meyarivan, T., 2002. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6 (2), 182–197.

Di Natale, M., Stankovic, J. A., 1995. Applicability of simulated annealing methods to real-time scheduling and jitter control. In: Proceedings of the 16th IEEE Real-Time Systems Symposium. pp. 190–199.

Di Natale, M., Zheng, W., Pinello, C., Giusto, P., Sangiovanni-Vincentelli, A., 2007. Optimizing end-to-end latencies by adaptation of the activation events in distributed automotive systems. In: Proceedings of the 13th IEEE Real Time and Embedded Technology and Applications Symposium. pp. 293– 302.

Dick, R., Jha, N., 2002. MOGAC: a multiobjective genetic algorithm for hardware-software cosynthesis of distributed embedded systems. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 17 (10), 920–935.

Garey, M., Johnson, D., Sethi, R., 1976. The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 117–129.

Glover, F., 1986. Future paths for integer programming and links to artificial intelligence. Computers & Operations Research 13 (5), 533–549.

Gutiérrez, J. J., Harbour, M. G., 1995. Optimized priority assignment for tasks and messages in distributed hard real-time systems. In: Proceedings of the 3rd Workshop on Parallel and Distributed Real-Time Systems. pp. 124–132.

Hamann, A., Jersak, M., Richter, K., Ernst, R., 2006. A framework for modular analysis and exploration of heterogeneous embedded systems. Real-Time Systems 33 (1), 101–137.

Hladik, P., Cambazard, H., Déplanche, A., Jussien, N., 2008. Solving a real- time allocation problem with constraint programming. Journal of Systems and Software 81 (1), 132–149.

Holland, J., 1975. Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor.

Kirkpatrick, S., 1984. Optimization by simulated annealing: Quantitative studies. Journal of Statistical Physics 34 (5), 975–986.

Metzner, A., Herde, C., 2006. RTSAT - An optimal and efficient approach to the task allocation problem in distributed architectures. In: Proceedings of the 27th IEEE Real-Time Systems Symposium. pp. 147–158.

Minoux, M., 1986. Mathematical programming: theory and algorithms. John Wiley & Sons.

Mitra, H., Ramanathan, P., 1993. A genetic approach for scheduling nonpreemptive tasks with precedence and deadline constraints. In: Proceedings of the Hawaii International Conference on System Sciences. Vol. 26. pp. 556–556.

Monnier, Y., Beauvais, J., Deplanche, A., 1998. A genetic algorithm for scheduling tasks in a real-time distributed system. In: Proceedings of the 24th Euromicro Conference. Vol. 2. pp. 708–714.

Palencia, J., Harbour, M., 1998. Schedulability analysis for tasks with static and dynamic offsets. In: Proceedings of the 19th IEEE Real-Time Systems Symposium. pp. 26–37.

Palencia, J. C., Harbour, M. G., 1999. Exploiting precedence relations in the schedulability analysis of distributed real-time systems. In: Proceedings of the 20th IEEE Real-Time Systems Symposium. pp. 328–339.

Pearl, J., 1984. Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley.

Pop, P., Eles, P., Peng, Z., 2002. Flexibility driven scheduling and mapping for distributed real-time systems. In: Proceedings of the 8th International Conference on Real-Time Computing Systems and Applications. pp. 337– 346.

Pop, P., Eles, P., Peng, Z., 2003a. Schedulability analysis and optimization for the synthesis of multi-cluster distributed embedded systems. In: Proceedings of the Conference on Design, Automation and Test in Europe. Vol. 1. pp. 184–189.

Pop, T., Eles, P., Peng, Z., 2003b. Design optimization of mixed time/eventtriggered distributed embedded systems. In: Proceedings of the 1st IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis. pp. 83–89.

Porto, S., Kitajima, J., Ribeiro, C., 2000. Performance evaluation of a parallel tabu search task scheduling algorithm. Parallel Computing 26 (1), 73–90.

Porto, S., Ribeiro, C., 1995. A tabu search approach to task scheduling on heterogeneous processors under precedence constraints. International Journal of High Speed Computing 7 (1), 45–71.

Samii, S., Yin, Y., Peng, Z., Eles, P., Zhang, Y., 2009. Immune genetic algorithms for optimization of task priorities and flexray frame identifiers. In: Proceedings of the 15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications. pp. 486–493.

Schrijver, A., 1998. Theory of linear and integer programming. John Wiley & Sons Inc.

Shang, L., Dick, R., Jha, N., 2007. SLOPES: Hardware-software cosynthesis of low-power real-time distributed embedded systems with dynamically reconfigurable FPGAs. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 26 (3), 508–526.

Tindell, K., Burns, A., Wellings, A., 1992. Allocating hard real-time tasks: an NP-hard problem made easy. Real-Time Systems 4 (2), 145–165.

Tindell, K., Clark, J., 1994. Holistic schedulability analysis for distributed hard real-time systems. Microprocessing and Microprogramming 40 (2-3), 117– 134.

Tsang, E., 1993. Foundations of constraint satisfaction. Vol. 289. Academic Press London.

Zheng, W., Zhu, Q., Di Natale, M., Sangiovanni-Vincentelli, A., 2007. Definition of task allocation and priority assignment in hard real-time distributed systems. In: Proceedings of the 28th IEEE Real-Time Systems Symposium. pp. 161–170.

Zhu, Q., Yang, Y., Scholte, E., Di Natale, M., Sangiovanni-Vincentelli, A., 2009. Optimizing extensibility in hard real-time distributed systems. In: Proceedings of the 15th IEEE Real-Time and Embedded Technology and Applications Symposium. pp. 275–284.

Abstract Views

786
Metrics Loading ...

Metrics powered by PLOS ALM


 

Citado por (artículos incluidos en Crossref)

This journal is a Crossref Cited-by Linking member. This list shows the references that citing the article automatically, if there are. For more information about the system please visit Crossref site

1. Control optimization of an aerial robotic swarm in a search task and its adaptation to different scenarios
Pablo Garcia-Aunon, Antonio Barrientos Cruz
Journal of Computational Science  vol: 29  primera página: 107  año: 2018  
doi: 10.1016/j.jocs.2018.10.004



Creative Commons License

Esta revista se publica bajo una Licencia Creative Commons Attribution-NonCommercial-CompartirIgual 4.0 International (CC BY-NC-SA 4.0)

Universitat Politècnica de València     https://doi.org/10.4995/riai

e-ISSN: 1697-7920     ISSN: 1697-7912