We consider the problem of synthesizing program inverses for imperative languages. Our primary motivation comes from optimistic parallel discrete event simulation (OPDES). There, a simulator must process events while respecting logical temporal event-ordering constraints; to extract parallelism, an OPDES simulator may speculatively execute events and only rollback execution when event-ordering violations occur. In this context, the ability to perform rollback by running time- and space-efficient reverse programs, rather than saving and restoring large amounts of state, can make OPDES more practical. Synthesizing inverses also appears in numerous other software engineering contexts, such as debugging, synthesizing “undo” code, or even generating decompressors automatically given only lossless compression code. This thesis mainly contains three chapters. In the first chapter, we focus on handling programs with only scalar data and arbitrary control flows. By building a value search graph (VSG) that represents recoverability relationships between variable values, we turn the problem of recovering previous values into a graph search one. Forward and reverse programs are generated according to the search results. For any loop that produces an output state given a particular input state, our method can synthesize an inverse loop that reconstructs the input state given the original loop's output state. The synthesis process consists of two major components: (a) building the inverse loop's body, and (b) building the inverse loop's predicate. Our method works for all natural loops, including those that take early exits (e.g., via breaks, gotos, returns). In the second chapter we extend our method to handling programs containing arrays. Based on Array SSA, we develop a modified Array SSA from which we could easily build equalities between arrays and array elements. Specifically, to represent the equality between two arrays, we employ the array subregion as the constraint. During the search those subregions will be calculated to guarantee that all array elements will be retrieved. We also develop a demand-driven method to retrieve array elements from a loop, in which each time we only try to retrieve an array element from an iteration if that element has not been modified in previous iterations. To ensure the correctness of each retrieval, the boundary conditions are created and checked at the entry and the exit of the loop. In the last chapter, we introduce several techniques of handling high-level constructs of C++ programs, including virtual functions, copying C++ objects, C++ STL containers, C++ source code normalization, inter-procedural function calls, etc. Since C++ is an object-oriented (OO) language, our discussion in this chapter can also be extended to other OO languages like Java.

<p>In this dissertation, we present work on developing superconducting circuits intended to advance the implementation of Asynchronous Ballistic Reversible Computation using Fluxon Logic. In the first Chapter we introduce the need for developing reversible computing, and discuss implementing asynchronous reversible computing using fluxons in superconducting circuits. In Chapter 2, we introduce basic superconductivity physics, including the Josephson effects, which is necessary to know for understanding the behavior of Josephson junction transmission lines. In Chapter 3, we introduce tools to physically understand the behavior of topologically protected solitons, 'fluxons', in Josephson junction transmission lines. Finally, in Chapter 4, we briefly discuss the history of fluxon-based computation devices and present current state of the art design of such reversible computation devices, including the fluxon Rotary gate that we have developed. Taken together, these represent advances in the direction of implementing asynchronous reversible computing in practice.</p>

Recently, researchers have been interested in reversible computing because of its ability to dissipate nearly zero heat and because of its applications in quantum computing and low power VLSI design. Synthesis and testing are two important areas of reversible logic. The thesis first presents an approach for the synthesis of reversible circuits from the exclusive- OR sum-of-products (ESOP) representation of functions, which makes better use of shared functionality among multiple outputs, resulting in up to 75% minimization of quantum cost compared to the previous approach. This thesis also investigates the previous work on constructing the online testable circuits and points out some design issues. A simple approach for online fault detection is proposed for a particular type of ESOP-based reversible circuit, which is also extended for any type of Toffoli circuits. The proposed online testable designs not only address the problems of the previous designs but also achieve significant improvements of up to 78% and 99% in terms of quantum cost and garbage outputs, respectively. / xii, 82 leaves : ill. ; 29 cm

Power dissipation in modern technologies is an important matter and overheating is a severe concern for both manufacturer (impossibility of introducing new and smaller scale technologies and limited temperature range for operating the product) and customer (power supply, which is especially important for mobile systems). One of the main profits that reversible circuit carries is theoretically the zero power dissipation in the sense that it is independent of underlying technology; irreversibility means heat generation. In the other words, reversible circuits may offer a feasible solution in the future that will aid certain reduction of the power loss. Reversible circuits are circuits that do not lose information during computation. These circuits can create unique output vector from each input vector, and vice versa, that is, there is a one-to-one mapping between the input and the output vectors. Historically, the reversible circuits have been inspired by theoretical research in low power electronics as well as practical progress of bit-manipulation transforms in cryptography and computer graphics. Interest in reversible circuit is also sparked by its applications in several up-to-date technologies, such as Nanotechnology, Quantum Computing, Optical Computing, Quantum Dot Cellular Automata, and Low Power Adiabatic CMOS. However, the most important application of reversible circuits is in Quantum Computing. Logic synthesis methodologies for reversible circuits are very different from those for classical CMOS and other technologies. The dissertation introduces a new concept of reversible logic circuits synthesis based on EXOR-sum of Products-of-EXOR-sums (EPOE). The motivation for this work is to reduce the number of the multiple-controlled Toffoli gates as well as the numbers of their inputs. To achieve these reductions the research generalizes from the existing 2-level AND-EXOR structures (ESOP) commonly used in reversible logic to a mixture of 3-level EXOR-AND-EXOR structures and ESOPs. The approaches can be applied to reversible and permutative quantum circuits to synthesize both completely and incompletely specified single-output functions as well as multiple-output functions. This dissertation describes the research intended to examine the methods to synthesize reversible circuits based on this new concept. The examinations indicate that the synthesis of reversible logic circuits based on EPOE approach produces circuits with significantly lower quantum costs than the common ESOP approach.

This dissertation describes the development of automated synthesis algorithms that construct reversible quantum circuits for reversible functions with large number of variables. Specifically, the research area is focused on reversible, permutative and fully specified binary and ternary specifications and the applicability of the resulting circuit to the physical limitations of existing quantum technologies. Automated synthesis of arbitrary reversible specifications is an NP hard, multiobjective optimization problem, where 1) the amount of time and computational resources required to synthesize the specification, 2) the number of primitive quantum gates in the resulting circuit (quantum cost), and 3) the number of ancillary qubits (variables added to hold intermediate calculations) are all minimized while 4) the number of variables is maximized. Some of the existing algorithms in the literature ignored objective 2 by focusing on the synthesis of a single solution without the addition of any ancillary qubits while others attempted to explore every possible solution in the search space in an effort to discover the optimal solution (i.e., sacrificed objective 1 and 4). Other algorithms resorted to adding a huge number of ancillary qubits (counter to objective 3) in an effort minimize the number of primitive gates (objective 2). In this dissertation, I first introduce the MMDSN algorithm that is capable of synthesizing binary specifications up to 30 variables, does not add any ancillary variables, produces better quantum cost (8-50% improvement) than algorithms which limit their search to a single solution and within a minimal amount of time compared to algorithms which perform exhaustive search (seconds vs. hours). The MMDSN algorithm introduces an innovative method of using the Hasse diagram to construct candidate solutions that are guaranteed to be valid and then selects the solution with the minimal quantum cost out of this subset. I then introduce the Covered Set Partitions (CSP) algorithm that expands the search space of valid candidate solutions and allows for exploring solutions outside the range of MMDSN. I show a method of subdividing the expansive search landscape into smaller partitions and demonstrate the benefit of focusing on partition sizes that are around half of the number of variables (15% to 25% improvements, over MMDSN, for functions less than 12 variables, and more than 1000% improvement for functions with 12 and 13 variables). For a function of n variables, the CSP algorithm, theoretically, requires n times more to synthesize; however, by focusing on the middle k (k by MMDSN which typically yields lower quantum cost. I also show that using a Tabu search for selecting the next set of candidate from the CSP subset results in discovering solutions with even lower quantum costs (up to 10% improvement over CSP with random selection). In Chapters 9 and 10 I question the predominant methods of measuring quantum cost and its applicability to physical implementation of quantum gates and circuits. I counter the prevailing literature by introducing a new standard for measuring the performance of quantum synthesis algorithms by enforcing the Linear Nearest Neighbor Model (LNNM) constraint, which is imposed by the today's leading implementations of quantum technology. In addition to enforcing physical constraints, the new LNNM quantum cost (LNNQC) allows for a level comparison amongst all methods of synthesis; specifically, methods which add a large number of ancillary variables to ones that add no additional variables. I show that, when LNNM is enforced, the quantum cost for methods that add a large number of ancillary qubits increases significantly (up to 1200%). I also extend the Hasse based method to the ternary and I demonstrate synthesis of specifications of up to 9 ternary variables (compared to 3 ternary variables that existed in the literature). I introduce the concept of ternary precedence order and its implication on the construction of the Hasse diagram and the construction of valid candidate solutions. I also provide a case study comparing the performance of ternary logic synthesis of large functions using both a CUDA graphic processor with 1024 cores and an Intel i7 processor with 8 cores. In the process of exploring large ternary functions I introduce, to the literature, eight families of ternary benchmark functions along with a Multiple Valued file specification (the Extended Quantum Specification XQS). I also introduce a new composite quantum gate, the multiple valued Swivel gate, which swaps the information of qubits around a centrally located pivot point. In summary, my research objectives are as follows: * Explore and create automated synthesis algorithms for reversible circuits both in binary and ternary logic for large number of variables. * Study the impact of enforcing Linear Nearest Neighbor Model (LNNM) constraint for every interaction between qubits for reversible binary specifications. * Advocate for a revised metric for measuring the cost of a quantum circuit in concordance with LNNM, where, on one hand, such a metric would provide a way for balanced comparison between the various flavors of algorithms, and on the other hand, represents a realistic cost of a quantum circuit with respect to an ion trap implementation. * Establish an open source repository for sharing the results, software code and publications with the scientific community. With the dwindling expectations for a new lifeline on silicon-based technologies, quantum computations have the potential of becoming the future workhorse of computations. Similar to the automated CAD tools of classical logic, my work lays the foundation for creating automated tools for constructing quantum circuits from reversible specifications.

<p>    </p> <p>We live in an age in which computation touches upon every aspect of our lives in ever increasing ways. To meet the demand for increased computing power and ability, new computation strategies are continually being proposed. In this dissertation, we consider two research projects related to two such cutting edge paradigms. We first consider developing superconducting devices that implement asynchronous reversible ballistic computation. This paradigm was developed to circumvent Landauer’s principle of a minimum energy required per bitwise computation operation. We report the design of a new device, the rotary, which is a critical step towards developing universal computation gates in the scheme of synchronous reversible ballistic computation. Next, we turn to the consideration of anyons which have been predicted to enable topological quantum computing, a quantum computing paradigm that is relatively immune to environmental noise. We consider initial steps in the development of a Bethe ansatz solvable model that will help decipher the many-body properties of Majorana zero modes in superconducting Kitaev wires. </p>

At this time the synthesis of reversible circuits for quantum computing is an active area of research. In the most restrictive quantum computing models there are no ancilla lines and the quantum cost, or latency, of performing a reversible form of the AND gate, or Toffoli gate, increases exponentially with the number of input variables. In contrast, the quantum cost of performing any combination of reversible EXOR gates, or CNOT gates, on n input variables requires at most O(n2/log2n) gates. It was under these conditions that EXOR-AND-EXOR, or EPOE, synthesis was developed. In this work, the GF(2) logic theory used in EPOE is expanded and the concept of an EXOR-AND product transform is introduced. Because of the generality of this logic theory, it is adapted to EXOR-AND-OR, or SPOE, synthesis. Three heuristic spectral logic synthesis algorithms are introduced, implemented in a program called XAX, and compared with previous work in classical logic circuits of up to 26 inputs. Three linear reversible circuit methods are also introduced and compared with previous work in linear reversible logic circuits of up to 100 inputs.

Le concept de réversibilité est ancien, mais il soulève de nos jours beaucoup d'intérêt. Il est en effet exploité dans de nombreux domaines tels que la conception de circuits, le débogage et le test de programmes, la simulation et l'informatique quantique. L'idée d'un modèle de programmation réversible peut se montrer particulièrement intéressante pour la construction de systèmes sûrs de fonctionnement, ne serait-ce que parce que plusieurs techniques connues pour la construction de tels systèmes exploitent une forme ou une autre de retour en arrière ou de reprise. Nous poursuivons dans cette thèse l'étude entreprise avec CCS réversible par Vincent Danos et Jean Krivine, en définissant un pi-calcul d'ordre supérieur réversible (rhopi). Nous prouvons que le modèle obtenu est causalement cohérent, et que l'on peut encoder fidèlement rhopi dans une variante du pi-calcul d'ordre supérieur. Nous définissons également une primitive de reprise à grain fin qui permet de contrôler le retour en arrière dans une exécution concurrente. Nous spécifions formellement la sémantique de cette primitive, et nous montrons qu'elle possède de bonnes propriétés, y compris en présence d'opérations de reprise concurrentes. Enfin nous définissons un algorithme concurrent implantant cette primitive de reprise et ous montrons que cet algorithme respecte la sémantique définie. / Reversible computing has a long history. Nowadays, reversible computing is attracting increasing interest because of its potential applications in diverse fields, including hardware design, biological modelling, program debugging and testing and quantum computing. Of particular interest is the application of reversible computation notions to the study of programming abstractions for dependable systems, because several techniques used to build dependable systems rely on some forms of undo or rollback. We continue, in this thesis, the study undertaken on reversible CCS by Vincent Danos and Jean Krivine, by defining a reversible higher-order pi-calculus (rhopi). We prove that reversibility in our calculus is causally consistent and that one can encode faithfully rhopi into a variant of HOpi. Moreover we design a fine-grained rollback primitive able to control the rollback of a concurrent execution. We give a formal specification of this primitive and show that it enjoys good properties, even in presence of concurrent conflicting rollbacks. We then devise a concurrent algorithm implementing such primitive and show that the algorithm respects the defined semantics.

With the probable end of Moore's Law in the near future, and with advances in nanotechnology, new forms of computing are likely to become available. Reversible computing is one of these possible future technologies, and it employs reversible circuits. Reversible circuits in a classical form have the potential for lower power consumption than existing technology, and in a quantum form permit new types of encryption and computation. One fundamental challenge in synthesizing the most general type of reversible circuit is that the storage space for fully specifying input-output descriptions becomes exponentially large as the number of inputs increases linearly. Certain restricted classes of reversible circuits, namely affine-linear, linear, and permutation circuits, have much more compact representations. The synthesis methods which operate on these restricted classes of reversible circuits are capable of synthesizing circuits with hundreds of inputs. In this thesis new types of synthesis methods are introduced for affine-linear, linear, and permutation circuits, as well as a synthesizable HDL design for a scalable, systolic processor for linear reversible circuit synthesis.

The main resources for computation are time, space and energy. Reducing them is the main challenge in the field of processor performance.In this thesis, we are interested in a fourth factor which is information. Information has an important and direct impact on these three resources. We show how it contributes to performance optimization. Landauer has suggested that independently on the hardware where computation is run information erasure generates dissipated energy. This is a fundamental result of thermodynamics in physics. Therefore, under this hypothesis, only reversible computations where no information is ever lost, are likely to be thermodynamically adiabatic and do not dissipate power. Reversibility means that data can always be retrieved from any point of the program. Information may be carried not only by the data but also by the process and input data that generate it. When a computation is reversible, information can also be retrieved from other already computed data and reverse computation. Hence reversible computing improves information locality.This thesis develops these ideas in two directions. In the first part, we address the issue of making a computation DAG (directed acyclic graph) reversible in terms of spatial complexity. We define energetic garbage as the additional number of registers needed for the reversible computation with respect to the original computation. We propose a reversible register allocator and we show empirically that the garbage size is never more than 50% of the DAG size. In the second part, we apply this approach to the trade-off between recomputing (direct or reverse) and storage in the context of supercomputers such as the recent vector and parallel coprocessors, graphical processing units (GPUs), IBM Cell processor, etc., where the gap between processor cycle time and memory access time is increasing. We show that recomputing in general and reverse computing in particular helps reduce register requirements and memory pressure. This approach of reverse rematerialization also contributes to the increase of instruction-level parallelism (Cell) and thread-level parallelism in multicore processors with shared register/memory file (GPU). On the latter architecture, the number of registers required by the kernel limits the number of running threads and affects performance. Reverse rematerialization generates additional instructions but their cost can be hidden by the parallelism gain. Experiments on the highly memory demanding Lattice QCD simulation code on Nvidia GPU show a performance gain up to 11%.