Loading Events

« All Events

  • This event has passed.

Logic Synthesis for Nanoscale Lattices

April 20, 2012 @ 3:00 pm - 4:00 pm

Room 1037 (Emerging Technology Building- ETB)

Dr. Marc Riedel/Univ. of Minnesota


As current CMOS-based technology is approaching its anticipated limits, research is shifting to novel forms of nanoscale technologies, including molecular-scale self-assembled systems. Such systems often implement computation through arrays of crossbar-type switches.

This talk discusses strategies for synthesizing 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 neighbours; 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 talk 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 talk also addresses the problem of implementing Boolean functions with lattices of four-terminal switches in the presence of defects. We assume that such defects occur probabilistically. Our approach is predicated on the mathematical phenomenon of percolation. With random connectivity, percolation gives rise to a sharp non-linearity in the probability of global connectivity as a function of the probability of local connectivity. We exploit this phenomenon to compute Boolean functions robustly.  We show that the margins, defined in terms of the steepness of the non-linearity, translate into the degree of defect tolerance.

A significant tangent for this work is its mathematical contribution: lattice-based implementations present a novel view of the properties of Boolean function duality.

Biography:  Marc Riedel has been an Assistant Professor of Electrical and Computer Engineering at the University of Minnesota since 2006. He is also a member of the Graduate Faculty in Biomedical Informatics and Computational Biology. In 2004-2005, he was a lecturer in Computation and Neural Systems at Caltech. He has held positions at Marconi Canada, CAE Electronics, Toshiba, and Fujitsu Research Labs. He received his Ph.D. and his M.Sc. in Electrical Engineering at Caltech and his B.Eng. in Electrical Engineering with a Minor in Mathematics at McGill University. His Ph.D. dissertation titled “Cyclic Combinational Circuits” received the Charles H. Wilts Prize for the best doctoral research in Electrical Engineering at Caltech. His paper “The Synthesis of Cyclic Combinational Circuits” received the Best Paper Award at the Design Automation Conference. He is a recipient of the NSF CAREER Award.


April 20, 2012
3:00 pm - 4:00 pm