Designing an efficient arithmetic division circuit has long been a major challenge. Traditional binary computation methods rely on complex algorithms that require multiple cycles, complex control logic, and substantial hardware resources. Implementing division with emerging in-memory computing technologies is even more challenging due to susceptibility to noise, process variation, and the complexity of binary division. In this work, we propose an in-memory division architecture leveraging stochastic computing (SC), an emerging technology known for its high fault tolerance and low-cost design. Our approach utilizes a magnetic tunnel junction (MTJ)-based memory architecture to efficiently execute logic-in-memory operations. Experimental results across various process variation conditions demonstrate the robustness of our method against hardware variations. To assess its practical effectiveness, we apply our approach to the Retinex Algorithm for image enhancement, demonstrating its viability in real-world applications.

In-memory computing (IMC) has emerged as a promising paradigm for overcoming the limitations of traditional von Neumann architectures by reducing data movement and enhancing computational efficiency. Despite significant advancements in this area, implementing complex arithmetic operations, such as division, directly within memory has remained an elusive challenge. This paper introduces a pioneering technique for performing division operations directly in memory, representing the first successful integration of such functionality into the IMC framework. Our approach leverages an innovative circuit based on an unconventional model of computing-stochastic computing. Our technique extends the computational capabilities of IMC systems and paves the way for lightweight division operations.

The Omicron variants boast the highest infectivity rates among all SARS-CoV-2 variants. Despite their lower disease severity, they can reinfect COVID-19 patients and infect vaccinated individuals as well. The high number of mutations in these variants render them resistant to antibodies that otherwise neutralize the spike protein of the original SARS-CoV-2 spike protein. Recent research has shown that despite its strong immune evasion, Omicron still induces strong T Cell responses similar to the original variant. This work investigates the molecular basis for this observation using the neural network tools NetMHCpan-4.1 and NetMHCiipan-4.0. The antigens presented through the MHC Class I and Class II pathways from all the notable SARS-CoV-2 variants were compared across numerous high frequency HLAs. All variants were observed to have equivalent T cell antigenicity. A novel positive control system was engineered in the form of spike variants that did evade T Cell responses, unlike Omicron. These evasive spike proteins were used to statistically confirm that the Omicron variants did not exhibit lower antigenicity in the MHC pathways. These results suggest that T Cell immunity mounts a strong defense against COVID-19 which is difficult for SARS-CoV-2 to overcome through mere evolution.

Stochastic computing is a paradigm in which logical operations are performed on randomly generated bit streams. Complex arithmetic operations can be performed by simple logic circuits, with a much smaller area footprint than conventional binary counterparts. However, the random or pseudorandom sources required to generate the bit streams are costly in terms of area and offset the gains. Also, due to randomness, the computation is not precise, which limits the applicability of the paradigm. Most importantly, to achieve reasonable accuracy, high latency is necessitated. Recently, deterministic approaches to stochastic computing have been proposed. They demonstrated that randomness is not a requirement. By structuring the computation deterministically, the result is exact and the latency is greatly reduced. However, despite being an improvement over conventional stochastic techniques, the latency increases quadratically with each level of logic. Beyond a few levels of logic, it becomes unmanageable. In this paper, we present a method for approximating the results of their deterministic method, with latency that only increases linearly with each level. The improvement comes at the cost of additional logic, but we demonstrate that the increase in area scales with √n, where n is the equivalent number of binary bits of precision. The new approach is general, efficient, composable, and applicable to all arithmetic operations performed with stochastic logic.

Prior research has introduced the Single-Instruction-Multiple-Data paradigm for DNA computing (SIMD DNA). It offers the potential for storing information and performing in-memory computations on DNA, with massive parallelism. This paper introduces three new SIMD DNA operations: sorting, shifting, and searching. Each is a fundamental operation in computer science. Our implementations demonstrate the effectiveness of parallel pairwise operations with this new paradigm.

Ever since Watson and Crick first described the molecular structure of DNA, its information-bearing potential has been apparent to computer scientists. This has led to a concerted effort in academia and industry to deliver practical DNA data storage systems. This paper presents a novel approach for both storage and computation with DNA. Data is stored in the form of analog values of the relative concentration of different DNA molecules. Computation is in the form of cas-cadable NAND operations, effected via toehold-mediated strand displacement reactions operating on these concentration values. Results were verified with the “Peppercorn Enumerator,” a recent software tool for analyzing domain-level strand displacement. In all cases, the relative error in output concentration was less than 0.03%. The approach is robust to encoding errors and cross-hybridization. It does not rely on long DNA strands, which are expensive to synthesize. It opens new avenues for storage and computing, including the implementation of a wide range of useful mathematical functions in vitro.

In this paper, we introduce a novel scheme for computing polynomial functions on a substrate of nicked DNA. We first discuss a fractional encoding of data, based on the concentration of nicked double DNA strands. Then we show how to perform multiplication on this representation. Next we describe the read-out process, effected by releasing single strands. We show how to perform simple mathematical operations such as addition and subtraction, as well as how to scale constant values using probabilistic switches. We also describe two complex operations: calculating a vector dot product and computing a general polynomial function. We conclude by discussing potential applications of our scheme, practical challenges, and future research directions.

Stochastic logic performs computation on data represented by random bit-streams. The representation allows complex arithmetic to be performed with very simple logic, but it suffers from high latency and poor precision. Furthermore, the results are always somewhat inaccurate due to random fluctuations. In this paper, we show that randomness is not a requirement for this computational paradigm. If properly structured, the same arithmetical constructs can operate on deterministic bit-streams, with the data represented uniformly by the fraction of 1's versus 0's. This paper presents three approaches for the computation: relatively prime stream lengths, rotation, and clock division. Unlike stochastic methods, all three of our deterministic methods produce completely accurate results. The cost of generating the deterministic streams is a small fraction of the cost of generating streams from random/pseudorandom sources. Most importantly, the latency is reduced by a factor of (1/2n), where n is the equivalent number of bits of precision. When computing in unary, the bit-stream length increases with each level of logic. This is an inevitable consequence of the representation, but it can result in unmanageable bit-stream lengths. We discuss two methods for maintaining constant bit-streams lengths via approximations, based on low-discrepancy sequences. These methods provide the best accuracy and area x delay product. They are fast-converging and therefore offer progressive precision.

Stochastic logic performs computation on data represented by random bit-streams. The representation allows complex arithmetic to be performed with very simple logic, but it suffers from high latency and poor precision. Furthermore, the results are always somewhat inaccurate due to random fluctuations. In this paper, we show that randomness is not a requirement for this computational paradigm. If properly structured, the same arithmetical constructs can operate on deterministic bit-streams, with the data represented uniformly by the fraction of 1's versus 0's. This paper presents three approaches for the computation: relatively prime stream lengths, rotation, and clock division. Unlike stochastic methods, all three of our deterministic methods produce completely accurate results. The cost of generating the deterministic streams is a small fraction of the cost of generating streams from random/pseudorandom sources. Most importantly, the latency is reduced by a factor of (1/2n), where n is the equivalent number of bits of precision. When computing in unary, the bit-stream length increases with each level of logic. This is an inevitable consequence of the representation, but it can result in unmanageable bit-stream lengths. We discuss two methods for maintaining constant bit-streams lengths via approximations, based on low-discrepancy sequences. These methods provide the best accuracy and area × delay product. They are fast-converging and therefore offer progressive precision.

Recently, deterministic approaches to stochastic computing (SC) have been proposed. These compute with the same constructs as stochastic computing but operate on deterministic bit streams. These approaches reduce the area, greatly reduce the latency (by an exponential factor), and produce completely accurate results. However, these methods do not scale well. Also, they lack the property of progressive precision enjoyed by SC. As a result, these deterministic approaches are not competitive for applications where some degree of inaccuracy can be tolerated. In this work we introduce two fast-converging, scalable deterministic approaches to SC based on low-discrepancy sequences. The results are completely accurate when running the operations for the required number of cycles. However, the computation can be truncated early if some inaccuracy is acceptable. Experimental results show that the proposed approaches significantly improve both the processing time and area-delay product compared to prior approaches.

This paper proposes a novel method, referred to as \textit{double-NAND expansion}, to implement polynomials with all positive coefficients using unipolar stochastic logic. %The inputs and outputs of these circuits lie between 0 and 1, and are encoded using unary bit streams. Prior work has addressed implementation of polynomials with alternately positive and negative coefficients and non-increasing magnitudes, using stochastic logic based on Horner's rule. However, Horner's expansion is not applicable to implementation of polynomials with all positive coefficients. The proposed double-NAND expansion leads to implementations of polynomials using no more than 2n NAND gates where n represents the degree of the polynomial. %While the Horner's rule leads to cascaded AND-NAND gates, the proposed expansion leads to cascaded double-NAND gates.The proposed implementations are compared with those based on multiplexers, Bernstein polynomial method, finite state machine method and factorization. The paper also considers implementations of several functions expressed as polynomials using truncated Mclaurin series based on the proposed approach. The experimental results show that the proposed method outperforms the prior methods in terms of accuracy, hardware complexity, and critical path.

Sorting is a common task in a wide range of applications from signal and image processing to switching systems. For applications that require high performance, sorting is often performed in hardware. Hardware cost and power consumption are the dominant concerns. The usual approach is to wire up a network of compare-and-swap units in a configuration called a Batcher (or Bitonic) network. This paper proposes a novel area-and power-efficient approach to sorting networks based on "unary processing." Data is encoded as serial bit-streams, with values represented by the fraction of 1's in a stream of 0's and 1's. (This is an evolution of prior work on stochastic logic. Unlike stochastic logic, the unary approach is deterministic and completely accurate.) Synthesis results of complete sorting networks show up to 87% area and power saving compared to the conventional binary implementations. However, the latency increases. To mitigate the increased latency, the paper uses a novel time-encoding of data. The approach is validated with implementation of an important application of sorting: median filtering. The result is a low-cost, energy-efficient implementation of median filtering with only a slight accuracy loss.

Computations based on stochastic bit streams have several advantages compared to deterministic binary radix computations, including low power consumption, low hardware cost, high fault tolerance, and skew tolerance. To take advantage of this computing technique, previous work proposed a combinational logic-based reconfigurable architecture to perform complex arithmetic operations on stochastic streams of bits. The long execution time and the cost of converting between binary and stochastic representations, however, make the stochastic architectures less energy efficient than the deterministic binary implementations. This article introduces a methodology for synthesizing a given target function stochastically using finite-state machines (FSMs), and enhances and extends the reconfigurable architecture using sequential logic. Compared to the previous approach, the proposed reconfigurable architecture can save hardware area and energy consumption by up to 30% and 40%, respectively, while achieving a higher processing speed. Both stochastic reconfigurable architectures are much more tolerant of soft errors (bit flips) than the deterministic binary radix implementations, and their fault tolerance scales gracefully to very large numbers of errors.

In the paradigm of stochastic computing, arithmetic functions are computed on randomized bit streams. The method naturally and effectively tolerates very high clock skew. Exploiting this advantage, this paper introduces polysynchronous clocking, a design strategy in which clock domains are split at a very fine level. Each domain is synchronized by an inexpensive local clock. Alternatively, the skew requirements for a global clock distribution network can be relaxed. This allows for a higher working frequency and so lower latency. The benefits of both approaches are quantified. Polysynchronous clocking results in significant latency, area, and energy savings for wide variety of applications.

Stochastic computing (SC) is a promising technique for applications that require low area overhead and fault tolerance, but can tolerate relatively high latency. In the SC paradigm, logical computation is performed on randomized bit streams. In prior work, streams were generated with linear feedback shift registers; these contributed heavily to the hardware cost and consumed a significant amount of power. This paper introduces a new approach for encoding signal values: computation is performed on analog periodic pulse signals. Exploiting pulse width modulation, time-encoded signals corresponding to specific values are generated by adjusting the frequency and duty cycles of pulse width modulated (PWM) signals. With this approach, the latency, area, and energy consumption are all greatly reduced. Experimental results on image processing applications show up to 99% performance speedup, 98% saving in energy dissipation, and 40% area reduction compared to prior stochastic approaches. Circuits synthesized with the proposed approach can work as fast and energy-efficiently as a conventional binary design while retaining the fault-tolerance and low-cost advantages of conventional stochastic designs.

Clock distribution networks (CDNs) are costly in high-performance ASICs. This paper proposes a new approach: splitting clock domains at a very fine level, down to the level of a handful of gates. Each domain is synchronized with an inexpensive clock signal, generated locally. This is possible by adopting the paradigm of stochastic computation, where signal values are encoded as random bit streams. The design method is illustrated with the synthesis of circuits for applications in signal and image processing.

Chemical reaction networks (CRNs) provide a fundamental model in the study of molecular systems. Widely used as formalism for the analysis of chemical and biochemical systems, CRNs have received renewed attention as a model for molecular computation. This paper demonstrates that, with a new encoding, CRNs can compute any set of polynomial functions subject only to the limitation that these functions must map the unit interval to itself. These polynomials can be expressed as linear combinations of Bernstein basis polynomials with positive coefficients less than or equal to 1. In the proposed encoding approach, each variable is represented using two molecular types: a type-0 and a type-1. The value is the ratio of the concentration of type-1 molecules to the sum of the concentrations of type-0 and type-1 molecules. The proposed encoding naturally exploits the expansion of a power-form polynomial into a Bernstein polynomials. The method is illustrated first for generic CRNs; then the chemical reactions designed for two examples are mapped to DNA strand-displacement reactions.

Stochastic logic performs computation on data represented by random bit streams. The representation allows complex arithmetic to be performed with very simple logic, but it suffers from high latency and poor precision. Furthermore, the results are always somewhat inaccurate due to random fluctuations. The random or pseudorandom sources required to generate the representation are costly, consuming a majority of the circuit area (and diminishing the overall gains in area). In this paper, we show that randomness is not a requirement for this computational paradigm. If properly structured, the same arithmetical constructs can operate on deterministic bit streams, with the data represented uniformly by the fraction of 1's versus 0's. This paper presents three approaches for the computation: relatively prime stream lengths, rotation, and clock division. The three methods are evaluated on a collection of arithmetical functions. Unlike stochastic methods, all three of our deterministic methods produce completely accurate results. The cost of generating the deterministic streams is a small fraction of the cost of generating streams from random/pseudorandom sources. Most importantly, the latency is reduced by a factor of 1/2n, where n is the equivalent number of bits of precision.

We consider the design of IIR filters operating on oversampled sigma-delta modulated bit streams using stochastic arithmetic. Conventional digital filters process multi-bit data at the Nyquist rate using multi-bit multipliers and adders. High resolution ADCs based on the sigma-delta modulation generate random bits at an oversampled rate as intermediate data. We propose to filter the sigma-delta modulated bit streams directly and present first and second order low pass IIR filters based on the stochastic integrator. Experimental results show a significant reduction in hardware area by using stochastic filters.

Most digital systems operate on a positional representation of data, such as binary radix. An alternative is to operate on random bit streams where the signal value is encoded by the probability of obtaining a one versus a zero. This representation is much less compact than binary radix. However, complex operations can be performed with very simple logic. Furthermore, since the representation is uniform, with all bits weighted equally, it is highly tolerant of soft errors (i.e., bit flips). Both combinational and sequential constructs have been proposed for operating on stochastic bit streams. Prior work has shown that combinational logic can implement multiplication and scaled addition effectively while linear finite-state machines (FSMs) can implement complex functions such as exponentiation and tanh effectively. Prior work on stochastic computation has largely been validated empirically.This paper provides a rigorous mathematical treatment of stochastic implementation of complex functions such as exponentiation and tanh implemented using linear FSMs. It presents two new functions, an absolute value function and exponentiation based on an absolute value, motivated by specific applications. Experimental results show that the linear FSM-based constructs for these functions have smaller area-delay products than the corresponding deterministic constructs. They also are much more tolerant of soft errors.

Maintaining the reliability of integrated circuits as transistor sizes continue to shrink to nanoscale dimensions is a significant looming challenge for the industry. Computation on stochastic bit streams, which could replace conventional deterministic computation based on a binary radix, allows similar computation to be performed more reliably and often with less hardware area. Prior work discussed a variety of specific stochastic computational elements (SCEs) for applications such as artificial neural networks and control systems. Recently, very promising new SCEs have been developed based on finite-state machines (FSMs). In this paper, we introduce new SCEs based on FSMs for the task of digital image processing. We present five digital image processing algorithms as case studies of practical applications of the technique. We compare the error tolerance, hardware area, and latency of stochastic implementations to those of conventional deterministic implementations using binary radix encoding. We also provide a rigorous analysis of a particular function, namely the stochastic linear gain function, which had only been validated experimentally in prior work.

A new SAT-Based algorithm for symbolic model checking has been gaining popularity. This algorithm, referred to as “Incremental Construction of Inductive Clauses for Indubitable Correctness” (IC3) or “Property Directed Reachability” (PDR), uses information learned from SAT instances of isolated time frames to either prove that an invariant exists, or provide a counter example. The information learned between each time frame is recorded in the form of cubes of the state variables. In this work, we study the effect of extending PDR to use cubes of intermediate variables representing the logic gates in the transition relation. We demonstrate that we can improve the runtime for satisfiable benchmarks by up to 3.2X, with an average speedup of 1.23X. Our approach also provides a speedup of up to 3.84X for unsatisfiable benchmarks.

This paper presents a methodology for implementing digital logic with molecular reactions based on a bistable mechanism for representing bits. The value of a bit is not determined by the concentration of a single molecular type; rather, it is the comparison of the concentrations of two complementary types that determines if the bit is “0” or “1”. This mechanism is robust: any small perturbation or leakage in the concentrations quickly gets cleared out and the signal value is not affected. Based on this representation for bits, a constituent set of logical components are implemented. These include combinational components - AND, OR, NOR, and XOR - as well as sequential components - D latches and D flip-flops. Using these components, three full-fledged design examples are given: a square-root unit, a binary adder and a linear feedback shift register. DNA-based computation via strand displacement is the target experimental chassis. The designs are validated through simulations of the chemical kinetics. The simulations show that the molecular systems compute digital functions accurately and robustly.

Stochastic computing is a novel approach to real arithmetic, offering better error tolerance and lower hardware costs over the conventional implementations. Stochastic modules are digital systems that process random bit streams representing real values in the unit interval. Stochastic modules based on finite state machines (FSMs) have been shown to realize complicated arithmetic functions much more efficiently than combinational stochastic modules. However, a general approach to synthesize FSMs for realizing arbitrary functions has been elusive. We describe a systematic procedure to design FSMs that implement arbitrary real-valued functions in the unit interval using the Taylor series approximation.

The Stochastic Computational Element (SCE) uses streams of random bits (stochastic bits streams) to perform computation with conventional digital logic gates. It can guarantee reliable computation using unreliable devices. In stochastic computing, the linear Finite State Machine (FSM) can be used to implement some sophisticated functions, such as the exponentiation and tanh functions, more efficiently than combinational logic. However, a general approach about how to synthesize a linear FSM-based SCE for a target function has not been available. In this paper, we will introduce three properties of the linear FSM used in stochastic computing and demonstrate a general approach to synthesize a linear FSM-based SCE for a target function. Experimental results show that our approach produces circuits that are much more tolerant of soft errors than deterministic implementations, while the area-delay product of the circuits are less than that of deterministic implementations.

The paradigm of logical computation on stochastic bit streams has several key advantages compared to deterministic computation based on binary radix, including error-tolerance and low hardware area cost. Prior research has shown that sequential logic operating on stochastic bit streams can compute non-polynomial functions, such as the tanh function, with less energy than conventional implementations. However, the functions that can be computed in this way are quite limited. For example, high order polynomials and non-polynomial functions cannot be computed using prior approaches. This paper proposes a new finite-state machine (FSM) topology for complex arithmetic computation on stochastic bit streams. It describes a general methodology for synthesizing such FSMs. Experimental results show that these FSM-based implementations are more tolerant of soft errors and less costly in terms of the area-time product that conventional implementations.

Numerical integration is a widely used approach for computing an approximate result of a definite integral. Conventional digital implementations of numerical integration using binary radix encoding are costly in terms of hardware and have long computational delay. This work proposes a novel method for performing numerical integration based on the paradigm of logical computation on stochastic bit streams. In this paradigm, ordinary digital circuits are employed but they operate on stochastic bit streams instead of deterministic values; the signal value is encoded by the probability of obtaining a one versus a zero in the streams. With this type of computation, complex arithmetic operations can be implemented with very simple circuitry. However, typically, such stochastic implementations have long computational delay, since long bit streams are required to encode precise values. This paper proposes a stochastic design for numerical integration characterized by both small area and short delay -- so, in contrast to previous applications, a win on both metrics. The design is based on mathematical analysis that demonstrates that the summation of a large number of terms in the numerical integration could lead to a significant delay reduction. An architecture is proposed for this task. Experiments confirm that the stochastic implementation has smaller area and shorter delay than conventional implementations.

This paper studies the implementation of Boolean functions by lattices of four-terminal switches. Each switch is controlled by a Boolean literal. If the literal takes the value 1, the corresponding switch is connected to its four neighbors; else it is not connected. A Boolean function is implemented in terms of connectivity across the lattice: it evaluates to 1 iff there exists a connected path between two opposing edges of the lattice. The paper addresses the following synthesis problem: how should one assign literals to switches in a lattice in order to implement a given target Boolean function? The goal is to minimize the lattice size, measured in terms of the number of switches. An efficient algorithm for this task is presented-one that does not exhaustively enumerate paths but rather exploits the concept of Boolean function duality. The algorithm produces lattices with a size that grows linearly with the number of products of the target Boolean function in ISOP form. It runs in time that grows polynomially. Synthesis trials are performed on standard benchmark circuits. The synthesis results are compared to a lower-bound calculation on the lattice size.

The accepted wisdom is that combinational circuits must have acyclic (i.e., feed-forward) topologies. Yet simple examples suggest that this is incorrect. In fact, introducing cycles (i.e., feedback) into combinational designs can lead to significant savings in area and in delay. Prior work described methodologies for synthesizing cyclic circuits with Sum-Of-Product (SOP) and Binary-Decision Diagram (BDD)-based formulations. Recently, techniques for analyzing and mapping cyclic circuits based on Boolean satisfiability (SAT) were proposed. This article presents a SAT-based methodology for synthesizing cyclic dependencies. The strategy is to generate cyclic functional dependencies through a technique called Craig interpolation. Given a choice of different functional dependencies, a branch-and-bound search is performed to pick the best one. Experiments on benchmark circuits demonstrate the effectiveness of the approach.

Just as electronic systems implement computation in terms of voltage (energy per unit charge), molecular systems compute in terms of chemical concentrations (molecules per unit volume). Prior work has established mechanisms for implementing logical and arithmetic functions including addition, multiplication, exponentiation, and logarithms with molecular reactions. In this paper, we present a general methodology for implementing synchronous sequential computation. We generate a four-phase clock signal through robust, sustained chemical oscillations. We implement memory elements by transferring concentrations between molecular types in alternating phases of the clock. We illustrate our design methodology with examples: a binary counter as well as a four-point, two-parallel FFT. We validate our designs through ODE simulations of mass-action chemical kinetics. We are exploring DNA-based computation via strand displacement as a possible experimental chassis.

Mounting concerns over variability, defects, and noise motivate a new approach for digital circuitry: stochastic logic, that is to say, logic that operates on probabilistic signals and so can cope with errors and uncertainty. Techniques for probabilistic analysis of circuits and systems are well established. We advocate a strategy for synthesis. In prior work, we described a methodology for synthesizing stochastic logic, that is to say logic that operates on probabilistic bit streams. In this paper, we apply the concept of stochastic logic to a reconfigurable architecture that implements processing operations on a datapath. We analyze cost as well as the sources of error: approximation, quantization, and random fluctuations. We study the effectiveness of the architecture on a collection of benchmarks for image processing. The stochastic architecture requires less area than conventional hardware implementations. Moreover, it is much more tolerant of soft errors (bit flips) than these deterministic implementations. This fault tolerance scales gracefully to very large numbers of errors.

Schemes for probabilistic computation can exploit physical sources to generate random values in the form of bit streams. Generally, each source has a fixed bias and so provides bits with a specific probability of being one. If many different probability values are required, it can be expensive to generate all of these directly from physical sources. This paper demonstrates novel techniques for synthesizing combinational logic that transforms source probabilities into different target probabilities. We consider three scenarios in terms of whether the source probabilities are specified and whether they can be duplicated. In the case that the source probabilities are not specified and can be duplicated, we provide a specific choice, the set {0.4, 0.5} ; we show how to synthesize logic that transforms probabilities from this set into arbitrary decimal probabilities. Further, we show that for any integern≥ 2, there exists a single probability that can be transformed into arbitrary base-nfractional probabilities. In the case that the source probabilities are specified and cannot be duplicated, we provide two methods for synthesizing logic to transform them into target probabilities. In the case that the source probabilities are not specified, but once chosen cannot be duplicated, we provide an optimal choice.

This paper studies the implementation of Boolean functions with lattices of two-dimensional switches. Each switch is controlled by a Boolean literal. If the literal is 1, the switch is connected to its four neighbours; else it is not connected. Boolean functions are implemented in terms of connectivity across the lattice: a Boolean function evaluates to 1 iff there exists a top-to-bottom path. The paper addresses the following synthesis problem: how should we map literals to switches in a lattice in order to implement a given target Boolean function? We seek to minimize the number of switches. Also, we aim for an efficient algorithm -- one that does not exhaustively enumerate paths. We exploit the concept of lattice and Boolean function duality. We demonstrate a synthesis method that produces lattices with a number of switches that grows linearly with the number of product terms in the function. Our algorithm runs in time that grows polynomially.

In the nascent field of synthetic biology, researchers are striving to create biological systems with functionality not seen in nature. This special session features talks that emphasize the fundamental engineering principles underlying this endeavor, highlighting possible synergies with electronic design automation (EDA). Pamela Silver will describe designing and constructing proteins and cells with predictable biological properties. These serve as potential therapeutics, cell-based sensors, factories for generating bio-energy, and bio-remediation. J. Christopher Anderson will demonstrate how complex biological functions can be decomposed into modular devices. He will describe the construction of therapeutic organisms and new tools for building complex systems. Richard Murray will discuss the use of concepts from control and dynamical systems in the analysis and design of biological feedback circuits at the molecular level.

Craig Interpolation is a state-of-the-art technique for logic synthesis and verification, based on Boolean Satisfiability (SAT). Leveraging the efficacy of SAT algorithms, Craig Interpolation produces solutions quickly to challenging problems such as synthesizing functional dependencies and performing bounded model-checking. Unfortunately, the quality of the solutions is often poor. When interpolants are used to synthesize functional dependencies, the resulting structure of the functions may be unnecessarily complex. In most applications to date, interpolants have been generated directly from the proofs of unsatisfiability that are provided by SAT solvers. In this work, we propose efficient methods based on incremental SAT solving for modifying resolution proofs in order to obtain more compact interpolants. This, in turn, reduces the cost of the logic that is generated for functional dependencies.

We present a methodology for implementing digital signal processing (DSP) operations such as filtering with biomolecular reactions. From a DSP specification, we demonstrate how to synthesize biomolecular reactions that produce time-varying output quantities of molecules as a function of time-varying input quantities. Unlike all previous schemes for biomolecular computation, ours produces designs that are dependent only on coarse rate categories for the reactions (“fast” and “slow”). Given such categories, the computation is exact and independent of the specific reaction rates. We implement DSP operations through a self-timed “handshaking” protocol that transfers quantities between molecular types based on the absence of other types. We illustrate our methodology with the design of a simple moving-average filter as well as a more complex biquad filter. We validate our designs through transient stochastic simulations of the chemical kinetics. Although conceptual for the time being, the proposed methodology has potential applications in domains of synthetic biology such as biochemical sensing and drug delivery. We are exploring DNA-based computation via strand displacement as a possible experimental chassis.

In this study, we apply a novel synthesis technique for implementing robust digital computation in nanoscale lattices with random interconnects: percolation theory on random graphs. We exploit the non-linearity that occurs through percolation to produce Boolean functionality. We show that the error margins, defined in terms of the steepness of the non-linearity, translate into the degree of defect tolerance. We study the problem of mapping Boolean functions onto lattices with good error margins.

Mounting concerns over variability, defects and noise motivate a new approach for integrated circuits: the design of stochastic logic, that is to say, digital circuitry that operates on probabilistic signals, and so can cope with errors and uncertainty. Techniques for probabilistic analysis are well established. We advocate a strategy for synthesis. In this paper, we present a reconfigurable architecture that implements the computation of arbitrary continuous functions with stochastic logic. We analyze the sources of error: approximation, quantization, and random fluctuations. We demonstrate the effectiveness of our method on a collection of benchmarks for image processing. Synthesis trials show that our stochastic architecture requires less area than conventional hardware implementations. It achieves a large speed up compared to software conventional implementations. Most importantly, it is much more tolerant of soft errors (bit flips) than these deterministic implementations.

As CMOS devices are scaled down into the nanometer regime, concerns about reliability are mounting. Instead of viewing nano-scale characteristics as an impediment, technologies such as PCMOS exploit them as a source of randomness. The technology generates random numbers that are used in probabilistic algorithms. With the PCMOS approach, different voltage levels are used to generate different probability values. If many different probability values are required, this approach becomes prohibitively expensive.

As integrated circuit technology plumbs ever greater depths in the scaling of feature sizes, maintaining the paradigm of deterministic Boolean computation is increasingly challenging. Indeed, mounting concerns over noise and uncertainty in signal values motivate a new approach: the design of stochastic logic, that is to say, digital circuitry that processes signals probabilistically, and so can cope with errors and uncertainty. In this paper, we present a general methodology for synthesizing stochastic logic for the computation of polynomial arithmetic functions, a category that is important for applications such as digital signal processing. The method is based on converting polynomials into a particular mathematical form --- Bernstein polynomials --- and then implementing the computation with stochastic logic. The resulting logic processes serial or parallel streams that are random at the bit level. In the aggregate, the computation becomes accurate, since the results depend only on the precision of the statistics. Experiments show that our method produces circuits that are highly tolerant of errors in the input stream, while the area-delay product of the circuit is comparable to that of deterministic implementations.

The accepted wisdom is that combinational circuits must have acyclic (i.e., loop-free or feed-forward) topologies. And yet simple examples suggest that this need not be so. In previous work, we advocated the design of cyclic combinational circuits (i.e., circuits with loops or feedback paths). We proposed a synthesis methodology and demonstrated that it produces significant improvements in area and in delay. The analysis method that we used to validate cyclic circuits was based on binary decision diagrams. In this paper, we propose a much more efficient technique for analysis based on Boolean satisfiability (SAT).

We are developing a framework for computation with biochemical reactions with a focus on synthesizing specific logical functionality, a task analogous to technology-independent logic synthesis. Our method synthesizes biochemical reactions that compute output quantities of molecular types as a function of input quantities, either deterministically or probabilistically. An important constraint is the timing, captured in the relative rates of the biochemical reactions: all the outputs of a given phase must be produced before the next phase can begin consuming them as inputs. To achieve this synchronization, the reaction rates must sometimes be separated by orders of magnitude: some much faster than others, some much slower. This might be costly or infeasible given a specific library of biochemical reactions. In this paper, we describe a novel mechanism for locking the computation of biochemical modules - analogous to handshaking mechanisms in asynchronous circuit design. With locking, our method synthesizes robust computation that is nearly rate independent, requiring at most two speeds (ldquofastrdquo and ldquoslowrdquo). The trade-off is with respect to the size of the solution: more reactions are needed. We characterize this trade-off for interand intra-module locking in general and for a variety of specific modules that we have designed. In particular, we discuss locking in detail for a stochastic module that implements probabilistic computation, producing different combinations of molecular types according to specified probability distributions.

Randomness is inherent to biochemistry: at each instant, the sequence of reactions that fires is a matter of chance. Some biological systems exploit such randomness, choosing between different outcomes stochastically - in effect, hedging their bets with a portfolio of responses for different environmental conditions. In this paper, we discuss techniques for synthesizing such stochastic behavior in engineered biochemical systems. We propose a general method for designing a set of biochemical reactions that produces different combinations of molecular types according to a specified probability distribution. The response is precise and robust to perturbations. Furthermore, it is programmable: the probability distribution is a function of the quantities of input types. The method is modular and extensible. We discuss strategies for implementing various functional dependencies: linear, logarithmic, exponential, etc. This work has potential applications in domains such as biochemical sensing, drug production, and disease treatment. Moreover, it provides a framework for analyzing and characterizing the stochastic dynamics in natural biochemical systems such as the lysis/lysogeny switch of the lambda bacteriophage.

Digital circuits are called combinational if they are memoryless: they have outputs that depend only on the current values of the inputs. Combinational circuits are generally thought of as acyclic (i.e., feed-forward) structures. And yet, cyclic circuits can be combinational. Cycles sometimes occur in designs synthesized from high-level descriptions. Feedback in such cases is carefully contrived, typically occurring when functional units are connected in a cyclic topology. Although the premise of cycles in combinational circuits has been accepted, and analysis techniques have been proposed, no one has attempted the synthesis of circuits with feedback at the logic level.We propose a general methodology for the synthesis of multilevel combinational circuits with cyclic topologies. Our approach is to introduce feedback in the substitution / minimization phase, optimizing a multilevel network description for area. In trials with benchmark circuits, many were optimized significantly, with improvements of up to 30% in the area. superior to acyclic.We argue the case for radically rethinking the concept of "combinational" in circuit design: we should no longer think of combinational logic as acyclic in theory or in practice, since nearly all combinational circuits are best designed with cycles.

The RAIN project is a research collaboration between Caltech and NASA-JPL on distributed computing and data-storage systems for future spaceborne missions. The goal of the project is to identify and develop key building blocks for reliable distributed systems built with inexpensive off-the-shelf components. The RAIN platform consists of a heterogeneous cluster of computing and/or storage nodes connected via multiple interfaces to networks configured in fault-tolerant topologies. The RAIN software components run in conjunction with operating system services and standard network protocols. Through software-implemented fault tolerance, the system tolerates multiple node, link, and switch failures, with no single point of failure. The RAIN-technology has been transferred to Rainfinity, a start-up company focusing on creating clustered solutions for improving the performance and availability of Internet data centers. In this paper, we describe the following contributions: 1) fault-tolerant interconnect topologies and communication protocols providing consistent error reporting of link failures, 2) fault management techniques based on group membership, and 3) data storage schemes based on computationally efficient error-control codes. We present several proof-of-concept applications: a highly-available video server, a highly-available Web server, and a distributed checkpointing system. Also, we describe a commercial product, Rainwall, built with the RAIN technology.

A methodology for evaluating the fault coverage of RAM test algorithms is proposed and the architecture of a flexible software analysis program is described. The analysis, performed for arbitrary test sequences, provides a comprehensive set of coverage statistics for functional cell-array faults. An overview of the analysis capabilities of the program is given, the fault state transition conditions for several representative fault classes are specified, and coverage analyses results for a variety of test algorithms are presented.