Offre de stage M2/Ingénieur : Simulation parallèle optimiste

Infos pratiques

Objectif

Évaluation, comparaison et perfectionnement d'outils de simulation parallèle optimiste

Description

Les grandes infrastructures (réseau sans fil, calcul hautes performances, cloud, smart grids, ...), délicates à modéliser en raison d’un grand nombre de paramètres et de leur caractère stochastique, sont optimisées grâce à des simulations préalables avant leur mise en oeuvre en vraie grandeur. Or, ces simulations sont coûteuses en temps de calcul, il est donc naturel de les paralléliser.

Plusieurs simulateurs parallèles existent, reposant sur des approches différentes, parfois encore au stade expérimental. La simulation parallèle optimiste consiste à permettre à certains processeurs de calculer un fragment de trajectoire même si ce dernier n’est pas forcément valide dans la trajectoire finale, afin d’économiser les temps de synchronisation.

Cependant, il est aujourd’hui difficile de savoir si la simulation parallèle permet réellement de gagner du temps, car les principaux simulateurs parallèles actuels ont été validés séparément sur des modèles et plate-formes différents. Ces conditions expérimentales étant difficilement reproductibles, la mission principale du stage sera de tester et comparer ces simulateurs dans des conditions identiques. L’objectif de cette expérimentation est de déterminer si ces approches optimistes permettent de gagner en efficacité, par comparaison avec une simple réplication de simulation séquentielle.

Selon les résultats obtenus, des améliorations de ces algorithmes parallèles pourront être proposées et testées.

Travail attendu

  1. Familiarisation avec la simulation parallèle et prise en main des outils logiciels (e.g. ROSS, PSI).
  2. Élaboration d’un benchmark commun : modèle de réseau et modèle d’application
  3. Comparaison expérimentale et analyse des outils logiciels existants
  4. Exploration de différentes pistes d’amélioration algorithmique

Bibliographie

  1. Chandy, K. M., & Misra, J. (1979). Distributed simulation: A case study in design and verification of distributed programs. IEEE Transactions on software engineering, (5), 440-452.
  2. Cope, J., Liu, N., Lang, S., Carns, P., Carothers, C., & Ross, R. (2011, June). Codes: Enabling co-design of multilayer exascale storage architectures. In Proceedings of the Workshop on Emerging Supercomputing Technologies (Vol. 2011).
  3. Fujimoto, R. M. (2000). Parallel and distributed simulation systems (Vol. 300). New York: Wiley.
    4. Fujimoto, R. (2015, December). Parallel and distributed simulation. In Proceedings of the 2015 Winter Simulation Conference (pp. 45-59). IEEE Press.
  4. Jefferson, D., Beckman, B., Wieland, F., Blume, L., & DiLoreto, M. (1987). Time warp operating system (Vol. 21, No. 5, pp. 77-93). ACM.
  5. Mubarak, M., Carothers, C. D., Ross, R., & Carns, P. (2012, November). Modeling a million-node dragonfly network using massively parallel discrete-event simulation. In High Performance Computing, Networking, Storage and Analysis (SCC), 2012 SC Companion: (pp. 366-376). IEEE.
  6. Nicol, D., Greenberg, A. and Lubachevsky, B. (1994). Massively Parallel Algorithms for Trace-Driven Cache Simulations, IEEE Trans. Parallel Distrib. Syst. 5(8), 1994, pp. 849-859.
  7. Thi, T. H. D., Fourneau, J. M., & Quessette, F. (2014, June). Time-Parallel Simulation for Stochastic Automata Networks and Stochastic Process Algebra. In International Conference on Analytical and Stochastic Modeling Techniques and Applications (pp. 140-154). Springer International Publishing.