Research

From The Circuits and Biology Lab at UMN

1 Circuits and Biology
2 Bio-Design Automation
3 Stochastic Logic
4 Combinational Circuits with Feedback
5 Former Work
6 Related Work

Circuits and Biology

In discourse, disciplines of scientific research sometimes are branded as "hard" or "soft" according to the perceived mathematical rigor and objectivity of their endeavors. The degree of hardness decreases from the physical sciences (rock-hard and objective), to the biological sciences, to the social sciences (soft and subjective). There is also a presumed food chain: the "pure" sciences and mathematics produce new understanding; the "applied" sciences and engineering consume it. Such characterizations are vacuous. Consider that statisticians in the social sciences engage in sophisticated mathematics and that theoretical physicists apply intuition to thought experiments. Increasingly, disciplines across the scientific spectrum are being hardened with quantitative analysis: data, observations, models – everything is stuffed into a computer and analyzed. Also, engineering methods for design are being used in a deliberate way to validate new science. As Richard Feynman stipulated, "If I can't create it, I don't understand it." Understanding is achieved by constructing and testing simplified systems from the bottom up, teasing out and nailing down the fundamental principles in the process.

The research activities in our lab encompass projects in the design and verification of digital circuits as well as in synthetic and computational biology. A broad theme is the application of computational expertise from the former (circuit design) to analysis and design problems in the latter (biology). A specific theme that cuts across both domains is constructing and deconstructing probabilistic behavior. In the biological realm, we are designing biochemical pathways that produce different combinations of molecular types according to programmable probability distributions. This gives us the ability to fine-tune the response – akin to hedging with a portfolio of investments. In the engineering realm, we are designing digital circuits that process "zeros" and "ones" probabilistically. This is a promising strategy for coping with the randomness that occurs due to noise and glitches as circuit components are scaled down to nanometers in size. In both realms, the tools of our trade are neither hard, nor soft, nor applied: rather, they are analytical, conceptual, and computational.

Bio-Design Automation

One of the great successes of the integrated circuit design community has been in abstracting and scaling the design problem. The physical behavior of transistors is understood in terms of differential equations – say, with models found in tools such as SPICE. However, the design of integrated circuits proceeds at a more abstract level – in terms of gates, modules, and components. In principle, one could write down a gargantuan system of coupled differential equations describing a circuit in its entirety, at the transistor level. However, one could never hope to compute solutions to such a system, and there would be little gained by doing~so. The value in the modeling effort stems from the abstractions and what they tell us. Similarly, design abstractions have significant value in the context of synthetic biology.

Given a detailed model for a cellular process and efficient techniques for analysis, one could contemplate "in silico" experimentation – that is to say, varying the inputs and parameters and observing the outputs – in a manner analogous to traditional "in vitro" and "in vivo" experimentation. The impetus for biological synthesis is, in fact, broader. Beyond analysis, there is the hope that one could engineer a form of "logical" control over biological processes, designing pathways that produce specific outputs in response to different combinations of inputs. This approach could have applications in biochemical sensing as well as in medical diagnosis and treatment of diseases.

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.

Paper: The Synthesis of Stochasticity in Biochemical Systems.

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 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 ("fast" and "slow"). The trade-off is with respect to the size of the solution: more reactions are needed. We characterize this trade-off for inter- and intra-module locking in general and for a variety of specific modules that we have designed.

Paper: Module Locking in Biochemical Synthesis.

Abstract: Characterizing the Stochastic Decisions of Biomolecular Systems with Probability Gradients.

Abstract: Exact Stochastic Simulation with Event Leaping.

Stochastic Logic

In a debate with an alchemist in 1628, the great French mathematician René Descartes denied the claim that probabilities are as good as certainties in science. Ever since, there has been a lingering stigma associated with estimations and approximations. Those who can, calculate things exactly. Those who can't, simulate and guess. Of course, in modern engineering, probabilistic analysis has become indispensable. However, it is generally applied as a tool for characterizing uncertainty: one postulates a definite model and then affixes uncertainties and error margins. 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 new. Instead of characterizing randomness and making inferences from statistics, we explore techniques for producing computation that is itself structured probabilistically.

The Probabilistic Paradigm

The successful design formula for all digital circuits has been rigidly hierarchical, with sharp boundaries in the levels of abstraction at different levels. At the logic level, there are standardized gates and components with prescribed functionality. At the system level, there are microprocessors with common instruction sets. At the algorithmic level, software executes without explicit reference to the underlying hardware. At all levels, there exists a substantial investment in the CAD tools – indeed, also in the expertise of the end-users – tailored for specific design and optimization tasks.

It is between the logical level and the physical level that the classic analog/digital boundary occurs: beneath it, circuits are physical devices operating on real-valued voltage signals; above it, they process zeros and ones. Implicitly, there is an another boundary of abstraction that occurs here, that between physical modeling and abstraction: above it there is certainty and determinism; beneath it, there is uncertainty and randomness.

Indeed, while physical circuits are modeled with variances and defects and designed with error margins and tolerances, logical circuits are not. From the logic level up, the precise Boolean functionality of a circuit is fixed; it is up to the physical layer to produce voltage values that can be interpreted as the exact logical values that are called for. This abstraction is firmly entrenched yet costly: variability, uncertainty, noise – all must be compensated for through ever more complex design techniques at the physical level. As the scale of technology pushes into ever deeper regimes, the cost and complexity are threatening to stall progress. We argue that the deterministic paradigm for computation is the wrong one.

We are developin a probabilistic calculus for analysis and for design based on a novel view of computation: instead of transforming definite inputs into definite outputs – say, Boolean, integer or real values into the same – circuits and biological systems transform probability values into probability values; so, conceptually, real-valued probabilities are both the inputs and the outputs (even though the underlying behavior might be discrete). Uncertainty is not merely something that is affixed after the fact or tolerated with margins in the designs; it is exploited for efficiency and robustness directly in the design.

This results in a dynamically tuneable trade-off between computation time, accuracy, and reliability. Not only can variations and uncertainties be tolerated, randomness can be exploited in processor design and at and algorithmic level. While the method entails redundancy in the encoding of signal values, complex operations can be performed using simple logic.

Our methodology targets circuits that are characterized by uncertainty in their physical attributes; thus, it provides a strategy for coping with variability of technological parameters. It is compelling for technologies that are inherently random in character – for instance, nanoscale technologies based on stochastic self-assembly. Furthermore, it provides a strategy for fault tolerance and failure resistance, both in the underlying logic components as well as in the signal values. If noise-related faults produce random bit flips, these result in fluctuations in the statistics; accuracy can be regained through increased redundancy. Thus, the approach provides tolerance of transient faults that scales gracefully to large numbers of errors.

Paper: The Synthesis of Stochastic Logic for Nanoscale Computation.

Paper: The Synthesis of Robust Polynomial Arithmetic with Stochastic Logic.

Combinational Circuits with Feedback

In the realm of digital design, a rigid hierarchical view has become firmly entrenched: Logic gates are built from transistors; combinational circuits are built from logic gates arranged in feed-forward (i.e., acyclic) configurations; synchronous circuits are built from combinational circuits and memory elements arranged in feedback (i.e., cyclic) configurations; and, finally, digital systems are built from synchronous modules and peripheral logic. This paradigm has been tremendously successful in the design of silicon integrated circuits – so successful, in fact, that the perception exists that this is the only way circuits can be designed.

We are exploring the topic of cyclic combinational circuits in depth – both the theoretical underpinnings and the practical implications. On the theoretical front, we have shown that the distinction between cyclic and acyclic circuits is a fundamental one. We have proved that certain functions can be implemented with fewer gates using cyclic designs than is possible with acyclic designs. In fact, some functions can be implemented with half as many gates. On the practical front, we have devised a general methodology for the analysis and synthesis of cyclic circuits.

The approach for synthesis is conceptually very general. Cycles are introduced through the incremental application of restructuring and minimization operations, optimizing a design for area and delay. These optimizations are carried through to the decomposition and technology mapping phases. Perhaps the most salient result to report is that cyclic solutions are not a rarity; they can readily be found for most circuits of practical interest.

Paper: The Analysis of Cyclic Circuits with Boolean Satisfiability.

Paper: Timing Analysis of Cyclic Combinational Circuits.

Paper: The Synthesis of Cyclic Combinational Circuits