Cyclic Combinational Circuits

SPEAKER: Dr. Marc D. Riedel, CalTechABSTRACT: A combinational circuit is one that does not preserve any state information: the outputs are Boolean functions of the current inputs. In contrast, a sequential circuit is one that maintains an internal state: the outputs depend on the sequence of values, past and current, applied to the inputs. The accepted wisdom is that combinational circuits must have acyclic (i.e., loop-free or feed-forward) topologies. In fact, the idea that "combinational" and "acyclic" are synonymous terms is so thoroughly ingrained that many textbooks provide the latter as a definition of the former. And yet simple examples suggest that this is incorrect.In this talk, we advocate the design of cyclic combinational circuits (i.e., circuits with loops or feedback paths). We demonstrate that cycles can be used to optimize designs by reducing the number of gates (the area) and by reducing the length of the signal paths (the delay). On the theoretical front, we discuss lower bounds and we prove that certain cyclic circuits have half the number of gates of the best possible equivalent acyclic implementations. On the practical front, we describe an efficient approach for analyzing cyclic circuits, and we provide a general framework for synthesizing such circuits. On trials with benchmarks and circuits from industry, we obtained significant improvements in area and delay in nearly all cases. Based on these results, we suggest that it is time to re-write the definition: combinational might well mean cyclic.BIO: Marc Riedel is a Post-Doctoral Scholar at the California Institute of Technology. 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. He has held positions at Marconi Canada, CAE Electronics, Toshiba and Fujitsu Research Labs. His paper "The Synthesis of Cyclic Combinational Circuits" received the Best Paper Award at the Design Automation Conference (DAC) in 2003, and his Ph.D. Dissertation received the Charles H. Wilts Prize for the best doctoral research in E.E. at Caltech in 2004.Host: Dr. Keith M. Chugg, x.07294, chugg@usc.edu

Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248

Audiences: Everyone Is Invited

Contact: Mayumi Thrasher