Computing with Things Small, Wet, and Random
Our research strives for novel and transformative approaches to design automation. A broad theme is the application of expertise from an established field (digital circuit design) to new areas (nanotechnology and synthetic biology). A specific theme that cuts across these domains is constructing and deconstructing probabilistic behavior. In the realm of synthetic biology, we are developing techniques for designing biochemical pathways that produce different combinations of molecular types according to specified probability distributions. In the realm of nanotechnology, we are developing develop techniques for designing digital circuits that process zeros and ones probabilistically.
Bio-Design Automation
We are developing a modular and extensible design flow for synthesizing biochemical computation. Given a target specification, our method selects biochemical reactions that produce specified outputs as a function of inputs. The design is first performed at a conceptual level, in terms of abstract biochemical reactions – a task analogous to technology-independent logic synthesis. Then the system is mapped onto specific protein-protein reactions, selected from libraries – a task analogous to technology mapping in circuit design.
Writing and Compiling Code into Biochemistry
Our compiler called VERB (Verilog Elements for Register-based Biochemistry) translates Verilog specifications into biochemical reactions that perform sequential arithmetic computation on protein quantities, analogous to register-based computations in digital systems. The designs are validated through transient stochastic simulation of the chemical kinetics. Our synthesis tool called BAMBI (Brian's Automated Modular Biochemical Instantiator) glues the biochemical modules together and maps these to reactions libraries.
Note that BAMBI is merely an acronym; it is not an attempt to put a "soft, cuddly face on the dangerous science of synthetic biology", as was suggested recently by a bio-ethicist!
Synthesizing Stochasticity
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 our approach, we synthesize such stochastic behavior deliberately: we design biochemical systems that produce different combinations of proteins according to specified probability distributions. Setting up such a probabilistic response is akin to hedging with a portfolio of investments: taken across a population of cells, the response is precise and robust to perturbations.
File:Quantities-to-probabilities.jpg From quantities to probabilities: the biochemical system either produces a fixed quantity of an output protein type Z or doesn't produce any amount of Z at all; it does so with probability corresponding to the relative amount of input protein types X and Y.
Clocking and Locking Biochemistry
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. We have proposed 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 ("fast" and "slow").
Stochastic Simulation and Transient Analysis
Characterizing the probabilistic behavior of biochemical systems is a challenging problem from a computational standpoint. The standard approach is to use stochastic simulation, as proposed by Gillespie. The drawback is the prohibitive computation time that is required. We are developing simulation techniques that are computationally efficient, based on caching and event leaping; further, we are developing information-theoretic analysis techniques, such as probability gradients, that provide fine-grained statistics for characterizing the behavior of biochemical systems. We have proposed a framework for stochastic transient analysis (STA) that incorporates time-dependent variations in the quantities of species into stochastic simulation.
Stochastic Computation
In the physical and biological sciences, statistical analysis of data is pervasive. However, such analysis generally is applied as a tool for inference: given noisy experimental data, one attempts to extract information that is beyond the reach of direct measurements. The approach taken in this project is fundamentally different. Instead of characterizing randomness and making inferences from statistics, we explore techniques for producing computation that is itself structured probabilistically.
Stochastic Logic
We synthesize circuits that, conceptually, transform probability values into probability values. Operations at the logic level are performed on randomized values in serial streams or on parallel “bundles” of wires. The bit streams or wire bundles are digital, carrying zeros and ones; they are processed by ordinary logic gates, such as AND and OR. The signal is conveyed through the statistical distribution of the logical values. While the method entails redundancy in the encoding of signal values, complex operations can be performed using simple logic.
We demonstrate how to generate arbitrary decimal probabilities from small sets – single probabilities or pairs of probabilities – through combinational logic.
File:ReSC-gamma-correction.jpg Results of error injection for implementations of the gamma correction function: the images in the top row are generated by conventional logic; the images in the bottom row are generated by stochastic logic. Soft errors are injected at a rate of: (a) 1%; (b) 2%; (c) 10%.
Our synthesis strategy is to cast logic computations as arithmetic operations in the probabilistic domain and implement these directly as stochastic operations on data-paths. Synthesis trials show that our stochastic architecture is much more tolerant of soft errors (bit flips) than these deterministic implementations. If noise-related faults produce random bit flips, these result in fluctuations in the statistics; accuracy is regained through increased redundancy. This tolerance of transient faults scales gracefully to large numbers of errors.
File:Crossbar.jpg Probabilistic bundles are implemented in nanowire crossbar technology through stochastic self-assembly: random doping produces FET-like connections.
File:Percolation.jpg Percolation in media with random local connectivity: below a critical threshold, the probability of global connectivity quickly drops to zero; above it, the probability quickly rises to one.
File:Lattice-computation.jpg Lattice-based computation of Boolean functions. Top-to-bottom and Left-to-right Boolean functions are
and
respectively that are mutually dual.
Nanoscale Computation
Our methodology targets circuits that are characterized by uncertainty in their physical attributes or that are inherently random in character – for instance, nanoscale technologies based on stochastic self-assembly. Existing strategies for synthesizing logic for nanowire arrays relied on probing the circuit and programming interconnects after fabrication. By synthesizing logical functionality on stochastic wire bundles, we exploit both the parallelism and the random effects of the self-assembly, obviating the need for such post-fabrication configuration.
With inherent randomness in the interconnects of nanofabrics, we suggest a new paradigm: robust digital computation through random percolation. We exploit the non-linearity that occurs through percolation to build reliable Boolean functions. We achieve this computation with no switches or logic elements; the functionality is produced by the percolation activity that occurs due to the random connectivity of the fabric.
We study the implementation of Boolean functions in a regular lattice of two-dimensional switches. Although framed in terms of a technology-independent model, the techniques are applicable to emerging technologies such as nanowire-based crossbar switching networks. Boolean variables are assigned to switches. If a Boolean variable is 1, the switch is connected to its four neighbors; 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 or left-to-right path. This
paper address the following logic synthesis problem: how to layout variables in a lattice in order to implement a given target Boolean function robustly and efficiently.
Combinational Circuits with Feedback
The accepted wisdom is that combinational circuits (i.e., memoryless circuits) must have acyclic (i.e., loop-free or feed-forward) topologies. And yet simple examples suggest that this need not be so. We advocate the design of cyclic combinational circuits (i.e., circuits with loops or feedback paths). We have proposed a methodology for synthesizing such circuits and demonstrated that it produces significant improvements in area and in delay.
In the original formulation, the functional dependencies were obtained through Sum-of-Products (SOP) minimization with the Berkeley SIS package; validation was performed with Binary Decision Diagram (BDD)-based analysis. In recent work, have developed Boolean Satisfiability (SAT)-based techniques for synthesizing cyclic dependencies, through Craig Interpolation.
File:Cyclic-combinational-circuit.jpg A cyclic combinational circuit produced by our tool
Cyclify. The circuit implements the functions
Note that the circuit consists of 9 two-input AND/OR gates (as well as inverters). In contrast, the best acyclic circuit implementing these three functions requires 10 such gates (as well as inverters).
Former Work
Please see Marc's former research pages at Caltech.
Related Work
Here are some papers of interest to our research group: References.
Internal
New Research Page (in progress)
; (b) Scaled addition: 
