Algoritmo genético permutacional para el despliegue y la planificación de sistemas de tiempo real distribuidos
- Ekain Azketa 1
- J. Javier Gutiérrez 2
- Marco Di Natale 3
- Luís Almeida 4
- Marga Marcos 5
- 1 IK4-Ikerlan Centro de Investigaciones Tecnológicas
-
2
Universidad de Cantabria
info
-
3
Sant'Anna School of Advanced Studies
info
-
4
Universidade Do Porto
info
-
5
Universidad del País Vasco/Euskal Herriko Unibertsitatea
info
Universidad del País Vasco/Euskal Herriko Unibertsitatea
Lejona, España
ISSN: 1697-7920
Año de publicación: 2013
Volumen: 10
Número: 3
Páginas: 344-355
Tipo: Artículo
Otras publicaciones en: Revista iberoamericana de automática e informática industrial ( RIAI )
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.
Referencias bibliográficas
- 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., Gutiérrez, J., 2011a. Permutational 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., Gutiérrez, 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.