Tri :
Date
Editeur
Auteur
Titre
|
|
Institut Supérieur de l'Aéronautique et de l'Espace
/ 29-11-2021
LAMOTHE François
Voir le résumé
Voir le résumé
Le problème de la transmission de ressources indivisibles au travers d'un réseau est un problème générique présent dans de nombreuses applications. En effet, ce type de problème se retrouve dans des industries telles que le transport de fret ou encore les télécommunications (réseaux optiques, communications satellitaires ...). L'amélioration des méthodes de résolution pour ce problème représente donc un enjeu important, en particulier dans l'application industrielle qui motive cette thèse : la constellation de satellites de télécommunication Telesat. En effet, cette industrie tend à construire des constellations contenant de plus en plus de satellites afin d'augmenter le débit internet que le système est capable de transmettre. En parallèle de l'augmentation du nombre de satellites, on constate aussi une augmentation du nombre d'utilisateurs de ces constellations. Celle ci s'explique à la fois par l'accroissement de la richesse de la population, l'essor de nouvelles applications telles que les accès internet dans les avions ou les bateaux mais aussi tout simplement par l'augmentation de la capacité et de la qualité des services de télécommunication par satellite. La combinaison de ces facteurs tend à créer des problèmes de transmission de ressources de plus en plus difficiles à résoudre ce qui nécessite des algorithmes de résolution plus performants.Dans cette thèse, nous nous intéressons au problème de transmission de la ressource indivisible qu'est le débit des utilisateurs dans une constellation. Ce problème correspond à un problème classiquement étudié dans la littérature des problèmes de flots, sous le nom de problème de flot insécable. Bien que ses propriétés théoriques soient bien connue et que de nombreuses approches de résolution existent, les méthodes de résolution proposées manquent d'efficacité lorsque la taille du problème est importante. Nous tentons de combler cette lacune en proposant des algorithmes présentant de bonnes performances sur de grandes instances de ce problème. D'autre part, l'introduction de la dynamique de la constellation dans le problème nous mène à nous intéresser au problème de flot insécable dynamique. Ce problème est peu étudié dans la littérature, c'est pourquoi nous étendons l'ensemble des méthodes de résolution testées sur ce problème en proposant différentes approches et en les comparant expérimentalement sur des jeux d'instances que nous proposons. Enfin, nous étudions des méthodes de décomposition permettant de renforcer la relaxation linéaire du problème flot insécable. En effet, cette relaxation linéaire est à la base de la plupart de méthode de résolution proposée dans la littérature. Le calcul d'une relaxation puissante est donc un enjeu de la résolution du problème de flot insécable. Après avoir présenté et réimplémenté deux méthodes de la littérature, nous proposons une nouvelle méthode de décomposition s'inspirant des deux méthodes précédentes. Une étude empirique montre que la nouvelle méthode proposée possède un avantage compétitif important sur les grandes instances du problème de flot insécable.
|
Texte intégral
|
|
Institut Supérieur de l'Aéronautique et de l'Espace
/ 31-03-2021
Sensfelder Nathanaël
Voir le résumé
Voir le résumé
L'objectif de cette thèse est d'offrir des outils d'aide à la certification aéronautique de processeurs COTS multi-cœurs. Ces architectures sont par nature parallèles et peuvent de ce fait largement améliorer les performances de calcul. Cependant elles souffrent d'un grand manque de prédictibilité, au sensoù calculer les pires d'exécution même pour des programmes simples est un problème complexe, voire impossible dans le cas général. En effet, les cœurs partagent l'accès à presque toutes les ressources ce qui provoque des conflits(qualifiés d'interférences) entrainant des variations non maîtrisées des temps d'exécutions. Parmi les mécanismes complexes d'un processeur multi-coeur se trouve la cohérence de caches. Celle-ci assure que tous les cœurs lisant ou écrivant dans un même bloc mémoire ne peuvent pas aveuglement ignorer les modifications appliquées par les autres. Afin de maintenir la cohérence de caches, le processeur suit un protocole pré-déterminé qui définit les messages à envoyer en fonction des actions d'un cœur ainsi que les actions à effectuer lors de la réception du message d'un autre cœur.Cette thèse porte sur l'identification des interférences générées par les mécanismes de cohérence de caches ainsi que sur les moyens de prédiction de leurs effets sur les applications en vue de réduire les effets négatifs temporels. La première contribution adresse les ambiguïtés dans la compréhension que les applicants ont de la cohérence de cache réellement présente dans l'architecture. En effet, la documentation des architectures ne fournit généralement pas suffisamment de détails sur les protocoles. Cette thèse propose une formalisation des protocoles standards, ainsi qu'une stratégie, reposant sur les micro-benchmarks, pour clarifier les choix d'implémentation du protocole de cohérence présent sur l'architecture. Cette stratégie a notamment été appliquée sur le NXP QorIQ T4240. Une fois le protocole correctement identifié, la seconde contribution consiste à réaliser une description bas-niveau de l'architecture en utilisant des automates temporisés afin de représenter convenablement les micro-comportements et comprendre clairement comment le protocole de cohérence de cache agit. Ainsi,un framework de génération de modèles génériques a été développé, capable de supporter plusieurs protocoles de cohérence de cache et de représenter différents agencements d'architectures afin de mieux correspondre à l'architecture choisie par le postulant. La troisième contribution explique comment utiliser cette représentation de l'architecture pour exhiber les interférences. Elle propose une stratégie pour détailler les causes et effets de chaque interférence liée à la cohérence de caches sur les programmes.Commençant par une simple analyse de temps d'exécution, les résultats descendent jusqu'au niveau des instructions pour indiquer comment chaque instruction génère et souffre des interférences. L'objectif étant alors de fournir suffisamment d'information à l'appliquant à la fois pour la certification, mais aussi pour définir une stratégie d'atténuation et de maîtrise des effets temporels.Ainsi, cette thèse fournit l'appliquant des outils pour comprendre les mécanismes de cohérence de cache présent sur une architecture donnée et pour exhiber les interférences associées.
|
Texte intégral
|
|
Institut Supérieur de l'Aéronautique et de l'Espace
/ 08-02-2021
Messaï Nadir-Alexandre
Voir le résumé
Voir le résumé
Cette thèse est dédiée à la conception et à l'étude d'une structure de boucle de raffinement auto-adaptative pour résoudre de manière fiable les équations intégrales acoustiques. Notre démarche est de revisiter l'ensemble des briques constitutives de cette architecture pour en améliorer l'efficacité algorithmique ainsi que la facilité d'utilisation, et vue d'en démocratiser son usage.Notre approche consista d'abord à étudier un schéma numérique de Galerkin discontinu. Cette méthode rend en effet possible l'utilisation de maillages $hp$ non-conformes et l'optimisation et la simplification de la construction de l'espace d'approximation. Nous fournissons une étude théorique détaillée de cette méthode et démontrons sa stabilité. Un ensemble d'expériences numériques a permis de confirmer le bon comportement pratique du schéma numérique.Nous avons ensuite adapté une méthode de compression matricielle basée sur une approche par interpolation directionnelle $mathcal{DH}^{2}$ ainsi que sa recompression algébrique. Un ensemble d'optimisations originales a été introduite en vue d'obtenir un algorithme efficace dans le cas de matrices issues du schéma de Galerkin discontinu. Nous obtenons textit{in fine} une compression robuste vis-à-vis de la fréquence et de l'hétérogénéité du maillage. Une analyse de complexité ainsi qu'un nombre conséquent d'expériences numériques, dont des comparaisons avec une $mathcal{H}$-matrice, sont également proposés.La dernière partie de la thèse fut d'abord dédiée à la construction d'un estimateur d'erreur textit{a posteriori} adapté au schéma de Galerkin discontinu qui soit fiable et local. Il est basé sur une approche de type résidu. Cet outil est indispensable pour guider le processus de raffinement local du maillage. Nous avons ensuite exploré un ensemble de procédures de raffinement local en $h$ et en $hp$ non-conformes. Cela permit de confirmer l'intérêt d'un raffinement $hp$ non-conforme, qui offre un meilleur taux de convergence de l'estimateur par rapport au raffinement en $h$ conforme. Une autre contribution originale de notre travail est de proposer un estimateur d'erreur qui prenne en compte l'ensemble des contributions à l'erreur globale : l'erreur de discretisation, l'erreur de résolution du système linéaire et l'erreur de compression. Cette finesse de description de l'erreur nous a permis d'automatiser le réglage de l'ensemble des paramètres de la boucle de raffinement auto-adaptative. Nous aboutissons finalement à une architecture de calcul extrêmement simple d'utilisation.
|
Texte intégral
|
|
Institut Supérieur de l'Aéronautique et de l'Espace
/ 16-12-2020
Perard Doriane
Voir le résumé
Voir le résumé
La blockchain est un registre distribué et décentralisé, permettant de stocker et d’échanger des informations de façon sécurisée, sans tiers de confiance. Pour cela,les informations, appelées transactions, sont regroupées au sein de blocs, qui sont ensuite liés entre eux de façon immuable grâce à des procédés cryptographiques. Le registre sert d’historique de toutes les actions menées par les participants du réseau depuis sa création.C’est une technologie en plein essor, de plus en plus utilisée au quotidien. Cet engouement croissant entraîne une explosion du nombre de transactions, ayant pour conséquence directe une forte augmentation de la taille des principales blockchains.Celles-ci deviennent donc plus compliquées à stocker dans leur intégralité, ce qui peut décourager certains nœuds de stocker toute la blockchain et ainsi réduire le niveau de décentralisation.Dans cette thèse, nous proposons un nouveau type de nœud, appelé low storage(LS) node, qui ne stocke plus les blocs en entier, mais des fragments de ceux-ci codés avec un code à effacement. Pour retrouver le bloc initial, un nœud LS commence par télécharger suffisamment de fragments codés depuis d’autres nœuds LS du réseau,puis procède au décodage.L’intérêt de cette approche est qu’elle permet à certains nœuds de stocker une version codée moins volumineuse de la blockchain tout en contribuant à la décentralisation de la blockchain. Elle facilite ainsi le passage à l’échelle des blockchains qui pose actuellement problème.Ce manuscrit présente également BlockHouse, un système complet permettant la location d’espace de stockage libre entre particuliers. La principale innovation est l’utilisation de contrats intelligents (smart contracts) déployés sur la blockchain qui permettent des paiements automatiques et sécurisés basés sur des preuves de récupérabilité des données régulièrement fournies par les serveurs de stockage.
|
Texte intégral
|
|
Institut Supérieur de l'Aéronautique et de l'Espace
/ 26-11-2020
Priem Rémy
Voir le résumé
Voir le résumé
De nos jours, la conception avant-projet en aéronautique repose majoritairement sur des modèles
numériques faisant interagir de nombreuses disciplines visant à évaluer les performances
de l’avion. Ces disciplines, comme l’aérodynamique, la structure et la propulsion, sont connectées
entre elles afin de prendre en compte leurs interactions. Cela produit un processus d’évaluation
des performances de l’avion coûteux en temps de calcul. En effet, une évaluation peut prendre de
trente secondes pour les modèles de basse fidélité jusqu’à plusieurs semaines pour les modèles
de plus haute fidélité. De plus, à cause de la multi-disciplinarité du processus et de la diversité
des outils de calcul, nous n’avons généralement pas accès aux propriétés ou au gradient de cette
fonction de performance. En outre, chaque discipline utilise ses propres variables de conception
et doit respecter des contraintes d’égalité ou d’inégalité qui sont souvent nombreuses et multimodales.
On cherche finalement à trouver la meilleur configuration possible dans un espace de
conception donné.
Cette recherche peut se traduire mathématiquement par un problème d’optimisation boite noire
sous contraintes d’inégalité et d’égalité, aussi connues comme contraintes mixtes, dépendant
d’un grand nombre de variables de conception. De plus, les contraintes et la fonction objective
sont coûteuses à évaluer et leur régularité n’est pas connue. C’est pourquoi, on s’intéresse
aux méthodes d’optimisations sans dérivées et particulièrement celles reposant sur les modèles
de substitution. Les méthodes d’optimisation Bayésienne, utilisant des processus gaussiens, sont
notamment étudiées car elles ont montré des convergences rapides sur des problèmes multimodaux.
En effet, l’utilisation d’algorithmes d’optimisation évolutionnaire ou reposant sur le gradient
n’est pas envisageable du fait du coût de calcul que cela implique : trop d’appels pour générer
des populations de points, ou pour approcher le gradient par différences finies.
Cependant la méthode d’optimisation Bayésienne est classiquement utilisée pour des problèmes
d’optimisation sans contrainte et de faible dimension. Des extensions ont été proposées
pour prendre en compte ce verrou de manière partielle. D’une part, des méthodes d’optimisation
ont été introduites pour résoudre des problèmes d’optimisation à contraintes mixtes. Toutefois,
aucune d’entre elles n’est adaptable à la grande dimension, aux problèmes multi-modaux et aux
contraintes mixtes. D’autre part, des méthodes d’optimisation ont été développées pour la grande
dimension pouvant aller jusqu’aumillion de variables de conception. De même, ces méthodes ne
s’étendent que difficilement aux problèmes contraints à cause du temps de calcul qu’ils nécessitent
ou de leur caractère aléatoire.
Une première partie de ce travail repose sur le développement d’un algorithme d’optimisation
Bayésienne résolvant les problèmes d’optimisation sans contrainte en grande dimension. Il repose
sur une stratégie d’apprentissage adaptatif d’un sous-espace linéaire réalisée conjointement
à l’optimisation. Ce sous-espace linéaire est ensuite utilisé pour réaliser l’optimisation. Cette méthode a été testée sur des cas tests académiques.
Une deuxième partie de ce travail traite du développement d’un algorithme d’optimisation
Bayésienne pour résoudre les problèmes d’optimisation multi-modaux sous contraintes mixtes. Il
a été comparé aux algorithmes de la littérature de manière intensive sur une grande batterie de
tests académiques.
Finalement, on a confronté le second algorithme à deux cas tests aéronautiques. Le premier
cas test est une configuration classique d’avion moyen-courrier à propulsion hybride électrique
développé par l’ONERA et l’ISAE-SUPAERO. Le second cas test est une configuration classique
d’avion d’affaire développée par Bombardier Aviation. Ce cas test repose sur une optimisation
à deux niveaux de fidélité. Un niveau de fidélité conceptuel et un niveau de fidélité préliminaire
pour lesquels le problème est respectivement évalué en trente secondes et 25 minutes. Cette dernière
étude a été réalisée lors d’une mobilité internationale chez Bombardier Aviation à Montréal
(CA). Les résultats ont montré l’intérêt de la méthode mise en place
|
Texte intégral
|
|
Institut Supérieur de l'Aéronautique et de l'Espace
/ 19-11-2020
Peschiera Franco
Voir le résumé
Voir le résumé
Cette thèse étudie le problème de planification de vol et de la maintenance
des avions militaires. D’abord, nous étudions la complexité de ce problème d’optimisation.
Puis, nous proposons un modèle de programmation linéaire en nombres entiers (PLNE) pour
le résoudre. Nous construisons un générateur d’instances et une heuristique pour générer des
solutions initiales. Ensuite, nous appliquons l’Apprentissage Automatique pour améliorer la
performance des modèles PLNE en utilisant des coupes valides générées à partir des conditions
initiales et des coupes apprises à partir de la prédiction des caractéristiques de solutions
optimales. Ces coupes sont appliquées à un nouveau modèle PLNE. Le résultat est une réduction
du temps de résolution avec peu de pertes d’optimalité et de faisabilité par rapport aux
méthodes matheuristiques alternatives. Finalement, nous présentons une nouvelle matheuristique
pour résoudre efficacement des grandes instances. La méthode utilise une descente à
voisinage variable qui combine la programmation dynamique (DP) et l’horizon glissant. La
DP exploite une représentation en graphe de l’espace des solutions de chaque avion. Le résultat
est des solutions rapides et presque optimales, et un passage à l’échelle efficace pour
des instances de très grande taille.
|
Texte intégral
|
|
Institut Supérieur de l'Aéronautique et de l'Espace
/ 06-03-2020
Singh Jasdeep
Voir le résumé
Voir le résumé
La thèse est une étude d'approches probabilistes pour la modélisation et l'analyse de systèmes temps réel. L'objectif est de comprendre et d'améliorer le pessimisme qui existe dans l'analyse du système. Les systèmes temps réel doivent produire des résultats avec des contraintes de temps réelles. L'exécution des tâches dans le système est basée sur leur pire temps d'exécution. En pratique, il peut y avoir de nombreux temps d'exécution possibles inférieurs au pire des cas. Nous utilisons le temps d’exécution probabiliste dans le pire cas, qui est une distribution de probabilité dans le pire des cas, qui limite tous les temps d’exécution possibles. Nous nous approchons avec le modèle de chaîne de Markov à temps continu pour obtenir des probabilités de manquer une contrainte de synchronisation dans le monde réel. Nous étudions également les systèmes de criticité mixte (MC) car ceux-ci ont également tendance à faire face au pessimisme dans un souci de sécurité. Les systèmes MC consistent en des tâches d’importance ou de criticité ged différentes. Le système fonctionne sous différents modes de criticité dans lesquels l'exécution des tâches de criticité identique ou supérieure est assurée. Nous abordons d’abord les systèmes MC en utilisant la chaîne de Markov en temps discret pour obtenir la probabilité que le système entre dans des niveaux de criticité plus élevés. Nous observons certaines limites de nos approches et nous procédons à la modélisation des systèmes probabilistes MC à l'aide de modèles Graph. Nous remettons en question les approches existantes dans la littérature et fournissons les nôtres. Nous obtenons des calendriers pour les systèmes MC optimisés pour l'utilisation des ressources. Nous faisons également le premier pas vers la dépendance entre les tâches en raison de leur scheduling.
|
Texte intégral
|
|
Institut Supérieur de l'Aéronautique et de l'Espace
/ 05-12-2019
Castiel Eyal
Voir le résumé
Voir le résumé
La performance des réseaux sans fil où les utilisateurs partagent l'air comme moyen de communication est fortement limitée par le phénomène d'interférence électromagnétique. En effet, deux utilisateurs proches qui communiquent sur la même fréquence verront leurs ondes interférer, ce qui peut entraîner la perte de l'information transmise. Ainsi, il est indispensable de mettre en place des protocoles d'accès visant à limiter l'interférence en choisissant de manière efficace les utilisateurs autorisés à émettre à chaque instant. D'un point de vue scientifique, il s'agit d'un problème difficile qui a attiré l'attention de la communauté en informatique et probabilités appliquées depuis plus de 30 ans. Récemment, une nouvelle classe de protocoles d'accès - appelés protocoles CSMA adaptatifs - a émergé, et semble très prometteuse : par exemple, il a été montré que ces nouveaux protocoles possèdent une propriété très attrayante de stabilité maximale. Le but de ce projet est d'approfondir la connaissance que l'on a des protocoles CSMA adaptatifs dits QB (pour l'anglais "Queue-Based") qui à ce jour est encore extrêmement limitée. Concernant ces protocoles, le but de ce projet est de prouver des résultats théoriques permettant de comprendre le compromis réalisable entre débit et délai. Modèle probabiliste - d'un point de vue technique, il s'agit d'étudier le modèle suivant: chaque utilisateur du réseau est représenté par le nœud d'un graphe G, appelé graphe d'interférence, et tel que deux voisins du graphe ne peuvent être actifs simultanément. Des paquets à transmettre arrivent à chaque nœud au cours du temps, et le but est de choisir quels nœuds sont actifs à un moment donné. Le protocole CSMA-QB répond à cette question de la manière suivante : lorsqu'un nœud est actif, il se désactive à taux constant et lorsqu'il est inactif et qu'aucun de ses voisins ne le bloquent, alors il s'active à un taux qui dépend du nombre de paquets en attente de transmission via une fonction ψ appelée fonction d'activation. Le but général de la thèse est de comprendre l'influence de la topologie de G et du choix de ψ sur la performance du protocole. Pour cela, il s'agira d'étudier le temps de mélange de la dynamique de Glauber ainsi qu'un phénomène classique en théorie des probabilités, appelé phénomène de moyennisation stochastique, qui permettent une compréhension fine du comportement dynamique du réseau.
|
Texte intégral
|
|
Institut Supérieur de l'Aéronautique et de l'Espace
/ 04-10-2019
Matiedje Tawa Jeanne
Voir le résumé
Voir le résumé
Cette étude concerne l’utilisation de la logique du premier ordre et la logique temporelle linéaire pour la spécification et la vérification des systèmes dynamiques ayant des structures riches. Elle concerne l’étude de la correction de fonctionnement du protocole de recherche distribuée Chord. L’objectif est d’une part d’améliorer la spécification et la vérification des systèmes dans le langage formel Electrum qui est une extension dynamique du langage formel Alloy basé sur la logique du premier ordre temporelle linéaire.Pour ce faire, nous avons développé une couche syntaxique au-dessus d’Electrum. L’objectif de cette couche est de faciliter la spécification du comportement dans Electrum, pour ce faire, nous avons défini une syntaxe permettant de générer automatiquement une partie de la spécification du comportement. Par ailleurs cette couche permet également de réduire les erreurs de spécification en déchargeant les utilisateurs de la spécification de certaines tâches comportementales ardues et sujettes aux erreurs.D’autre part, l’objectif est d’analyser formellement la correction de la propriété fondamentale de vivacité du protocole Chord. Pour ce faire nous avons spécifié et vérifié le protocole Chord avec l’extension d’Electrum que nous avons développée, puis nous avons prouvé sa correction et montré les avantages de notre méthode d’analyse.
|
Texte intégral
|
|
Institut Supérieur de l'Aéronautique et de l'Espace
/ 15-07-2019
Deschamps Henrick
Voir le résumé
Voir le résumé
Les travaux menés dans cette thèse de doctorat s’inscrivent dans le cadre d’un effort plus
large d’automatisation des systèmes de simulation industriels. Dans l’industrie aéronautique,
et plus particulièrement au sein d’Airbus, l’application historique de la simulation est la
formation des pilotes. Il existe aussi des utilisations plus récentes dans la conception de
systèmes, ainsi que dans l’intégration de ces systèmes. Ces dernières utilisations exigent un
très haut degré de représentativité, là où historiquement le plus important était le ressenti du
pilote. Les systèmes sont aujourd’hui divisés en plusieurs sous-systèmes qui sont conçus, implémentés et validés indépendamment, afin de maintenir leur contrôle malgré l’augmentation de leurs complexités et la réduction des temps de mise sur le marché. Airbus maîtrise déjà la
simulation de ces sous-systèmes, ainsi que leurs intégrations en simulation. Cette maîtrise
est empirique, les spécialistes de la simulation reprennent l’ordonnancement d’intégrations
précédentes, et l’adaptent à une nouvelle intégration. C’est un processus qui peut parfois être
chronophage, et qui peut introduire des erreurs. Les tendances actuelles de l’industrie sont à la flexibilité des moyens de production, à
l’intégration d’outils logistiques permettant le suivi, à l’utilisation d’outils de simulation en
production, et à l’optimisation des ressources. Les produits sont de plus en plus souvent des
itérations d’anciens produits améliorés, et les tests et simulations intégrés à leurs cycles de vie.
Travailler de manière empirique dans une industrie qui nécessite de la flexibilité est
une contrainte, et il est aujourd’hui important de facilement modifier des simulations. La
problématique est donc de mettre en place des méthodes et outils permettant
a priori de générer des ordonnancements de simulations représentatifs. Afin de répondre à ce problème, nous avons mis en place une méthode permettant de décrire les composants d’une simulation, la manière dont cette simulation pourra être exécutée,
ainsi que des fonctions permettant de générer des ordonnancements. Par la suite, nous avons
implémenté un outil afin d’automatiser la recherche d’ordonnancement, en se basant sur des
heuristiques. Enfin nous avons testé et vérifié notre méthode et outils sur des cas d’études
académiques et industriels.
|
Texte intégral
|
|