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

• Ekain Azketa ^[5] ; J. Javier Gutiérrez ^[1] ; Marco Di Natale ^[2] ; Luís Almeida ^[3] ; Marga Marcos ^[4]
  1. [1] Universidad de Cantabria

     Universidad de Cantabria

     Santander, España

     
  2. [2] Sant'Anna School of Advanced Studies

     Sant'Anna School of Advanced Studies

     Pisa, Italia

     
  3. [3] Universidade Do Porto

     Universidade Do Porto

     Santo Ildefonso, Portugal

     
  4. [4] Universidad del País Vasco/Euskal Herriko Unibertsitatea

     Universidad del País Vasco/Euskal Herriko Unibertsitatea

     Leioa, España

     
  5. [5] IK4-Ikerlan Centro de Investigaciones Tecnológicas

  Mostrar afiliaciones +
• Localización: Revista iberoamericana de automática e informática industrial ( RIAI ), ISSN-e 1697-7920, Vol. 10, Nº. 3, 2013, págs. 344-355
• Idioma: español
• DOI: 10.1016/j.riai.2013.05.006
• Títulos paralelos:
  • Permutational genetic algorithm for the deployment and scheduling of distributed real time systems
• Enlaces
  • Texto completo
• Resumen
  • español

    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.

  • English

    The deployment and scheduling of tasks and messages in distributed real-time systems are NP-hard problems, so there are no optimal methods to solve them in polynomial time. Consequently, these problems are suitable to be approached with generic search and optimisation algorithms. In this paper we propose a multi-objective genetic algorithm based on a permutational solution encoding for the deployment and scheduling of distributed real-time systems. Besides deploying and scheduling tasks and messages, the algorithm can minimize the number of the used computers, the utilization of computing and networking resources and the average worst-case response times of the applications. The experiments show that this genetic algorithm can successfully synthesize complex distributed real-time systems in reasonable times.

• 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...
  • Azketa, E., Uribe, J., Marcos, M., Almeida, L., Gutiérrez, J., 2011a. Permutational genetic algorithm for fixed priority scheduling of distributed...
  • Azketa, E., Uribe, J., Marcos, M., Almeida, L., Gutiérrez, J., 2011b. Permutational genetic algorithm for the optimized assignment of priorities...
  • Azketa, E., Uribe, J. P., Marcos, M., Almeida, L., Gutiérrez, J. J., 2012b. An empirical study of permutational genetic crossover and mutation...
  • 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...
  • 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...
  • Di Natale, M., Stankovic, J. A., 1995. Applicability of simulated annealing methods to real-time scheduling and jitter control. In: Proceedings...
  • Di Natale, M., Zheng, W., Pinello, C., Giusto, P., Sangiovanni-Vincentelli, A., 2007. Optimizing end-to-end latencies by adaptation of the...
  • Dick, R., Jha, N., 2002. MOGAC: a multiobjective genetic algorithm for hardware-software cosynthesis of distributed embedded systems. IEEE...
  • 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...
  • Hamann, A., Jersak, M., Richter, K., Ernst, R., 2006. A framework for modular analysis and exploration of heterogeneous embedded systems....
  • Hladik, P., Cambazard, H., Déplanche, A., Jussien, N., 2008. Solving a real- time allocation problem with constraint programming. Journal...
  • 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...
  • 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...
  • Monnier, Y., Beauvais, J., Deplanche, A., 1998. A genetic algorithm for scheduling tasks in a real-time distributed system. In: Proceedings...
  • Palencia, J., Harbour, M., 1998. Schedulability analysis for tasks with static and dynamic offsets. In: Proceedings of the 19th IEEE Real-Time...
  • Palencia, J. C., Harbour, M. G., 1999. Exploiting precedence relations in the schedulability analysis of distributed real-time systems. In:...
  • 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...
  • Pop, P., Eles, P., Peng, Z., 2003a. Schedulability analysis and optimization for the synthesis of multi-cluster distributed embedded systems....
  • Pop, T., Eles, P., Peng, Z., 2003b. Design optimization of mixed time/eventtriggered distributed embedded systems. In: Proceedings of the...
  • Porto, S., Kitajima, J., Ribeiro, C., 2000. Performance evaluation of a parallel tabu search task scheduling algorithm. Parallel Computing...
  • Porto, S., Ribeiro, C., 1995. A tabu search approach to task scheduling on heterogeneous processors under precedence constraints. International...
  • Samii, S., Yin, Y., Peng, Z., Eles, P., Zhang, Y., 2009. Immune genetic algorithms for optimization of task priorities and flexray frame identifiers....
  • 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...
  • 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...
  • 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...
  • Zhu, Q., Yang, Y., Scholte, E., Di Natale, M., Sangiovanni-Vincentelli, A., 2009. Optimizing extensibility in hard real-time distributed systems....