Reversible computing and cellular automata—A survey

Reversible computing is a paradigm where computing models are defined so that they reflect physical reversibility, one of the fundamental microscopic physical property of Nature. In this survey/tutorial paper, we discuss how computation can be carried out in a reversible system, how a universal reversible computer can be constructed by reversible logic elements, and how such logic elements are related to reversible physical phenomena. We shall see that, in reversible systems, computation can often be carried out in a very different manner from conventional (i.e., irreversible) computing systems, and even very simple reversible systems or logic elements have computation- or logical-universality. We discuss these problems based on reversible logic elements/circuits, reversible Turing machines, reversible cellular automata, and some other related models of reversible computing.     

Transflective IPS‐LCD with improved reflective contrast ratio

Abstract— In order to improve the reflective contrast ratio of transflective IPS‐LCDs, a novel pixel design for a normally white reflective IPS has been proposed. In this design, the large‐inter‐electrode‐spacing layout using a novel driving method and a double‐layered electrode have effectively reduced the light leakage. By applying these two technologies, a transflective IPS‐LCD has been successfully demonstrated with a high contrast ratio (15:1) in the reflective mode and a wide‐viewing‐angle characteristic in the transmissive mode.     

Refined mapping of a gene responsible for Fukuyama-type congenital muscular dystrophy: evidence for strong linkage disequilibrium

Fukuyama-type congenital muscular dystrophy (FCMD), the second most common form of childhood muscular dystrophy in Japan, is an autosomal recessive severe muscular dystrophy associated with an anomaly of the brain. After our initial mapping of the FCMD locus to chromosome 9q31-33, we further defined the locus within a region of approximately 5 cM between loci D9S127 and CA246, by homozygosity mapping in patients born to consanguineous marriages and by recombination analyses in other families. We also found evidence for strong linkage disequilibrium between FCMD and a polymorphic microsatellite marker, mfd220, which showed no recombination and a lod score of (Z) 17.49. A "111-bp" allele for the mfd220 locus was observed in 22 (34%) of 64 FCMD chromosomes, but it was present in only 1 of 120 normal chromosomes. This allelic association with FCMD was highly significant (chi 2 = 50.7; P < .0001). Hence, we suspect that the FCMD gene could lie within a few hundred kilobases of the mfd220 locus.     

Functional un|unparsing

Danvy??s functional unparsing problem (Danvy in J. Funct. Program. 8(6), 621?C625, 1998) is to implement a type-safe ??printf?? function, which converts a sequence of heterogeneous arguments to a string according to a given format. The dual problem is to implement a type-safe ??scanf?? function, which extracts a sequence of heterogeneous arguments from a string by interpreting (Friedman and Wand in LFP, pp. 348?C355, 1984 and in Essentials of Programming Languages, MIT Press, 2008) the same format as an equally heterogeneous sequence of patterns that binds zero or more variables. We derive multiple solutions to both problems (Wand in J. ACM 27(1), 164?C180, 1980) from their formal specifications (Wand in Theor. Comput. Sci. 20(1), 3?C32, 1982). On one hand, our solutions show how the Hindley-Milner type system, unextended, permits accessing heterogeneous sequences with the static assurance of type safety. On the other hand, our solutions demonstrate the use of control operators (Felleisen et al. in Proceedings of the 1988 ACM Conference on Lisp and Functional Programming, pp. 52?C62, ACM Press, New York, 1988; Wand in POPL 85: Conference Record of the Annual ACM Symposium on Principles of Programming Languages, vol. 16, ACM Press, New York, 1985; Meyer and Wand in Logics of Programs, Lecture Notes in Computer Science, vol. 193, pp. 219?C224, Springer, Berlin, 1985) to communicate with formats as coroutines (Wand in Proceedings of the 1980 ACM Conference on Lisp and Functional Programming, vol. 12, pp. 285?C299, ACM Press, New York, 1980 and Haynes et al. in LFP, pp. 293?C298, 1984).     

High-performance cone beam reconstruction using CUDA compatible GPUs

Compute unified device architecture (CUDA) is a software development platform that allows us to run C-like programs on the nVIDIA graphics processing unit (GPU). This paper presents an acceleration method for cone beam reconstruction using CUDA compatible GPUs. The proposed method accelerates the Feldkamp, Davis, and Kress (FDK) algorithm using three techniques: (1) off-chip memory access reduction for saving the memory bandwidth; (2) loop unrolling for hiding the memory latency; and (3) multithreading for exploiting multiple GPUs. We describe how these techniques can be incorporated into the reconstruction code. We also show an analytical model to understand the reconstruction performance on multi-GPU environments. Experimental results show that the proposed method runs at 83% of the theoretical memory bandwidth, achieving a throughput of 64.3 projections per second (pps) for reconstruction of 512³-voxel volume from 360 512²-pixel projections. This performance is 41% higher than the previous CUDA-based method and is 24 times faster than a CPU-based method optimized by vector intrinsics. Some detailed analyses are also presented to understand how effectively the acceleration techniques increase the reconstruction performance of a naive method. We also demonstrate out-of-core reconstruction for large-scale datasets, up to 1024³-voxel volume.     

Universality Issues in Reversible Computing Systems and Cellular Automata (Extended Abstract)

In this survey, we deal with the problem how a universal computer can be constructed in a reversible environment. We discuss this problem based on the frameworks of reversible Turing machines, reversible logic circuits, and reversible cellular automata. We can see that in spite of the constraint of reversibility, there are several very simple reversible systems that have universal computing ability.     

Buoyancy engine developed for underwater gliders

A buoyancy engine with a swashplate-type axial piston pump was developed. Its oil extrusion and drawing properties under high hydraulic pressure were evaluated. This buoyancy engine is now installed in an underwater glider that will achieve long-term monitoring of ocean environments up to 2100 m depth in a designated area with lower operational costs. This bidirectionally functioning pump can control the amount of oil in extrusion and draw operations. When drawing oil under high pressure, the hydraulic pump and the electric motor, respectively, act as a hydraulic motor and an electric generator. The generated electric power is absorbed by a damping resistor. The oil-drawing and extrusion properties were measured using a large hyperbaric chamber that is able to produce an almost identical environment to that of actual operations. Results confirmed stable oil extrusion operations up to 21 MPa. Regarding oil-drawing properties, although it was measured only up to 10 MPa in the hyperbaric chamber, it can be inferred that the system can draw the oil and can control the buoyancy precisely up to 21 MPa by replacing the two-way ball valve with an electromagnetic latching solenoid valve.     

Hyper least squares fitting of circles and ellipses

This work extends the circle fitting method of Rangarajan and Kanatani (2009) to accommodate ellipse fitting. Our method, which we call HyperLS, relies on algebraic distance minimization with a carefully chosen scale normalization. The normalization is derived using a rigorous error analysis of least squares (LS) estimators so that statistical bias is eliminated up to second order noise terms. Numerical evidence suggests that the proposed HyperLS estimator is far superior to the standard LS and is slightly better than the Taubin estimator. Although suboptimal in comparison to maximum likelihood (ML), our HyperLS does not require iterations. Hence, it does not suffer from convergence issues due to poor initialization, which is inherent in ML estimators. In this sense, the proposed HyperLS is a perfect candidate for initializing the ML iterations.     

Translational lemmas for DLOGTIME-uniform circuits,alternating TMs,and PRAMs

We present translational lemmas for the three standard models of parallel computation, and apply them to obtain tight hierarchy results. It is shown that, for arbitrarily small rational constant , (i) there is a language which can be accepted by a -uniform circuit family of depth and size but not by any -uniform circuit family of depth and size , (ii) there is a language which can be accepted by a -time -space ATM with l worktapes but not by any -time -space ATM with the same l worktapes if the number of tape symbols is fixed, and (iii) there is a language which can be accepted by a -time PRAM with processors but not by any -time PRAM with processors. Here, c > 0, d ≥ 1, r ₁ > 1, and r ₂ ≥ 1 are arbitrary rational constants, and l ≥ 2 is an arbitrary integer. Preliminary versions of different parts of this paper appeared in Proc. MCU 2004 (LNCS 3354) and Proc. FCT 2005 (LNCS 3623).