Robert K. Brayton

Robert K. Brayton

Auto-generated profile, based on publicly available information

Robert K. Brayton

University of California

Research Focus & Metrics

Academic Career Length

43Years (1984-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 November 2006
Verified
Conference Paper
Closed access
AMAlan Mishchenko
Alan Mishchenko
SCSatrajit Chatterjee
Satrajit Chatterjee
RBRobert Brayton
Robert Brayton
NENiklas Een
Niklas Een
The paper explores several ways to improve the speed and capacity of combinational equivalence checking based on Boolean satisfiability (SAT). State-of-the-art methods use simulation and BDD/SAT sweeping on the input side (i.e. proving equivalence of some internal nodes in a topological order), interleaved with attempts to run SAT on the output (i.e. proving equivalence of the output to constant 0). This paper improves on this method by (a) using more intelligent simulation, (b) using CNF-based SAT with circuit-based decision heuristics, and (c) interleaving SAT with low-effort logic synthesis. Experimental results on public and industrial benchmarks demonstrate substantial reductions in runtime, compared to the current methods. In several cases, the new solver succeeded in solving previously unsolved problems

1 January 2007
Verified
Conference Paper
Closed access
YYYu-Shen Yang
Yu-Shen Yang
SSSubarna Sinha
Subarna Sinha
AVAndreas Veneris
Andreas Veneris
RBRobert K. Brayton
Robert K. Brayton
In the digital VLSI cycle, a netlist is often modified to correct design errors, perform small specification changes or implement incremental rewiring-based optimization operations. Most existing automated logic rectification tools use a small set of predefined logic transformations when they perform such modifications. This paper first shows that a small set of predefined transformations may not allow rectification to exploit the full potential of the design. Then, it proposes an automated simulation-based methodology to "approximate" sets of pairs of functions to be distinguished (SPFDs) and avoid the memory/time explosion problem. This representation is used by a SAT-based algorithm that devises appropriate logic transformations to fix a design. The SAT method is later complemented by a greedy one that improves on runtime performance. An extensive suite of experiments documents the added potential of the proposed rectification methodology.


1 November 2006
Verified
Conference Paper
Closed access
SCSatrajit Chatterjee
Satrajit Chatterjee
AMAlan Mishchenko
Alan Mishchenko
RBRobert Brayton
Robert Brayton
Enumeration of bounded size cuts is an important step in several logic synthesis algorithms such as technology mapping and re-writing. The standard algorithm does not scale beyond 6 or 7 inputs because it enumerates all cuts and there are too many of them. We address the enumeration problem by introducing the notion of cut factorization. In cut factorization, one enumerates global and local cuts (collectively called the factor cuts) of the network, and uses these to generate other cuts. Depending on how global and local cuts are defined, one obtains different factorization schemes. In the first scheme, complete factorization, it is possible to generate any cut from factor cuts. However, complete factorization is expensive though less expensive than exhaustive enumeration. In the second scheme, partial factorization, there is no guarantee of generating all cuts from factor cuts. However, it is much faster, and produces good results. In this paper we also present two applications of factor cuts: LUT mapping and macrocell mapping. In LUT mapping, we find that considering only factor cuts guarantees depth optimality for most nodes in the network. For the remaining nodes, other cuts need to be generated from factor cuts and examined. In macrocell mapping, we focus on a particular 9-input macrocell, and use factor cuts as a heuristic method to improve depth by reducing structural bias. Factor cuts are used to map the macrocell as a whole whenever possible instead of mapping its parts separately. In this context factor cuts enable a new quality-run-time tradeoff between mapping parts of the macrocell separately (poor quality), and mapping using all 9-input cuts (long run-time)

1 January 1984
Verified
Book Chapter
Closed access
PDF file
RBRobert K. Brayton
Robert K. Brayton
GHGary D. Hachtel
Gary D. Hachtel
CMCurtis T. McMullen
Curtis T. McMullen
ASAlberto L. Sangiovanni-Vincentelli
Alberto L. Sangiovanni-Vincentelli

19 April 2011 in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Verified
Journal Article
Closed access
YYYu-Shen Yang
Yu-Shen Yang
SSSubarna Sinha
Subarna Sinha
AVAndreas Veneris
Andreas Veneris
RBRobert K. Brayton
Robert K. Brayton
During the very large scale integration design process, a synthesized design is often required to be modified in order to accommodate different goals. To preserve the engineering effort already invested, designers seek small logic structural transformations to achieve these logic restructuring goals. This paper proposes a systematic methodology to devise such transformations automatically. It first presents a simulation-based formulation to approximate sets of pairs of functions to be distinguished and avoid the memory/time explosion issue inherent with the original representation. Then, it uses this new data structure to devise the required transformations dynamically without the need of a static dictionary model. The methodology is applied to both combinational and sequential designs with transformations at a single or multiple locations. An extensive suite of experiments documents the benefits of the proposed methodology when compared to existing practices.