Les systèmes électroniques embarqués dans les véhicules ont une complexité sans cesse croissante. Cependant, il est crucial d'en maîtriser le comportement temporel afin de garantir la sécurité ainsi que le confort des passagers. La vérification des contraintes temporelles de bout-en-bout est donc un enjeu majeur lors de la conception d'un véhicule. Dans le contexte de l'architecture logicielle AUTOSAR standard dans les véhicules, nous décomposons la vérification d'une contrainte de bout-en-bout en sous-problèmes d'ordonnancement sur les calculateurs et sur les réseaux de communication que nous traitons ensuite séparément. Dans un premier temps, nous présentons une approche permettant d'améliorer l'utilisation des calculateurs exécutant un grand nombre de composants logiciels, compatible avec l'introduction progressive des plateformes multi-coeurs. Nous décrivons des algorithmes rapides et efficaces pour lisser la charge périodique sur les calculateurs multi-coeurs en adaptant puis en améliorant une approche existant pour les bus CAN. Nous donnons également des résultats théoriques sur l'efficacité des algorithmes dans certains cas particuliers. Enfin, nous décrivons les possibilités d'utilisation de ces algorithmes en fonction des autres tâches exécutées sur le calculateur. La suite des travaux est consacrée à l'étude des distributions de temps de réponse des messages transmis sur les bus CAN. Dans un premier temps nous présentons une approche de simulation basée sur la modélisation des dérives d'horloges des calculateurs communicant sur le réseau. Nous montrons que nous obtenons des distributions de temps de réponse similaires en réalisant une longue simulation avec des dérives d'horloge ou en faisant un grand nombre de courtes simulations sans dérives d'horloge. Nous présentons enfin une technique analytique pour évaluer les distributions de temps de réponse des trames CAN. Nous présentons différents paramètres d'approximation permettant de réduire le nombre très important de calculs à effectuer en limitant la perte de précision. Enfin, nous comparons expérimentalement les résultats obtenus par analyse et simulation et décrivons les avantages et inconvénients respectifs de ces approches / The complexity of electronic embedded systems in cars is continuously growing. Hence, mastering the temporal behavior of such systems is paramount in order to ensure the safety and comfort of the passengers. As a consequence, the verification of end-to-end real-time constraints is a major challenge during the design phase of a car. The AUTOSAR software architecture drives us to address the verification of end-to-end real-time constraints as two independent scheduling problems respectively for electronic control units and communication buses. First, we introduce an approach, which optimizes the utilization of controllers scheduling numerous software components that is compatible with the upcoming multicore architectures. We describe fast and efficient algorithms in order to balance the periodic load over time on multicore controllers by adapting and improving an existing approach used for the CAN networks. We provide theoretical result on the efficiency of the algorithms in some specific cases. Moreover, we describe how to use these algorithms in conjunction with other tasks scheduled on the controller. The remaining part of this research work addresses the problem of obtaining the response time distributions of the messages sent on a CAN network. First, we present a simulation approach based on the modelisation of clock drifts on the communicating nodes connected on the CAN network. We show that we obtain similar results with a single simulation using our approach in comparison with the legacy approach consisting in numerous short simulation runs without clock drifts. Then, we present an analytical approach in order to compute the response time distributions of the CAN frames. We introduce several approximation parameters to cope with the very high computational complexity of this approach while limiting the loss of accuracy. Finally, we compare experimentally the simulation and analytical approaches in order to discuss the relative advantages of each of the two approaches

De nos jours, la validation des unités de contrôle électronique ECU se fonde généralement sur la simulationHardware-In-the-Loop où les systèmes physiques qui manquent sont modélisés à l’aide deséquations différentielles hybrides. La complexité croissante de ce type de modèles rend le compromisentre le temps de calcul et la précision de la simulation difficile à satisfaire. Cette thèse étudie et proposedes méthodes d’analyse et d’expérimentation destinées à la co-simulation temps-réel ferme de modèlesdynamiques hybrides. Elle vise notamment à définir des solutions afin d’exploiter plus efficacement leparallélisme fourni par les architectures multi-coeurs en utilisant de nouvelles méthodes et paradigmesde l’allocation des ressources. La première phase de la thèse a étudié la possibilité d’utiliser des méthodesd’intégration numérique permettant d’adapter l’ordre comme la taille du pas de temps ainsi quede détecter les événements et ceci dans le contexte de la co-simulation modulaire avec des contraintestemps-réel faiblement dures. De plus, l’ordre d’exécution des différents modèles a été étudié afin dedémontrer l’influence du respect des dépendances de données entre les modèles couplés sur les résultatsde la simulation. Nous avons proposé pour cet objectif, une nouvelle méthode de co-simulationqui permet le parallélisme complet entre les modèles impliquant une accélération supra-linéaire sanspour autant ajouter des erreurs liées à l’ordre d’exécution. Enfin, les erreurs de retard causées par lataille de pas de communication entre les modèles ont été améliorées grâce à une nouvelle méthoded’extrapolation par contexte des signaux d’entrée. Toutes les approches proposées visent de manièreconstructive à améliorer la vitesse de simulation afin de respecter les contraintes temps-réel, tout engardant la qualité et la précision des résultats de simulation sous contrôle. Ces méthodes ont été validéespar plusieurs essais et expériences sur un modèle de moteur à combustion interne et intégrées àun prototype du logiciel xMOD. / Nowadays the validation of Electronic Control Units ECUs generally relies on Hardware-in-The-Loopsimulation where the lacking physical systems are modeled using hybrid differential equations. Theincreasing complexity of this kind of models makes the trade-off between time efficiency and the simulationaccuracy hard to satisfy. This thesis investigates and proposes some analytical and experimentalmethods towards weakly-hard real-time co-simulation of hybrid dynamical models. It seeks in particularto define solutions in order to exploit more efficiently the parallelism provided by multi-core architecturesusing new methods and paradigms of resource allocation. The first phase of the thesis studied the possibilityof using step-size and order control numerical integration methods with events detection in thecontext of real-time modular co-simulation when the time constraints are considered weakly-hard. Moreover,the execution order of the different models was studied to show the influence of keeping or not thedata dependencies between coupled models on the simulation results. We proposed for this aim a newmethod of co-simulation that allows the full parallelism between models implying supra-linear speed-upswithout adding errors related to their execution order. Finally, the delay errors due to the communicationstep-size between the models were improved thanks to a proposed context-based inputs extrapolation.All proposed approaches target constructively to enhance the simulation speed for the compliance toreal-time constraints while keeping the quality and accuracy of simulation results under control and theyare validated through several test and experiments on an internal combustion engine model and integratedto a prototype version of the xMOD software.

L'accroissement régulier de la fréquence des micro-processeurs et des importants gains de puissance qui en avaient résulté ont pris fin en 2005. Les autres techniques matérielles d'amélioration de performance se sont largement essouflées. Les fabricants de micro-processeurs ont donc choisi d'exploiter le nombre croissant de transistors disponibles en plaçant plusieurs cœurs de processeurs sur une même puce. Dans cette thèse, nous préparons l'arrivée de processeurs multi-cœur à grand nombre de cœurs par des recherches dans trois directions. Premièrement, nous améliorons l'environnement de parallélisation CAPSULE (parallélisation conditionnelle) en lui adjoignant des primitives de synchronization de tâches robustes. Nous montrons les gains obtenus par rapport aux approches usuelles en terme de rapidité et de stabilité du temps d'exécution. Deuxièmement, nous adaptons CAPSULE à des machines à mémoire distribuée en présentant un modèle de données qui permet au système de déplacer automatiquement les données en fonction des accès effectués par les programmes. De nouveaux algorithmes répartis et locaux permettent de décider de la création effective des tâches et de leur répartition. Troisièmement, nous développons un nouveau simulateur d'évènements discrets, SiMany, qui peut prendre en charge des centaines à des milliers de cœurs. Il est plus de 100 fois plus rapide que les meilleurs simulateurs flexibles actuels. Après validation, nous montrons que SiMany permet l'exploration d'un plus large champ d'architectures ainsi que l'étude des grandes lignes du comportement des logiciels sur celles-ci.

Le calcul scientifique est souvent associé au calcul numérique. Pourtant dans de nombreuses disciplines scientifiques il est nécessaire d'aller au-delà du calcul approché : nécessité de certification des résultats, calculs dans des structures mathématiques discrètes, instabilité des algorithmique numériques. Le calcul exact s'attache donc à donner des résultats exacts ou certifiés. Cependant, la principale obstruction à l'utilisation du Calcul Formel est bien souvent les faibles performances des systèmes commerciaux y compris pour les opérations fondamentales comme l'algèbre linéaire. L'objectif de ces travaux est donc de réduire l'écart entre le calcul exact et le calcul numérique, tant sur le plan algorithmique, que sur le plan logiciel. Les défis sont multiples : développer une arithmétique efficace dans les structures discrètes ; concevoir des algorithmes ayant un terme dominant de complexité optimal même en tenant compte de la croissance des données intermédiaires ; transcrire ces algorithmes dans des logiciels combinant efficacité pérenne, interfaçage et généricité.

Rechercher les similarités entre séquences est une opération fondamentale en bioinformatique, que cela soit pour étudier des questions biologiques ou bien pour traiter les données issues de séquenceurs haut-débit. Il y a un vrai besoin d'algorithmes capables de traiter des millions de séquences rapidement. Pour trouver des similarités approchées, on peut tout d'abord considérer de petits mots exacts présents dans les deux séquences, les graines, puis essayer d'étendre les similarités aux voisinages de ces graines. Cette thèse se focalise sur la deuxième étape des heuristiques à base de graines : comment récupérer et comparer efficacement ces voisinages des graines, pour ne garder que les bons candidats ? La thèse explore différentes solutions adaptées aux processeurs massivement multicoeurs: aujourd'hui, les GPUs sont en train de démocratiser le calcul parallèle et préparent les processeurs de demain. La thèse propose des approches directes (extension de l'algorithme bit-parallèle de Wu-Manber, publiée à PBC 2011, et recherche dichotomique) ou bien avec un index supplémentaire (utilisation de fonctions de hash parfaites). Chaque solution a été pensée pour tirer le meilleur profit des architectures avec un fort parallélisme à grain fin, en utilisant des calculs intensifs mais homogènes. Toutes les méthodes proposées ont été implémentés en OpenCL, et comparées sur leur temps d'exécution. La thèse se termine par un prototype de read mapper parallèle, MAROSE, utilisant ces concepts. Dans certaines situations, MAROSE est plus rapide que les solutions existantes avec une sensibilité similaire.