This thesis presents a new method for the controllable damping of deformable objects. The method evolves from physically based techniques; however, it allows for non-physical, but visually plausible motion. This flexibility leads to a simple interface, with intuitive control over the behaviour of the material. This method is particularly suited for strongly damped materials, which account for the majority of objects of interest to animation, since it produces non-oscillatory behaviour. This is similar to critical damping, except that it affects all modes independently. The new method is based on the minimization of a slightly modified version of total energy. This framework can be used to simulate many other physical phenomena, and therefore lends itself to coupling with other simulations. Implementation details for a simple example are given. Results are shown for varying parameters and compared to those produced by a traditional method.

This thesis presents a new method for the controllable damping of deformable objects. The method evolves from physically based techniques; however, it allows for non-physical, but visually plausible motion. This flexibility leads to a simple interface, with intuitive control over the behaviour of the material. This method is particularly suited for strongly damped materials, which account for the majority of objects of interest to animation, since it produces non-oscillatory behaviour. This is similar to critical damping, except that it affects all modes independently. The new method is based on the minimization of a slightly modified version of total energy. This framework can be used to simulate many other physical phenomena, and therefore lends itself to coupling with other simulations. Implementation details for a simple example are given. Results are shown for varying parameters and compared to those produced by a traditional method.

This thesis presents a new method for the controllable damping of deformable objects. The method evolves from physically based techniques; however, it allows for non-physical, but visually plausible motion. This flexibility leads to a simple interface, with intuitive control over the behaviour of the material. This method is particularly suited for strongly damped materials, which account for the majority of objects of interest to animation, since it produces non-oscillatory behaviour. This is similar to critical damping, except that it affects all modes independently. The new method is based on the minimization of a slightly modified version of total energy. This framework can be used to simulate many other physical phenomena, and therefore lends itself to coupling with other simulations. Implementation details for a simple example are given. Results are shown for varying parameters and compared to those produced by a traditional method. / Science, Faculty of / Computer Science, Department of / Graduate

Over the past several decades, we have experienced tremendous growth of real-time systems in both scale and complexity. This progress is made possible largely due to advancements in semiconductor technology that have enabled the continuous scaling and massive integration of transistors on a single chip. In the meantime, however, the relentless transistor scaling and integration have dramatically increased the power consumption and degraded the system reliability substantially. Traditional real-time scheduling techniques with the sole emphasis on guaranteeing timing constraints have become insufficient. In this research, we studied the problem of how to develop advanced scheduling methods on hard real-time systems that are subject to multiple design constraints, in particular, timing, energy consumption, and reliability constraints. To this end, we first investigated the energy minimization problem with fault-tolerance requirements for dynamic-priority based hard real-time tasks on a single-core processor. Three scheduling algorithms have been developed to judiciously make tradeoffs between fault tolerance and energy reduction since both design objectives usually conflict with each other. We then shifted our research focus from single-core platforms to multi-core platforms as the latter are becoming mainstream. Specifically, we launched our research in fault-tolerant multi-core scheduling for fixed-priority tasks as fixed-priority scheduling is one of the most commonly used schemes in the industry today. For such systems, we developed several checkpointing-based partitioning strategies with the joint consideration of fault tolerance and energy minimization. At last, we exploited the implicit relations between real-time tasks in order to judiciously make partitioning decisions with the aim of improving system schedulability. According to the simulation results, our design strategies have been shown to be very promising for emerging systems and applications where timeliness, fault-tolerance, and energy reduction need to be simultaneously addressed.

Processes that take place in the Earth’s mantle are not accessible to direct observation. Natural samples of mantle material that have been transported to the surface as xenoliths provide useful information on phase relations and compositions of phases at the pressure and temperature conditions of each rock fragment. In the past, considerable effort has been devoted by petrologists to investigate upper mantle processes experimentally. Results of high temperatures, high pressure experiments have provided insight into lower crust-upper mantle phase relations as a function of temperature, pressure and composition. However, the attainment of equilibrium in these experiments, especially in complex systems, may be very difficult to test rigorously. Furthermore, experimental results may also require extrapolation to different pressures, temperatures or bulk compositions. More recently, thermodynamic modeling has proved to be a very powerful approach to this problem, allowing the deciphering the physicochemical conditions at which mantle processes occur. On the other hand, a comprehensive thermodynamic model to investigate lower crust-upper mantle phase assemblages in complex systems does not exist. ¶ In this study, a new thermodynamic model to describe phase equilibria between silicate and/or oxide crystalline phases has been derived. For every solution phase the molar Gibbs free energy is given by the sum of contributions from the energy of the end-members, ideal mixing on sites, and excess site mixing terms. It is here argued that the end-member term of the Gibbs free energy for complex solid solution phases (e.g. pyroxene, spinel) has not previously been treated in the most appropriate manner. As an example, the correct expression of this term for a pyroxene solution in a general (Na-Ca-Mg-Fe2+-Al-Cr-Fe3+-Si-Ti) system is presented and the principle underlying its formulation for any complex solution phase is elucidated.¶ Based on the thermodynamic model an algorithm to compute lower crust-upper mantle phase equilibria for subsolidus mineral assemblages as a function of composition, temperature and pressure has been developed. Included in the algorithm is a new way to represent the total Gibbs free energy for any multi-phase complex system. At any given temperature and pressure a closed multi-phase system is at its equilibrium condition when the chemical composition of the phases present in the system and the number of moles of each are such that the Gibbs free energy of the system reaches its minimum value. From a mathematical point of view, the determination of equilibrium phase assemblages can, in short, be defined as a constrained minimization problem. To solve the Gibbs free energy minimization problem a ‘Feasible Iterate Sequential Quadratic Programming’ method (FSQP) is employed. The system’s Gibbs free energy is minimized under several different linear and non-linear constraints. The algorithm, coded as a highly flexible FORTRAN computer program (named ‘Gib’), has been set up, at the moment, to perform equilibrium calculations in NaO-CaO-MgO-FeO-Al2O3-Cr2O3-Fe2O3- SiO2-TiO2 systems. However, the program is designed in a way that any other oxide component could be easily added.¶ To accurately forward model phase equilibria compositions using ‘Gib’, a precise estimation of the thermodynamic data for mineral end-members and of the solution parameters that will be adopted in the computation is needed. As a result, the value of these parameters had to be derived/refined for every solution phase in the investigated systems. A computer program (called ‘GibInv’) has been set up, and its implementation is here described in detail, that allows the simultaneous refinement of any of the end-member and mixing parameters. Derivation of internally consistent thermodynamic data is obtained by making use of the Bayesian technique. The program, after being successfully tested in a synthetic case, is initially applied to pyroxene assemblages in the system CaO-MgO-FeO-Al2O3-SiO2 (i.e. CMFAS) and in its constituent subsystems. Preliminary results are presented.¶ The new thermodynamic model is then applied to assemblages of Ca-Mg-Fe olivines and to assemblages of coexisting pyroxenes (orthopyroxene, low Ca- and high Ca clinopyroxene; two or three depending on T-P-bulk composition conditions), in CMFAS system and subsystems. Olivine and pyroxene solid solution and end-member parameters are refined, in part using ‘GibInv’ and in part on a ‘trial and error’ basis, and, when necessary, new parameters are derived. Olivine/pyroxene phase relations within such systems and their subsystems are calculated over a wide range of temperatures and pressures and compare very favorably with experimental constraints.

The main topic of this thesis is the development of computational search methods that are useful in drug design applications. The emphasis is on exhaustiveness of the search method such that it can guarantee a certain level of geometric accuracy. In particular, the following two problems are addressed: (i) Prediction of binding mode of a drug molecule to a receptor and (ii) prediction of crystal structures of drug molecules. Predicting the binding mode(s) of a drug molecule to a target receptor is pivotal in structure-based rational drug design. In contrast to most approaches to solve this problem, the idea in this work is to analyze the search problem from a computational perspective. By building on top of an existing docking tool, new methods are proposed and relevant computational results are proven. These methods and results are applicable for other place-and-join frameworks as well. A fast approximation scheme for the docking of rigid fragments is described that guarantees certain geometric approximation factors. It is also demonstrated that this can be translated into an energy approximation for simple scoring functions. A polynomial time algorithm is developed for the matching phase of the docked rigid fragments. It is demonstrated that the generic matching problem is NP-hard. At the same time the optimality of the proposed algorithm is proven under certain scoring function conditions. The matching results are also applicable for some of the fragment-based de novo design methods. On the practical side, the proposed method is tested on 829 complexes from the PDB. The results show that the closest predicted pose to the native structure has the average RMS deviation of 1.06 °A. The prediction of crystal structures of small organic molecules has significantly improved over the last two decades. Most of the new developments, since the first blind test held in 1999, have occurred in the lattice energy estimation subproblem. In this work, a new efficient systematic search method that avoids random moves is proposed. It systematically searches through the space of possible crystal structures and conducts search space cuts based on statistics collected from the structural databases. It is demonstrated that the fast search method for rigid molecules can be extended to include flexible molecules as well. Also, the results of some prediction experiments are provided showing that in most cases the systematic search generates a structure with less than 1.0°A RMSD from the experimental crystal structure. The scoring function that has been developed for these experiments is described briefly. It is also demonstrated that with a more accurate lattice energy estimation function, better results can be achieved with the proposed robust search method.

The main topic of this thesis is the development of computational search methods that are useful in drug design applications. The emphasis is on exhaustiveness of the search method such that it can guarantee a certain level of geometric accuracy. In particular, the following two problems are addressed: (i) Prediction of binding mode of a drug molecule to a receptor and (ii) prediction of crystal structures of drug molecules. Predicting the binding mode(s) of a drug molecule to a target receptor is pivotal in structure-based rational drug design. In contrast to most approaches to solve this problem, the idea in this work is to analyze the search problem from a computational perspective. By building on top of an existing docking tool, new methods are proposed and relevant computational results are proven. These methods and results are applicable for other place-and-join frameworks as well. A fast approximation scheme for the docking of rigid fragments is described that guarantees certain geometric approximation factors. It is also demonstrated that this can be translated into an energy approximation for simple scoring functions. A polynomial time algorithm is developed for the matching phase of the docked rigid fragments. It is demonstrated that the generic matching problem is NP-hard. At the same time the optimality of the proposed algorithm is proven under certain scoring function conditions. The matching results are also applicable for some of the fragment-based de novo design methods. On the practical side, the proposed method is tested on 829 complexes from the PDB. The results show that the closest predicted pose to the native structure has the average RMS deviation of 1.06 °A. The prediction of crystal structures of small organic molecules has significantly improved over the last two decades. Most of the new developments, since the first blind test held in 1999, have occurred in the lattice energy estimation subproblem. In this work, a new efficient systematic search method that avoids random moves is proposed. It systematically searches through the space of possible crystal structures and conducts search space cuts based on statistics collected from the structural databases. It is demonstrated that the fast search method for rigid molecules can be extended to include flexible molecules as well. Also, the results of some prediction experiments are provided showing that in most cases the systematic search generates a structure with less than 1.0°A RMSD from the experimental crystal structure. The scoring function that has been developed for these experiments is described briefly. It is also demonstrated that with a more accurate lattice energy estimation function, better results can be achieved with the proposed robust search method.

The thermoelectric effect was discovered well over a century ago, yet performance has not shown improvement until recent years. Prior work has shown that the thermoelectric effect can be enhanced by the use of microscale pieces of thermoelectric material. Conventional assembly techniques are inadequate to deal with parts of this size, making it necessary to find a suitable alternative before these devices can be made economically. Capillary self-assembly is a promising alternative to conventional techniques. This method employs the use of preparing substrates with areas of favorable surface tension to place and align parts. Still, many obstacles have to be overcome to adapt this process for use of constructing thermoelectric coolers. The goal of this work is to overcome these obstacles and assess the viability of self-assembly for fabricating these devices. In effort to make the method more effective a process for creating more uniform deposits of solder is also assessed. This work shows that microscale thermoelectric elements can be assembled into functional thermoelectric devices using self-assembly techniques through the assembly of coolers in experimental work.

The continuous scaling down of the metal-oxide-semiconductor field-effect transistor (MOSFET) has improved the performance of electronic appliances. Unfortunately, it has come to a stage where further scaling of the MOSFET is no longer possible due to the physical and the fabrication limitations. This has motivated researchers towards designing and fabricating novel devices that can replace MOSFET technology. Carbon Nanotube Field-Effect Transistors, Single Electron Tunneling Junctions, Nano-Magnetic Devices, and Spin Field-Effect Transistors are some prospective candidates that could replace MOSFET devices. In this dissertation, we have studied the computational performance of Nano−Magnetic Devices due to their attractive features such as room temperature operation, high density, robustness towards thermal noise, radiation hardened nature and low static power dissipation. In this work, we have established that data can be propagated in a causal fashion from a driver cell to the driven cells. We have fabricated a ferromagnetic wire architecture and used a magnetic force microscopy (MFM) tip to provide localized magnetic inputs. This experiment validated two important phenomena; (1) a clocking field is essential to propagate data and (2) upon removal of the clocking field data can be propagated according to the input data. Next, we have fabricated and captured MFM images of a nano-magnetic logic architecture that has computed the majority of seven binary variables. The architecture was designed by interconnecting three three-input majority logic gates with ferromagnetic and antiferromagnetic wire architectures. This seven input majority logic architecture can potentially implement eight different logic functions that could be configured in real-time. All eight functions could be configured by three control parameters in real-time (by writing logic one or zero to them). Even though we observed error-free operations in nano-magnetic logic architectures, it became clear that we needed better control (write/read/clock) over individual single layer nano-magnetic devices for successful long-term operation. To address the write/clock/read problems, we designed and fabricated amultilayer nano-magnetic device. We fabricated and performed a set of experiments with patterned multilayer stacks of Co/Cu/Ni80Fe20 with a bottom layer having a perpendicular magnetization to realize neighbor interactions between adjacent top layers of devices. Based on the MFM images, we conclude that dipolar coupling between the top layers of the neighboring devices can be exploited to construct three-input majority logic gates, antiferromagnetic and ferromagnetic wire architectures. Finally, we have experimentally demonstrated a magnetic system that could be used to solve quadratic optimization problems that arise in computer vision applications. We have harnessed the energy minimization nature of a magnetic system to directly solve a quadratic optimization process. We have fabricated a magnetic system corresponding to a real world image and have identified salient features with true positive rate more than 85%. These experimental results feature the potentiality of this unconventional computing method to develop a magnetic processor which solves such complex problems in few clock cycles.

Quadratic optimization problems arise in various real world application domains including engineering design, microeconomics, genetic algorithms, integrated circuit chip design, probabilistic graphical models and computer vision. In particular, there are many problems in computer vision that require binary quadratic optimization such as motion segmentation, correspondences, figure-ground segmentation, clustering, grouping, subgraph matching, and digital matting. The objective of an optimization algorithm can be related to the state of a physical system, where the goal is to bring the initial arbitrary state of the system to a state with minimum possible energy. By recognizing that the Hamiltonian of nanomagnets can be expressed in a quadratic form, we exploit the energy minimization aspect of these nanomagnets to solve the quadratic optimization problem in a direct manner. Most hard problems especially in computer vision can be naturally cast as energy minimization problems and solving these using traditional techniques like simulated annealing, graph cuts evidently associate with exorbitant computational efforts. In this dissertation, transcoding the conceptual crossover between the magnetic Hamiltonian and the optimization problem, we envision a nanomagnetic coprocessor with a grid of nanomagnets embracing an optimization heuristic enabling to solve energy minimization in a single clock cycle. We will essentially be solving an optimization problem with each input-and-readout cycle as compared to orders of magnitude more clock cycles that would be needed in a Boolean logic circuit. The dissertation presents results for quadratic minimization problem in the context of perceptual organization of edges in computer vision and compare quality of results using traditional optimization methods and that expected from magnetic computing. The dissertation also presents image processing algorithms for analysis of results produced by actual fabrication of the magnetic systems.