No description available.

Miniaturisation of electronic chips poses challenges at the design stage. The progressively decreasing circuit dimensions result in complex electrical behaviour that necessitates complex models. Simulation of complex circuit models involves extraordinarily large compu- tational complexity. Such complexity is better managed through Model Order Reduction. Model order reduction has been successful in large reductions in system order for most types of circuits, at high levels of accuracy. However, multiport circuits with large number of inputs/outputs, pose an additional computational challenge. A strategy based on exible clustering of interconnects results in more e cient reduction of multiport circuits. Clustering methods traditionally use Krylov-subspace methods such as PRIMA for the actual model reduction step. These clustering methods are unable to reduce the model order to the optimum extent. SVD-based methods like Truncated Balanced Realization have shown higher reduction potential than Krylov-subspace methods. In this thesis, the di erences in reduction potential and computational cost thereof between SVD-based methods and Krylov-subspace methods are identi ed, analyzed and quanti ed. A novel algorithm has been developed, utilizing a particular combination of both these methods to achieve better results. It enhances the clustering method for model reduction using Truncated Balanced Realization as a second-level reduction technique. The algorithm is tested and signi cant gains are illustrated. The proposed novel algorithm preserves the other advantages of the current clustering algorithm.

Le travail présenté dans ce mémoire s'intéresse à la simulation du comportement mécanique de câbles d'ascenseurs. Le but de ce travail est d'élaborer une méthode permettant de simuler le comportement mécanique de tels câbles à moindre coût, et avec une précision suffisante.Dans un premier temps, différentes méthodes permettant de modéliser ou de simuler le comportement de ces câbles ont été comparées, et leurs avantages et inconvénients ont été analysés. Les résultats de modèles analytiques et de simulations éléments finis ont été comparés avec des données expérimentales. Les modèles analytiques considérés dans ce travail présentent un coût de calcul bien moins élevé que les modèles éléments finis, mais n'offrent pas une précision suffisante dans leurs résultats pour simuler le comportement de câbles d'ascenseurs. L'approche éléments finis a été retenue pour cette raison comme la plus adaptée pour simuler ce genre de câbles. Les coûts de calcul liés à cette approche sont cependant très élevés, et demandent la mise en oeuvre de méthodes particulières en vue de les réduire.Afin de réduire les temps de calculs, trois types de méthodes ont été considérées : les méthodes d'homogénéisation, les méta-modèles, et les techniques de réduction de modèle. L'approche de réduction de modèle a été retenue comme la plus appropriée et a été implémentée dans le code de simulation par éléments finis Multifil. Des résultats avec une bonne précision ont été obtenus en utilisant cette méthode, mais les coûts des simulations initiales sur le modèle complet afin d'obtenir un ensemble de solutions permettant de construire une base réduite apparaissent trop élevés dès qu'il s'agit de traiter des câbles de longueurs importantes. Pour remédier à ce problème, une méthode de réduction par tronçon a été formulée et implémentée. Cette méthode tire parti de la structure périodique du câble et permet d'identifier a base de réduction seulement sur un motif périodique élémentaire. Cette base est ensuite utilisée pour représenter la solution sur l'ensemble d'un câble composé de plusieurs tronçons.Le coût des multiplications matricielles nécessaires pour transformer le système linéaire du problème initial, en système linéaire réduit reste cependant trop important pour obtenir un gain significatif, en particulier dans le contexte de la résolution d'un problème non-linéaire. Pour pallier cette difficulté, une technique supplémentaire, appelée ``Discrete Empirical Interpolation Method'' (DEIM), a été mise en oeuvre avec succès, et a permis d'obtenir au final une réduction du coût de calcul d'un facteur 4. / The work presented in this dissertation is focused on the simulation of the mechanical behaviour of lift's wire ropes. The aim of the work is to elaborate a method to simulate the mechanical behaviour of such wire ropes with low computational cost and sufficient accuracy.First of all, several methods to model or simulate wire ropes have been compared and their weak and strong points have been highlighted. Analytical and finite element methods have been compared with experimental tests. It was concluded that analytical methods considered in this work have a lower computational cost than finite element methods, but the results obtained using them are not accurate enough to simulate lift wire ropes. Therefore, finite element methods have been considered as the most appropriate to simulate these wire ropes. However, their computational cost is high so some methods to reduce it must be applied.In order to reduce the computational time, three type of methods have been considered: homogenization, metamodeling and model order reduction. Model order reduction technique was chosen as the most adequate method and it was implemented in the wire rope finite element simulation program Multifil. Accurate results have been obtained, however the computational cost needed by initial simulations to get the snapshots used to define a reduce basis was too high for long wire ropes. To solve this problem, a sectionwise reduction method was proposed and implemented. This formulation takes advantage of the periodic structure of wire ropes: the reduced basis is identified only on a reference elementary section and used for all repetitive sections of a multi-section wire rope. The computational cost induced by the multiplication of matrices in order to transform the linear system of the initial problem into the linear system of the reduced problem was shown to remain too high, particularly in the context of the solving of a non-linear problem, to allow the global computational time to be significantly decreased using the proposed techniques. To overcome this difficulty, an additional technique, namely the so-called Discrete Empirical Interpolation Method (DEIM) was successfully implemented and tested, allowing a time reduction factor of 4 to be obtained.

Small signal stability has always been an important concern for analog designers. Recent advances such as the Loop Finder algorithm allows designers to detect and identify local, potentially unstable return loops without the need to identify and add breakpoints. However, this method suffers from extremely high time and memory complexity and thus cannot be scaled to very large analog circuits. In this research work, we first take an in-depth look at the loop finder algorithm so as to identify certain key enhancements that can be made to overcome these shortcomings. We next propose pole discovery and impedance computation methods that address these shortcomings by exploring only a certain region of interest in the s-plane. The reduced time and memory complexity obtained via the new methodology allows us to extend automatic stability checking to much larger circuits than was previously possible.

Fast methods for the electromagnetic simulation of integrated circuit (IC) package modules through model order reduction are demonstrated. The 3D integration of multiple functional IC chip/package modules on a single platform gives rise to geometrically complex structures with strong electromagnetic phenomena. This motivates our work on a fast full-wave solution for the analysis of such modules, thus contributing to the reduction in design cycle time without loss of accuracy. Traditionally, fast design approaches consider only approximate electromagnetic effects, giving rise to lumped-circuit models, and therefore may fail to accurately capture the signal integrity, power integrity, and electromagnetic interference effects. As part of this research, a second order frequency domain full-wave susceptance element equivalent circuit (SEEC) model will be extracted from a given structural layout. The model so obtained is suitably reduced using model order reduction techniques. As part of this effort, algorithms are developed to produce stable and passive reduced models of the original system, enabling fast frequency sweep analysis. Two distinct projection-based second order model reduction approaches will be considered: 1) matching moments, and 2) matching Laguerre coefficients, of the original system's transfer function. Further, the selection of multiple frequency shifts in these schemes to produce a globally representative model is also studied. Use of a second level preconditioned Krylov subspace process allows for a memory-efficient way to address large size problems.

Large scale linear time invariant (LTI) systems arise in many physical and technical fields. An approximation, e.g. with model order reduction techniques, of this large systems is crucial for a cost efficient simulation. In this thesis we focus on a model order reduction method based on modal approximation, where the LTI system is projected onto the left and right eigenspaces corresponding to the dominant poles of the system. These dominant poles are related to the most dominant parts of the residue expansion of the transfer function and usually form a small subset of the eigenvalues of the system matrices. The computation of this dominant poles can be a formidable task, since they can lie anywhere inside the spectrum and the corresponding left eigenvectors have to be approximated as well. We investigate the subspace accelerated dominant pole algorithm and the two-sided and alternating Jacobi-Davidson method for this modal truncation approach. These methods can be seen as subspace accelerated versions of certain Rayleigh quotient iterations. Several strategies that admit an efficient computation of several dominant poles of single-input single-output LTI systems are examined. Since dominant poles can lie in the interior of the spectrum, we discuss also harmonic subspace extraction approaches which might improve the convergence of the methods. Extentions of the modal approximation approach and the applied eigenvalue solvers to multi-input multi-output are also examined. The discussed eigenvalue algorithms and the model order reduction approach will be tested for several practically relevant LTI systems.

Cette thèse s’inscrit dans le cadre de l’étude du post-flambement local des grandes struc- tures composites raidies. La simulation du post- flambement par la méthode des éléments- finis est aujourd’hui limitée par le coût du calcul en particulier pour les grandes structures. Seules des zones restreintes peuvent être étudiées, en négligeant les interactions global/local. L’objectif de cette thèse est de proposer une stratégie de calcul performante pour la simula- tion du post-flambement local des grandes structures raidies à partir des connaissances sur le comportement mécanique des structures en post-flambement et d’un découpage naturel le long des raidisseurs favorable au calcul parallèle.Dans la littérature, les méthodes de réduction de modèle adaptative ont démontré leur ca- pacité à réduire le nombre d’inconnues tout en maîtrisant l’erreur d’approximation de la solution des problèmes non-linéaires. Par ailleurs, les méthodes de décomposition de do- maine avec localisation non-linéaire sont particulièrement adaptées au calcul parallèle en mécanique des structures en présence de non-linéarités locales.Les travaux de thèse portent dans un premier temps sur une stratégie de réduction de modèle adaptative spécifique au cas du post-flambement. Dans le cas d’un flambement local d’une grande structure raidie une combinaison avec une méthode de décomposition de domaine primale est ensuite proposée. Toutes ces stratégies sont implémentées dans un code de re- cherche programmé pendant la thèse. / This thesis is part of the study of local post-buckling of large stiffened composite struc- tures. The finite element simulation of structures subjected to post-bucking still faces com- putational limits, especially for large structures. Only restricted area may be studied for now, neglecting global/local interactions.The aim of the thesis is to propose an efficient computational strategy for local post-buckling analysis of large stiffened structures from knowledge on mechanical behavior of post-buckling structures and a natural partitionning along stiffeners conducive to parallel computation. In litterature, the adaptive model reduction solving techniques have demonstrated their abi- lity to drastically reduce the number of unknowns as well as to control the approximation error of solving non-linear problems. Furthermore, domain decomposition methods with a non-linear local step are suited to parallel computation in structural mechanics in the pre- sence of local non-linearities.Our work deals first with an adaptive model reduction strategy dedicated to post-buckling problems. In order to adress larger stiffened structures subjected to local post-buckling, like an aircraft fuselage, partitioning is then performed. The model reduction, as well as the adap- tive procedure are written in the framework of the primal domain decomposition method with a non-linear local step. These strategies are implemented in a research code developed for the purpose of the thesis.

Doctor of Philosophy / Department of Computing and Information Science / John M. Hatcliff / With the advent of multi-core processors and rich language support for concurrency, the paradigm of concurrent programming has arrived; however, the cost of developing and maintaining concurrent programs is still high. Simultaneously, the increase in social ubiquity of computing is reducing the "time-to-market" factor while demanding stronger correctness requirements. These effects are amplified with ever-growing size of software systems. Consequently, there is (will be) a rise in the demand for scalable and accurate techniques to enable faster development and maintenance of correct large scale concurrent software. This dissertation presents a collection of scalable and accurate approaches to tackle the above situation. Primarily, the approaches are focused on discovering dependences (relations) between various parts of the software/program and leveraging the dependences to improve maintenance and development tasks via program slicing (comprehension) and verification. Briefly, the proposed approaches are embodied in the following specific contributions: 1. New trace-based foundation for control dependences. 2. An equivalence class based analysis to efficiently and accurately calculate escape information and intra- and inter-thread dependences. 3. A new parametric data flow style slicing algorithm with various extensions to uniformly and easily realize and reason about most existing forms of static sequential and concurrent slicing. 4. A new generic notion of property/trace sensitivity to represent and reason about richer forms of context sensitivity. 5. Program dependence based partial order reduction techniques to enable efficient and accurate state space exploration in both static and dynamic mode. In an attempt to simplify the approaches, they have been based on the basic concepts/ideas of the affected techniques (e.g. program slicing is a rooted transitive closure of dependence relation). As trace-based reasoning is well suited for concurrent systems, an attempt has been made to explore trace-based reasoning wherever possible. While providing a rigorous theoretical presentation of these techniques, this effort also validates the techniques by implementing them in a robust tool framework called Indus (available from http://indus.projects.cis.ksu.edu) and then providing experimental results that demonstrate the effectiveness of the techniques on various concurrent applications. Given the current trend towards concurrent programming and social ubiquity of computing, the approaches proposed in this dissertation provide a foundation for collectively attacking scalability, accuracy, and soundness challenges in current and emerging systems.

Les applications de transmission de messages distribués font partie du courant dominant des technologies de l'information car elles exploitent la puissance des systèmes informatiques parallèles pour produire des performances plus élevées. La conception de programmes distribués reste difficile car les développeurs doivent raisonner sur la concurrence, le non-déterminisme, la distribution de données… qui sont les principales caractéristiques des programmes distribués. En outre, il est pratiquement impossible de garantir l'exactitude de tels programmes via des approches de test classiques, car il est possible que l'on n'atteigne jamais avec succès l'exécution qui conduit à des comportements indésirables dans les programmes. Il existe donc un besoin de techniques de vérification plus puissantes. La vérification des modèles est l'une des méthodes formelles qui permet de vérifier automatiquement et efficacement certaines propriétés des modèles de systèmes informatiques en explorant tous les comportements possibles (états et transitions) du modèle de système. Cependant, les espaces d'état augmentent de façon exponentielle avec le nombre de processus simultanés, conduisant à une «explosion de l'espace d'état» .La réduction dynamique de l'ordre partiel basée sur le dépliage (UDPOR) est une technique récente mélangeant la réduction dynamique de l'ordre partiel (DPOR) avec des concepts de théorie de la concurrence tels que dépliages pour atténuer efficacement l'explosion de l'espace d'états lors de la vérification des modèles de programmes simultanés. Il est optimal dans le sens où chaque trace de Mazurkiewicz, c'est-à-dire une classe d'entrelacements équivalents en commutant des actions indépendantes adjacentes, est explorée exactement une fois. Et elle s'applique aux programmes en cours d'exécution, pas seulement aux modèles de programmes.La thèse vise à adapter UDPOR pour vérifier les programmes distribués asynchrones (par exemple les programmes MPI) dans le cadre du simulateur SIMGRID d'applications distribuées. Pour ce faire, un modèle de programmation abstrait de programmes distribués asynchrones est défini et formalisé en langage TLA +, permettant de définir avec précision une relation d'indépendance, ingrédient principal de la sémantique concurrentielle. Ensuite, l'adaptation de l'UDPOR, impliquant la construction d'un dépliage, est rendue efficace par une analyse précise des dépendances dans le modèle de programmation, permettant des calculs efficaces d'opérations habituellement coûteuses. Un prototype d'implémentation d'UDPOR adapté aux programmes asynchrones distribués a été développé, donnant des résultats expérimentaux prometteurs sur un ensemble significatif de références. / Distributed message passing applications are in the mainstream of information technology since they exploit the power of parallel computer systems to produce higher performance. Designing distributed programs remains challenging because developers have to reason about concurrency, non-determinism, data distribution… that are main characteristics of distributed programs. Besides, it is virtually impossible to ensure the correctness of such programs via classical testing approaches since one may never successfully reach the execution that leads to unwanted behaviors in the programs. There is thus a need for more powerful verification techniques. Model-checking is one of the formal methods that allows to verify automatically and effectively some properties on models of computer systems by exploring all possible behaviors (states and transitions) of the system model. However, state spaces increase exponentially with the number of concurrent processes, leading to “state space explosion”.Unfolding-based Dynamic Partial Order Reduction (UDPOR) is a recent technique mixing Dynamic Partial Order Reduction (DPOR) with concepts of concurrency theory such as unfoldings to efficiently mitigate state space explosion in model-checking of concurrent programs. It is optimal in the sense that each Mazurkiewicz trace, i.e. a class of interleavings equivalent by commuting adjacent independent actions, is explored exactly once. And it is applicable to running programs, not only models of programs.The thesis aims at adapting UDPOR to verify asynchronous distributed programs (e.g. MPI programs) in the setting of the SIMGRID simulator of distributed applications. To do so, an abstract programming model of asynchronous distributed programs is defined and formalized in the TLA+ language, allowing to precisely define an independence relation, a main ingredient of the concurrency semantics. Then, the adaptation of UDPOR, involving the construction of an unfolding, is made efficient by a precise analysis of dependencies in the programming model, allowing efficient computations of usually costly operation. A prototype implementation of UDPOR adapted to distributed asynchronous programs has been developed, giving promising experimental results on a significant set of benchmarks.

La simulation numérique, c'est-à-dire l'utilisation des ordinateurs pour exécuter un programme physique, est une partie importante du monde technologique actuel. Elle est nécessaire dans de nombreux domaines scientifiques et techniques pour étudier le comportement de systèmes dont les modèles mathématiques sont trop complexes pour fournir des solutions analytiques et elle rend possible l'évaluation virtuelle des réponses des systèmes (jumeaux virtuels). Cela réduit considérablement le nombre de tests expérimentaux nécessaires à la conception précise du système réel que le modèle numérique représente. Cependant, ces jumeaux virtuels, basés sur des méthodes classiques qui utilisent une représentation fine du système (ex. méthode des éléments finis), permettent rarement une rétroaction en temps réel, même dans un contexte de calcul haute performance, fonctionnant sur des plateformes puissantes. Dans ces circonstances, les performances en temps réel requises dans certaines applications sont compromises. En effet, les jumeaux virtuels sont statiques, c'est-à-dire qu'ils sont utilisés dans la conception de systèmes complexes et de leurs composants, mais on ne s'attend pas à ce qu'ils prennent en compte ou assimilent des données affin de définir des systèmes d'application dynamiques pilotés par les données. De plus, des écarts significatifs entre la réponse observée et celle prévue par le modèle sont généralement constatés en raison de l'imprécision des modèles employés, de la détermination des paramètres du modèle ou de leur évolution dans le temps. Dans cette thèse, nous proposons différentes méthodes pour résoudre ces handicaps affin d'effectuer une surveillance et un contrôle en temps réel. Dans la première partie, les techniques de Réduction de Modèles sont utilisées pour tenir compte des contraintes en temps réel; elles calculent une bonne approximation de la solution en simplifiant la procédure de résolution plutôt que le modèle. La précision de la solution n'est pas compromise et des simulations e-caces peuvent être réalisées (jumeaux numériquex). Dans la deuxième partie, la modélisation pilotée par les données est utilisée pour combler l'écart entre la solution paramétrique calculée, en utilisant des techniques de réduction de modèles non intrusives, et les champs mesurés, affin de rendre possibles des systèmes d'application dynamiques basés sur les données (jumeaux hybrides). / Numerical simulation, the use of computers to run a program which implements a mathematical model for a physical system, is an important part of today technological world. It is required in many scientific and engineering fields to study the behavior of systems whose mathematical models are too complex to provide analytical solutions and it makes virtual evaluation of systems responses possible (virtual twins). This drastically reduces the number of experimental tests for accurate designs of the real system that the numerical model represents. However these virtual twins, based on classical methods which make use of a rich representations of the system (e.g. finite element method), rarely allows real-time feedback, even when considering high performance computing, operating on powerful platforms. In these circumstances, the real-time performance required in some applications are compromised. Indeed the virtual twins are static, that is, they are used in the design of complex systems and their components, but they are not expected to accommodate or accommodate or assimilate data so as to define dynamic data-driven application systems. Moreover significant deviations between the observed response and the one predicted by the model are usually noticed due to inaccuracy in the employed models, in the determination of the model parameters or in their time evolution. In this thesis we propose different methods to solve these handicaps in order to perform real-time monitoring and control. In the first part Model Order Reduction (MOR) techniques are used to accommodate real-time constraints; they compute a good approximation of the solution by simplifying the solution procedure instead of the model. The accuracy of the predicted solution is not compromised and efficient simulations can be performed (digital twins). In the second part data-driven modeling are employed to fill the gap between the parametric solution, computed by using non-intrusive MOR techniques, and the measured fields, in order to make dynamic data-driven application systems possible (hybrid twins).