Stateless model checking is a technique for testing and verifying concurrent programs, based on exploring the different ways in which operations executed by the processes of a concurrent program can be scheduled. The goal of the technique is to expose all behaviours that can be a result of scheduling non-determinism. As the number of possible schedulings is huge, however, techniques that reduce the number of schedulings that must be explored to achieve verification have been developed. Dynamic partial order reduction (DPOR) is a prominent such technique. This dissertation presents a number of improvements to dynamic partial order reduction that significantly increase the effectiveness of stateless model checking. Central among these improvements are the Source and Optimal DPOR algorithms (and the theoretical framework behind them) and a technique that allows the observability of the interference of operations to be used in dynamic partial order reduction. Each of these techniques can exponentially decrease the number of schedulings that need to be explored to verify a concurrent program. The dissertation also presents a simple bounding technique that is compatible with DPOR algorithms and effective for finding bugs in concurrent programs, if the number of schedulings is too big to make full verification possible in a reasonable amount of time, even when the improved algorithms are used. All improvements have been implemented in Concuerror, a tool for applying stateless model checking to Erlang programs. In order to increase the effectiveness of the tool, the interference of the high-level operations of the Erlang/OTP implementation is examined, classified and precisely characterized. Aspects of the implementation of the tool are also described. Finally, a use case is presented, showing how Concuerror was used to find bugs and verify key correctness properties in repair techniques for the CORFU chain replication protocol. / UPMARC / RELEASE

A computationally efficient, discrete model is presented for transmission line analysis and passive model order reduction of high-speed interconnect systems. The development of this model was motivated by the on-going efforts in chip/package co-design to route a major portion of the on-chip clock and high-speed data buses through the package in order to overcome the bandwidth reduction and delay caused by the high ohmic loss of on-chip wiring. The geometric complexity of the resulting interconnections is such that model order reduction is essential for rapid and accurate signal integrity assessment to support pre-layout design iteration and optimization. The modal network theory of the skin effect in conjunction with the theory of compact differences is used for the development of discrete models for dispersive, multi-conductor interconnects compatible with passive model order reduction algorithms. The passive reduced-order interconnect modeling algorithm, PRIMA, is then used on the resulting discrete model to generate a low-order, multi-port macromodel for interconnect networks. Numerical examples are used to demonstrate the validity and efficiency of the proposed model.

Le domaine de l'interaction fluide-structure regroupe l'étude de tous les phénomènes présentant le couplage du mouvement d'une structure avec celui d'un fluide. La gamme des phénomènes étudiés est très étendue, allant de l'étude de cylindres vibrants dans des écoulements comme c'est le cas dans l'industrie nucléaire, à des structures vibrantes dans des écoulements turbulents, en passant par des phénomènes de surface libre dans des réservoirs. Cependant, la complexité des phénomènes étudiés se répercute par des coûts de calculs prohibitifs, ce qui nous amène à rechercher des modèles réduits dont le temps de calcul serait plus réaliste. Dans cette thèse, on va présenter les différents modèles d'interaction fluide-structure et on va mettre en avant le modèle adopté dans notre étude. La réduction du modèle ainsi que l'optimisation des structures vont être introduites dans un contexte de couplage. En introduisant les incertitudes, l'étude fiabiliste de même qu'une approche d'optimisation basée fiabilité vont être proposées. Les différentes méthodologies adoptées vont être validées numériquement et comparées expérimentalement / The domain of the fluid-structure interaction includes the study of all phenomena presenting the coupling of the motion of a structure with the one of a fluid. The range of the phenomena being studied is very extensive, going from the study of vibrating cylinders in the flow as is the case in the nuclear industry, to vibrating structures in turbulent flows, through the free surface phenomena in reservoirs. However, the complexity of the phenomena studied is reflected by the cost of the prohibitive calculations, which leads us to look for models with the computation time would be more realistic. In this thesis, we will present different models of fluid-structure interaction and we will put forward the model adopted in our study. Reducing the model as well as the optimization of the structures will be introduced into a coupling setting. By introducing uncertainties, the reliability study as well as an optimization based reliability approach will be proposed. The different methodologies adopted will be validated numerically and experimentally compared

Two methods using lumped element (lumped parameter) methods to model flexible bodies have been presented. The methods are based on the concept of using a Guyan reduced stiffness matrix to describe the elasticity of a body. The component to be modeled has been divided into two parts using FE software and the mass and inertia tensor for the respective part of the component have been retrieved. The first method has been based on including the elements from the stiffness matrix in compliant constraints. The compliant constraints have been derived and a prototype has been implemented in MATLAB. It has been shown that using compliant constraints and stiffness parameters from a Guyan reduced stiffness matrix it is possible, with highly accurate results, to describe the deformation of a flexible body in multibody simulations. The second method is based on springs and dampers and has been implemented in the simulation environment Dymola. The springs and dampers have been constructed to include coupling elements from a Guyan reduced stiffness matrix. It has been shown that using the proposed method it is possible, with highly accurate results, to describe the static deformation of a flexible body. Further, using dynamic simulations of a full robot manipulator model, it has been shown that it is possible to use the spring-damper model to capture the deformation of the links of a manipulator in dynamic simulations with large translations and rotations.

Les progrès constants en miniaturisation des transistors et l’augmentation des fréquences des signaux utilisés sont les principales tendances dans l’évolution des circuits électroniques. Avec ces évolutions apparaissent de nombreux effets indésirables qui perturbent le comportement des systèmes électroniques et sont soupçonnés d’être responsables de la majorité des dégradations de signaux dans les systèmes en haute fréquence. Des retards de propagation indésirables sont ainsi introduits par la présence des interconnexions, et la diaphonie, phénomène dû aux couplages entre lignes d’interconnexions, peut éventuellement provoquer des commutations non désirées des transistors. La prise en compte des interconnexions, dès les premières phases de conception d'un système, est par conséquent devenue une nécessité ces dernières années. Mais la simulation temporelle d’un réseau d’interconnexions est très gourmande en temps de calcul, ce qui impacte la durée globale de conception. Le remplacement des modèles électriques, décrivant précisément les interconnexions, par des modèles plus simples est primordial pour limiter les coûts de calcul. Une méthode de réduction d'ordre des modèles peut alors être employée pour effectuer cette opération efficacement. Le modèle final doit en effet décrire assez précisément certains aspects importants du modèle original et conserver les propriétés importantes du réseau d'interconnexions. Cette démarche permettra aux concepteurs d’effectuer des simulations temporelles rapides et d’étudier les paramètres d’intégrité du signal tel que le retard, le temps de montée, le dépassement….L'objectif de cette thèse est d’établir un nouvel outil de réduction de complexité des modèles de réseaux d'interconnexions. Différentes descriptions initiales des systèmes d'interconnexions sont envisagées : modèles circuits (fonctions de transfert) ou mesures fréquentielles. L’approche développée repose sur l’utilisation des fonctions orthogonales de Müntz-Laguerre et de Kautz afin de décrire mathématiquement, de manière précise, le système d'origine. Un opérateur linéaire, lié à ces fonctions de base, est ensuite appliqué pour déterminer un modèle rationnel de moindre complexité. La technique proposée est comparée à d'autres méthodes de la littérature d’abord sur des exemples académiques. Tout le potentiel de la méthode est ensuite illustré par sa mise en œuvre sur des réseaux d'interconnexions. / The ongoing progress in transistor miniaturization and a continuous frequency increase are the main trends in the present day evolution of electronic circuits. A number of undesired effects are intrinsic to these developments and are suspected to be responsible for most of the flawed signals present in high frequency systems. Parasitic delays are thus introduced by the presence of interconnect lines and crosstalk due to coupling may lead to undesired switching events in transistor circuits. Accounting for the presence of interconnect lines, at a very early stage in the design flow has become unavoidable in recent years. However, time domain simulations of massively coupled interconnect networks may be computationally costly and have a tremendous impact on the overall duration of the design process. Replacing complex, high order circuit models by more compact surrogates is thus necessary. Model order reduction is an effective way to derive such surrogates. The final model must mimic certain aspects of the original model with sufficient accuracy and preserve the interconnect network’s most important properties. This approach enables designers to account for the undesired effects of interconnect lines such as, delays, rise-times and overshoots while maintaining the overall duration of time-domain simulations within acceptable limits. The aim of this thesis is to create a new model order reduction tool applicable to complex interconnect networks. Different initial representations were considered – circuit models (transfer functions) or frequency domain measurements. The proposed approach uses orthogonal basis functions such as Müntz-Laguerre and Kautz to build an accurate mathematical representation of the original system .A linear operator, related to these functions, is subsequently used to derive a simplified model. The technique is first compared to other approaches using examples available in literature, its full potential being demonstrated on coupled interconnect models.

In this paper we describe an approach to generating low-order models of spiral inductors that accurately capture the dependence on both frequency and geometry (width and spacing) parameters. The approach is based on adapting a multiparameter Krylov-subspace based moment matching method to reducing an integral equation for the three dimensional electromagnetic behavior of the spiral inductor. The approach is demonstrated on a typical on-chip rectangular inductor. / Singapore-MIT Alliance (SMA)

The research described in this dissertation deals with an open problem concerning the synthesis of controllers of xed order and structure. This problem is encountered in a variety of applications. Simply put, the problem may be put as the determination of the set, S of controller parameter vectors, K = (k1; k2; : : : ; kl), that render Hurwitz a family (indexed by F) of complex polynomials of the form fP0(s; ) + Pl i=1 Pi(s; )ki; 2 Fg, where the polynomials Pj(s; ); j = 0; : : : ; l are given data. They are specied by the plant to be controlled, the structure of the controller desired and the performance that the controllers are expected to achieve. Simple examples indicate that the set S can be non-convex and even be disconnected. While the determination of the non-emptiness of S is decidable and amenable to methods such as the quantier elimination scheme, such methods have not been computationally tractable and more importantly, do not provide a reasonable approximation for the set of controllers. Practical applications require the construction of a set of controllers that will enable a control engineer to check the satisfaction of performance criteria that may not be mathematically well characterized. The transient performance criteria often fall into this category. From the practical viewpoint of the construction of approximations for S, this dissertation is dierent from earlier work in the literature on this problem. A novel feature of the proposed algorithm is the exploitation of the interlacing property of Hurwitz polynomials to provide arbitrarily tight outer and inner approximation to S. The approximation is given in terms of the union of polyhedral sets which are constructed systematically using the Hermite-Biehler theorem and the generalizations of the Descartes' rule of signs.

The research described in this dissertation deals with an open problem concerning the synthesis of controllers of xed order and structure. This problem is encountered in a variety of applications. Simply put, the problem may be put as the determination of the set, S of controller parameter vectors, K = (k1; k2,...,kl), that render Hurwitz a family (indexed by F) of complex polynomials of the form {P0(s.a) + [summation] i=1 Pi(s,a)ki, a [set membership] F}, where the polynomials Pj(s,a), j = 0,...,l are given data. They are specied by the plant to be controlled, the structure of the controller desired and the performance that the controllers are expected to achieve. Simple examples indicate that the set S can be non-convex and even be disconnected. While the determination of the non-emptiness of S is decidable and amenable to methods such as the quantier elimination scheme, such methods have not been computationally tractable and more importantly, do not provide a reasonable approximation for the set of controllers. Practical applications require the construction of a set of controllers that will enable a control engineer to check the satisfaction of performance criteria that may not be mathematically well characterized. The transient performance criteria often fall into this category. From the practical viewpoint of the construction of approximations for S, this dissertation is dierent from earlier work in the literature on this problem. A novel feature of the proposed algorithm is the exploitation of the interlacing property of Hurwitz polynomials to provide arbitrarily tight outer and inner approximation to S. The approximation is given in terms of the union of polyhedral sets which are constructed systematically using the Hermite-Biehler theorem and the generalizations of the Descartes' rule of signs.

The full model of a double-wishbone suspension has more than 30 differential-algebraic equations which takes a remarkably long time to simulate. By contrast, the look-up table for the same suspension is simulated much faster, but may not be very accurate. Therefore, developing reduced models that approximate complex systems is necessary because model reduction decreases the simulation time in comparison with the original model, enables real time applications, and produces acceptable accuracy. In this research, we focus on model reduction techniques for vehicle systems such as suspensions and how they are approximated by models having lower degrees of freedom. First, some existing model reduction techniques, such as irreducible realization procedures, balanced truncation, and activity-based reduction, are implemented to some vehicle suspensions. Based on the application of these techniques, their disadvantages are revealed. Then, two methods of model reduction for multi-body systems are proposed. The first proposed method is 2-norm power-based model reduction (2NPR) that combines 2-norm of power and genetic algorithms to derive reduced models having lower degrees of freedom and fewer number of components. In the 2NPR, some components such as mass, damper, and spring are removed from the original system. Afterward, the values of the remaining components are adjusted by the genetic algorithms. The most important advantage of the 2NPR is keeping the topology of multi-body systems which is useful for design purposes. The second method uses proper orthogonal decomposition. First, the equations of motion for a multi-body system are converted to explicit second-order differential equations. Second, the projection matrix is obtained from simulation or experimental data by proper orthogonal decomposition. Finally, the equations of motion are transferred to a lower-dimensional state coordinate system. The implementation of the 2NPR to two double-wishbone suspensions and the comparison with other techniques such as balanced truncation and activity-based model reduction also demonstrate the efficiency of the new reduction technique.

The factored state representation and concurrency semantics of Petri nets are closely related to those of classical planning models, yet automated planning and Petri net analysis have developed independently, with minimal and mainly unconvincing attempts at crossfertilisation. This thesis exploits the relationship between the formal reachability problem, and the automated planning problem, via Petri net unfolding, which is an attractive reachability analysis method for highly concurrent systems as it facilitates reasoning about independent sub-problems. The first contribution of this thesis is the theory of directed unfolding: controlling the unfolding process with informative strategies, for the purpose of optimality and increased efficiency. The second contribution is the application of directed unfolding to automated planning. Inspired by well-known planning heuristics, this thesis shows how problem specific information can be employed to guide unfolding, in response to the formal problem of developing efficient, directed reachability analysis methods for concurrent systems. Complimenting this theoretical work, this thesis presents a new forward search method for partial order planning which can be exponentially more efficient than state space search. Our suite of planners based on directed unfolding can perform optimal and suboptimal classical planning subject to arbitrary action costs, optimal temporal planning with respect to arbitrary action durations, and address probabilistic planning via replanning for the most likely path. Empirical results reveal directed unfolding is competitive with current state of the art automated planning systems, and can solve Petri net reachability problems beyond the reach of the original “blind” unfolding technique. / Thesis (Ph.D.) -- University of Adelaide, School of Electrical and Electronic Engineering, 2008