Thèse de doctorat de Fabien Gaud

THÈSE Pour obtenir le grade de DOCTEUR DE L’UNIVERSITÉ DE GRENOBLE Spécialité : Informatique Arrêté ministériel : 7 août 2006 Présentée et soutenue publiquement par Fabien GAUD le 02 Décembre 2010 ÉTUDE ET AMÉLIORATION DE LA PERFORMANCE DES SERVEURS DE DONNÉES POUR LES ARCHITECTURES MULTI-CŒURS Thèse dirigée par Jean-Bernard STEFANI et codirigée par Renaud LACHAIZE et Vivien QUÉMA JURY M. Pierre SENS Professeur, Université Paris 6 Président M. Pascal FELBER, Université de Neuchâtel Rapporteur M. Gilles GRIMAUD Professeur, Université de Lille M. MULLER Directeur de recherche, INRIA Examinateur M. Jean-Bernard STEFANI de M. Renaud LACHAIZE Maître de conférence, Université Joseph Fourier M. Vivien QUÉMA Chargé de recherche, CNRS Examinateur Thèse préparée au sein du Laboratoire d’Informatique de Grenoble, dans l’École Doctorale Mathématiques, Sciences et Technologies de l’Information, InformatiqueÀ ma famille À NatachaRemerciements Je tiens tout d’abord à remercier Pierre Sens, Professeur à l’Université Paris 6, de me faire l’hon- neur de présider ce jury. Je remercie également Pascal Felber, Professeur à l’Université de Neuchâtel, et Gilles Grimaud, Professeur à l’Université des Sciences et Technologies de Lille, d’avoir accepté d’être rapporteurs de cette thèse et d’avoir évalué mon travail de manière approfondie et constructive. Merci également à Gilles Muller, Directeur de recherche à l’INRIA d’avoir accepté d’être examinateur de ce travail et d’avoir participé à ces travaux. Je souhaite également remercier mes encadrants sans qui cette thèse n’aurait pas été possible. Tout d’abord, je remercie Jean-Bernard Stefani, Directeur de recherche à l’INRIA, de m’avoir permis de faire une thèse au sein de l’équipe Sardes et pour toute la liberté qu’il m’a laissée dans le choix de mes travaux. Je remercie également vigoureusement Renaud Lachaize, Maître de conférence à l’Université Joseph Fourier, et Vivien Quéma, Chargé de recherche au CNRS, pour m’avoir accepté en tant que stagiaire lors de mon Master puis en tant que doctorant. Je ne les remercierai jamais assez pour leur encadrement et pour leur disponibilité. Je tiens également à remercier les personnes suivantes sans qui ces trois années de thèse n’auraient pas été aussi intéressantes : mes amis et collègues du bureau B218 : Fabien, Baptiste et Sylvain qui ont grandement contri- bué à mes travaux et à ce que ces trois années se passent dans la bonne humeur. toute l’équipe Sardes pour m’avoir accueilli et pour la bonne ambiance qui y règne. Willy pour m’avoir accompagné pendant mes travaux de Master, de thèse et pendant les sémi- naires de l’équipe. tous les enseignants avec qui j’ai pu collaborer et notamment Pierre-Yves Gibello pour m’avoir permis de participer au projet Ecom, Pascal Sicard pour ces deux années très intéressantes et toute l’équipe d’Intergiciels et Bases de Données pour m’avoir confié les clés de la partie « Intergiciels », ce qui fut une expérience très enrichissante. tous mes amis, et notamment Julien, Walid, Dudu et Grunch, qui ont supporté mes humeurs et mes disponibilités changeantes. Enfin, je garde une pensée toute particulière pour toutes les personnes de ma famille, qui m’ont accompagné tout au long de mes études, et pour Natacha, qui a réussi à me supporter tout au long de mon parcours universitaire. iTable des matières Introduction 1 1 Émergence des processeurs multi-cœurs 5 1.1 Processeurs mono-cœur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.1 Principaux composants d’un processeur . . . . . . . . . . . . . . . . . . . . 6 1.1.2 Problèmes d’évolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.3 Vers des processeurs parallèles . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2 Processeurs SMT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.1 Fonctionnement d’une architecture SMT . . . . . . . . . . . . . . . . . . . 9 1.2.2 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3 Processeurs multi-cœurs à accès mémoire uniforme . . . . . . . . . . . . . . . . . . 10 1.3.1 Fonctionnement d’une architecture multi-cœurs à accès mémoire uniforme . 10 1.3.2 Mesures de performances . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3.3 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.4 Processeurs multi-cœurs à accès mémoire non uniforme . . . . . . . . . . . . . . . . 14 1.4.1 Fonctionnement d’une architecture multi-cœurs à accès mémoire non uniforme 15 1.4.2 Mesures de performances . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.4.3 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.5 Processeurs du futur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.5.1 Le projet Tera-scale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.5.2 Processeurs hétérogènes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.6 Bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2 Modèles de programmation pour les architectures multi-cœurs 23 2.1 Modèles de programmation classiques . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.1.1 Programmation à base de threads . . . . . . . . . . . . . . . . . . . . . . . 24 2.1.2 Améliorations du modèle de threads . . . . . . . . . . . . . . . . . . . . . . 27 2.1.3 événementielle . . . . . . . . . . . . . . . . . . . . . . . . 29 2.1.4 Amélioration du modèle d’événements . . . . . . . . . . . . . . . . . . . . 31 2.1.5 Approches visant à unifier les deux modèles . . . . . . . . . . . . . . . . . . 34 2.2 Nouveaux modèles de programmation multi-cœurs . . . . . . . . . . . . . . . . . . 35 2.2.1 Modèles de fork-join . . . . . . . . . . . . . . . . . . . . . 35 2.2.2 Programmation par étages . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.2.3 Files d’éléments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.2.4 MapReduce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.2.5 Grand central . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.3 Bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 iii3 Environnements d’exécution pour architectures multi-cœurs 41 3.1 Repenser les systèmes d’exploitation pour les architectures multi-cœurs . . . . . . . 41 3.1.1 Rôles principaux du système d’exploitation . . . . . . . . . . . . . . . . . . 42 3.1.2 Architecture des systèmes d’e . . . . . . . . . . . . . . . . . . . 44 3.1.3 Systèmes d’exploitations pour les architectures multi-cœurs . . . . . . . . . 46 3.2 Repenser l’exécution des tâches sur les . . . . . . . . . . . 51 3.2.1 Équilibrage de charge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.2.2 Affinités et compétition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.2.3 Allocation mémoire efficace . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.3 Bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4 Positionnement de la contribution 59 4.1 Contexte de laution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.2 Vol de tâches efficace pour les systèmes événementiels multi-cœurs . . . . . . . . . 60 4.3 Étude et amélioration des performances du serveur Web Apache sur les architectures multi-cœurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 5 Vol de tâches efficace pour les systèmes événementiels multi-cœurs 63 5.1 Description du support d’exécution Libasync-smp . . . . . . . . . . . . . . . . . . . 64 5.1.1 Programmation événementielle colorée . . . . . . . . . . . . . . . . . . . . 64 5.1.2 Architecture du support d’exécution Libasync-smp . . . . . . . . . . . . . . 67 5.1.3 Algorithme de vol de tâches . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.1.4 Évaluation des performances du vol de tâches . . . . . . . . . . . . . . . . . 71 5.2 Un nouvel algorithme de vol de tâches . . . . . . . . . . . . . . . . . . . . . . . . . 73 5.2.1 Vol de tâches sensible à la localité . . . . . . . . . . . . . . . . . . . . . . . 74 5.2.2 Vol de tâches avec analyse de la rentabilité . . . . . . . . . . . . . . . . . . 74 5.2.3 Vol de tâches avec pénalité . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 5.3 L’environnement d’exécution Mely . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5.3.1 Architecture de Mely . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5.3.2 Mise en œuvre du vol de tâches . . . . . . . . . . . . . . . . . . . . . . . . 78 5.3.3 Détails supplémentaires de mise en œuvre . . . . . . . . . . . . . . . . . . . 79 5.4 Évaluation du mécanisme de vol de tâches de Mely . . . . . . . . . . . . . . . . . . 82 5.4.1 Conditions expérimentales . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 5.4.2 Micro-tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 5.4.3 Serveurs de données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 6 Étude et amélioration des performances du serveur Web Apache sur une architecture multi-cœurs NUMA 93 6.1 État de l’art de l’évaluation des serveurs Web . . . . . . . . . . . . . . . . . . . . . 94 6.2 Mécanismes d’injection de charge . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 6.2.1 Caractéristiques des différents mécanismes d’injection de charge . . . . . . . 96 6.2.2 Charge et environnement d’injection employés . . . . . . . . . . . . . . . . 98 6.3 Présentation du serveur Web Apache . . . . . . . . . . . . . . . . . . . . . . . . . . 100 6.3.1 Modèle d’exécution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 6.3.2 Interaction/Intégration avec PHP . . . . . . . . . . . . . . . . . . . . .