 |
Wednesday, March 3, 1:30-2:30 p.m. HH-1112
|
Stephen A. Edwards
Dept. of Computer Science
Columbia University
|
Making Cyclic Circuits Acyclic
Cyclic circuits that do not hold state or oscillate are often the most convenient representation for certain functions, such as arbiters, and can easily be produced inadvertently in high-level synthesis, yet are troublesome for most circuit analysis tools. I'll present an algorithm that generates an acyclic circuit that computes the same function as a given cyclic circuit for those inputs where the cyclic circuit does not oscillate or hold state. The algorithm identifies all patterns on inputs and internal nodes that lead to acyclic evaluation orders for the cyclic circuit, which are represented as acyclic circuit fragments, then combines these to produce an acyclic circuit that can exhibit all of these behaviors.Experimental results suggest this potentially exponential algorithm is practical for small circuits and may be improved to handle larger circuits. This algorithm should make dealing with cyclic combinational circuits nearly as easy as dealing with their acyclic counterparts.Bio
Stephen A. Edwards received the B.S. degree in Electrical Engineering from the California Institute of Technology in 1992, and the M.S. and Ph.D degrees, also in Electrical Engineering, from the University of California, Berkeley in 1994 and 1997 respectively.He is currently an assistant professor in the Computer Science Department of Columbia University in New York, which he joined in 2001 after a three-year stint with Synopsys, Inc., in Mountain View, California.His research interests include embedded system design, domain-specific languages, and compilers. He is the author of Languages for Digital Embedded Systems (Boston: Kluwer, 2000) as well as numerous journal and conference papers. He is a recipient of the NSF CAREER Award.
| |
