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

Erakutsi afiliazioak +
Aldizkaria:
Revista iberoamericana de automática e informática industrial ( RIAI )

ISSN: 1697-7920

Argitalpen urtea: 2013

Alea: 10

Zenbakia: 3

Orrialdeak: 344-355

Mota: Artikulua

DOI: 10.1016/J.RIAI.2013.05.006 DIALNET GOOGLE SCHOLAR lock_openSarbide irekia editor

Beste argitalpen batzuk: Revista iberoamericana de automática e informática industrial ( RIAI )

Laburpena

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.

Erreferentzia bibliografikoak

  • 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.
Datuen iturria: Dialnet