Difference between revisions of "Research"
Line 2:  Line 2:  
Our research spans different disciplines ranging from digital circuit design, to algorithms, to mathematics, to synthetic biology. It tends to be ''inductive'' (as opposed to ''deductive'') and ''conceptual'' (as opposed to ''applied''). A recurring theme is building systems that compute in novel or unexpected ways with new and emerging technologies. Often, the task of ''analyzing'' the way things work in a new technology is straightforward; however the task of ''synthesizing'' new computational constructs is more challenging.  Our research spans different disciplines ranging from digital circuit design, to algorithms, to mathematics, to synthetic biology. It tends to be ''inductive'' (as opposed to ''deductive'') and ''conceptual'' (as opposed to ''applied''). A recurring theme is building systems that compute in novel or unexpected ways with new and emerging technologies. Often, the task of ''analyzing'' the way things work in a new technology is straightforward; however the task of ''synthesizing'' new computational constructs is more challenging.  
+  
+  ==Computing with Random Bit Streams==  
+  
+  "''To invent, all you need is a pile of junk and a good imagination.''" –– '''Thomas A. Edison''' (1847–1931)  
+  
+  Humans are accustomed to counting in a positional number system – [http://en.wikipedia.org/wiki/Decimal decimal] radix. Nearly all computer systems operate on another positional number system – [http://en.wikipedia.org/wiki/Binary_numeral_system binary] radix. From the standpoint of ''representation'', such positional systems are compact: given a radix ''b'', one can represent ''b<sup>n</sup>'' distinct numbers with ''n'' digits. However, from the standpoint of ''computation'', positional systems impose a burden: for each operation such as addition or multiplication, the signal must be "''decoded''", with each digit weighted according to its position. The result must be "''encoded''" back in positional form. Any student who has designed a [http://en.wikipedia.org/wiki/Binary_multiplier binary multiplier] in a course on [[EE2301  logic design]] can appreciate all the complexity that goes into wiring up such an operation.  
+  
+  ==== Logic that Operates on Probabilities ====  
+  
+  We advocate an alternative representation: 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. For instance, multiplication can be performed with a single AND gate; scaled addition can be performed with a multiplexer (MUX).  
+  
+  { align="center"  
+   [[Image:stochasticmultiplier.pngcenterthumb350px'''Multiplication''' with an AND gate. Here the variables represents the ''probabilities'' of obtaining a 1 versus a 0 in stochastic bit streams. The AND gate produces an output probability <math>c</math> that is the product of the of the input probabilities <math>a</math> and <math>b</math>.]]  
+    
+   [[Image:stochasticadder.pngthumb320px'''Scaled addition''' with a multiplexer (MUX).  
+  Given input probabilities <math>a</math>, <math>b</math> and <math>s</math>, the MUX produces an output probability <math>c = a s + (1  s) b</math>.]]  
+  }  
+  
+  We have developed a general method for synthesizing digital circuitry that computes on such stochastic bit streams. Our method can be used to synthesize arbitrary polynomial functions. Through polynomial approximations, it can also be used to synthesize nonpolynomial functions. Because the representation is uniform, with all bits weighted equally, the resulting circuits are highly tolerant of [http://en.wikipedia.org/wiki/Soft_error soft errors] (i.e., bit flips).  
+  
+  {  
+    
+  { style="background:#F0E68C"  
+   valign="top"  
+   width="100"  '''title''':  
+   width="500" [[Media:Qian_Riedel_Synthesizing_Logical_Computation_on_Stochastic_Bit_Streams.pdf  Synthesizing Logical Computation on Stochastic Bit Streams]]  
+   valign="top"  
+   '''authors''':  
+   [[Weikang Qian]] and [[Marc Riedel]]  
+   valign="top"  
+   '''presented at''':  
+   [http://www.dac.com/events/eventdetails.aspx?id=7737 Design Automation Conference], Anaheim, CA, 2008.<br>(Nominated as a '''Research Highlight''', [http://cacm.acm.org/ Communications of the ACM]).<br>  
+  }  
+   align=center width="70"   
+  <span class="plainlinks">  
+  [http://cadbio.com/wiki/images/6/64/Qian_Riedel_Synthesizing_Logical_Computation_on_Stochastic_Bit_Streams.pdf http://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>  
+  <br>  
+  [[Media:Qian_Riedel_Synthesizing_Logical_Computation_on_Stochastic_Bit_Streams.pdf  Paper]]  
+   align=center width="70"   
+  <span class="plainlinks">[http://mriedel.ece.umn.edu/files/Qian_Riedel_The_Synthesis_of_Robust_Polynomial_Arithmetic_with_Stochastic_Logic.ppt http://mriedel.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>  
+  <br> [http://mriedel.ece.umn.edu/files/Qian_Riedel_The_Synthesis_of_Robust_Polynomial_Arithmetic_with_Stochastic_Logic.ppt Slides]  
+  }  
+  
+  ====Logic that Generates Probabilities====  
+  
+  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 that have a specific probability of being one versus zero. If many different probability values are required, it can be difficult or expensive to generate all of these directly from physical sources. In this work, we demonstrate novel techniques for synthesizing combinational logic that transforms a set of ''source'' probabilities into different ''target'' probabilities.  
+  <!The problem I consider is: given a set ''S'' of ''n'' probabilistic inputs with probabilities ''p''<sub>1</sub>, ..., ''p''<sub><I>n</I></sub> of being one and a target probability ''q'', how can we synthesize a combinational circuit that takes inputs from the set ''S'' and produces an output with probability ''q'' of being one?>  
+  
+  [[File:Generate_Probabilities_Example.pngcenterframeGiven a set ''S'' of source probabilities {0.4, 0.5}, we can synthesize a combinational circuit to generate an arbitrary ''decimal'' output probability. The example shows how to generate 0.119. Each AND gate performs a multiplication and each inverter performs a "oneminus" operation.]]  
+  
+  {  
+    
+  { style="background:#F0E68C"  
+   valign="top"  
+   width="100"  '''title''':  
+   width="500"  [[Media:Qian_Riedel_Zhou_Bruck_Transforming_Probabilities_with_Combinational_Logic.pdf  Transforming Probabilities with Combinational Logic]]  
+   valign="top"  
+   '''authors''':  
+   [[Weikang Qian]], [[Marc Riedel]], [http://paradise.caltech.edu/~hzhou/ Hongchao Zhou], and [http://paradise.caltech.edu/bruck.html Jehoshua Bruck]  
+   valign="top"  
+   '''will appear in''':  
+   [http://tcad.polito.it/ IEEE Trans. on ComputerAided Design of Integrated Circuits and Systems], 2012.  
+   valign="top"  
+   '''presented at''':  
+   [http://www.iccad.com/events/eventdetails.aspx?id=1065C International Conference on ComputerAided Design], San Jose, 2009<br>(nominated for '''IEEE/ACM William J. McCalla ICCAD Best Paper Award''').  
+  }  
+   align=center width="70"   
+  <span class="plainlinks">  
+  [http://cadbio.com/wiki/images/d/db/Qian_Riedel_Zhou_Bruck_Transforming_Probabilities_with_Combinational_Logic.pdf http://mriedel.ece.umn.edu/wiki/images/0/04/Pdf.jpg]</span>  
+  <br>  
+  [[Media:Qian_Riedel_Zhou_Bruck_Transforming_Probabilities_with_Combinational_Logic.pdf  Paper]]  
+   align=center width="70"   
+  <span class="plainlinks">[http://mriedel.ece.umn.edu/files/Qian_Riedel_Bazargan_Lilja_The_Synthesis_of_Combinational_Logic_to_Generate_Probabilities.ppt http://mriedel.ece.umn.edu/wiki/images/3/36/Ppt.jpg]</span>  
+  <br> [http://mriedel.ece.umn.edu/files/Qian_Riedel_Bazargan_Lilja_The_Synthesis_of_Combinational_Logic_to_Generate_Probabilities.ppt Slides]  
+  }  
+  
+  Please see our "[[Papers,_Theses,_and_Presentations Publications]]" page for more of our papers on these topics.  
==Computing with Molecules==  ==Computing with Molecules==  
Line 112:  Line 189:  
Please see our "[[Papers,_Theses,_and_Presentations Publications]]" page for more of our papers on these topics.  Please see our "[[Papers,_Theses,_and_Presentations Publications]]" page for more of our papers on these topics.  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
==Computing with Nanoscale Lattices==  ==Computing with Nanoscale Lattices== 
Revision as of 23:33, 9 January 2016
"You see things; and you say, 'Why?' But I dream things that never were; and I say, 'Why not?'"–– George Bernard Shaw (1856 –1950)
Our research spans different disciplines ranging from digital circuit design, to algorithms, to mathematics, to synthetic biology. It tends to be inductive (as opposed to deductive) and conceptual (as opposed to applied). A recurring theme is building systems that compute in novel or unexpected ways with new and emerging technologies. Often, the task of analyzing the way things work in a new technology is straightforward; however the task of synthesizing new computational constructs is more challenging.
Contents
Computing with Random Bit Streams
"To invent, all you need is a pile of junk and a good imagination." –– Thomas A. Edison (1847–1931)
Humans are accustomed to counting in a positional number system – decimal radix. Nearly all computer systems operate on another positional number system – binary radix. From the standpoint of representation, such positional systems are compact: given a radix b, one can represent b^{n} distinct numbers with n digits. However, from the standpoint of computation, positional systems impose a burden: for each operation such as addition or multiplication, the signal must be "decoded", with each digit weighted according to its position. The result must be "encoded" back in positional form. Any student who has designed a binary multiplier in a course on logic design can appreciate all the complexity that goes into wiring up such an operation.
Logic that Operates on Probabilities
We advocate an alternative representation: 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. For instance, multiplication can be performed with a single AND gate; scaled addition can be performed with a multiplexer (MUX).
We have developed a general method for synthesizing digital circuitry that computes on such stochastic bit streams. Our method can be used to synthesize arbitrary polynomial functions. Through polynomial approximations, it can also be used to synthesize nonpolynomial functions. Because the representation is uniform, with all bits weighted equally, the resulting circuits are highly tolerant of soft errors (i.e., bit flips).

Logic that Generates Probabilities
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 that have a specific probability of being one versus zero. If many different probability values are required, it can be difficult or expensive to generate all of these directly from physical sources. In this work, we demonstrate novel techniques for synthesizing combinational logic that transforms a set of source probabilities into different target probabilities.

Please see our "Publications" page for more of our papers on these topics.
Computing with Molecules
“If I can’t create it, I don’t understand it.” –– Richard Feynman (1918–1988)
The theory of massaction kinetics underpins our understanding of biological and chemical systems. It is a simple and elegant formalism: molecular reactions define rules according to which reactants form products; each rule fires at a rate that is proportional to the quantities of the corresponding reactants that are present. Just as electronic systems implement computation in terms of voltage (energy per unit charge), we can conceive of molecular systems that compute in terms of chemical concentrations (molecules per unit volume). We are studying techniques for implementing a variety of computational constructs with molecular reactions such as logic, memory, arithmetic, and signal processing. Although conceptual, we target DNA Strand Displacement as our experimental chassis.

Computational Constructs
We have developed a strategy for implementing digital logic with molecular reactions. Based on a bistable mechanism for representing bits, we implement a constituent set of logical components, including combinational components such as AND, OR, and XOR gates, as well as sequential components such as D latches and D flipflops. Using these components, we build fullfledged digital circuits such as a binary counters and linear feedback shift registers.

We have developed a strategy for implementing arithmetic with molecular reactions – operations such as increments & decrements, multiplication, logarithms, and exponentiation. Try out our compiler: it translates arbitrary constructs from a Clike language into a robust implementation with molecular reactions.

We have developed a strategy for implementing signal processing with molecular reactions including operations such as filtering. We have demonstrated robust designs for FiniteImpulse Response (FIR), InfiniteImpulse Response (IIR) filters, and Fast Fourier Transforms (FFTs).


The impetus for this research is not computation per se. Molecular computation will never compete with conventional computers made of silicon integrated circuits for tasks such as number crunching. Chemical systems are inherently slow and messy, taking minutes or even hours to finish, and producing fragmented results. Rather, the goal is to create “embedded controllers” – viruses and bacteria that are engineered to perform useful molecular computation in situ where it is needed, for instance for drug delivery and biochemical sensing.
Please see our "Publications" page for more of our papers on these topics.
Computing with Nanoscale Lattices
"Listen to the technology; find out what it’s telling you.” –– Carver Mead (1934– )
In his seminal Master's Thesis, Claude Shannon made the connection between Boolean algebra and switching circuits. He considered twoterminal switches corresponding to electromagnetic relays. A Boolean function can be implemented in terms of connectivity across a network of switches, often arranged in a series/parallel configuration. We have developed a method for synthesizing Boolean functions with networks of fourterminal switches. Our model is applicable for variety of nanoscale technologies, such as nanowire crossbar arrays, as molecular switchbased structures.

The impetus for nanowirebased technology is the potential density, scalability and manufacturability. Many other novel and emerging technologies fit the general model of fourterminal switches. For instance, researchers are investigating spin waves. A common feature of many emerging technologies for switching networks is that they exhibit high defect rates.
We have devised a novel framework for digital computation with lattices of nanoscale switches with high defect rates, based on the mathematical phenomenon of percolation. With random connectivity, percolation gives rise to a sharp nonlinearity in the probability of global connectivity as a function of the probability of local connectivity. We exploit this phenomenon to compute Boolean functions robustly in the presence of defects.

Please see our "Publications" page for more of our papers on these topics.
Computing with Feedback
"A person with a new idea is a crank until the idea succeeds." –– Mark Twain (1835–1910)
The accepted wisdom is that combinational circuits (i.e., memoryless circuits) must have acyclic (i.e., loopfree or feedforward) 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.

Please see our Publications page for more of our papers on this topic.
Algorithms and Data Structures
"There are two kinds of people in the world: those who divide the world into two kinds of people, and those who don't." –– Robert Charles Benchley (1889–1945)
Consider the task of designing a digital circuit with 256 inputs. From a mathematical standpoint, such a circuit performs mappings from a space of <math>2^{256}</math> Boolean input values to Boolean output values. (The number of rows in a truth table for such a function is approximately equal to the number of atoms in the universe – <math>10^{77}</math> rows versus <math>10^{79}</math> atoms!) Verifying such a function, let alone designing the corresponding circuit, would seem to be an intractable problem. Circuit designers have succeeded in their endeavor largely as a result of innovations in the data structures and algorithms used to represent and manipulate Boolean functions. We have developed novel, efficient techniques for synthesizing functional dependencies based on socalled SATsolving algorithms. We use Craig Interpolation to generate circuits from the corresponding Boolean functions.

Please see our "Publications" page for more of our papers on this topic. (Papers on SATbased circuit verification, that is, not on squids.)
Mathematics
"Mathematics may be defined as the subject in which we never know what we are talking about, nor whether what we are saying is true." –– Bertrand Russell (1872–1970)
The great mathematician John von Neumann articulated the view that research should never meander too far down theoretical paths; it should always be guided by potential applications. This view was not based on concerns about the relevance of his profession; rather, in his judgment, realworld applications give rise to the most interesting problems for mathematicians to tackle. At their core, most of our research contributions are mathematical contributions. The tools of our trade are discrete math, including combinatorics and probability theory.

Please see our "Publications" page for more of our papers on this topic.