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

  1. Ekain Azketa 1
  2. J. Javier Gutiérrez 2
  3. Marco Di Natale 3
  4. Luís Almeida 4
  5. Marga Marcos 5
  1. 1 IK4-Ikerlan Centro de Investigaciones Tecnológicas
  2. 2 Universidad de Cantabria
    info

    Universidad de Cantabria

    Santander, España

    ROR https://ror.org/046ffzj20

  3. 3 Sant'Anna School of Advanced Studies
    info

    Sant'Anna School of Advanced Studies

    Pisa, Italia

    ROR https://ror.org/025602r80

  4. 4 Universidade Do Porto
    info

    Universidade Do Porto

    Oporto, Portugal

    ROR https://ror.org/043pwc612

  5. 5 Universidad del País Vasco/Euskal Herriko Unibertsitatea
    info

    Universidad del País Vasco/Euskal Herriko Unibertsitatea

    Lejona, España

    ROR https://ror.org/000xsnr85

Mostrar afiliaciones +
Revista:
Revista iberoamericana de automática e informática industrial ( RIAI )

ISSN: 1697-7920

Año de publicación: 2013

Volumen: 10

Número: 3

Páginas: 344-355

Tipo: Artículo

DOI: 10.1016/J.RIAI.2013.05.006 DIALNET GOOGLE SCHOLAR lock_openAcceso abierto editor

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.
Fuente de los datos: Dialnet