Siga este enlace para ver otros tipos de publicaciones sobre el tema: Analyse de pire cas.
Tesis sobre el tema "Analyse de pire cas"
Crea una cita precisa en los estilos APA, MLA, Chicago, Harvard y otros
Consulte los 50 mejores tesis para su investigación sobre el tema "Analyse de pire cas".
Junto a cada fuente en la lista de referencias hay un botón "Agregar a la bibliografía". Pulsa este botón, y generaremos automáticamente la referencia bibliográfica para la obra elegida en el estilo de cita que necesites: APA, MLA, Harvard, Vancouver, Chicago, etc.
También puede descargar el texto completo de la publicación académica en formato pdf y leer en línea su resumen siempre que esté disponible en los metadatos.
Explore tesis sobre una amplia variedad de disciplinas y organice su bibliografía correctamente.
1
Adnan, Muhammad. "Analyse pire cas exact du réseau AFDX". Thesis, Toulouse, INPT, 2013. http://www.theses.fr/2013INPT0146/document.
Texto completoResumen
L'objectif principal de cette thèse est de proposer les méthodes permettant d'obtenir le délai de transmission de bout en bout pire cas exact d'un réseau AFDX. Actuellement, seules des bornes supérieures pessimistes peuvent être calculées en utilisant les approches de type Calcul Réseau ou par Trajectoires. Pour cet objectif, différentes approches et outils existent et ont été analysées dans le contexte de cette thèse. Cette analyse a mis en évidence le besoin de nouvelles approches. Dans un premier temps, la vérification de modèle a été explorée. Les automates temporisés et les outils de verification ayant fait leur preuve dans le domaine temps réel ont été utilisés. Ensuite, une technique de simulation exhaustive a été utilisée pour obtenir les délais de communication pire cas exacts. Pour ce faire, des méthodes de réduction de séquences ont été définies et un outil a été développé. Ces méthodes ont été appliquées à une configuration réelle du réseau AFDX, nous permettant ainsi de valider notre travail sur une configuration de taille industrielle du réseau AFDX telle que celle embarquée à bord des avions Airbus A380. The main objective of this thesis is to provide methodologies for finding exact worst case end to end communication delays of AFDX network. Presently, only pessimistic upper bounds of these delays can be calculated by using Network Calculus and Trajectory approach. To achieve this goal, different existing tools and approaches have been analyzed in the context of this thesis. Based on this analysis, it is deemed necessary to develop new approaches and algorithms. First, Model checking with existing well established real time model checking tools are explored, using timed automata. Then, exhaustive simulation technique is used with newly developed algorithms and their software implementation in order to find exact worst case communication delays of AFDX network. All this research work has been applied on real life implementation of AFDX network, allowing us to validate our research work on industrial scale configuration of AFDX network such as used on Airbus A380 aircraftThe main objective of this thesis is to provide methodologies for finding exact worst case end to end communication delays of AFDX network. Presently, only pessimistic upper bounds of these delays can be calculated by using Network Calculus and Trajectory approach. To achieve this goal, different existing tools and approaches have been analyzed in the context of this thesis. Based on this analysis, it is deemed necessary to develop new approaches and algorithms. First, Model checking with existing well established real time model checking tools are explored, using timed automata. Then, exhaustive simulation technique is used with newly developed algorithms and their software implementation in order to find exact worst case communication delays of AFDX network. All this research work has been applied on real life implementation of AFDX network, allowing us to validate our research work on industrial scale configuration of AFDX network such as used on Airbus A380 aircraft
2
Hardy, Damien. "Analyse pire cas pour processeur multi-cœurs disposant de caches partagés". Phd thesis, Université Rennes 1, 2010. http://tel.archives-ouvertes.fr/tel-00557058.
Texto completoResumen
Les systèmes temps-réel strict sont soumis à des contraintes temporelles dont le non respect peut entraîner des conséquences économiques, écologiques, humaines catastrophiques. Le processus de validation, garantissant la sûreté de ces logiciels en assurant le respect de ces contraintes dans toutes les situations possibles y compris le pire cas, se base sur la connaissance à priori du pire temps d'exécution de chacune des tâches du logiciel. Cependant, l'obtention de ce pire temps d'exécution est un problème difficile pour les architectures actuelles, en raison des mécanismes matériels complexes pouvant amener une variabilité importante du temps d'exécution. Ce document se concentre sur l'analyse du comportement temporel pire cas des hiérarchies de mémoires cache, afin de déterminer leur contribution au pire temps d'exécution. Plusieurs approches sont proposées afin de prédire et d'améliorer le pire temps d'exécution des tâches s'exécutant sur des processeurs multi-cœurs disposant d'une hiérarchie de mémoires cache avec des niveaux partagés entre les différents cœurs de calculs.
3
Hardy, Damien. "Analyse pire cas pour processeur multi-coeurs disposant de caches partagés". Rennes 1, 2010. http://www.theses.fr/2010REN1S143.
Texto completoResumen
Les systèmes temps-réel strict sont soumis à des contraintes temporelles dont le non respect peut entraîner des conséquences économiques, écologiques, humaines catastrophiques. Le processus de validation, garantissant la sûreté de ces logiciels en assurant le respect de ces contraintes dans toutes les situations possibles y compris le pire cas, se base sur la connaissance à priori du pire temps d’exécution de chacune des tâches du logiciel. Cependant, l’obtention de ce pire temps d’exécution est un problème difficile pour les architectures actuelles, en raison des mécanismes matériels complexes pouvant amener une variabilité importante du temps d’exécution. Ce document se concentre sur l’analyse du comportement temporel pire cas des hiérarchies de mémoires cache, afin de déterminer leur contribution au pire temps d’exécution. Plusieurs approches sont proposées afin de prédire et d’améliorer le pire temps d’exécution des tâches s’exécutant sur des processeurs multi-coeurs disposant d’une hiérarchie de mémoires cache avec des niveaux partagés entre les différents coeurs de calculsHard real-time systems are subject to timing constraints and failure to respect them can cause economic, ecological or human disasters. The validation process which guarantees the safety of such software, by ensuring the respect of these constraints in all situations including the worst case, is based on the knowledge of the worst case execution time of each task. However, determining the worst case execution time is a difficult problem for modern architectures because of complex hardware mechanisms that could cause significant execution time variability. This document focuses on the analysis of the worst case timing behavior of cache hierarchies, to determine their contribution to the worst case execution time. Several approaches are proposed to predict and improve the worst case execution time of tasks running on multicore processors with a cache hierarchy in which some cache levels are shared between cores
4
Bauer, Henri. "Analyse pire cas de flux hétérogènes dans un réseau embarqué avion". Thesis, Toulouse, INPT, 2011. http://www.theses.fr/2011INPT0008/document.
Texto completoResumen
La certification des réseaux avioniques requiert une maîtrise des délais de transmission des données. Cepednant, le multiplexage et le partage des ressource de communications dans des réseaux tels que l'AFDX (Avionics Full Duplex Switched Ethernet) rendent difficile le calcul d'un délai de bout en bout pire cas pour chaque flux. Des outils comme le calcul réseau fournissent une borne supérieure (pessimiste) de ce délai pire cas. Les besoins de communication des avions civils modernes ne cessent d'augmenter et un nombre croissant de flux aux contraintes et aux caractéristiques différentes doivent partager les ressources existantes. Le réseau AFDX actuel ne permet pas de différentier plusieurs classes de trafic : les messages sont traités dans les files des commutateurs selon leur ordre d'arrivée (politique de service FIFO). L'objet de cette thèse est de montrer qu'il est possible de calculer des bornes pire cas des délais de bout en bout avec des politiques de service plus évoluées, à base de priorités statiques (Priority Queueing) ou à répartition équitable de service (Fair Queueing). Nous montrons comment l'approche par trajectoires, issue de la théorie de l'ordonnancement dans des systèmes asynchrones distribués peut s'appliquer au domaine de l'AFDX actuel et futur (intégration de politiques de service plus évoluées permettant la différentiation de flux). Nous comparons les performances de cette approche avec les outils de référence lorsque cela est possible et étudions le pessimisme des bornes ainsi obtenuesThe certification process for avionics network requires guaranties on data transmission delays. However, calculating the worst case delay can be complex in the case of industrial AFDX (Avionics Full Duplex Switched Ethernet) networks. Tools such as Network Calculus provide a pessimistic upper bound of this worst case delay. Communication needs of modern commercial aircraft are expanding and a growing number of flows with various constraints and characteristics must share already existing resources. Currently deployed AFDX networks do not differentiate multiple classes of traffic: messages are processed in their arrival order in the output ports of the switches (FIFO servicing policy). The purpose of this thesis is to show that it is possible to provide upper bounds of end to end transmission delays in networks that implement more advanced servicing policies, based on static priorities (Priority Queuing) or on fairness (Fair Queuing). We show how the trajectory approach, based on scheduling theory in asynchronous distributed systems can be applied to current and future AFDX networks (supporting advanced servicing policies with flow differentiation capabilities). We compare the performance of this approach with the reference tools whenever it is possible and we study the pessimism of the computed upper bounds
5
Lesage, Benjamin. "Architecture multi-coeurs et temps d'exécution au pire cas". Phd thesis, Université Rennes 1, 2013. http://tel.archives-ouvertes.fr/tel-00870971.
Texto completoResumen
Les tâches critiques en systèmes temps-réel sont soumises à des contraintes temporelles et de correction. La validation d'un tel système repose sur l'estimation du comportement temporel au pire cas de ses tâches. Le partage de ressources, inhérent aux architectures multi-cœurs, entrave le calcul de ces estimations. Le comportement temporel d'une tâche dépend de ses rivales du fait de l'arbitrage de l'accès aux ressources ou de modifications concurrentes de leur état. Cette étude vise à l'estimation de la contribution temporelle de la hiérarchie mémoire au pire temps d'exécution de tâches critiques. Les méthodes existantes, pour caches d'instructions, sont étendues afin de supporter caches de données privés et partagés, et permettre l'analyse de hiérarchies mémoires riches. Le court-circuitage de cache est ensuite utilisé pour réduire la pression sur les caches partagés. Nous proposons à cette fin différentes heuristiques basées sur la capture de la réutilisation de blocs de cache entre différents accès mémoire. Notre seconde proposition est la politique de partitionnement Preti qui permet l'allocation d'un espace sans conflits à une tâche. Preti favorise aussi les performances de tâches non critiques concurrentes aux temps-réel dans les systèmes de criticité hybride.
6
Temmerman, Michel. "Analyse et synthèse du tolérancement "au pire des cas" et statistique dans l'environnement CFAO". Châtenay-Malabry, Ecole centrale de Paris, 2001. http://www.theses.fr/2001ECAP0719.
Texto completoResumen
Les outils et méthodes introduits dans cette thèse sont bases sur l'utilisation du concept de surfaces associées technologiquement et topologiquement (satt). Apres un état de l'art du tolérancement, le nouveau concept de pseudo-satt est présente. Il permet de construire une structure satt généralisée avec boucles de contacts en relation avec la déclaration du spécificateur. Des lois de comportement géométrique et fonctionnel sont alors générées en utilisant les paramètres de petits déplacements associes au concept de satt. Une première simulation au pire des cas est proposée en appliquant les lois de comportement pour générer des équations et inéquations au tolérancement et jeux fonctionnels. Une deuxième simulation statistique est proposée toujours en appliquant les lois de comportement pour générer des équations statistiques sous contraintes de spécifications avec attributs statistiques en relation avec la norme iso.
7
Colin, Antoine. "Estimation de temps d'éxécution au pire cas par analyse statique et application aux systèmes d'exploitation temps réel". Rennes 1, 2001. http://www.theses.fr/2001REN10118.
Texto completoResumen
Soit X une variété algébrique réelle affine compacte non singulière. Une variété algébrique réelle affine X' est obtenue par modification de X si elle peut être construite à partir de X par une suite d'éclatements et de contractions le long de centres non singuliers. Dans la première partie, nous montrons qu'une variété X' ainsi construite a sa cohomologie entièrement algébrique si la variété X et tous les centres de la modification ont aussi leur cohomologie entièrement algébrique. Dans la deuxième et la troisième partie, nous définissons et développons la notion de (co)homologie équivariante en utilisant des complexes de (co)chaînes. En particulier, on retrouve ainsi dans le cadre équivariant les propriétés de la (co)homologie classique. De plus, si X est une variété algébrique définie sur R, compacte et non singulière, il existe un diagramme reliant l'homologie de l'ensemble des points complexes X(C), l'homologie de l'ensemble des points réels X(R) et l'homologie équivariante de X. Ce diagramme nous permet d'obtenir des informations sur les groupes de cohomologie algébrique de l'ensemble des points réels. Comme exemple, nous regardons le cas des variétés toriques dans la quatrième partie. Nous montrons ainsi que l'ensemble des points réels d'une variété torique compacte non singulière a sa cohomologie entièrement algébrique en appliquant les résultats de la première partie dans un premier temps, puis de la deuxième et troisième partie dans un second
8
Bourgade, Roman. "Analyse du temps d'exécution pire-cas de tâches temps-réel exécutées sur une architecture multi-cœurs". Phd thesis, Université Paul Sabatier - Toulouse III, 2012. http://tel.archives-ouvertes.fr/tel-00746073.
Texto completoResumen
Les défaillances des applications embarquées dans les systèmes temps-réel strict peuvent avoir des conséquences graves (catastrophes industrielles, mise en danger de vies humaines). La vérification des contraintes temporelles d'un système temps-réel strict dépend de la connaissance du temps d'exécution pire-cas des tâches constituant l'application embarquée. L'utilisation de processeurs multi-cœurs est l'un des moyens actuellement mis en œuvre afin d'améliorer le niveau de performances des systèmes embarqués. Cependant, la détermination du temps d'exécution pire-cas d'une tâche sur ce type d'architecture est rendue difficile par le partage de certaines ressources par les cœurs, et notamment le bus d'interconnexion permettant l'accès à la mémoire centrale. Ce document propose un nouveau mécanisme d'arbitrage de bus à deux niveaux permettant d'améliorer les performances des ensembles de tâches exécutés tout en garantissant le respect des contraintes temporelles. Les méthodes décrites permettent d'établir un niveau de priorité d'accès au bus optimal pour chacune des tâches exécutées. Elles permettent également de trouver une allocation optimale des tâches aux cœurs lorsqu'il y a plus de tâches à exécuter que de cœurs disponibles. Les résultats expérimentaux montrent une diminution significative des estimations de temps d'exécution pire-cas et de l'utilisation du processeur.
9
Bourgade, Roman. "Analyse du temps d'exécution pire-cas de tâches temps-réel exécutées sur une architecture multi-coeurs". Toulouse 3, 2012. http://thesesups.ups-tlse.fr/1740/.
Texto completoResumen
Les défaillances des applications embarquées dans les systèmes temps-réel strict peuvent avoir des conséquences graves (catastrophes industrielles, mise en danger de vies humaines). La vérification des contraintes temporelles d'un système temps-réel strict dépend de la connaissance du temps d'exécution pire-cas des tâches constituant l'application embarquée. L'utilisation de processeurs multi-cœurs est l'un des moyens actuellement mis en œuvre afin d'améliorer le niveau de performances des systèmes embarqués. Cependant, la détermination du temps d'exécution pire-cas d'une tâche sur ce type d'architecture est rendue difficile par le partage de certaines ressources par les cœurs, et notamment le bus d'interconnexion permettant l'accès à la mémoire centrale. Ce document propose un nouveau mécanisme d'arbitrage de bus à deux niveaux permettant d'améliorer les performances des ensembles de tâches exécutés tout en garantissant le respect des contraintes temporelles. Les méthodes décrites permettent d'établir un niveau de priorité d'accès au bus optimal pour chacune des tâches exécutées. Elles permettent également de trouver une allocation optimale des tâches aux cœurs lorsqu'il y a plus de tâches à exécuter que de cœurs disponibles. Les résultats expérimentaux montrent une diminution significative des estimations de temps d'exécution pire-cas et de l'utilisation du processeurSoftware failures in hard real-time systems may have hazardous effects (industrial disasters, human lives endangering). The verification of timing constraints in a hard real-time system depends on the knowledge of the worst-case execution times (WCET) of the tasks accounting for the embedded program. Using multicore processors is a mean to improve embedded systems performances. However, determining worst-case execution times estimates on these architectures is made difficult by the sharing of some resources among cores, especially the interconnection bus that enables accesses to the shared memory. This document proposes a two-level arbitration scheme that makes it possible to improve executed tasks performances while complying with timing constraints. Described methods assess an optimal bus access priority level to each of the tasks. They also allow to find an optimal allocation of tasks to cores when tasks to execute are more numerous than available cores. Experimental results show a meaningful drop in worst-case execution times estimates and processor utilization
10
Mangoua, sofack William. "Amélioration des délais de traversée pire cas des réseaux embarqués à l’aide du calcul réseau". Thesis, Toulouse, ISAE, 2014. http://www.theses.fr/2014ESAE0024/document.
Texto completoResumen
Le calcul réseau (network calculus) est une théorie basée sur l’algèbre min-plus. Il offre un cadre formel de modélisation des réseaux de communication. Il a été utilisé pour certifier le réseau AFDX embarqué dans l’A380 de Airbus. Seulement, les bornes sur le délai annoncés par ces travaux de certification souffrent d’une sur-approximation dans le cas précis de l’agrégation dans un contexte de priorité statique non préemptive.L’objectif de nos travaux est de réduire cette sur-approximation. Dans cette thèse, nous proposons un service résiduel permettant d’obtenir de meilleurs bornes sur le délai dans le cas de la politique à priorité statique non préemptive et de la politique DRR. Nous montrons aussi comment ces deux politiques peuvent être combinées dans une politique hiérarchique à deux niveauxThe thesis addresses performance analysis of embedded real time network using network calculus. Network calculus is a theory based on min-plus algebra. We use network calculus to assess the quality of service of a residual flow in two context : aggregation with non-preemptive priority policy and DRR policy. The main contribution concerns the evaluation of residual service, given to each flow. We also present how to handle DRR and non-preemptive priority policy hierrachically
11
Touzeau, Valentin. "Analyse statique de caches LRU : complexité, analyse optimale, et applications au calcul de pire temps d'exécution et à la sécurité". Thesis, Université Grenoble Alpes (ComUE), 2019. http://www.theses.fr/2019GREAM041.
Texto completoResumen
Dans le cadre des systèmes critiques, la certification de programmes temps-réel nécessite de borner leur temps d'exécution.Les mémoires caches impactant fortement la latence des accès mémoires, les outils de calcul de pire temps d'exécution incluent des analyses de cache.Ces analyses visent à prédire statiquement si ces accès aboutissent à des cache-hits ou des cache-miss.Ce problème étant indécidable en général, les analyses de caches emploient des abstractions pouvant mener à des pertes de précision.Une hypothèse habituelle pour rendre le problème décidable consiste à supposer que toutes les exécutions du programme sont réalisables.Cette hypothèse est raisonnable car elle ne met pas en cause la validité de l'analyse: tous les véritables chemins d'exécutions du programme sont couverts par l'analyse.Néanmoins, la classification des accès mémoires reste difficile en pratique malgré cette hypothèse, et les analyses de cache efficaces utilisent des approximations supplémentaires.Cette thèse s'intéresse à la possibilité de réaliser des analyses de cache de précision optimale sous l'hypothèse que tous les chemins sont faisables.Les problèmes de classification d'accès mémoires en hits et miss y sont définis formellement et nous prouvons qu'ils sont NP-difficiles, voire PSPACE-difficiles, pour les politiques de remplacement usuelles (LRU, FIFO, NMRU et PLRU).Toutefois, si ces résultats théoriques justifient l'utilisation d'abstractions supplémentaires, ils n'excluent pas l'existence d'un algorithme efficace en pratique pour des instances courantes dans l'industrie.Les abstractions usuelles ne permettent pas, en général, de classifier tous les accès mémoires en Always-Hit et Always-Miss.Certains sont alors classifiés Unknown par l'analyse de cache, et peuvent aboutir à des cache-hits comme à des cache-miss selon le chemin d'exécution emprunté.Cependant, il est aussi possible qu'un accès soit classifié comme Unknown alors qu'il mène toujours à un hit (ou un miss), à cause d'une approximation trop grossière.Nous proposons donc une nouvelle analyse de cache d'instructions LRU, capable de classifier certains accès comme Definitely Unknown, une nouvelle catégorie représentant les accès pouvant mener à un hit ou à un miss.On est alors certain que la classification de ces accès est due au programme et à la configuration du cache, et pas à une approximation peu précise.Par ailleurs, cette analyse réduit le nombre d'accès candidats à une reclassification par des analyses plus précises mais plus coûteuses.Notre principale contribution est une analyse capable de produire une classification de précision optimale.Celle-ci repose sur une méthode appelée block focusing qui permet le passage à l'échelle en analysant les blocs de cache un par un.Nous profitons ainsi de l'analyse de l'analyse Definitely Unknown, qui réduit le nombre de candidats à une classification plus précise.Cette analyse précise produit alors une classification optimale pour un coût raisonnable (proche du coût des analyses usuelles May et Must).Nous étudions également l'impact de notre analyse exacte sur l'analyse de pipeline.En effet, lorsqu'une analyse de cache ne parvient pas à classifier un accès comme Always-Hit ou Always-Miss, les deux cas (hit et miss) sont envisagés par l'analyse de pipeline.En fournissant une classification plus précise des accès mémoires, nous réduisons donc la taille de l'espace d'états de pipeline exploré, et donc le temps de l'analyse.Par ailleurs, cette thèse étudie la possibilité d'utiliser l'analyse Definitely Unknown dans le domaine de la sécurité.Les mémoires caches peuvent être utilisées comme canaux cachés pour extraire des informations de l'exécution d'un programme.Nous proposons une variante de l'analyse Definitely Unknown visant à localiser la source de certaines fuites d'informationThe certification of real-time safety critical programs requires bounding their execution time.Due to the high impact of cache memories on memory access latency, modern Worst-Case Execution Time estimation tools include a cache analysis.The aim of this analysis is to statically predict if memory accesses result in a cache hit or a cache miss.This problem is undecidable in general, thus usual cache analyses perform some abstractions that lead to precision loss.One common assumption made to remove the source of undecidability is that all execution paths in the program are feasible.Making this hypothesis is reasonable because the safety of the analysis is preserved when adding spurious paths to the program model.However, classifying memory accesses as cache hits or misses is still hard in practice under this assumption, and efficient cache analysis usually involve additional approximations, again leading to precision loss.This thesis investigates the possibility of performing an optimally precise cache analysis under the common assumption that all execution paths in the program are feasible.We formally define the problems of classifying accesses as hits and misses, and prove that they are NP-hard or PSPACE-hard for common replacement policies (LRU, FIFO, NRU and PLRU).However, if these theoretical complexity results legitimate the use of additional abstraction, they do not preclude the existence of algorithms efficient in practice on industrial workloads.Because of the abstractions performed for efficiency reasons, cache analyses can usually classify accesses as Unknown in addition to Always-Hit (Must analysis) or Always-Miss (May analysis).Accesses classified as Unknown can lead to both a hit or a miss, depending on the program execution path followed.However, it can also be that they belong to one of the Always-Hit or Always-Miss category and that the cache analysis failed to classify them correctly because of a coarse approximation.We thus designed a new analysis for LRU instruction that is able to soundly classify some accesses into a new category, called Definitely Unknown, that represents accesses that can lead to both a hit or a miss.For those accesses, one knows for sure that their classification does not result from a coarse approximation but is a consequence of the program structure and cache configuration.By doing so, we also reduce the set of accesses that are candidate for a refined classification using more powerful and more costly analyses.Our main contribution is an analysis that can perform an optimally precise analysis of LRU instruction caches.We use a method called block focusing that allows an analysis to scale by only analyzing one cache block at a time.We thus take advantage of the low number of candidates for refinement left by our Definitely Unknown analysis.This analysis produces an optimal classification of memory accesses at a reasonable cost (a few times the cost of the usual May and Must analyses).We evaluate the impact of our precise cache analysis on the pipeline analysis.Indeed, when the cache analysis is not able to classify an access as Always-Hit or Always-Miss, the pipeline analysis must consider both cases.By providing a more precise memory access classification, we thus reduce the state space explored by the pipeline analysis and hence the WCET analysis time.Aside from this application of precise cache analysis to WCET estimation, we investigate the possibility of using the Definitely Unknown analysis in the domain of security.Indeed, caches can be used as side-channel to extract some sensitive data from a program execution, and we propose a variation of our Definitely Unknown analysis to help a developer finding the source of some information leakage
12
Ruiz, Jordy. "Détermination de propriétés de flot de données pour améliorer les estimations de temps d'exécution pire-cas". Thesis, Toulouse 3, 2017. http://www.theses.fr/2017TOU30285/document.
Texto completoResumen
La recherche d'une borne supérieure au temps d'exécution d'un programme est une partie essentielle du processus de vérification de systèmes temps-réel critiques. Les programmes de tels systèmes ont généralement des temps d'exécution variables et il est difficile, voire impossible, de prédire l'ensemble de ces temps possibles. Au lieu de cela, il est préférable de rechercher une approximation du temps d'exécution pire-cas ou Worst-Case Execution Time (WCET). Une propriété cruciale de cette approximation est qu'elle doit être sûre, c'est-à-dire qu'elle doit être garantie de majorer le WCET. Parce que nous cherchons à prouver que le système en question se termine en un temps raisonnable, une surapproximation est le seul type d'approximation acceptable. La garantie de cette propriété de sûreté ne saurait raisonnablement se faire sans analyse statique, un résultat se basant sur une série de tests ne pouvant être sûr sans un traitement exhaustif des cas d'exécution. De plus, en l'absence de certification du processus de compilation (et de transfert des propriétés vers le binaire), l'extraction de propriétés doit se faire directement sur le code binaire pour garantir leur fiabilité. Toutefois, cette approximation a un coût : un pessimisme - écart entre le WCET estimé et le WCET réel - important entraîne des surcoûts superflus de matériel pour que le système respecte les contraintes temporelles qui lui sont imposées. Il s'agit donc ensuite, tout en maintenant la garantie de sécurité de l'estimation du WCET, d'améliorer sa précision en réduisant cet écart de telle sorte qu'il soit suffisamment faible pour ne pas entraîner des coûts supplémentaires démesurés. Un des principaux facteurs de surestimation est la prise en compte de chemins d'exécution sémantiquement impossibles, dits infaisables, dans le calcul du WCET. Ceci est dû à l'analyse par énumération implicite des chemins ou Implicit Path Enumeration Technique (IPET) qui raisonne sur un surensemble des chemins d'exécution. Lorsque le chemin d'exécution pire-cas ou Worst-Case Execution Path (WCEP), correspondant au WCET estimé, porte sur un chemin infaisable, la précision de cette estimation est négativement affectée. Afin de parer à cette perte de précision, cette thèse propose une technique de détection de chemins infaisables, permettant l'amélioration de la précision des analyses statiques (dont celles pour le WCET) en les informant de l'infaisabilité de certains chemins du programme. Cette information est passée sous la forme de propriétés de flot de données formatées dans un langage d'annotation portable, FFX, permettant la communication des résultats de notre analyse de chemins infaisables vers d'autres analyses. Les méthodes présentées dans cette thèse sont inclues dans le framework OTAWA, développé au sein de l'équipe TRACES à l'IRIT. Elles usent elles-mêmes d'approximations pour représenter les états possibles de la machine en différents points du programmeThe search for an upper bound of the execution time of a program is an essential part of the verification of real-time critical systems. The execution times of the programs of such systems generally vary a lot, and it is difficult, or impossible, to predict the range of the possible times. Instead, it is better to look for an approximation of the Worst-Case Execution Time (WCET). A crucial requirement of this estimate is that it must be safe, that is, it must be guaranteed above the real WCET. Because we are looking to prove that the system in question terminates reasonably quickly, an overapproximation is the only acceptable form of approximation. The guarantee of such a safety property could not sensibly be done without static analysis, as a result based on a battery of tests could not be safe without an exhaustive handling of test cases. Furthermore, in the absence of a certified compiler (and tech- nique for the safe transfer of properties to the binaries), the extraction of properties must be done directly on binary code to warrant their soundness. However, this approximation comes with a cost : an important pessimism, the gap between the estimated WCET and the real WCET, would lead to superfluous extra costs in hardware in order for the system to respect the imposed timing requirements. It is therefore important to improve the precision of the WCET by reducing this gap, while maintaining the safety property, as such that it is low enough to not lead to immoderate costs. A major cause of overestimation is the inclusion of semantically impossible paths, said infeasible paths, in the WCET computation. This is due to the use of the Implicit Path Enumeration Technique (IPET), which works on an superset of the possible execution paths. When the Worst-Case Execution Path (WCEP), corresponding to the estimated WCET, is infeasible, the precision of that estimation is negatively affected. In order to deal with this loss of precision, this thesis proposes an infeasible paths detection technique, enabling the improvement of the precision of static analyses (namely for WCET estimation) by notifying them of the infeasibility of some paths of the program. This information is then passed as data flow properties, formatted in the FFX portable annotation language, and allowing the communication of the results of our infeasible path analysis to other analyses
13
Li, Hanbing. "Extraction and traceability of annotations for WCET estimation". Thesis, Rennes 1, 2015. http://www.theses.fr/2015REN1S040/document.
Texto completoResumen
Les systèmes temps-réel devenaient omniprésents, et jouent un rôle important dans notre vie quotidienne. Pour les systèmes temps-réel dur, calculer des résultats corrects n’est pas la seule exigence, il doivent de surcroît être produits dans un intervalle de temps borné. Connaître le pire cas de temps d’exécution (WCET - Worst Case Execution Time) est nécessaire, et garantit que le système répond à ses contraintes de temps. Pour obtenir des estimations de WCET précises, des annotations sont nécessaires. Ces annotations sont généralement ajoutées au niveau du code source, tandis que l’analyse de WCET est effectuée au niveau du code binaire. L’optimisation du compilateur est entre ces deux niveaux et a un effet sur la structure du code et annotations. Nous proposons dans cette thèse une infrastructure logicielle de transformation, qui pour chaque optimisation transforme les annotations du code source au code binaire. Cette infrastructure est capable de transformer les annotations sans perte d’information de flot. Nous avons choisi LLVM comme compilateur pour mettre en œuvre notre infrastructure. Et nous avons utilisé les jeux de test Mälardalen, TSVC et gcc-loop pour démontrer l’impact de notre infrastructure sur les optimisations du compilateur et la transformation d’annotations. Les résultats expérimentaux montrent que de nombreuses optimisations peuvent être activées avec notre système. Le nouveau WCET estimé est meilleur (plus faible) que l’original. Nous montrons également que les optimisations du compilateur sont bénéfiques pour les systèmes temps-réelReal-time systems have become ubiquitous, and play an important role in our everyday life. For hard real-time systems, computing correct results is not the only requirement. In addition, the worst-case execution times (WCET) are needed, and guarantee that they meet the required timing constraints. For tight WCET estimation, annotations are required. Annotations are usually added at source code level but WCET analysis is performed at binary code level. Compiler optimization is between these two levels and has an effect on the structure of the code and annotations.We propose a transformation framework for each optimization to trace the annotation information from source code level to binary code level. The framework can transform the annotations without loss of flow information. We choose LLVM as the compiler to implement our framework. And we use the Mälardalen, TSVC and gcc-loops benchmarks to demonstrate the impact of our framework on compiler optimizations and annotation transformation. The experimental results show that with our framework, many optimizations can be turned on, and we can still estimate WCET safely. The estimated WCET is better than the original one. We also show that compiler optimizations are beneficial for real-time systems
14
Hermant, Jean-François. "Quelques problèmes et solutions en ordonnancement temps réel pour systèmes répartis". Paris 6, 1999. http://www.theses.fr/1999PA066665.
Texto completo
15
Simard, Catherine. "Analyse d'algorithmes de type Nesterov et leurs applications à l'imagerie numérique". Mémoire, Université de Sherbrooke, 2015. http://hdl.handle.net/11143/7714.
Texto completoResumen
Ce mémoire se veut d'abord un recueil des principales variantes de l'algorithme optimal en pire cas pour la résolution de problèmes convexes et fortement convexes sans contraintes présenté par Yurii Nesterov en 1983 et en 2004. Ces variantes seront présentées dans un cadre unifié et analysées de manière théorique et empirique. On y retrouve une analyse des rôles des différents paramètres composant l'algorithme de base ainsi que de l'influence des constantes L et mu, respectivement la constante de Lipschitz du gradient et la constante de forte convexité de la fonction objectif, sur le comportement des algorithmes. On présentera également une nouvelle variante hybride et nous démontrerons empiriquement qu'elle performe mieux que plusieurs variantes dans la majorité des situations. La comparaison empirique des différentes variantes sur des problèmes sans contraintes utilise un modèle de calcul se basant sur le nombre d'appels à un oracle de premier ordre plutôt que sur le nombre d'itérations. Enfin, une application de ces variantes sur trois instances de problèmes en imagerie numérique ainsi qu'une analyse empirique des résultats obtenus en confrontation avec la méthode optimale FISTA et l'algorithme classique L-BFGS-B viennent clore ce mémoire.
16
Maroneze, André Oliveira. "Certified Compilation and Worst-Case Execution Time Estimation". Thesis, Rennes 1, 2014. http://www.theses.fr/2014REN1S030/document.
Texto completoResumen
Les systèmes informatiques critiques - tels que les commandes de vol électroniques et le contrôle des centrales nucléaires - doivent répondre à des exigences strictes en termes de sûreté de fonctionnement. Nous nous intéressons ici à l'application de méthodes formelles - ancrées sur de solides bases mathématiques - pour la vérification du comportement des logiciels critiques. Plus particulièrement, nous spécifions formellement nos algorithmes et nous les prouvons corrects, à l'aide de l'assistant à la preuve Coq - un logiciel qui vérifie mécaniquement la correction des preuves effectuées et qui apporte un degré de confiance très élevé. Nous appliquons ici des méthodes formelles à l'estimation du Temps d'Exécution au Pire Cas (plus connu par son abréviation en anglais, WCET) de programmes C. Le WCET est une propriété importante pour la sûreté de fonctionnement des systèmes critiques, mais son estimation exige des analyses sophistiquées. Pour garantir l'absence d'erreurs lors de ces analyses, nous avons formellement vérifié une méthode d'estimation du WCET fondée sur la combinaison de deux techniques principales: une estimation de bornes de boucles et une estimation du WCET via la méthode IPET (Implicit Path Enumeration Technique). L'estimation de bornes de boucles est elle-même décomposée en trois étapes : un découpage de programmes, une analyse de valeurs opérant par interprétation abstraite, et une méthode de calcul de bornes. Chacune de ces étapes est formellement vérifiée dans un chapitre qui lui est dédiée. Le développement a été intégré au compilateur C formellement vérifié CompCert. Nous prouvons que le résultat de l'estimation est correct et nous évaluons ses performances dans des ensembles de benchmarks de référence dans le domaine. Les contributions de cette thèse incluent la formalisation des techniques utilisées pour estimer le WCET, l'outil d'estimation lui-même (obtenu à partir de la formalisation), et l'évaluation expérimentale des résultats. Nous concluons que le développement fondé sur les méthodes formelles permet d'obtenir des résultats intéressants en termes de précision, mais il exige des précautions particulières pour s'assurer que l'effort de preuve reste maîtrisable. Le développement en parallèle des spécifications et des preuves est essentiel à cette fin. Les travaux futurs incluent la formalisation de modèles de coût matériel, ainsi que le développement d'analyses plus sophistiquées pour augmenter la précision du WCET estiméSafety-critical systems - such as electronic flight control systems and nuclear reactor controls - must satisfy strict safety requirements. We are interested here in the application of formal methods - built upon solid mathematical bases - to verify the behavior of safety-critical systems. More specifically, we formally specify our algorithms and then prove them correct using the Coq proof assistant - a program capable of mechanically checking the correctness of our proofs, providing a very high degree of confidence. In this thesis, we apply formal methods to obtain safe Worst-Case Execution Time (WCET) estimations for C programs. The WCET is an important property related to the safety of critical systems, but its estimation requires sophisticated techniques. To guarantee the absence of errors during WCET estimation, we have formally verified a WCET estimation technique based on the combination of two main methods: a loop bound estimation and the WCET estimation via the Implicit Path Enumeration Technique (IPET). The loop bound estimation itself is decomposed in three steps: a program slicing, a value analysis based on abstract interpretation, and a loop bound calculation stage. Each stage has a chapter dedicated to its formal verification. The entire development has been integrated into the formally verified C compiler CompCert. We prove that the final estimation is correct and we evaluate its performances on a set of reference benchmarks. The contributions of this thesis include (a) the formalization of the techniques used to estimate the WCET, (b) the estimation tool itself (obtained from the formalization), and (c) the experimental evaluation. We conclude that our formally verified development obtains interesting results in terms of precision, but it requires special precautions to ensure the proof effort remains manageable. The parallel development of specifications and proofs is essential to this end. Future works include the formalization of hardware cost models, as well as the development of more sophisticated analyses to improve the precision of the estimated WCET
17
Ballabriga, Clément. "Vérification de contraintes temporelles strictes sur des programmes par composition d'analyses partielles". Toulouse 3, 2010. http://thesesups.ups-tlse.fr/1001/.
Texto completoResumen
Les systèmes temps-réel critiques doivent impérativement obéir à des contraintes temporelles strictes. Le respect de ces contraintes doit donc être prouvé, et le calcul de pire temps d'exécution (WCET ou Worst Case Execution Time) joue un rôle important dans cette preuve. Le calcul de WCET par analyse statique est généralement réalisé sur un programme entier. Ceci présente deux inconvénients : la plupart de ces méthodes de calcul voient leur temps d'exécution augmenter de manière non linéaire par rapport à la taille de la tâche à analyser, et un problème se pose lorsque cette tâche est constituée de plusieurs composants (dont certains ne sont pas disponibles au moment de l'analyse). Il est donc nécessaire d'introduire une approche d'analyse partielle, permettant d'analyser séparément les composants d'un programme, produisant un résultat de WCET partiel pour chaque composant. Ces résultats partiels peuvent ensuite être composés pour obtenir le WCET du programme. Le calcul de WCET comporte plusieurs analyses dont les résultats sont exprimés sous forme d'un système ILP, qui doit ensuite être résolu pour obtenir le WCET. Chaque analyse doit être adaptée pour faire de l'analyse partielle. Cette adaptation sera illustrée à l'aide de diverses analyses existantes, et une formulation générale pour l'analyse partielle sera donnée. Il sera ensuite montré qu'il est possible d'utiliser l'analyse partielle afin d'accélérer la résolution ILP. L'expérimentation montre que l'analyse partielle permet de réduire le temps de calcul et de traiter le cas des programmes avec composants, sans rajouter trop de pessimismeHard real-time systems are subject to real-time constraints. It is necessary to prove that no constraint violation can occur, and the WCET (Worst Cast Execution Time) computation plays an important role in this proof. The WCET computation by static analysis is traditionally performed on a complete program. This approach has two drawbacks: most computation methods run in non linear time with respect to the size of the analysed program, and problems arise when this program is made up of multiple components (some components may be unavailable at analysis time). Therefore, it is necessary to introduce a partial analysis method, in order to process separately each program component, producing partial WCET results for each component. The partial results can then be composed to get the WCET of the whole program. The WCET computation by IPET (Implicit Path Enumeration Technique) involves several analyses, each one contributes to an ILP system, and this system is solved to get the WCET. To perform partial analysis, each analysis involved in WCET computation must be adapted. We illustrate this process by taking the example of several existing analyses, then a more general framework for partial analysis is described. Next, we show that it is possible to take advantage of partial analysis to speed up ILP solving. Our experimentations show that the partial analysis leads to faster WCET computation time and allows handling programs made up of components, without adding too much overestimation
18
Baga, Yohan. "Analyse de Flux de Trames AFDX en Réception et Méthode d’Optimisation Mémoire". Thesis, Cergy-Pontoise, 2018. http://www.theses.fr/2018CERG0957/document.
Texto completoResumen
L’essor des réseaux AFDX comme infrastructure de communication entre les équipements de bord des aéronefs civils motive de nombreux travaux de recherche pour réduire les délais de communication tout en garantissant un haut niveau de déterminisme et de qualité de service. Cette thèse traite de l’effet des accolements de trames sur l’End System de réception, notamment sur le buffer interne afin de garantir une non perte de trames et un dimensionnement mémoire optimal. Une modélisation pire cas du flux de trames est réalisée selon une première méthode pessimiste, basée sur un flux de trames périodiques ; puis une seconde, plus optimiste, basée sur des intervalles de réception et un placement de trames itératif. Une étude probabiliste met en œuvre des distributions gaussiennes pour évaluer les probabilités d’occurrences des pires cas d’accolements et apporte un éclairage qui ouvre une discussion sur la pertinence de ne considérer que la modélisation pire cas pour dimensionner le buffer de réception. Un gain mémoire supplémentaire peut être obtenu par la mise en œuvre de la compression sans perte LZWThe rise of AFDX networks as a communication infrastructure between on-board equipment of civil aircraft motivates many research projects to reduce communication delays while guaranteeing a high level of determination and quality of service. This thesis deals with the effect of the back-ot-back frame reception on the reception End System, in particular, on the internal buffer, in order to guarantee a non-loss of frames and optimal memory dimensioning. A worst-case modeling of the frame flow is carried out according to a first pessimistic method, based on a periodic frame flow. Then a more optimistic method is presented based on the reception intervals and an iterative frame placement. A probabilistic study implements Gaussian distributions to evaluate the occurrence probabilities of the worst back-to-back frames and provides an illumination that opens a discussion on the relevance of not considering the worst-case modeling to size the reception buffer. Additional memory gain can be achieved by implementing LZW lossless compression
19
Rihani, Hamza. "Analyse temporelle des systèmes temps-réels sur architectures pluri-coeurs". Thesis, Université Grenoble Alpes (ComUE), 2017. http://www.theses.fr/2017GREAM074/document.
Texto completoResumen
La prédictibilité est un aspect important des systèmes temps-réel critiques. Garantir la fonctionnalité de ces systèmespasse par la prise en compte des contraintes temporelles. Les architectures mono-cœurs traditionnelles ne sont plussuffisantes pour répondre aux besoins croissants en performance de ces systèmes. De nouvelles architectures multi-cœurssont conçues pour offrir plus de performance mais introduisent d'autres défis. Dans cette thèse, nous nous intéressonsau problème d’accès aux ressources partagées dans un environnement multi-cœur.La première partie de ce travail propose une approche qui considère la modélisation de programme avec des formules desatisfiabilité modulo des théories (SMT). On utilise un solveur SMT pour trouverun chemin d’exécution qui maximise le temps d’exécution. On considère comme ressource partagée un bus utilisant unepolitique d’accès multiple à répartition dans le temps (TDMA). On explique comment la sémantique du programme analyséet le bus partagé peuvent être modélisés en SMT. Les résultats expérimentaux montrent une meilleure précision encomparaison à des approches simples et pessimistes.Dans la deuxième partie, nous proposons une analyse de temps de réponse de programmes à flot de données synchroness'exécutant sur un processeur pluri-cœur. Notre approche calcule l'ensemble des dates de début d'exécution et des tempsde réponse en respectant la contrainte de dépendance entre les tâches. Ce travail est appliqué au processeur pluri-cœurindustriel Kalray MPPA-256. Nous proposons un modèle mathématique de l'arbitre de bus implémenté sur le processeur. Deplus, l'analyse de l'interférence sur le bus est raffinée en prenant en compte : (i) les temps de réponseet les dates de début des tâches concurrentes, (ii) le modèle d'exécution, (iii) les bancsmémoires, (iv) le pipeline des accès à la mémoire. L'évaluation expérimentale est réalisé sur desexemples générés aléatoirement et sur un cas d'étude d'un contrôleur de volPredictability is of paramount importance in real-time and safety-critical systems, where non-functional properties --such as the timing behavior -- have high impact on the system's correctness. As many safety-critical systems have agrowing performance demand, classical architectures, such as single-cores, are not sufficient anymore. One increasinglypopular solution is the use of multi-core systems, even in the real-time domain. Recent many-core architectures, such asthe Kalray MPPA, were designed to take advantage of the performance benefits of a multi-core architecture whileoffering certain predictability. It is still hard, however, to predict the execution time due to interferences on sharedresources (e.g., bus, memory, etc.).To tackle this challenge, Time Division Multiple Access (TDMA) buses are often advocated. In the first part of thisthesis, we are interested in the timing analysis of accesses to shared resources in such environments. Our approach usesSatisfiability Modulo Theory (SMT) to encode the semantics and the execution time of the analyzed program. To estimatethe delays of shared resource accesses, we propose an SMT model of a shared TDMA bus. An SMT-solver is used to find asolution that corresponds to the execution path with the maximal execution time. Using examples, we show how theworst-case execution time estimation is enhanced by combining the semantics and the shared bus analysis in SMT.In the second part, we introduce a response time analysis technique for Synchronous Data Flow programs. These are mappedto multiple parallel dependent tasks running on a compute cluster of the Kalray MPPA-256 many-core processor. Theanalysis we devise computes a set of response times and release dates that respect the constraints in the taskdependency graph. We derive a mathematical model of the multi-level bus arbitration policy used by the MPPA. Further,we refine the analysis to account for (i) release dates and response times of co-runners, (ii)task execution models, (iii) use of memory banks, (iv) memory accesses pipelining. Furtherimprovements to the precision of the analysis were achieved by considering only accesses that block the emitting core inthe interference analysis. Our experimental evaluation focuses on randomly generated benchmarks and an avionics casestudy
20
Silantiev, Alexey. "Groupes quantiques associés aux courbes rationnelles et elliptiques et leurs applications". Angers, 2008. http://www.theses.fr/2008ANGE0061.
Texto completoResumen
Le contexte général dans lequel s'inscrivent les travaux développés dans ce mémoire est le contrôle des processus industriels complexes. Ces travaux proposent des nouvelles techniques d'amélioration du contrôle statistique des processus non gaussiens : la carte de contrôle avec des paramètres variables et la carte de contrôle théorique pour la loi de distribution de Rayleigh. Un modèle d'intégration des outils des domaines de l'APC (Automatic Process Control) et de la MSP est proposée et ensuite analysé par le biais des deux modèles de processus réelThe general context of the work developed here is the control of complex industrial processes. These works offer new methods of improvement of statistical process control for non Gaussian distribution : the control chart with variable parameters and the theoretical control chart for the Rayleigh distribution. A model of integration of the APC (Automatic Process Control) and MSP technics is introduced, and then analyzed by using the models of two real process
21
Henry, Julien. "Static analysis of program by Abstract Interpretation and Decision Procedures". Thesis, Grenoble, 2014. http://www.theses.fr/2014GRENM037/document.
Texto completoResumen
L'analyse statique de programme a pour but de prouver automatiquement qu'un programme vérifie certaines propriétés. L'interprétation abstraite est un cadre théorique permettant de calculer des invariants de programme. Ces invariants sont des propriétés sur les variables du programme vraies pour toute exécution. La précision des invariants calculés dépend de nombreux paramètres, en particulier du domaine abstrait et de l'ordre d'itération utilisés pendant le calcul d'invariants. Dans cette thèse, nous proposons plusieurs extensions de cette méthode qui améliorent la précision de l'analyse.Habituellement, l'interprétation abstraite consiste en un calcul de point fixe d'un opérateur obtenu après convergence d'une séquence ascendante, utilisant un opérateur appelé élargissement. Le point fixe obtenu est alors un invariant. Il est ensuite possible d'améliorer cet invariant via une séquence descendante sans élargissement. Nous proposons une méthode pour améliorer un point fixe après la séquence descendante, en recommençant une nouvelle séquence depuis une valeur initiale choisie judiscieusement. L'interprétation abstraite peut égalementêtre rendue plus précise en distinguant tous les chemins d'exécution du programme, au prix d'une explosion exponentielle de la complexité. Le problème de satisfiabilité modulo théorie (SMT), dont les techniques de résolution ont été grandement améliorée cette décennie, permettent de représenter ces ensembles de chemins implicitement. Nous proposons d'utiliser cette représentation implicite à base de SMT et de les appliquer à des ordres d'itération de l'état de l'art pour obtenir des analyses plus précises.Nous proposons ensuite de coupler SMT et interprétation abstraite au sein de nouveaux algorithmes appelés Modular Path Focusing et Property-Guided Path Focusing, qui calculent des résumés de boucles et de fonctions de façon modulaire, guidés par des traces d'erreur. Notre technique a différents usages: elle permet de montrer qu'un état d'erreur est inatteignable, mais également d'inférer des préconditions aux boucles et aux fonctions.Nous appliquons nos méthodes d'analyse statique à l'estimation du temps d'exécution pire cas (WCET). Dans un premier temps, nous présentons la façon d'exprimer ce problème via optimisation modulo théorie, et pourquoi un encodage naturel du problème en SMT génère des formules trop difficiles pour l'ensemble des solveurs actuels. Nous proposons un moyen simple et efficace de réduire considérablement le temps de calcul des solveurs SMT en ajoutant aux formules certaines propriétés impliquées obtenues par analyse statique. Enfin, nous présentons l'implémentation de Pagai, un nouvel analyseur statique pour LLVM, qui calcule des invariants numériques grâce aux différentes méthodes décrites dans cette thèse. Nous avons comparé les différentes techniques implémentées sur des programmes open-source et des benchmarks utilisés par la communautéStatic program analysis aims at automatically determining whether a program satisfies some particular properties. For this purpose, abstract interpretation is a framework that enables the computation of invariants, i.e. properties on the variables that always hold for any program execution. The precision of these invariants depends on many parameters, in particular the abstract domain, and the iteration strategy for computing these invariants. In this thesis, we propose several improvements on the abstract interpretation framework that enhance the overall precision of the analysis.Usually, abstract interpretation consists in computing an ascending sequence with widening, which converges towards a fixpoint which is a program invariant; then computing a descending sequence of correct solutions without widening. We describe and experiment with a method to improve a fixpoint after its computation, by starting again a new ascending/descending sequence with a smarter starting value. Abstract interpretation can also be made more precise by distinguishing paths inside loops, at the expense of possibly exponential complexity. Satisfiability modulo theories (SMT), whose efficiency has been considerably improved in the last decade, allows sparse representations of paths and sets of paths. We propose to combine this SMT representation of paths with various state-of-the-art iteration strategies to further improve the overall precision of the analysis.We propose a second coupling between abstract interpretation and SMT in a program verification framework called Modular Path Focusing, that computes function and loop summaries by abstract interpretation in a modular fashion, guided by error paths obtained with SMT. Our framework can be used for various purposes: it can prove the unreachability of certain error program states, but can also synthesize function/loop preconditions for which these error states are unreachable.We then describe an application of static analysis and SMT to the estimation of program worst-case execution time (WCET). We first present how to express WCET as an optimization modulo theory problem, and show that natural encodings into SMT yield formulas intractable for all current production-grade solvers. We propose an efficient way to considerably reduce the computation time of the SMT-solvers by conjoining to the formulas well chosen summaries of program portions obtained by static analysis.We finally describe the design and the implementation of Pagai,a new static analyzer working over the LLVM compiler infrastructure,which computes numerical inductive invariants using the various techniques described in this thesis.Because of the non-monotonicity of the results of abstract interpretation with widening operators, it is difficult to conclude that some abstraction is more precise than another based on theoretical local precision results. We thus conducted extensive comparisons between our new techniques and previous ones, on a variety of open-source packages and benchmarks used in the community
22
Naji, Amine. "Timing analysis for time-predictable architectures". Electronic Thesis or Diss., Sorbonne université, 2019. http://www.theses.fr/2019SORUS282.
Texto completoResumen
En raison de la complexité croissante des architectures matérielles, l'analyse temporelle du logiciel temps-réel devient de plus en plus complexe et imprécise. Les architectures prédictibles des ordinateurs ont donc été proposées afin d'assurer un support matériel dédié à analyse temporelle. The but est de fournir des estimations plus précises de pire-temps d'exécution de programmes (WCET), tout en gardant le coût et la compexité de l'analyse minimal. Ces estimations proviennent typiquement d'outils dédiés à l'analyse WCET. L'émergence de ces architectures spécialisées est, toutefois, assez récent. Bien que plusieurs designs d'architectures ont été proposés, des efforts sont encore nécessaires pour évaluer leurs capacités à améliorer les performances pire cas. Pour plusieurs composants matériels prédictibles, l'analyse temporelle est manquante ou partiellement supportée. En conséquence, les architectures prédictibles sont à peine supportées dans les outils d’analyse WCET existants. Dans cette thèse, nous nous intéressons au processeur prédictible Patmos. Le support existant autour de la plateforme permet une exploration effective des techniques d'optimisation pour les performances pire cas. Les principales contributions comprennent: (1) Une gestion des prédicats dans le flux d'anayse WCET, (2) Une comparaison de la précision des analyses d'occupancy pour le stack cache, (3) Une analyse des coûts de préemption pour le stack cache, (4) Des mécanismes de préemption pour le stack cache, et (5) Des techniques de prefetching pour le stack cache. En outre, nous présentons Odyssey -- notre outil d'analyse WCET pour le processeur PatmosWith the rising complexity of the underlying computer hardware, the analysis of the timing behavior of real-time software is becoming more and more complex and imprecise. Time-predictable computer architectures thus have been proposed to provide hardware support for timing analysis. The goal is to deliver tighter worst-case execution time (WCET) estimates while keeping the analysis overhead minimal. These estimates are typically provided by standalone WCET analysis tools. The emergence of time-predictable architectures is, however, quite recent. While several designs have been introduced, efforts are still needed to assess their effectiveness in actually enhancing the worst-case performance. For many time-predictable hardware, timing analysis is either non-existing or lacking proper support. Consequently, time-predictable architectures are barely supported in existing WCET analysis tools. The general contribution of this thesis is to help filling this gap and turning some opportunities into concrete advantages. For this, we take interest in the Patmos processor. The already existing support around Patmos allows for an effective exploration of techniques to enhance the worst-case performance. Main contributions include: (1) Handling of predicated execution in timing analysis, (2) Comparison of the precision of stack cache occupancy analyses, (3) Analysis of preemption costs for the stack cache, (4) Preemption mechanisms for the stack cache, and (5) Prefetching-like technique for the stack cache. In addition, we present our WCET analysis tool Odyssey, which implements timing analyses for Patmos
23
Delbot, François. "Au delà de l'évaluation en pire cas : comparaison et évaluation en moyenne de processus d'optimisation pour le problème du vertex cover et des arbres de connexion de groupes dynamiques". Phd thesis, Université d'Evry-Val d'Essonne, 2009. http://tel.archives-ouvertes.fr/tel-00927315.
Texto completoResumen
La théorie de la complexité distingue les problèmes que l'on sait résoudre en un temps polynomial en la taille des données (que l'on peut qualifier de raisonnable), des problèmes NP-complets, qui nécessitent (en l'état actuel des connaissances) un temps de résolution exponentiel en la taille des données (que l'on peut qualifier de déraisonnable). C'est pour cette raison que la communauté scientifique s'est tournée vers les algorithmes (polynomiaux) d'approximation dont la mesure de qualité se fait le plus souvent grâce au rapport d'approximation en pire cas (pour un problème de minimisation de taille, un algorithme a un rapport d'approximation de k si la taille de toute solution pouvant être retournée par l'algorithme est inférieure ou égale à k fois la taille de la solution optimale). Dans la littérature, on en vient à considérer qu'un algorithme est plus performant qu'un autre lorsqu'il possède un plus petit rapport d'approximation en pire cas. Cependant, il faut être conscient que cette mesure, désormais "classique", ne prend pas en compte la réalité de toutes les exécutions possibles d'un algorithme (elle ne considère que les exécutions menant à la plus mauvaise solution). Mes travaux de thèse ont pour objet de mieux "capturer" le comportement des algorithmes d'approximation en allant plus loin que le simple rapport d'approximation en pire cas, et ce sur deux problèmes distincts : I. Le problème du Vertex Cover En montrant que les performances moyennes d'un algorithme peuvent être décorélées des performances en pire cas. Par exemple, nous avons montré que dans la classe des graphes spécialement conçus pour le piéger en pire cas, l'algorithme glouton "Maximum Degree Greedy" retourne, en moyenne, des solutions dont la taille tend vers l'optimum lorsque n tend vers l'infini. En évaluant les performances moyennes d'un algorithme. Nous avons prouvé que l'algorithme online présenté par Demange et Paschos en 2005 (dont le rapport d'approximation en pire cas est égal au degré maximum du graphe) est au plus 2-approché en moyenne dans n'importe quel graphe. Ce résultat, combiné à d'autres, montre que cet algorithme est "en pratique" meilleur que la plupart des algorithmes 2-approchés connus, malgré un mauvais rapport d'approximation en pire cas . En comparant les performances de différents algorithmes (analytiquement et expérimentalement). Nous avons proposé un algorithme de liste et nous avons prouvé analytiquement qu'il retourne toujours une meilleure solution que celle construite par un autre algorithme de liste récent [ORL 2006] quand ils traitent la même liste de sommets (dans certains graphes particuliers, la différence de taille peut être arbitrairement grande). Nous avons également comparé analytiquement (en utilisant des outils comme les séries génératrices) les performances moyennes de six algorithmes sur les chemins. Nous les avons ensuite expérimentées sur un grand nombre de graphes de diverses familles bien choisies. On constate dans ces études que les algorithmes 2-approchés étudiés sont ceux qui obtiennent les plus mauvaises performances en moyenne et que ceux qui ont les meilleurs comportements moyens ont de mauvais rapports d'approximation (fonction du degré max. du graphe). Tous ces résultats montrent que le rapport d'approximation en pire cas n'est pas toujours suffisant pour caractériser l'intégralité de la qualité d'un algorithme et que d'autres analyses (en moyenne notamment) doivent être effectuées pour en faire le tour. II. Le problème de la connexion de groupes dynamiques dans les réseaux Nous avons analysé un processus de mise-à-jour d'un arbre connectant dans un réseau un groupe que les membres peuvent rejoindre ou quitter à tout moment. Notre processus possède de bonnes propriétés : il est simple à implémenter et il garantit, après chaque opération d'ajout ou de retrait, que le diamètre de l'arbre est au plus 2 fois l'optimal. Cependant, pour obtenir cette garantie, nous devons autoriser la reconstruction totale de l'arbre lorsque le membre identifié comme sa racine quitte le groupe. Ces étapes de reconstruction sont très coûteuses et nous cherchons donc à en évaluer le nombre. Des travaux précédents montraient que dans le pire cas, il faut reconstruire (quasiment) à chaque étape pour conserver la garantie sur le diamètre. Nous montrons dans cette thèse (en utilisant les marches aléatoires, etc.) que, en fonction de certains paramètres du problèmes (comme les probabilités associées aux opérations d'ajout et de retrait), l'espérance du nombre de reconstructions est soit logarithmique en le nombre d'évènements (ajout ou retrait), soit constant. Ce résultat montre que le comportement moyen est très bon (malgré un pire cas très défavorable) et que notre processus de mise-à-jour peut être une solution viable en pratique.
24
Barré, Mathieu. "Worst-case analysis of efficient first-order methods". Electronic Thesis or Diss., Université Paris sciences et lettres, 2021. http://www.theses.fr/2021UPSLE064.
Texto completoResumen
De nombreuses applications modernes reposent sur la résolution de problèmes d’optimisations (par exemple, en biologie numérique, en mécanique, en finance), faisant des méthodes d’optimisation des outils essentiels dans de nombreux domaines scientifiques. Apporter des garanties sur le comportement de ces méthodes constitue donc un axe de recherche important. Une façon classique d’analyser un algorithme d’optimisation consiste à étudier son comportement dans le pire cas. C'est-à-dire, donner des garanties sur son comportement (par exemple sa vitesse de convergence) qui soient indépendantes de la fonction en entrée de l’algorithme et vraies pour toutes les fonctions dans une classe donnée. Cette thèse se concentre sur l’analyse en pire cas de quelques méthodes du premier ordre réputées pour leur efficacité. Nous commençons par étudier les méthodes d’accélération d’Anderson, pour lesquelles nous donnons de nouvelles bornes de pire cas qui permettent de garantir précisément et explicitement quand l’accélération a lieu. Pour obtenir ces garanties, nous fournissons des majorations sur une variation du problème d’optimisation polynomiale de Tchebychev, dont nous pensons qu’elles constituent un résultat indépendant. Ensuite, nous prolongeons l’étude des Problèmes d’Estimation de Performances (PEP), développés à l’origine pour analyser les algorithmes d’optimisation à pas fixes, à l’analyse des méthodes adaptatives. En particulier, nous illustrons ces développements à travers l’étude des comportements en pire cas de la descente de gradient avec pas de Polyak, qui utilise la norme des gradients et les valeurs prises par la fonction objectif, ainsi que d’une nouvelle version accélérée. Nous détaillons aussi cette approche sur d’autres algorithmes adaptatifs standards. Enfin, la dernière contribution de cette thèse est de développer plus avant la méthodologie PEP pour l’analyse des méthodes du premier ordre se basant sur des opérations proximales inexactes. En utilisant cette approche, nous définissons des algorithmes dont les garanties en pire cas ont été optimisées et nous fournissons des analyses de pire cas pour quelques méthodes présentes dans la littératureMany modern applications rely on solving optimization problems (e.g., computational biology, mechanics, finance), establishing optimization methods as crucial tools in many scientific fields. Providing guarantees on the (hopefully good) behaviors of these methods is therefore of significant interest. A standard way of analyzing optimization algorithms consists in worst-case reasoning. That is, providing guarantees on the behavior of an algorithm (e.g. its convergence speed), that are independent of the function on which the algorithm is applied and true for every function in a particular class. This thesis aims at providing worst-case analyses of a few efficient first-order optimization methods. We start by the study of Anderson acceleration methods, for which we provide new explicit worst-case bounds guaranteeing precisely when acceleration occurs. We obtained these guarantees by providing upper bounds on a variation of the classical Chebyshev optimization problem on polynomials, that we believe of independent interest. Then, we extend the Performance Estimation Problem (PEP) framework, that was originally designed for principled analyses of fixed-step algorithms, to study first-order methods with adaptive parameters. This is illustrated in particular through the worst-case analyses of the canonical gradient method with Polyak step sizes that use gradient norms and function values information, and of an accelerated version of it. The approach is also presented on other standard adaptive algorithms. Finally, the last contribution of this thesis is to further develop the PEP methodology for analyzing first-order methods relying on inexact proximal computations. Using this framework, we produce algorithms with optimized worst-case guarantees and provide (numerical and analytical) worst-case bounds for some standard algorithms in the literature
25
Louise, Stéphane. "Calcul de majorants sûrs de temps d'exécution au pire pour des tâches d'applications temps-réels critiques, pour des systèmes disposants de caches mémoire". Phd thesis, Université Paris Sud - Paris XI, 2002. http://tel.archives-ouvertes.fr/tel-00695930.
Texto completoResumen
Ce mémoire présente une nouvelle approche pour le calcul de temps d'exécution au pire (WCET) de tâche temps-réel critique, en particulier en ce qui concerne les aléas dus aux caches mémoire. Le point général est fait sur la problématique et l'état de l'art en la matière, mais l'accent est mis sur la théorie elle-même et son formalisme, d'abord dans le cadre monotâche puis dans le cadre multitâche. La méthode utilisée repose sur une technique d'interprétation abstraite, comme la plupart des autres méthodes de calcul de WCET, mais le formalisme est dans une approche probabiliste (bien que déterministe dans le cadre monotâche) de par l'utilisation de chaînes de Markov. La généralisation au cadre multitâche utilise les propriétés proba- bilistes pour faire une évaluation pessimiste d'un WCET et d'un écart type au pire, grâce à une modification astucieuse du propagateur dans ce cadre. Des premières évaluations du modèle, codées à la main à partir des résultats de compilation d'applications assez simples montrent des résultats promet- teurs quant à l'application du modèle sur des programmes réels en vraie grandeur.
26
Varoumas, Steven. "Modèles de programmation de haut niveau pour microcontrôleurs à faibles ressources". Electronic Thesis or Diss., Sorbonne université, 2019. http://www.theses.fr/2019SORUS394.
Texto completoResumen
Les microcontrôleurs sont des circuits imprimés programmables nichés dans de nombreux objets de notre quotidien. En raison de leurs ressources limitées, ils sont souvent programmés dans des langages de bas niveau comme le C, ou en langage assembleur. Ces derniers n'offrent pas les mêmes abstractions et les mêmes garanties que des langages de haut niveau, comme OCaml. Cette thèse propose alors un ensemble de solutions destinées à enrichir la programmation de microcontrôleurs avec des paradigmes de programmation de plus haut niveau. Ces solutions apportent une montée en abstraction progressive, permettant notamment de réaliser des programmes indépendants du matériel utilisé. Nous présentons ainsi une première abstraction du matériel prenant la forme d’une machine virtuelle OCaml, qui permet de profiter des nombreux avantages du langage tout conservant une faible empreinte mémoire. Nous étendons par la suite OCaml avec un modèle de programmation synchrone inspiré du langage Lustre et permettant d'abstraire les aspects concurrents d’un programme. Une spécification formelle du langage est donnée, et plusieurs propriétés de typage sont par la suite vérifiées. Les abstractions offertes par nos travaux induisent par ailleurs la portabilité de certaines analyses statiques pouvant être réalisées sur le bytecode des programmes. Une telle analyse, servant à estimer le temps d’exécution pire-cas d’un programme synchrone, est alors proposée. L'ensemble des propositions de cette thèse constitue une chaîne complète de développement, et plusieurs exemples d’applications concrètes illustrant l'intérêt des solutions offertes sont alors présentéesMicrocontrollers are programmable integrated circuit embedded in multiple everyday objects. Due to their scarce resources, they often are programmated using low-level languages such as C or assembly languages. These languages don't provide the same abstractions and guarantees than higher-level programming languages, such as OCaml. This thesis offers a set of solutions aimed at extending microcontrollers programming with high-level programming paradigms. These solutions provide multiple abstraction layers which, in particular, enable the development of portable programs, free from the specifics of the hardware. We thus introduce a layer of hardware abstraction through an OCaml virtual machine, that enjoys the multiple benefits of the language, while keeping a low memory footprint. We then extend the OCaml language with a synchronous programming model inspired from the Lustre dataflow language, which offers abstraction over the concurrent aspects of a program. The language is then formally specified and various typing properties are proven. Moreover, the abstractions offered by our work induce portability of some static analyses that can be done over the bytecode of programs. We thus propose such an analysis that consists of estimating the worst case execution time (WCET) of a synchronous program. All the propositions of this thesis form a complete development toolchain, and several practical examples that illustrate the benefits of the given solutions are thus provided
27
Babus, Florina. "Contrôle de processus industriels complexes et instables par le biais des techniques statistiques et automatiques". Phd thesis, Université d'Angers, 2008. http://tel.archives-ouvertes.fr/tel-00535668.
Texto completoResumen
Le contexte général dans lequel s'inscrivent les travaux développés dans ce mémoire est le contrôle des processus industriels complexes. Ces travaux proposent des nouvelles techniques d'amélioration du contrôle statistique des processus non gaussiens : la carte de contrôle avec des paramètres variables et la carte de contrôle théorique pour la loi de distribution de Rayleigh. Un modèle d'intégration des outils des domaines de l'APC ( Automatic Process Control ) et de la MSP est proposée et ensuite analysée par le biais des deux modèles de processus réel.
28
Giroudot, Frédéric. "NoC-based Architectures for Real-Time Applications : Performance Analysis and Design Space Exploration". Thesis, Toulouse, INPT, 2019. https://oatao.univ-toulouse.fr/25921/1/Giroudot_Frederic.pdf.
Texto completoResumen
Les architectures mono-processeur montrent leurs limites en termes de puissance de calcul face aux besoins des systèmes actuels. Bien que les architectures multi-cœurs résolvent partiellement ce problème, elles utilisent en général des bus pour interconnecter les cœurs, et cette solution ne passe pas à l'échelle. Les architectures dites pluri-cœurs ont été proposées pour palier les limitations des processeurs multi-cœurs. Elles peuvent réunir jusqu'à des centaines de cœurs sur une seule puce, organisés en dalles contenant une ou plusieurs entités de calcul. La communication entre les cœurs se fait généralement au moyen d'un réseau sur puce constitué de routeurs reliés les uns aux autres et permettant les échanges de données entre dalles. Cependant, ces architectures posent de nombreux défis, en particulier pour les applications temps-réel. D'une part, la communication via un réseau sur puce provoque des scénarios de blocage entre flux, ce qui complique l'analyse puisqu'il devient difficile de déterminer le pire cas. D'autre part, exécuter de nombreuses applications sur des systèmes sur puce de grande taille comme des architectures pluri-cœurs rend la conception de tels systèmes particulièrement complexe. Premièrement, cela multiplie les possibilités d'implémentation qui respectent les contraintes fonctionnelles, et l'exploration d'architecture résultante est plus longue. Deuxièmement, une fois une architecture matérielle choisie, décider de l'attribution de chaque tâche des applications à exécuter aux différents cœurs est un problème difficile, à tel point que trouver une une solution optimale en un temps raisonnable n'est pas toujours possible. Ainsi, nos premières contributions s'intéressent à cette nécessité de pouvoir calculer des bornes fiables sur le pire cas des latences de transmission des flux de données empruntant des réseaux sur puce dits "wormhole". Nous proposons un modèle analytique, BATA, prenant en compte la taille des mémoires tampon des routeurs et applicable à une configuration de flux de données périodiques générant un paquet à la fois. Nous étendons ensuite le domaine d'applicabilité de BATA pour couvrir un modèle de traffic plus général ainsi que des architectures hétérogènes. Cette nouvelle méthode, appelée G-BATA, est basée sur une structure de graphe pour capturer les interférences possibles entre flux de données. Elle permet également de diminuer le temps de calcul de l'analyse, améliorant la capacité de l'approche à passer à l'échelle. Dans une seconde partie, nous proposons une méthode pour la conception d'applications temps-réel s'exécutant sur des plateformes pluri-cœurs. Cette méthode intègre notre modèle d'analyse G-BATA dans un processus de conception systématique, faisant en outre intervenir un outil de modélisation et de simulation de systèmes reposant sur des concepts d'ingénierie dirigée par les modèles, TTool, et un logiciel pour l'analyse de performance pire-cas des réseaux, WoPANets. Enfin, nous proposons une validation de nos contributions grâce à (a) une série d'expériences sur une plateforme physique et (b) deux études de cas d'applications réelle; le système de contrôle d'un véhicule autonome et une application de décodeur 5GMonoprocessor architectures have reached their limits in regard to the computing power they offer vs the needs of modern systems. Although multicore architectures partially mitigate this limitation and are commonly used nowadays, they usually rely on intrinsically non-scalable buses to interconnect the cores. The manycore paradigm was proposed to tackle the scalability issue of bus-based multicore processors. It can scale up to hundreds of processing elements (PEs) on a single chip, by organizing them into computing tiles (holding one or several PEs). Intercore communication is usually done using a Network-on-Chip (NoC) that consists of interconnected onchip routers allowing communication between tiles. However, manycore architectures raise numerous challenges, particularly for real-time applications. First, NoC-based communication tends to generate complex blocking patterns when congestion occurs, which complicates the analysis, since computing accurate worst-case delays becomes difficult. Second, running many applications on large Systems-on-Chip such as manycore architectures makes system design particularly crucial and complex. On one hand, it complicates Design Space Exploration, as it multiplies the implementation alternatives that will guarantee the desired functionalities. On the other hand, once a hardware architecture is chosen, mapping the tasks of all applications on the platform is a hard problem, and finding an optimal solution in a reasonable amount of time is not always possible. Therefore, our first contributions address the need for computing tight worst-case delay bounds in wormhole NoCs. We first propose a buffer-aware worst-case timing analysis (BATA) to derive upper bounds on the worst-case end-to-end delays of constant-bit rate data flows transmitted over a NoC on a manycore architecture. We then extend BATA to cover a wider range of traffic types, including bursty traffic flows, and heterogeneous architectures. The introduced method is called G-BATA for Graph-based BATA. In addition to covering a wider range of assumptions, G-BATA improves the computation time; thus increases the scalability of the method. In a second part, we develop a method addressing design and mapping for applications with real-time constraints on manycore platforms. It combines model-based engineering tools (TTool) and simulation with our analytical verification technique (G-BATA) and tools (WoPANets) to provide an efficient design space exploration framework. Finally, we validate our contributions on (a) a serie of experiments on a physical platform and (b) two case studies taken from the real world: an autonomous vehicle control application, and a 5G signal decoder application
29
Mussot, Vincent. "Automates d'annotation de flot pour l'expression et l'intégration de propriétés dans l'analyse de WCET". Thesis, Toulouse 3, 2016. http://www.theses.fr/2016TOU30247/document.
Texto completoResumen
Dans le domaine des systèmes critiques, l'analyse des temps d'exécution des programmes est nécessaire pour planifier et ordonnancer au mieux différentes tâches et par extension pour dimensionner les systèmes. La durée d'exécution d'un programme dépend de divers facteurs comme ses entrées ou le matériel utilisé. Or cette variation temporelle pose problème dans les systèmes temps-réel dans lesquels il est nécessaire de dimensionner précisément les temps processeur alloués à chaque tâche, et pour cela, connaître leur temps d'exécution au pire cas. Au sein de l'équipe TRACES à l'IRIT, nous cherchons à calculer une borne supérieure à ce temps d'exécution au pire cas qui soit la plus précise possible. Pour cela, nous travaillons sur le graphe de flot de contrôle d'un programme qui représente un sur-ensemble des ses exécutions possibles, que nous accompagnons d'annotations sur des comportements spécifiques du programme susceptibles de réduire la sur-approximation de notre estimation. Dans les outils destinés au calcul du temps d'exécution au pire cas des programmes, les annotations sont habituellement exprimées et intégrées grâce à des langages d'annotation spécifiques. Nous proposons d'utiliser des automates appelés automates d'annotation de flot en lieu et place de ces langages, afin de fonder non seulement l'expression, mais également l'intégration d'annotations dans l'analyse sur des bases formelles. Nous présentons ces automates enrichis de contraintes, de variables et d'une hiérarchie et nous montrons comment ils supportent les divers types d'annotations utilisés dans le domaine de l'analyse du temps d'exécution au pire cas. Par ailleurs, l'intégration des annotations dans une analyse se fait habituellement par l'association de contraintes numériques au graphe de flot de contrôle. Les automates que nous présentons supportent cette méthode mais leur expressivité offre également de nouvelles possibilités d'intégration basées sur le dépliage du graphe de flot de contrôle. Nous présentons des résultats expérimentaux issus de la comparaison de ces deux méthodes qui montrent comment le dépliage de graphe peut améliorer la précision de l'analyse. A terme, ce gain de précision dans l'estimation du temps d'exécution au pire cas permettra de mieux exploiter le matériel sans faire courir de risques à l'utilisateur ou au systèmeIn the domain of critical systems, the analysis of execution times of programs is needed to schedule various task at best and by extension to dimension the whole system. The execution time of a program depends on multiple factors such as entries of the program or the targeted hardware. Yet this time variation is an issue in real-time systems where the duration is required to allow correct processor time to each task, and in this purpose, we need to know their worst-case execution time. In the TRACES team at IRIT, we try to compute a safe upper bound of this worst-case execution time that would be as precise as possible. In order to do so, we work on the control flow graph of a program that represents an over-set of its possible executions and we combine this structure with annotations on specific behaviours of the program that might reduce the over-approximation of our estimation. Tools designed to compute worst-case execution times of programmes usually support the expression and the integration of annotations thanks to specific annotation languages. Our proposal is to replace these languages with a type of automata named flow fact automata so that not only the expression but also the integration of annotations in the analysis inherit from the formal basis of automata. Based on these automata enriched with constraints, variables and a hierarchy, we show how they support the various annotation types used in the worst-case execution time domain. Additionally, the integration of annotations in an analysis usually lead to associate numerical constraint to the control flow graph. The automata presented here support this method but their expressiveness offers new integration possibilities based on the partial unfolding of control flow graph. We present experimental results from the comparison of these two methods that show how the graph unfolding can improve the analysis precision. In the end, this precision gain in the worst-case execution time will ensure a better usage of the hardware as well as the absence of risks for the user or the system itself
30
Bettonte, Gabriella. "Quantum approaches for Worst-Case Execution-Times analysis of programs". Electronic Thesis or Diss., université Paris-Saclay, 2023. http://www.theses.fr/2023UPASG026.
Texto completoResumen
L'informatique quantique gagne en popularité dans la communauté informatique. La prise de conscience du potentiel de l'informatique quantique a commencée en 1981, lorsque Richard Feynman a imaginé la construction d'un ordinateur quantique. Cependant, le domaine a connu beaucoup de scepticisme quant à ses capacités pratiques à long terme pour résoudre les problèmes. En particulier, les chercheurs tente de relever le défi de construire des ordinateurs quantiques scalables et fiables. Dernièrement, de nombreuses entreprises ont obtenu des résultats encourageants et ont construit des machines quantiques avec suffisamment de qubits pour commencer à mener des expériences intéressantes dessus. Nous avons choisi l'évaluation du pire temps d'exécution (WCET) comme application de nos recherches sur l'informatique quantique, car elle est cruciale pour diverses applications temps réel. L'analyse WCET garantit que le temps d'exécution d'un programme respecte toutes les contraintes d'ordonnancement et de timing. Dans l'histoire des algorithmes quantiques, l'attention a souvent été accordée aux problèmes avec une structure mathématique particulière. L'évaluation des WCET, à l'opposé, n'est pas un problème a priori favorable au contexte quantique, et possède des solutions classiques efficaces déjà éprouvées. Ainsi, il est intéressant d'explorer l'impact de l'informatique quantique sur ce type de problèmes, dans l'esprit de trouver des domaines nouveaux et concrets dans lesquels l'informatique quantique pourrait apporter sa contribution. Si ce n'est pas le cas, la recherche dans ces domaines spécifiques peut aider à définir les limites des applications qui pourraient bénéficier de l'informatique quantique. Cette thèse présente différentes approches quantiques pour effectuer des évaluations WCETs de programmes pour des modèles simplifiésQuantum computing is gaining popularity in the computer science community. The awareness of the potential of quantum computing started in 1981, when Richard Feynman first speculated about building a quantum computer. However, until recently, the field has known much skepticism about its long-term practical capabilities to solve problems. In particular, researchers are still facing the challenge of building scalable and reliable quantum computers. Lately, many companies have obtained encouraging results and built quantum machines with enough qubits to start conducting interesting experiments. We chose the worst-case execution-time (WCET) evaluation as the application of our research on quantum computing, as it is crucial for various real-time applications. WCET analysis guarantees that a program's execution time matches all the scheduling and timing constraints. In quantum algorithms history, attention was often given to problems with a particular mathematical structure. The WCETs evaluation, as an opposite, is not a particularly quantum-friendly problem, and it has already proven efficient classical solutions. Hence, it is worth exploring the impact of quantum computing on those kinds of problems, with the spirit of finding new and concrete fields to which quantum computing could bring its potential. If not, research on such specific fields will help to set the boundaries of which applications could benefit from quantum computing. This thesis presents different quantum approaches to perform WCETs evaluations of programs under simplified assumptions
31
Stehlé, Damien. "Algorithmique de la réduction de réseaux et application à la recherche de pires cas pour l'arrondi defonctions mathématiques". Phd thesis, Université Henri Poincaré - Nancy I, 2005. http://tel.archives-ouvertes.fr/tel-00011150.
Texto completoResumen
Les réseaux euclidiens sont un outil particulièrement puissant dansplusieurs domaines de l'algorithmique, en cryptographie et en théorie
algorithmique des nombres par exemple. L'objet du présent mémoire est dual : nous améliorons les algorithmes de réduction des réseaux,
et nous développons une nouvelle application dans le domaine
de l'arithmétique des ordinateurs. En ce qui concerne l'aspect algorithmique, nous nous intéressons aux cas des petites dimensions (en dimension un, où il s'agit du calcul de pgcd, et aussi en dimensions 2 à 4), ainsi qu'à la description d'une nouvelle variante de l'algorithme LLL, en dimension quelconque. Du point de vue de l'application, nous utilisons la méthode
de Coppersmith permettant de trouver les petites racines de polynômes modulaires multivariés, pour calculer les pires cas pour l'arrondi des fonctions mathématiques, quand la fonction, le mode d'arrondi, et la précision sont donnés. Nous adaptons aussi notre technique aux mauvais cas simultanés pour deux fonctions. Ces deux méthodes sont des pré-calculs coûteux, qui une fois
effectués permettent d'accélérer les implantations des fonctions mathématiques élémentaires en précision fixée, par exemple en double précision.
La plupart des algorithmes décrits dans ce mémoire ont été validés
expérimentalement par des implantations, qui sont
disponibles à l'url http://www.loria.fr/~stehle.
32
Senoussaoui, Ikram. "Co-ordonnancement processeur et mémoire des applications temps-réel sur les plateformes multicœurs". Electronic Thesis or Diss., Université de Lille (2022-....), 2023. http://www.theses.fr/2023ULILB051.
Texto completoResumen
La demande en puissance de calcul dans les systèmes embarqués temps-réel a considérablement augmenté ces dernières années. Les plateformes multicœurs qui sont généralement équipés d'un sous-système de mémoire partagé par tous les cœurs ont répondu dans une certaine mesure à ce besoin croissant en capacité de calcul. Cependant, dans les systèmes temps-réel, l'utilisation simultanée du sous-système de mémoire peut induire à des interférences mémoire significatives.Ces dernières peuvent rendre les pires temps d'exécution des tâches (WCET) très pessimistes et conduire à une sous-utilisation du système. Cette thèse se concentre sur la réduction des interférences résultantes des conflits liés aux ressources partagées (par exemple les mémoires cache, les bus de communication et la mémoire principale) dans les systèmes multicœursgrâce au co-ordonnancement des calculs et des transferts de donnée des applications temps-réel. À cette fin, nous utilisons des modèles de tâches existants tels que le modèle DFPP (Deferred Fixed Preemption Point), le modèle PREM (PRedictable-Exécution-Model) et le modèle AER (Acquisition-Execution-Restitution model). Nous proposons un nouveau modèle de tâche réaliste et plusieurs algorithmes de co-ordonnancement et de partitionnement des tâches temps-réel. Nous montrons que de tels ordonnanceurs peuvent améliorer jusqu'à 50% le taux d'ordonnançabilité par rapport aux ordonnanceurs équivalents générés avec les méthodes de l'état de l'art. De plus, nous démontrons expérimentalement l'applicabilité de nos méthodologies sur la famille de processeurs multicœurs Infineon AURIX TC-397 en utilisant différents benchmarksThe demand for computational power in real-time embedded systems has increased significantly in recent years. Multicore platforms which are generally equipped with a single memory subsystem shared by all cores, have satisfied this increasing need for computation capability to some extent. However, in real-time systems, simultaneous use of the memory subsystem may result in significantmemory interference. Such memory interference owing to resource contention may lead to very pessimistic worst-case execution time bounds (WCETs) and lead to under-utilization of the system.This thesis focuses on reducing interference resulting from shared resource contention (e.g., caches, buses and main memory) on multicore systems through processor and memory co-scheduling for real-time applications. To this end, we use existing task models such as DFPP (Deferred Fixed Preemption Point) model, PREM (Predictable-Execution-Model) and AER (Acquisition-Execution-Restitution) model. We also propose a new realistic task model and several algorithms for task set allocation and for processor and memory co-scheduling. We show that our proposed methodologies can improve schedulability by up to 50% compared to equivalent schedules generated with the state-of-the-art methods. Furthermore, we experimentally demonstrate the applicability of our methodologies on the Infineon AURIX TC-397 multicore family of processors using different benchmarks
33
Preda, Valentin. "Robust microvibration control and worst-case analysis for high pointing stability space missions". Thesis, Bordeaux, 2017. http://www.theses.fr/2017BORD0785/document.
Texto completoResumen
Le contexte général des travaux de recherche de cette thèse concerne les problématiques liées à l’optimisation glob-ale liée à la conception des futurs satellites d’observation terrestre et de missions scientifiques, nécessitantune très haute stabilité en pointage (capacité du satellite à garder son point de visée). Plus particulièrement,les travaux concernent le contrôle actif des modes micro-vibratoires.Dans une mission satellitaire d’observation terrestre, la qualité des images dépend bien évidemmentdes instruments de mesure optique (diamètre du miroir, aberrations optiques et qualité du polissage)mais également des performances de la stabilité de la ligne de visée du satellite qui peut s’avérer dégradéepour cause de micro-vibrations. La présence de ces micro-vibrations est liée aux divers éléments tournantdu satellite tels que les mécanismes de rotation des panneaux solaires ou de contrôle d’orientation dusatellite (on parle de contrôle d’attitude réalisé au moyen de roues inertielles).Le contrôle des micro-vibrations représentent ainsi un défit technologique, conduisant l’ESA et les ac-teurs industriels du monde spatial, a considéré cette problématique comme hautement prioritaire pour ledéveloppement des satellites d’observation terrestre nouvelle génération.Il existe à l’heure actuelle deux principes fondamentaux de contrôle des micro-vibrations :• le contrôle dit passif: la stratégie consiste à introduire des dispositions constructives et des matériauxparticuliers permettant de minimiser la transmission des vibrations à l’environnement.• le contrôle dit actif : le concept de contrôle actif des vibrations est tout autre : l’idée est cette fois-ci,de bloquer la micro-vibration en exerçant une vibration antagoniste créée artificiellement avec despropriétés en opposition, à tout instant, relativement à la vibration indésirable, pour rendre nulleleur somme.L’industrie spatiale aborde cette problématique en plaçant des isolateurs en élastomère au voisinage dechaque source de micro-vibrations. Cette solution, qui a fait ses preuves puisqu’elle équipe actuelle-ment nombre de satellites en orbite, permet de rejeter nombre de micro-vibrations. Malheureusement,la demande de plus en plus importante de grande stabilité de la ligne de visée pour les futures missionsd’observation terrestres telles que les missions GAIA rend l’approche passive insuffisante.L’ESA et Airbus Defence and Space, ont donc collaborer conjointement avec l’équipe ARIA au travers decette thèse, dans des travaux de recherche dans le domaine du contrôle actif pour palier ces problèmes.L’objectif visé est de coupler les approches passives et actives afin de rejeter à la fois les micro-vibrations enhautes fréquences (approche passive existant) et en basses fréquences (approche active objet des travauxde la thèse)Next generation satellite missions will have to meet extremely challenging pointing stability requirements. Even low levels of vibration can introduce enough jitter in the optical elements to cause a significant reduction in image quality. The success of these projects is therefore constrained by the ability of on-board vibration isolation and optical control techniques to keep stable the structural elements of the spacecraft in the presence of external and internal disturbances.In this context, the research work presented in this thesis combines the expertise of the European Space Agency (ESA), the industry (Airbus Defence and Space) and the IMS laboratory (laboratoire de l’Intégration du Matériau au Système) with the aim of developing new generation of robust microvibration isolation systems for future space observation missions. More precisely, the thesis presents the development of an Integrated Modeling, Control and Analysis framework in which to conduct advanced studies related to reaction wheel microvibration mitigation.The thesis builds upon the previous research conducted by Airbus Defence and Space and ESA on the use of mixed active/passive microvibration mitigation techniques and provides a complete methodology for the uncertainty modeling, robust control system design and worst-case analysis of such systems for a typical satellite observation mission. It is shown how disturbances produced by mechanical spinning devices such as reaction wheels can be significantly attenuated in order to improve the pointing stability of the spacecraft even in the presence of model uncertainty and other nonlinear phenomenon.Finally, the work introduces a new disturbance model for the multi harmonic perturbation spectrum produced by spinning reaction wheels that is suitable for both controller synthesis and worst-case analysis using modern robust control tools. This model is exploited to provide new ways of simulating the image distortions induced by such disturbances
34
Burguière, Claire. "Modéliser la prédiction de branchement pour le calcul de temps d'exécution pire-cas". Toulouse 3, 2008. http://thesesups.ups-tlse.fr/383/.
Texto completoResumen
De nos jours, les pipelines haute-performance sont de plus en plus utilisés dans les systèmes temps-réel et il devient de plus en plus difficile de garantir que les programmes respecteront leurs échéances. Certains éléments de l'architecture des processeurs récents ont des comportements dynamiques difficiles à modéliser pour le calcul de temps d'exécution pire-cas (WCET) par méthode statique. Dans ce rapport nous étudions l'impact de la prédiction de branchement dynamique sur le temps d'exécution pire-cas. Cet impact dépend de la valeur de la prédiction (correcte ou mauvaise). Deux approches permettent de modéliser la prédiction de branchement dynamique. L'approche locale consiste à estimer le nombre de mauvaises prédictions pire-cas. Par approche globale, le calcul de la prédiction est décrit sous forme de système de contraintes linéaires en nombres entiers. Nous présentons la construction de ce système en fonction des différents mécanismes qui constituent un prédicteur de branchement dynamique (indexation de la table de prédiction, conflits sur les entrées de cette table et calcul de la prédiction par des compteurs). Nous détaillons deux modèles de prédicteurs de branchement : le prédicteur bimodal et un prédicteur global 2-bits. Pour comparer la taille de ces systèmes de contraintes nous proposons une mesure de la complexité de modélisation basée sur le nombre de contraintes, le nombre de variables et l'arité du système. A partir d'une analyse des résultats obtenus, nous précisons les limites des deux approches et dans quels contextes elles sont bien adaptéesThe wider and wider use of high-performance processors as part of real-time systems makes it more and more difficult to guarantee that programs will respect their deadlines. While the computation of Worst-Case Execution Times relies on static analysis of the code, the challenge is to model with enough safety and accuracy the behaviour of intrinsically dynamic components. In this report, we focus on the impact of dynamic branch prediction on the worst-case execution time. We present two approaches to model this impact. Local approach examines each branch individually to determine its worst-case number of mispredictions. In the global approach, an ILP system of constraints describes the computation of the branch prediction. Each part of the dynamic branch predictor can be modelled separately: BHT indexing, conflicts on BHT entries and 2-bit counter computation of the prediction. We introduce two branch predictor models: the bimodal predictor and a 2-bit global predictor. We propose a way to compare the effort needed to build the system of constraints that we name modelling complexity. This complexity is quantified as a function of: the number of constraints, the number of variables and the system arity. We analyse the modelling complexity of some branch predictors and we deduce the context of use that fit for the global approach. We examine the differences between the two approaches
35
Mouafo, Tchinda Yves. "Robustesse des applications temps-réel multicoeurs : techniques de construction d'un ordonnacement équitable tolérant aux pannes matérielles". Thesis, Chasseneuil-du-Poitou, Ecole nationale supérieure de mécanique et d'aérotechnique, 2017. http://www.theses.fr/2017ESMA0015/document.
Texto completoResumen
Cette thèse propose des techniques de construction d'une séquence d'ordonnancement valide par un algorithme équitable pour des systèmes temps-réel multicoeurs subissant des pannes processeurs permanentes. Selon la nature des tâches les concepteurs peuvent allouer ou pas du temps supplémentaire pour récupérer l'exécution perdue. Dans un premier temps, nous traitons le cas de la défaillance d'un seul coeur. Nous montrons alors que s'il n'y a pas d'allocation de temps supplémentaire, prévoir un coeur de plus que le minimum nécessaire permet de construire une séquence valide : c'est la Technique de la Redondance Matérielle Limitée. Toutefois, si une telle allocation s'impose, nous proposons trois techniques : la Technique des Sous-tâches de Substitution qui augmente le WCET des tâches afin de prévoir du temps additionnel en remplacement du temps perdu, la Technique Contraindre puis Relâcher qui crée une marge de temps entre le délai critique et la période d'une tâche pour rattraper l'exécution perdue et la Technique du Flux Apériodique (TFA) qui réordonnance l'exécution perdue dans les unités de temps creux équitablement réparties. Ensuite, l'utilisation conjointe de ces techniques est envisagée en fonction de la nature des tâches impactées. Enfin, le cas de la défaillance de plusieurs coeurs est étudié. Pour ajuster la charge du système au nombre de coeurs fonctionnels, deux approches sont proposées : le changement de mode de criticité qui modifie les paramètres temporels de certaines tâches et l'abandon de certaines tâches en fonction de leur importance dans le systèmeThis thesis proposes several techniques to build a valid schedule with a Pfair algorithm for multicore real-time systems despite permanent processor failures. Depending on the nature of the tasks, additional time may be allocated or not to recover the lost execution. First, we consider a single core failure. We then show that if no additional time is allocated, the use of a single more core than the required minimum provides a valid schedule : it is the Limited Hardware Redundancy Technique. However, if full recovery is mandatory, we propose three techniques : the Substitute Subtasks Technique which increases the WCET to provide additionnal time which can be used to recover the lost time, the Constrain and Release Technique which creates a time margin between each task's deadline and the following period which can be used to recover the lost execution and the Aperiodic Flow Technique which reschedules the lost execution within the idle time units. Then, these techniques are mixed to adapt the scheduling behaviour to the nature of the impacted tasks. Finally, the case of the failure of several cores is studied.To adapt the system load to the number of remaining functionnal cores we use the criticality mode change which modifies the temporal parameters of some tasks or we discard some tasks according to their importance
36
Soni, Aakash. "Real-time performance analysis of a QoS based industrial embedded network". Thesis, Toulouse, INPT, 2020. http://www.theses.fr/2020INPT0047.
Texto completoResumen
L'AFDX est utilisé comme un réseau fédérateur pour la transmission des flux avioniques critiques. Ce réseau est certifié grâce à l'analyse pire-cas utilisant l'approche Network Calculus (NC). Le pessimisme introduit par NC conduit souvent à un réseau surdimensionné et éventuellement sous-utilisé. Les avionneurs envisagent d'augmenter l'utilisation des ressources du réseau AFDX en ajoutant du trafic supplémentaire provenant d'autres fonctions critiques et non critiques. Le partage du réseau AFDX avec des flux de criticité mixtes nécessite l'utilisation d'un mécanisme de qualité de service (QoS) pour satisfaire les contraintes de délai des différentes classes de flux. Dans cette thèse, nous étudions un tel réseau déployant de la qualité de service, en particulier, basé sur l'ordonnancement DRR et WRR. Nous proposons une méthode optimale de distribution de la bande passante qui assure le service requis par les flux critiques tout en fournissant un service maximisé aux flux non-critiques. Nous proposons également une approche NC optimisée qui, sur une configuration industrielle de réseau AFDX, a permis de réduire les bornes jusqu'à 40%AFDX serves as a backbone network for transmission of critical avionic flows. This network is certified thanks to the WCTT analysis using Network Calculus (NC) approach. However, the pessimism introduced by NC approach often leads to an over-sized and eventually an underutilized network. The manufacturers envision to better use the available network resources by increasing occupancy rate of the AFDX network by allowing additional traffic from other critical and non-critical functions. Such harmonization of AFDX network with mixed criticality flows necessitates the use of QoS mechanism to satisfy the delay constraints in different classes of flow. In this thesis we study such QoS-aware network, in particular, based on DRR and WRR scheduling. We propose an optimal bandwidth distribution method that ensures the service required by critical flows while providing maximum service to other non-critical flows. We also propose an optimized NC approach to compute tight delay bounds. Our approach has led to computation of up to 40% tighter bounds, in an industrial AFDX configuration, as compared to the classical approach
37
Emery, Laetitia. "Approches archéométriques des productions faïencières françaises au XVIIIe siècle : le cas de la manufacture Babut à Bergerac (env. 1740 - 1789)". Phd thesis, Université Michel de Montaigne - Bordeaux III, 2012. http://tel.archives-ouvertes.fr/tel-00751413.
Texto completoResumen
La faïence est une céramique caractérisée par son revêtement vitreux blanc opaque, grâce à l'adjonction d'oxyde d'étain ; sur ce fond on peut apposer les décors polychromes. Résultant d'une technologie abbaside (VIIIe siècle), elle connait son apogée en France au XVIIIe siècle. Les précédentes études menées sur la faïence moderne ont mis en évidence la nécessité de procéder à une approche pluridisciplinaire pour appréhender ce matériau complexe, ses techniques de fabrication, et cerner les enjeux de sa production. Ce travail de recherche s'inscrit dans la continuité pour s'élargir aux productions faïencières du Sud Ouest de la France quelques peu délaissées du point de vue archéométrique. La manufacture Babut, première faïencerie établie à Bergerac, fut sélectionnée dans ce but. La production perdure sur cinquante ans environ, jusqu'à la Révolution Française.En prenant en considération ces observations, cette thèse a permis tout d'abord d'identifier la production du point de vue des matériaux et des techniques, de mettre en place un référentiel géochimique, ainsi qu'établir un corpus stylistique de base pour cette manufacture. Ensuite l'étude a porté sur l'évaluation du potentiel de méthodes d'analyses non destructives pour l'attribution de provenance directe à partir de la surface des glaçures. Et enfin ce travail a permis d'examiner la place de la faïence bergeracoise et de sa production au sein du tissu industriel régional, et les replacer dans le contexte plus général de la production faïencière française à l'aube de la Révolution industrielle.
38
Ait, Bensaid Samira. "Formal Semantics of Hardware Compilation Framework". Electronic Thesis or Diss., université Paris-Saclay, 2023. http://www.theses.fr/2023UPASG085.
Texto completoResumen
Les analyses statiques de pire temps d’exécution sont utilisées pour garantir les délais requis pour les systèmes critiques. Afin d’estimer des bornes précises sur ces temps d’exécution, ces analyses temporelles nécessitent des considérations sur la (micro)- architecture. Habituellement, ces modèles de micro-architecture sont construits à la main à partir des manuels des processeurs. Cependant, les initiatives du matériel libre et les langages de description de matériel de haut niveau (HCLs), permettent de réaborder la problématique de la génération automatique de ces modèles de micro-architecture, et plus spécifiquement des modèles de pipeline. Nous proposons un workflow qui vise à construire automatiquement des modèles de chemin de données de pipeline à partir de conceptions de processeurs décrites dans des langages de contruction de matériel (HCLs). Notre workflow est basé sur la chaine de compilation matériel Chisel/FIRRTL. Nous construisons au niveau de la représentation intermédiaire les modèles de pipeline du chemin de données. Notre travail vise à appliquer ces modèles pour prouver des propriétés liées à la prédictibilité temporelle. Notre méthode repose sur la vérification formelle. Les modèles générés sont ensuite traduits en modèles formels et intégrés dans une procédure existante basée sur la vérification de modèles pour détecter les anomalies de temps. Nous utilisons le langage de modélisation et de vérification TLA+ et expérimentons notre analyse avec plusieurs processeurs RISC-V open-source. Enfin, nous faisons progresser les études en évaluant l’impact de la génération automatique à l’aide d’une série de critères synthétiquesStatic worst-case timing analyses are used to ensure the timing deadlines required for safety-critical systems. In order to derive accurate bounds, these timing analyses require precise (micro-)architecture considerations. Usually, such micro-architecture models are constructed by hand from processor manuals.However, with the open-source hardware initiatives and high-level Hardware Description Languages (HCLs), the automatic generation of these micro-architecture models and, more specifically, the pipeline models are promoted. We propose a workflow that aims to automatically construct pipeline datapath models from processor designs described in HCLs. Our workflow is based on the Chisel/FIRRTL Hardware Compiler Framework. We build at the intermediate representation level the datapath pipeline models. Our work intends to prove the timing properties, such as the timing predictability-related properties. We rely on the formal verification as our method. The generated models are then translated into formal models and integrated into an existing model checking-based procedure for detecting timing anomalies. We use TLA+ modeling and verification language and experiment with our analysis with several open-source RISC-V processors. Finally, we advance the studies by evaluating the impact of automatic generation through a series of synthetic benchmarks
39
Bechtel, Andrew Joseph. "External strengthening of reinforced concrete pier caps". Diss., Georgia Institute of Technology, 2011. http://hdl.handle.net/1853/42809.
Texto completoResumen
The shear capacity of reinforced concrete pier caps in existing bridge support systems can be a factor which limits the capacity of an existing bridge. In their usual configuration, pier caps behave as deep beams and have the ability to carry load through tied arch action after the formation of diagonal cracks. Externally bonded fiber reinforced polymer (FRP) reinforcement has been shown to increase the shear capacity of reinforced concrete members which carry load through beam action. However, there is an insufficient amount of research to make it a viable strengthening system for beams which carry load through arch action, such as pier caps. Accordingly, this research was aimed at investigating the behavior of reinforced concrete pier caps through a coordinated experimental and analytical program and to recommend an external strengthening method for pier caps with perceived deficiencies in shear strength.
The experimental study was performed on laboratory specimens based on an existing bridge in Georgia. A number of factors were examined, including size, percentage longitudinal reinforcement and crack control reinforcement. The results showed that increasing the longitudinal tension reinforcement increased the beam capacity by changing the shape of the tied arch. In contrast, the presence of crack control reinforcement did not change the point at which diagonal cracking occurred, but it did increase the ultimate capacity by reinforcing the concrete against splitting. The results of the experimental study were used in conjunction with a larger database to examine different analytical methods for estimating the ultimate capacity of deep beams, and a new method was developed for the design of external strengthening. Two specimens were tested with externally bonded FRP reinforcement applied longitudinally to increase the strength of the tension tie. The test results correlated well with the proposed method of analysis and showed that increasing the strength of the longitudinal tension tie is an effective way to increase the strength of a reinforced concrete deep beam.
40
Bel, Hadj Aissa Nadia. "Maîtrise du temps d'exécution de logiciels déployés dans des dispositifs personnels de confiance". Thesis, Lille 1, 2008. http://www.theses.fr/2008LIL10133/document.
Texto completoResumen
La prolifération de petits équipements ouverts tels que les dispositifs personnels de confiance a favorisé l'essor des environnements d'exécution dynamiquement adaptables. Ainsi, de nouveaux logiciels peuvent être déployés à la volée après que les équipements soient délivrés à leurs porteurs. Par nos travaux, nous aspirons à garantir que chaque nouveau logiciel, dont le déploiement aboutit, est en mesure de délivrer les réponses aux requêtes qui lui sont adressées dans un délai maximal préalablement établi. Les garanties apportées sont cruciales tant en terme de sûreté de fonctionnement que de sécurité. À cet effet, nous avons proposé de distribuer le calcul du temps d'exécution au pire cas à la manière des approches de codes porteurs de preuve. Le fournisseur de code se voit attribuer les calculs gourmands en ressources matérielles ne supposant aucune connaissance préalable de l'environnement d'exécution sur lequel s'exécutera son logiciel, en l'occurrence la détermination des bornes des boucles. Quant au consommateur, il vérifie grâce à la preuve les bornes inférées par le fournisseur et calcule le temps d'exécution au pire cas. Nous avons évalué expérimentalement le bien-fondé de notre démarche sur une architecture matérielle et logicielle répondant aux exigences des dispositifs personnels de confiance. Enfin, nous nous sommes préoccupés du cas où plusieurs logiciels, émanant d'entité différentes, coexistent. Nous avons mis l'accent sur l'impact de l'interaction entre ces logiciels sur les garanties préalablement apportées par le système sur le temps d'exécution au pire cas et nous avons ébauché une solution basée sur les contrats pour maintenir ces garantiesThe proliferation of small and open objects such as personal trusted devices has encouraged the spread of dynamically adaptable runtime environments. Thus, new software can be deployed on the fly after the devices are delivered to their holders. Through our work, we aim to ensure that each new software, whose deployment is successful, will be able to deliver responses within a maximum delay previously established. These guarantees are crucial in terms of safety and security. To this end, we propose to distribute the computation of worst case execution time. Our solution embraces a proof carrying code approach making distinction between a powerful but untrusted computer used to produce the code, and a safe but resource constrained code consumer. The producer does not assume any prior knowledge of the runtime environment on which its software will be executed. The code is statically analyzed to extract loop bounds and a proof containing this information is joint to the software. By a straightforward inspection of the code, the consumer can verify the validity of the proof and compute the global worst case execution time. We experimentally validate our approach on a hardware and software architecture which meets the requirements of trusted personal devices. Finally, we address the challenges raised when software from different service providers potentially untrusted can coexist and interact in a single device. We focus on the impact of the interaction between different software units on the guarantees previously given by the system on the worst case execution time and we outline a solution based on contracts to maintain these guarantees
41
SOPHIYAIR, ELEONORE. "Diabete et grossesse : analyse retrospective de 57 cas". Montpellier 1, 1989. http://www.theses.fr/1989MON11299.
Texto completo
42
FABRIZI, CARLO. "Analisi computazionale dell’aeroacustica di un pneumatico in rotolamento". Doctoral thesis, Università degli Studi di Roma "Tor Vergata", 2010. http://hdl.handle.net/2108/1369.
Texto completoResumen
Il traffico stradale è una delle maggiori fonti di inquinamento acustico della società moderna. Conseguentemente, lo sviluppo dei nuovi veicoli è soggetta a direttive sempre più stringenti in termini di emissione rumorosa. Le maggiori sorgenti di rumore dei comuni veicoli stradali sono il rumore del motore, quello della trasmissione, il rumore aerodinamico e quello dell’interazione pneumatico-strada. Quest’ultimo diventa dominante tra i 50 e 100 km/h, velocità tipiche dei tratti urbani ed extra-urbani. Il rumore derivante dall’interazione pneumatico-strada è la combinazione di vibrazioni strutturali e fenomeni aeroacustici che generano e amplificano/riducono il suono emesso dal pneumatico. L’analisi numerica presentata in questa tesi ha lo scopo di investigare i meccanismi di generazione del rumore aeroacustico del pneumatico e allo stesso tempo fornire uno strumento di sviluppo di coperture a basso impatto acustico.
Il presente lavoro è diviso in due parti, l’analisi dell’aerodinamica stazionaria e l’analisi aeroacustica del pneumatico in rotolamento. Nella prima, lo studio della soluzione numerica delle Navier-Stokes mediate ha consentito di evidenziare i fenomeni aerodinamici, come separazioni o flussi a getto, che possono originare emissione acustica. Nella seconda parte tali aspetti sono stati analizzati con maggiore dettaglio per mezzo delle analogie aeroacustiche, definendo la reale capacità di predizione dello strumento numerico e fornendo suggerimenti per lo sviluppo di pneumatici più silenziosi.Road traffic is one of the major source of noise in modern society. Consequently, the development of new vehicles is subject to increasingly stringent guidelines in terms of noise emissions. The main noise sources of common road vehicles are the engine, the transmission, the aerodynamic and the tire-road interaction. The latter becomes dominant between 50 and 100 mph, speeds typical of urban and extra-urban roads. The noise that arises from tire-road is the combination of structural vibration and aeroacoustics phenomena that create and amplification/reduction of the sound emitted from the tire. The aim of the numerical analysis presented in this thesis is to investigate the aeroacoustic noise generation mechanisms of the tire and at the same time provide a tool to develop low noise tire. The present work is divided into two parts, the analysis of the steady aerodynamics and the aeroacoustic of the rolling tire. In the first part, the study of the Navier-Stokes numerical solution made it possible to highlight the aerodynamic phenomena, such as separations or jet streams, which can cause noise. In the second part these aspects have been analyzed in greater detail by means of aeroacoustic analogies, defining the capacity of the numerical tool to provide suggestions for the development of quieter tires.
43
Sirigu, Marco. "Synthétisation d'un calculateur de délai et de puissance : application à la technologie MOS complémentaire". Paris 11, 1985. http://www.theses.fr/1985PA112062.
Texto completoResumen
Cette thèse présente la mise au point d'un calculateur de délai (retard à la propagation) et de puissance consommée, qui donne la possibilité de faire intervenir les effets des paramètres du procédé associés à une technologie fixée. Les techniques employées permettent de mettre en évidence les principaux paramètres de la technologie utilisée, ou bien de les déterminer (dans le cas d'un changement de technologie). En conclusion, on souligne la faisabilité de ce calculateur et on en donne des utilisations mises en place, ou pouvant l’être, par exemple : le calcul des délais de macromodèles.
44
Okiye, Waais Idriss. "Analyse multidimensionnelle de la pauvreté : le cas de Djibouti". Thesis, Bourgogne Franche-Comté, 2017. http://www.theses.fr/2017UBFCB001/document.
Texto completoResumen
L'objet de cette thèse est de proposer et de développer les différentes mesures multidimensionnelles de la pauvreté. La multidimensionnalité de la pauvreté fait aujourd'hui consensus. Scientifiques, décideurs politiques et professionnels du développement s'accordent pour dire que la seule dimension monétaire (le manque de revenu) ne suffit pas à représenter la pauvreté. En se basant sur les travaux de Sen (Prix Nobel d'Economie) en particulier sur l'approche des capacités, nous proposons quatre mesures différentes de la pauvreté. La première est une mesure monétaire basée sur l'approche utilitaire ; la seconde est une mesure subjective basée sur les expériences des ménages ; la troisième est une mesure multidimensionnelle axiomatique et enfin la dernière est une mesure non axiomatique basée sur la théorie des ensembles flous. Elles sont toutes mises en oeuvre en utilisant les données d'enquêtes EDAM3-IS (Enquête Djiboutienne Auprès des Ménages 2012). Les résultats s'inscrivent dans un contexte de croissance économique que connait Djibouti. Cependant, toutes les mesures utilisées ont montré des grandes disparités régionales entre la capitale et les régions en termes d'infrastructure de base et de bien-être des ménages. Chacune de ses méthodes a fourni des résultats avec différentes interprétations des déterminants de la pauvreté. Cela ne signifie pas qu'il existe une méthode bien meilleure que l'autre, mais chaque approche, dans un contexte particulier, peut-être plus pertinente. Ainsi, l'identification des pauvres en appliquant les différentes mesures de la pauvreté nous a donné un profil différencié. Par conséquent, le décideur doit définir au préalable l'objectif poursuivi dans les politiques de lutte contre la pauvreté. Nous pouvons souligner que l'intégration d'une pondération subjective dans la mesure de la pauvreté est une de nos contributions au développement de mesures multidimensionnelles de la pauvretéThe aim of this thesis is to propose and develop the various multidimensional measures of poverty. There is a consensus on the multidimensional nature of poverty. Scientists, policy makers and development professionals agree that the monetary dimension (lack of income) is inadequate to represent poverty. On the basis of the work of Sen (Nobel Proze of Economics), particularly on the capability approach, we propose four different measures of poverty. The first one is a monetary measure based on the utilitarian approach ; the second is a subjective measure founded on household experience ; the third is a multidimensional axiomatic measure and the final one is a non-axiomatic measure based on the theory of fuzzy sets. They are implemented using survey data EDAM3-IS (Djiboutian Survey of Households 2012). The esults fall within the framework of economic growth in Djibouti. However, all the measures used have shown great disparities between the capital and the regions in terms of basic infrastructure and household welfare. Each method produced results with different interpretations of the determinants of poverty. This does not mean that there is one method being better than the other but rather each approach, in a particular context, may be more relevant. Thus, identifying the poor by applying the different measures of poverty gave us a clear-cut profile, which implies that the decision-maker must first set the aim in view in the implementation of anti-poverty policies. It can be emphasized that the inclusion of a subjective weighting in the process of measuring of poverty is one of our contributions towards the development of multidimensional measures of poverty
45
Bouallegue, Olfa. "Analyse économique des révolutions : Cas de la révolution Tunisienne". Thesis, Montpellier, 2017. http://www.theses.fr/2017MONTD020/document.
Texto completoResumen
En 2011, des mouvements sociaux et révolutionnaires d’une ampleur rare ont agité certains pays du nord de l’Afrique. Cela correspond à ce qu’on a appelé le printemps arabe.Le premier de ces pays touchés par ces mouvements est la Tunisie. Cette thèse porte sur la révolution tunisienne. Elle propose une analyse théorique et empirique de cette révolution.D’un point de vue théorique, ce travail se situe dans le cadre de l’analyse économique. Nous nous situons donc dans le prolongement de la littérature économique qui, à partir des années 1970, s’est intéressée aux mouvements sociaux et plus précisément les révolutions. La théorie économique a offert un autre cadre permettant d’analyser la manière dont l’action d’un petit groupe d’individus peut provoquer des bouleversements de grande envergure. L’un des objets de cette thèse est alors de proposer une synthèse de cette littérature. Nous soulignons que cette thèse revient sur les définitions de la révolution et propose une présentation qui essaye d’être exhaustive des analyses économiques des révolutions. Quatre types de modèles sont définis : la méthode décisionnelle, la théorie des jeux, la méthode d'analyse Tobit et le modèle seuil de mobilisation. Ces modèles ont parvenu à expliquer l’émergence d’un mouvement révolutionnaire mais ne prennent pas en compte la particularité de chaque pays, nous insistons en particulier sur ce point. Il n’en est pas moins vrai que, la littérature théorique sur les révolutions a précisé ce caractère unique pour chaque révolution. Autour de cette spécificité, l’idée centrale de cette thèse a été construite : quelles sont les causes de la révolution tunisienne ? En outre, la contribution principale de cette thèse est d’ordre empirique. Bien que de nombreuses recherches aient analysé de différentes manières les causes des révolutions (Données de panel, modèles économétriques), la méthode d’analyse en composantes principales (ACP) est, à notre connaissance, la première contribution dans l’analyse des révolutions et surtout la première étude de ce type appliquée à la Tunisie. Cette méthode a pu détecter trois ramifications caractérisant le 14 janvier 2011. Trois révolutions d’ordre sociologique et sociétal semblent particulièrement importantes : une révolution démographique, une révolution de l’alphabétisation et une révolution des attentes. Premièrement, la transition démographique et ses implications économiques et sociales. Deuxièmement, les inégalités et l’élargissement de la fracture sociale entre les régions. Troisièmement, la mauvaise gestion du pays suite à l’emprise de l’économie sous Ben Ali et ses conséquences catastrophique sur l’investissement et la création d’emploisRevolution, which embodies major turns in the course of history, has for a long time been a social study subject. With the coming of the school of public choice in the 1960's, a new economic current helped to undestand revolution. Many economists such as: James M. Buchanan (1962), Gordon Tullock (1971-1974) and John E. Romer (1985) have applied economic theory to social and political science using tools developed by microeconomy. The goal of my research paper is to highlight the contribution of economic theory in the understanding of revolution. I have first drawn a line between two approaches that have studied revolution: The sociological approach which mainly explains why do people revolt when they are faced with structural imbalances. The economic approach which uses the theory of rational choice to demonstrate how people choose to be passive when they are confronted with a revolution
46
Chenguiti, Khalid. "Analyse en composantes principales fonctionnelle cas des prises alimentaires". Mémoire, Université de Sherbrooke, 2006. http://savoirs.usherbrooke.ca/handle/11143/4722.
Texto completoResumen
Les méthodes d'analyse statistique des données fonctionnelles sont une extension des méthodes de l'analyse statistique des données à des données qui se présentent sous forme de courbes. L'analyse en composantes principales fonctionnelle"ACPF" est une méthode d'analyse statistique qui permet de résumer l'information contenue dans un ensemble de données fonctionnelles, permettant de produire des fonctions dites composantes principales de dimension minimale qui reproduisent un maximum d'information sur les données étudiées. L'application de l'ACPF à des données de prises alimentaires porcines permet de mettre en évidence les avantages de considérer une ACPF au lieu d'une analyse en composantes principales"ACP" usuelle. Les composantes principales obtenues par l'ACPF des courbes de prises alimentaires nous ont permis de résumer les tendances principales régissant le comportement alimentaire des porcs observés. Malgré la complexité des facteurs influençant le processus de prise alimentaire porcine, tels le poids, le contexte social et le changement de composition alimentaire, la synthèse produite par l'ACPF démontre sa pertinence. L'analyse des vitesses et des accélérations à partir des données brutes de la prise alimentaire porcine ont permis de compléter l'analyse permettant de comparer, à travers l'ACPF, les caractéristiques géométriques des courbes. L'analyse en composantes principales a permis de trouver des pistes prometteuses pour la caractérisation des courbes complexes de consommation et la détermination de critères prévisionnels associés aux comportements particuliers causés par le développement de maladies. Les différentes analyses discriminantes exposent clairement ces tendances particulières liées aux phénomènes étudiés et la détection préalable de facteurs de maladies. La synthèse produite par les différentes ACPF permet de mettre en évidence les tendances générales prépondérantes régissant le comportement alimentaire procurant ainsi des informations utilisées pour la modélisation de ce comportement.
47
Méhel, Éric. "Kératotomie radiaire : analyse vidéokératoscopique : à propos de 80 cas". Nantes, 1994. http://www.theses.fr/1994NANT252M.
Texto completo
48
Ochs, Patrick. "L'investissement immatériel et la commercialisation : analyse du cas français". Paris 2, 1995. http://www.theses.fr/1995PA020005.
Texto completoResumen
L'investissement immateriel progresse, en france, de 1973 a 1993 de maniere plus rapide que l'investissement materiel. Cette evolution conjugue a la fois investissement immateriel et depenses immaterielle actuellement l'absence d'indicateu rs d'evaluation financiere pertinents de l'investissement immateriel a caractere commercial ne permet pas aux entreprise s de mesurer les enjeux que representent ces engagements intangibles a court, moyen et long terme. Il s'agit tout d'abord de definir l'investissement immateriel dans le processus de commercialisation de l'entreprise compte tenu des interrelations economiques, financieres, comptables, fiscales et strategiques. Ensuite, il s'agit d'expliquer la contribution de l'investissement immateriel en commercialisation a la fois a la competitivite et a la valeur de l'entreprise. Enfin, il convient de presenter les resultats d'une validation empirique des hypotheses formulees, qui porte sur 8213 entreprises industrielles, et les resultats d'une comparaison de 1109 entreprises qui appartiennent a quatre secteurs d'activite industriels differents. En conclusion, il s'agit de proposer une autre architecture de gestion financiere de l'immateriel et une nouvelle vision patrimoniale de l'investissement immateriel en commercialisationIn france, intangible investment progressed more rapidly than tangible investment between 1973 an 1993. This change draw s together intangible investment and intangible expenditure. At present, for lack of relevant financial indicators to evaluate intangible investment of a business nature, companies are not able to asses the implications involved in these intangible commitments in the short, middle and long ter. . Primarily, it is important to define intangible investment in the company's marketing procedure, given the economic, fin ancial, accounting, fiscal and strategic inter-relationships. There follows an explanation of the contribution of intangible investment in marketing, both to the competitiveness and the value of the company. At this point, an appropri ate presentation is made of the results of an empirical validation of the hypotheses raised; this validation deals with 8213 companies and the results of a comparative study of 1109 companies which belong to four different industrial sector s. The conclusion proposes another framework for financial management of the intangible and a new patrimonial perspectiv e for intangible investment in marketing
49
Hancard, Olivier. "Le défi technologique : analyse théorique et étude de cas". Paris 1, 1997. http://www.theses.fr/1997PA010045.
Texto completoResumen
Le progrès technologique est ses corollaires, le progrès technique et le progrès scientifique, forment une trilogie analytique qui recouvre des enjeux économiques empiriques doubles d'un défi théorique et conceptuel. Après avoir développé une lecture critique du débat théorique "traditionnel", nous le projetons dans l'univers conceptuel néo-darwiniste. La démarche, sans être infructueuse, rencontre ses propres limites. Nous nous tournons alors vers une "macroéconomie de la production de connaissances". Nous définissons l'efficience macroéconomique de cette "production cognitive" (production d'une connaissance neuve dont l'assimilation est la cognition), par l'équilibre entre deux phénomènes antagonistes : la diffusion et la germination. Nous développons subséquemment une autre modélisation sur la "sur-germination" stratégique des politiques scientifiques et technologiques nationales sous la pression des rivalités technologiques internationales. Nous proposons également des réflexions théoriques sur des stratégies de RD plus surprenantes, et sur la nature cognitive des produits économiques (par référence à la distinction entre artisanat, art et industrie). Nous interceptons des problèmes de théorie de la valeur. Par ailleurs, le technologique est aussi un défi économique empirique. Internationalement, nous comparons globalement les dynamiques de RD, avant d'étudier trois "micro-défis" technologiques (l'innovation sur les métaux, Le travail des métaux et les polymères), et deux thèmes microéconomiques particulières (un cas de coopération inter firmes en RD, et, enfin, la petite entreprise technologique en France)Technological progress and its corollaries, technical improvement and scientific progress, constitute an analytical trilogy, which determine some empirical economic stakes as some theoretical and conceptual challenges. After having developed a critical reading of the "usual" theoretical discussion, we open this debate to neo-darwinist concepts. The procedure, not totally fruitless, comes up against its own bounds. Therefore, we choose then to argue about constitution of a "macroeconomic analysis of knowledge production". We define macroeconomic efficiency of the "cognitive production" (the production of a new knowledge whose assimilation is cognition), by an equilibrium between two antagonist dynamics : "diffusion" and "germination". Subsequently, we build another model about strategic "over-germination" of national scientific and technological policies under pressure of international technological rivalries. We also propose some theoretical reflexions about astonishing forms of R&D strategies, and about the cognitive economic nature of different kinds of products (by using a conceptual distinction between the "artisan craft", the "artist production" and the "industrial product"). We are coming up to problems concerning the value theory. Then, we overcome the theoretical discussion to face some empirical technological challenges. Internationally, we first compare R&D dynamics, before studying three "micro-technological challenges" (innovation on metals, work of metals and polymers), and, finally, two microeconomic subjects (a case of joint r&d between independant firms, a description of the small technological French firm)
50
Khalil, Emam. "Analyse du dumping et de l'antidumping : cas de l'Egypte". Caen, 2009. http://www.theses.fr/2009CAEN0658.
Texto completoResumen
Cette thèse s'articule autour de quatre axes principaux. Nous commençons par une analyse détaillée des définitions économiques et légales du dumping, ce qui nous permet de relier les problèmes de détermination et d'évaluation du préjudice à l'interprétation des termes juridiques et à la divergence des méthodes de calcul. Sont, ensuite, exposés et analysés les mécanismes de l'antidumping, leur fonctionnement et leur intérêt économique pour les pays développés et émergeants. Les mesures antidumping sont devenues l'outil le plus utilisé en termes de politique commerciale, la recherche se propose de clarifier les liens entre cette politique, le protectionnisme et le libre échange. Le troisième thème est consacré à une description des différents dispositifs antidumping : ceux de l'OMC, de l'UE, des USA et de l'Egypte. Nous orienterons alors notre recherche vers une étude de l'efficacité du système égyptien d'antidumping (SEAD), sa conformité avec les accords de l'OMC et ses éventuelles améliorations. Dans la dernière partie de ce travail, nous mettons en évidence l'impact des droits antidumping (et de l'usage, éventuellement abusif, des mesures antidumping) sur le bien-être social, à travers une étude sectorielle du marché de l'acier en Egypte.