Difference between revisions of "Research"

From The Circuits and Biology Lab at UMN
Jump to navigationJump to search
(Computing with Things Small, Wet, and Random)
(Computing with Things Small, Wet, and Random)
Line 19: Line 19:
 
| |        
 
| |        
 
|}
 
|}
 
Test.
 
  
 
{|
 
{|

Revision as of 10:49, 24 January 2011

The great mathematician John von Neumann articulated the view that research should always be guided by applications that can have a positive and meaningful influence on humankind. This view was not based solely on his altruistic concerns, although these were deeply-rooted; rather, in his judgment, real-world applications give rise to the most interesting problems in mathematics. Our research spans different disciplines from circuit design, to algorithms, to mathematics, to synthetic biology. In all of these disciplines, we strive for contributions that satisfy von Neumann's criteria: conceptually interesting research that has the potential for a significant impact.

Computing with Things Small, Wet, and Random

title: Computing with Things Small, Wet, and Random
Design Automation for Digital Computation with Nanoscale Technologies and Biological Processes
author: Marc Riedel
       

Ppt.jpg
Slides

       
title: Circuit Engineers Doing Biology
A Discourse on the Changing Landscape of Scientific Research
author: Marc Riedel
       

Pdf.jpg
Abstract

       

Ppt.jpg
Slides

       

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.

title: A Synthesis Flow for Digital Signal Processing with Biomolecular Reactions
authors: Hua Jiang, Aleksandra Kharam (Vedeneeva), Marc Riedel and Keshab Parhi
to be presented at: 2010 IEEE/ACM International Conference on Computer-Aided Design; 2010 IEEE Workshop on Signal Processing Systems
       

Pdf.jpg
Paper

       

Pdf.jpg
Paper

title: Writing and Compiling Code into Biochemistry
authors: Adam Shea, Brian Fett, Marc Riedel, and Keshab Parhi
presented at: Pacific Symposium on Biocomputing, Kona, Hawaii, 2010 (also see blog); International Conference on Computer-Aided Design , San Jose, CA, 2009.
   

Pdf.jpg
Paper

       

Ppt.jpg
Slides


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.
title: Synthesizing Stochasticity in Biochemical Systems
authors: Brian Fett, Shuki Bruck, and Marc Riedel
presented at: Design Automation Conference, San Diego, 2007; Synthetic Biology 3.0, Zürich, 2007.
       

Pdf.jpg
Paper

       

Ppt.jpg
Slides

       

M4v.jpg
Video

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").

title: [nearly] Rate Independent Synthesis of Stochastic Biochemical Computation
authors: Brian Fett, Adam Shea, and Marc Riedel
presented at: Institute of Biological Engineering Annual Conference, Santa Clara, CA, 2009.
       

Pdf.jpg
Abstract

       

Ppt.jpg
Slides

title: Module Locking in Biochemical Systems
authors: Brian Fett and Marc Riedel
presented at: International Conference on Computer-Aided Design, San Jose, CA, 2008; Synthetic Biology 4.0, Hong Kong, 2008.
       

Pdf.jpg
Paper

       

Ppt.jpg
Slides

Stochastic Simulation and Transient Analysis

File:Event-leaping.jpg
Exact Stochastic Simulation with Event Leaping: multiple reactions are executed in a single step.

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.

title: Exact Stochastic Simulation with Event Leaping
authors: Marc Riedel and Shuki Bruck
presented at: International Conference on Systems Biology, Boston, 2005.
       

Pdf.jpg
Abstract

       

Ppt.jpg
Slides

title: Characterizing Biochemical Systems with Probability Gradients
authors: Brian Fett and Marc Riedel
presented at: International Conference on Systems Biology, Yokohama, Japan, 2006.
       

Pdf.jpg
Abstract

title: Stochastic Transient Analysis of Biochemical Systems
authors: Bin Cheng and Marc Riedel
presented at: Pacific Symposium on Biocomputing, Hawaii, 2009.
       

Pdf.jpg
Paper

       

Pdf.jpg
M.S. Thesis

       

Ppt.jpg
Slides

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.

File:Multiplication-scaled-addition.jpg
Multiplication and scaled addition on stochastic bit streams:
(a) Multiplication: ; (b) Scaled addition:

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.

File:Synthesis-Probability-Example.jpg
A circuit taking input probabilities from the set S = {0.4, 0.5} generating a decimal output probability of 0.757.
title: The Synthesis of Robust Polynomial Arithmetic with Stochastic Logic
authors: Weikang Qian and Marc Riedel
presented at: Design Automation Conference, Anaheim, CA, 2008
       

Pdf.jpg
Paper

       

Ppt.jpg
Slides

title: The Synthesis of Stochastic Logic to Perform Multivariate Polynomial Arithmetic
authors: Weikang Qian and Marc Riedel
presented at: The International Workshop on Logic and Synthesis, Lake Tahoe, CA, 2008
       

Pdf.jpg
Paper

       

Ppt.jpg
Poster

We demonstrate how to generate arbitrary decimal probabilities from small sets – single probabilities or pairs of probabilities – through combinational logic.

title: The Synthesis of Combinational Logic to Generate Probabilities
authors: Weikang Qian, Marc Riedel, Kia Bazargan, and David Lilja
presented at: International Conference on Computer-Aided Design, San Jose, 2009.
       

Pdf.jpg
Paper

       

Ppt.jpg
Slides

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.

title: An Architecture for Fault-Tolerant Computation with Stochastic Logic
authors: Xin Li, Weikang Qian, Marc Riedel, Kia Bazargan, and David Lilja
presented at: Great Lakes Symposium on VLSI, Boston, MA, 2009
submitted to: IEEE Transactions on Computers.
       

Pdf.jpg
Paper

       

Ppt.jpg
Slides

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.
title: Estimation and Optimization of Reliability of Noisy Digital Circuits
authors: Satish Sivaswamy, Kia Bazargan and Marc Riedel
presented at: The International Symposium on Quality Electronic Design, San Jose, CA, 2009.
       

Pdf.jpg
Paper

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.

title: The Synthesis of Stochastic Circuits for Nanoscale Computation
authors: Weikang Qian, John Backes, and Marc Riedel
presented at: International Workshop on Logic and Synthesis, San Diego, CA, 2007.
published in: International Journal of Nanotechnology and Molecular Computation, Vol. 1, Issue 4, 2010.
       

Pdf.jpg
Paper

       

Ppt.jpg
Slides

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.

title: Nanoscale Digital Computation Through Percolation
authors: Mustafa Altun, Marc Riedel, and Claudia Neuhauser
presented at: Design Automation Conference, San Francisco, CA, 2009.

Pdf.jpg
Abstract

Ppt.jpg
Slides

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.

title: Logic Synthesis for Switching Lattices
authors: Mustafa Altun and Marc Riedel
submitted to: IEEE Transactions on Computers.

Pdf.jpg
Paper

title: Lattice-Based Computation of Boolean Functions
authors: Mustafa Altun and Marc Riedel
presented at: Design Automation Conference, Anaheim, CA, 2010.

Pdf.jpg
Paper

Ppt.jpg
Slides

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.

title: The Analysis and Mapping of Cyclic Circuits with Boolean Satisfiability
authors: John Backes, Brian Fett and Marc Riedel
submitted to: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
       

Pdf.jpg
Paper

title: Cyclic Boolean Circuits
authors: Marc Riedel and Shuki Bruck
submitted to: Journal of Discrete Applied Mathematics, 2009.
       

Pdf.jpg
Paper

       

Pdf.jpg
PhD Dissertation

       

Ppt.jpg
Slides

title: The Synthesis of Cyclic Combinational Circuits
authors: Marc Riedel and Shuki Bruck
presented at: Design Automation Conference, Anahiem, CA, 2003.
       

Pdf.jpg
Paper

       

Pdf.jpg
Abstract

       

Ppt.jpg
Slides

title: Timing Analysis of Cyclic Combinational Circuits
authors: Marc Riedel and Shuki Bruck
presented at: The International Workshop on Logic and Synthesis, Temecula, CA, 2004.
       

Pdf.jpg
Paper

       

Ppt.jpg
Slides

title: The Analysis of Cyclic Circuits with Boolean Satisfiability
authors: John Backes, Brian Fett, and Marc Riedel
presented at: The International Conference on Computer-Aided Design, San Jose, CA, 2008.
       

Pdf.jpg
Paper

       

Ppt.jpg
Slides

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).

SAT-Based Algorithms

The power of modern SAT solvers is becoming more and more significant. SAT solvers are being used for many applications in Logic Synthesis and Verification. Recently, Craig Interpolation has been shown to be an important tool to boost the performance of some SAT-Based Algorithms. In our work we show how SAT can be used to analyze and synthesis cyclic circuits. We also introduce improvements to interpolation algorithms.


title: Reduction of Interpolants For Logic Synthesis
authors: John Backes and Marc Riedel
presented at: International Workshop on Logic and Synthesis, Irvine, CA, 2010.
to be presented at: The International Conference on Computer-Aided Design, San Jose, CA, 2010.
       

Pdf.jpg
Paper

       

Ppt.jpg
Slides

title: The Synthesis of Cyclic Dependencies with Craig Interpolation
authors: John Backes and Marc Riedel
presented at: International Workshop on Logic and Synthesis, Berkeley, CA, 2009.
       

Pdf.jpg
Paper

       

Ppt.jpg
Slides

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)