Robert Brayton

Digital Library

ACM Paris Kanellakis Theory and Practice Award

USA - 2006


For leading the development and practical realization of algorithms for logic synthesis and for electronic system simulation, thereby helping to create key enabling technologies for the Electronic Design Automation industry.

This award recognizes Robert Brayton's sustained leadership and contributions to the development of algorithms for logic synthesis and for electronic system simulation.

Dr. Brayton's research on logic synthesis has provided a key enabling technology in reducing the human effort required to design complex digital systems. Some of his important specific results concern methods of generating efficient logic circuit representations. The first set of results, embodied in the Espresso logic minimizer developed in collaboration with G. Hachtel, C. McMullen and A. Sangiovanni-Vincentelli, gave a practical technique for generating a two-level logic circuit, providing near-optimal results with reasonable performance, in addition to being the tool of choice for generating program-logic arrays. The second, developed in collaboration with C. McMullen first and then with Hachtel and Sangiovanni-Vincentelli, is the collection of algebraic methods, Boolean algorithms and design flows for multi-level logic that form the heart of most hardware synthesis tools in use today.

In the area of circuit simulation, Dr. Brayton's research enabled the development of circuit simulators with surprising power and generality. Key techniques here include the backward difference formula methods for solving differential-algebraic equations, developed in collaboration with F. Gustavson and G. Hachtel, and Sparse Tableau Analysis as a strategy for generating equations from circuits, developed in collaboration with G. Hachtel and F. Gustavson.

Dr. Brayton's leadership and technical contributions, and the guidance he has given other researchers over decades has had significant practical impact on the field of Electronic Design Automation - virtually no major digital circuit in the world is designed today without using some of the concepts pioneered by Dr. Brayton and his collaborators.