As CMOS scaling faces a technological barrier in the near future, novel design paradigms are being proposed to keep up with the ever growing need for computation power and speed. Most of these novel technologies have device sizes comparable to atomic and molecular scales. At these levels the quantum mechanical effects play a dominant role in device performance, thus inducing uncertainty. The wave nature of particle matter and the uncertainty associated with device operation make a case for probabilistic modeling of the device. As the dimensions go down to a molecular scale, functioning of a nano-device will be governed primarily by the atomic level device physics. Modeling a device at such a small scale will require taking into account the quantum mechanical phenomenon inherent to the device. In this dissertation, we studied one such nano-device: Quantum-Dot Cellular Automata (QCA). We used probabilistic modeling to perform a fast approximation based method to estimate error, power and reliability in large QCA circuits. First, we associate the quantum mechanical probabilities associated with each QCA cell to design and build a probabilistic Bayesian network. Our proposed modeling is derived from density matrix-based quantum modeling, and it takes into account dependency patterns induced by clocking. Our modeling scheme is orders of magnitude faster than the coherent vector simulation method that uses quantum mechanical simulations. Furthermore, our output node polarization values match those obtained from the state of the art simulations. Second, we use this model to approximate power dissipated in a QCA circuit during a non-adiabatic switching event and also to isolate the thermal hotspots in a design. Third, we also use a hierarchical probabilistic macromodeling scheme to model QCA designs at circuit level to isolate weak spots early in the design process. It can also be used to compare two functionally equivalent logic designs without performing the expensive quantum mechanical simulations. Finally, we perform optimization studies on different QCA layouts by analyzing the designs for error and power over a range of kink energies.To the best of our knowledge the non-adiabatic power model presented in this dissertation is the first work that uses abrupt clocking scheme to estimate realistic power dissipation. All prior works used quasi-adiabatic power dissipation models. The hierarchical macromodel design is also the first work in QCA design that uses circuit level modeling and is faithful to the underlying layout level design. The effect of kink energy to study power-error tradeoffs will be of great use to circuit designers and fabrication scientists in choosing the most suitable design parameters such as cell size and grid spacing.

published_or_final_version / Physics / Master / Master of Philosophy

Enligt oss så är det största problemet med att processuellt generera en pseudo-oändlig spelvärld i realtid är att få genereringen att ske så sömlöst som möjligt samtidigt som världen upplevs som konsekvent. För att finna lösningar på detta problem så analyserar vi andra studier och spel som utnyttjar processuell generering. Vi använder sedan de metoder och tekniker vi funnit för skapandet av en egen applikation för att få en djupare förståelse för hur dessa fungerar i praktiken och hur mycket varje metod påverkar prestandan. I vår slutsats beskriver vi de problem vi fann, deras orsak och ger förslag på lösningar. På grund av studiens tekniska karaktär så riktar den sig främst till programmerare. Vi hoppas att med denna studie kunna komplettera andra studier inom detta, enligt oss, relativt outforskade område. / According to us, the biggest problem with procedurally generating a pseudo-infinite game world in real-time is to have it generate as seamlessly as possible and keeping the world consistent at the same time. In order to come up with solutions to this problem we analyzed other studies and games which utilize procedural generation. We then used the methods we found in order to create our own application to further understand how they work in practice and how much each method affexts the performance of said application. In our conclusion we describe the problems that arose as well as explain what caused them, as well as present possible solutions to them. Due to the technical nature of this study it is mainly aimed at programmers. We hope that this study can complement other studies within what we think is a relatively unexplored subject.

Cellular automata (CA) are an interesting computation medium to study because of their simplicity and inherently parallel operation. These characteristics make them a useful and efficient computation tool for applications such as cryptography and physical systems modelling, particularly when implemented on specialized parallel hardware. In this dissertation, we study a number of applications of CA and develop new theoretical results used for them. We begin by presenting conditions which guarantee that a composition of marker cellular automata has the same neighbourhood as each of the individual components. We show that, under certain technical assumptions, a marker cellular automaton has a unique inverse with a given neighbourhood. We use these results to develop a working key generation algorithm for a public-key cryptosystem based on reversible cellular automata originally conceived by Kari. We also give an improvement to a CA algorithm which solves a version of the convex hull problem, ensuring that the algorithm does not require a global rule change and correcting the operation in a special case. Finally, we study a modified version of an established CA-based car traffic flow model for the single-lane highway case, and use CA as a modelling tool to investigate the coverage problem in wireless sensor network design. We developed functional software implementations for all of these experiments. / Thesis (Master, Computing) -- Queen's University, 2009-03-23 11:20:58.666

This study extends a recently-developed [1] cellular automata (CA) elastodynamic modeling approach to arbitrary two-dimensional geometries through development of a rule set appropriate for triangular cells. The approach is fully object-oriented (OO) and exploits OO conventions to produce compact, general, and easily-extended CA classes. Meshes composed of triangular cells allow the elastodynamic response of arbitrary two-dimensional geometries to be computed accurately and efficiently. As in the previous rectangular CA method, each cell represents a state machine which updates in a stepped-manner using a local "bottom-up" rule set and state input from neighboring cells. The approach avoids the need to develop partial differential equations and the complexity therein. Several advantages result from the method's discrete, local and object-oriented nature, including the ability to compute on a massively-parallel basis and to easily add or subtract cells in a multi-resolution manner. The extended approach is used to generate the elastodynamic responses of a variety of general geometries and loading cases (Dirichlet and Nuemann), which are compared to previous results and/or comparison results generated using the commercial finite element code, COMSOL. These include harmonic interior domain loading, uniform boundary traction, and ramped boundary displacement. Favorable results are reported in all cases, with the CA approach requiring fewer degrees of freedom to achieve similar or better accuracy, and considerably less code development.

Thesis (M.A.)--University of Hawaii at Manoa, 2005. / Includes bibliographical references (leaves 88-91). / viii, 91 leaves, bound col. ill., col. maps 29 cm

Simulating geographic phenomena in a realistic and plausible way requires real-world entities to be abstracted based on the dynamic physical characteristics they exhibit, and treated as individuals in a simulation domain. These processes cannot be adequately supported by the traditional spatial model based on cellular-space such as Cellular Automata (CA). Although this approach has received a great attention as a most favoured technique for simulating the geographic phenomena from different aspects, the need for a generic spatial model to overcome the limitations encountered in such an approach has been raised. This applies particularly to the way real-world entities are represented in a simulation domain regarding their physical characteristics and temporal aspects. In this thesis, a new computational approach for a spatial model suitable for simulating geographic phenomena is presented: the vector agents model. The vector agent is goal-oriented, adaptable, physically defined by an Euclidean geometry and able to change its own geometric characteristics while interacting with other agents in its neighbourhood using a set of rules. The agent is modelled with sensor, state, and strategies. The successful implementation of the model�s architecture allows the representation of the physical characteristics of real-world entities and to observe their complex and dynamic behaviour in a simulation domain. Vector agents have developed out of a need to create a systematic basis for the geometric components of Geographic Automata Systems (GAS), as outlined by Torrens and Benenson (2005). A generic vector agents model was built, then tested and validated from different aspects, from which results demonstrated the model�s efficiency. It is confirmed that vector agents are flexible in producing different complex shapes and patterns for recreating real geographic phenomena through the generic use of three algorithms of geometric manipulation: midpoint displacement by using the relaxed Brownian Motion (fractal-like) algorithm, edge displacement and vertex displacement. The effectiveness of this was initially ascertained visually. A simple heuristic to govern shape growth rate and complexity was derived based on the interplay of the three algorithms. There was a further abstract model comparison against the cellular-agents environment, with the result that vector agents have the ability to emerge patterns similar to what can be produced by cellular-agents with the advantage of representing entities as individuals with their own attributes with realistic geometric boundaries. On the other hand, the city as a complex geographic phenomenon was used as a specific domain for validating the model with a real-world system. The results of the urban land use simulations (driven by simple rules based on three classical urban theories) confirmed that: (a) the model is flexible enough to incorporate various external rules based on real-world systems and (b) the model has a sufficient capability in emerging a variety of patterns under several environments close to actual patterns. The agent environment also proved to be an effective way of easily combining the rules associated with each urban theory (different agents behaved according to different theories). Finally, limitations raised through the development of this work are addressed leading to outline possible extensions of both model computation and the domain of applications.

There exists a vital need to increase our understanding of the fast-growing informal settlements (IS) within the burgeoning mega cities of the less developed countries. Previous attempts have used descriptive speculation about underlying social, political and cultural forces, but they have not generated sufficient understanding to underpin useful and effective management policies. The result has been the piecemeal application of planning procedures and IS policies that were developed elsewhere, in developed nations. This thesis explains why such methods tend not to work within developing countries.

Thesis (M.C.S.)--Carleton University, 2004. / Includes bibliographical references (p. 110-112). Also available in electronic format on the Internet.

Thesis (MSc)--University of Stellenbosch, 2008. / Bibliography. Also available via the Internet.